Two customers buy the last unit at the same instant. Each transaction reads available = 1, computes 1 - 1 = 0, and writes 0. Both commits succeed, the stock never becomes negative, and two units are sold from one. No individual statement is wrong; the interleaving is.
| Step | T1 | T2 | Last written available (not necessarily committed) |
|---|---|---|---|
| 1 | read 1 | 1 | |
| 2 | read 1 | 1 | |
| 3 | write 0 | 0 | |
| 4 | write 0 | 0 | |
| 5 | commit | commit | 0 |
The lost update is the motivating problem. Isolation names an allowed history; concurrency control is the mechanism that admits or rejects individual operations on the path to that history. A stock row can be protected with a lock, a version check, a timestamp rule, or serializable dependency tracking. Those mechanisms fail differently, so a system design must choose an error it can handle rather than merely demand “no races.”
This schedule also shows why the repair must match the invariant. A conditional update SET available = available - 1 WHERE available >= 1 prevents the negative count without an explicit read, while a plain read-then-write needs a lock or version check that spans both steps. The protocol is chosen from the invariant, not from a preference for one lock mode.
Why two commits are not enough
Both transactions in the lost-update schedule commit successfully without error. Evaluate which assertions regarding this concurrent execution are correct:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Strict two-phase locking blocks unsafe orderings
| Requested lock | Existing shared | Existing exclusive |
|---|---|---|
| shared | compatible | wait |
| exclusive | wait | wait |
Strictness is a recovery aid as well as a serializability tool: no committed transaction has observed a value that must later be undone. It can still reduce concurrency when a long transaction holds a hot row. A carefully bounded critical transaction is often more important than choosing an exotic lock mode.
Application — lock the fact, not the screen
A reservation flow reads inventory, calls a remote payment service for 10 seconds, then decrements inventory. Should it hold an exclusive database lock during the call?
HintExpandCollapse
A database lock protects a local invariant; remote latency makes the protected interval unbounded.
Worked solutionExpandCollapse
No. Holding the lock causes a slow external system to serialize unrelated reservations and can create deadlocks. First record an idempotent payment intent or outbox state, perform the remote call outside the inventory-critical transaction, then execute a short conditional reservation transaction. The repair is an explicit state machine, not a longer lock.
For one inventory row, the critical statement can be:
UPDATE inventory
SET available = available - :quantity
WHERE sku = :sku AND available >= :quantity;The caller must inspect the affected-row count. 1 commits the reservation; 0 means the attempt lost the race or the request is no longer satisfiable and must not be treated as success. A serialization/deadlock error may be retried with the same idempotency key, bounded attempts, and backoff; a committed success must be returned from the idempotency record rather than applied twice. The predicate is necessary but not, by itself, evidence that an aggregate invariant spanning several stock rows is protected.
Deadlock is a graph, not “a slow query”
Detection periodically finds cycles and aborts a victim. Prevention imposes an ordering, such as always locking inventory before orders. Timeouts are simpler but can abort work that would have completed and may miss an operational root cause. Victim selection weighs age, work done, locks held, and rollback cost; it must never assume the transaction’s external side effects can be undone by database rollback.
Prediction — break the cycle
T1 holds warehouse/5 and waits for sku/9; T2 holds sku/9 and waits for warehouse/5. Give one prevention and one detection response.
Worked solutionExpandCollapse
Prevention: define and enforce a global lock order, for example (warehouse_id, sku) sorted lexicographically, so both transactions request warehouse 5 before sku 9. Detection: record T1 → T2 and T2 → T1, abort a chosen victim, roll back its database work, then retry only if its operation uses an idempotency key or has no exposed external effect. Retrying without that boundary can duplicate messages or charges.
Protocols move the conflict check to different times
Worked example. A flash-sale counter has frequent writes to one row; an analytics dashboard reads millions of rows and rarely writes. One protocol need not optimize both workloads.
| Protocol | When it rejects/confirms conflict | Strength | Cost / failure mode |
|---|---|---|---|
| strict 2PL | lock request | clear exclusion and recoverable writes | waits and deadlocks |
| timestamp ordering | operation violates timestamp order | no deadlocks | restarts under hot contention |
| optimistic control | commit-time read/write-set validation | readers run freely when conflicts are rare | expensive wasted work on conflict |
| MVCC | version visibility plus write/serializability validation | readers often avoid writer blocking | old-version retention; write skew unless stronger validation |
Timestamp ordering and optimistic control do not make conflicts disappear: they shift them into aborts. MVCC makes a snapshot readable, not necessarily serializable. A high-contention counter may prefer a single conditional update or a sharded/aggregated representation over a broad transaction that repeatedly aborts.
Worked example — snapshot isolation permits write skew. Two doctors are on call, and the invariant is “at least one doctor remains on call.” T1 reads the on-call set and removes Alice; T2 concurrently reads the same set and removes Bob. Under snapshot isolation each transaction reads a consistent snapshot and writes a different row, so neither write conflicts with the other. Both commit, and the invariant is false. The conflict is on the predicate “the on-call set has size at least two,” not on a single row. Repairs include serializable isolation with predicate or summary-row protection, a constraint enforced by a coordinated operation, or a design that makes the aggregate a versioned object. Retrying one transaction after commit is insufficient because neither transaction observed a write conflict.
Granularity must match the invariant
| Invariant | Suitable shared boundary | Common false repair |
|---|---|---|
| one seat never sold twice | one inventory/seat row plus conditional update | read value in application, then unconditional write |
| no duplicate username | unique constraint | rely on an application mutex |
| at least one doctor on call | serializable predicate protection or summary row | lock only the doctor being changed |
| total monthly credit ≤ limit | tenant-month summary row or serializable validation | lock each newly inserted invoice |
Transfer — predict contention before implementing
A service records one million page views per minute and must display an approximate dashboard every minute; it also records money transfers requiring exact balances. Which path may tolerate commutative or delayed aggregation, and which cannot?
HintExpandCollapse
Separate the semantic requirement from the shared data shape.
Worked solutionExpandCollapse
Page-view counters can be sharded, buffered, or eventually aggregated when a bounded delay/error is acceptable. Money transfers require an exact invariant at commit and need a transaction/constraint boundary that prevents overdraft. Applying exact locking to every page view wastes concurrency; applying approximate aggregation to balances changes the financial contract.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 4.2.1: Strict 2PL Deadlock Precedence Cycle Detection
Consider two transactions under strict two-phase locking: holds an exclusive lock on row and requests an exclusive lock on row holds an exclusive lock on row and requests an exclusive lock on row Construct the wait-for graph, verify why this state is a deadlock, and describe how the engine resolves it.
HintExpandCollapse
Draw directed edges from the waiting transaction to the lock-holding transaction.
Worked solutionExpandCollapse
The wait-for graph contains directed edges: (since waits for held by and (since waits for held by The resulting cycle represents a circular wait where neither transaction can progress. The engine’s deadlock detector identifies the cycle and aborts one transaction (the victim), rolling back its operations and releasing its locks so the other can proceed.
Exercise 4.2.2: Row-Level Lock Inadequacy for Predicate Constraints
Explain why executing SELECT * FROM Doctor WHERE on_call = true FOR UPDATE; in PostgreSQL fails to protect against phantom inserts that violate predicate-level business invariants.
HintExpandCollapse
Row locks attach only to currently existing tuples returned by the query.
Worked solutionExpandCollapse
SELECT ... FOR UPDATE acquires row-level locks strictly on existing physical tuples matching the predicate at query execution time. It cannot lock nonexistent rows. A concurrent transaction can insert a brand new Doctor record that satisfies the predicate, committing without waiting on existing row locks. Preventing phantom violations requires true predicate locks (SSI), table-level locking, or explicit locks on a parent anchor row.
Exercise 4.2.3: Atomic Conditional Write for Inventory Reservation
Write an atomic SQL update statement that decrements inventory item 42 by 1 while strictly guaranteeing that available stock never drops below zero, without requiring an explicit application-side lock or prior select.
HintExpandCollapse
Include the non-negative invariant directly in the WHERE clause and inspect row count.
Worked solutionExpandCollapse
UPDATE inventory
SET available = available - 1
WHERE item_id = 42
AND available >= 1;If the statement affects 1 row, the reservation succeeded atomically within single-statement execution. If it affects 0 rows, stock was exhausted, and the application safely rejects the purchase without race conditions.
Exercise 4.2.4: Workload-Aware Concurrency Control: Exact vs. Commutative Aggregation
A social platform handles 100,000 post like increments per second and 500 bank balance transfers per second. Contrast how concurrency control should be architected for the like counter versus the bank balance.
HintExpandCollapse
Determine whether operation order matters and whether intermediate states violate invariant constraints.
Worked solutionExpandCollapse
Like increments are commutative can be applied in any order) and tolerate eventual consistency: they should be sharded into counter slots per post or buffered in an in-memory queue and flushed in batches, avoiding single-row lock serialization. In contrast, bank balance transfers are non-commutative with zero error tolerance: an account must never overdraw, requiring strict serializable isolation or row-level FOR UPDATE serialization on account balances at commit time.