Acknowledged, then forgotten: a crash under periodic fsync

Figure 1Under periodic, the acknowledgement comes before the bytes reach the disk. Pull the plug inside that window and the record is gone from this broker.

Felix's default fsync mode is periodic. A broker acknowledges a record once the bytes are in the page cache, and a timer flushes them to the device every 250 ms. Lose power inside that window and the record is gone from that broker's disk.

The usual answer is replication. The record is on other replicas, so the broker that crashed can copy it back. Kafka's operations docs make that argument directly. They recommend “the default flush settings which disable application fsync entirely,” and say “a failed node will always recover from its replicas” (Kafka docs, Application vs. OS Flush Management).

The argument has a precondition. The cluster has to know that the crashed node is behind. Felix didn't.

What we found

Take a shard with three replicas, A leading, B and C following, and Quorum acknowledgement (a majority of the three).

A client publishes W. A appends it and ships it to B. B answers. A and B are a majority, so A acknowledges W to the client. C hasn't received it yet.
B loses power before its next flush. W was only in its page cache.
B restarts. Its data directory is intact, and it comes back with a log that ends before W.
A's last report to the control plane says B is caught up. Nothing contradicts it: the shard is idle, so nothing new ships, and A's cursor for B still says “confirmed through W”.
A dies.
Placement looks for a caught-up follower, finds B in A's report, and promotes it.
B serves the shard without W. C never had it. The record the client was told is durable is gone.

Figure 2The seven steps on one timeline. Two faults, and the record the client was promised is held by nobody who serves the shard.

Why it matters

The client was told W was safe, and it wasn't. Nothing in the cluster noticed: no error, no warning, no log line. B served the shard with a gap where W used to be, and the first sign of trouble would be a consumer that never saw a record it was promised.

It took two faults, a follower losing power and then the leader dying, but those are exactly the faults three replicas with majority acknowledgement are meant to survive. It also happened in the default configuration. Nobody had to turn on anything unusual.

The leader version, below, was worse. A leader that lost power and came back quickly could write new records over offsets it had already acknowledged, so the loss wasn't even limited to the idle-shard case.

How we found it

It came out in stages. The first piece turned up while reviewing an unrelated change: on an idle shard, the leader never refreshed its view of a follower, so a follower that lost its whole disk went on being reported as caught up (#1266). The fix for that gave each data directory an identity. Reviewing that fix turned up the next problem. A crash under periodic keeps the directory, so it keeps the identity, but it can still lose the tail (#1284).

The TLA+ model of a shard (docs/formal/FelixShard.tla) already had a Wipe action for a lost directory. I added Crash, which keeps the directory and drops an unsynced suffix:

Crash(f) ==
    /\ CrashLoses
    /\ wipes < Wipes
    /\ IF CrashLeader THEN bgen[f] > 0 ELSE bgen[f] = 0
    /\ Len(log[f]) > 0
    /\ \E k \in 0..Len(log[f]) :
          /\ log' = [log EXCEPT ![f] = SubSeq(@, 1, k)]
          /\ hwm' = [hwm EXCEPT ![f] = IF @ > k THEN k ELSE @]
    /\ wipes' = wipes + 1
    /\ IF RotateOnCrash
       THEN /\ sid' = [sid EXCEPT ![f] = @ + 1]
            /\ registered' = [registered EXCEPT ![f] = sid[f] + 2]
       ELSE UNCHANGED << sid, registered >>
    ...

The invariant that breaks is AckedSurvive: whoever is serving holds every acknowledged record. FelixShardCrashKeepsId.cfg runs three brokers, one write, and the crash without RotateOnCrash. TLC's counterexample is the sequence above: the leader acknowledges a record on itself and one follower, the follower crashes and loses it, the leader's lease lapses, and placement promotes the follower on the leader's last report, whose identity still matches.

The fix

The fix has three parts: give each copy of the data an identity, treat a crash that may have lost writes as a new identity, and make every decision that trusts a copy check that identity first.

Name the data, not the node

Each data directory now gets a random 16-byte id, stored in <data dir>/storage-id. A clean restart keeps it, and a wiped or replaced directory gets a new one. The broker sends it when it registers with the control plane (#1269).

Followers also send it in the peer handshake, so at the start of every exchange the leader knows which copy it's talking to. If the id changed, the leader forgets everything it believed about that follower and starts its copy over from the beginning. Reports to the control plane say which id each follower was measured under, and placement only promotes a follower while that id matches the one it's registered with now (#1270, #1271).

Figure 3The id names the data, not the broker. A copy with a new id is a stranger: whatever the leader knew about the old one no longer applies.

Two smaller holes showed up along the way. Exchanges run concurrently, so a follower that failed fast could trigger a recount that still used a wiped follower's old position (#1274). And a leader can stay on a follower's old QUIC connection for a few seconds after that follower restarts, so the handshake now carries the follower's incarnation too, and placement trusts the one measured on the connection (#1282).

A crash is a new identity

None of that helps if a crash keeps the id. So an unclean stop under a relaxed fsync mode now looks like a lost directory (#1294). A small <data dir>/run-state file records “running, under this mode” at startup and “stopped cleanly” at the end of a drain that flushed every store. At the next start:

let (loaded, origin) = storage_identity::load_or_create(root, &mut fresh)?;
let last_run = read(root, loaded)?;
// A new id already tells peers to start over.
let rotate = origin == Origin::Loaded
    && match last_run {
        LastRun::Clean | LastRun::Crashed { relaxed: false, .. } => false,
        // Same boot and a synced page cache: the id stays.
        LastRun::Crashed { relaxed: true, boot: crashed_in } =>
            crashed_in.is_none() || crashed_in != boot || !synced_after_crash(root),
        LastRun::Unrecorded => repair_pending(),
    };
let id = if rotate {
    storage_identity::replace(root, fresh())?
} else {
    loaded
};

The new id is on disk before the broker registers or answers a handshake, so nobody sees the old id from the new process. A crash under OnCommit keeps the id, because everything it acknowledged was synced.

A process crash is different. When the broker is killed but the machine stays up, the kernel still has every write and flushes it after the process dies, so nothing is lost. Treating that like a power loss is expensive: under the default mode, killing two brokers of a three-copy shard would leave it waiting for an operator. So the broker also records the machine's boot id, and only takes a new identity when the machine itself went down (#1367).

Figure 4Under a relaxed fsync mode. A killed process leaves its writes with the kernel, which still flushes them. A machine that went down takes the page cache with it, so the broker comes back under a new id.

The leader side

Reviewing that change raised the obvious next question: what if the broker that crashes is the leader (#1295)?

A leader that crashed under Periodic and restarted before placement failed it over was still the assignment's leader. It reopened its old generation with the shorter log. B, holding W, would refuse the conflicting writes, but C, which never got W, would accept them. A and C are a majority, so new records could be acknowledged at W's offset.

FelixShardLeaderCrashKeepsGen.cfg shows it: the leader acknowledges a record on itself and a follower, crashes and loses it, and serves on its lease without it. The rotated identity alone doesn't stop this, because the leader isn't asking anyone whether it's caught up.

Figure 5The same crash on the leader, before and after the fix. A takes the shard back, at a new generation, only when every follower is behind it.

Now a broker that comes back under a new id gives up every replicated shard it led (#1305). The open is refused before anything is written, the copy's ballot is rewritten to name no leader so a later clean start can't lead it either, and the replication driver holds those shards until each open has decided. The crashed leader also refuses a successor's promotion fence from that copy, since its short log could otherwise stand in for B's. Placement sees the leader registered under a new id and promotes a caught-up follower without waiting for the lease. FelixShardLeaderCrashGivesUp.cfg passes.

That left a race (#1315). The crashed leader probes its followers and reports where each copy ends. Placement could act on that probe or on the pre-crash report, and the outcome depended on which arrived first. Now placement promotes any follower level with or ahead of the crashed leader, and names the crashed leader again at a new generation only when every follower is behind it. FelixShardLeaderCrashReclaim.cfg passes; FelixShardLeaderCrashReclaimBlind.cfg, which reclaims without measuring the followers, loses the record.

The fence

Everything so far was checked against the report-and-lease path. Felix also fences a promotion: the new leader asks a majority to take its generation and takes the furthest tail among them. A follower whose id rotated still counted toward that majority (#1335). With three replicas, a follower that lost W in a crash plus the new leader can make a majority without W.

To close that, the failover's assignment names the storage id each replica had in the report it was decided on, and the promoted leader counts a fence answer only from a connection whose handshake id matches. Anything else still takes the promise, so it refuses the old leader, but it doesn't count. The model covers that mode too, majority acknowledgement plus the fence, with a violating twin for each passing config (#1333, #1356).

Figure 6A fence answer counts only when the id on the connection matches the one in the report the failover was decided on.

What it costs

A broker whose machine crashes under a relaxed mode is copied again from scratch by every leader it follows. A process crash doesn't cost that.

There's also a case where a shard simply waits. If the leader dies and every follower it reported has come back under a new id, none of them matches the report, so the shard sits at NoCaughtUpReplica until the old leader returns. If it never does, an operator runs felixctl placement abandon, which re-places the shard on the furthest copy that's left, or restores from a backup with felix-broker restore-point. Before this work, the cluster would have picked a short copy on its own and said nothing.

And a crashed leader's shards fail over even if it comes back within seconds. They go back to it only when every follower is behind it.

If those costs don't suit you, on_commit avoids all of them: everything it acknowledges is on disk, so a crash keeps the id.

What we learned

Replication is only a durability argument if the cluster knows which copies are behind. “B is caught up” was a claim about a node, and the data that claim described had changed underneath it. Felix now tracks the data a node holds, not just the node.

Each fix found the next problem. Giving directories an identity led to the crash case, the crash case led to the leader case, and the leader case led to the fence. Reviewing a fix as carefully as the original change is what kept the chain going.

Figure 7Each fix, reviewed, knocked over the next problem.

A model that passes can still be checking nothing. One spec change left part of the model stuck, so configs that should have explored thousands of states stopped after five. The passing ones still passed. What caught it was a config that was supposed to fail and didn't.

Figure 8A violating twin is the same setup with one fix removed. When it passes too, the model isn't checking what you think.

It also matters which mode the model checks. The crash actions were first modelled only in the report-and-lease path, while Felix ships majority acknowledgement plus the fence. A review spotted that gap, and the same review found the fence bug in exactly the mode the model had skipped.

Finally, being too careful has a cost. Treating every process crash like a power loss kept data safe but left shards waiting for an operator. A process crash keeps the page cache. Telling the two apart with the boot id kept the safety without the stall.

What we'll do differently

Every change to replication or storage gets an adversarial review before it merges: a review whose only job is to break it. Findings become issues, not comments.

Every passing model configuration gets a violating twin: the same setup with one fix removed, which must fail. If the twin passes, the model isn't checking what we think it is.

New fault types are modelled in the mode Felix ships first, and the other modes after.

Tests that kill brokers run in the default fsync mode. A test that switches to on_commit to stay deterministic can hide exactly the behaviour users get by default, so when we need both, we keep both.

Trying it

The Docker Compose guide runs a control plane and a broker from the published images with docker compose up -d (or podman compose). The storage identity and run-state files are described in the durable storage docs, and the TLA+ configs named here are in docs/formal/.