Book Deep Read · Database Internals · Chapter 14
Database Internals · Ch 14 · Alex Petrov · 2019
When you tap "transfer sent," it isn't one machine keeping the books. It's three or five machines, each keeping its own copy. This chapter answers a blunt question: how do you guarantee those ledgers stay the same ledger? Not "roughly in sync" — but "nobody can ever produce two contradictory versions." Computing has a name for that job: consensus.
Picture five people in five cities with nothing but patchy walkie-talkies, trying to settle on a dinner time. Signals drop, people step away, and worst of all: you can never tell whether someone left or is just frozen for three seconds and about to come back. You have to settle on a time, and once settled, everyone who asks later must get the same answer — even the two who never heard it.
The obvious fix is "pick a chief; the chief decides." The trouble starts when the chief goes quiet: the rest promote themselves at the same time, and now there are two chiefs and two contradictory ledgers — the condition engineers call split brain. Worse, the old chief may only have been stalled; he still believes he's in charge and keeps writing. This isn't hypothetical: one garbage-collection pause or one flaky cable is enough to manufacture two very confident chiefs.
The first idea is "more than half." No decision counts unless more than half the group nods. The beauty is this: any two groups that each hold more than half must share at least one member — among five people, any two trios overlap. That overlapping person is a living archive. The moment a new round opens, they speak up: "hold on, we already settled on nine o'clock." So a new decision can never overturn an old one; it can only repeat it.
The second idea is "seniority check at every changeover." Each new chief gets a numbered term that only ever goes up. To become chief you need votes from more than half, and people only vote for someone whose records are no shorter than their own. So the incoming chief already holds everything that was ever settled and can't erase it on arrival. Add one rule — "the moment you see a higher term number, step down" — and the stale chief is told he's last season's news the instant he speaks.
In practice the world runs on two tellings of one story: Paxos, correct and famously hard to follow, and Raft, which deliberately retells the same thing as a manual you can implement from — the one behind etcd, Kubernetes, CockroachDB and modern Kafka. The honest cost: every write waits for more than half the group to nod, and if three of five machines die, the system would rather stop writing altogether than produce two versions.
Consensus isn't "majority rule by vote." It's a set of no-take-backs rules: everything needs more than half to agree, and any two such groups must overlap in at least one member who remembers the last decision — so history can only be continued, never rewritten.
Want the two phases of Paxos, Raft's terms and logs, and what Byzantine tolerance actually costs? → Switch to the deep read
Consensus is not "voting by majority." It is how a set of machines that can crash at any moment and whose messages arrive late or out of order agree, irrevocably, on the order of a sequence of operations. This chapter puts Paxos, Raft and Zab side by side, and they all converge on the same shape: elect one leader to impose an order, then pin his log down with a majority. What makes consensus hard was never choosing a value — it is proving that a value already chosen can never be rewritten by whoever comes next.
⌊N/2⌋+1 out of N.0.5–2ms inside a datacenter, 1–3ms across availability zones in one region, and 70–150ms between continents.This is the closing chapter of Part II ("Distributed Systems") and of the book. It follows Ch 9 on failure detection (a timeout can always mistake slow for dead), Ch 10 on leader election (electing a leader does not by itself make him unique), Ch 11 on replication and consistency, and Ch 13 on distributed transactions (2PC needs unanimity, so one dead coordinator leaves everyone holding locks). This chapter assembles those incomplete parts into one protocol that can argue for its own correctness — the thing real systems call the cluster brain: ZooKeeper, etcd, Consul, CockroachDB, TiKV.
Every earlier chapter left a hole: failure detection mistakes slow for dead; an election can produce one leader on each side of a partition; replicated logs can fork; atomic commitment needs everyone, so one unreachable node blocks the lot. Consensus has to close those holes with a protocol that delivers three properties at once — agreement (no two nodes decide different values), validity (the decided value was actually proposed by someone, not invented), and termination (a decision is eventually reached).
The premise is harsh. By the FLP impossibility result, in a purely asynchronous network where even one node may crash, no deterministic algorithm can guarantee both safety and liveness. So every practical protocol makes the same bargain: safety is held unconditionally; liveness is bought with timeouts and randomization — which is why every consensus implementation hides a pile of timeout knobs.
What happens if you skip it? Take Kubernetes: the entire truth of the cluster — which Pod runs where, who backs a Service, who holds a lock — lives in a 3- or 5-node etcd. If a partition let both sides accept writes and answer "ok," the scheduler would act on two contradictory truths and start containers accordingly: the same cloud disk mounted and written by two processes at once. Consensus is where the system's single source of truth comes from; if it is wrong once, every correctness property above it collapses.
The chapter opens with broadcast rather than dropping Paxos on you. Best-effort broadcast only promises "I sent it" — if the sender dies mid-way, some receive and some don't. Reliable broadcast promises every correct node eventually receives it, but in whatever order. Atomic broadcast (total order broadcast) adds the decisive clause: every node receives the messages in exactly the same order.
The key insight is that total order broadcast and consensus are equivalent problems. Given total order broadcast, treat "the first value broadcast" as the chosen one and you have consensus; conversely, run one instance of consensus per log position and you have total order broadcast. What a database actually wants was never "pick a value" — it is every replica replaying the same writes in the same order. That is why consensus always shows up in engineering wearing the costume of "replicate an identical log." ZooKeeper's Zab is designed straight from this view: leadership is divided by epoch, with a discovery phase (the new leader finds the most up-to-date log), a synchronization phase (that log is pushed onto a quorum) and a broadcast phase (steady-state appends, one at a time).
Paxos splits nodes into three roles (one machine can play all of them): the proposer proposes, the acceptor votes and remembers, the learner finds out the result. One round of Basic Paxos takes two phases:
n and asks a quorum "will you take n?" An acceptor that has seen nothing higher promises to reject anything numbered below n from now on — and returns the highest-numbered value it has already accepted.So phase 1 is not a vote at all — it is preemption plus interrogation. Preemption invalidates every older proposal still in flight; interrogation drags back any history that may already have been decided. Quorum intersection is what makes the interrogation airtight: any two majorities share at least one node, and that node remembers what it last accepted. All of Paxos reduces to one sentence — latecomers may not rewrite history, only keep repeating it.
The cost is concrete too: 2 RTTs and 2 disk fsyncs per decided value, and worse, two proposers can preempt each other's ballot numbers forever (livelock). Those two costs motivate every variant below.
Multi-Paxos makes a plain but decisive change: since re-running phase 1 for every log entry is too expensive, elect a distinguished proposer (a leader) who runs phase 1 once for the whole log, leaving each subsequent command just one phase-2 round trip. The leader holds the role via a lease — one of the rare places where a consensus protocol leans on physical clocks: nobody may start an election while the lease holds, so clock drift must be bounded, or safety rests on operations rather than on the algorithm.
Three variants worth remembering, each selling one thing to buy another:
⌈3N/4⌉ rather than a simple majority) and a fallback to the classic path whenever two clients collide — so it only pays off when conflicts are rare.|Q1| + |Q2| > N. With N=4 you can run Q1=3, Q2=2: steady-state writes wait on only 2 nodes, pushing the cost onto the rare election.Raft's goal was never speed — it was understandability. Its authors say plainly that the distance between the published description of Paxos and a working system is so large that every team ends up inventing its own details. Raft nails those details down with three things:
150–300ms) to break ties, so a typical failover completes in a few hundred milliseconds. Logs flow only from leader to follower; a follower's conflicting tail is truncated and overwritten — there is no such thing as merging.Every protocol above assumes crash-stop: a node is either correct or silent. Byzantine faults allow a node to emit arbitrary, mutually contradictory messages — compromised, firmware-buggy, or simply hostile. PBFT's price is visible at a glance: tolerating f traitors needs 3f+1 nodes (crash-stop needs only 2f+1), a three-phase exchange of pre-prepare / prepare / commit, and message volume growing as O(N²). The conclusion is equally clear: inside your own datacenter, run by one organization, the Byzantine assumption rarely pays for itself; its real stage is mutually distrusting parties, of which blockchains are the industrialized version.
Safety is the same across all of them (no two contradictory committed values). The differences are all in who imposes the order, how many rounds steady state costs, and how hard it is to implement correctly.
| Protocol | Steady-state write | Leader | Used by | Cost / fit |
|---|---|---|---|---|
| Basic Paxos | 2 RTTs + 2 fsyncs | none | almost never used directly | competing proposers can livelock; a teaching tool and a foundation |
| Multi-Paxos | 1 RTT | yes (lease) | Chubby, Spanner's per-shard groups | the papers leave gaps each team fills differently; hard to align implementations |
| Raft | 1 RTT | yes (strong leader) | etcd, Consul, TiKV, CockroachDB, Kafka KRaft | the log must flow one way; no parallel writes from several nodes |
| Zab | 1 RTT | yes (epoch) | ZooKeeper | tightly bound to ZooKeeper's session and ordering semantics; hard to reuse alone |
| EPaxos | 1 round when conflict-free | none | research and a few experimental builds | complex dependency graph and recovery; slower as conflicts rise |
| Flexible Paxos | can wait on just 2 nodes | yes | a tuning option in some Paxos implementations | moves cost to election: recovery must reach more nodes |
| PBFT family | several rounds, O(N²) messages | yes (view) | consortium chains, cross-organization ledgers | needs 3f+1 nodes; markedly worse throughput and scale |
How many nodes should a cluster have? Twice the nodes is not twice as good — write latency is set by "the k-th fastest node."
| Size | Tolerates | Each write waits for | When to pick it |
|---|---|---|---|
| N = 3 | 1 node | the 2nd fastest node | single datacenter, latency-sensitive; during a rolling upgrade you effectively have no redundancy |
| N = 5 | 2 nodes | the 3rd fastest node | the production default; still tolerates 1 failure mid-upgrade |
| N = 7+ | 3 nodes | the 4th fastest node | rarely worth it: bigger quorums, worse tail latency, more to operate |
Geography makes this table painful. Across three availability zones the RTT is roughly 1–3ms and consensus writes are tolerable; spread the replicas across continents (70–150ms RTT) and every write waits on a transoceanic round trip — which is exactly why Spanner needs TrueTime and why EPaxos bothers with commit-to-the-nearest-replica.
The correct engineering use of consensus compresses into one rule: let it govern the small and precious, never the large and numerous. Small and precious means metadata and leadership — who owns a shard, what the configuration is, who holds a lock. Kubernetes puts the whole truth of a cluster into etcd, but that is usually tens of megabytes to a few gigabytes; the business data travels another replication path. The moment every business write is funnelled into one consensus group, throughput is pinned by one leader's fsync plus one quorum round trip.
The industry's standard answer is partitioning: CockroachDB and TiKV cut data into many ranges (CockroachDB's default range is about 64MB) and run an independent Raft group per range, so thousands of groups advance in parallel while each group remains textbook Raft. The other common optimization is the lease read: the lease-holding replica answers reads locally instead of running a consensus round per read.
10,000 writes/sec; Kubernetes and others take it as cluster truth — evidence that one Raft group is sized for metadata, not for bulk business writes. etcd official README ↗64MB, three replicas) maintains its own instance of a distributed consensus algorithm, with range leases separate from Raft leadership so the lease holder can serve reads locally — a public specimen of the "slice consensus small, then parallelize" route. CockroachDB design.md ↗① Consensus = total order broadcast: a database doesn't want "a chosen value," it wants every replica replaying one log in one order (the replicated state machine).
② The point of a majority is intersection: any two majorities share a node, that node remembers history, so a chosen value can never be rewritten by a latecomer.
③ Paxos's two phases: phase 1 claims a ballot number and interrogates history; phase 2 writes the value — and any old value that comes back must be re-proposed instead of your own.
④ Multi-Paxos's core optimization: elect a leader, run phase 1 once, leave 1 RTT per command in steady state; leadership rests on a lease, hence on bounded clock drift.
⑤ Each variant sells something: Fast Paxos trades a bigger fast quorum for one hop; EPaxos trades a dependency graph for having no leader; Flexible Paxos needs only |Q1|+|Q2| > N, pushing cost onto elections.
⑥ Raft's three pillars: terms as a logical clock, randomized election timeouts (150–300ms), and an election restriction guaranteeing the new leader's log is current — logs flow one way only.
⑦ Byzantine tolerance is expensive: 3f+1 nodes, three phases, O(N²) messages — worth it only when the participants distrust each other.
⑧ FLP in practice: safety is held unconditionally, liveness is bought with timeouts and randomization.
⑨ Where it lands: consensus governs metadata and leadership; data scales by partitioning into many groups (multi-raft, one group per range), never by funnelling every write through one.