Distributed locks and fencing tokens: an interactive simulator
A distributed lock with a lease cannot by itself guarantee that only one client acts at a time. A holder that pauses, or whose message is delayed, can act after its lease has expired and another client holds the lock. A fencing token closes the gap: a number that increases every time the lock is granted, sent with every write, so the storage can reject writes carrying a lower token than one it has already seen.
The playground has two clients sharing a lock with a 10 second lease, and the storage both write to. Pick a scenario, then turn fencing tokens on and off and watch which writes storage accepts.
Client 1 takes the lock with token 33, then stops for 14 seconds in a garbage-collection pause. Its lease expires at 11 s, the lock service gives the lock to client 2 with token 34, and client 2 writes. Then client 1 wakes up, still believing it holds the lock, and writes. Storage cannot tell the stale write from a good one and accepts it, overwriting client 2’s data. Turn on fencing tokens to see the difference.
How lease-based locks work
- Acquire: a client asks the lock service for the lock and gets it for a lease, say 10 seconds, along with a token.
- Renew: while it is working it extends the lease before it runs out.
- Release: when done it gives the lock back. If it crashes instead, the lease expires and someone else can take the lock.
The lease is what stops a crashed client from blocking everyone forever. It is also the problem: the lock service decides the lease is over based on its own clock, and the client may have no idea.
Why a lease is not enough
A client can stop running at any moment without noticing: a stop-the-world garbage collection, a virtual machine being paused or migrated, a page fault on swapped-out memory. In the second preset, client 1 stops for 14 seconds right after taking the lock. Its lease expires, client 2 takes the lock and writes, and then client 1 resumes, believes it still holds the lock and writes too, overwriting client 2’s work. For 6 seconds both clients believed they held the lock.
Checking the lease just before writing does not help, because the pause can come between the check and the write. Neither does renewing more often, as the last preset shows: a client renews only while it is running. And the write itself can be delayed: in the fourth preset client 1 sends its write while its lease is valid, and the network delivers it after client 2 has written.
How fencing tokens fix it
The lock service gives every lease a number higher than the last: 33 for client 1, then 34 for client 2. The client sends its token with every write, and the storage remembers the highest token it has accepted and rejects anything lower. When client 1 wakes up and writes with 33, storage has already seen 34 and turns it away. The token does not stop two clients from believing they hold the lock; it makes sure the outdated one cannot change anything.
This needs two things: a lock service that hands out a strictly increasing number, such as ZooKeeper’s zxid or etcd’s revision, both built on consensus; and storage that checks it, which usually means a conditional write.
-- the lock service returns a token that grows with every grant, e.g. etcd's revision
-- or a ZooKeeper zxid; storage keeps the highest token it has accepted
UPDATE reports
SET body = $1, fence = $2
WHERE id = $3
AND fence <= $2; -- the current holder may write again; older holders may not
-- 0 rows updated: a newer lock holder has written since. Stop, do not retry.Locks for efficiency vs locks for correctness
Ask what goes wrong if two clients hold the lock at once. If the lock only avoids doing the same work twice, such as sending a daily report or rebuilding a cache, an occasional duplicate is harmless and a simple lock in Redis with an expiry is fine. If the lock protects data, so that two holders would corrupt it or double-spend, you need fencing, and a lock service that can provide tokens. Redlock, the multi-node Redis locking algorithm, was criticised by Martin Kleppmann in 2016 on exactly these grounds: it relies on timing assumptions and provides no fencing token. Its author disputed the critique, but the rule holds either way: if correctness depends on the lock, fence.
In a system design interview
When you reach for a distributed lock, say what it protects and how a stale holder is stopped: “Only one worker should process a given account’s settlement. Workers take a lease in etcd and get its revision as a fencing token; every write to the ledger carries it, and the ledger rejects writes with an older token. So a worker that stalls past its lease cannot write after its replacement.” Expect the follow-ups: what happens to work in progress when a lease is lost, how long leases should be, and whether you could avoid the lock entirely with a conditional write or a single owner per partition.
Read the guide to distributed locks and leases, see Raft for the consensus behind lock services, or watch a strong candidate design a job scheduler, where only one worker may run each job.
Questions people ask
What is a fencing token?
A number that a lock service issues with each lease, higher every time the lock is granted. The lock holder sends it with every write, and the storage remembers the highest token it has accepted and rejects writes with a lower one, so a client that has lost the lock without knowing cannot change anything.
Why is a lease-based distributed lock not safe on its own?
Because the holder cannot tell when its lease has expired. A garbage-collection pause, a paused virtual machine or a delayed network packet can make it act after the lock service has given the lock to someone else, so two clients briefly both believe they hold it. Checking the lease before acting does not help, since the pause can come after the check.
How do you implement fencing tokens?
Use a lock service that returns a strictly increasing number with each grant, such as etcd’s revision or a ZooKeeper zxid, and make storage check it: store the highest token seen with the data and make every write conditional, for example UPDATE … WHERE fence <= :token. A write that updates nothing means a newer holder has taken over.
Does renewing a lease prevent two lock holders?
No. Renewal keeps the lease alive while the holder is running, but a holder that is paused cannot renew, and when it resumes it may not notice that its lease ran out during the pause. Renewal reduces how often leases expire under a healthy holder; it does not remove the need for fencing.
Is Redis Redlock safe?
It is contested. Martin Kleppmann argued in 2016 that Redlock depends on bounded pauses, network delays and clock drift, and provides no fencing token, so it cannot guarantee correctness; Redis’s author disagreed. Either way, a Redis lock is fine for avoiding duplicate work, and anything that protects correctness should use fencing tokens from a consensus-based lock service.
When do you need a distributed lock?
When only one process may do something at a time: run a scheduled job, process a partition, or modify a shared resource that has no transactions. Often you can avoid one with a conditional write, a unique constraint, or by giving each partition a single owner. If you do use a lock and correctness depends on it, fence the writes.
What is the difference between a lock for efficiency and a lock for correctness?
A lock for efficiency stops work being done twice, so if it occasionally fails the cost is some wasted work, and a simple lock with an expiry is enough. A lock for correctness protects data from conflicting changes, so a failure corrupts data, and it needs a reliable lock service plus fencing tokens checked by the storage.