Managing Critical State: Distributed Consensus for Reliability

In one line

The chapter makes a single claim: the moment a group of processes must agree on some state, you are facing distributed consensus — there is no shortcut. Heartbeats, timeouts and timestamps are not ways around consensus; they are an incorrect implementation of it, and the incorrectness only shows up on the day the network partitions.

Glossary

Where it sits

This chapter lives in Part IV of the SRE book, "Managing Complex Systems," and is written by Laura Nolan. The two preceding chapters (Ch 21 overload, Ch 22 cascading failures) are about how a single service avoids destroying itself; this one steps up a level to how several machines keep their critical state correct. It is the most theoretical chapter in the book and maps directly onto DDIA Chapter 9; Ch 25 and Ch 26 both assume the state underneath them is trustworthy.

The problem it attacks

The chapter opens with three real (anonymized) outages that share one trait — each tried to avoid consensus. ① Split-brain: a primary/standby pair used heartbeats for liveness; network congestion timed the heartbeat out, the standby promoted itself, and the primary had never died. Both wrote files, reconciliation was manual, and some data was lost for good. ② Failover requires a human: another system avoided split-brain by declaring that only a person may designate the primary — so availability was pinned to human reaction time, plus a great deal of toil. ③ A homegrown group-membership algorithm: gossip for membership plus custom liveness checks; under network trouble the cluster split into two groups each convinced the other was dead, and wrote to both.

The author's diagnosis is unsparing: these systems needed consensus all along; their authors just wouldn't admit it. "Heartbeat plus timeout" treats a fundamentally unsolvable question — in an asynchronous network, does silence mean dead or merely slow? — as if it were solvable. The price isn't "one extra failover now and then." It is diverged data, and once data has diverged, nothing automatic can decide for you which copy is right.

While we're here, a widely mangled point: CAP says that during a partition you choose between consistency and availability — not that you must pick two of three on an ordinary Tuesday. Consensus systems choose C: the minority side would rather refuse service than diverge. That trades an irreversible outcome (split-brain) for a recoverable one (a short outage).

The core, explained

Why heartbeats and timeouts can never be enough

The root cause: in an asynchronous network, "crashed" and "slow" are indistinguishable. A missing heartbeat may be a dead process, or a long GC pause, or congestion on one hop — no external observation separates the two. All you can pick is a threshold for "how long counts as dead," and whatever you pick, some day it declares a healthy peer dead. This is what the 1985 FLP impossibility result says: in a fully asynchronous model, if even one process may crash, no deterministic algorithm both guarantees safety and guarantees a decision in bounded time.

Real systems make the trade in one direction only: give up "always terminates," never give up "always safe" — using timeouts and randomization (that's what Raft's randomized election timeout is for) to break ties. The cost is that on a truly bad network you may re-elect repeatedly and stay leaderless for a while, but you never end up with two leaders. The folk remedy makes the trade backwards: promote on timeout, and split-brain follows.

The two pillars: a majority, and one shared log

Pillar one: quorum intersection. Any two majorities share at least one member. Among five replicas, any two groups of three must overlap — and the overlapping replica remembers it already voted in the previous round, so it refuses to vote for a conflicting decision. Two disjoint majorities cannot exist, and split-brain is ruled out at the root. It also explains the preference for odd counts: six replicas still need four for a majority, tolerate the same two failures as five, and cost you one extra machine and one extra unit of latency.

Pillar two: the replicated state machine. What consensus really produces is not "one agreed value" but a log whose contents and order are identical on every replica. Each replica applies the same deterministic operations in the same order, so the states cannot drift. As the chapter puts it plainly: consensus is the building block; the replicated state machine is the thing you actually wanted — databases, lock services, config stores and message queues are all the same RSM behind a different interface.

Paxos, Multi-Paxos and Raft, in plain words

Paxos (Leslie Lamport) has a two-round skeleton. ① Claim a proposal number — a candidate carries a globally increasing number to a majority of replicas and asks "may I propose?"; each replica that agrees promises never to accept a smaller number afterwards and reports back the latest value it has already accepted. ② Propose and commit — the candidate proposes a value, but if round one surfaced any already-accepted value it must reuse that value; a majority accepting seals it. That "must reuse" rule is the entire secret of never contradicting a past decision: the new majority necessarily overlaps the old one, so it always sees the old decision and cannot overturn it.

Multi-Paxos is the practical form: running two full rounds per entry is expensive, so a stable leader takes round one once, and every later entry needs a single round — putting one write at one network round trip plus one fsync. Raft (2014) reorganizes the same thing into leader election, log replication and safety, with understandability as an explicit design goal. It is no faster and no safer than Paxos, but engineers can read it and implement it correctly — which is itself reliability. etcd, Consul, TiKV and Kafka's KRaft all use Raft; Zab is ZooKeeper's variant.

One order-of-magnitude difference that gets overlooked: all of these tolerate only crash failures — nodes die but never lie — and tolerating f failures needs 2f + 1 replicas. Tolerating Byzantine failures, where a node sends contradictory messages on purpose, jumps to 3f + 1. Inside a data center, almost everyone builds only the former.

Five shapes consensus takes in practice

• ① A reliable replicated state machine — the fundamental shape; the four below are special cases of it.
• ② Replicated data and config stores — configuration, metadata, service-discovery tables. It is for low-volume, high-value data: the Chubby paper describes itself as "coarse-grained locking as well as reliable (though low-volume) storage." Don't park business data in it.
• ③ Highly available processing via leader election — one primary plus hot standbys, automatically re-elected. Leader election and consensus are the same problem, and this is precisely where most teams reach for a homegrown solution. GFS, Colossus and Bigtable all have this shape.
• ④ Distributed coordination and locking — locks and barriers. There's a lethal detail here; see below.
• ⑤ Reliable queuing and messaging — build the queue itself on consensus (who claimed which item, and for how long), or use atomic broadcast / pub-sub. Google's Photon relies on a Paxos-replicated IdRegistry so that ad clicks joined across data centers are never billed twice.

The lethal detail: a distributed lock must be a lease, and it must carry an increasing number. A lock holder can be frozen by a long GC pause, a VM suspend or a network problem without ever noticing; by the time it wakes, the lease has expired and someone else holds the lock — while it still believes it does. The fix is for the lock service to hand out a monotonically increasing sequencer (a fencing token), and for the downstream store to check it and reject writes carrying a stale one. Holding a lock is not correctness — the single most quotable line in the chapter.

"Consensus is too slow" is a myth

The chapter goes out of its way to rebut a widespread line: consensus algorithms are too slow and too low-throughput for serious systems. They are indeed more expensive than a single machine, but the expense sits in two predictable places. Network round trips — a commit waits for a majority to answer, so the floor on write latency is the round trip to the third-fastest replica (with five). Intra-data-center RTT is typically sub-millisecond, cross-DC within a region a few milliseconds, cross-continent tens of milliseconds, and trans-oceanic a hundred-plus milliseconds — that floor is set by the speed of light. Durable writes — the log must be fsynced before you dare acknowledge: typically a few milliseconds on spinning disks, down to sub-millisecond on SSD/NVMe.

The optimizations are a short list. A stable leader removes phase one. Batching merges many proposals into one fsync and one broadcast, lifting throughput at a small cost in per-entry latency. Pipelining sends the next entry before the previous is acknowledged while preserving order, and pays off most on high-bandwidth, high-latency links. Fast Paxos lets clients send directly to all replicas, skipping the hop through the leader, at the price of a larger quorum. Quorum leases give some replicas a read lease over some of the data, so reads are local and still strongly consistent. And since the leader itself is the throughput ceiling, shard into many consensus groups — Spanner runs one Paxos state machine per tablet.

Deployment and monitoring: how many, where, and what to watch

How many. n replicas tolerate (n-1)/2 failures. Google's default is five, for a very practical reason: you want to survive one unexpected failure while one replica is down for planned maintenance. Three replicas can't do that — during the maintenance window you have zero redundancy. Beyond five, fault tolerance grows slowly while latency and cost keep climbing.

Where. The iron rule is that a majority must not sit inside one failure domain. Five replicas across three data centers (2 + 2 + 1) survive the loss of any one; all five in one room means the room takes everything with it. But the wider you spread, the higher the write latency, because a majority now includes a distant replica. The leader should sit near where the writes are. That's the other half of the GitHub lesson: allowing automated promotion across a continent lets the system make a decision that is bad for both latency and consistency at the worst possible moment.

What to watch. Healthy replica count; whether a leader exists and how often it changes; log index and how far each replica lags; proposals seen versus accepted; throughput and latency distribution; network round-trip time and fsync wait. A rule of thumb: a flapping leader, or one persistently lagging replica, predicts trouble earlier than "overall latency is a bit high" — it means the system is already re-electing repeatedly and simply hasn't fallen over yet.

Key trade-offs

Table 1 · Homegrown heartbeat+timeout vs. an off-the-shelf consensus system

Table 2 · Replica count and placement: tolerance, latency, cost

Table 3 · What you want to do → which shape to use

Why it matters / in real systems

This chapter answers an interview question you will almost certainly be asked: "how would you build highly available primary failover?" The expected answer is not "heartbeats and a virtual IP" — it is hand leader election to a consensus system, and fence writes downstream with a token. Nearly everything around you is an instance of it: Kubernetes keeps all cluster state in etcd (Raft); ZooKeeper (Zab) long served as the coordination layer for HBase and older Kafka; CockroachDB and TiKV made "one Raft group per data shard" standard; Spanner runs one Paxos group per tablet.

Pitfalls and debates

• Treating a lock as a correctness guarantee. Without a fencing token, a distributed lock is paper against a long GC pause or a VM suspend (Fig 3).
• The consensus system becomes a global single dependency. Because it works so well, everything quietly assumes it is always up. Google's counter-move is to take Chubby down on purpose, on a schedule — the same lesson the SRE book repeats elsewhere: availability far above what you promised teaches everyone to depend on the excess.
• CAP treated as a buffet. It forces the choice between C and A only during a partition, and it is not an argument that "therefore we don't need consistency."
• "Consensus is too slow" is usually untested. The real bottlenecks are where the leader sits and cross-region RTT, not the algorithm.
• Raft is not "more correct" than Paxos. Their safety properties are the same; Raft wins on understandability and on describing membership change completely — and membership change is exactly what homegrown implementations get wrong, which is the strongest argument for not writing your own.
• Period limits. Written in 2016, when the Raft ecosystem was young; since then etcd spread with Kubernetes and Kafka replaced ZooKeeper with KRaft. The core judgment — if you need consensus, use something that exists — has only been reinforced.

Takeaways