Locks and fencing tokens

A lease that expires while its holder is paused, and the token that makes it safe.

On the roadmap:Advanced · step 4: Distributed systems

Intermediateabout 10 to 15 min6 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

Lease length (seconds)10

How long client A pauses (seconds)15

A checks that it still holds the lock just before it writesThe storage uses fencing tokens, and refuses a token lower than one it has seen

A pause of this kind cannot be seen from inside the process: the clock jumps and nothing else tells it. A one-second garbage collection is common, and ten-second ones have been reported in real systems.

Final value

It should be

Stale write accepted

yes

Stale write refused

A woke up after its lease ended and wrote anyway. The storage accepted it, so B's update was overwritten: the value is 11 and should be 15. Turn on fencing to see the storage refuse it.

Who held the lock when

Green is the lease. Amber is A paused. If A wakes after the red line, it is writing without the lock and does not know.

In order

0.0 s · Client AA asks for the lock and gets it, with token 1. The lease lasts 10 s.
0.0 s · Lock serviceThe lock service will give the lock to someone else after 10 s, whatever A is doing.
1.0 s · Client AA reads the value: 10. It plans to write 11.
2.0 s · Client AA pauses for 15 s (a long garbage collection, a stalled network, a busy machine).
10.0 s · Lock serviceA's lease runs out. A is not there to renew it, so the lock is free.
10.3 s · Client BB asks for the lock and gets it, with token 2.
10.5 s · Client BB reads 10 and writes 15.
10.5 s · StorageThe store now holds 15, written with token 2.
17.0 s · Client AA wakes up. Nothing tells it that time has passed, so it still believes it holds the lock, and writes 11 with token 1.
17.0 s · StorageThe store accepts it. B's update is overwritten: the value is 11.

In plain words

A distributed lock lets one client at a time work on a shared resource. To survive a crashed holder, the lock is a lease that runs out on its own. But a client can freeze mid-task without knowing, so it may still believe it holds the lock after the lease has passed to someone else.

Why it matters

Many systems use a lock to keep two workers from doing the same job, and assume that holding the lock means being safe. It does not: a long pause, a slow network or a busy machine breaks that assumption. The fix is a fencing token, so the storage itself can refuse a write from a client that has lost its place.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

Martin Kleppmann's essay How to do distributed locking describes exactly this failure, with a client that pauses during garbage collection, and recommends a fencing token that the storage checks.
Google's Chubby lock service hands out sequencers, which a service can check to reject requests from an old lock holder. ZooKeeper's transaction IDs and etcd's revision numbers are used as fencing tokens in the same way.
Redis-based locks such as Redlock are fine for efficiency, to avoid doing work twice. For correctness they have been criticised, because without a monotonically increasing token the storage cannot tell a stale writer from the current one.
A lease is still the right way to release a lock held by a dead client. Fencing just makes the system safe when the client is alive but late.