Raft, Visually

The last lesson ended on a promise: "That's the whole machine, assembled and running, and you can drive it." This is that lesson. You will watch a cluster accept commands, crash, argue, heal, and never once disagree about what happened.

Here's the part nobody tells you upfront: you already own most of this machine. Terms as numbered rounds. One remembered vote per node per term. A majority of the full membership wins. Randomized timers to break symmetry, heartbeats to keep challengers quiet, and a rising number that makes stale kings step down on contact. That was Leader Election, and every piece of it is reused here unchanged.

But an election only answers who speaks. Consensus was never really about who wears the crown — back in The Consensus Problem, the goal was a cluster of crashing machines agreeing on one truth: one answer it will never take back. Where does that truth actually live?

In a list. A plain, numbered, append-only list of commands. Bolt a replicated list onto the election machine you already built, add three careful clauses, and you get the algorithm that quietly runs more infrastructure than any other piece of theory in this course. It's called Raft, and odds are you operate it already: every Kubernetes cluster carries etcd, and etcd is Raft with an API. If you ran the Kafka codelab back in Fundamentals of System Design, the KRaft in the name is this exact machine — that's what "the broker is its own coordinator" meant.

The plan: meet the list, watch the leader copy it, learn which candidates may be crowned, drive the whole thing yourself, and then step carefully around the one trap that catches almost everyone who thinks they've understood it.

Strip any service down far enough and it's a state machine: a lump of state plus commands that change it. A key-value store is state plus set x=5. A bank ledger is balances plus transfers. And state machines have one lovely property: they're deterministic. Feed two copies the same commands in the same order and they compute the same state, forever, without ever comparing notes.

That flips the problem. To agree on state, the cluster only needs to agree on order — one shared list of commands. You've met this move before: on the ordering ladder in Ordering in Practice, the cheapest total order was the single writer. Raft is the single-writer rung rebuilt for Hard Mode: one writer at a time, chosen by election, replaceable when it dies.

So every node keeps a log — think of it as a diary. Each entry holds three things:

• an index: which numbered slot it occupies,
• a command: the actual work, straight from a client,
• a term: the numbered round it was written in.

There's the term again, taking its third job. In the last lesson it stamped ballots and ranked authority. Now it's ink on every diary page, recording which reign wrote the entry. Keep an eye on it; the two hardest rules in Raft both turn on that stamp.

One more word, and it's the most important one in the lesson. An entry is committed when it can never be lost. The paper's definition is exact: "A log entry is committed once the leader that created the entry has replicated it on a majority of the servers" — hold that thought, because a later section will show that sentence hides a trap. Committed is a promise about durability, not execution: applied is the separate, later moment when a node's state machine actually runs the entry. Committed pages are permanent; applied pages have happened. A healthy node is always applying a little behind the commit frontier, and that gap is normal.

What Raft promises, and what this lesson will earn piece by piece, is the paper's State Machine Safety property: "if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index." Same pages, same order, same world.

In Leader Election, the heartbeat was pure suppression: each one said the throne is occupied, reset your timer. Raft keeps that heartbeat and gives it a second job: carrying pages. The message is called an AppendEntries call, and an empty one is just a heartbeat wearing its old uniform.

Here's the healthy path, end to end. A client sends set x=5 to the leader. The leader writes it into its own diary in pencil — appended, stamped with the current term, not yet committed. The next AppendEntries to each follower carries the new page. Followers write it down and acknowledge. The moment a majority of diaries hold the page, the leader marks it committed, applies it, answers the client, and tells the followers where the commit frontier now sits so they can apply it too.

But copying pages blindly would be fragile — a follower that missed a delivery would drift, silently, forever. So every AppendEntries carries a safety latch: alongside the new pages, the leader names the entry that sits just before them — its index and its term. The follower checks its own diary for that exact entry. Present? Accept the new pages. Missing or different? Refuse the whole delivery.

A refusal starts the repair walk: "the leader decrements nextIndex and retries the AppendEntries RPC. Eventually nextIndex will reach a point where the leader and follower logs match. When this happens, AppendEntries will succeed, which removes any conflicting entries in the follower's log and appends entries from the leader's log." The leader backs up page by page until it finds common ground, then overwrites everything after it.

That little latch buys an enormous property, the paper's Log Matching guarantee: "If two entries in different logs have the same index and term, then they store the same command" — and stronger — "then the logs are identical in all preceding entries." Why it holds is a staircase argument: a leader only ever writes one command into a given slot of a given term, and every accepted delivery re-verified the entry behind it, which had verified the entry behind it. Match at the tip, and the whole spine matches beneath.

Notice the asymmetry, because it's the sentence to carry out of this section: followers can lose pencil entries; leaders never erase their own. A follower's conflicting tail is scribbled draft, safely overwritten. The current leader's diary is the reference copy. The leader's log is the law.

And what stops a stale king's deliveries from doing damage? The same number as always. Every AppendEntries carries the sender's term, and any node holding a higher one refuses it flat. In Network Partitions & Split Brain you bolted that check onto the storage gate as a fencing token; Raft builds it into every single message. Authority is a number that only goes up.

Now the machinery from Leader Election develops a crack. Imagine a follower that's been asleep for an hour. Its diary is missing fifty committed pages. Its timer fires, it campaigns, it wins — nothing in the last lesson forbids it. And the moment it's crowned, the leader's log is the law stops being a safety rule and becomes a weapon: repair would march through the cluster erasing committed truth to match an ignorant king.

Raft closes the crack with one new clause on the ballot. A candidate's vote request now carries the fingerprint of its last diary entry: the index and the term. Each voter compares that fingerprint against its own last entry, and grants the vote only if the candidate's diary is at least as complete. The paper's comparison, exactly: "If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date."

Read the order of those two sentences again, because most people's instinct gets it backwards. The longest log does not win. The latest term does. A diary of six pages ending in term 5 beats a diary of forty pages ending in term 4. Those forty pages were written under an old reign, and however many there are, no majority can have committed them past what the term-5 writer knew — later ink outranks more ink. Length only breaks ties within the same term.

Here's why one humble comparison is enough, and the proof is one you already own. A committed page lives on a majority of diaries — that's the definition. A winning candidate collected votes from a majority of voters. Two majorities of the same five nodes must share a member — that's the pigeonhole proof from Quorum Intuition, Revisited, and you cannot put more pigeons into fewer holes. So at least one voter that blessed the winner personally holds every committed page. That voter compared diaries before saying yes. Any candidate missing a committed page reads as less complete to that voter, and the vote is refused.

The consequence carries the weight of the whole design, and the paper names it Leader Completeness: "if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms." Raft never copies committed data to a new leader, never runs a recovery phase, never reconciles diverging histories after the fact. It simply refuses to crown anyone who'd need any of that. The election is the recovery.

Reading about diaries is one thing. Watching a cluster keep one while you attack it is another. Everything below is the real machine: real logs, real ballots, real repair — nothing is scripted.

Drive it like this:

1. Type a command and send it. Watch the page land in the leader's log in pencil, fly out on the next heartbeat, and turn permanent the moment the commit flag slides past it. That's the whole healthy path, once per heartbeat, forever.
2. Kill the leader mid-story. A timer fires, a candidate with a complete diary wins, and the new reign picks up exactly where the old one stopped. Wake the old leader and watch it discover the higher term and fall in line.
3. Partition the leader with one loyal follower. Type writes into the stranded side: pages pile up in pencil, and the commit flag never moves — two diaries out of five is not a majority. Meanwhile the other three elect a new leader and keep committing. One cluster, two stories, only one of them real.
4. Heal it. The old king meets the higher term and steps down; repair walks its diary back, dissolves the conflicting tail, and stamps the new reign's pages over it. Nothing committed was touched. Everything pencil was disposable. This is the moment most of Raft exists to make boring.
5. Run the laggard for office. Pick the most out-of-date node and force it to campaign. Read the ballots: every healthy voter checks the fingerprint and refuses. The rule you just learned, enforced live, vote by vote.

One detail worth noticing while you play: after any election, the very first thing a new leader commits is a page of its own term. The next section is about why that detail is carrying more weight than it looks.

Go back to the commit definition: replicated on a majority, by the leader that created it. Innocent sentence. The paper spends its most famous diagram — Figure 8 — showing how a reasonable person misreads it, and the misreading is this: "on a majority" is not the same as "committed" when the page is from an older term.

Here's the trap, told with five diaries. The leader of term 2 writes a page into slot 2, copies it to one follower, and crashes. A node on the far side — which never saw that page — wins term 3 with votes from the nodes whose diaries end even earlier, writes its own rival page into slot 2 in pencil, and crashes before copying it anywhere. The original leader comes back, wins term 4, and resumes copying its old term-2 page. The page reaches a third diary: a majority now holds it. Committed?

No. And the villain is the up-to-date rule itself. That far-side node still ends its diary with a term-3 page, and 3 beats 2 — by the comparison you just learned, it can still win an election against nodes whose diaries end in term 2, and the moment it does, the leader's log is the law overwrites slot 2 in every diary it can reach. A page sitting on a majority, erased anyway. If the term-4 leader had told a client "that write is committed," the cluster would have taken back an answer — the one sin the whole section exists to prevent.

So Raft adds its last careful clause, and the paper states it plainly: "Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader's current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property."

In diary terms: old pages don't become permanent by being popular. They become permanent by being buried — when a page from the current reign lands on a majority, Log Matching guarantees every page beneath it sits in those same diaries, and the whole stack commits at once. In the story above, once the term-4 leader replicates a term-4 page onto a majority, the rival's term-3 pencil can no longer win any election: the very rule that made it dangerous now reads it as out-of-date.

This clause also answers a question you might not have thought to ask: how does a freshly crowned leader know where the commit frontier is? It doesn't. It can't count replicas of old pages, and it won't lie to clients. So real implementations have every new leader immediately append a no-op — a blank page in its own term — and commit that. The blank page buries everything behind it, the frontier snaps forward, and the reign can start answering. That's the detail from the lab: the first committed page of every reign is the reign's own.

The core machine is done. What remains is the sanding that production added — starting with a debt this course owes you.

Pre-vote, the promised story. Leader Election left you with an honest wart: a node cut off from the cluster rages in the dark, inflating its term with every failed campaign, and on healing, its swollen number forces a pointless re-election. The fix is almost embarrassingly polite. Before bumping its term, a would-be candidate runs a dry-run election: it asks every node, "would you vote for me?" — same rules, same fingerprint check, but nobody's term changes and no votes are spent. Only a majority of hypothetical yeses unlocks a real campaign. The isolated node's dry runs fail forever, its term never inflates, and healing becomes a non-event: it simply hears a heartbeat and falls back in line. The idea comes from the Raft author's PhD thesis, and etcd ships it switched on by default.

Reads are not free. Here's the question staff engineers ask in the interview: the leader holds the committed state, so can it answer reads locally, no round trips? Almost — and the "almost" is the zombie from two lessons ago. A deposed leader that hasn't yet heard about the new term believes it still reigns, and for that window it would happily serve stale truth. So an honest leader confirms it's still leader before answering: either it checks in with a majority first (etcd calls this ReadIndex), or it holds a clock-based lease — cheaper, but now correctness leans on clocks, and you know from the clock lessons what that bargain smells like. Serving reads is a running theme once coordination becomes a service; the recipes live a few lessons ahead.

Housekeeping, in two sentences. Diaries can't grow forever, so nodes periodically photograph their state machine and tear out every page the photo already covers — that's a snapshot, and it's how a node that's been dead for a week catches up in seconds instead of replaying a year of pages. And clusters do change shape — adding and removing members is its own delicate protocol, because for one careless moment there could be two overlapping definitions of "majority."

The numbers, for scale. The paper suggests election timeouts of 150 to 300 milliseconds. etcd defaults to a 100-millisecond heartbeat and a 1,000-millisecond election timeout, and tuning them is exactly the bet you learned in Heartbeats & Failure Detection: shorter means faster failover and jumpier elections; longer means calmer clusters that grieve longer.

And the roll call, so none of this feels academic. Every Kubernetes cluster: etcd, which is Raft. Consul, Vault, Nomad: Raft. CockroachDB runs a separate Raft group per range of data — thousands of tiny parliaments per cluster. TiKV, the same trick per region. RabbitMQ's quorum queues: Raft. NATS JetStream: Raft. Kafka's KRaft: a dialect where followers pull instead of the leader pushing, but the same terms, the same log, the same rules. You don't study Raft to pass an exam. You study it because it is quietly holding up your stack right now.

• Raft = the election machine you built, plus a replicated log, plus three clauses. The consistency check on every delivery, the up-to-date rule on every ballot, and the current-term commit rule. Nothing else was new.
• Agreement on state is agreement on order. Deterministic state machines fed the same log compute the same world. Raft is the single-writer rung rebuilt so the writer can die.
• Committed means on a majority; applied means executed. The gap between them is normal. The client is answered from committed, never from hoped.
• The leader's log is the law. Followers can lose pencil; leaders never erase their own. Repair walks back to common ground and overwrites the draft.
• The latest term outranks the longest log. Voters compare fingerprints term-first; length only breaks ties. The election refuses ignorant kings, which is why Raft never needs a recovery phase: the election is the recovery.
• Old pages commit by burial, not by popularity. Never count replicas of a previous term's entry; commit a current-term page and everything beneath it commits for free. Every new reign opens with a no-op for exactly this reason.
• Production sanding: pre-vote makes healing boring, ReadIndex or leases make reads honest, snapshots keep diaries short.

Three properties, earned: at most one leader per term (last lesson's proof). Every committed page present in every future leader's diary (the pigeonhole, one more time). No two machines ever applying different commands at the same slot (the two rules of this lesson, combined). That last one is the sentence the whole section was for: a cluster of crashing machines, agreeing on one truth.

One loose end. This algorithm is barely a decade old, it won Best Paper, and in the authors' study most students scored better on it than on the algorithm it replaced — a protocol that had already been running the world's coordination for twenty years while famously resisting explanation. Raft was designed to be understood. The thing it was designed to be more understandable than — why it's legendary, why the mathematics earned twenty years of awe, and why it still lost the popularity war — that story is next: Paxos, the Intuition.