Check-then-act

The problem it solves

if (!map.has(key)) {
  map.set(key, computeIt());
}

Two threads run this at the same moment. Both call has, both are told the key is absent, both compute the value, both insert. The map ends with one entry, which is what you wanted — and two threads each believe they are the one that created it, which is not.

That second half is where the damage lives. In real systems the branch does more than insert: it sends the welcome email, charges the card, opens the connection, writes the audit row, registers the cleanup handler. One of those happens twice, and the map looks perfectly correct afterwards, so nothing points at the map.

The reason this deserves its own page rather than being folded into the lost update is that the variable being raced does not look like shared mutable state. has is a question. Questions feel safe to ask. Nobody writes if (!map.has(k)) and thinks “I am now holding a value that another thread may invalidate before I use it” — but that is exactly what has happened, and the answer starts going stale the instant it is returned.

The mechanism

Every check-then-act bug has the same three-part shape:

1. Read some shared state.
2. Decide something based on what you read.
3. Act on the decision.

Between 1 and 3 there is a window, and the correctness of 3 depends on 1 still being true. Nothing enforces that. The check was accurate when it was performed and describes a world that no longer exists by the time you rely on it.

Once you have the shape, you see it everywhere: if (!file.exists()) create(file), if (balance >= amount) withdraw(amount), if (instance == null) instance = new Singleton(), if (!isLocked()) lock(). The security literature calls it TOCTOU — time-of-check to time-of-use — and treats it as a vulnerability class, because a sufficiently motivated attacker can widen the window deliberately.

The fix is never to check more carefully. It is to make the check and the act one indivisible operation, so there is no interval in which the answer can rot.

What the enumeration shows

The default program is two threads doing exactly the pattern above, with an inserts counter recording how many of them believed they created the entry. Of 252 interleavings, 210 insert twice. The map ends with one key either way; the count is what reveals the double work.

Then try the fix that everybody tries first. Switch to check-then-act-half-locked, which takes a mutex around the write. It is a real lock, correctly acquired and released, and the bug is completely untouched — 8 of 14 interleavings still double-insert. The lock is in the wrong place: the race is between the check and the act, so a critical section that begins after the check protects nothing that was ever at risk.

Finally put-if-absent, which does the whole thing as one compare-and-swap. Every interleaving is correct, and the schedule count barely changes — the fix did not remove orderings, it removed the window those orderings were exploiting.

Comparing those three variants in sequence is the most useful thing on this page, because the wrong fix is genuinely plausible and produces code that looks synchronised.

The numbers worth carrying

• Unprotected check-then-act, two threads: 210 of 252 interleavings do the work twice.
• Lock around the write only: 8 of 14 still do. A lock in the wrong place is worth nothing.
• One indivisible operation: 0 of 252.

The general rule to carry: the window is the distance between the check and the act, measured in operations rather than nanoseconds. Anything you do between them — computing the value, logging, an extra validation — makes it wider.

Where it breaks down

The check and the act may be in different systems. if (!s3.exists(key)) s3.put(key, body) cannot be made atomic by any amount of local locking, because the state lives somewhere else. What you need is a conditional operation offered by that system — If-None-Match, a conditional put, an INSERT ... ON CONFLICT DO NOTHING — and if it does not offer one, the race is not fixable at your layer.

A lock only works if everyone takes it. A correct critical section around check-and-act is a genuine fix, and only for threads inside one process that all agree to use it. Two processes, two servers, or one process plus a database client mean the lock does not cover the state being checked. See distributed locks for why a lease across machines is weaker still.

Sometimes doing it twice is fine. If the action is idempotent — computing a cached value, creating a directory, setting a flag to true — the race costs duplicated work and nothing else, and the cheapest correct answer may be to accept it. Knowing when the double execution is harmless is as valuable as knowing how to prevent it.

What people get wrong

“I put a lock around it.” Around what? The window is between the check and the act, so the lock must be acquired before the check and held past the act. This page has a variant demonstrating the off-by-one that most people write.

“Making the read atomic fixes it.” An atomic read gives you an accurate answer to a question about the past. The answer still expires. See atomic operations.

“Double-checked locking solves this.” It solves the cost of the lock, not the race, and it was famously broken in Java before the 2004 memory model because the partially-constructed object could be published — a visibility bug hiding inside a correct-looking atomicity fix. If you cite it, cite the memory-model half too.

“It only happens under high load.” It happens whenever two requests for the same new key arrive close together, which is exactly what a cache miss on a popular key produces — see cache stampede. Popularity, not load, is the trigger.

In production

Every storage layer worth using offers a conditional primitive, and the whole point of them is to close this window: putIfAbsent and computeIfAbsent on a ConcurrentMap, SETNX in Redis, INSERT ... ON CONFLICT in Postgres, conditional expressions in DynamoDB, If-None-Match on HTTP, O_EXCL on open. When you find yourself writing check-then-act, the first question is whether the thing you are checking already offers one of these.

The second pattern worth knowing is doing the work optimistically and letting the constraint arbitrate: both threads compute the value, both attempt to insert, one wins on a unique index and the other discards its result. That trades duplicated computation for a guarantee that is enforced by the database rather than by everyone remembering a convention — and it is the same shape as idempotency keys in a message consumer.

computeIfAbsent deserves a specific caution: it holds a per-bin lock while your mapping function runs, so a function that is slow, or that touches the same map, can block or deadlock. Compute outside, insert conditionally.

The follow-up questions

“What is wrong with if (!map.has(k)) map.put(k, v)?” — Both threads can pass the check. Say what the branch does in the real system, because that is where the damage is.

“You added a lock and it still happens. Why?” — The lock starts after the check. This is the diagnosis worth being able to make quickly.

“How would you fix it without a lock?” — A conditional operation: putIfAbsent, compare-and-swap, a unique constraint. Name the one that fits the storage you are actually using.

“When is it acceptable to leave it?” — When the action is idempotent and duplicated work is cheap. Saying so confidently is a better answer than reflexively locking.