Lesson 8. Raft, Leader Election and Log Replication

Mission link: Lesson 7 named the replicated-state-machine problem consensus solves. Raft is the specific, deliberately understandable protocol this workspace uses to make that concrete: this lesson covers its two core mechanisms, before lesson 9 covers what running either actually costs.
Primary source: Paper: "In Search of an Understandable Consensus Algorithm", Ongaro and Ousterhout, 2014
Prerequisites: Lesson 7, Partial failure

Warm-up

1. ▢ Define a replicated state machine and the problem it solves.

2. ▢ Distinguish safety from liveness for a consensus protocol.

Know this

Raft's first move: reduce consensus to "agree on who's in charge"

Raft's central design choice is leadership: at any time, at most one server in the cluster is the leader, and every client write goes through it. This turns the general "how do multiple servers agree on a value" problem into two narrower ones: first, how does the cluster elect a leader and detect when it needs a new one (leader election); second, given a leader, how does it get its log of commands replicated correctly to the rest of the cluster (log replication). Reducing consensus to these two mechanisms is exactly what the paper's title means by "understandable": each piece is simpler to reason about than a single protocol solving both problems undifferentiated.

Leader election: a term counter and a majority vote

Every server is a follower, a candidate, or the leader. A follower that stops hearing from a leader within a timeout (lesson 3's failure-detection problem, applied here directly) becomes a candidate, increments a monotonically increasing term number, and requests votes from the rest of the cluster. A server votes for at most one candidate per term, on a first-come basis; a candidate that receives votes from a majority of the cluster becomes leader for that term. Requiring a majority, not unanimity, is what lets Raft keep working when some servers are unreachable: it only needs more than half the cluster to agree at any moment, not all of it.

Log replication: the leader is the only source of truth for order

Once elected, the leader accepts client commands, appends each one to its own log, and replicates that log entry to followers via AppendEntries messages. A log entry is considered committed, safe to apply and report as done, once the leader confirms a majority of servers have stored it. Followers never accept commands directly from clients and never independently decide their own log order; they only ever adopt entries the current leader sends them. This is the mechanism that provides the single agreed order lesson 6 and 7 described: since only one leader proposes order at a time, and a majority must durably store each entry before it's committed, no two conflicting orders can both become committed.

Why a term number, not just an election, prevents split-brain

A stale leader that hasn't noticed a new election happened (it was partitioned away, then reconnects) could otherwise keep believing it's still in charge. Raft prevents this with the term number: every message carries the sender's term, and a server that sees a higher term than its own immediately steps down (if it was a leader or candidate) and updates its own term. A stale leader's AppendEntries messages get rejected by followers who've already voted in, and moved on to, a higher term, so the old leader discovers it's stale as soon as it talks to anyone from the new term and reverts to being a follower.

Practice

1. ▢ Why does reducing consensus to "elect one leader, then replicate its log" make Raft easier to reason about than a protocol without a designated leader?

2. ▢ Why does Raft require only a majority vote to elect a leader, rather than a unanimous one?

3. ▢ When is a log entry considered committed, and why does that specific condition matter for safety?

4. ▢ A leader gets partitioned away from the rest of the cluster, which elects a new leader in its absence. The old leader later reconnects, still believing it's in charge. What stops it from causing a conflicting write?

5. ▢ Which claim correctly describes Raft's core mechanisms?

   • a) Followers independently decide log order and reconcile differences after the fact
   • b) A leader is elected by majority vote per term, and only the leader proposes log order, which followers replicate; a majority must store an entry before it's committed
   • c) Raft requires unanimous agreement from every server before committing any log entry
   • d) Term numbers are only used for debugging and have no role in preventing conflicting leaders

Real-world reps

• [ ] Use the primary source's companion visualization (raft.github.io) to watch a simulated leader election and a simulated network partition, and note what happens to the partitioned-away leader when the partition heals.
• [ ] Find a system you know of that uses Raft (or a similar leader-based consensus protocol) for coordination. Identify what decision its leader is elected to make authoritative (a configuration value, a replication order, a lock).
• [ ] Tomorrow: read the primary source's section on log replication and commitment in full, including its argument for why an entry from a previous term can't be considered committed just because a majority stores it under the current leader, without an entry from the current term also being replicated.

Going further

• Paper: "In Search of an Understandable Consensus Algorithm", Ongaro and Ousterhout, 2014
• Site: "The Raft Consensus Algorithm", raft.github.io
• Resources

Not landing? Reread the primary source at the top, since this lesson compresses it and compression is where understanding leaks. Check the glossary for any term that felt slippery.

If the lesson itself is unclear rather than the material, that is a defect: open an issue.