Consensus and leader election
How do several machines agree on one leader, even when some of them fail?
How do machines agree on a leader when they cannot tell a crash from a silence?
Many systems need exactly one machine to be in charge of something at any moment. A replicated database needs one primary that accepts writes, or two clients can each be told that their conflicting updates succeeded. A job scheduler needs one instance handing out work, or a job runs twice. A lock service needs a single answer to the question of who holds the lock. The machine in charge is called the leader. Choosing it, and agreeing on what it has decided, is the problem of consensus.
The obvious arrangement uses two machines. The second listens for a regular heartbeat from the first and takes over when the heartbeat stops. The difficulty is in what a missing heartbeat means. The first machine may have crashed, or the network between the two may have failed while both machines kept working. Seen from the waiting machine, the two cases are identical, because in both of them no message arrives. If the second machine never takes over, a real crash leaves the system with no leader. If it does take over, a network fault leaves the system with two leaders, each sure that it is alone. This is called split brain, and two leaders that both accept writes will produce two histories that cannot both be kept.
Real systems meet this problem. On 21 October 2018, maintenance work cut the link between GitHub’s East Coast network hub and its main East Coast data center for 43 seconds. GitHub’s failover tooling promoted database primaries on the West Coast. The East Coast held a few seconds of writes that had never reached the West, and the West then accepted about forty minutes of new writes that the East did not have. Neither copy could be thrown away, and GitHub ran with degraded service for 24 hours and 11 minutes while engineers reconciled the two (GitHub’s post-incident analysis). The tooling did what its rules said. The rules had no way to tell a short partition from the loss of a data center.
A network can also fail in a way that gives two true answers to the question “is the leader alive?”. On 2 November 2020 a partly failed switch in one of Cloudflare’s racks left an etcd node that could reach one peer but not the leader. That node kept starting elections while its peer kept voting for the old leader, so no stable leader emerged and etcd stopped accepting writes. The damage then spread: a database cluster manager that depended on etcd promoted a database replica, which took hours to rebuild, and Cloudflare’s API and dashboard were impaired for 6 hours and 33 minutes in all (Cloudflare’s account).
The question has a precise form and a long literature. Fischer, Lynch and Paterson proved in 1985 that in an asynchronous network, where a message can be delayed for any length of time, no deterministic protocol can guarantee that machines will always reach agreement if even one of them may crash (the FLP paper). Every practical protocol therefore makes the same bargain. It promises never to decide two conflicting things, and it promises to make progress only while the network behaves reasonably well. Leslie Lamport’s Paxos, written in 1989 and published in 1998, was the first widely used protocol to strike that bargain (The Part-Time Parliament). Raft, published by Diego Ongaro and John Ousterhout in 2014, strikes the same bargain with rules designed to be easier to understand and implement, and it is the protocol studied here in detail (the Raft paper).
Both rest on one idea: a decision counts only when a majority of the machines accept it. Any two majorities of the same group share at least one member, so two conflicting decisions can never both gather a majority. With five machines, three must agree, and a network cut can leave at most one side holding three. The idea is older than computing. A committee that may act only when a quorum is present relies on the same arithmetic for the same reason. In software you will find it in etcd, which stores the state of every Kubernetes cluster; in ZooKeeper, which coordinated Kafka and Hadoop clusters for more than a decade; in Google’s Chubby lock service (the Chubby paper); in Kafka’s own Raft-based controller; and in the replication layer of databases such as Spanner and CockroachDB.
Pause and predict Before reading how Raft works, design the rule yourself. You have three machines in three zones, and one of them must act as leader. Write down the condition a machine must meet before it may act as leader, and what it should do when it stops hearing from the others. Test your rule against two cases: the leader crashes, and a network fault separates the leader from the other two machines. What does your rule cost in time when a leader really does crash?
Two machines cannot decide who is alive
Running two copies with a heartbeat between them is called active-passive failover. It is common, and it works perfectly when the only failure is a crash. Its flaw is the failure it cannot see: a network cut between two machines that are both healthy.
- Split brain
- Two parts of a system each believe they are the one in charge, and both act. Their decisions conflict.
- For example: Two job schedulers each believe they lead, and both hand job 4,217 to a worker, so it runs twice.
Pause and predict With two machines and one heartbeat between them, which takeover rule prevents split brain and also never leaves you with no leader?
A mental model
A housing society’s committee has the same problem, and solves it with a rule book.
Raft in four rules
Consensus means several machines agreeing on a value, or on a sequence of values, even when some fail. Raft (Ongaro and Ousterhout, 2014) is the algorithm most systems now use for it, designed to be easier to understand than Paxos. It agrees on a log of commands; anything built on that log (a scheduler, a configuration store, a lock) inherits the agreement.
- Terms. Time is divided into numbered terms. Each term has at most one leader. Every message carries the sender’s term; a node that sees a higher term than its own updates to it and becomes a follower at once, even if it was the leader.
- Elections. A follower that hears nothing from a leader for its election timeout becomes a candidate: it increases the term, votes for itself and asks the others. Each node votes at most once per term, and only for a candidate whose log is at least as up to date as its own (the log whose last entry has the later term is more up to date; if the last terms are equal, the longer log is). A candidate with votes from a majority becomes leader. Timeouts are random (the paper suggests 150 to 300 ms), so usually one node times out first and wins before anyone else starts.
- Log replication. Clients send commands to the leader. The leader appends each to its log and sends it to the followers, along with the position and term of the entry before it. A follower accepts only if its own log matches at that point; if not, the leader backs up and resends earlier entries until the logs agree. This is log replication, and empty messages of the same kind serve as heartbeats.
- Commit. An entry is committed once the leader has stored it on a majority, and the leader advances its commit index. Only then is it applied and acknowledged to the client. A leader commits by counting copies only for entries from its own term; entries from earlier terms become committed along with them. That is why a new leader first writes an empty entry in its own term.
Why a majority is enough
Pause and predict In a five-node cluster, can two candidates both win the same term?
Sizes, timeouts and the cost of agreeing
| Nodes | Majority | Failures survived | Comment |
|---|---|---|---|
| 3 | 2 | 1 | The usual minimum, one node per zone |
| 4 | 3 | 1 | One more machine, no more failures survived |
| 5 | 3 | 2 | Survives a crash during planned maintenance |
| 7 | 4 | 3 | Rare: every write waits for three followers |
A cluster of n nodes survives ⌊(n − 1) / 2⌋ failures. An even-sized cluster survives no more failures than the odd size below it: four nodes need three for a majority, so they survive one failure, the same as three nodes.
Failover time. When a leader crashes, nothing can be committed until a follower’s timer runs out and an election finishes: roughly one election timeout plus one round of votes. The Raft paper asks for broadcast time ≪ election timeout ≪ time between failures, and suggests 150 to 300 ms. etcd defaults to a 100 ms heartbeat and a 1,000 ms election timeout, and its tuning guide asks for an election timeout of at least ten times the round trip between members.
Commit latency. A write commits when the leader and enough followers to make a majority have it on disk. In a five-node cluster the leader needs two followers, so the write waits for the second-fastest follower. With followers at round trips of 1, 1, 2 and 2 ms in three zones of one region, plus a 1 ms disk flush, a commit costs about 1 + 1 = 2 ms. Put two followers in another region at 30 ms and it still costs about 2 ms, because the fast pair forms the majority; put three far away and every write costs at least 30 ms.
Where should leadership live?
Suppose one component, a job scheduler run as two copies in two zones, needs a leader backed by a majority, and every assignment it makes is written to one PostgreSQL database. There are two ways to get that leader.
The lease row still relies on agreement, from a place that already has it: the database primary, where every write is already serialised, and whose own failover the cloud provider runs. The lease alone would not make it safe. A lease expires at a time on a clock, and a process that pauses (for garbage collection, say) can wake up after its lease has expired and still believe it holds it. The fencing token is what makes it safe: the protected table itself refuses writes from an older holder.
The etcd cluster is the right choice when many services need coordination, or when the thing being protected is not one database. Both are reasonable. For one component that writes to one database, the option with fewer systems to run is usually the better fit.
The rejected path wins as soon as the numbers change. In Kubernetes, the scheduler, the controller manager and many operators each need exactly one active copy, and each elects its leader through a Lease object stored in etcd, because one shared consensus service is far less to build and keep correct than a separate fenced table for every component. And if a 10-second pause in assigning work costs more than running three small machines (a payment switch that must keep approving transactions, say), the 1 to 2 second failover of a consensus cluster is worth what it costs to operate.
In SQL the check is one transaction: lock the lease row with SELECT token FROM scheduler_lease FOR SHARE, confirm it still equals the token this scheduler was given, then write the assignment. A takeover must update that same row, so it waits for, and is ordered with, every write in progress.
What to remember
- A timeout cannot tell a crashed node from an unreachable one. Failover on silence alone causes split brain.
- With an odd number of nodes, act only with a majority: any two majorities overlap, so a cut leaves at most one side able to decide.
- Raft: numbered terms, randomized election timeouts, one vote per node per term for an up-to-date candidate, and a log entry committed once a majority holds it.
- A deposed leader may still believe it leads. Make the store refuse its writes with a fencing token (the term or a lease counter).
- Consensus costs a round trip to a majority per write. Use it for small, critical facts, often through a service such as etcd or ZooKeeper, rather than for bulk data.
A missing heartbeat does not prove a machine is dead, so act only with a majority and make the store check a fencing token.
In the real world
The simulator runs the core of Raft: elections, the up-to-date check, replication with the consistency check, and the commit rule. Real implementations add what a toy can skip: every vote and entry written to disk before replying, snapshots so logs do not grow for ever, safe changes of cluster membership, a pre-vote round so a node returning from a partition does not disrupt a healthy leader, and reads that confirm leadership with a majority before answering.
Raft appears again in two places. The key-value store design chooses not to use it for every write, and pays for that with conflicting versions. Kafka’s brokers elect their controller with a Raft-based protocol, KRaft, which Kafka internals describes.