The question this answers
What is the smallest region of this function that must be protected, and how do I know I have not made it one statement too small?
A reserveSeat(showId, seatId) handler: look up the show, verify the seat is free, fetch the user's loyalty tier over the network, compute a price, mark the seat taken, and append an audit row.
show.seats — a map from seat id to null or a booking id — held in memory and reachable from every request task. The loyalty lookup and the audit sink are not shared state; they are I/O.
A seat is reserved by at most one booking: for every seat id, seats[seatId] transitions from null to a booking id exactly once, and no two bookings observe it as null.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The two failure directions are not symmetric
Getting the region wrong fails in two directions, and they cost completely different things. Too wide costs throughput: correctness is preserved, the system is simply slower than it needed to be, and the damage is proportional to how much unrelated work you dragged inside. Too narrow costs correctness: the invariant breaks, silently, on a schedule your tests do not produce.
That asymmetry is worth stating plainly because it dictates the order of operations. Start wide — put the lock around the whole operation, convince yourself it is correct — and then shrink it deliberately, checking at each step that the invariant still cannot be observed false. Shrinking is an optimisation, and like every optimisation it should be measured (What Contention Actually Costs) rather than assumed. Starting narrow and widening on failure means shipping the failure.
The reserveSeat handler below has an obvious wide answer and a much better narrow one, and the difference between them is a network call. The loyalty lookup takes 40 ms and touches nothing shared. Holding the seat lock across it converts a microsecond-scale critical section into a 40-millisecond one, which is a 40,000× increase in the window during which every other task wanting any seat in this show is blocked.
1reserveSeat(showId, seatId, userId):2 with show.lock: # <-- acquired here3 show = shows[showId]4 if show.seats[seatId] != null:5 return SEAT_TAKEN6 tier = loyaltyService.get(userId) # 40 ms of network. Touches nothing shared.7 price = priceFor(show, seatId, tier) # pure computation8 booking = Booking(userId, price)9 show.seats[seatId] = booking.id10 auditSink.append(booking) # another 5 ms of I/O11 return booking # <-- released here12 13# Correct: no interleaving can break the invariant.14# Cost: the lock is held for ~45 ms per reservation. Every other task15# reserving ANY seat in this show waits behind it, so peak throughput for16# the whole show is ~22 reservations/second regardless of core count.1reserveSeat(showId, seatId, userId):2 show = shows[showId] # read of an immutable registry entry3 tier = loyaltyService.get(userId) # outside. 40 ms, shared nothing.4 price = priceFor(show, seatId, tier) # outside. pure.5 booking = Booking(userId, price) # outside. object is task-local until published.6 7 with show.lock: # <-- region begins8 if show.seats[seatId] != null: # check9 return SEAT_TAKEN10 show.seats[seatId] = booking.id # act11 # <-- region ends12 auditSink.append(booking) # outside. I/O, and not part of the invariant.13 return booking14 15# The region is now two operations on one map entry: microseconds.16# Note what moved and why: the price computation moved out because it17# touches nothing shared; the audit append moved out because the audit18# invariant is "every successful booking is eventually audited", which is19# an at-least-once obligation, not a mutual-exclusion one.Both versions preserve the invariant. The narrow one preserves it while holding the lock for roughly one ten-thousandth as long, because the only statements that must be indivisible are the ones that read and write the shared map. Everything else — the network call, the pricing, the object construction, the audit — either touches nothing shared or is governed by a different, weaker obligation.
One statement too narrow
Now the other direction, which is where the real bugs live. A reviewer looking at the minimal version above might reasonably suggest shrinking further: the check is a read, the assignment is a write, and each could have its own lock. Or, more commonly and more subtly, the two get separated by a refactor — isSeatFree() becomes a helper with its own lock, takeSeat() becomes another, and both are "synchronized".
The schedule below is what that produces. Every single access to show.seats happens under the lock. A race detector finds nothing, because there is no unsynchronized access. And two bookings hold the same seat, because mutual exclusion on each half of a check-then-act guarantees nothing about the pair.
The rule this yields: the region must span from the first read the decision depends on to the last write that makes the decision true. Any lock boundary drawn inside that span is a lock that runs, costs, and prevents nothing. This is also why "make the data structure thread-safe" is rarely the answer — a thread-safe map makes each operation atomic and leaves every check-then-act over it broken.
| # | Task A — reserve seat H12 for user 900 | Task B — reserve seat H12 for user 901 | State |
|---|---|---|---|
| 1 | acquire lock | · | seats[H12]=null lock=A |
| 2 | read seats[H12] → null | · | seats[H12]=null lock=A |
| 3 | release lock | · | seats[H12]=null lock=free |
| 4 | · | acquire lock | seats[H12]=null lock=B |
| 5 | · | read seats[H12] → null | seats[H12]=null lock=B ✕ Two bookings have now both observed the seat as free. The invariant is already doomed; nothing has been written yet. |
| 6 | · | release lock | seats[H12]=null lock=free |
| 7 | acquire lock; write seats[H12] = bk-900; release | · | seats[H12]=bk-900 lock=free |
| 8 | · | acquire lock; write seats[H12] = bk-901; release | seats[H12]=bk-901 lock=free ✕ The seat now belongs to booking 901; booking 900 was confirmed to user 900 and no longer exists in the map. Two tickets, one seat, no error. |
| 9 | return 200 { seat: H12, booking: bk-900 } | · | seats[H12]=bk-901 |
The method: three boundary questions
Finding the minimal region is mechanical once the invariant is named (Invariants: Name It Before You Lock It). Walk the function statement by statement and ask three questions in order. The answers give you the boundary directly, and they are the same three questions regardless of language or primitive.
One extra rule matters more than the rest in production code: an I/O call inside the region is almost always a mistake, and an I/O call whose latency you do not control is always one. A lock held across a network request has a hold time set by someone else's p99, which means your throughput ceiling is set by a system you do not operate. This is common enough to be its own lesson — see Lock Scope: What You Hold It Across — and it is also the mechanism behind most lock convoys (Lock Convoys).
The matrix below applies the three questions to reserveSeat line by line. Note that the answer for the audit append is "outside", not because it is unimportant but because its obligation is *at-least-once delivery*, a different invariant with a different mechanism — a retry or an outbox, not a mutex.
| Statement | Q1: touches state in the invariant? | Q2: does a later decision depend on it? | Q3: is it slow or externally controlled? | Verdict |
|---|---|---|---|---|
show = shows[showId] | no — the registry entry is immutable after startup | no | no | OUTSIDE |
tier = loyaltyService.get(userId) | no | no — price does not affect who gets the seat | yes — 40 ms, third-party p99 | OUTSIDE (and would be even if it were fast) |
price = priceFor(...) | no — pure function of local values | no | no | OUTSIDE |
if seats[seatId] != null | YES — reads the invariant's state | YES — the write below is conditional on it | no | IN — this is where the region starts |
seats[seatId] = booking.id | YES — writes the invariant's state | n/a — this is the decision | no | IN — this is where the region ends |
auditSink.append(booking) | no — different state, different invariant | no | yes — I/O | OUTSIDE; its own at-least-once obligation |
Key points
- The critical section is the span from the first read a decision depends on to the last write that makes the decision true. Not the set of accesses — the span.
- Too wide costs throughput and stays correct. Too narrow costs correctness and stays fast. Start wide, shrink deliberately, verify at each step.
- A check-then-act split across two separately locked regions is fully synchronized and fully broken — race detectors will report nothing.
- "Thread-safe data structure" makes each operation atomic and leaves every check-then-act over it racy. It is a component, not a solution.
- Anything pure, task-local, or governed by a different invariant belongs outside the region — including the object you are about to publish, as long as nothing else can reach it yet.
- I/O inside the region hands your throughput ceiling to whoever owns that I/O's latency.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Name the invariant and list the shared locations it mentions. Everything else in the function is a candidate for exclusion.
- • Find the earliest statement whose value a later shared write depends on. The region starts there — not at the write.
- • Find the last statement that restores the invariant. The region ends there — not at the end of the function.
- • Move everything between those bounds that touches neither the invariant's state nor the decision *out*: pure computation, allocation, logging, I/O, and object construction that has not yet been published.
- • Verify the shrink: for each statement moved out, ask what an interleaving at that point could observe. If the answer is "a value nobody else can reach", the move is safe.
- • Wide region: A holds the lock through the loyalty call; B waits 40 ms and then observes H12 taken. Correct, slow.
- • Minimal region: A holds the lock for the check and the write; B blocks for microseconds and observes H12 taken. Correct, fast.
- • Region split in two: A checks (null), releases; B checks (null), releases; A writes bk-900; B writes bk-901. Two bookings, one seat, every access locked.
- • Region too narrow the other way — only the write is locked: A reads null unsynchronized, B reads null unsynchronized, both write under the lock. Same double-booking, plus an unsynchronized read that is now also a data race in C++.
- • No region at all, but the map is a "concurrent map": every individual
getandputis atomic; the check-then-act between them is not. Identical failure.
- • A correctly drawn region guarantees that no other participant observes the state while the invariant is false. That is the entire guarantee.
- • It does not guarantee ordering between tasks — which of two waiting tasks gets the seat is a fairness question the primitive may or may not answer. See Fairness.
- • It does not guarantee anything about state outside the region, including the object you constructed before entering, once that object becomes reachable.
- • It guarantees nothing across process boundaries. The same region on two servers protects two different maps; see A Mutex on Server A Does Nothing About Server B.
- • Contention is proportional to hold time × arrival rate. Halving the region halves the wait for everyone behind it, which is why shrinking is worth real effort on a hot path.
- • The wide version pins the whole show to ~22 reservations per second because 45 ms of hold time admits no more, no matter how many cores are available.
- • Granularity is the other axis: one lock per show rather than one per cinema turns a global bottleneck into per-show bottlenecks. One lock per *seat* goes further and adds a lock-ordering obligation if a booking ever spans two seats. See Lock Ordering.
- • Measure hold time and wait time separately — hold time is what you shrink, wait time is what users feel. See Hold Time, Wait Time, and the Ratio Between Them.
- • Double booking — the check-then-act split across regions. Two winners, no error.
- • Lock convoy — a wide region under load produces a queue that never drains, so latency grows without bound while CPU sits idle. See Lock Convoys.
- • Deadlock introduced by shrinking — splitting one lock into two finer ones creates an ordering obligation that did not exist before. See Lock Ordering.
- • Blocked event loop — the wide version in a single-threaded runtime does not merely slow this handler down, it stalls every unrelated task in the process. See Blocking the Event Loop.
- • Silent regression — a later commit moves one statement inside the region "for safety" and quietly restores the 40 ms hold time.
- • On any hot shared structure: shrinking the region is the highest-yield contention fix available and does not change the primitive or the API.
- • When a lock is held across I/O — moving the call out is usually a small refactor with a large, measurable effect on p99.
- • When adding a feature to an already-locked function; the three questions tell you immediately whether the new statement belongs inside.
- • When shrinking crosses the invariant boundary. A region that is one statement too small is worse than one that is ten too large.
- • When shrinking requires splitting one lock into several and the resulting ordering obligation is not written down. You traded contention for deadlock.
- • When the region is already microseconds and the contention is elsewhere. Shrinking a cold lock is effort spent on a number nobody measures.
- • When the "shrink" is achieved by moving a write outside and hoping — the classic way a correct region becomes an incorrect one during a refactor.
- • Lock hold time distribution, not the mean. A p99 hold time three orders of magnitude above p50 usually means an I/O call slipped inside on one path.
- • Lock wait time at p99, and the count of tasks waiting — the pair distinguishes "held too long" from "acquired too often". See Hold Time, Wait Time, and the Ratio Between Them.
- • Throughput ceiling per protected resource: if reservations per second for a show plateaus at roughly 1/hold-time, the region is your bottleneck.
- • An assertion at the region's exit that recomputes the invariant, enabled in staging. It catches a boundary drawn one statement too narrow far more reliably than a load test does.
- • A minimal region is harder to read than a wide one: the reasoning for why each excluded statement is safe outside lives in the author's head unless it is written down.
- • Every shrink is a claim that must be re-verified when the function changes, and function changes do not carry a reminder.
- • Finer granularity multiplies lock objects, which multiplies the lock-ordering surface and the deadlock surface.
- • Constructing an object outside the region and publishing it inside adds a safe-publication obligation in languages with a relaxed memory model. See Safe Publication: Handing Over a Finished Object.
- • Push the whole decision into a system that arbitrates atomically:
UPDATE seats SET booking = ? WHERE show = ? AND seat = ? AND booking IS NULLand check the affected row count. No region, no lock, and it works across servers. See The Database Solves Concurrency For Its Data, Not For Your Memory. - • Use a data structure whose API *is* the region: an atomic
putIfAbsent/set-if-nullis a check-then-act with no window, which is the entire reason those methods exist. - • Give each show to a single owner task and send reservations as messages — one actor, no interleaving, at the cost of a per-show serialisation point. See The Actor Model.
- • Optimistic control: read a version, compute freely, write conditionally on the version being unchanged, retry on conflict. Better when conflicts are rare. See Optimistic vs Pessimistic.
How much of the task is inside the lock?
A mutex buys correctness with throughput
if (balance >= 100) withdraw(100) — drive it until it overdraws
balance = 100
withdraw(amount): # both tasks run this concurrently
b = read(balance) # 1
if b >= amount: # 2 <- decided on a value that may already be stale
debit(amount) # 3| # | Withdrawal A (100) | Withdrawal B (100) | State |
|---|---|---|---|
| 1 | rA ← read balance | · | balance=100 paidOut=0 |
| 2 | if rA >= 100 | · | balance=100 paidOut=0 |
| 3 | debit 100 | · | balance=0 paidOut=100 |
What people believe, and what is true
Every access is inside a lock, so it is safe.
Mutual exclusion per access says nothing about a sequence of accesses. The double-booking schedule above has 100% locked access and 0% correctness.
A bigger lock is always safer.
Wider is safer for *this* invariant and strictly worse for throughput, and it is how deadlocks are born: a region wide enough to contain a second lock acquisition is a region wide enough to contain a cycle.
Using a concurrent hash map removes the need for a critical section.
It removes the need for one around each individual operation. if absent then put still needs one, unless you use the structure's own atomic putIfAbsent.