Consensus

The problem

Some things must have exactly one answer across a cluster. Which node is the primary. Whether this lock is held. What the next entry in the replicated log — the ordered list of changes every copy applies — is. If two nodes each believe they are the primary, they both accept writes, and the data diverges — split brain, the failure every distributed database is built to prevent.

The difficulty is not agreeing when everything works. It is agreeing when a node has crashed, or is merely slow, and nobody can tell which; when a message is delayed long enough to arrive after the decision it was about; when the network splits and each side can only see itself. Consensus protocols — Paxos, Raft, Zab — are the algorithms that produce one answer under those conditions.

Majorities

The core idea is smaller than its reputation. A decision counts only when a majority of nodes has accepted it. Five nodes, three must agree. Any two majorities of the same set overlap in at least one node, so two conflicting decisions cannot both be majorities — the overlapping node would have had to accept both, and it does not.

That one property does the work. If the network splits five nodes into three and two, the three can keep deciding and the two cannot; there is no configuration in which both halves proceed. The widget lets you partition a cluster and kill nodes and shows which side, if any, can still make progress.

Odd sizes. Three nodes tolerate one failure, five tolerate two, four tolerate one — the same as three, for more machines and more messages.

Leaders, terms and logs

Raft makes the idea concrete. One node is leader for a term; followers accept its writes. Every write is appended to the leader's log and sent to all followers; once a majority has written it, it is committed and the client is answered. If the leader stops sending heartbeats, a follower times out, starts a new term with a higher number, and asks for votes. A majority of votes makes it leader; a node votes at most once per term, so two leaders in the same term are impossible.

A node that was partitioned away may still think it is leader of an old term. When the partition heals it hears the higher term number, steps down, and discards anything it accepted that the majority never saw. Nothing it did in isolation was ever committed, because it could not reach a majority to commit it.

The cost

Every committed write is a round trip from the leader to a majority. Across a region that is a millisecond; across continents it is a hundred. Consensus is therefore used for the things that need it — cluster membership, leader election, configuration, locks — and rarely for the bulk data path, which uses the cheaper replication the CAP and replication concepts describe. etcd, ZooKeeper and Consul exist to be the small, slow, correct core that everything else coordinates through.

Where it goes wrong

• Even clusters. Four nodes split two and two can never elect anyone.
• Losing the majority. Three of five down and the cluster stops — correctly. It cannot know whether the missing three are dead or merely unreachable and deciding on their own.
• Slow disks. A commit waits for a majority to write, so one slow disk in a three-node cluster is on the critical path half the time.
• Reading from a follower. It may be behind. Reads that must be fresh (linearisable) go through the leader, or through a lease that proves it is still the leader.

Take this with you

• The one idea: a decision counts only when a majority accepts it, and two majorities always overlap — so there can never be two answers.
• In an interview, explain majorities, odd cluster sizes, and why consensus is used for small things (leader, locks, config) rather than bulk data.
• At work, keep the consensus cluster small, odd, and on fast disks — and never run one across a slow link without knowing what a commit costs.