9.5.5 — The Concurrency Problem Set

Interviewers reuse about ten concurrency problems. They look like puzzles, and each one is really a check on whether you can express a specific guarantee with the right primitive. This page works through all of them, and after the first three you will notice that most of them are the same problem in different clothing.

Two helpers are used throughout. The first is the Semaphore from 9.5.2, which is the workhorse for every ordering problem here. The second is a broadcast gate, which is a condition variable with the smallest interface that works:

class Gate {
  #waiters: Array<() => void> = [];

  async until(condition: () => boolean): Promise<void> {
    while (!condition()) {                                        // (1) always a while
      await new Promise<void>(r => this.#waiters.push(r));        // (2) sleep until woken
    }
  }

  wakeAll(): void {
    const woken = this.#waiters;                                  // (3) take the list first
    this.#waiters = [];
    for (const wake of woken) wake();                             // (4) everyone re-checks
  }
}

(1) The while is mandatory for the reasons in 9.5.2: being woken is a hint to re-check, never a promise that the condition holds. (2) A parked resolver, the same deferred trick used everywhere in this chapter. (3) Swap the list out before calling anyone, or a waiter that immediately re-parks itself would be added to the list you are still iterating over. (4) Wake everyone and let each decide whether it is their turn. This is broadcast, and it is the safe default; signal is an optimisation you apply only when you can prove exactly one waiter can proceed.

1. Print in order

The problem. Three functions, first, second and third, are called on three separate threads in an arbitrary order. Make the output always be first second third.

What it is testing. Whether you know that a semaphore starting at zero is a signal, not just a limiter.

const canRunSecond = new Semaphore(0);          // (1) starts closed
const canRunThird  = new Semaphore(0);

async function first(): Promise<void> {
  print("first");
  canRunSecond.release();                       // (2) open the next gate
}

async function second(): Promise<void> {
  await canRunSecond.acquire();                 // (3) blocks until first() ran
  print("second");
  canRunThird.release();
}

async function third(): Promise<void> {
  await canRunThird.acquire();
  print("third");
}

(1) Zero permits means the first acquire blocks. (2) Releasing a permit is the signal that the prerequisite is done. (3) Whichever thread arrives here first simply waits, so the calling order stops mattering.

The generalisation, which is the actual answer: to enforce an order, give each step a gate that only its predecessor can open. Every remaining ordering problem on this page is a variation on that one sentence.

2. Print foobar alternately, n times

The problem. Two threads. One can only print foo, the other only bar. Output must be foobarfoobar... exactly n times.

What it is testing. Whether you can build a two-way handoff without a shared "turn" variable that would itself need protecting.

const fooTurn = new Semaphore(1);               // (1) foo goes first
const barTurn = new Semaphore(0);

async function foo(n: number): Promise<void> {
  for (let i = 0; i < n; i++) {
    await fooTurn.acquire();                    // (2) wait for my turn
    print("foo");
    barTurn.release();                          // (3) hand the turn over
  }
}

async function bar(n: number): Promise<void> {
  for (let i = 0; i < n; i++) {
    await barTurn.acquire();
    print("bar");
    fooTurn.release();
  }
}

(1) The starting permits decide who goes first, which is the whole configuration. (2) and (3) are the handoff: each thread waits for its own semaphore and releases the other one. Neither ever touches shared data, so there is nothing to lock.

Notice how a semaphore's lack of an owner is doing real work here. foo releases a permit that bar will acquire. A mutex could not express this, because a mutex may only be released by the thread holding it.

3. Print zero, even, odd

The problem. Three threads. zero may only print 0, even only even numbers, odd only odd. Output must be 0102030405... up to n.

What it is testing. The same handoff as before, but with a decision about which gate to open next.

const zeroTurn = new Semaphore(1);
const oddTurn  = new Semaphore(0);
const evenTurn = new Semaphore(0);

async function zero(n: number): Promise<void> {
  for (let i = 1; i <= n; i++) {
    await zeroTurn.acquire();
    print("0");
    if (i % 2 === 1) oddTurn.release();          // (1) the number about to print is odd
    else evenTurn.release();
  }
}

async function odd(n: number): Promise<void> {
  for (let i = 1; i <= n; i += 2) {
    await oddTurn.acquire();
    print(String(i));
    zeroTurn.release();                          // (2) always back to zero
  }
}

async function even(n: number): Promise<void> {
  for (let i = 2; i <= n; i += 2) {
    await evenTurn.acquire();
    print(String(i));
    zeroTurn.release();
  }
}

(1) zero is the coordinator: after printing, it decides who is allowed to go next. (2) Both number threads return control to zero, which is what produces the alternating 0.

The lesson worth carrying: when a sequence has a repeating element, make that element the coordinator. Trying to make odd and even hand off to each other directly requires them to know each other's schedule, and the code gets much worse.

4. Multithreaded FizzBuzz

The problem. Four threads: one prints fizz for multiples of 3, one prints buzz for multiples of 5, one prints fizzbuzz for multiples of 15, and one prints the number otherwise. Output must be the ordinary FizzBuzz sequence.

What it is testing. Whether you notice that a chain of semaphores stops working when the next gate depends on a computed value. Each thread must wait for a condition rather than for a specific predecessor.

let current = 1;                                                    // (1) shared counter
const gate = new Gate();

async function role(n: number, mine: (v: number) => boolean, say: (v: number) => string) {
  while (true) {
    await gate.until(() => current > n || mine(current));            // (2) wait for my kind
    if (current > n) return;                                         // (3) exit condition
    print(say(current));
    current++;                                                       // (4) advance
    gate.wakeAll();                                                  // (5) let everyone re-check
  }
}

const isFizz     = (v: number) => v % 3 === 0 && v % 5 !== 0;
const isBuzz     = (v: number) => v % 5 === 0 && v % 3 !== 0;
const isFizzBuzz = (v: number) => v % 15 === 0;
const isNumber   = (v: number) => v % 3 !== 0 && v % 5 !== 0;

(1) One shared counter that only the thread whose turn it is may modify. (2) The wait is on a predicate, not on a named predecessor — that is the structural change from the previous three problems. (3) Every waiter must be able to exit, or three threads hang forever after the last number is printed; this line is the one candidates most often forget. (4) Advancing is safe because only the matching thread reaches it. (5) Broadcast, because you do not know which of the other three is now eligible.

The general lesson: when the next actor is decided by data rather than by position, stop chaining semaphores and start waiting on a condition. Semaphores encode a fixed order; conditions encode a rule.

The threaded-language caveat. In Node this is correct as written, because current++ and the predicate check cannot be interrupted — there is no preemption between synchronous statements. In Java or C++ the shared counter needs a mutex held across the predicate check and the increment, which is precisely the mutex-plus-condition-variable pairing from 9.5.2. Saying that difference out loud is worth doing, because it shows you know which guarantees came from the language and which you built.

5. Building H₂O

The problem. Threads call hydrogen() and oxygen(). Let them through only in groups of two hydrogens and one oxygen, and no thread from the next molecule may print until the current one is complete.

What it is testing. Two guarantees at once — a ratio and a grouping — and whether you realise they need two different tools.

const hSlots = new Semaphore(2);                 // (1) at most 2 hydrogens per molecule
const oSlots = new Semaphore(1);                 // (1) at most 1 oxygen per molecule
const complete = new Barrier(3);                 // (2) nobody leaves until all three arrive

async function hydrogen(): Promise<void> {
  await hSlots.acquire();
  print("H");
  await complete.wait();                         // (3) wait for the molecule to be whole
  hSlots.release();                              // (4) only now may the next molecule start
}

async function oxygen(): Promise<void> {
  await oSlots.acquire();
  print("O");
  await complete.wait();
  oSlots.release();
}

(1) The permit counts give you the ratio. Three hydrogens cannot print in a row, because only two permits exist. (2) A barrier releases all its participants only when the full count has arrived, which is what makes them a group. (3) Each atom announces itself, then waits for the molecule to be complete. (4) Releasing the permit after the barrier is the critical ordering. Release before it, and a hydrogen from the next molecule could slip in and print while this molecule is still assembling, breaking the grouping guarantee.

The lesson: a ratio and a grouping are separate requirements needing separate mechanisms — permits for the ratio, a barrier for the grouping. Candidates who try to express both with one semaphore produce code that satisfies the counts and violates the batching, which is exactly the bug the problem is designed to expose.

6. Dining philosophers

The problem. Five philosophers sit around a table with five forks between them. Each needs both neighbouring forks to eat. The obvious solution deadlocks.

Why it deadlocks. If every philosopher picks up their left fork first, and they all do it simultaneously, all five forks are held and all five philosophers wait for their right fork. That is a perfect circular wait — Coffman's fourth condition (9.5.3) — arranged in a ring.

What it is testing. Whether you reach for lock ordering, and whether you can name the alternatives and their costs.

const forks = Array.from({ length: 5 }, () => new Mutex());

async function philosopher(seat: number): Promise<void> {
  const left = seat;
  const right = (seat + 1) % 5;
  const [firstFork, secondFork] = [left, right].sort((a, b) => a - b);   // (1)

  await forks[firstFork].withLock(async () => {                          // (2)
    await forks[secondFork].withLock(async () => {
      eat(seat);
    });
  });
}

(1) The one line that fixes it. Every philosopher takes the lower-numbered fork first, regardless of whether it is their left or right. (2) Now consider philosopher 4, whose forks are 4 and 0. Everyone else takes their left fork, but philosopher 4 takes fork 0 first. That asymmetry is what breaks the ring: a cycle would require somebody to hold a higher number while waiting for a lower one, and no philosopher ever does.

Three alternative solutions, worth naming to show breadth.

Limit the diners. A semaphore with four permits means at most four philosophers ever reach for forks, so at least one always gets both. This breaks hold-and-wait by limiting demand and is easy to explain, but it artificially caps concurrency.

Make the pickup atomic. Take both forks under one table-wide lock, or neither. Simple and correct, and it serialises all pickups, which is the coarse-grained trade from 9.5.2.

Timed acquisition. Try for the second fork with a timeout; on failure, put the first one down and retry after a jittered delay. This escapes the deadlock rather than preventing it, and without the jitter it livelocks — all five philosophers put down and pick up in perfect unison forever.

The transferable version: this is the wallet transfer from 9.5.2, with five participants instead of two. Any time code takes two locks, sort them. It is the same fix at any table size.

7. A bounded blocking queue

The problem. Implement a queue with a fixed capacity where enqueue blocks when full and dequeue blocks when empty, safe for many producers and many consumers.

This is BoundedQueue from 9.5.4, and rather than repeat it, here are the three details that separate a passing answer from a strong one.

Wait in a loop, not an if. With several consumers, being woken does not mean the item is still there — another consumer may have taken it first. Re-check the condition every time you wake.

Wake the right side. Removing an item frees space, so it must wake a producer. Adding an item creates work, so it must wake a consumer. Using one wait list for both means you can wake a producer when what you needed was a consumer, and the queue quietly stalls with items in it and idle consumers.

size() is a snapshot, not a fact. By the time the caller reads the number you returned, it may already be wrong. This makes if (queue.size() > 0) queue.take() a check-then-act race, which is why blocking queues offer take() and poll(timeout) rather than encouraging callers to look before they leap. Being able to explain why a correct size() is still a dangerous API is a genuinely senior observation.

8. A thread-safe cache with expiry

The problem. A cache where entries expire after a time-to-live, safe under concurrent access, and where a miss on a hot key must not trigger a hundred identical database queries at once.

What it is testing. The stampede. Everyone gets the locking right and most people miss the fact that expiry creates a synchronised miss across every caller at the same instant.

type Entry<V> = { value: V; expiresAt: number };

class TtlCache<K, V> {
  #entries = new Map<K, Entry<V>>();
  #inFlight = new Map<K, Promise<V>>();                       // (1) the anti-stampede map

  constructor(private readonly ttlMs: number, private readonly load: (k: K) => Promise<V>) {}

  async get(key: K): Promise<V> {
    const hit = this.#entries.get(key);
    if (hit && hit.expiresAt > Date.now()) return hit.value;   // (2) fresh: done

    const pending = this.#inFlight.get(key);
    if (pending) return pending;                               // (3) somebody is already loading

    const promise = this.load(key)                             // (4) start exactly one load
      .then(value => {
        this.#entries.set(key, { value, expiresAt: Date.now() + this.ttlMs });
        return value;
      })
      .finally(() => { this.#inFlight.delete(key); });         // (5) always clean up

    this.#inFlight.set(key, promise);                          // (6) publish before awaiting
    return promise;
  }
}

(1) The map of in-flight loads is the entire trick. (2) The fast path touches nothing shared. (3) A caller arriving during a load waits on the existing promise rather than starting its own. A hundred concurrent misses on one key produce one database query and a hundred satisfied callers. This is usually called single-flight. (4) Only the first caller reaches this line. (5) The finally matters as much as it does for a lock: if a failed load left its promise in the map, every future caller would get the same rejection forever and the key would be permanently poisoned. (6) Publishing before returning is what makes step (3) work, and in Node it is safe because there is no await between the check on line (3) and this line — no other request can interleave. In a threaded language this whole sequence needs computeIfAbsent or a lock.

Two refinements a strong answer adds.

Expiry needs jitter too. If a thousand keys are loaded during a deploy, they all expire at the same millisecond and you get a synchronised stampede across every key at once — the single-flight map does not help, because the keys are different. Setting the TTL to ttl ± 10% random spreads the renewals out.

Serving stale beats blocking. For most read paths, returning the expired value immediately while refreshing in the background gives better latency and protects the database during an outage. That is a product decision about staleness, and it should be stated as one rather than assumed.

9. A concurrent map

The problem. A map safe for concurrent reads and writes that does not serialise everything behind one lock.

The answer is striping, built in 9.5.2: a fixed number of locks, key hashed to one of them, so unrelated keys never contend.

The interesting part is what a striped map cannot promise, and the interviewer is usually fishing for exactly this.

size() is approximate. Counting means visiting every stripe, and by the time you reach the last one the first has changed. You can lock all stripes at once for an exact count, but that stops the entire map and is almost never worth it.

Iteration sees a smear. An iterator that walks the stripes gives you a view that was never true at any single moment: it may include an entry added after you started, or miss one that was there when you began. This is called a weakly consistent iterator, and it is a deliberate trade, not a bug.

Two operations do not compose. if (!map.has(k)) map.set(k, v) is a check-then-act race even when both individual calls are perfectly thread-safe. This is the single most important thing to say about concurrent collections: thread-safe methods do not make thread-safe sequences. That is why these APIs ship compound operations — putIfAbsent, computeIfAbsent, merge — which do the check and the act under one lock. Reaching for those instead of writing the if is the mark of somebody who has been bitten.

10. Parallel merge sort

The problem. Sort a large array using multiple cores.

What it is testing. Whether you understand that this is CPU-bound work, so it needs actual parallelism rather than concurrency, and whether you know when to stop splitting.

The structure is fork-join: split the array, sort both halves in parallel, merge the results.

async function parallelSort(items: number[], depth = 0): Promise<number[]> {
  if (items.length < 10_000 || depth >= MAX_DEPTH) {          // (1) stop splitting
    return items.slice().sort((a, b) => a - b);
  }
  const mid = items.length >> 1;
  const [left, right] = await Promise.all([                    // (2) both halves at once
    runOnWorker(items.slice(0, mid), depth + 1),
    parallelSort(items.slice(mid), depth + 1),                 // (3) reuse this thread
  ]);
  return merge(left, right);                                   // (4) sequential, and unavoidable
}

(1) The cutoff is the whole design. Below some size, the cost of moving data to another thread exceeds the cost of just sorting it, and a naive implementation that splits down to single elements is slower than the plain sort. The depth cap matters too: with eight cores there is no point creating a thousand parallel tasks, because they will queue and add switching cost without adding capacity (9.5.1).

(2) The two halves are independent, which is why merge sort parallelises well: there is no shared mutable state between them at all and therefore no locking anywhere in this algorithm.

(3) Send one half to a worker and do the other half here. Sending both and waiting idle wastes the current thread.

(4) The merge is inherently sequential, and it is what limits your speedup. This is Amdahl's law made concrete (2.4): if 10 percent of the work cannot be parallelised, then infinite cores still leave you ten times faster at best.

The Node-specific trap that makes this problem worth asking. Real threads in Node are worker_threads, and by default sending an array to a worker copies it, which for a large array can cost more than the sorting saved. The fix is to keep the data in a SharedArrayBuffer so workers sort regions of the same memory, or to transfer ownership of the buffer rather than copying it. That is 9.5.6, and noticing the copy before you are told about it is the point of the question.

11. What all of these have in common

Ten problems, four ideas.

Ordering problems (1, 2, 3, 4) are all wait for my turn, act, open the next gate. Use semaphores when the order is fixed, and a condition on a shared variable when the next actor depends on data.

Grouping problems (5) need a barrier for the group and permits for the ratio, and the release must come after the barrier.

Deadlock problems (6) are solved by sorting the resources. Every time.

Shared-data structures (7, 8, 9, 10) are all about the same trap: individually safe operations do not make a safe sequence. The cures are compound operations that do the check and the act together, a stored promise to collapse duplicate work, and striping so unrelated keys never meet.

If a problem you have not seen appears in an interview, sort it into one of those four and the tool follows from the category.

Next: 9.5.6 is about the runtime you actually ship on — what JavaScript gives you for free, what it does not, and what changes when you introduce real threads.

Recall

• Ordering: a semaphore starting at zero is a signal. Give each step a gate only its predecessor can open. Fixed order means chained semaphores; data-dependent order means waiting on a condition.
• foobar and zero-even-odd: each thread waits on its own semaphore and releases the other one. A mutex cannot do this, because a mutex may only be released by its holder.
• FizzBuzz: wait on a predicate over a shared counter, broadcast after advancing, and give every waiter an exit condition or the threads hang after the last number.
• H₂O: permits give the ratio, a barrier gives the grouping, and the permit must be released after the barrier or the next molecule leaks in.
• Dining philosophers: sort the forks. Alternatives are limiting diners to N−1, one lock for the whole pickup, or timed retry with jitter — each with a stated cost.
• Bounded queue: wait in a loop; wake the correct side; size() is a snapshot, so if (size > 0) take() is a race.
• TTL cache: store the in-flight promise so a hundred misses cause one load, clean it up in finally, and jitter the TTL so keys do not expire together.
• Concurrent map: thread-safe methods do not make thread-safe sequences. Use computeIfAbsent-style compound operations. size() is approximate and iteration is weakly consistent.
• Parallel sort: cut off below a size threshold and a depth cap, keep the merge sequential (Amdahl), and beware the copy cost of sending data to a worker.

Self-test: Why can a semaphore hand off a turn where a mutex cannot? What happens in FizzBuzz if you forget the exit condition? Why must the H₂O permit be released after the barrier and not before? Give the four solutions to dining philosophers with one cost each. Why is if (!map.has(k)) map.set(k, v) unsafe on a thread-safe map?

Quiz Bank

FoundationalPrint in order, foobar, and zero-even-odd are usually presented as three separate problems. Show that they are one problem, and give the general solution.

They are all turn-taking: several threads must produce output in a fixed sequence, and each thread may only produce its own kind of output. The general solution is one sentence: give every step a gate that only its predecessor can open.

A gate is a semaphore that starts with zero permits. Zero permits means the first acquire blocks, so the thread waits. Releasing a permit is the signal that the previous step is done.

Print in order is a straight chain: first releases the gate for second, which releases the gate for third. The threads may be started in any order and the output does not change, because arrival order and permission order are separate things.

FooBar is a two-node cycle instead of a chain: foo waits on its own gate and opens bar's; bar waits on its own and opens foo's. The starting permits — one for foo, zero for bar — decide who begins, and that single number is the entire configuration.

Zero-even-odd is a cycle with a branch. zero always runs, and then chooses which of the other two gates to open based on whether the next number is odd or even. Both of them always return control to zero.

The property that makes all three work, and the thing to say out loud: no thread ever reads or writes shared data, so there is nothing to lock. The only shared thing is permission, and permission is exactly what a semaphore is for. That is why the semaphore's lack of an owner matters here: thread A releases a permit that thread B acquires, which a mutex forbids by design.

Where the technique stops working, which is the natural follow-up. When the next thread is decided by a computed value rather than a fixed position — multithreaded FizzBuzz — a chain of gates cannot express it, because you would need a gate per possible outcome and the coordinator would have to know the whole schedule. At that point you switch to waiting on a condition over a shared counter and broadcasting after each advance. Fixed order means chained semaphores; a rule means a condition.

FoundationalWhy does the naive dining philosophers solution deadlock, and give three fixes with the cost of each.

The deadlock. Each philosopher picks up their left fork and then their right. If all five do this at the same moment, all five forks are held and every philosopher is waiting for a fork held by the neighbour on their right. The wait-for graph is a five-node ring, which is Coffman's circular-wait condition arranged as literally a circle (9.5.3).

The detail that makes it a good teaching problem is that no single philosopher does anything unreasonable. Each takes two forks it genuinely needs, in a perfectly sensible order. The failure is entirely in the interaction, which is why it cannot be found by reviewing one philosopher's code.

Fix one: lock ordering. Number the forks and require everyone to take the lower number first. Four philosophers take their left fork first, and one — the one whose forks are 4 and 0 — takes their right first. That asymmetry breaks the ring, because a cycle needs somebody holding a high number while waiting for a low one, and the rule forbids it. Cost: essentially none at runtime. The real cost is that every developer must follow the convention, so it needs to be written down and, ideally, enforced by a helper that does the sorting for you.

Fix two: limit the number of diners. A semaphore with four permits means at most four philosophers ever reach for forks, so at least one always finds both free. This breaks hold-and-wait by capping demand. Cost: it artificially reduces concurrency, and choosing the number requires knowing the ring size, so the solution does not generalise to a graph of arbitrary shape.

Fix three: take both forks atomically. One lock over the whole table; you take both forks or neither. Cost: every pickup in the system serialises, which for five philosophers is fine and for five thousand is a bottleneck. This is coarse-grained locking, and its virtue is that it is obviously correct.

Fix four, worth mentioning to show you know the difference between preventing and escaping: timed acquisition. Try for the second fork with a timeout, and on failure put the first one down and retry. Cost: this does not prevent the deadlock, it escapes it, so you pay the timeout every time it occurs. And without random jitter on the retry it converts the deadlock into a livelock, with all five philosophers putting down and picking up in perfect unison forever.

The one to choose is ordering, and the reason to say so explicitly is that it is the same fix as the two-wallet transfer, the same fix as two rows in a database transaction, and the same fix at any number of participants. One technique, unlimited table size.

AppliedImplement a cache with a time-to-live that does not stampede the database when a hot key expires. Explain every part that is not obvious.

The problem the naive version has. A correct-looking TTL cache checks whether the entry is fresh, and on a miss it loads from the database and stores the result. Under load on a hot key, the expiry moment causes every concurrent request to miss simultaneously — they all check freshness before any of them has finished loading — so a hundred identical queries hit the database at once. The cache made things worse than no cache at that instant, because at least without a cache the load would have been spread out.

The fix is a second map holding the in-flight promise for each key.

const pending = this.#inFlight.get(key);
if (pending) return pending;                    // join the load already running

The first caller to miss starts the load and immediately publishes its promise. Every subsequent caller finds that promise and awaits it instead of starting its own. One query, a hundred satisfied callers. This is single-flight, and it is the answer to the question being asked.

The parts that are not obvious.

Publish the promise before awaiting anything. The whole scheme depends on the second caller finding the entry. In Node this works because there is no await between checking the map and setting it, so no other request can interleave in that window. In a threaded language the check and the set must be one atomic operation — computeIfAbsent — because otherwise two threads both find it absent and both start loading, which is the very bug you were fixing.

Delete the in-flight entry in a finally, not on success. If a failed load left its rejected promise in the map, every later caller would join that same rejected promise and get the old error forever. The key would be permanently poisoned and only a restart would clear it. This is the same finally discipline as releasing a lock, for the same reason.

Jitter the expiry. Single-flight solves a stampede on one key. It does nothing about a thousand different keys all loaded during a deploy and therefore all expiring in the same millisecond. Setting the TTL to a random value within ten percent of the target spreads the renewals across a window and turns a spike into a hum.

Decide about stale reads explicitly. Serving the expired value immediately while refreshing in the background gives better latency and keeps the service usable when the database is struggling. That is a real improvement and it is also a product decision about how stale is acceptable, so it should be stated rather than assumed. For a price displayed on a page, thirty seconds stale is fine. For a permission check, it is not.

Bound the cache. A cache with a TTL and no size limit still grows without bound if new keys keep arriving, because entries are only removed when someone asks for them again. It needs an eviction policy as well as an expiry policy, and those are two different things (9.7.30 builds the LRU that provides it).

InterviewYou are given a thread-safe map. A colleague writes: if the key is absent, compute the value and put it. Explain what is wrong and what the general principle is.

What is wrong. Both operations are individually thread-safe and the sequence is not. Two threads can both run has(key), both get false, both compute, and both write. Depending on the map, the result is a duplicate computation, or a lost write, or two different objects handed to two callers who each believe they hold the only one.

That last case is the dangerous one and it is worth spelling out. If the value is a database connection, a file handle, or a lock, then two threads holding two supposedly-unique objects for the same key is a correctness failure that will show up much later and somewhere else entirely. A duplicate computation wastes CPU; a duplicate resource corrupts state.

The general principle, and the sentence to say: thread safety does not compose. A collection guarantees that each individual method is atomic. It guarantees nothing about a sequence of methods, because the lock is released between them, and the gap is exactly the check-then-act window from 9.5.1. Every "safe" collection in every language has this property, and it is the single most common misunderstanding about them.

The fix is a compound operation — one call that does the check and the act under the collection's own lock:

const value = map.computeIfAbsent(key, k => expensive(k));

This is why every concurrent map API ships putIfAbsent, computeIfAbsent, merge and replace(key, expected, next). They exist precisely because the two-call version is unsafe, and their presence in the API is a signal that the library authors expect you to need them.

Two related things worth adding unprompted.

The same trap applies to the compound you write yourself. if (queue.size() > 0) queue.take() is the same bug wearing different clothes. The size was true when you read it and may be false when you act on it, which is why blocking queues offer take() and poll(timeout) rather than encouraging you to look first.

In Node, this exact sequence is safe, provided there is no await between the check and the write, because nothing can interleave between two synchronous statements. Put an await in the middle — which computeIfAbsent with an async loader requires — and the race is back, which is why the cache in section 8 stores the promise rather than awaiting the value before writing. Knowing which guarantees came from your runtime and which you built yourself is what makes this answer senior rather than merely correct.

StaffTake one of these puzzle problems and turn it into a real production design: build the ordered per-partner delivery of the H2O grouping problem, at 50,000 events per minute, on multiple machines.

The puzzles teach mechanisms in isolation. Production adds four things the puzzles carefully exclude: failure, restart, scale-out and observability. Working through what changes is more instructive than the puzzle itself.

What the puzzle gives you. H₂O is a batching problem: gather exactly N of one kind and M of another, release them as a group, and do not let the next group start early. Real batching problems are everywhere — group notifications so a user gets one digest rather than forty emails, batch database writes so you do one insert of a hundred rows rather than a hundred inserts, batch calls to a partner API that charges per request.

What breaks immediately in production.

A barrier waits forever, and production cannot. The puzzle guarantees that three atoms eventually arrive. Reality does not: you may collect one hydrogen and no oxygen ever comes. So the barrier needs a timeout, and the timeout needs a decision attached — flush the partial group, or park it, or fail it. That decision is a business question, not a technical one. For a notification digest, flush after five minutes even if the batch is small. For a database write batch, flush on size or on age, whichever comes first, which is why every real batcher has both a maxSize and a maxWaitMs.

A crash loses the group. The puzzle's participants live in memory. A production batcher holding forty pending events in memory loses all forty when the process restarts, which violates any no-loss requirement. So the pending items must be durable — a database row per item with a batch_id, or a durable queue — and the batcher works on stored state rather than on in-memory arrivals. The barrier stops being a synchronisation primitive and becomes a query: are there N unbatched items, or is the oldest one older than the deadline?

Multiple machines break the count. Two instances each holding a partial batch produce two half-groups instead of one whole one. The semaphore permits and the barrier were process-local, and neither survives scale-out — the same lesson as the mutex in 9.5.2. The fix is to partition by the key you batch on, so all events for one partner reach one instance, and that instance is the only one forming batches for it. Now the in-memory mechanism is correct again within its partition, which is the general move: make the shared thing unshared by ownership.

Applying that to the webhook platform at 50,000 per minute.

Partition by partner id, so one partner's events land on one consumer, which gives ordering and makes batching local at once. Persist every event on arrival and acknowledge with 202, so nothing is lost before the batcher sees it. The batcher then works from stored rows: take up to a hundred events for this partner, or fewer if the oldest has waited two seconds, and deliver them as one call. Grouping is now a query with a limit and an age check rather than a barrier, and it survives restart because the state is in the database.

Delivery uses a bounded pool with a per-destination sub-limit and a circuit breaker, so one dead customer endpoint cannot consume the whole pool (9.5.4). Failed batches retry with jittered backoff and then park, and — a detail the puzzle version never raises — a failed batch must not block the partner's ordered stream forever, so you need an explicit rule: either the stream halts at the failure and the operator is alerted, which preserves strict ordering, or the failed batch parks and the stream continues, which preserves throughput and breaks ordering. You cannot have both, and choosing consciously is the design.

Observability is not optional at this size. Per-partner backlog depth, oldest unbatched age, average batch size, and delivery pool utilisation. Average batch size is the one people forget and it is the most diagnostic: if it sits at one, your batching is doing nothing and the wait is pure added latency; if it constantly hits the maximum, the batch limit is your bottleneck rather than a safety valve.

The general lesson to close on. Every puzzle primitive on this page has a production counterpart, and the translation follows the same three rules each time. In-memory becomes durable, because processes restart. Unbounded waits become deadlines, because participants sometimes never arrive. Process-local becomes partitioned, because there is always more than one machine. The mechanism you learned from the puzzle is still exactly right — it just now operates on stored state, with a timeout, inside one owner's partition.