Consensus & leader election

Three servers each keep a copy of a bank account's ledger, so that losing one server loses nothing. Two requests arrive at almost the same moment: deposit $100 and withdraw $120, on an account holding $50. Applied in one order, the withdrawal succeeds. In the other, it bounces. Every copy must apply them in the same order, or the copies disagree about your money.

Consensus is getting several machines to agree on one value, even though some of them may crash and messages may be delayed or lost. Agreeing once is useful; agreeing again and again on "what comes next" gives you a shared, ordered log of changes, which every copy applies in the same order. That covers most of what systems need consensus for:

• One leader: exactly one machine in charge at a time.
• One order of changes: the replicated ledger above.
• Locks and settings: who holds a lock, which database is primary, what the current configuration is.

Two kinds of promise are at stake:

• Safety: nothing bad ever happens. The machines never decide two different things.
• Liveness: something good eventually happens. They do reach a decision.

It has been proved that when messages can be delayed without limit, no deterministic protocol can guarantee both, if even one machine might crash. A machine that has gone quiet might be dead or just slow, and waiting for it forever means never deciding, while giving up on it risks deciding without its vote.

A consensus protocol may stall, but it never decides two different things. Real protocols keep safety absolutely and treat liveness as "almost always". They use timeouts and randomness to move on when the network behaves reasonably, which is nearly all the time. During a bad partition, they pause rather than guess.

The trick at the heart of every consensus protocol: a decision needs the agreement of a majority of the machines. Of five machines, any two groups of three must overlap in at least one machine, because 3 + 3 is more than 5. That machine will not agree to two conflicting things, so two conflicting decisions can never both win.

In general, 2f + 1 machines survive f failures. Look at the even rows: four machines survive no more failures than three, and two survive none, yet they cost more and every decision waits for more of them. That is why clusters have odd sizes, usually three or five.

Most protocols pick one leader to make proposals, because one machine choosing the order is far simpler than everyone negotiating every entry. The leader sends regular heartbeats. When a follower hears none for a while, it tries to take over:

Four rules make this safe:

• Terms. Every election starts a new, higher term number.
• One vote per term. Each machine votes at most once in a term, so at most one candidate can collect a majority.
• Random timeouts. Each machine waits a slightly different random time, often a few hundred milliseconds, before standing. So usually one stands alone and wins; if two tie, both wait another random time and try again.
• Only an up-to-date candidate wins. A machine refuses to vote for a candidate whose log is behind its own, so a new leader always has every decision already made.

And the old leader? If it was only cut off, it still thinks it leads. But it can no longer reach a majority, so nothing it proposes is ever accepted, and the moment it hears a higher term it steps down. The term number does the same job as a fencing token (see Failure detection & split brain).

With a leader in place, every change goes through it and into the shared log:

Now crash the leader at the worst moment:

• After a majority stored the entry: it survives. Any new leader needs votes from a majority, which overlaps the majority holding entry 7, and the voting rule means only a machine that has entry 7 can win.
• Before a majority stored it: it may be lost. That is safe, because the client was never told "done". It retries.

This is the essence of the best-known protocols. Paxos is the older and more famous; Raft was designed later to be easier to understand and to build, and at heart it works as described here.

Consensus is not free. Every change waits for a majority to answer: about a millisecond or two when the machines are in nearby buildings, tens of milliseconds when they are in different regions. So systems use it for small, critical things, such as who is leader, which database is primary, who holds a lock, the current configuration, and let the bulk of the data flow by cheaper means.

You will almost never implement it. Small open-source coordination services built on these protocols exist for exactly this job, and many databases run consensus internally for their own replication. Use those. The protocols fit on a page, but real implementations must also handle disks that lie about what they saved, machines joining and leaving, and snapshots of logs that grow forever. Independent testing has repeatedly found subtle bugs even in mature, widely used implementations.

One limit to remember: these protocols assume machines crash; they do not assume machines lie. Tolerating liars is a different, costlier problem that needs at least 3f + 1 machines to survive f of them (see Why distributed systems are hard).