Part 4 of 6 · 3 min read
Raft leader election
Terms, votes, a majority and random timeouts.
Think of a class choosing a monitor. When the monitor goes silent, the first student who notices stands up and says "vote for me, round 2." Each student can give one vote per round. Whoever gets more than half the class wins that round. If two stand up together and the votes split, they wait different random times and try again.
The book teaches Raft, an algorithm designed to be simple to understand. Each process is in one of three states:
- Follower: recognises another process as the leader.
- Candidate: proposes itself in a new election.
- Leader: the one in charge.
Time is divided into terms of any length. A term is a logical clock, a counter that only increases. A term starts with an election. For any term there is at most one leader.
How it runs:
- All processes start as followers.
- A follower expects regular heartbeats from the leader. Each contains the current term.
- If none arrives within a timeout, the follower presumes the leader dead, adds one to its term, becomes a candidate, votes for itself and asks all others to vote for it, stamping the request with the term.
- Each process votes for at most one candidate in a term, first come first served.
- A candidate stays a candidate until one of three things happens.
The three outcomes:
- It wins: more than half of all processes vote for it. It becomes leader and starts sending heartbeats.
- Another wins: it receives a heartbeat from a leader whose term is greater than or equal to its own, and returns to being a follower. This can happen, for example, if the candidate had a long garbage collection pause and woke to find the election over.
- No one wins (a split vote): several followers became candidates together and none got a majority. After a timeout the candidate starts a new election. The timeout is picked at random from a fixed interval to make another split vote unlikely.
Term
A term in Raft is a numbered period that starts with an election. Terms only increase, and each has at most one leader.
Example: the cluster is in term 7 with node 2 as leader. Node 2 stops. Node 4 times out first and starts term 8.
The majority rule is the key to safety: one vote per process per term means two candidates cannot both get more than half.
A worked example with five nodes (A to E), made up to show the idea. A is the leader in term 4 and then crashes.
| Time | Event |
|---|---|
| 0 | A stops sending heartbeats |
| 1.4 s | C's election timeout (random between 1.0 and 2.0 s) fires first. C moves to term 5 and votes for itself |
| 1.4 s | C asks B, D and E for votes in term 5 |
| 1.5 s | B and D vote for C. E has not voted yet in term 5, so E also votes for C |
| 1.5 s | C has 4 votes (itself, B, D, E), more than half of 5. C is leader of term 5 and sends heartbeats |
| 1.6 s | If A returns, it sees a heartbeat for term 5, higher than its term 4, and becomes a follower |
Why 5 nodes: a majority is 3, so the cluster survives 2 failed nodes. With 3 nodes it survives 1. This matches the quorum rule of module 4.
A split vote case. B and D both time out at nearly the same moment and each votes for itself in term 6. A has crashed. C votes for B, E votes for D. B has 2 votes (itself, C), D has 2 votes (itself, E). Neither has 3. After a random wait, say B waits 1.3 s and D waits 1.8 s, B starts term 7 first and wins. The random timeout is what ends the tie.
Check yourself:
- Why can two candidates not both win the same term?
- What does a candidate do if it sees a heartbeat with a higher term?