# DDIA Ch. 9: a fencing token bounces a zombie leaseholder's write ## Concept A lock service grants a lease to `client1`, which then suffers a long GC pause — so long that its lease expires while it is frozen. The lock service, seeing the lease lapse, legitimately grants it to `client2`. When `client1` wakes it *still believes it is the leader* and issues a write. Now two clients each think they hold the lock: split brain. Send both writes at a plain **StorageService** and the zombie's stale write is **accepted**, silently overwriting the live data — no error raised. Turn on **fencing** — every lease grant carries a monotonically increasing token (33, 34, …), and storage remembers the highest token it has accepted and rejects anything lower — and the same stale write is **rejected** (`token 33 < 34`). The exact HBase bug from DDIA Figures 9-4/9-5/9-6, and its one-line fix. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 9 — *The Trouble with Distributed Systems*, §"Distributed Locks and Leases" / §"Fencing off zombies and delayed requests" (Figures 9-4, 9-5, 9-6): > Let's assume that every time the lock server grants a lock or lease, it also > returns a *fencing token*, which is a number that increases every time a lock > is granted [...] We can require that every time a client sends a write request > to the storage service, it must include its current fencing token. The book argues that even a *correct* lock service cannot stop a paused client from acting on a lease it has already lost; the only defense is to make the **resource** check a token. Here you trigger the zombie write, watch it corrupt storage, then add the token and watch storage reject it. ## Prerequisites The surprise is that holding a lease is not the same as *still* holding it. Each line notes where the idea shows up. 1. **Leases and locks are the same primitive with a timeout** — a lease is a lock that expires, so the lock service can reclaim it from a dead holder without waiting forever. It shows up as `LockService.acquire`, which the service is free to grant to `client2` once `client1`'s lease lapses. 2. **A process pause is indistinguishable from a crash** — a GC pause (or a scheduler preemption, or VM migration) can freeze a process for seconds; from outside it looks dead, and its lease is reclaimed, but it is not dead and will resume. It shows up as the "enters a long GC pause" step: `client1` keeps its in-memory belief "I am the leader" straight across the gap. 3. **Network delays are unbounded** — a packet can be arbitrarily delayed and arrive long after the sender lost its lease. It shows up in Scenario 3, where `client1`'s write was already in flight when its lease expired. 4. **A fencing token is a monotonic counter checked by the resource** — each grant gets a strictly larger number; the resource keeps the highest it has accepted and rejects anything lower. It shows up as `StorageService.max_token` and the `token < max_token` guard. ### Where to learn the prerequisites - **Leases, pauses, and fencing (#1, #2, #4):** DDIA §"Process Pauses" and §"Fencing off zombies and delayed requests" — the GC-pause thought experiment and Figures 9-4 through 9-6 are exactly this exercise. - **Unbounded delays (#3):** DDIA §"Unreliable Networks" and §"Timeouts and Unbounded Delays" — why you cannot pick a timeout that is always right. The pair that carries the result is **#2 + #4**: the pause is what makes the stale action *unpreventable at the client*, and the token is what makes it *rejectable at the resource*. Everything else is staging. ## Environment Deterministic, so the accept/reject outcomes reproduce exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker, no deps - No real concurrency and no wall-clock time: the pause and the message ordering are modeled explicitly, step by step, so the transcript is fixed every run - Fixed token sequence: the lock service hands out **33**, then **34** ## Mental model A lease is a *promise* — "you are the leader until time T." The trouble is that a promise can be **silently broken by a pause**: the lock service revokes the lease on schedule, but the frozen holder is never told, and when it thaws it acts on a promise that no longer holds. You cannot prevent the stale action — the client genuinely cannot know it was paused past its deadline. A fencing token makes the broken promise **visible to the storage service**. The grant is stamped `33`; the next grant is stamped `34`. Storage keeps the highest token it has ever honored. When the zombie's `token 33` write arrives after a `token 34` write, storage can *see* that this writer is operating on a stale grant and refuses it — even though the client still sincerely believes it is the leader. The check turns "trust that the client still holds the lock" into "the resource verifies a monotonic guard," which is the same shape as compare-and-set. - **StorageService (unfenced)** — `write(data)` accepts anything. It has no way to tell a current writer from a zombie. - **StorageService (fenced)** — `write(data, token)` rejects `token < max_token`, else records `max_token = token` and stores the data. The whole thing is one script, `code/fencing_token.py`, run three times over the same interleaving with the guard off, on, and against a delayed packet. ## Setup ``` cd study/ddia/ch09/code python3 fencing_token.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — no fencing: the zombie write lands **Predict.** `client1` holds the lease (would-be token 33), pauses, and its lease expires. `client2` acquires the lease (would-be token 34) and writes `client2 data`. Then `client1` wakes, still believing it is the leader, and writes `client1 stale data`. The lock service is *correct* — only one client holds the lease at a time. Is the storage safe? What does it hold at the end? **Observe.** ``` SCENARIO 1 -- no fencing token: the zombie write is accepted ==================================================================== client1 acquires the lease (would-be token 33) client1 enters a long GC pause ........ (frozen; cannot act) ... while client1 is paused, its lease EXPIRES ... client2 acquires the lease (would-be token 34) writes reach unfenced storage: client2 writes 'client2 data' (no token) -> ACCEPTED storage now holds 'client2 data' ... client1 WAKES, still believing it is the leader ... client1 writes 'client1 stale data' (no token) -> ACCEPTED storage now holds 'client1 stale data' FINAL storage contents: 'client1 stale data' >> CORRUPTED: the zombie's stale write overwrote the live one. Two clients each 'held' the lock; storage could not tell them apart. ``` **Corrupted — storage holds `client1 stale data`.** The lock service did nothing wrong: at no instant did two clients hold the lease. But mutual exclusion at the *lock* did not translate into mutual exclusion at the *resource*, because the resource trusts whoever calls `write`. The zombie's write is last, so it wins. ### Step 2 — fencing on: the stale token is rejected **Predict.** Identical interleaving, but now each lease carries a fencing token (`client1` → 33, `client2` → 34) and storage tracks the highest token it has accepted. `client2` writes with token 34; `client1` wakes and writes with token 33. What does storage do with the token-33 write, and what does it hold at the end? **Observe.** ``` SCENARIO 2 -- fencing on: storage rejects the lower token ==================================================================== client1 acquires the lease (token 33) client1 enters a long GC pause ........ (frozen; cannot act) ... while client1 is paused, its lease EXPIRES ... client2 acquires the lease (token 34) writes reach fenced storage (it tracks the highest token seen): client2 writes 'client2 data' token 34 -> ACCEPTED storage now holds 'client2 data' [max_token=34] ... client1 WAKES, still believing it is the leader ... client1 writes 'client1 stale data' token 33 -> REJECTED token 33 < 34 FINAL storage contents: 'client2 data' >> SAFE: token 33 < 34, so the zombie's write bounced off the guard. No error on client1's side was needed; the RESOURCE said no. ``` **Safe — storage holds `client2 data`.** The token-34 write raised `max_token` to 34; the zombie's token-33 write is now provably stale (`33 < 34`) and is rejected. `client1` still *believes* it is the leader — nothing corrected its in-memory state — but its belief no longer reaches the data. ### Step 3 — a delayed in-flight request is fenced too **Predict.** Same tokens, but this time `client1` *sent* its write before pausing; the packet was merely delayed in the network and arrives after `client2`'s token-34 write. The guard is on the token, not on who is "current." Accepted or rejected? **Observe.** ``` SCENARIO 3 -- fencing on: a delayed in-flight write is fenced too ==================================================================== client1 acquires the lease (token 33) client1 SENDS a write, then its lease expires -- the packet is delayed in the network, still in flight. client2 acquires the lease (token 34) client2's write lands first; client1's delayed packet arrives after: client2 writes 'client2 data' token 34 -> ACCEPTED storage now holds 'client2 data' [max_token=34] ... the delayed token-33 packet from client1 finally arrives ... client1 writes 'client1 delayed data' token 33 -> REJECTED token 33 < 34 FINAL storage contents: 'client2 data' >> SAFE: the guard is on the TOKEN, not on who is 'current' -- an old-enough token loses no matter when its packet shows up. ``` **Rejected, same as the zombie.** A delayed packet and a paused process are the same problem: a write stamped with a stale token arriving after a fresher one. The token check does not care *why* the write is late — a low token loses regardless of whether its sender is paused, crashed-and-recovered, or just slow. ## What you should see - **Unfenced:** `client1`'s stale token-33 write is **ACCEPTED**; storage ends holding `client1 stale data` — **corrupted**. - **Fenced:** the token-34 write sets `max_token = 34`; `client1`'s token-33 write is **REJECTED** (`token 33 < 34`); storage holds `client2 data` — **safe**. - **Delayed:** a token-33 packet arriving after the token-34 write is **REJECTED** by the same guard; storage holds `client2 data`. ## Why Mutual exclusion via a lock assumes the holder can *act on time*: that between "you hold the lease" and "your lease expired" the holder either does its work or hears the revocation. A GC pause breaks that assumption. The lock service revokes the lease exactly on schedule, but revocation is a message the frozen holder never receives, and its own clock froze with it — so on waking it has no way to know it was paused past its deadline. You **cannot prevent the stale action**: at the moment `client1` calls `write`, everything it can observe says it is still the leader. This is why "only one client holds the lease" is true and yet insufficient — the guarantee is about the *lock*, and the corruption happens at the *resource*. Since you cannot stop the stale write from being *sent*, the only place left to stop it is where it *lands*. The fencing token does exactly that by attaching a monotonic number to authority itself: grant 33 is strictly older than grant 34, and *that ordering is a fact the resource can check without trusting anyone*. Storage keeps `max_token`, the high-water mark of authority it has honored, and enforces one rule: `token < max_token → reject`. The instant `client2`'s token-34 write lands, `max_token` becomes 34 and every grant numbered ≤ 34 is retroactively dead. `client1`'s token-33 write is now self-evidently stale — the guard reads `33 < 34` and says no. Note the direction of the check: it is on the **token**, not on identity or recency, which is why the delayed packet in Scenario 3 loses for the identical reason. It is the compare-and-set shape — "write only if the guard is still at least what I expect" — applied to leadership instead of to a value.
The boundary — fencing needs the resource to check the token. The whole defense lives in StorageService's guard. If the resource cannot (or does not) inspect a token — a dumb blob store, a legacy filesystem, a device with no such API — there is nothing to reject the zombie, and you are back to Scenario 1 no matter how good your lock service is. Fencing also needs the tokens to be monotonic and issued by the same authority that grants the lease, otherwise "higher" is meaningless. And it protects the resource, not the client's belief: client1 still thinks it is the leader: fencing does not fix split brain, it makes split brain harmless at the one place that matters.
### Go deeper 1. **STONITH.** "Shoot The Other Node In The Head" is the blunt alternative: instead of letting the zombie live and rejecting its writes, physically fence it off (power it down, revoke its network) before granting the lease onward. Compare the failure modes — STONITH needs a reliable way to kill a node you cannot talk to; fencing needs a resource that checks tokens. 2. **Why the resource must check, not the client.** Move the token comparison into `client1` ("don't write if my lease expired") and convince yourself it cannot work: the paused client has no fresh information, so its own check passes on stale data. The guard has to sit on the far side of the network, at the thing being protected. 3. **Why monotonic, not just unique.** Replace the increasing counter with random unique tokens and watch the guard lose its power — `max_token` can only reject "lower" if "lower" means "older." Monotonicity is what encodes the *order* of grants into a single comparable number.