Lesson 28 · Consensus · Module 3

Raft: Leader Election

Lesson 27 left you with a protocol that is provably safe and quietly maddening: two proposers can out-bid each other forever, and nobody decides anything. Raft's answer is not a cleverer tie-break. It is a coin toss, and the coin toss is the contribution.

The win in this lesson: you will be able to trace an election from the moment a leader stops sending heartbeats to the moment a new leader serves its first request, and say precisely what randomised timeouts buy that Paxos's proposal numbers did not.

1. Safe is not the same as finished

Paxos is not broken. The Raft paper says so in the same breath as its complaint:

"Paxos ensures both safety and liveness, and it supports changes in cluster membership. Its correctness has been proven, and it is efficient in the normal case."

In Search of an Understandable Consensus Algorithm (Extended Version), Ongaro & Ousterhout, §3

Two things still hurt. The first is the one from lesson 27: two proposers taking turns raising the proposal number, each invalidating the other's prepare phase, neither ever reaching a decision. Safety holds the whole time — nothing wrong is ever chosen — and progress is zero. The second is that the shape of the algorithm resists being built:

"If a series of decisions must be made, it is simpler and faster to first elect a leader, then have the leader coordinate the decisions."

Ongaro & Ousterhout, §3

That sentence is the whole design. Paxos treats leadership as an optional performance trick bolted on to a peer-to-peer core. Raft makes electing a leader the first phase of consensus itself, and then spends all its ingenuity on making that one election terminate quickly. This lesson is only the election. The log comes next.

2. Terms: a logical clock, not a clock

Before any of the mechanism, one idea. Raft chops time into numbered terms, and every message carries the sender's term number.

"Raft divides time into terms of arbitrary length […] Terms are numbered with consecutive integers. Each term begins with an election […] Raft ensures that there is at most one leader in a given term."

Ongaro & Ousterhout, §5.1

A term is not a duration. It is a counter that only goes up, and its job is to let a server work out whether what it just heard is current or stale:

"Terms act as a logical clock [14] in Raft, and they allow servers to detect obsolete information such as stale leaders. Each server stores a current term number, which increases monotonically over time. Current terms are exchanged whenever servers communicate; if one server’s current term is smaller than the other’s, then it updates its current term to the larger value."

Ongaro & Ousterhout, §5.1

Two consequences, and both are in the condensed spec as single lines. Every server, in every state, obeys this rule: "If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower (§5.1)". And in the other direction: "If a server receives a request with a stale term number, it rejects the request."

3. Three states, and the two rules that connect them

"Followers are passive: they issue no requests on their own but simply respond to requests from leaders and candidates. The leader handles all client requests (if a client contacts a follower, the follower redirects it to the leader). […] The third state, candidate, is used to elect a new leader as described in Section 5.2."

Ongaro & Ousterhout, §5.1

Only two pieces of state matter for an election, and the paper's Figure 2 insists both are on stable storage before any RPC is answered: "currentTerm latest term server has seen (initialized to 0 on first boot, increases monotonically)" and "votedFor candidateId that received vote in current term (or null if none)". That second field is doing more work than its size suggests; §5 below turns it into a safety proof.

The rule that starts everything

A leader's only job between client requests is to be heard:

"Leaders send periodic heartbeats (AppendEntries RPCs that carry no log entries) to all followers in order to maintain their authority."

Ongaro & Ousterhout, §5.2

And the follower's side, quoted from the condensed spec:

Followers (§5.2):
  • Respond to RPCs from candidates and leaders
  • If election timeout elapses without receiving AppendEntries RPC
    from current leader or granting vote to candidate: convert to candidate

Read the second bullet's tail again: or granting vote to candidate. A follower that has just voted resets its own timer. Voting is not free — it buys the candidate a little quiet in which to finish counting.

4. One election, end to end

Five servers, because that is the paper's default: "A Raft cluster contains several servers; five is a typical number, which allows the system to tolerate two failures." A majority is three. The leader dies.

"To begin an election, a follower increments its current term and transitions to candidate state. It then votes for itself and issues RequestVote RPCs in parallel to each of the other servers in the cluster."

Ongaro & Ousterhout, §5.2

Winning, and the two other ways it can end

"A candidate wins an election if it receives votes from a majority of the servers in the full cluster for the same term. Each server will vote for at most one candidate in a given term, on a first-come-first-served basis […] Once a candidate wins an election, it becomes leader. It then sends heartbeat messages to all of the other servers to establish its authority and prevent new elections."

Ongaro & Ousterhout, §5.2

That pair of sentences is a proof, compressed. At most one vote per server per term, plus a majority is required, means two winners in one term would need two disjoint majorities of the same set — impossible, because any two majorities of five share at least one member, and that member only voted once. Figure 3 states it as a guarantee: "Election Safety: at most one leader can be elected in a given term."

The second ending is that somebody else got there first:

"While waiting for votes, a candidate may receive an AppendEntries RPC from another server claiming to be leader. If the leader’s term (included in its RPC) is at least as large as the candidate’s current term, then the candidate recognizes the leader as legitimate and returns to follower state."

Ongaro & Ousterhout, §5.2

The third ending is the interesting one.

5. Split votes, and what randomness actually buys

"The third possible outcome is that a candidate neither wins nor loses the election: if many followers become candidates at the same time, votes could be split so that no candidate obtains a majority."

Ongaro & Ousterhout, §5.2

Here is lesson 27's livelock in a new costume. Two candidates, each with its own supporters, neither able to reach three. Both time out. Both try again. If they keep timing out together, they keep splitting the vote together, and the cluster has no leader forever while remaining perfectly safe.

"However, without extra measures split votes could repeat indefinitely. Raft uses randomized election timeouts to ensure that split votes are rare and that they are resolved quickly. To prevent split votes in the first place, election timeouts are chosen randomly from a fixed interval (e.g., 150–300ms). This spreads out the servers so that in most cases only a single server will time out; it wins the election and sends heartbeats before any other servers time out."

Ongaro & Ousterhout, §5.2

And the same trick is applied to the retry, not just the first attempt:

"Each candidate restarts its randomized election timeout at the start of an election, and it waits for that timeout to elapse before starting the next election; this reduces the likelihood of another split vote in the new election."

Ongaro & Ousterhout, §5.2

The answer to the question in the standfirst

Paxos's proposal numbers are a total order. They settle who wins any given comparison, and that is precisely the problem: the loser learns it lost and immediately proposes a higher number, so the order that resolves each round also guarantees a next round. Ranking does not stop duelling; it is what the duel is fought with.

Randomised timeouts do not order the candidates at all. They order their wake-ups, independently and afresh each round, so the probability of another collision decays geometrically. The authors reached this the long way round, and said so:

"Elections are an example of how understandability guided our choice between design alternatives. Initially we planned to use a ranking system: each candidate was assigned a unique rank, which was used to select between competing candidates. […] We made adjustments to the algorithm several times, but after each adjustment new corner cases appeared. Eventually we concluded that the randomized retry approach is more obvious and understandable."

Ongaro & Ousterhout, §5.2

They tried Paxos's answer — rank the contenders — inside Raft, and threw it away. That is the whole comparison in one paragraph, written by the people who ran the experiment.

The measured effect is unglamorous and large. With no randomness the paper's test cluster took over ten seconds to elect a leader; "Adding just 5ms of randomness helps significantly, resulting in a median downtime of 287ms", and "with 50ms of randomness the worst-case completion time (over 1000 trials) was 513ms" (§9.3). Five milliseconds of noise is the difference between a livelock and a blip.

6. Residual risk

Randomisation removes a liveness hazard. It does not make elections free, and three prices are worth naming before you meet them in production.

You are unavailable for roughly one election timeout, every time. The shaded window in the first diagram is real writes failing. Raft is explicit about the split:

"One of our requirements for Raft is that safety must not depend on timing […] However, availability (the ability of the system to respond to clients in a timely manner) must inevitably depend on timing. […] Leader election is the aspect of Raft where timing is most critical."

Ongaro & Ousterhout, §5.6

The timeout has to be chosen against your actual network. The requirement is an inequality, quoted here exactly as the paper prints it: broadcastTime ≪ electionTimeout ≪ MTBF. Set the timeout too low and healthy leaders get deposed by a slow link — you have built an outage generator out of a liveness mechanism. Set it too high and every genuine failure costs you that much downtime. Only the middle term is yours to choose; the other two are facts about your hardware.

A majority is a hard floor, not a soft one. Three of five must be reachable and able to persist a vote to stable storage before replying. A minority partition cannot elect anyone and should not pretend otherwise: if your client library retries into that partition expecting eventual success, you have lesson 04's selfish retry aimed at a cluster that is, correctly, refusing to make progress.

7. Check yourself

8. Back to your world

Find something in your own system that elects or claims: a lock in a key-value store, a "only one worker runs this job" flag, a cron box that must be singular. Ask three questions of it. What is its term — what monotonically increasing number does a stale holder carry, so that the rest of the system can reject it? How long is the window between the holder dying and a replacement claiming? And do all the contenders retry on the same interval?

The third question is the cheap win. If several instances wake on a fixed schedule to claim the same lock, they will collide on every cycle, and the fix is not a smarter tie-break — it is a random offset. If the first question has no answer, you do not have leader election; you have a race with good manners.