Concurrency
Part 4 of 6 · Distributed locksFencing Tokens — Stopping Stale Lock Holders After Partition
A monotonic fencing token must be checked by storage; without it, TTL/lease locks are unsafe after GC pauses or partitions.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Who stops the stale holder
Prefer
Monotonic fence checked by storage
Lock service issues 41, then 42. Client A still believes it owns 41 after a pause. Storage rejects F=41 once last_fence is 42. Clients can lie, bug, or pause — the resource must enforce.
- Per-resource counters are enough; never decrease.
- Same-holder retries may use >=; a new holder usually needs >.
- Reject with a distinct error (Fenced / 412) and metric it.
Alternative
Trust the client to stop, or TTL with no sequencer
A lease tells you that you probably own the critical section. Without a token at storage, GC, partitions, laptop sleep, and overloaded event loops all create zombies.
- Opaque UUIDs are not ordered — prefer integers or revisions.
- One fence per resource does not cover multi-key invariants — use DB transactions or etcd Txn.
- Best-effort cache fill may skip fencing; ledgers never skip.
Fencing rule
The token is useless if only the client remembers it.
- 1
Issue a monotonic fence on acquire
Per resource or global. ZK zxid / sequential node, etcd revision, Redis INCR, DynamoDB version, Chubby sequencer. - 2
Client includes fence on every mutating request
Every PUT, not just the first. Retries from the same holder still carry F. - 3
Storage compares to last_fence
Update last_fence only when request.fence >= last_fence (usually > for a new holder). - 4
Reject otherwise
Distinct error: Fenced / 412 / conditional check fail. Log acquire, write, and reject.
Overview
A fencing token is a monotonic number issued on every successful lock acquire. The shared storage (or any resource manager) accepts a write only if the token is ≥ the last accepted token for that resource.
Without fencing, TTL/lease locks are unsafe for shared mutable state: a GC-paused holder can wake after expiry and corrupt data even though the lock service already gave the lease to someone else.
Interview soundbite: a lease tells you that you probably own the critical section; a fencing token lets the storage prove you still do.
The stale holder problem
Partitions, STW GC, laptop sleep, and overloaded event loops all create "zombie" holders.
Sequence
- 1
1 Client A stale → 2 Lock service
acquire token=41 TTL=10s
- 2
1 Client A stale
GC / network partition 20s
- 3
2 Lock service
lease 41 expires
- 4
4 Client B → 2 Lock service
acquire token=42
- 5
4 Client B → 3 Storage no fence
PUT x=B
- 6
3 Storage no fence → 4 Client B
OK
- 7
1 Client A stale
resumes, still believes owner
- 8
1 Client A stale → 3 Storage no fence
PUT x=A
- 9
3 Storage no fence → 1 Client A stale
OK
- 10
3 Storage no fence
last writer wins — invariant broken
Lesson map
Fencing Tokens — Stopping Stale Lock Holders After Partition
A monotonic fencing token must be checked by storage; without it, TTL/lease locks are unsafe after GC pauses or partitions.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 Client A stale"] l["2 Lock service"] s["3 Storage no fence is one of the participants this lesson's sequence actually names."] b["4 Client B"] a -->|acquire token=41| l b -->|acquire token=42| l b -->|PUT x=B| s s -->|OK| b a -->|PUT x=A| s s -->|OK| a
Kleppmann's canonical diagram is exactly this zombie writer; fencing is the prescribed fix.
Fencing rule
- Lock service returns a monotonically increasing fence (per resource or global).
- Client includes fence on every mutating request.
- Storage updates
last_fenceonly whenrequest.fence >= last_fence(usually>for new holders;>=if the same holder retries). - Reject otherwise with a distinct error (Fenced / 412 / conditional check fail).
Decisions
- 1
1 Write request + fence F
- next2 F >= last_fence?
- ?
2 F >= last_fence?
- no3 Reject — stale holder
- yes4 Apply write
- 3
3 Reject — stale holder
- 4
4 Apply write
- next5 last_fence = F
- 5
5 last_fence = F
Critical: the token must be checked by the resource, not only remembered by the client.
Where the token comes from
| Source | Token | Notes |
|---|---|---|
| ZooKeeper | zxid / sequential node id | Natural monotonicity |
| etcd | key revision / lease id patterns | Use revision compares in Txn |
| Redis | Increment a fence: counter atomically on acquire | Must live with the lock grant |
| DynamoDB | Version attribute + ConditionExpression | Token is the version |
| Chubby-style | Sequencer | Classic Google paper pattern |
Lease id is a fencing token only if it is monotonic and checked. Opaque UUIDs are not ordered — prefer integers/revisions.
Fencing makes TTL locks safer for writes; acquire still needs some mutual exclusion mechanism. Together they approximate Chubby sequencers. Fencing tokens that only increase avoid ABA on the lock grant itself; storage versions may still need CAS — see optimistic coordination.
One fence per resource is insufficient for multi-object invariants — use DB transactions or etcd Txn.
Best-effort systems (single-flight cache fill) may skip fencing if losing mutual exclusion only wastes CPU. Ledgers, inventory, unique booking slots — never skip.
HTTP status for reject: often 409 Conflict or 412 Precondition Failed — be consistent and metric it. Log fence on acquire, renew, write, reject — essential for incidents.
How to test: inject a pause between acquire and write; ensure the second client wins and the first write is rejected.
Sandbox: reject the stale PUT (Python)
Same pause as the sequence diagram. Unfenced storage accepts A after B; fenced storage returns reject.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
Acquire as A (token 41). Freeze A for 20s on a 10s lease. B acquires 42 and writes. Thaw A; A PUTs with 41. What does storage return? What log lines do you want for the incident? Repeat with a UUID instead of 41/42 — can storage decide?
Interview Q&A
Define fencing token.
Answer
Monotonic id from the lock service; resource rejects lower tokens.
Why not trust the client to stop?
Answer
Clients lie / bug / pause; the resource must enforce.
Global vs per-resource counters?
Answer
Per-resource is enough; global also works if dense enough. Never decrease.
How does this relate to Kleppmann's blog?
Answer
His canonical diagram is exactly the zombie writer; fencing is the prescribed fix.
Is lease id a fencing token?
Answer
Only if it is monotonic and checked; opaque UUIDs are not ordered — prefer integers/revisions.
What HTTP status for fence reject?
Answer
Often 409 Conflict or 412 Precondition Failed — be consistent and metric it.
Can fencing replace consensus locks?
Answer
It makes TTL locks safer for writes; acquire still needs some mutual exclusion mechanism. Together they approximate Chubby sequencers.
ABA and fencing?
Answer
Fencing tokens that only increase avoid ABA on the lock grant itself; storage versions may still need CAS — see the optimistic lesson.
Multi-object transactions?
Answer
One fence per resource is insufficient for multi-key invariants — use DB transactions or etcd Txn.
How to test?
Answer
Inject pause between acquire and write; ensure second client wins and first write is rejected.
Logging?
Answer
Log fence on acquire, renew, write, reject — essential for incidents.
Interview closer?
Answer
TTL without fencing is a footgun for shared mutable state; I would issue a sequencer and enforce it at storage.