Book Deep Read · Database Internals · Chapter 13
Database Internals · Ch 13 · Alex Petrov · 2019
You tap "transfer." Money leaves your account and lands in someone else's. If only one of those two halves happens, that is a disaster. A single database solved this problem decades ago — this chapter asks the harder version: when the two accounts do not even live on the same machine, how do you guarantee "either both or neither"? That is a distributed transaction.
Picture three people in three cities who must sign the same contract, and it has to be all three or none, and they can only use the phone. The usual trick is to appoint a convener who makes two rounds. Round one: ask each person "can you sign?" — and note that answering "yes" means picking up the pen and holding your slot, with no backing out. Round two: once every answer is in, tell each of them "sign."
The odd part sits between the rounds. After collecting every "yes" but before telling anyone anything, the convener drops their phone in a lake. The other two dare not sign (what if the convener actually decided to call it off?) and dare not walk away (what if someone already signed?). All they can do is hold the pen, occupy the room, and wait.
This is not clumsiness; it is unavoidable. From where the other two stand, "the convener never decided" looks exactly like "the convener decided and I never heard." While the second possibility is live, nobody dares call it themselves. So the two-round scheme has a hard flaw: it guarantees you never get it wrong, but not that you keep moving. In a database, "holding the pen" means those rows are locked — nobody can read or write them — and a convener's restart can take minutes.
Does one more phone call help? A little: the convener first announces "I am about to have you sign," and after that, anyone who hears nothing further signs by default. But if the phone line is cut in half, each side acts on its default and you can end up half-signed, half-cancelled — worse than being stuck. The three moves that actually work do not improve those two rounds; they change the foundation:
① Take a number first, act second. Stop asking "can you?" Instead, put everything everyone wants to do into one agreed numbered order, and let each person work the list. Same order, same rules, same result — no negotiation needed.
② More than one convener. Let a small group hold that role jointly, so a decision is remembered by several people at once; one phone in the lake changes nothing.
③ Write "who signed" onto the contract itself. Agree that one particular page is decisive: once it is signed, the whole thing is in force. Anyone who later opens the binder tidies the other pages up or crosses them out — no convener has to stay in the room.
All three charge tuition: the take-a-number approach demands that you declare everything you intend to do up front, with no improvising mid-way; the many-conveners approach needs very accurate clocks and more expensive machine rooms. Which is why engineering often has a better fourth answer: first check whether this really has to be one transaction at all.
Getting "all or nothing" across machines is hard because everyone must promise not to back out before any decision can be made — and in the sliver between that promise and the decision arriving, one fallen convener leaves everybody holding locks. Every later answer changes the foundation instead: take a number, make the convener a group, write the state into the data itself — or just do not open the transaction.
Want the actual 2PC / 3PC protocols, the Calvin-versus-Spanner split, and the diagrams? → Switch to the deep read
This chapter is about atomic commitment: making a transaction that spans several nodes either take effect everywhere or nowhere. The central insight is that it is a close relative of consensus, but a stricter one — consensus makes progress with a majority, atomic commitment requires unanimity, so a single unreachable participant stalls it. Two-phase commit (2PC) buys "never wrong" with blocking; three-phase commit (3PC) tries to buy liveness back and breaks under network partitions. The real ways out change the foundation: Calvin reaches consensus on the order and then never negotiates; Spanner keeps 2PC but makes every role a Paxos group; Percolator writes the transaction state into the data tables themselves; and coordination avoidance argues which transactions never needed coordination at all.
0.5ms inside a datacenter, often 70–150ms across continents; an extra protocol round costs an extra RTT.Late in Part II, "Distributed Systems." Chapters 11 and 12 handled replication and consistency for a single key (quorums, read repair, anti-entropy), but those mechanisms have nothing to say about changing two keys together; this chapter fills that gap, and the "majority agrees" primitive it leans on arrives in Chapter 14 on consensus. Real-world counterparts: XA in MySQL and PostgreSQL, Google's Percolator and Spanner, FaunaDB (the commercial Calvin), CockroachDB, TiDB.
On one machine, atomicity needs nothing but a WAL: the log lives on one disk, and written means written. The moment a transaction crosses shards, "written" no longer has a single source of truth — A made it durable, B did not, and the network will not tell you whether B is dead or merely slow (Chapter 9's conclusion). The only two outcomes of not solving this are half-completed states ("debited but never credited") or retreating to "no cross-shard writes" and pushing consistency onto application code and nightly reconciliation. So the chapter poses a precise question: on a set of nodes that may crash and whose messages may be delayed, how do you make them arrive at one and the same irrevocable answer to "commit or roll back"?
This is the distinction to load into your head first. Consensus lets a majority decide and the minority follow; atomic commitment rules that only a unanimous Yes commits, and any single No forces a global rollback. Two consequences: the outcome is not "elected" but uniquely fixed by any participant's veto; and a surviving majority is not enough — one missing vote and nothing moves. So 2PC is not "a worse consensus algorithm than Paxos." It solves a different problem, and that problem cannot have both safety and liveness on an asynchronous network.
Two-phase commit splits into a voting round and a commit round. The coordinator sends Propose; each participant makes "I am prepared" durable and answers Yes or No. Answering Yes surrenders the right to change your mind: from then on it must be able to commit, so locks stay held until round two arrives. In round two the coordinator tallies the votes and first writes the decision to its own log — from that instant the decision is irrevocable, and even if it crashes immediately after, it can only resume with that same decision on restart — then sends Commit/Abort and collects acks.
The two failure modes are nothing alike. A cohort dying before it votes is easy: the coordinator never gets the vote, aborts globally, and all you lose is a wasted attempt. A dying coordinator is the real problem — participants that voted Yes sit in an uncertain state where they can neither commit nor abort on their own, holding locks until it recovers. Participants asking each other (cooperative termination) only rescues the case where someone already received the decision; if everyone alive has merely voted Yes, the whole group waits. So the price of 2PC is not those 2 RTTs (roughly 150–300ms across continents) but that, in the worst case, locks are held for as long as the coordinator takes to recover — minutes.
Three-phase commit inserts a PreCommit round ("I am about to have you commit") and arms both sides with timeouts: a participant that times out after PreCommit commits on its own; one that times out before it aborts on its own. A dead coordinator no longer freezes anybody, so liveness returns. The cost has two layers. The visible one is an extra RTT. The fatal one is that it only holds in a model where nodes stop but the network never partitions and delays are bounded. Split the network down the middle and the half that saw PreCommit commits while the half that did not aborts — atomicity is torn open, which is worse than being stuck. That is why industry essentially never ships 3PC.
Calvin changes the question. If agreeing on the outcome is the hard part, then agree only on the order of the inputs. A sequencing layer collects transactions into fixed-length batches (the paper uses 10ms epochs) and replicates that order with Paxos; each replica then executes in the same order under the same deterministic locking rules. Same inputs and same order means the same result — so there is no commit negotiation, and no need to replicate execution results either. The Calvin paper (Thomson et al., SIGMOD 2012) reports roughly 500,000 TPC-C transactions per second on 100 commodity machines. The cost is concrete: a transaction must submit all of its logic at once (stored-procedure style, so no interactive "read something, then decide what to do next"), and its read/write set must be known in advance; when it is not, a reconnaissance query (OLLP) runs first and is redone if the data moved.
Spanner runs 2PC on top of Paxos: each shard is a Paxos group, and the coordinator and participant roles are each held by a group. "The coordinator crashed" degenerates into "the group elected a new leader," and the uncertainty window shrinks from minutes to seconds — the blocking did not disappear, it was demoted to a recoverable failure. The other half of the trick is TrueTime, which returns the clock as a value with an uncertainty interval (the width ε sawtooths at single-digit milliseconds); a transaction waits out ε before releasing (commit wait), so timestamp order matches real order. Read-write transactions use two-phase locking plus 2PC; read-only transactions just take a timestamp and read a snapshot, with no locks and no 2PC.
Percolator is Google's transaction layer on top of Bigtable, and its idea is contrarian: have no standing coordinator; store the coordination state in the database itself. Each logical column becomes three — data (versioned values), lock, and write (a pointer to the committed version). After taking a start_ts, prewrite writes data and lock on every row involved, designating one of them the primary lock with the others pointing at it; at commit, writing the write record on the primary row successfully commits the whole transaction — that single write is the commit point, and the remaining locks are left for later readers to clean up (roll forward if the primary committed, roll back if it is gone). It trades snapshot isolation for the removal of the coordinator as a single point; the price is that readers tidy up after writers, and a lock collision means rollback and retry, which hurts under high contention.
The closing section takes the sharpest position: coordination is expensive largely because much of it was never necessary. The test is invariant confluence (I-confluence): if merging two states that each satisfy an invariant yields a state that still satisfies it, that class of transactions can run concurrently with no coordination at all. Adding elements to a set is I-confluent; a uniqueness constraint or "the balance must not go negative" is not — each side is legal alone and illegal merged, so those must coordinate. RAMP transactions offer a weaker but often sufficient guarantee, read atomicity: you see either all of a transaction's writes or none of them. They use multi-versioning plus a little metadata, detect a partial read, and fix it with one extra round of reads — no locks, no 2PC.
The soul of the chapter is this table: these options are not trading "which is faster" but where the uncertainty is parked and who pays for it.
| Approach | Where the commit point is | When the coordinator/leader fails | Cost | When to pick it |
|---|---|---|---|---|
| 2PC (XA) | the coordinator's log | blocks: Yes-voters hold locks until recovery — minutes | 2 RTTs; coordinator is a single point; long-held locks | one datacenter, few participants, fast coordinator recovery; be wary across services |
| 3PC | after PreCommit reaches the cohorts | non-blocking, via timeouts on both sides | one more RTT; tears atomicity under partition | essentially never; more theoretical than practical value |
| Calvin-style (deterministic ordering) | the moment Paxos replicates the order | just elect a new leader; execution negotiates nothing | one-shot transactions only; read/write sets must be known | high-contention OLTP that can be written as stored procedures |
| Spanner-style (2PC over Paxos) | the coordinator group's Paxos log | demoted to a leader change — seconds | needs TrueTime-grade clocks; writes pay commit wait | general interactive SQL plus cross-region strong consistency, if you can afford the hardware |
| Percolator-style (state in the table) | the primary row's write record | no standing coordinator; stale locks cleaned by readers | readers tidy up after writers; rollback-and-retry under contention | built on an existing KV store where snapshot isolation suffices (TiDB took this road) |
| Coordination avoidance (I-confluence / RAMP) | each node commits locally | not a concept here | only for confluent invariants; a weaker guarantee | when the invariant is provably confluent — the cheapest distributed transaction is none |
Two questions come first when choosing: ① does this transaction really have to cross shards? (co-locate the related rows under a user ID and the whole chapter's trouble evaporates) ② what is the weakest guarantee the business accepts? (if read atomicity is enough, do not reach for 2PC)
The chapter hands you a yardstick: to size up any database's distributed transactions, ask where its commit point is and who holds locks when that point fails. Apply it: XA is textbook 2PC, and a dead coordinator leaves lock-holding orphaned transactions behind; TiDB took the Percolator road, with the commit point on the primary key's row; CockroachDB writes the state as a single transaction record and the second phase touches only that record; Spanner and FaunaDB are the commercial Spanner-style and Calvin-style systems. Asked "how do you do a transaction across databases" in an interview, naming these commit points beats reciting two rounds of messages.
PENDING, and committing updates only that one record — "Lower latency than traditional 2PC commit protocol (w/o contention) because second phase requires only a single write to the transaction record instead of a synchronous round to all transaction participants."CockroachDB design doc (docs/design.md) · github.com/cockroachdb① The chapter's problem is atomic commitment: nodes must reach one irrevocable "commit or roll back" for a transaction that spans them.
② It is not consensus: consensus runs on a majority, atomic commitment needs unanimity, and any participant's veto uniquely fixes the outcome — a surviving majority is not enough.
③ 2PC: a voting round and a commit round; a Yes forfeits the right to back out and takes locks; the real commit point is the coordinator's own log. Its disease is not the 2 RTTs but the uncertainty window a crashed coordinator leaves, with participants holding locks until recovery.
④ 3PC adds PreCommit and two-sided timeouts to regain liveness, but tears atomicity under partition, so industry does not use it.
⑤ Calvin: agree on the input order (10ms batches plus Paxos), execute deterministically on every replica, negotiate nothing; the price is one-shot transactions with known read/write sets.
⑥ Spanner: 2PC over Paxos, so the coordinator is a group and blocking is demoted to a leader change; TrueTime's ε and commit wait align timestamp order with real order.
⑦ Percolator: data / lock / write columns; landing the primary row's write record is the commit point, leftover locks are cleaned by later readers, and no coordinator stands by.
⑧ Coordination avoidance: confluent invariants (I-confluence) need no coordination, and RAMP delivers read atomicity with versions plus metadata. The first engineering question is always whether the transaction can avoid crossing shards.