A lock service grants a lease to client1, which then GC-pauses until its lease expires; the service hands the lease to client2. When client1 wakes it still thinks it is the leader and writes. Without a fencing token that stale write is accepted and storage is corrupted; with one it is rejected (token 33 < 34) and storage stays safe — the HBase bug from DDIA Figures 9-4/9-5/9-6 and its one-line fix.
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.
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.
The surprise is that holding a lease is not the same as still holding it. Each line notes where the idea shows up.
LockService.acquire, which the service is free to grant to client2 once client1's lease lapses.client1 keeps its in-memory belief "I am the leader" straight across the gap.client1's write was already in flight when its lease expired.StorageService.max_token and the token < max_token guard.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.
write(data) accepts anything. It has no way to tell a current writer from a zombie.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.
cd study/ddia/ch09/code
python3 fencing_token.pyDo not read the output yet — make each prediction first.
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?
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.
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?
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.
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?
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.
client1's stale token-33 write is ACCEPTED; storage ends holding client1 stale data — corrupted.max_token = 34; client1's token-33 write is REJECTED (token 33 < 34); storage holds client2 data — safe.client2 data.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.
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.
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.max_token can only reject "lower" if "lower" means "older." Monotonicity is what encodes the order of grants into a single comparable number.Sources: DDIA 2e, Ch. 9, §"Distributed Locks and Leases", §"Fencing off zombies and delayed requests", §"Process Pauses" · Figures 9-4, 9-5, 9-6.