The Famous Bug Was the Hardest to Find
Raft is the algorithm that lets a handful of servers agree on one log of commands, even while some of them crash and the network loses messages. It runs inside etcd, Consul, and CockroachDB. I wrote one: leader election and log replication, a few hundred lines of JavaScript, plus a simulator to torture it.
Same plan as the regex engines: build it, test it hard, then plant bugs on purpose and see which ones the tests notice. The surprise this time was which bug got away.
A world to break it in
The simulator is one event queue and one seeded random number generator, so every run can be replayed exactly. Five nodes send messages through a fake network. It delays each message by a random amount (so messages arrive out of order), drops some, and duplicates some. Every so often it crashes a node and restarts it later, or splits the network in two for a while. A crashed node keeps only what Raft says to save to disk: its current term, who it voted for, and its log. Everything else is lost.
After every single event, a checker tests Raft's safety rules:
- At most one leader per term.
- If two logs have the same term at some index, they're identical up to there.
- A newly elected leader has every entry that was already committed.
- No two nodes ever apply different commands at the same index.
After the chaos stops, one more check: the cluster has to commit a new command within a few seconds. Safe but stuck still counts as a failure.
The test caught me first
The first big batch used swarm testing: each run picks its own mix of faults (cluster size, latency, loss, how often things crash), so some runs are all partitions and some are a thousand tiny crashes. My correct Raft failed 66 of 1,000 runs, all on the liveness check.
Not a safety bug, a slowness bug. A node that came back after a long outage could be 1,000 entries behind, with a stale tail that didn't match. My leader backed up one entry per round trip to find where they agreed, then sent only 20 entries per round of messages. On a lossy network that took longer than the check allowed. The Raft paper mentions the fix in passing: the follower reports the term of the conflicting entry, and the leader skips that whole term in one step. With that, plus streaming the next batch as soon as one is acknowledged, the stuck runs went away.
Then I hit the checker's own bug. It submitted one probe command and waited for it to commit. Sometimes the probe went to a leader that was deposed a moment later, and Raft rightly threw away its uncommitted entry. A client that never retries isn't a client. With retries, the correct implementation passes every run.
Ten planted bugs
Then the mutation testing. Each bug is one small, realistic mistake, switched on by name. Here's how often each one was caught, out of 1,000 runs of 20 simulated seconds each:
| planted bug | fixed | swarm | strict |
|---|---|---|---|
vote-twice | 892 | 679 | 892 |
no-up-to-date-check | 1,000 | 674 | 1,000 |
match-from-next | 928 | 424 | 1,000 |
skip-prev-term-check | 499 | 298 | 499 |
truncate-always | 15 | 50 | 952 |
commit-past-new-entries | 24 | 28 | 24 |
forget-vote | 0 | 25 | 0 |
count-stale-votes | 0 | 2 | 0 |
commit-old-terms | 0 | 1 | 65 |
ignore-higher-term-reply | 0 | 0 | 0 |
"Fixed" uses one set of fault rates for every run. "Swarm" gives every run its own. "Strict" is the fixed mix plus a stronger check, explained below. The correct implementation passed all 1,000 runs in every column. Each bug is described in the demo at the bottom.
The easy ones fall over in seconds: vote twice in a term and you get two leaders; vote for a candidate with an out-of-date log and you get a leader that's missing committed data. The interesting row is commit-old-terms, because it's the one bug everybody is warned about.
Figure 8
Figure 8 of the Raft paper shows a trap. A leader is only allowed to count replicas for entries from its own term. An older entry that happens to be on a majority of servers is not safe yet. Here's the scenario, which you can replay below:
- n0 leads term 1 and appends "b", but only n1 receives it.
- n0 crashes. n4 wins term 2, appends "c" at the same index, and crashes before sending it anywhere.
- n0 comes back, wins term 3, and copies "b" to n2 and n3. Now "b" is on four of five servers. Committed?
- No. n0 crashes again, and n4 comes back. Its last entry is from term 2, which counts as newer than anything from term 1, so the others vote for it. As leader it overwrites "b" with "c" everywhere.
If n0 had counted "b" as committed in step 3, a committed entry just vanished. That's the planted bug, and in a hand-written script it fails every time.
In random testing it was caught zero times in 1,000 runs with the fixed mix, and about once per 1,000 otherwise.
It fired 8,685 times
I instrumented the buggy line. Across 1,000 runs with the fixed mix, the bug fired (a leader counted an old-term entry as committed) 8,685 times, in 999 of the 1,000 runs. The bug wasn't rare at all. Damage was rare.
For a wrong commit to matter, some other node has to be holding a different entry at that index. That happened 199 times. And for it to break anything, that node then has to win an election before the leader overwrites its entry, which is usually milliseconds later. That needs another crash at exactly the wrong moment. It happened zero times.
So there are three steps: the bug runs, it creates a dangerous state, and the danger turns into damage. A random test that only checks for damage pays all three probabilities at once. More chaos didn't help much. Bursts of traffic followed by silence, to set the trap more often, moved it from zero to about two per thousand.
Check for danger, not damage
So I changed the oracle instead of the fuzzer. Raft's correctness argument says why the leader rule is safe: a committed entry is on a majority, and a node missing it can't collect votes from that majority. So right after anything commits, the strict check asks: is there any node, up or down, whose log is up-to-date enough to win an election, that doesn't have this entry? In correct Raft that can't happen, and it never fired. In the Figure 8 replay it fires the moment n0 counts "b" as committed, before anything has gone wrong, while n4 is still down.
With the strict check, commit-old-terms is caught in 65 of 1,000 runs instead of 0. The bug where followers chop off their log on every message, which only showed up 15 times before, now shows up 952 times. Same runs, same seeds. The fuzzer was already finding these bugs. The checker just wasn't looking.
What still gets through
- forget-vote (a restarted node forgets who it voted for): needs a voter to crash and come back in the middle of one election, then vote again. The fixed mix never caught it. Swarm caught it 25 times in 1,000, and 18 of the 22 that broke within the main run were three-node clusters, where one double vote is enough to give two candidates a majority. My fixed mix only ever used five nodes. Swarm testing earns its keep exactly here: it tries the configurations I didn't think to.
- count-stale-votes (a candidate counts a "yes" from an earlier election): needs a vote delayed across a whole election timeout. Caught a couple of times per thousand.
- ignore-higher-term-reply: never caught, and I think that's correct. A deposed leader that ignores "you're out of date" replies can't commit anything, because its followers reject its old term. It steps down the next time it hears from the new leader. It wastes some time, but it's not a safety bug, so the checker shouldn't flag it.
The regex lesson was that a test that has never failed hasn't told you anything. This one adds to it: a random test finds a bug in proportion to how often it causes damage, not how often it's wrong. The famous bug was wrong 8,685 times and harmless every time. If your checker can describe a dangerous state, check for that and don't wait for the crash.
Try it
Five nodes, live. The orange ring is the leader. The grey arc around each follower is its election timer; when it runs out, the node calls an election. Click a node to crash it, or click it again to restart it. The rows below are each node's log: the number is the term, and bright means committed. Pick a planted bug and hit fast-forward to see how long it takes to break. Replay Figure 8 with no bug, then again with commit-old-terms, then again with the strict check on.
The source is one file: Raft, the simulator, the checks, and the planted bugs. What I left out is most of what makes Raft hard in production: snapshots, membership changes, real disks that lie about fsync, and clients that need exactly-once answers.