Raft keeps five servers agreeing on one list of commands, and it does that while messages get lost, servers crash and the network splits. Chapter 27 explains its rules one at a time. It's harder to see from prose how they fit together when everything goes wrong at once, because on a real cluster the messages fly in parallel and you never get to choose which one arrives first.
Here you do choose. The five servers, S1 to S5, are drawn in a ring. Each one is a follower (it does what the leader says), a candidate (it's asking for votes), or the leader (it takes client writes and copies them out). Each carries a term, a number that goes up by one every time someone starts an election, and remembers who it voted for in that term. Below the ring is each server's log, the numbered list of commands, one cell per index. A cell's colour is the term it was written in, and its border turns solid once that server knows the entry is committed, meaning stored on a majority and safe to apply. Every message on the wire is listed on the right and drawn as an arrow. There are only four kinds: RequestVote and its reply, and AppendEntries (which carries log entries, or nothing at all as a heartbeat) and its reply.
Nothing moves until you say so. Next step runs the scenario's next event or delivers the oldest message, and the line at the bottom names the rule that applied. You can also deliver any message out of order, drop it, or pick a server and fire its election timer, crash it, or move it across a partition.
| log | 1 | 2 | 3 | 4 | commit |
|---|---|---|---|---|---|
| S1 | · | · | · | · | 0 |
| S2 | · | · | · | · | 0 |
| S3 | · | · | · | · | 0 |
| S4 | · | · | · | · | 0 |
| S5 | · | · | · | · | 0 |
Things to try
1. One election, one write
Start with Election. All five servers are followers at term 0 with empty logs. Press Next step once: S1's election timeout, the countdown a follower runs while it hears nothing from a leader, runs out. S1 moves to term 1, votes for itself and sends four RequestVotes. Keep stepping. Each follower sees a higher term than its own, adopts it, and grants its vote, because it hasn't voted in term 1 and S1's log is no worse than its own (both are empty).
S1 has its own vote. Four vote replies are on their way back. After how many of them does S1 become leader?
Keep going until the scenario writes x=1. S1 appends it at index 1, tagged with term 1, and sends it out. Watch the dashed border on S1's cell and the matchIndex line under the table, which is the leader's record of how far each follower's log is known to match its own. The entry is committed on the reply that brings it to three copies, not on the fourth. Then a heartbeat carries S1's commit index to the followers, and their borders turn solid too.
2. Drop the messages that don't matter
Press Reset and step until S1 has written x=1 and four AppendEntries are in flight. Drop two of them.
Two of the four followers never get the entry. Does x=1 still commit?
3. A split vote
Choose Split vote. S3, the old leader, is down, so four servers remain, and the timers of S1 and S4 run out almost together. Both become candidates in term 2. The script delivers S1's request to S2 first and S4's request to S5 first, then lets the rest arrive.
S1 and S4 each have their own vote plus one more. Who wins term 2?
Try the scenario again and make the tie yourself: fire S1's timeout, then S4's, then deliver messages in any order you like. As long as each candidate gets one of the two voters, the term is lost.
4. The leader dies with a committed entry not everyone has
Choose Leader crash. S1 leads term 1 and has committed x=2 at index 2, which is on S1, S2 and S3. S4 and S5 never received it. The script crashes S1 and lets S5's timer run out first.
S5's log ends at index 1. Can it become leader of term 2?
S3 wins term 3 and starts sending AppendEntries. S4 and S5 fail the consistency check: every AppendEntries names the index and term of the entry just before the new ones, and a follower that doesn't have that entry refuses. S3 backs up its nextIndex for them and resends from index 2, and they accept. Now x=2 is on four of five servers. Read the narration on that reply before you go on.
Entry 2 is on four servers. Does S3 commit it now?
5. The stale leader, and a rule switched off
Choose Stale leader. S1 leads term 2, and the network splits S1 and S2 from the other three. A client writes x=9 to S1, which copies it to S2 and stops there: two of five, never committed. On the other side, S3 wins term 3 with the votes of S4 and S5 and commits x=7 at the same index 3. For a while two servers both believe they lead, in different terms.
The network heals. What happens to x=9?
Now break something. Tick Break it: voters skip the up-to-date check, which reloads the current scenario with that rule off. Switch to Leader crash, press Next step twice (S1 crashes, S5 times out), then Deliver all in flight. Without the restriction S2 and S3 vote for S5, and it leads term 2 with a log that ends at index 1. Select S5, press Client write, and deliver everything. S5's new entry goes in at index 2, the followers' x=2 conflicts with it and is deleted, and the safety line at the bottom turns red: an entry that was committed is gone.
The button beside the checkbox runs 200 random runs of 300 events each, from fixed seeds, so it gives the same answer every time. The events are chosen at random from everything you can do by hand, plus delivering messages out of order and twice. With every rule in place, none of the 200 runs elects two leaders in one term or loses a committed entry. With the restriction off, about one run in five loses a committed entry.
What this shows
Most of Raft is about which messages a server may ignore. A message with an older term gets refused. A vote request from a server with a worse log gets refused. A second vote request in the same term gets refused, and so does an AppendEntries that doesn't line up with the follower's log. Each refusal is a rule you can name, and together they explain why you could drop and reorder anything you liked in this lab, and the random runs could duplicate messages too, without breaking anything: one leader per term follows from one vote per term and overlapping majorities, and committed entries survive because only a server that holds them can win the next election.
The cost shows up as waiting. A cut-off leader keeps accepting writes it can never commit, a split vote burns a whole term, and an old entry sits uncommitted on four servers until the new leader writes something of its own.
The lab leaves out real clocks (you fire every timeout), the empty entry a new leader appends, membership changes, and the pre-vote extension.
Where this comes from
- Chapter 27, Consensus: Raft, Paxos & Leases, section 5, "Electing a leader": terms, the three roles, one election message by message, and section 5.3, "Only an up-to-date server can win", for the election restriction.
- Chapter 27, section 6, "Copying the log": the consistency check and the Log Matching Property in 6.2, and how the leader computes the commit index from match indexes in 6.3.
- Chapter 27, section 7, "Committing entries from earlier terms": the paper's Figure 8 step by step, and why a new leader appends an empty entry.
- Chapter 27, section 9, "Keeping elections quiet", for what a cut-off server does to a healthy cluster when it rejoins, and how pre-vote and CheckQuorum help.
- Diego Ongaro and John Ousterhout, "In Search of an Understandable Consensus Algorithm", USENIX ATC 2014. Figure 2 there lists every rule this lab implements.