Commentary: raft-toy

An entry sits on three of five servers — a real majority — and the leader is forbidden to call it committed, because it was created two terms ago. Two steps later it exists on no server at all. Figure 8 of the Raft paper, staged deliberately. A study guide for raft.py.

cd raft-toy
python3 demo.py      # the aha (§6)
python3 test_raft.py # pins every number this page claims

1. Orientation

This toy is five simulated servers running a stripped-down Raft: leader election, log replication, and the commit rule. There are no threads, no sockets, no clock and no random number generator. Messages accumulate in a Python list, and a driver decides which ones get delivered and which ones are thrown away.

That is the whole trick. A run is a pure function of the schedule, so the schedule can be written down — and this toy is about one specific schedule, the one drawn as Figure 8 of the Raft paper.

You will see the same five-phase schedule executed twice. The first time, the cluster uses the commit rule almost everybody invents when they first think about replication: an entry is committed once a majority of servers store it. The second time it uses the rule Raft actually specifies. Nothing else differs — figure8() takes the rule as an argument and changes not one other line.

The first run reports an entry committed. Two steps later, that entry does not exist on any of the five servers.

By the end you should be able to:

• state the commit rule from Raft §5.4.2 from memory, and say why "a majority stores it" is not it;
• point at the one line in raft.py that separates the two rules, and predict what deleting it does;
• explain why the entry that destroys the "committed" value is one that was never replicated to a single other server;
• say what a leader must do at the start of its term before it can safely answer a read, and why real systems write a no-op to do it.

2. The problem this mechanism exists to solve

A replicated log has one job: every server applies the same commands in the same order, and once a client is told "done," it stays done. The second half is the hard part, and it is the only part this toy is about.

"Done" has to mean something specific, because the leader is a single machine that can die at any instant. The obvious definition is a quorum: once a majority of servers have the entry on disk, any future majority must overlap this one, so at least one server in any future election has the entry. That overlap argument is correct, and it is why quorums are everywhere.

The trap is that overlap guarantees the entry survives somewhere; it does not guarantee the next leader keeps it. Those are different claims, and the gap between them is where Figure 8 lives. A future leader is chosen by an election, and the election rule compares logs by their last entry's term, not by whether they contain some particular older entry. A server can hold your majority-replicated entry and still vote for a candidate that does not have it, because that candidate's log looks newer.

So there are two competing goals:

• Commit early. The sooner an entry is declared committed, the sooner the client hears back, and the sooner a new leader can serve reads from it. Counting replicas is the cheapest possible test — one integer comparison per peer, no extra round trips.
• Never unsay it. A commit is a promise. Withdrawing one is not a performance problem, it is a correctness catastrophe: the state machine has already applied the command, and the client has already acted on the answer.

Raft resolves this by making the cheap test legal only for entries the current leader created itself. Everything older gets committed indirectly, carried along behind a current-term entry. That is more conservative than strictly necessary — the paper says so outright, noting there are situations where a leader could safely conclude an older entry is committed (for example if it is stored on every server) — and Raft declines the extra cases for simplicity.

Other designs make other choices. Multi-Paxos attaches a ballot number to each slot independently, so it does not inherit this problem in the same shape; Viewstamped Replication runs an explicit view-change protocol that reconciles logs before the new primary accepts anything. Raft's answer is cheaper to implement and, as this toy shows, has exactly one subtle consequence you have to know about.

3. Background you need

The two starred rows carry the result. Everything else is scaffolding you need in order to stage the situation where they matter.

4. The mental model

Five servers, one log each, growing left to right. Each cell is command@term. The schedule walks the cluster through five states:

The shape to remember: index 2 is contested. Two different leaders, in two different terms, each put a different command in that slot. A majority holding one of them is not the same as that one having won.

The fix, in one picture:

5. Reading the source

In reading order. Every excerpt is captioned with its provenance so it cannot drift from the file.

5.1 Entry — why the term is stored per record

class Entry:
    """A log record. Storing the creating leader's `term` is what makes the
    commit rule expressible at all."""

    __slots__ = ("term", "cmd")

This looks like bookkeeping and is not. An entry's term is set once, by the leader that created it, and it is never rewritten — not when a later leader replicates it, not when it is finally committed. That immutability is the whole reason advance_commit can ask "is this entry mine?" three terms later.

If entries were stamped with the term of whoever last replicated them, b@2 would become b@4 the moment S1 pushed it out in step (c), the commit rule would see a match, and Raft would have exactly the bug it is designed to avoid. The paper flags this explicitly: log entries retain their original term numbers, and the extra complexity in the commitment rules is the price.

5.2 on_vote — the election restriction

def on_vote(self, m):
    """The election restriction: never vote for a candidate whose log is
    behind yours, by (term, index) -- a longer log with an older final term
    loses to a shorter one with a newer term."""
    idx, lt = self.last()
    up_to_date = (m["last_term"], m["last_index"]) >= (lt, idx)
    granted = (m["term"] == self.term
               and self.voted_for in (None, m["src"])
               and up_to_date)

Three separate conditions, and the tuple comparison is doing more than it looks. Python compares (last_term, last_index) lexicographically, so term dominates index: a candidate with a shorter log wins the comparison if its final entry is from a newer term.

That is not a quirk of the encoding, it is the rule from §5.4.1, and it is precisely what lets S5 — whose log is [a@1, c@3], two entries — beat S2 and S3, whose logs are [a@1, b@2], also two entries. Term 3 beats term 2. S5 wins and truncates.

The >= rather than > is load-bearing in the most literal way. Change it and the cluster cannot hold a single election:

With >, a candidate must be strictly newer than every voter — but at the start of time all logs are empty and equal, so nobody ever grants a vote, S1 burns all four attempts, and the demo dies with a KeyError on the first client write. With >=, the same call returns term 1 and the role leader.

5.3 send_append — the consistency check

def send_append(self, p):
    """Carries the (index, term) of the entry *before* the ones it sends;
    a follower matching there matches everywhere earlier."""
    ni = self.next_index[p]
    self.send(p, type="append", term=self.term, prev_index=ni - 1,
              prev_term=self.log[ni - 2].term if ni > 1 else 0,
              entries=self.log[ni - 1:], commit=self.commit_index)

Every AppendEntries carries the index and term of the entry before the ones it is sending. The follower accepts only if it has an entry at that index with that term. That single check is the Log Matching Property: if two logs agree on (index, term) at one position, they are identical at every earlier position.

This is what makes "prior entries are committed indirectly" a theorem rather than a hope. When step (c′) commits index 3, it is not separately verifying that indexes 1 and 2 are replicated — it is relying on the fact that a follower which accepted index 3 must match everywhere below it.

5.4 advance_commit — the whole toy

def advance_commit(self):
    """THE commit rule. Walk down for the highest index a majority stores;
    under RAFT, skip any index whose entry came from an earlier term."""
    for n in range(len(self.log), self.commit_index, -1):
        stored = 1 + sum(1 for p in self.peers if self.match_index[p] >= n)
        if stored * 2 <= len(self.peers) + 1:
            continue
        if self.rule == RAFT and self.log[n - 1].term != self.term:
            continue                      # <-- Figure 8 lives on this line
        self.commit_index = n             # everything below n rides along
        return

Four judgement calls in nine lines. Three of them turn out to matter, and one does not — all four were checked by writing the variant and running it against the same schedule (§7.4).

The term clause is the mechanism. Delete it — which is exactly what rule == NAIVE does — and the demo's headline flips from "refused" to "committed, then erased."

The return is not an optimisation, despite looking like one. The loop counts down from the newest entry, so the first index that qualifies is the highest one, and returning there is correct. Remove the return and the loop keeps going to lower indexes, each assignment overwriting the last, so commit_index ends up at the lowest qualifying index instead of the highest. Run under the naive rule, that variant reports claimed b@2 committed: False against a baseline of True — it silently un-does the very thing the demo is built to show.

stored counts the leader itself via the leading 1 +. The leader has the entry by construction (it appended it), and match_index only tracks peers. Forget the 1 + and a 5-node cluster needs 3 followers, i.e. 4 of 5, which is a quorum of a 7-node cluster.

The <= is the one that does not matter here, and it is worth knowing why. stored * 2 <= len(self.peers) + 1 rejects; with 5 nodes len(peers) + 1 is 5, so it commits at stored in {3, 4, 5}. Changing it to < gives {3, 4, 5} as well — identical. The two differ only at even cluster sizes: with 4 nodes, <= commits at {3, 4} and < commits at {2, 3, 4}, and 2 of 4 is not a majority. The line is a real off-by-one hazard that this schedule cannot expose, which is a good argument for odd cluster sizes and a better argument for not trusting a line because one test passed.

5.5 on_append — the line that erases a commit

def on_append(self, m):
    ok = False
    if m["term"] >= self.term:
        self.role = "follower"
        pi, pt = m["prev_index"], m["prev_term"]
        ok = pi <= len(self.log) and (pi == 0 or self.log[pi - 1].term == pt)
    if ok:
        # The leader's log wins, unconditionally. This truncation is the
        # line that erases a "committed" entry in the demo.
        self.log = self.log[:pi] + list(m["entries"])

self.log[:pi] + list(m["entries"]) is an assignment, not an append. A follower does not merge, negotiate or object; whatever the leader sends replaces everything from pi onward. In step (d) that one expression deletes b@2 from S2, S3 and S4, and in step (e) from S1.

5.6 Cluster.deliver — determinism, and the partition model

def deliver(self, only=None, rounds=12):
    """Run until quiet. Anything addressed outside `only` is LOST, not
    queued -- the partition model, and what lets a schedule say "this
    entry reaches exactly S2"."""
    for _ in range(rounds):
        batch, self.net[:] = list(self.net), []
        if not batch:
            break
        for m in batch:
            if self.nodes[m["dst"]].alive and (only is None or m["dst"] in only):
                self.nodes[m["dst"]].recv(m)

Two decisions here.

Messages outside only are dropped, not queued. They are gone. That is what lets the schedule say "this entry reaches exactly S2 and nobody else" in one argument, and it is a faithful model of a network partition that heals after the interesting moment has passed. A queue would be a delay model, which is a different thing and cannot produce step (a).

The loop runs until the network goes quiet. One deliver() call is therefore "let the cluster settle," not "advance one tick" — which is what makes next_index back-off (a reject, a decrement, a resend, an accept) complete inside a single call. rounds=12 is a safety valve against an infinite exchange, not a tuning knob; the demo never approaches it.

Nowhere in this file is there a time, a random, or a thread. The determinism is structural, not injected: there is nothing to seed.

6. The demo, and what it proves

python3 demo.py. The real output follows, in three parts.

6.1 The naive rule

6.2 Deriving the majority

The headline number is 3. Five servers, so a majority is ⌊5/2⌋ + 1 = 3. After step (c), holders(2, 'b') returns [1, 2, 3]:

The leader computes the same count arithmetically: stored = 1 + |{p : match_index[p] >= 2}| = 1 + |{2, 3}| = 3, and 3 * 2 = 6, which is greater than len(peers) + 1 = 5. A genuine majority, by the same test that would commit any current-term entry.

The naive rule stops there and sets commit_index = 2. The transcript line commit_index = 2 [rule = naive] is that assignment.

6.3 Why the majority did not save it

Step (d) is the punchline, and it turns on one comparison. Candidate S5 sends last_index=2, last_term=3. Each voter evaluates (m["last_term"], m["last_index"]) >= (lt, idx):

Three grants plus S5's own vote is 4 of 5 — S5 becomes leader of term 5, and its first AppendEntries truncates index 2 on all three. Note what S2 and S3 just did: they voted away an entry they were personally storing. They had b@2 in their logs. Nothing in the vote path looks at that. It compares last terms, and 3 > 2.

The last line of the run is the verdict:

A client that wrote b was told the write was durable. Five servers later hold no trace of it.

6.4 The same schedule, real rule

Step (d) still happens. S5 still wins, still truncates, and b@2 still ends up on nobody. Raft does not prevent the overwrite — it prevents the lie. That distinction is the single most useful thing on this page. The safety property is not "committed entries are never lost"; it is "an entry that was declared committed is never lost," and the rule earns that by declaring fewer things.

The commit_index = 0 is worth a second look, because it is stronger than "it refused index 2." S1 in term 4 cannot commit index 1 either: a@1 is from term 1, which is also not term 4. Its log is two entries long, a majority stores both, and it may commit neither.

That is not a bug in the toy, it is Raft, and it is why commit_index returning to 0 on restart (Cluster.crash, raft.py line 200) matters — it is volatile state in Figure 2 of the paper. A freshly elected leader genuinely does not know which entries are committed, and cannot find out by counting. The real fix is in §8 of the paper: "Raft handles this by having each leader commit a blank no-op entry into the log at the start of its term." One write of the leader's own term, and everything below it commits at once. test_raft.py pins exactly that: a term-4 leader with [a@1, b@2] and a majority commits 0, and the same leader with [a@1, b@2, no-op@4] commits 3.

6.5 The boundary — where the effect vanishes

The paper's Figure 8(e). Same schedule as before, with one extra line: while S1 is leader in term 4, it accepts one more client command, d, and gets it to the same majority that already has b@2.

commit_index jumps from 0 to 3 in one step. Index 3 qualifies on its own merits — d@4, leader's term 4, stored on 3 of 5 — and indexes 1 and 2 are committed indirectly, by the Log Matching Property: any server that accepted index 3 necessarily matches at 1 and 2.

And now S5 cannot come back. Its last entry is c@3; S2's and S3's is d@4, and (3, 2) >= (4, 3) is false, so they refuse. S5 campaigns four times, burning terms 4, 5, 6 and 7, and collects only S4's vote each time — S4: voted_for=5, while S2 and S3 show voted_for=None at term 7, having stepped down to the higher term without granting anything. Two votes of five is not a majority. b@2 survives on [1, 2, 3].

The effect vanishes the moment the leader writes anything of its own. In a real cluster under load that is microseconds, which is why this hazard is invisible in practice and why it took a figure in a paper to make people see it. The dangerous window is precisely an idle cluster that has just changed leaders — which is also the window right after a failure, when a monitoring system is most likely to be issuing reads.

6.6 What the trace itself proves

Two events in the schedule were removed one at a time and the run repeated. Both results were surprising enough to be worth stating.

Remove the partition in step (a) — let b@2 reach all five servers instead of only S2:

S5 wins step (d) exactly as before — but it does no damage, because its log is now [a@1, b@2, c@3]: c landed at index 3, not index 2, so there is no conflict to truncate. The hazard was never about S5 winning. It was about the dropped message in step (a), which is what created two different entries competing for one index.

Remove S5's own write in step (b) — S5 becomes leader but never accepts c:

S5 cannot win step (d) at all. Its last entry is a@1, term 1, against S2 and S3's term 2 — it burns four terms and fails. So the entry that destroys a majority-replicated value is c@3: an entry that was never replicated to a single other server, and that no client was ever told anything about. It never needed to be durable. It only needed to exist, once, on one machine, long enough to raise that machine's last log term.

6.7 The tests

python3 test_raft.py — 13 tests, all passing, no pytest:

They pin the headline (both rules on the identical schedule, opposite verdicts), the majority arithmetic at step (c), the boundary, the negative result from §7.2, and unit checks on the vote comparison, the next_index back-off, truncation, crash persistence, message loss, and byte-identical output across repeated runs.

7. Design decisions and roads not taken

7.1 A written schedule, not a searched seed

The alternative was to give the driver randomised election timeouts and random crash injection, search seeds until one produced a violation, and ship the seed. That is a legitimate technique, and it was measured rather than dismissed.

A search was actually run against this exact raft.py: 3000 seeds, each a 40-round random schedule (random crashes, restarts, campaigns, client writes, and a random delivery subset each round), all under the naive rule, watching for an entry that a leader had reported committed and that later differed at that index. It works — 170 of 3000 seeds, 5.7%, produce a violation. Those figures come from that run and nothing else; they are not quoted from anywhere.

The search was still rejected, on the evidence it produced about itself:

A reader can hold the scripted version in their head. The searched version requires trusting a magic number and reading a 50-event trace to find the needle — and worse, it hides the adversary. The whole lesson is what an attacker has to arrange: a dropped message, two crashes, and one write that goes nowhere. A seed says "this happens sometimes." The script says why.

The 5.7% earns its place here anyway, because it answers the obvious objection: if the schedule is hand-picked, is it a contrived special case? No. Random schedules hit it roughly one time in eighteen.

7.2 The negative result: the election restriction is not what saves you

The obvious guess, having read §5.2, is that the (term, index) comparison in on_vote is doing the safety work — that it stops the wrong candidate winning. It was tested by weakening it to compare log length only, ignoring terms entirely, and re-running the identical schedule under the real commit rule.

Nothing changed. claimed=False, b@2 survivors: none, S5's final log [a@1, c@3]. S5 still wins step (d), because with length-only comparison its two-entry log ties S2's and S3's two-entry logs and >= grants the vote anyway.

So the election restriction is not what saves Figure 8 in this schedule; the commit rule is, on its own. This is worth knowing because the two rules are usually taught together as a pair, which makes it easy to assume either one would do. The paper's own safety argument (Figure 9) needs both — the restriction is what makes the general proof go through, and there are other schedules where it is the binding constraint. But it is not load-bearing here, and a commentary that claimed it was would be wrong.

7.3 Why ship both rules in one file

Node.rule is a string compared inside the hot path, which is not how anyone would write production code. It buys the only thing this page really needs: the guarantee that both runs execute the same schedule. Two separate implementations, or a git branch, would leave the reader wondering whether some other difference crept in. One function, one argument, one clause.

7.4 The counterfactuals that were run

Every judgement call in advance_commit and on_vote was replaced with its plausible alternative and re-run against the same schedule:

Two of the seven are negative results, and they stayed in. A line that looks decisive and is not is worth as much page space as one that is.

7.5 What is deliberately absent

• Randomised election timeouts. See §8 — the reason is substantive, not budgetary.
• Snapshots and log compaction. Orthogonal to the commit rule, and the paper gives them their own section (§7).
• Cluster membership change. The joint-consensus protocol is a second mechanism and would make this two toys.
• Disk persistence. Node.term, voted_for and log are marked persistent by a comment and by crash() not clearing them. Actually writing and fsync-ing them is wal-kv's subject, not this one.
• Client sessions and deduplication. The paper's §8 answer to "the leader died after committing but before replying" is serial numbers per client. Out of scope.

8. What's simplified vs. the real thing

Messages are Python dicts in a list. No serialisation, no network, no retransmission, no reordering beyond what the driver chooses, and no duplicate delivery. Real implementations must handle all four; the RPCs are specified as idempotent for exactly this reason.

Delivery is synchronous and batched. deliver() runs the cluster to quiescence, so a leader's next_index back-off — reject, decrement, resend, accept — completes atomically from the schedule's point of view. Real leaders do this over many round trips, and real implementations optimise it by having the follower return a conflict hint so the leader can skip a whole term's worth of entries instead of decrementing one at a time.

Everything the follower is missing, in one message, and no heartbeats. The toy sends self.log[ni - 1:] and only ever sends when something changes. Real leaders heartbeat on an interval to suppress elections and to propagate commitIndex, which is why followers here lag on commit in the transcript (S2 shows commit=1 while the leader shows 3).

No state machine. Entries are strings that are never applied to anything. commit_index is the promise; a real system also has lastApplied and a state machine behind it, and the whole point of committing is to feed that machine.

No persistence, no fsync. Marked, not implemented — see §7.5.

Scale. The paper reports its own RAMCloud implementation at roughly 2000 lines of C++ excluding tests, comments and blanks, for a mechanism this toy covers in 152 lines of Python. The missing 1850 lines are almost entirely the five items above.

Budget note. raft.py is 216 lines total against this repo's 100–200 line target. 152 of those are code and the rest are comments and docstrings; the overrun is real and it is because this toy needs three sub-protocols — election, replication, and the commit rule — where every other toy in the repo needs one.

9. Check yourself

Every answer is derivable from raft.py and the transcripts above, and every one was verified by running it.

10. Further reading

• In Search of an Understandable Consensus Algorithm (Extended Version) — Ongaro & Ousterhout, 2014. The paper. §5.4.2 is this toy in two paragraphs, and Figure 8 on page 8 is the schedule demo.py stages; the caption names the same servers and votes. §8 is where the no-op entry appears. Read §5.4 before anything else.
• raft.github.io — the project's home, with a live cluster visualisation that lets you crash nodes by clicking them. The best complement to this toy: it shows the timeout half that this toy deliberately omits.
• Consensus: Bridging Theory and Practice — Ongaro's dissertation, 2014. The long version: membership change, log compaction, and a much fuller treatment of read-only queries and leases. Chapter 3 restates the commit rule with more room than the paper had.
• The Secret Lives of Data — a scrolling animation of leader election and replication. Worth twenty minutes before reading the paper if terms and elections are new; it does not cover the Figure 8 hazard.
• ongardie/raft.tla — the TLA+ specification of Raft. Where "we checked the safety argument" stops being a figure of speech. Diff it against raft.py to see what a real specification keeps that a toy throws away.
• etcd-io/raft — the Raft library behind etcd, and the one most people actually run. advance_commit's production cousin is two functions: raft.maybeCommit (raft.go) calls raftLog.maybeCommit(entryID{term: r.Term, index: r.trk.Committed()}), and that in turn commits only if at.term != 0 && at.index > l.committed && l.matchTerm(at) — where matchTerm is t == id.term, the term of the entry at that index against the leader's current term. The same clause, in Go. The no-op is there too: becomeLeader appends &pb.Entry{Data: nil} and panics if it is dropped.
• Raft does not guarantee liveness in the face of a full omission adversary — a short, sharp piece on where Raft's guarantees stop. Good calibration after this page, which is entirely about safety.
• Jepsen: etcd 3.4.3 — what it looks like when someone tests these properties adversarially against a real system rather than a 216-line simulation.
• Raft user study — the study behind the paper's "understandable" claim, comparing students learning Raft against students learning Paxos. Unusual and worth skimming for what it says about which parts people get wrong.