Distributed locks and fencing

The problem it solves

Two processes must not do the same thing at the same time — process one payment, run one migration, write one file. On a single machine a mutex settles it. Across machines, the usual reach is for a lock in Redis or ZooKeeper: acquire a key, do the work, release it.

The lock needs a lease, an expiry, because a client that dies while holding it must not block everyone forever. And the lease is where the guarantee quietly disappears. A lease expires by wall-clock time on the lock server, which has no idea what the client is doing. If the client is paused — a stop-the-world garbage collection, a hypervisor migration, a descheduled container, a page fault storm — the lease expires, another client acquires the lock, and then the first client wakes up and continues, still believing it holds the lock. It writes. Nothing crashed. The mutual exclusion you were paying for never existed at that moment.

The mechanism

The failure is not a bug in Redis or in your client library. It is structural: a lock server can revoke a lease, and it cannot stop a paused process from acting when it resumes, because the paused process finds out it lost the lock only by asking — and by the time it asks, it has already written.

Fencing tokens fix it, and they fix it by moving the enforcement to the only place that can enforce anything: the resource.

Every lock grant carries a monotonically increasing token: 33, then 34, then 35. The client passes its token with every write. The resource — the database, the file store, whatever is being protected — remembers the highest token it has seen and rejects any write carrying a lower one. The zombie client wakes up holding token 33, writes, and the store rejects it, because it has already accepted a write with token 34. The lock service is no longer being asked to guarantee something it cannot; it is being asked to hand out increasing numbers, which it can do reliably.

The essential shift: correctness is no longer a property of the lock. It is a property of the resource, checked at the moment of the write.

What the simulation shows

Clients acquire the lock, work, and occasionally pause for longer than their lease.

Run the default with fencing off. The sequence panel shows the whole story in one picture: client A takes the lock, pauses, the lease expires, client B takes the lock and starts working, and then A resumes and writes. The zombie-writes counter climbs. Two clients were inside the critical section, and both were following the protocol correctly.

Now turn fencing on. The pause still happens; the lease still expires; A still wakes up and still tries to write. The write is rejected by the store, and the zombie counter stays at zero. Nothing about the lock changed. The resource changed.

Then the tempting non-fix: quadruple the lease. Zombie writes become rarer. They do not stop, because a longer lease only requires a longer pause, and the length of the pause is not under your control. A JVM full GC on a large heap can be seconds; a hypervisor migration can be longer; a container that loses its CPU share can be arbitrarily long. Tuning the lease is choosing a probability, not building a guarantee — and it is exactly the mistake this page exists to prevent.

The numbers worth carrying

Pauses are longer than people expect. A stop-the-world GC on a multi-gigabyte JVM heap: tens to hundreds of milliseconds routinely, seconds occasionally. Live VM migration: hundreds of milliseconds of blackout. A container throttled by cgroup CPU limits: unbounded. Network partitions: unbounded by definition.

So the lease question — “how long a pause must I survive?” — has no upper bound, which is the whole argument. A fencing token has no such parameter.

Renewal helps and does not close the gap: a client renewing at half the lease is safe against pauses shorter than half a lease, and against nothing longer.

Where it breaks down

The resource must support the check. A compare-and-set on a version column, a conditional write with an expected value (If-Match on S3, condition expressions in DynamoDB), or an explicit token column all work. A plain file write on NFS does not. If the resource cannot check, fencing is unavailable and you should say so rather than pretend the lock is sufficient.

Not all lock services give monotonic tokens. ZooKeeper’s zxid and its sequential znodes do; etcd’s revision numbers do. Plain Redis SET NX does not — it gives you a random value for safe release, which is not the same thing. Redlock, the multi-instance Redis locking algorithm, was the subject of a well-known exchange between Martin Kleppmann and Salvatore Sanfilippo; the durable conclusion is that any lock relying on timing assumptions cannot guarantee mutual exclusion, and that fencing is what actually provides safety.

Clock assumptions. Leases assume bounded clock drift between the lock server and its own expiry logic. Use monotonic clocks for measuring elapsed time; wall clocks jump.

The lock service is now a dependency with its own availability, its own latency on the critical path, and its own split-brain considerations if it is replicated.

What people get wrong

“We use Redis for locking, so we have mutual exclusion.” You have mutual exclusion in the absence of pauses, partitions and clock skew — that is, in the absence of the conditions that make distributed systems distributed.

“A longer lease is safer.” It is less frequently unsafe, which is not the same property, and it lengthens every recovery when a holder genuinely dies. It is a trade with a worse position on both axes than fencing.

“Renewal fixes it.” Renewal fixes short pauses. The failure is a long pause.

“Just make the operation idempotent.” Often the correct move — see idempotency — and it solves a different problem. Idempotency makes repetition safe; fencing makes stale writes rejected. A zombie writing an old value idempotently is still writing the wrong value.

In production

ZooKeeper’s ephemeral sequential znodes give both a lock and a monotonic number, which is why it remains the reference implementation for this pattern. etcd’s leases plus revision numbers do the same. Chubby, Google’s lock service, is the origin of much of this thinking and its paper is explicit that the sequencer (their name for a fencing token) is what makes the lock safe.

The practical order of preference is worth stating in an interview: avoid the lock entirely (partition the work so only one worker can own each key — see sharding); if you cannot, use a conditional write on the resource, which is optimistic concurrency and needs no lock at all; and if you genuinely need a lock, use one that issues fencing tokens and a resource that checks them.

The follow-up questions

“How do you do a distributed lock?” — Lease plus fencing token, and say why the token is the part that provides safety.

“What if the holder pauses?” — The failure this page is about. Walk through the sequence; then the fix.

“Would a longer lease help?” — No. Explain that the pause length is not bounded by anything you control.

“Do you need a lock at all?” — Often not. Optimistic concurrency with a version check, or partitioning so that only one worker owns a key, are both stronger and cheaper. Reaching for that first is the senior answer.