The master dies: what actually happens to your data

Four ways to lose an acknowledged write

None of the four is exotic. Each has its own subsection in the Raft paper, and subsections do not get written for fun: somebody had already shipped the obvious version.

The third row is the nastiest: it needs four leadership changes in a particular order and turns up in debugging approximately never. In the paper it is Figure 8, and the algorithm carries an extra rule purely because of it.

Why ordinary tests miss this

• An integration test runs the happy path: everyone alive, the network fine, every message delivered once and in order. That is precisely the path on which a consensus algorithm is not needed.
• Chaos engineering kills containers at random moments — but does not record what exactly it did. It failed once, and it cannot be replayed.
• A failure that cannot be replayed does not get fixed; it gets blamed on infrastructure. It is the same mechanism as with a flaky test, only the price of being wrong is different.
• Time is scarce. Catching a rare schedule in a real cluster costs real seconds, and there are thousands of schedules worth catching.

A simulation instead of a rack of servers

Step one is to make the node a state machine with no I/O in it. It touches neither clock nor socket nor disk: tick advances its timers, receive feeds it a message, propose gives it a command, and everything it wants to do comes back out through takeMessages and takeApplied. etcd’s raft package has the same shape for the same reason: an implementation that calls setTimeout and writes to a socket internally can only be tested by running it and hoping.

Step two is that the cluster exists only inside the simulation. Every tick, delay, dropped packet, duplicate, reordering and crash is a decision drawn from a seed. Raft’s proofs assume exactly that world — messages lost, delayed, duplicated and reordered, nodes crashing and restarting. Injecting anything less means testing a network the algorithm was never designed for.

import { check } from 'unflake';
import { runScenario, SafetyMonitor, checkLinearizable, operationsFrom, HOSTILE } from 'bulwark';

await check('raft stays safe', async (sim) => {
  const { cluster } = await runScenario(sim, {
    size: 5,
    clients: 3,
    faults: HOSTILE,
    chaos: true, // crashes, restarts, partitions
  });

  // Replicas are compared once the faults have stopped.
  const disagreement = SafetyMonitor.replicasAgree(cluster);
  if (disagreement) sim.fail(disagreement);

  // Every client history is checked for linearizability.
  const report = checkLinearizable(operationsFrom(cluster.history));
  if (report.status === 'not-linearizable') sim.fail(report.reason);
}, { runs: 200 });

What is actually checked

The five safety properties from the Raft paper are evaluated after every state transition — after a tick, after a delivered message — rather than polled once a second. A violation is then attributed to the transition that caused it, not to the moment the test happened to look.

Separately there is linearizability of the client history: every operation must appear to take effect instantaneously at some point between its call and its return, and all of them in a single order consistent with real time. A system can satisfy all five properties and still show a client something impossible — apply a retried command twice. Consensus is intact and the client saw the impossible, which is exactly why payment systems need idempotent operations.

Deciding linearizability is NP-complete, so the search has a budget. When the budget runs out the honest answer is inconclusive, not “fine”. The gap between “not found” and “does not exist” is the same one as with sampled schedules.

Testing the test: the bug museum

A suite that is always green might be catching bugs or might be looking at nothing — the colour does not tell you which. So you take the working implementation, switch off exactly one rule of the algorithm, and require the harness to catch it with a seed and with the name of the property that broke.

no up-to-date check      → Leader Completeness: n2 became leader in term 4 without
                           committed entry r6 at index 8 (term 1)              (run 2)
no prevLog check         → Log Matching: index 1 term 1 holds noop:n1:1 elsewhere
                           but r2 on n4                                        (run 1)
keeps conflicting entry  → State Machine Safety: index 8: n5 applied noop:n5:6,
                           n2 applied r7                                       (run 4)
no leader no-op          → replicas disagree: n1={"a":"p1.2","b":"p0.2"}
                           but n4={"a":"p1.2","b":"p1.3"}                       (run 25)
ignores a newer term     → client 2 gave up on cas                             (run 1)
Figure 8                 → Leader Completeness: n5 became leader in term 4 without
                           committed entry entry-A at index 1 (term 1)         (run 1)
unpersisted vote         → Election Safety: n2 and n3 are both leader in term 1

What matters is not that all seven are caught but that they are caught differently. Three break a safety property outright. One leaves every safety property intact and quietly stops the cluster converging. One costs no safety at all — only progress. Flattening that into “the test goes red” throws away the informative part.

The last two exhibits are directed rather than random. Figure 8 needs four leadership changes in a prescribed order with prescribed partitions; the window in which a vote fails to reach disk is one tick wide. Hoping to stumble into either is not a plan.

The bug the harness found in the implementation itself

This is the case the whole apparatus exists for. Every safety property held under every schedule — and the chaos suite still failed, on run 25, with two replicas holding different values. The logs agreed. Nothing had crashed. No rule from the paper had been violated.

The cause is §5.4.2 working exactly as specified. A leader may not commit an entry inherited from an earlier term by counting replicas; it has to commit an entry of its own term, which carries the earlier ones with it. But if the clients fall silent right after a leadership change, that entry never arrives — so the inherited entries stay uncommitted forever, and replicas that applied them under the previous leader sit permanently ahead of replicas that never got the commit signal.

The remedy is one sentence in §8: a new leader immediately appends a blank no-op entry for its own term. That is now in the implementation, and its absence is exhibit four in the museum.

What this method cannot do

• Passing is not proof. Hundreds of seeds are hundreds of schedules from an astronomically larger space. A very good fuzz run, not a theorem; TLA+ specifications of Raft prove things a simulation cannot.
• The fault model is finite. Loss, delay, duplication, reordering, partitions and crash-restart with durable state — yes. Disk corruption, partial writes, clock skew and Byzantine behaviour — no.
• This is not a database. No membership changes, no log compaction, no snapshots — and those are exactly what turns a correct algorithm into a deployable system, each with its own safety argument.
• The checker can give up. Linearizability is NP-complete, the budget is finite, inconclusive is a real outcome and is reported as one.

What to ask when someone promises you fault tolerance

The last question is the most practical. What usually gets lost is not consensus itself but the boundary around it: a retry without an idempotency key, an “ok” sent before the commit, a repeat that duplicates a payment. We cover that in our work on financial systems and cloud infrastructure; the full list of technical write-ups lives in the Engineering section.