Raft leader election

Raft splits consensus into three jobs: electing a leader, replicating a log, and staying safe. This page covers the first. Every node is a follower, a candidate or the leader. The leader is the only node that accepts client commands, and an election picks it.

The big idea

Think of a classroom with a teacher. If nobody hears the teacher for a while, a student calls for a vote on who leads next. Students vote for whoever seems most qualified, and only one leader is chosen.

The analogy breaks at one point. Raft voters do not judge by seniority. They check each candidate's log, and refuse anyone whose log is behind theirs.

Walking through it

Here is a 3-node cluster. The timeouts are illustrative, close to the etcd default of 1,000 ms.

t=0        S1 is leader in term 2, sends its last heartbeat, then crashes
t=1,000    S2's timeout fires first (1,000 ms after the last heartbeat)
           S2 becomes candidate for term 3, votes for itself, asks S3
t=1,010    S3 has not voted in term 3, so it grants the vote
           S2 has 2 of 3 votes, so it is leader for term 3

A node grants its vote only in two cases. It has not voted yet in this term. And the candidate's log is at least as up to date as its own. The check compares the last log term first, then the last log index.

Say S4 asks for a vote with last log term 2 and index 3. S3 has term 2 and index 4. S3 refuses, because S4's log is shorter.

Timeouts are randomized, usually 150 to 300 ms in the paper. That keeps followers from timing out together. If two candidates still split the vote, both wait a new random time and try again.

Common mistakes

• Using the same timeout on every node. Followers then start votes together and split the vote forever. Randomize the timeout.
• Setting the timeout close to the heartbeat interval. The timeout must be much larger than both the heartbeat and the typical round trip.
• Assuming an old leader knows it was replaced. A paused leader may wake up still thinking it leads. It learns the truth when it sees a higher term, then steps down.

Check yourself

1. Why can't S4 win the election in the example above? Its log is behind S3's, so voters refuse. Without the votes of a majority, it cannot become leader.
2. A leader pauses for 5 seconds, then wakes. What happens? It sends a message with an old term. Other nodes reply with a higher term, so the leader steps down to follower.

Key takeaways

• Raft elects one leader per term. Followers start a vote when heartbeats stop.
• Random election timeouts make split votes rare.
• Voters refuse candidates whose logs are behind theirs. That protects committed data.
• Higher terms win. A stale leader steps down as soon as it sees one.

Further learning

Next, see how the elected leader copies commands to followers in Raft log replication.

Diego Ongaro, one of the Raft authors, explains election and replication with animations.