Distributed Key-Value Store Failures: Quorum Loss, Recovery & Hot Keys

A key-value store fails in the places where it makes promises: when it says a write is durable, when it says one owner holds a key, when it says two of three replicas agree, and when it says a deleted value is gone. Thirty-six incidents, each walked from trigger through recovery, show what the reference design does at each of those promises and what it cannot do.

Every incident here is a hypothetical scenario for the fictional Meridian Profiles platform (tenants Atlas, Birch and Cedar; replica group members A, B and C; regions EU and US). None describes a real outage at a real company, and every number is a teaching assumption or derived arithmetic, not a measurement. The design being stressed is the one in Complete Design: partitioned, leader-based replication with a replicated commit log per partition, majority commit, single-key linearizable access in the home region, and asynchronous remote replicas. A leaderless alternative appears twice, labeled as such, because its failures are instructive and different.

Each incident carries the same ten elements, in a table at its end: trigger, timeline, visible symptom, root cause, detection, containment, recovery, prevention, what still holds, and the cost of the fix. The prose before the table does the real explaining and is arranged around whatever makes that failure interesting, whether that is arithmetic, an ordering of events or an argument about who is allowed to decide. Where the answer is not what you would guess (a 412 that means *you* won; a repair that restores deleted data; a backup that cannot be decrypted), the prose says so up front.

What the system is doing while it fails: five postures

The requirements for the reference design say that every failure should end in one of a small set of postures, never in false success. Available means requests succeed with the stated guarantee. Stale means requests succeed but a labeled read mode returns older data. Read-only or rejecting means the store refuses writes (503 UNAVAILABLE, 429 when throttled, WRONG_EPOCH for stale routing) because it cannot commit them safely. Unavailable means it cannot serve the operation at all, as when no majority exists. Unsafe appears only when an invariant was missing, and the incident says which one. A timeout is not a posture; it is an unknown outcome.

Vocabulary the incidents lean on

The incidents use a handful of terms freely, so here they are once, in the sense this page uses them. A write-ahead log (WAL) is an append-only file where a change is recorded before it is applied; after a crash the store replays it. `fsync` is the operating-system call that forces buffered file bytes onto the storage device, and a record counts as durable on one node only after it returns. A memtable is the in-memory sorted buffer of recent writes; it is flushed into an immutable sorted file called an SSTable, and compaction merges those files in the background. A partition is a slice of the keyspace; its replicas (here A, B and C) form a group with one leader that orders writes and followers that copy them, and a learner is a replica still catching up that does not yet vote. A quorum is a majority of the group (2 of 3), and an entry is committed once a quorum holds it durably.

Leadership is numbered: a term increases on every election, and messages from an older term are refused. Ownership of a partition is numbered separately by the map epoch. The replication protocol described is Raft-style, meaning the leader-and-majority design published as the Raft consensus algorithm, though the incidents do not depend on any particular implementation. Linearizable means every operation appears to take effect once, at a single instant between its start and its reply, so a read after an acknowledged write never sees older data. An idempotency key is a client-chosen identifier that lets the store recognize a retry and return the first outcome instead of applying twice. A tombstone is a versioned delete marker that stays until every replica has seen it. RPO (recovery point objective) is how much recent data a failover may lose, and RTO (recovery time objective) is how long recovery takes. Leaderless terms (siblings, read repair, hinted handoff, last-write-wins) are defined where the two alternative-design incidents use them.

Failure map: all 36 incidents

A write that reaches the leader can die in at least five different places before the client hears anything, and each place leaves a different truth on disk. Six incidents walk those places: the process dying before it logs, the log that was written but never flushed, the commit nobody was told about, the half-written record, and the two leader crashes that straddle quorum.

Two ideas keep these incidents apart. Durable means the record survives the failure being discussed, which for a single node is a completed fsync and for a replicated partition is a majority of replicas holding it durably. Acknowledged means the client was told so. A correct store only ever acknowledges after durable; it can never promise the reverse, because the reply can be lost after the commit. That asymmetry is why a timeout is always an *unknown outcome*, and why most of the fixes below are some form of retry with an idempotency key.

F01 — Process crash before the WAL append

Meridian's leader for partition P7 receives Put(atlas/user42/settings) for evt-024. The request has been parsed and validated, and the process is killed by the kernel's out-of-memory handler before it calls the append routine. Nothing was written, nothing was applied, nothing was acknowledged.

From the client's side this looks identical to far worse outcomes. It sent a request and the connection reset or timed out; it has no way to tell whether the server died before the log append, after it, or after the commit. The safe contract is the same in all three cases: treat it as unknown, reread or retry with the *same* idempotency key. Here the retry finds no record of the key and applies the write once, which is exactly right. The store's job is to make sure this cheap case and the expensive ones (F03, F18) are handled by one client rule rather than three.

F02 — Crash after the append but before the flush

This one depends entirely on a single line of the write path. The leader has appended the record to the log file, so the bytes sit in the operating system's page cache, and the machine loses power before the kernel writes them to the device. After restart the file ends one record earlier than the process believed. If the store acknowledged *after* fsync returned, nothing was promised for this record and the client retry (F01 logic) repairs it. If someone had configured the log for speed, acknowledging after write() and flushing on a timer, then evt-024 was acknowledged and has vanished.

Group commit is why the safe configuration is affordable: records arriving in a 1 ms window share one flush, so a node applying 6,250 writes/s flushes about 6.25 records at a time (assumed figures). The other trap is below the filesystem. A drive or controller with a volatile write cache that acknowledges flushes it has not performed can lose a record the store believed was durable; the guarantee is only as honest as the storage stack, so the operations answer is a hardware and filesystem checklist plus a power-pull test, not a hopeful reading of the config.

F03 — Crash after commit, before the response

Leader A appends evt-024, B acknowledges, the entry commits at v8, and A dies before its reply leaves the socket. The write is durable and applied. The client sees a timeout. Everything now depends on what the client does next, and there are three branches that differ sharply.

If it retries a plain Put carrying the same idempotency key, the new leader looks the key up in the replicated dedup table, finds the committed result and returns v8 again; nothing is applied twice. If it retries without a key, an overwrite Put of the same value is harmless but an increment or an append would apply twice. If it retries a CAS with expectedVersion=7, the answer is 412, because the record is already at v8. That 412 is the cruel one: it looks like a lost race, but the winner was the client itself. A client that gets 412 after an unknown outcome must read the record and compare it with what it tried to write before concluding anything.

F04 — Torn or corrupt WAL entry

A power cut lands in the middle of a 4 KiB append and the log ends with half a record. On restart, replay reads records one at a time, each carrying a length, a sequence number and a checksum. The last record's checksum fails, and the engine stops there, truncates the file to the previous good record and carries on. This is a tail tear, and it is safe: a record is acknowledged only after it was flushed whole, so a half-written one was never promised to anyone.

The same checksum failure in the *middle* of the log is a different animal. Records after it may be perfectly valid, but you cannot tell whether the corrupted one was acknowledged, and skipping it silently would apply later records on top of a gap. The rule is stop, do not skip: mark the replica as damaged, take it out of the voting set until it is rebuilt, and repair it from a healthy peer. In a replicated group that is routine (F09). On a single copy, the honest answer is that the engine cannot continue without an operator's decision.

F17 — Leader crashes before quorum commit

Leader A appends log entry 42 for evt-024 at term 4 and sends it to B and C. A crashes before it hears back from either. What happened to the entry depends on how far it travelled. If B received it, B holds entry 42 and C may not. Nobody counted a majority, so the entry is uncommitted: it may survive or vanish, and either outcome is allowed because the client was never told.

The election decides which. A new leader must have a log at least as up to date as a majority of voters. If B, which holds entry 42, wins, it will carry the entry forward and commit it once it commits something in its own term (a no-op entry is the usual trigger), so a write the client saw time out may appear moments later. If C, which lacks it, wins, entry 42 is overwritten when B syncs. A client that polls after a timeout can see the write as absent and then present; that is legal, and it is the reason the reference design calls the post-timeout state unknown rather than failed.

F18 — Leader crashes after commit, new leader must honor it

Here the commit was real: A and B hold entry 42, and A dies before replying. C, still behind at entry 41, cannot become leader, because B would deny it a vote for having a shorter log. Only B (or A on return) can win, and whoever wins holds every committed entry. That rule, that an elected leader contains everything already committed, is the heart of why majority commit survives leader changes.

The sharper edge is the *read* that follows. Once B is leader, it may not know the true commit index until it has committed something in its own term. A linearizable read that B answered from its local state too early could omit the entry that A had already acknowledged to some other client. So the new leader does two things first: commits a no-op in its term, then serves linearizable reads only after confirming it still holds leadership (a read-index round to a majority, or a valid lease). During those few milliseconds, linearizable reads wait or get 503; follower-stale reads, if the caller chose them, stay available and are marked as stale.

Disks fail in boring ways: they fill up, they flip bits, and they fall behind on housekeeping. The incidents here are the quiet ones, where nothing crashes and the service degrades because the storage engine ran out of room, trust or time.

A log-structured engine makes these failures interact. Compaction needs free space to make free space; a slow follower forces the leader to keep log it would otherwise discard; and a checksum mismatch is only useful if the store refuses to return the corrupt bytes. The planning numbers in this module keep volumes at or below 60% full (an assumed target) precisely because the engine's own housekeeping needs the headroom.

F05 — Disk full on the leader

Atlas runs a bulk import, and the volume holding partition P7's leader reaches 100%. The next WAL append fails with an out-of-space error. The store has one honest option: refuse the write. Acknowledging into memory and hoping would be a silent durability failure, so the leader returns 503 and, depending on policy, steps down so that a follower with free space can lead.

The trap is that the remedies need space too. Compaction rewrites SSTables into new files before deleting the old ones, so it cannot run on a full disk; a delete writes a tombstone, which is more data; and snapshots, used to catch up followers, need scratch space. A volume that is 100% full is therefore close to wedged. The practical defense is thresholds well before the wall: alert at an assumed 70%, throttle ingest at an assumed 80%, and keep a reserved emergency file or reserved blocks that only the recovery path may use. Hand-deleting WAL segments to make room is the one move that converts a capacity incident into data loss.

F06 — Disk full on a follower

Follower C's volume fills, perhaps because it also hosts a different partition's large replica. C can no longer append, so it falls behind and eventually stops acknowledging. A and B, a majority of three, keep committing; clients notice nothing. That is the dangerous part. The partition is now one failure from losing write availability, and the dashboards that show only client error rates stay green.

A secondary effect makes it worse. The leader keeps the log tail that C has not confirmed so that C can catch up from it; with C stalled, the leader's log retention grows, and now the leader's disk is under pressure for a failure that is not its own. Policy has to pick a point where the leader stops holding the log for C and instead plans a snapshot-based rebuild once C has space, accepting that C will be restored from a snapshot rather than a log tail.

F07 — SSTable checksum corruption

A read for birch/user17/settings reaches a data block in an SSTable whose stored checksum no longer matches its content, a bit flip on the medium that happened weeks ago. Without checksums the engine would hand back whatever the bytes decode to, possibly a plausible but wrong value. With them, the read fails for that key on that replica, the error is logged and the request is retried on another replica.

The deeper risk is compaction. If the engine merges the corrupt table into a new one without verifying, it produces a fresh file with a valid checksum over corrupt data, laundering the damage. So reads and compaction both verify block checksums, and a background scrub reads cold files before they are needed. When a bad block is found, the replica marks the table suspect, and the repair path fetches the affected key range from a replica at the same commit point, rewrites it, and records the repair. If the corrupt copy is the leader's, linearizable reads for those keys return 503 or move with leadership until repaired.

F08 — Compaction backlog and the P99 spike

Compaction is the engine's debt payment. Writes land in memtables, flush into small immutable SSTables, and compaction merges them in the background to keep lookups cheap. When the write rate stays above what compaction can absorb, the tables pile up. Reads now probe more files, so tail latency climbs first, while the average hides it. Past a configured threshold the engine slows or stalls writes to let compaction catch up, which is when a P99 incident becomes a write-rejection incident.

Bloom filters keep the reads tolerable for a while. At 10 bits per key and seven hash functions the false-positive rate is about 0.82% (classic arithmetic, not a vendor figure), so a lookup for an absent key across 5 tables expects about 0.041 needless disk reads, and across 40 tables about 0.33. Present keys still pay for every table that might hold a newer version. That is read amplification, and it is why the metric to watch is not CPU but pending compaction bytes and table count per level.

Repair and restore are the paths you use after something else went wrong, which makes them the paths most likely to be untested, throttle-less and badly timed. Four incidents show what happens when recovery itself is the hazard: a corrupt snapshot, a restore that undoes deletes, a rebuild that starves foreground traffic, and a backup nobody can decrypt.

F09 — Snapshot corruption and repair from another replica

Follower C is far enough behind that the leader no longer has the log entries it needs, so it sends a snapshot: the state machine at a known log index, streamed in chunks. C writes the chunks to disk and, at the end, verifies a whole-snapshot hash. The hash does not match; a chunk was damaged on disk or in transit. C refuses to install it and stays a non-voting learner.

The correct response is almost boring: discard, and ask again, preferably from a different source. Replica B holds the same committed state, so the control plane retargets the transfer to B and the leader is spared another heavy read. The incident turns nasty only if the system installs first and verifies later, or if the same damaged snapshot file is the only copy. Snapshots carry their last-included index and term so the replica resumes the log from exactly the right point, and per-chunk checksums let a retry resend only the broken chunk.

F27 — Failed restore reintroduces deleted secrets

On Monday a Birch administrator deletes birch/secrets/api-token. On Tuesday a bad migration corrupts a tenant's records and operators restore the partition from Sunday's backup. The backup holds the token, so the restore puts it back, live, with an old version number, and nothing in the store objects: from its point of view this is just a recovered record. The tombstone that recorded the delete was written after the backup.

Backup restore is a time machine for *everything*, including things people wanted gone. The defences are procedural and structural. Restore into a quarantine copy, then replay the archived write-ahead log up to the desired point in time so the delete is applied (point-in-time recovery). Keep a deletion ledger outside the restored data (tenant, key, deleted-at) and re-apply it before the restored partition rejoins. For secrets, delete the encryption key for the record, so restored ciphertext is useless. And remember that physical removal from backups is bounded by retention: with an assumed 35-day backup policy, a deleted value can persist in old backups for up to 35 days, which must be stated rather than hidden.

F28 — Replica repair overwhelmed by foreground traffic

Node 41 dies and its 32 partition replicas, about 64 GB of replicated data (the worksheet's assumed per-node figure), must be rebuilt elsewhere. The rebuild streams from the surviving replicas, which are also serving the day's peak. At the planning peak each node already runs at about 73% of an assumed node budget, so adding a rebuild stream on the same nodes pushes them past it. Foreground P99 rises just as the cluster is most exposed, running 2-of-3 on 32 partitions.

Both extremes are wrong. Unthrottled repair finishes quickly and takes down foreground latency; heavily throttled repair keeps latency flat and extends the window in which a second failure would cost quorum. The arithmetic is simple enough to decide on: at an assumed 50 MB/s cap, 64 GB takes about 21 minutes, at 200 MB/s about 5. The operations choice is a cap that foreground P99 can tolerate, spread across many source nodes rather than concentrated on two, raised overnight and lowered at peak, and visible on the same dashboard as under-replicated partitions.

F35 — Backup encryption key inaccessible during restore

The nightly backups are encrypted with a key held in the organization's key-management service, which is the right design: a stolen backup is useless without the key. During an incident, a restore begins and fails at the first decrypt. The key's access policy was tightened last month and the restore role was not in it; or the key was scheduled for deletion; or the key service is itself in the affected region. Whatever the cause, the backups exist and cannot be read, which in practice means there are no backups.

This failure is invisible until the day it matters, because backup jobs write encrypted files successfully and a *restore* is the only operation that proves the key is usable. So the control is a restore drill that exercises the production decryption path on a schedule, in addition to checksums of the backups themselves. Other controls: separate duties so that deleting a key needs a second approver and a waiting period; keep old key versions after rotation for the full retention window; and hold an escrowed recovery path with documented access that works when the primary key service is unavailable.

Every key must resolve to exactly one owner at a time, and every incident here is a way that sentence stops being true: the mapping changes the wrong way, a move is interrupted, a client acts on yesterday's map, a key is built without its tenant, or the service that publishes the map goes dark.

The mechanism that keeps ownership honest is small. Keys hash to a fixed number of logical partitions (1,024 in the planning worksheet); a partition map says which replica group owns each partition and carries an epoch that increases on every ownership change; requests carry the epoch the client believes in; and the owner rejects a request whose epoch is stale. Most of what follows is what happens when one of those four pieces is missing.

F12 — New node added with unsafe modulo remapping

The cluster has three nodes and the router assigns a key to hash(key) mod 3. Capacity is short, so an operator adds a fourth node and changes the router to mod 4. For a uniformly distributed hash a key stays on its node only if its residue under 3 equals its residue under 4, which holds for 3 of every 12 residues. A quarter of the keys stay and 75% move, which with 2.048 TB of logical data means about 1.536 TB must migrate (4.608 TB counting three copies).

The damage comes before the migration finishes. The router now sends Get(atlas/user42/settings) to a node that has never seen it. That node answers 404, which is a *false* not-found for a record that exists. Writes land on the new owner too, so for the moved keys there are now two divergent copies. The recovery is to revert the router to the old mapping while the copies are still unmerged and to reconcile any writes made in between by version. The durable fix is not a cleverer modulus but a different shape: hash keys to fixed virtual partitions, and move whole partitions between nodes. Adding a fourth node to three then moves only about 25%, all of it onto the new node, 0.512 TB logical, and moves them with the epoch protocol of F14 and F15.

F13 — Rebalance interrupted halfway through

Partition P7 is being moved from node 2 to the new node 4. The copy has finished, the controller has fenced the source (it stopped accepting writes), and then the controller process crashes before it publishes the new epoch. The partition now has an owner that will not accept writes and a destination that is not yet the owner. If nothing intervenes, clients receive 503 for P7 indefinitely.

Two design choices decide how bad this is. First, the migration must be a recorded, resumable state machine (snapshot, catch-up, verify, fence, flip, retire) stored with the control plane, so a restarted controller reads 'P7 is fenced, destination verified' and finishes the flip rather than starting over. Second, the fence must carry a deadline: if the flip is not committed in, say, a few seconds, the source un-fences itself under its old epoch and the move is abandoned. A fence without a timeout turns a controller crash into an outage; a flip without a fence turns it into F15. One more detail keeps the timeout itself safe: abandoning the move and committing the flip must be mutually exclusive transitions recorded in the control plane's replicated state, so a slow controller cannot flip ownership after the source has already un-fenced and resumed writes. The partially copied data on node 4 is simply unused garbage until the flip, and is cleaned up if the move is canceled.

F14 — Stale partition-map epoch sends writes to the old owner

A client library caches the partition map at epoch 17. During a rebalance, P7 moves and the map advances to epoch 18. The client sends Put(atlas/user42/settings) for evt-024 to the old owner with epoch=17. The old owner knows it is no longer the owner of P7 at epoch 18, so it refuses: a retryable WRONG_EPOCH (a 421-style redirect) carrying the new owner and epoch. The client refreshes its map and resends the same request with the same idempotency key.

What the epoch buys you is clear if you imagine its absence. Without the check, the old owner, still holding a copy of P7, accepts the write, acknowledges it, and the write lands on a replica group that the rest of the cluster has stopped consulting. It is lost the moment the old replica is retired. The cost of the right design is one extra hop for stale clients, paid only after moves, and a small bit of discipline in the client: refresh on WRONG_EPOCH, do not hammer the old owner, and bound the redirect loop so that a map-service outage does not become a spin (F29).

F15 — Split or migration race loses an update when fencing is absent

Take the migration from F13 and remove the fence. The destination takes a snapshot at log index 9,000 and begins applying later entries. The source is still the owner and accepts a write, Put(atlas/user42/settings) as index 9,001, and acknowledges it. The controller then flips ownership, having decided the destination is 'close enough'. The destination has entries through 9,000 only. The acknowledged write at 9,001 lives on a source that is about to be retired, and reads at the new owner return the older value. The lost update was acknowledged, durable and then orphaned.

The ordering that prevents it is strict: fence the source so it accepts no new writes, let the destination apply through the source's *final* index, confirm the destination's applied index equals the source's last index, only then commit the epoch change. In this example the fence lasts until the destination reports index 9,001 applied; the write in flight at the fence is either included in that index or rejected with a retryable error. An invariant worth testing directly: run a continuous writer with a checker during rebalances in a staging cluster and assert that every acknowledged write is readable afterwards.

F16 — A key replicated into the wrong namespace

A new code path in the settings service builds the key user42/settings instead of atlas/user42/settings; the tenant prefix was dropped. The store accepts it: a key is just bytes, and the hash puts it wherever it lands. Birch has its own user42 and the same code path now writes user42/settings for both. The two tenants' records overwrite each other, and a read for Birch's user returns Atlas's preferences.

No storage fault produced this; the store did exactly what it was asked. The failure is that tenant identity was an argument the caller could forget. The reference design applies the tenant namespace on the server side, derived from the verified credential, so that a request cannot name a key outside its tenant, and rejects keys that do not begin with the tenant's prefix. Detection comes from the same place: a canary tenant that tries to read keys it does not own should always get 404, and a periodic scan checks that every stored key begins with a known tenant prefix. Recovering the overwritten records means finding them in the log or in backups by the key and version history, and restoring each to its tenant.

F29 — Control-plane or map-service outage: warm versus cold clients

The partition map is published by a small control-plane service. Raft groups elect leaders by themselves, and the data plane does not need the control plane to serve reads and writes. So when the control plane goes dark, the first thing the on-call sees is that most traffic keeps working. The clients that were already running hold a cached map and keep sending to the right owners. The trouble sits at the edges: a freshly deployed pod has no cached map and cannot bootstrap; a partition that moves, which now cannot happen anyway, would leave warm clients with a map that is never refreshed.

Practical hardening is cheap. Every storage node can serve the current map it has, so a cold client needs only a list of seed nodes, not the control plane. Caches are kept past their usual refresh interval during a control-plane outage rather than being dropped. Rebalancing, splits and node adds are frozen by policy while the control plane is down, since they need a coordinator, and automated failover of whole regions (F31) must not run without it. The outage is then boring: warm service, no topology changes, a degraded deploy path.

Averages hide the failures in a partitioned store. A cluster that is comfortable on average can be on fire at one leader, one tenant or one oversized request, and in each case the fix is to put a limit or a fan-out in front of the thing that is concentrated.

F10 — A hot key saturates one partition leader

Meridian's tenants all read one record, atlas/feature=checkout_policy, on every page load. Use a simplified 100-partition illustration (distinct from the 1,024-partition fleet plan): an average of 200,000 reads/s spread over 100 partitions is 2,000/s per partition, and the dashboard looks calm. This one key takes 60,000 reads/s, 30× the average partition and 30% of fleet average read traffic, all landing on whichever replicas serve it. If linearizable reads must go through the leader and one replica handles an assumed 25,000 point reads/s, that leader is at 240% of its budget and queues, and every other key on the partition inherits the queue.

Fan-out is available for reads and not for writes. Serving the key from three replicas with follower-stale reads, explicitly labeled and bounded, gives 3 × 25,000 = 75,000 reads/s of capacity, so 60,000 runs at 80%, workable but thin. A short-TTL client or edge cache, explicitly optional and with the staleness it implies, removes most of the traffic entirely; request coalescing collapses simultaneous identical reads to one. What none of this does is fix writes: all updates to the one key still serialize through one leader, and salting the key into many copies is only legitimate for read-only data. The lesson for capacity planning is that per-key peak, not partition average, sets the limit.

F11 — A hot tenant saturates its neighbors

Atlas starts a bulk import of tenant configuration, 15,000 writes/s sustained, while Birch and Cedar run ordinary traffic. The three tenants share leaders and compaction budgets. Atlas's burst fills the write queue of partitions it shares, commit latency for everyone rises, and Cedar's single settings update now takes 600 ms instead of 20. Nothing is broken; one tenant simply consumed the shared resource.

The response has two layers. At admission, per-tenant quotas return 429 to the tenant that exceeds its share, with a retry hint, before the write ever reaches the log. Inside the store, weighted fair queues keep one tenant's backlog from monopolising a partition's commit path, and compaction and repair budgets are accounted per tenant where the engine allows it. For a tenant that is permanently large, placement helps: move Atlas's partitions to dedicated nodes so its spikes cannot pass through Birch's leaders. The 429 versus 503 distinction matters here: 429 tells the client it exceeded *its* quota, while 503 says the service cannot take the request, and clients should react to them differently. See rate limiting and bulkheads.

F33 — A multi-tenant scan bypasses authorization via a caller-supplied tenant ID

Scan by prefix is a product feature only on range-partitioned data, and Meridian's scan endpoint takes a tenant field in the request body: Scan(tenant=birch, prefix=user). The authorization check verifies the caller's token is valid, and then trusts the body to say whose data to read. An Atlas credential sends tenant=birch and receives Birch's records.

The bug is one of identity source. A tenant must come from the *verified credential*, never from a field the caller controls, and then be applied at every layer: the scan's start and end keys are clamped to the tenant's prefix, an empty or wildcard prefix is rejected, and storage, logs and admin operations all work in that namespace. Detection is an audit comparison: the tenant in the token against the tenant touched by the operation, alerted on any mismatch. Containment is to disable or restrict the endpoint immediately, then use the access logs to scope what was read. A fix that merely validates the body against the token still leaves the unnecessary field in the API; remove it.

F34 — Key-size abuse or oversized writes exhaust memory and disk

The teaching limits are a key of at most 1 KiB and a value of at most 256 KiB, against an average record of about 1 KiB. A buggy client starts writing 256 KiB blobs at 1,000 writes/s. That is 256,000 KiB/s (about 250 MiB/s) of client ingest compared with about 1,000 KiB/s (under 1 MiB/s) for average records: 256× the bytes per write, before multiplying by three replicas and by compaction's rewrite factor. Memtables fill in seconds, flushes produce huge SSTables, and the Bloom filters and indexes grow with them. The limits only help if they are enforced before the log.

Enforcement lives at the earliest point that can see the size: the API edge returns 413 for oversized values and a validation error for keys above 1 KiB, before anything is appended, replicated or logged. Below that, a per-tenant byte-rate quota catches the case of many *valid* but large writes. Large objects that genuinely belong somewhere should go to an object store with the key-value record holding a pointer. A store that lets one big request in has accepted a replicated, compacted, backed-up copy of it, which is expensive to remove.

Leaders, terms and quorums are what turn replication into a promise instead of a hope. These four incidents are the cases that test that promise: a leader that cannot reach a majority, a leader that does not know it has been replaced, a follower that answers from the past, and two writers who both believe they are updating the same version.

F19 — A minority network partition attempts to accept writes

A network fault separates leader A from followers B and C. Clients on A's side can still reach A. A can append entries locally but cannot get a second acknowledgement, so nothing commits: its writes time out or return 503 UNAVAILABLE, never success. On the other side B and C time out waiting for heartbeats, hold an election, and B becomes leader at term 4 with C's vote. Two out of three is a majority; the majority side keeps serving.

The partition shows the cost of choosing consistency during a split. Clients stuck with A cannot write and cannot do linearizable reads either, because A can no longer confirm it is still the leader. They can still make follower-stale reads if the caller chose that mode, clearly labeled stale. Nothing here violates the reference design: A is unavailable for those operations by design. When the partition heals, A learns about term 4, steps down, and discards its uncommitted entries (which were never acknowledged), and clients redirected to B resume.

F20 — A stale leader fails to be fenced

Leader A, term 3, stalls for 12 seconds in a long pause (a VM freeze, say). B and C elect B at term 4. When A wakes, it has no idea any of this happened: its clock says it is leader, and its lease, if it relies on one, may *look* valid. The write path is protected by terms: any append A sends to B or C carries term 3 and is rejected, because they have seen term 4. Reads are where it can bite. If A serves a linearizable read from local state under a lease it believes is valid, it may return a value that B has since overwritten.

There are two defences and a system should use at least one. The read-index approach has the leader confirm its leadership with a majority before each linearizable read batch, which costs a round trip but trusts no clock. The lease approach lets the leader answer locally while its lease is valid, but the lease must be shorter than the election timeout with a margin for clock drift, and a paused process must re-check on wake. For work *outside* the store, such as another system acting on a lease grant, the term is passed along as a fencing token so the downstream resource rejects the older holder. This incident is the reason that 'I think I am leader' is never sufficient on its own.

F21 — A follower serves a stale read during lag

Follower C is 2 seconds behind after a compaction pause. A user in Meridian's admin console saves new settings (v8 for atlas/user42/settings), the page reloads, and the read goes to C under the follower-stale mode. The response shows v7. From the user's side, the save did not work, though it committed on a majority.

Nothing is wrong, provided the API told the truth. A follower-stale read advertises exactly this trade: lower latency and offloaded leaders in exchange for being behind by some bounded or unbounded lag. The product problem is the user who just wrote. read-your-writes fixes it with a version floor: the write response returns committedVersion=8 (the session token), the client sends minVersion=8 on the read, and a follower that has not applied v8 forwards to the leader or waits briefly. Dashboards should publish replication lag per follower, and the router should drop followers beyond a staleness bound from the read pool.

F22 — Concurrent updates and the lost-update trap

Two admin tools edit the same settings record. Each does the obvious thing: Get, change one field in the client, Put. Tool 1 reads v7 and sets theme=dark; Tool 2 reads v7 and sets language=fr; each writes the whole record. Tool 2's write lands second and erases the theme change: a lost update, with both writes acknowledged. The store did nothing wrong, since a plain Put is an overwrite. The check-then-put lived in the application, where the check and the put are two separate operations with a gap.

The cure is a conditional write inside the replicated state machine: Put(expectedVersion=7) is evaluated by the leader at the position in the log where it is applied, so exactly one of the two writes sees version 7 and the other sees 8 and gets 412 Precondition Failed. The loser rereads, merges and retries (the worked timeline later shows the exact steps). Two cautions: CAS on a hot key can turn into a retry storm, so retries need jitter and a limit, and a conditional write is only as strong as the replication underneath it: in a leaderless design the same call needs a different explanation (F23).

These four incidents belong to the *alternative* leaderless design and to the clocks that every design leans on. They are here because the usual claims made for tunable quorums, that overlap gives consistency and that timestamps order writes, are exactly the claims that fail.

F23 — Leaderless divergent siblings and conflict resolution

In the leaderless alternative with N=3, W=2, R=2, two clients update atlas/user42/settings at the same time through different coordinators. Coordinator X gets acks from replicas A and B for a write that sets theme; coordinator Y gets acks from B and C for a write that sets language. Both met W=2, both succeeded, and the replicas now hold different values at the same logical position. Neither write knew about the other: they are concurrent, not ordered.

A later read with R=2 sees both versions and has to decide. With version vectors (or vector clocks) the store can tell the writes were concurrent and returns both as siblings, leaving the merge to the application: here, a field-wise merge that keeps theme and language. With last-write-wins, the store silently keeps the one with the later timestamp and discards the other, a lost update that no error reports (see F26 for why the timestamp may not be trustworthy). Siblings need a merge function that is correct for the data (a union for sets, a field merge for settings, and sometimes no good answer), and read repair or anti-entropy then writes the merged result back so siblings do not accumulate.

F24 — The quorum-overlap claim fails under sloppy replacements

N=3, R=2, W=2 gives R+W=4, greater than 3, and the textbook intuition is that any read quorum overlaps any write quorum. It is only an intuition, and a sloppy quorum breaks it. The preference list for a key is A, B, C. C is unreachable. To keep accepting writes, the coordinator uses stand-in node D, outside the preference list, for the third copy, and stores a hint for C. A write is acknowledged with acks from A and D, meeting W=2.

Now C returns before D's hint is delivered, and a read arrives that contacts B and C. Neither holds the new value: A and D do. R+W>N still holds on paper and the read returns the old value, with no error and no sibling. Hinted handoff is best-effort repair: Cassandra's documentation states hints do not guarantee eventual consistency the way anti-entropy repair does, and hints are only stored for a limited window (a max_hint_window default of 3 hours in the current Apache Cassandra docs and sample configuration; check your version). Cassandra counts a hint toward a write only at consistency level ANY, so the sloppy-quorum behavior in this incident is the original Dynamo design rather than what Cassandra does at its ordinary quorum levels. The correct statement is narrow. With *strict* quorums, overlap guarantees that a read sees the latest write *that has completed*, and even that is not linearizability, because of concurrent writes, failed partial writes, clock skew and membership changes.

F25 — A delayed tombstone resurrects an older value

A delete in a replicated store is a write: it records a tombstone with a newer version, and the old value is dropped later during compaction. Take the key atlas/user42/legacy-flag with three replicas. A deletes it and the tombstone is acknowledged by A and C; B was down and missed it, still holding the value. The retention period for tombstones, an assumed 10 days as in Cassandra's documented default gc_grace_seconds of 864,000 s, expires, compaction drops the tombstone on A and C, and then B, which has been offline for 11 days, comes back with the old value.

With the tombstones gone, A and C have no evidence of the delete, so repair compares B's value with their absence and concludes that A and C are *missing* a record. The deleted value is copied back to them: a zombie. The rule that prevents it is that tombstone retention must be longer than the longest time any replica can be offline or unrepaired before it is repaired, and a replica beyond that horizon must be wiped and rebuilt, not rejoined. In a log-replicated reference design the same hazard returns whenever a replica is restored from an old snapshot or backup past the retention horizon, so it holds there too.

F26 — Clock skew alters last-write-wins and TTL results

The US client library timestamps its own writes using the machine clock, which is running 90 seconds ahead. In a last-write-wins model, the US client's write at 12:00:00 (real time) carries 12:01:30. An EU client writes a legitimate update at 12:00:40; its timestamp is lower than the US one, so the store keeps the older, US write. The newer write was acknowledged and then lost, and no one is told.

TTL has the same weakness. If expiry is decided by the node's own clock, a fast node expires records early and a slow one serves them late, by as much as the skew. The reference design avoids both by not letting caller or node clocks order anything: versions come from the leader's replicated log, and a TTL is stored as an expiry timestamp assigned at commit and evaluated against a bounded clock, with expiry applied by replicated tombstone rather than each replica deciding alone. Where cross-cluster last-write-wins is used by a product, it should say whose time: Google's Bigtable documentation, for instance, describes two writes to the exact same cell (same row, column and timestamp) sent to different clusters as resolved by a deterministic last-write-wins rule based on server-side time, which is still a decision to discard one write, just a reproducible one.

Across regions, the speed of light and the legal system both show up as failure modes. The reference design keeps a home-region leader and ships its log to a remote region asynchronously, so a regional disaster raises questions the single-region incidents never had to ask: what was lost, who may take over, and where the data is allowed to live.

The context for all four: EU is the home region, US holds an asynchronous replica, and replication lag is assumed to be 300 ms. Remote reads are eventually consistent unless routed to the home region. Asynchronous cross-region replication does not give global strong consistency, and nothing below should be read as claiming it does. Each recovery number is an illustrative example, not a promise.

F30 — Cross-region replication lag after an abrupt disaster

EU loses power at once, and the US replica, 300 ms behind, holds atlas/user42/settings at v10 while EU had acknowledged v11. Assume EU takes 12,000 writes/s (30% of the 40,000 average, an illustrative share). A 300 ms lag means up to 12,000 × 0.3 = 3,600 acknowledged-but-unreplicated writes at risk at the instant of failure. That figure is exposure, not a measured loss: it depends on how much of the lag window actually held unreplicated data.

Promoting US is a business decision with an engineering price: those acknowledged writes disappear from the live system, the version counter on the US side continues from v10, and users who saw v11 in EU now see v10. The honest RPO statement is lag-dependent and non-zero, and the response is a procedure rather than a reflex: decide to promote, record the last log position US applied, publish the lost-window boundary to tenants, and when EU's storage returns, extract the unreplicated tail from EU's log and offer it for manual or tenant-specific reconciliation, because it conflicts with what US accepted in the meantime. The worked timeline below walks the same event step by step.

F31 — Incorrect regional failover creates split-brain

An automated failover script promotes US when its health check cannot reach EU for 60 seconds. EU is not down. The path between the monitoring system and EU failed, and EU's leaders keep serving local traffic. Now US also accepts writes. atlas/user42/settings receives v11 in EU and a different v11 in US, concurrently, with each side's clients entirely satisfied.

Failover must be a decision with proof, not a reaction to silence. The safeguards: a region's right to lead is a lease or ownership epoch granted by an authority that both sides respect; EU's leaders step down when their lease expires without renewal, and US may only take over *after* the previous lease has provably expired or EU has been fenced; failover is approved by more than one signal (multiple vantage points, a human for region-scale moves). Once split-brain occurs, the only recovery is reconciliation: pick the surviving history, then expose the other side's writes as conflicts for owners to resolve. There is no automatic merge that is correct for arbitrary data.

F32 — Region-residency policy blocks an otherwise convenient failover

Cedar's contract requires its records to stay in the EU. The US replica therefore does not hold Cedar's records, or holds only what policy permits. When EU fails, the platform *could* technically restore Cedar's data into US capacity from a backup copy and keep serving. It must not. The failover plan classifies tenants by residency, and for Cedar the correct state is unavailable until an EU-resident capacity returns.

This turns a purely technical decision into a product one, and it needs to be written down before the incident. Options that stay inside the rule: a second EU region or a second EU zone group so that EU-resident tenants have an in-jurisdiction failover target, accepting the cost; or an explicit contractual availability level that tolerates downtime during a regional disaster. Tenants without the restriction (Atlas, in this fiction) may use US failover with the RPO caveats of F30. The failure to avoid is silent: an operator under pressure restoring EU data into the US because it works. The restore tooling should refuse to place restricted tenants' data outside their allowed regions.

F36 — Regional write-read mismatch and a read-your-writes violation

A user in Frankfurt saves a setting in EU (v11) and the next request is routed by a global load balancer to the US region because of a transient health blip. The US replica is 300 ms behind, and within that interval the read returns v10. For the user it is a save that did not stick. A second attempt on the same record may even produce a conflict, because the client's cached version is now confusing.

The contract for this has to be explicit: remote reads are eventual unless they are routed to the home region. The fixes are a session token or version floor (the write returns v11; the next read sends minVersion=11; a US replica that has not applied it forwards to EU or waits a bounded time), affinity routing so a session sticks to its home region, or choosing linearizable reads for the flows where it matters. Even then, be careful with promises: Bigtable's documentation, for example, notes that sending a workload's reads and writes to a single cluster gives read-your-writes in a replicated instance, while row-affinity routing across clusters raises the rate of read-your-writes without guaranteeing it (checked against its routing documentation). The lesson is to specify which of those you offer, not to imply it.

Five sequences that are worth following step by step, because the order of events is the whole story: two writers on one version, a replica group losing members, a delete that comes back, a region disappearing, and one key drowning a leader.

These timelines reuse incidents above (F22, F17–F20, F25, F30, F10) but slow them down to individual events. Log indexes, versions and timings are hypothetical teaching values.

Timeline 1 — Two writers on version 7

Writer W1 and Writer W2 both read atlas/user42/settings at v7 and both want to change it. Each sends Put(expectedVersion=7) at nearly the same moment, so the two requests race to the leader. The comparison runs on the leader while the entry is applied, not on the client, which is what makes the outcome unambiguous.

Two details deserve attention. Entry 413 is still *in the log* and commits, but applying it does nothing; the failure is a deterministic outcome of the state machine, identical on every replica. And if W1's reply is lost (F03), W1 retrying CAS(7) would also get 412: the correct behavior is to reread and see its own value at v8.

Timeline 2 — RF=3 with A leader, B follower, C lagging

Replication factor 3 describes how many copies exist; it says nothing about who may decide. Here A leads term 4, B is in sync, and C trails: it has applied entries only up to 41. Majority is 2 of 3, so commitment needs A plus one other.

Timeline 3 — Delete resurrection

This is F25 as a sequence. The record is atlas/user42/legacy-flag, retained tombstones last 10 days (assumed, as in a documented Cassandra default), and replica B is offline for the delete. The design question is not *whether* the tombstone expires but whether it expires before every replica has seen it.

Timeline 4 — EU region loss with the US replica 300 ms behind

EU is the home region. US applies the EU log 300 ms late. The incident is the abrupt loss of EU at T=0, and the decisions are about what to claim.

Timeline 5 — The hot partition

A simplified 100-partition illustration: 200,000 reads/s average, so 2,000/s per partition on average. One key, atlas/feature=checkout_policy, takes 60,000 reads/s. Assume 25,000 point reads/s per replica.

Thirty-six failures reduce to a short list of signals, a handful of drills and a few standing rules. Without them, each incident above is a surprise; with them, most are routine.

Signals that deserve a page, and signals that deserve a ticket

Service objectives work best when written about operations rather than uptime: for example the fraction of linearizable reads answered within a latency goal, the fraction of writes acknowledged after a majority flush (which should be all of them), and the age of the oldest under-replicated partition. A store that answers quickly from a stale replica has a good latency number and a bad correctness one, so the objectives should name the read mode.

Drills that exercise the failures

• Kill a leader under peak write load and verify no acknowledged write is lost, the election time is within the target, and linearizable reads wait for the no-op commit (F17, F18).
• Partition a leader from its followers and confirm it returns 503 while the majority side elects a new leader, then heal and check the old leader steps down (F19, F20).
• Cut power to a node mid-write with the storage stack in its production configuration and replay the log, checking that only the tail record is affected (F02, F04).
• Run a rebalance while a continuous writer and a checker verify every acknowledged write remains readable, and kill the controller during the fence (F13, F15).
• Restore last night's backup into quarantine, decrypt with the production role, replay the archived log to a chosen time and verify that deleted keys stay deleted (F27, F35).
• Flood one tenant with writes and confirm that others' P99 stays inside its objective (F11).
• Take the control plane offline and start a new client pod (F29).
• Simulate loss of the home region and walk the decision procedure, including the residency check and the fence (F30, F31, F32).

• Acknowledging a write before the log flush, or before a majority has it, to win latency (F02, F17).
• Retrying a mutating call after a timeout without an idempotency key, or treating a CAS 412 after a timeout as proof of loss (F03).
• Trusting a tenant ID, a timestamp or a leadership belief supplied by something that could be wrong (F16, F20, F26, F33).
• Promoting a region because monitoring cannot see it (F31).
• Letting tombstone retention be shorter than the longest repair gap (F25).
• Taking backups without ever restoring them (F27, F35).
• Hand-deleting WAL segments to free disk (F05).
• Claiming read-after-write, linearizability or zero data loss without saying which read mode, region and assumptions apply (F21, F24, F30, F36).