Summary and key takeaways
Back to Tomas and Lena. Tomas started this mechanism believing that a database either works or has a bug. He ends it knowing that many users create a different kind of problem: correctness depends on the interleaving of operations, and conflict is arithmetic. Lena's rule still stands: do not tune the mechanism first; measure the conflict probability.
The central idea. Concurrency control does not remove conflict. It decides how conflict is paid for. There are exactly three currencies: waiting (locks), wasted work (aborts and retries), and weakened semantics (the application repairs the result). Every scheme buys a mix.
Big ideas, one sentence each:
- Conflict is quadratic and sensitive to skew. Transactions in flight L = λW (Little's Law); pairs grow like L², so expected conflicts are about L²k²/2N. Ten times the throughput is about a hundred times the conflict, and hot keys shrink the effective N by orders of magnitude.
- Three currencies. Waiting, wasted work, weakened semantics. Which one you choose depends on the measured conflict probability.
- The version-or-block fork. A reader either blocks writers (locks) or reads an old version (MVCC). MVCC moves the cost to storing and collecting versions, and who pays differs by implementation (the writers in Postgres-style storage, the reader in undo-segment style).
- The conservative-approximation pattern. When the exact test is intractable (view serializability, predicate locks, cycle detection), systems use a conservative approximation and pay with false positives: intention locks, next-key locks, SSI's two-bit test, file-level conflict checks.
- Atomicity is one designated write. Atomicity over n items is atomicity over one item: a log record, a pointer CAS, a primary row. Everything else (undo, redo, savepoints, manifests, outbox) defends that declaration.
- The in-doubt window cannot be removed. The outcome of a commit is committed, aborted or unknown, on one node as much as across ten. Idempotency keys and reconciliation are how you live with it.
- Availability multiplies with unanimity. Atomic commit over n participants is Aⁿ (0.999¹⁰ ≈ 0.99); consensus needs only a majority. Replication improves the base, not the exponent. Lock hold time W grows by two round trips and enters the conflict formula squared.
- Algebra beats protocols. Commutative, associative, idempotent operations (escrow counters, sketches, idempotent consumers) make coordination optional. First ask whether the operation can be restated.
- Shorten W first. Since W enters squared, the cheapest improvement is almost always less time in the transaction: no external calls inside it, one-shot statements, partitioned writers, and deferred or last-placed irreversible steps.
Formulas to remember:
| Formula | Meaning | Seen in |
|---|---|---|
| L = λW | Transactions in flight = arrival rate × time in system | Why concurrency is different, lock hold time in 2PC |
| L²k²/2N | Expected conflicts among L transactions touching k of N items | Why concurrency is different; file-level conflicts in Transaction mechanics |
| cost per commit = F/(λT) | A flush F shared by λT commits | Group commit |
| n²T/2 | Time to drain n writers contending on one pointer with naive retry | CAS retries |
| 0.999ⁿ | Availability when n components must all be up | 2PC |
| commits/s ≤ 1 / (atomic primitive latency) | Per independent committer | fsync, object-store CAS |
Patterns that repeat:
- Where the data lives decides which of commit and abort is cheap. In place: cheap commit, costly abort. Out of place: free abort, contended commit.
- Immutable storage grows an indirection layer plus a garbage collector: MVCC chains plus vacuum, data files plus manifests plus compaction.
- Costs are conserved: savepoints are free to take and costly to read past; the outbox moves duplicates to the consumer; clock uncertainty is billed either to writes (commit wait) or to reads (restarts).
- A fixed per-operation cost derives a natural batch size: group commit, Silo epochs, the timestamp oracle.
- Three ways out of 2PC's blocking: make the decision-holder fault-tolerant (Paxos-commit, Spanner), make the decision discoverable (Percolator), or make it unnecessary (Calvin).
- Order the irreversible step last, and design the manual reconciliation path before launch.
- Independence is assumed and false: hot keys defeat uniform-access estimates; correlated failures change how often, and how badly, a unanimity protocol blocks.
A final checklist for your own system:
- Measure the abort rate and the conflict probability before changing the mechanism.
- Name your single atomic event and divide one by its latency.
- Decide, for each cross-service flow, whether it really needs atomicity; if not, use a saga, an outbox and idempotent consumers.
- Mark read-only transactions as read-only; put a timeout on idle transactions.
- Retry only operations that re-read their inputs, with jittered backoff and a retry budget.