Felix
All posts

The follower that forgot

On an idle shard nothing ships, so a leader never learned that a follower had lost its disk; this is how a storage identity per data directory fixed that, and why it changes only when a directory may hold less than its peers were told.

Gabriel Loewen 7 min read

Take a shard with five replicas and Quorum acknowledgement, and let it go quiet. Every record a client was promised sits on A, the leader, and on B and C. Then C loses its disk and comes back empty.

A kept reporting C as caught up. It did so on every pass, for as long as the shard stayed idle. If A then died, placement could promote C. C would fence with D and E, and its own empty log would count as a vote. The fence would complete without the records, and two faults on a five-copy shard would have lost data the client had been told was safe.

The fix is to stop trusting a follower's position and ask which copy of the data it describes.

What we found

A leader tracks each follower with a cursor. One field, confirmed, is the last position the follower answered holding. The report the leader sends to the control plane calls a follower caught up when confirmed reaches the position the leader reports against (#1266).

Only shipping lowers confirmed. The leader sends a batch, the follower compares it against its own log and answers where it really is. On an idle shard there is nothing to send, so the exchange ends UpToDate without asking the follower anything. A follower that restarted at the same generation didn't touch the cursor either.

So the cursor was a photograph. It was taken the last time anyone asked, and nothing made the leader look again.

The Felix cat, as the leader, takes a head count at a meeting. Its clipboard reads: 3 hold it, A B C. It says: C answered. Still three of us. Beside it sits cat B, and in C's seat is a cardboard cutout of a cat propped on a stand.C answered. Still three of us.3 hold itA B CABC
Figure 1The leader’s head count records the last answer. On an idle shard nothing asks again, so a cutout can sit in C’s seat and the count stays at three.

A leader's count of who holds a record is what lets it acknowledge under Quorum. It is also what a failover trusts when the leader is gone. Both were reading a number that nobody had checked since it was written.

A name for the data

Each broker with durable storage keeps a random 16-byte id in <data dir>/storage-id, written atomically and read before any store opens. It names the data, not the node. A restart keeps it. A wipe, a replaced disk or a fresh volume leaves no file, so the next start makes a new one. A file that doesn't decode is replaced too, because a new id only claims less.

The broker registers the id with the control plane and presents it in the replication handshake as a negotiated bit, so a peer that doesn't offer it sees the frames it always did (#1269, #1270).

At the start of each exchange the leader asks the connection which id the follower presented. If it differs from the one the cursor was learned under, the cursor starts over at the shard's base with nothing confirmed, and so do the follower's cursors on the group, dead-letter and counter logs. A follower that stopped cleanly and restarted presents the same id and keeps its place. If the lookup fails, the cursor is left alone and the shipping that follows meets the same failure.

The exchanges run concurrently and the leader recounts the quorum mark as each one lands, so a check made inside C's exchange doesn't protect a recount triggered by B's. The mark therefore counts a follower only once one of its requests in that pass has been answered over a connection whose id matches its cursor. Any other follower, a down one included, counts as holding nothing, and the majority that answers carries the mark (#1274).

Who may be promoted

The leader's report names the id each follower was counted under, and placement compares it with the id the follower is registered with (replication design).

Two papers side by side. Leader A's report says C is caught up, under storage id 7f3a. The control plane's registry says C is registered under a new id, c91e. A not-equal sign sits between them. The Felix cat reads three rules: the same id counts, a different id never counts, and no id counts only on a fresh report.A's reportC: caught upID7f3a…C registered asC: new diskIDc91e…≠same id: countsdifferent id: never countsno id: only a fresh reportA dead leader’s last report keepscounting, on a match only.
Figure 2A report names the id each follower was counted under, and placement checks it against the id the follower is registered with now.
  • Equal: the report describes the copy the follower still has. It counts while the report is believed.
  • Different: the follower lost its directory since. It never counts from that report, however fresh.
  • Missing on either side: a broker that predates ids. It counts only from a fresh report taken at its current incarnation, since a restart is the only sign it may have lost its log.

Reports expire after twice the node expiry timeout plus a heartbeat, since the leader keeps writing after it reports. A dead leader can't refresh its last report, though, so a slow control plane could let it expire and leave the shard unplaceable (#1250). So while the report's leader is still the assignment's leader, at the same node incarnation that made the report, and is marked down or left, the report's age is measured to that leader's last heartbeat instead of to now.

That holds only for a follower whose id matches, so one that lost its disk can't ride on a dead leader's report. A follower that merely restarted keeps its id and still counts for as long as that condition holds (#1271).

When the directory survives

A wipe is the easy case: the file is gone. The harder cases keep the directory and its id but leave it holding less than peers were told. Each rotates the id for its own reason.

The Felix cat asks: could this disk hold less than I told my peers? Below, six cases. A clean stop then restart keeps the storage id. A killed process keeps it only when the boot is known and the same and syncfs succeeds. A killed process with an unknown boot or a failed sync, a machine crash under periodic or none, a restore from before the last registration, and a wiped or replaced disk each get a new id.Could this disk hold lessthan I told my peers?clean stop, then restartkeepskilled; same known boot, syncfs okkeepskilled; boot unknown or syncfs failsnew idmachine crash under periodic or nonenew idrestored from before the last registrationnew iddisk wiped or replacednew id
Figure 3The id changes when a directory may hold less than its peers were told. A killed process keeps it only when the boot is known and unchanged and the filesystems sync.

A machine crash under periodic or none

Under these modes a record is acknowledged once the kernel has it, before it is synced, so a power loss can drop an acknowledged tail while the directory and its id survive. A start after an unclean stop in either mode takes a new id, unless the crashed run was in the boot still running and the filesystems sync. A process crash leaves the page cache with the kernel, which still writes it back, so nothing acknowledged is gone. Anything unknown rotates, and on_commit syncs before acknowledging, so its crash keeps the id. The mechanism is in Acknowledged, then forgotten (#1294, #1371).

A directory older than the node

A volume restored from a snapshot has a valid id, and the id matches what peers know. The directory inside it is older than what they counted. Nothing in the directory shows that, under any fsync mode.

The registrations can. The broker writes the node incarnation the control plane gave it at each registration to <data dir>/registration. At startup a cluster member with durable storage asks the control plane for its node's current incarnation before any store opens. If the control plane is ahead of the record, the node registered at least once that this directory never saw, and the id rotates (#1343).

A data directory with a paper note reading: data dir saw 4. Beside it a ledger reads: control plane registered it, 6. A less-than sign sits between them. The Felix cat, at the control plane, says: You're older than I am. A line underneath reads: Behind: new id. Equal, or ahead: keep it.You're older than I am.data dir saw4<control planeregistered it6Behind: new id. Equal, or ahead: keep it.
Figure 4A restored directory carries the registration number it last saw. A control plane that is ahead has registered the node since.

Only a control plane that is ahead counts. One that is behind was itself restored or forgot the node, which says nothing about this directory. A control plane that can't be reached holds startup: the broker opens nothing and announces nothing until it answers, and its /live endpoint stays up so a probe doesn't restart it.

Some restores stay invisible. A snapshot taken during the node's current registration records the incarnation the control plane still holds, so it looks like the live directory. For those, and for a broker with no cluster, the backup guide says to delete storage-id before starting. felix-broker restore-point does it for you, before it cuts any log.

What it costs

A rotation costs one copy started over per shard the broker follows, since its leaders compare from the shard's base. A false rotation is a spent copy. A false keep is lost data. Every rule above leans the same way.

A follower without an id, from an older build, is judged by the report's age alone: it counts only from a fresh report taken at its current incarnation, never from a dead leader's held one. If it restarts after its leader's last report and the leader then dies, the shard waits for the leader rather than guess.

What we learned

A cursor is a claim about the past. Without something that refreshes it, it is a guess, and an idle system is where nothing refreshes it. The claim has to be attached to what it describes.

The identity has to name the data and not the node. The node was fine, running and registered and answering. It was the thing it had counted that was gone.

Each rotation rule exists because a directory can hold less than it once did without changing: the sync that never happened, the snapshot that is older than the registration. Where the evidence is unclear, the id changes.

Trying it

The Docker Compose guide runs a control plane and a broker with docker compose up -d (or podman compose). The durable storage page covers the run-state record and the crash rules, and the backup and restore guide covers what to do when a data directory is put back by hand. docs/replication-design.md has the leader and placement side. The companion post, Acknowledged, then forgotten, covers the model checking behind the crash rules.

Try Felix

Write the compose file from the Docker Compose guide, then start a broker and its control plane. With Podman, use podman compose.

docker compose up -d
Felix on GitHub RSS feed More posts