Fencing Tokens: Stopping a Stale Lock Holder From Corrupting State

The problem: a lock you hold is not a lock you enforce

Distributed locks make an implicit, dangerous assumption: that a client which was told "you hold the lock" still holds it at the moment it acts. In a single machine that's true — the OS scheduler and the lock word are co-located. Across a network, the gap between "I acquired the lease" and "I am writing" can stretch arbitrarily.

• A stop-the-world GC pause can freeze a JVM for seconds; the lease expires unnoticed.
• A network partition cuts the client off from the lock service while it keeps talking to storage.
• Plain clock skew or a slow syscall stalls the client past the lease deadline.

In every case the lock service, seeing an expired lease, correctly hands the lock to a new client. Now two clients each believe they hold it — a split brain. The original holder, a "zombie," wakes up and writes. Money moves twice, a file is truncated, an invariant breaks. The lock did its job; the assumption that holding it means being allowed to write is what failed. Fencing tokens fix that assumption by making the resource verify, not trust.

How it works: issue, carry, compare

A fencing token is a single strictly-increasing counter with three obligations spread across three parties.

1. Issue. On every successful acquire, the lock service returns a token that is strictly larger than any it has ever returned for that resource: 33, then 34, then 35... It must never repeat or go backwards, even across lock-service restarts (so it's persisted or derived from a consensus log).
2. Carry. The client attaches the token to every operation it sends to the protected resource — not just the first.
3. Compare. The resource keeps max_seen, the highest token it has ever accepted. On each write it enforces the invariant.

on acquire(resource):        # lock service
    token = next_monotonic(resource)   # 33, 34, 35 ...
    return token

on write(resource, token, data):   # the resource itself
    if token <= max_seen[resource]:
        reject("stale token")
    else:
        max_seen[resource] = token
        apply(data)

The crucial shift: authority moves from the client's belief to the resource's memory. A zombie's token is, by construction, smaller than the token of whoever acquired the lock after it — so its write is always rejected.

Complexity and a worked step-trace

The enforcement is cheap. Per write the resource does one comparison and one conditional store: O(1) time. Storage overhead is O(number of protected resources) — one integer (max_seen) per resource, typically 8 bytes. Token generation by the lock service is O(1) plus whatever it costs to make the counter durable and ordered (an atomic increment, or one entry in a Raft/Zab log).

A trace of the canonical race, tokens shown in brackets:

t0  Client1 acquire(res) -> token 33      max_seen = 32
t1  Client1 begins long GC pause...
t2  lease(33) expires
t3  Client2 acquire(res) -> token 34
t4  Client2 write(res, 34, X)  34 > 32 -> ACCEPT, max_seen = 34
t5  Client1 wakes, unaware
t6  Client1 write(res, 33, Y)  33 <= 34 -> REJECT

The write with token 33 is refused after 34 has been seen. Note the ordering that matters is at the resource, not wall-clock: even if Client1's packet arrives first, once 34 lands, 33 is permanently dead. The invariant is a per-resource monotone barrier — max_seen only ever climbs.

Where it's used in real systems

You rarely mint tokens by hand; robust systems expose a monotonic counter you can reuse:

• Apache ZooKeeper. The classic lock recipe uses ephemeral sequential znodes; the czxid (creation transaction id) or a parent's cversion is globally monotonic via the Zab protocol and serves directly as a fencing token.
• etcd. Every key mutation gets a Raft-ordered revision/mod_revision; a client fences with the lock's revision and enforces it via a transactional compare-and-swap at the store.
• Google Chubby / lease systems. Chubby's lock "sequencer" — a lock name plus generation number — is the original industrial fencing token; servers validate the sequencer before acting.
• HDFS and HA leaders. An "epoch" or "generation clock" number rejects writes from a deposed NameNode/leader — the same idea under a different name.

The common thread: the token piggybacks on an existing totally-ordered log (Zab, Raft, Paxos), so monotonicity comes for free from consensus rather than from a fragile local clock.

Compared to the alternatives

The alternative to fencing is trusting the lease — and its variants all share one flaw: the resource has no way to tell a live holder from a zombie.

• Plain lease + client trust: simplest, and unsafe under any pause or partition. The client's confidence is not evidence.
• Shorter leases: shrink the danger window but never close it, and short leases mean more renewal traffic and more spurious expirations.
• Redlock (multi-master Redis): Martin Kleppmann's 2016 critique showed its random lock value carries no ordering, so it cannot fence; you'd need a consensus system to generate ordered tokens — at which point you already have what you need.

The tradeoff fencing asks for: the resource must participate. It has to store max_seen and check it on every write. If the resource is a dumb blob store with no conditional-write primitive, you can't fence it directly — you must front it with something that can (a transactional layer, or object-storage conditional/If-Match writes). That cooperation requirement is the price of correctness.

Pitfalls, failure modes, and why it matters

Fencing is simple to state and easy to get subtly wrong.

• Non-monotonic tokens. A random UUID, a wall-clock timestamp (subject to skew and NTP jumps), or a counter that resets on lock-service restart all break the invariant. The token must be strictly increasing and durable across restarts.
• Resource doesn't check. A token nobody validates is decoration. The enforcement must live at the resource, not in client code the zombie is also running.
• Wrong comparison. Using < instead of <= lets two clients with the same token both write; the check must reject equal-or-lower.
• Side effects outside the fence. Fencing protects the write to the fenced store. If the zombie also sends an email or calls a non-fenced API, that action escapes.
• Multiple resources. A single logical operation touching two stores needs the token honored at both, or the fence has a hole.

Its significance is foundational: fencing tokens are how practitioners reconcile the fact that, under the FLP/CAP reality of asynchronous networks, you cannot prevent a client from thinking it holds a lock — so instead you make its stale actions harmless. It is the small idea that makes distributed mutual exclusion actually safe.

Distributed lock strategies and whether they safely stop a stale holder

Approach	Produces monotonic token?	Stale-holder write blocked?	Notes / tradeoff
Lease + trust the client	No	No	Client believes it holds the lock; a GC pause or partition silently voids that belief
Redlock (Redis multi-master)	No	No	Random lock value is not ordered; Kleppmann showed it cannot fence without added consensus
ZooKeeper lock + zxid / znode version	Yes	Yes	czxid or cversion is globally monotonic via Zab; natural fencing token, needs ZK cluster
etcd lock + mod_revision	Yes	Yes	Raft-ordered revision is monotonic; compare-and-swap enforces at the store
Fencing token (generic pattern)	Yes	Yes (if resource checks it)	Only works if the resource persists max token and rejects lower ones