Raft 01: Leader Election

The System Design episode on who is allowed to write and what the picking cannot protect. This lesson builds the picking. Part of the Raft series, Build Your Own Raft.

Before you start. This series builds a small copy of Raft, the algorithm a group of machines uses to keep one shared list of commands. This first stage builds only the part that decides which machine is in charge. You need Build Your Own Raft for the map and for what the simulated world looks like (five nodes, a queue for a network, a clock that moves one tick at a time). The idea of one machine holding the pen comes from Who holds the pen (consensus & Raft).

The idea in 30 seconds

Raft divides time into numbered terms, and each term has at most one leader.
A follower that hears no heartbeat for a whole timeout adds one to its term, votes for itself and asks for votes.
A node votes at most once per term, and a candidate needs a majority of the whole cluster, so two leaders in one term cannot both win.
A node that sees a higher term adopts it and becomes a follower, which is how a stale leader steps down.
Timeouts are randomized. If every node used the same timeout they would all become candidates together and split the vote forever.
A majority can elect a new leader while the old leader is only unreachable, not dead. Whatever the old leader did before it was cut off is a separate problem, and the election cannot fix it.

Read the story · Skip to the numbers