Every distributed system has some small amount of state that all its parts must agree on: who is the leader, what the configuration is, which task holds a lock. Getting that wrong gives you split brain and data loss. This chapter is the SRE book's treatment of distributed consensus: not a proof of Paxos but a guide to when you need it, how the systems built on it behave, and what to watch when you run one.

Chubby, Zookeeper and etcd are the practical faces of this material. The chapter's argument is that whenever you find yourself designing a protocol for "the primary tells the secondary" you are reinventing consensus badly, and you should use one of these instead.

In one minute

• Problems that look different but all need consensus: leader election, group membership, distributed locking, replicated configuration, and keeping a replicated state machine consistent.
• The CAP theorem says you cannot have consistency, availability and partition tolerance all at once. Consensus systems choose consistency and give up availability in a minority partition. ACID versus BASE is the same trade-off in datastore terms.
• Ad hoc approaches (heartbeats to decide the leader, "the primary with the lowest IP wins", relying on timeouts) fail under partitions and clock drift, often producing two leaders.
• Paxos: proposers obtain a majority of promises for a sequence number, then get a majority to accept a value. Because any two majorities overlap, at most one value is chosen per slot. Multi-Paxos elects a stable leader to skip the first phase. Related algorithms: Raft, Zab, Mencius, Fast Paxos.
• Patterns: replicated state machine (apply the same ordered operations everywhere), replicated datastore and configuration store, leader election as a special case of consensus, distributed coordination and locking (with lease expiry), reliable distributed queues and messaging.
• Performance: a round of Multi-Paxos with a stable leader costs one round trip to a quorum. Latency is bounded by the slowest member of the fastest quorum, so place replicas deliberately and use witness or quorum lease tricks to reduce it. Batching, pipelining and separating the log disk from the state disk improve throughput.
• Deployment: use an odd number of replicas (3 or 5), spread them across failure domains, and plan for the majority of replicas failing scenario; groups of 5 tolerate 2 failures.
• Monitor: number of members and their state, proposals seen and agreed, leader changes, consensus latency, throughput, and the lag of each replica. Alert on persistent lack of a leader or on a replica falling behind.

Motivating the use of consensus: distributed systems coordination failure

Two stories. In the first, a system uses a heartbeat to decide whether the primary is alive; a network partition makes both sides believe they are the primary and both accept writes. In the second, a cluster of servers each tries to be sure of group membership by pinging the others, and a slow network produces inconsistent views in which half the cluster thinks the other half is dead. Both are consensus problems solved without a consensus algorithm. The chapter also notes that the Fischer, Lynch and Paterson result says asynchronous consensus with even one crash is impossible in theory, and that practical algorithms work because they assume timeouts and rely on the network eventually behaving.

How distributed consensus works

Consensus is agreement on a value among a group of processes where some may fail. Paxos achieves it in two phases. A proposer picks a sequence number higher than any it has seen, sends a prepare to the acceptors, and collects promises from a majority that they will not accept proposals with lower numbers; the promises also carry any value they have already accepted. The proposer then proposes a value (either the highest-numbered already-accepted one or its own) and if a majority accepts, the value is chosen. Since any two majorities share at least one member, two different values can never both be chosen. Multi-Paxos extends this to a sequence of values by letting a leader skip the prepare phase while its leadership is unchallenged, so each operation costs a single round trip.

System architecture patterns for distributed consensus

Replicated state machines. If every replica applies the same operations in the same order, every replica reaches the same state. Consensus provides the ordered log of operations. Almost every consensus-based system is a replicated state machine with an application layer on top.

Reliable replicated datastores and configuration stores. Chubby, Zookeeper and etcd store small amounts of data with strong consistency. Reads can be served from the leader for strong consistency or from any replica for lower latency and possibly stale results; the chapter notes that true strong reads from followers need either a quorum read or leader leases.

Highly available processing using leader election. Leader election is consensus on a single value: who leads. The leader then does the work (such as scheduling in a cluster manager), and the state it manipulates should be stored in the replicated store so that a new leader can take over.

Distributed coordination and locking. Locks held by a process that dies would never be released, so locks are leases with expiry, and lock holders must handle losing the lease. Barriers, which release a group of processes at once, are built the same way.

Reliable distributed queuing and messaging. Queues are a leader-elected workload with a replicated log. The chapter cautions that a queue with at-least-once delivery requires idempotent consumers and that exactly-once needs consensus on the consumer side too.

Distributed consensus performance

Consensus is not inherently slow; the cost is a quorum round trip per operation. Multi-Paxos with a stable leader reduces this to one round trip. For geographically distributed replicas, place them so that a quorum can be formed from nearby replicas, and consider which replica should be leader based on where writes come from. Fast Paxos lets clients propose directly to acceptors but can be slower on wide-area networks where the leader is closer to a quorum than the client is. Quorum leases allow consistent reads from a replica for a time window.

Throughput improves with batching (many operations per consensus round) and pipelining (several rounds in flight, with a window to limit it). Disk writes dominate latency on a single round, so keep the consensus log on a fast disk separate from the data disk, and use enough replicas that the slowest disk does not determine latency.

Deploying distributed consensus-based systems

Number of replicas: an odd number, usually three or five; five tolerates two failures, which covers one maintenance plus one unplanned loss. Location: spread across failure domains (racks, power, datacenters) so that a single event cannot take a majority; but keep latency in mind, since a majority across continents means every write is intercontinental. Capacity: provision for the load after a failure, because losing a replica raises the per-replica load. The chapter also discusses adding and removing members, which is itself a consensus operation and should be done one at a time.

Monitoring distributed consensus systems

Watch the number of members and the state of each (leader, follower, unreachable), the number of proposals and the number agreed, leader elections and their frequency, the time since the last successful round, the latency distribution of consensus rounds, and the log lag of each replica. A system with no leader for more than a few seconds, or with frequent leader changes, is in trouble even if it is technically up. Alert on a replica falling persistently behind, since it reduces the effective quorum size.

Conclusion

Use a proven consensus system for the critical state. Build the application as a replicated state machine on top of it. Place replicas deliberately. Monitor the consensus layer itself, because when it fails, everything above it fails with it.