A trace is a proof artifact. A final table can look plausible after a lost update, a write skew, a deadlock victim, or a crash replay; the trace retains the operations, visibility rules, and failure boundary that distinguish them. Use the notation below before proposing a lock level or an ORM setting.
Record enough state to replay the decision
| Notation | Meaning | Question it answers |
|---|---|---|
| r1(x=20) | T1 read 20 from x | which version did T1 base its decision on? |
| w2(x=13) | T2 wrote 13 | which operations conflict? |
| X1(x) | T1 holds an exclusive lock on x | why is T2 waiting or allowed through? |
| C1 / A1 | T1 commits / aborts | may its writes become visible? |
| L=911 durable | log through LSN 911 is stable | what can recovery rely on after a crash? |
The first question is always semantic: what must remain true? The second is operational: at what read, write, commit, or recovery point is that truth enforced? A trace missing either cannot diagnose the system.
Prediction — insufficient evidence
A support log says “stock became 13 after two requests for 7.” It contains only final row values. Name two distinct explanations that remain possible.
HintExpandCollapse
Final values discard order and visibility.
Worked solutionExpandCollapse
A lost update can produce 13 from initial stock 20 when both transactions read 20 and overwrite each other. A correctly serialized system could also produce 13 after one request succeeds and a compensating restock changes the value. The missing data are the read versions, statement outcomes, commit order, and any intervening events; final state alone is not a concurrency proof.
Trace a lost update without smuggling in oversell
| Step | T1 | T2 | Stored stock | Consequence |
|---|---|---|---|---|
| 1 | read 20 | 20 | T1 plans 13 | |
| 2 | read 20 | 20 | T2 also plans 13 | |
| 3 | write 13; commit | 13 | one decrement recorded | |
| 4 | write 13; commit | 13 | second decrement lost |
A weak implementation reads stock in the application and executes an unconditional write. A row-local repair puts the condition and decrement in one SQL statement: update stock only when stock is at least the requested amount. The affected-row count distinguishes reservation from rejection. A lock or serializable protocol can also serialize the read-modify-write, but the conditional statement expresses the invariant directly.
Worked trace — complete the repair trace
Assume T1 performs the conditional decrement first and commits. T2 performs the same conditional decrement after T1. Fill in T2’s affected-row outcome and final stock.
Worked solutionExpandCollapse
T1 changes 20 to 13. T2 sees 13, and its condition stock >= 7 remains true, so it changes 13 to 6 and affects one row. If the initial stock were 10, T1 would leave 3 and T2 would affect zero rows. Conflating the 10-unit case with a lost update hides whether the design lost a write or correctly rejected an oversell.
Evidence beyond the final value
A support log shows stock = 13 after two requests for 7 units, starting from initial stock = 20. Evaluate which evidence sources reliably diagnose whether an anomaly occurred:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Trace write skew as a predicate failure
Counterexample. The invariant “at least one doctor remains on call” spans a set of rows. T1 changes doctor A; T2 changes doctor B. No row is written twice, yet both can jointly violate the predicate.
A row-level optimistic version check can accept both writes because their write sets are disjoint. Repairs include serializable validation, predicate/range protection, or a single summary row updated as part of the rule. The trade-off is expected aborts or contention at the shared boundary.
Prediction — identify the false repair
Which repair is insufficient by itself: lock A only, lock both currently on-call rows, serializable transaction, or update a protected on-call-count row?
Worked solutionExpandCollapse
Locking A only is insufficient because T2 changes B. Locking both rows can work only if every transaction that could change membership follows the same discipline and range changes are also controlled; it is brittle. Serializable validation or a protected count/summary row gives a shared conflict boundary. The key gap is the predicate, not the absence of a row lock.
Trace waiting, deadlock, and a chosen abort
| Step | T1 | T2 | Waits-for graph |
|---|---|---|---|
| 1 | holds X(order 7) | none | |
| 2 | holds X(stock 9) | none | |
| 3 | waits for X(stock 9) | T1 → T2 | |
| 4 | waits for X(order 7) | T1 ↔ T2 |
Transfer — order, crash, and webhook retry
Design the event order for: reserve stock, write an order, charge a provider, and send a confirmation. A crash can happen after any step; the provider can send the same webhook twice and out of order.
HintExpandCollapse
Make the database state transition and the retry key durable before depending on external delivery.
Worked solutionExpandCollapse
In one transaction, insert the order in a pending state, reserve stock conditionally, store a unique provider-event/idempotency key, and insert an outbox record; then commit. A worker invokes the provider with that key and records only legal monotonic payment transitions in later transactions. Deduplicate webhook IDs with a unique constraint, and send confirmation from a committed outbox. Recovery can replay unclaimed outbox records; it must not infer a payment from a network timeout.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 4.3.1: Differentiating Lost Updates from Serial Compensations
Given a log indicating an inventory record transitions from 20 to 13 after two customer purchase requests for 7 units, describe what specific timeline artifacts are required to definitively prove whether a lost update occurred.
HintExpandCollapse
Inspect read timestamps, statement outcomes, and external audit logs.
Worked solutionExpandCollapse
To prove whether a lost update occurred, the timeline must establish: (1) whether transaction read the initial value 20 (lost update) or the committed value 13; (2) whether ‘s decrement statement actually affected a row or was rejected by a conditional check (rows affected = 0); and (3) whether an external supplier restock event (+7 units) occurred between two serialized sales. Scalar end-state alone is ambiguous.
Exercise 4.3.2: Write Skew Interleaving Trace Verification
Consider transactions and operating under snapshot isolation on rows and with invariant Verify why schedule violates the invariant despite zero lock or write-write conflicts.
HintExpandCollapse
Trace the disjoint write sets against the joint invariant predicate.
Worked solutionExpandCollapse
Under snapshot isolation, reads snapshot and decides it is safe to set because is true. Concurrently, reads the identical snapshot and sets because is true. Because modifies item and modifies item their write sets and are completely disjoint. Both commit without error, leaving and directly violating
Exercise 4.3.3: Deadlock Wait-For Graph and Victim Selection Policy
Construct a 4-step execution trace involving transactions and and resources order_7 and stock_9 that produces a circular wait under strict 2PL. Specify a heuristic for victim selection that minimizes aborted work.
HintExpandCollapse
Have each transaction acquire one resource and subsequently request the resource held by the other.
Worked solutionExpandCollapse
Trace:
- acquires exclusive lock
- acquires exclusive lock
- requests and blocks
- requests and blocks The wait-for graph has cycle A sound victim selection policy aborts the younger transaction or the transaction that has generated fewer write-ahead log bytes, minimizing rollback work and lock churn.
Exercise 4.3.4: Crash-Safe Payment and Webhook Event Choreography
Design an idempotent, crash-safe transaction sequence that coordinates reserving local inventory, writing an order, calling an external payment gateway, and handling duplicate out-of-order webhook notifications.
HintExpandCollapse
Commit local state and outbox record before external network calls; deduplicate incoming webhooks.
Worked solutionExpandCollapse
- Local transaction: In a single database transaction, insert
orders(id, status='pending'), execute conditional stock reservationUPDATE inventory SET stock = stock - 1 WHERE stock >= 1, generate an idempotency keyk, and insert anoutboxtask record withk. Commit. - Gateway invocation: A worker reads the outbox task and dispatches the payment charge with key
k. - Webhook handling: Incoming payment webhooks carry key
k. The endpoint attemptsINSERT INTO processed_events (event_id, idempotency_key) VALUES (...). If a unique-key collision occurs, it immediately returns HTTP 200 without reprocessing. Otherwise, it updatesordersstatus topaidwithin an atomic transaction.