Raft leader election

The problem it solves

A group of machines needs to agree on one thing: who is in charge. Almost every strongly consistent system reduces to that, because once a single leader exists, ordering is easy — the leader decides — and the hard part becomes electing a new one when the old one dies, without ever having two at once.

Two leaders is the failure that must not happen. Two leaders means two orderings of the same data, accepted by different clients, both believing themselves authoritative. Everything downstream is corrupt and no automatic reconciliation can fix it, because both orderings were legitimately acknowledged.

Raft was designed as a consensus algorithm that could be understood, taught and implemented correctly, and its leader election is the part most worth understanding in detail.

The mechanism

Every node is a follower, a candidate or a leader, and time is divided into numbered terms.

A follower expects heartbeats from a leader. If none arrives within its election timeout, it increments the term, becomes a candidate, votes for itself, and asks everyone else for a vote. A node grants its vote if — and only if — it has not already voted in that term and the candidate’s log is at least as up to date as its own. A candidate that collects votes from a majority becomes leader and starts sending heartbeats, which suppress further elections.

Two rules together make two leaders impossible:

1. One vote per node per term.
2. A majority is required to win.

Any two majorities of the same set must share at least one member, and that member voted only once in the term. So at most one candidate can reach a majority in any term. This is a proof, not a heuristic, and it is the sentence to be able to produce on demand.

Termination is a separate problem from safety. If every follower’s timeout were identical, they would all become candidates at the same instant, split the vote, all fail to reach a majority, and repeat — forever. Raft’s answer is randomised election timeouts: each node picks its timeout uniformly from a range, so one node reliably goes first, and the rest of the cluster receives its request before their own timers fire.

What the simulation shows

The state machine shows each node’s belief about itself, and the message panel shows vote requests and heartbeats crossing between them.

Let it run and a leader emerges within roughly one election timeout. Then the leader is killed: a gap, an election, a new leader. Read the write-availability panel — the cluster is unavailable for writes for exactly one election timeout, and no longer. That number is your failover time, and it is a design parameter rather than a mystery.

Now the demonstration that matters: turn randomised timeouts off. Every follower campaigns at the same instant. Every candidate votes for itself. Nobody reaches a majority. The term increments and it happens again, and again — hundreds of elections, zero leaders, indefinitely. Safety is preserved throughout (there is never more than one leader, because there is never one leader) and the system is completely useless. Randomisation is what makes the algorithm terminate, and it is the part most descriptions skip.

Then drop a third of all messages. Correctness is untouched — still never two leaders — and elections take longer and occasionally waste a term. That is exactly the right behaviour under a lossy network, and the distinction between slower and wrong is the one to draw.

The numbers worth carrying

The standard guidance is broadcastTime ≪ electionTimeout ≪ MTBF. Broadcast time is one round trip: sub-millisecond within a rack, a few milliseconds within a datacentre, tens of milliseconds cross-region. Election timeouts are typically 150–300 ms for a single-datacentre cluster — etcd defaults to 1000 ms with a 100 ms heartbeat, deliberately conservative — and must be an order of magnitude larger than broadcast time, or spurious elections will happen constantly.

Your unavailability window during a leader failure is one election timeout plus the time to detect it, which is itself up to one heartbeat interval. Halving the timeout halves the outage and increases the rate of unnecessary elections; that is the tuning trade, and stating it is the answer to “how would you make failover faster”.

Quorum size is floor(n/2) + 1: three nodes tolerate one failure, five tolerate two, seven tolerate three. Larger clusters tolerate more failures and make every commit slower, since a majority must acknowledge. Five is the usual sweet spot.

Where it breaks down

Election is not the whole algorithm. Raft also covers log replication, commitment rules, and the restriction that only a candidate with an up-to-date log may win — which is what prevents a lagging node from being elected and silently discarding committed entries. Election is the interesting half to visualise and the smaller half to implement.

Even-sized clusters waste a node: four tolerates the same single failure as three, and an even split leaves nobody with a majority. See split brain.

Membership changes are the dangerous part. Naively changing the node set can produce two disjoint majorities under two different configurations — genuine split brain, in a protocol designed to prevent it. Raft specifies joint consensus or single-node-at-a-time changes for this reason, and it is where real implementations have shipped real bugs.

A partitioned old leader keeps believing it is leader until it fails to reach a majority. Reads served from it are stale, which is why leader-lease reads or read-index quorum checks are needed for linearizable reads — a subtlety many implementations got wrong before it was widely understood.

What people get wrong

“Randomised timeouts are an optimisation.” Without them the algorithm does not terminate. The simulation makes this unarguable in one click.

“A majority prevents two leaders because of the timeouts.” No — because two majorities intersect, and the shared member votes once per term. Timeouts are about liveness, quorum intersection is about safety, and confusing the two is the most common tell.

“Raft is faster than Paxos.” They have the same message complexity. Raft’s contribution is understandability and a specified, complete algorithm — including membership changes and log compaction, which Paxos papers leave as exercises.

“We will use Raft for our data path.” Every write costs a majority round trip. That is correct for configuration, locks and metadata, and often far too slow for the main data path. Know what you are buying.

In production

etcd (and therefore Kubernetes), Consul, CockroachDB, TiKV and MongoDB’s replica-set election protocol are all Raft or Raft-derived. ZooKeeper’s ZAB predates it and solves the same problem. In all of them, the operational failure to watch for is election churn: if the election timeout is comparable to your network’s tail latency, the cluster elects, loses, and re-elects, and the write availability panel above becomes your production dashboard.

The advice that follows: put Raft clusters where round-trip time is low and stable — same region, ideally same datacentre with racks for fault isolation — and if you need geographic distribution, understand that every write pays a cross-region round trip.

The follow-up questions

“Why can there never be two leaders?” — One vote per term plus majority, and two majorities intersect. Say it in one sentence.

“What happens without randomised timeouts?” — Split votes forever. The strongest available demonstration that liveness and safety are different properties.

“How long are you unavailable when the leader dies?” — One election timeout plus detection. Give the number and the tuning trade.

“Three nodes or five?” — Failure tolerance versus commit latency, and never an even number.