Deep-Read · DDIA · Chapter 9
Designing Data-Intensive Applications · Ch 9 · Martin Kleppmann · 2017
Every large website you use runs not on one computer but on hundreds or thousands working together. They must agree on certain facts: who is the leader (who's in charge), whether an order actually went through, whether a username is already taken. This chapter is about how a bunch of computers — each of which can crash, and whose messages can be lost — reliably get on the same page. That's consistency and consensus.
Picture a room of people sharing one notebook — except each person actually holds their own photocopy. Ideally: the instant anyone writes a line, everyone's next glance shows the same latest value, and nobody ever reads a stale one. That effect — a pile of copies that behaves as if there were only one — is this chapter's most important idea, called linearizability. The catch: syncing copies takes time, so a careless glance shows you what someone wrote three seconds ago.
If the computers disagree, chaos follows: two machines both think they're the leader (called split brain) and a charge gets applied twice; two people both grab the same username. Worse, the network partitions — half the machines suddenly can't reach the other half, and nobody can tell whether the other side truly died or is just temporarily unreachable. Making one unified decision in that half-light is the hardest thing in distributed systems.
The secret is surprisingly simple — vote, and require a majority. To get everyone to accept a fact, have more than half the machines vote for it. Why more than half? Because any two majorities must share at least one member, so you can never simultaneously elect two contradictory outcomes — split brain is blocked at the root. Electing a leader is one such vote; ordering events is another — everyone copies what happened into one shared ledger in the same order, nobody cuts in line, and the order is unified. This "reach agreement by majority" machinery is called consensus.
Good news: this stuff is fiendishly hard to get right, so don't build it yourself — off-the-shelf coordination services like ZooKeeper and etcd already package it; just call them for leader election, locks, and ordering. And remember the famous trade-off (CAP): once the network partitions, you can keep either consistency or availability, not both. Honestly, agreement isn't free — waiting for a majority on every decision is inherently slower than a single machine; that slowness is what buys you "never gets it wrong."
For a crowd of computers that crash and lose contact to reliably agree, the tool is a majority vote — which in one stroke handles leader election, ordering, and grabbing a unique name. The price is more latency, and when the network splits you must pick consistency or availability. Don't build it yourself — use ZooKeeper / etcd.
Want the real machinery — linearizability, total order broadcast, consensus and 2PC? → Switch to the deep read
This is the summit of DDIA's "Distributed Data" part: it gathers the earlier troubles (replication lag, partial failure, unreliable clocks) into one question — on an unreliable foundation, what is the strongest guarantee we can build? The answer rests on three pillars: linearizability — making a pile of replicas behave "as if there were only one"; ordering (causality and total order) — imposing one agreed order on events happening all over; and the book's crown jewel, consensus — getting a set of crash-prone nodes to agree on something. The key insight: linearizable storage, total order broadcast, and consensus are the same problem in three disguises; solve it and you get leader election, uniqueness constraints, and atomic commit all at once.
This chapter closes and crowns Part II, "Distributed Data." It builds on Ch 5 (replication and its consistency pitfalls), Ch 7 (transactions, the strong single-machine guarantees), and Ch 8 (the trouble with distributed systems — partial failure, unreliable networks and clocks). It turns those "bad news" chapters into a positive question: exactly how strong a guarantee can we build, and what do we pay for it? In practice it is the theoretical core of an entire class of systems: ZooKeeper, etcd, Google Chubby / Spanner, Raft / Paxos. Master it and you hold the key to distributed coordination.
Ch 8 laid out the bad news: networks drop and delay packets, nodes crash, clocks lie, and you cannot tell "a node died" from "it's merely slow / unreachable." In that half-light even the simplest needs break down — try to elect a leader and you may elect two (split brain), whose concurrent writes diverge; enforce a unique username and two requests hit different replicas, each thinking "nobody took it," so both succeed; make a cross-service order all-or-nothing and you may deduct stock but never collect payment.
The core question, then: on an unreliable foundation, can we build a "reliable abstraction" that lets the layer above pretend things aren't so bad? Just as transactions (Ch 7) let an app pretend "no concurrency, no crashes," this chapter delivers the distributed version of that magic — linearizable storage, a unified event order, reliable consensus. Without it you either live with fragility or hand-roll consistency over and over, hitting the same pitfalls each time.
What it is. Linearizability is the strongest single-object consistency guarantee. In one line: make the whole distributed system behave as if there were only one copy of the data and every read/write took effect atomically at one instant. At heart it is a recency guarantee — what you read is the result of the most recent write, not some stale snapshot on one replica.
Intuition and the test. The key rule: once any read returns the new value, no later read may return the old one — even from a different replica. There is a "flip" instant when the value atomically changes from old to new; reads before it may see old, reads after must see new, with no flip-flopping in between. The timeline below shows this iron law for a register x.
Don't confuse it with serializability (common trap). Serializability is an isolation property of transactions — a set of multi-object transactions behaves as if executed one at a time in some serial order, regardless of whether that order matches real time. Linearizability is a recency guarantee on a single object. They are orthogonal; satisfying both is strict serializability, which only systems like Spanner provide.
Who can't live without it. Three cases have a hard need: (1) locking & leader election — all nodes must agree on a single, up-to-date "who holds the lock / who is leader," or split brain; (2) uniqueness constraints — usernames, account IDs, no overselling of stock all need "exactly one winner right now"; (3) cross-channel timing dependencies — the book's classic: a user uploads an image, the web server drops a "resize" job on a message queue, and if the queue delivers the job before the DB replica has the image, the resizer reads a stale replica without the file and fails. Only linearizable storage cures such cross-channel races.
Linearizability is powerful but expensive (the bill comes next section). Step back: many problems are really about ordering. Two kinds of order matter.
Causal order is a partial order. Causality says effect follows cause: you must see a message before you can reply to it. But two unrelated events (Alice edits her bio, Bob posts an update) are concurrent — causality does not order them. So causality is a partial order: some events comparable, some concurrent. Linearizability is a total order: pretending there is one copy, any two operations get a unique before/after. A total order always respects causality, so linearizability implies causal consistency.
Can we keep only causality and skip the pricey total order? Yes — and it's a sweet spot: causal consistency is the strongest consistency model that stays performant and available in the face of network delay and partitions, since it doesn't coordinate globally on every operation. In practice, stamp each operation with a logical clock (Lamport timestamp: each node keeps a counter + node id, taking the larger and incrementing) and you get a total order that respects causality.
But a total-order number still isn't enough. Lamport timestamps can order events uniquely after the fact, yet a uniqueness constraint needs a decision on the spot: two users grab @alice at once and you must know right now who's first — you can't wait until "all messages are collected and sorted." So ordering must be made real-time, deciding order as events happen. That is —
Total order broadcast (a.k.a. atomic broadcast). It is a protocol for exchanging messages between nodes with two safety properties: reliable delivery (no message lost; if one node gets it, all healthy nodes eventually do) and totally ordered delivery (every node receives all messages in exactly the same order). Think of it as one shared, append-only ledger for the whole network: anyone who wants to record something drops in a message, the system assigns it a globally unique slot, then replays it identically to every node. It does three jobs at once: database replication (replicas replay in the same order = state machine replication), serializable transactions (feed transactions into one log order), and fencing tokens (the slot number is monotonically increasing — the anti-zombie-lock token).
The chapter's deepest insight lives here: total order broadcast, linearizable compare-and-set, and consensus are equivalent problems — solve one and you can solve the rest. Total order broadcast "decides the next message," which is just repeatedly reaching consensus on "the next value"; conversely, running consensus over and over yields a sequence of ordered values = total order broadcast. So cracking consensus is one key that opens three locks.
What consensus requires. Getting nodes to agree on a value, formally, needs four properties: uniform agreement (no two nodes decide differently), integrity (no node reneges on a decided value), validity (the decided value was proposed by some node), and termination (as long as a majority is alive, a decision is reached and it never hangs forever). The first three ensure safety; the fourth ensures liveness — and it is exactly termination that separates consensus from "2PC, which merely deadlocks."
How it works (plainly). The mainstream fault-tolerant algorithms — Paxos, Raft, Zab, Viewstamped Replication — follow a strikingly common recipe: two rounds of voting. Round one elects a leader, carrying an increasing epoch number that bumps by one each time the leadership changes; round two has the elected leader propose a value and collect a majority of votes. The anti-split-brain magic hides in "any two voting majorities must intersect": if an old leader hasn't died yet but a new one is elected, the new leader's election majority contains a node that has seen the higher epoch and will reject the old leader's proposal — so the old leader's write can't reach a majority and is void. Thus only one leader can make progress at a time.
A close cousin of consensus is atomic commit: a transaction spanning several machines (say, two shards) must all commit or all abort, never half-and-half. The classic answer, two-phase commit (2PC), adds a coordinator. Phase 1, "prepare": the coordinator asks all participants "can you commit?"; a participant that answers "yes" has made an irrevocable promise (even if it crashes, on recovery it must still be able to commit). Phase 2, "commit / abort": if any said "no," the coordinator tells everyone to roll back; only if all said "yes" does it tell everyone to commit.
2PC's Achilles' heel: the coordinator is a single point. If the coordinator crashes at the very instant when "everyone answered yes but the commit order hasn't gone out," participants are stuck in doubt — they've promised and can't self-abort, yet get no instruction, so they can only hold their locks and wait for the coordinator to come back, freezing the affected data meanwhile. This is the watershed between 2PC and true fault-tolerant consensus: 2PC lacks consensus's fourth property, termination — once the coordinator falls, the protocol can block indefinitely. (Three-phase commit tries to patch this hole but relies on an assumption — bounded network delay — that doesn't hold in reality, so it's rarely used.)
This chapter's soul is the spectrum "stronger guarantee, higher cost." First the consistency-model spectrum, then the trade-off CAP forces, then 2PC vs fault-tolerant consensus.
Table 1 · Consistency-model spectrum: strength ↔ performance / availability
| Model | Guarantees | Available under partition? | Hurt by network delay? | Representative systems |
|---|---|---|---|---|
| Linearizable | looks like one copy; reads are always latest | No (must stall — CP) | Yes — every op coordinates, slow | ZooKeeper, etcd, Spanner (reads/writes) |
| Causal | respects causal order; concurrent ops unordered | Yes (can keep serving) | No — "strongest model without a perf penalty" | causal / session modes in some databases |
| Eventual | only promises "converges eventually"; stale reads allowed | Yes (AP) | No — fastest | Cassandra, Dynamo-style leaderless |
Table 2 · CAP: under a partition, pick consistency or availability
| CP: keep consistency, drop availability | AP: keep availability, drop consistency | |
|---|---|---|
| Behavior under partition | the minority side refuses service (better unavailable than stale) | both sides keep serving, then converge / merge conflicts later |
| Fits | leader election, locks, uniqueness, non-negative balance | shopping carts, like counts, read-heavy data tolerant of brief staleness |
| Examples | ZooKeeper, etcd, HBase | Cassandra, Riak, DynamoDB (tunable) |
| Common misread | CAP forces the choice only when a partition is actually happening; with no partition you can have both. It also ignores latency — linearizability is slow even without a partition, and most systems drop it for performance, not fault tolerance. | |
Table 3 · Distributed atomic commit: 2PC vs fault-tolerant consensus
| Two-phase commit (2PC) | Fault-tolerant consensus (Raft / Paxos) | |
|---|---|---|
| Goal | all-or-nothing commit across nodes | agree on a sequence of values = total order broadcast |
| Coordinator / leader | single coordinator, single point | elected leader, can fail over |
| On coordinator/leader crash | participants in doubt, blocked holding locks (no termination) | a live majority elects a new leader and continues |
| Nodes needed | every participant must vote "yes" | only a majority alive |
| Real-world cost | XA transactions measured an order of magnitude slower than single-node; lock contention while pending | frequent elections / flaky networks hurt; fixed membership, timeout-based failure detection |
Rule of thumb: need a "single global decision" (leader, lock, uniqueness) → hand it to a linearizable coordination service (ZooKeeper / etcd), don't hand-roll it; can tolerate brief inconsistency and want maximum availability and low latency → go eventual with a leaderless store; want "the strongest consistency without a perf penalty" in between → causal. Avoid cross-database transactions when you can; if you must, respect 2PC's blocking risk and make the coordinator itself highly available.
This chapter is the common baseline for coordination in interviews and architecture. Any "who is leader," "who owns the lock," "in what order" question ultimately reduces to consensus; and industry's consensus implementations nearly all converge on the same parts: keep a small slice of critical metadata (who's leader, shard ownership, config) in memory and replicate it across nodes with fault-tolerant total order broadcast — precisely the skeleton of ZooKeeper (Zab) and etcd (Raft). They expose four things: linearizable atomic operations (compare-and-set for locks and leader election), total ordering of operations (the zxid / index is the fencing token), failure detection (sessions + ephemeral nodes; a disconnected client's lock auto-releases), and change notifications (watches). Kafka, HBase, and Kubernetes lean on them for election, shard assignment, and service discovery — solving the hardest problem, consensus, once, and reusing it everywhere.
① In one line: build a "reliable abstraction" on an unreliable foundation — linearizability, ordering, consensus are the three pillars.
② Linearizability: make replicas look like one copy, each op atomic; once a new value is read it can't fall back. It's a recency guarantee, not serializability (transaction isolation).
③ Who needs it: leader election / locks, uniqueness constraints, cross-channel timing (the image-resize race).
④ Ordering: causality is a partial order (concurrency unordered), linearizability a total order that implies causality; causal consistency is "the strongest consistency with no perf penalty."
⑤ Total order broadcast = one shared append-only log doing three jobs: state machine replication, serializable transactions, fencing tokens (slot numbers).
⑥ Crown jewel: total order broadcast ≡ linearizable CAS ≡ consensus. Consensus blocks split brain via two rounds of voting + increasing epochs + intersecting majorities.
⑦ Atomic commit uses 2PC, but the coordinator is a single point and its crash means in-doubt blocking — it lacks consensus's termination, so it isn't fault-tolerant consensus.
⑧ CAP forces the consistency-vs-availability choice only under a partition, and ignores latency; it isn't "pick 2 of 3."
⑨ In practice: ZooKeeper (Zab) / etcd (Raft) solve consensus once and expose locks, election, ordering, failure detection, watches; Chubby, Spanner, the Raft ecosystem, and Jepsen are four hard pieces of evidence.
⑩ Rule of thumb: need a unique global decision → use a coordination service, don't hand-roll; can tolerate inconsistency → go eventual for availability and low latency.