Consistency and Consensus: Linearizability, the Honest Version of CAP, and Total Order Broadcast

The previous post concluded that no single node’s judgment can be trusted, so truth can only be decided by a majority. This chapter is about how a majority decides safely — the theoretical climax of DDIA. The algorithmic details (how Raft, Paxos and Zab vote and change terms) I took apart in the SRE consensus post; this one takes the three pillars unique to Ch9: what the strongest consistency guarantee looks like, what CAP actually says, and the true face of that mystical word “consensus”.

Linearizability: making the system “look like a single copy of the data”

The ceiling of consistency guarantees is called linearizability, and its definition can be put plainly: the whole system behaves as if there were only “one” copy of the data, and every operation is atomic — once anyone has read the new value, everyone afterwards must read the new value and never see the old one again. DDIA explains it with a football match:

What truly can’t do without it? The list is short: uniqueness constraints (two people grabbing the same username or the last seat at once — at heart “everyone must agree on who was first”), leader election (two nodes must never both believe they’re the leader), and timing dependencies across systems. And it’s shockingly expensive: synchronous single-leader replication is slow, Dynamo-style quorums strictly speaking aren’t linearizable either (unless you add synchronous read repair), and during a partition you have to sacrifice availability — which brings us to that over-quoted theorem.

The honest version of CAP: a partition isn’t something you “choose”

CAP is usually told as “consistency, availability, partition tolerance — pick two”. DDIA is blunt about this, and its criticism deserves to be carried over in spirit: a network partition (P) is not an option you can decline; it’s a fault that “will happen”. You can’t “choose not to have partitions” any more than you can choose not to have earthquakes. So the real trade-off is:

• When a partition happens: you can only choose between C (refuse service to stay consistent) and A (keep serving, possibly inconsistently) — this is the only thing CAP says.
• In normal times without a partition (the vast majority of the time): CAP says nothing at all; what you’re really trading is consistency vs latency (linearizable reads and writes need cross-node coordination, and that’s slow).

So coarse labels like “we’re an AP system” or “that’s a CP database” mostly don’t survive a follow-up question — different operations in the same system often sit at different points. Rather than memorising three letters, ask two concrete questions: during those minutes of partition, what do you protect? In normal times, how much latency will you pay for how much consistency?

The true face of consensus: total order broadcast is “everyone agreeing on the same log”

“Consensus” sounds mystical; DDIA gives it an equivalent form any engineer grasps instantly — total order broadcast: every node receives the same sequence of messages in the same order, none lost, none duplicated. And that’s the same problem as consensus: agreeing on message order = doing consensus repeatedly (what’s message 1? what’s message 2? …). Its power lies here:

A few common “fake consensuses” are also exposed in this chapter: 2PC is not consensus — when the coordinator dies after prepare, all participants block waiting, and the loss of a single point halts the whole game; consensus algorithms cure precisely this with a majority + the ability to change leader. Lamport timestamps can produce a total order after the fact, but can’t answer “do we grant this username” right now — for an immediate ruling you still need consensus. And the epoch / term number in consensus algorithms (which stops a stale leader waking up and causing havoc) should look familiar — it’s a relative of the fencing token: once again a monotonically increasing number plus a majority; the final answer of distributed systems is always those two ingredients.

Reflections

The places that need linearizability are an order of magnitude fewer than you think

This chapter first makes the strongest guarantee sound tempting, then honestly tells you how expensive it is — and my practical conclusion is: what truly can’t do without linearizability is almost only two categories, “uniqueness” and “who’s the leader”, and what they share is “the whole world must agree on one ruling immediately”. For everything else, the cheap dishes on the consistency menu (read-your-writes, causal) are almost always enough. It also makes me ask one more question of any “our system needs strong consistency” requirement: which operation, which ruling needs it? Eight times out of ten, digging down leaves a single uniqueness constraint — so fence the expensive guarantee around that small patch (hand it to a database unique index or a coordination service) and relax the rest. Consistency is like safety stock: maxing it out everywhere is waste; stocking it at the critical points is skill.

”Consensus = one log everyone agrees on” — this equivalence let me see five systems as one

Total order broadcast ≡ consensus is the biggest “aha” I got from DDIA. Consensus went from “mysterious voting algorithm” to one sentence: everyone shares the same log whose order is beyond dispute, and each copies it faithfully. That instantly connected five points on my map that had been isolated: Raft’s replicated log, ZooKeeper‘s zxid sequence, the offset order of a Kafka partition, a database’s WAL replication stream, even Redis’s replication stream — all the shape “one log + apply in order”, differing only in how strictly that log is protected (majority consensus, a single leader, or best effort). Once you recognise the shape, you can nearly guess a new system’s replication docs: find where its log is, who decides the order, what protects that order. One equivalence beats ten architecture documents.

What CAP taught me isn’t theory, it’s the discipline of refusing coarse labels

The biggest thing I took from DDIA’s criticism of CAP is a discipline of questioning. “We’re an AP system” sounds professional in an architecture meeting and says nothing at all — during a partition, which operation degrades? How? How much latency is paid for consistency in normal times? This merges with what I’ve found all along: consistency is a menu, not a switch, isolation levels are a spectrum, not a boolean — nearly every important property of distributed systems is “per operation, in tiers”, and any phrasing that compresses it into one letter is dodging the real design decision. Now, when the three-letter theorem gets wheeled out, I ask two questions: during those minutes of partition, what do you protect? In normal times, how much latency do you pay? Only if you can answer have you actually thought about it. DDIA Part II ends here — the network drops, clocks drift, nodes play dead, and with one log protected by a majority we’ve built small islands of determinism in a probabilistic world. In the next part, data starts flowing between systems.