Distributed Systems Core · lesson 8 of 11 · about 26 min
Why a lock that merely expires is not a safe lock: lost updates without mutual exclusion, the TTL trade-off, the paused holder that wakes up believing it still owns the lock, fencing tokens that make the storage the real guard, what to build the lock on, and the job that outlives its lock. Tap any for a plain-language card.
Why a lock
Below, 5 workers each add one to a shared counter 200 times, with a couple of milliseconds between their read and their write. Without a lock many updates are lost; with one the answer is exact. The rest of the lesson is about what happens when the lock itself cannot be trusted.
More workers means more collisions. Switch to the lock and watch the loss drop to zero.
5 workers added up 1,000 increments but the counter says 310: 690 updates were overwritten by workers that had read an old value.
Seeded event simulation: each worker reads, waits an exponential think time (mean 2 ms), then writes read + 1.
The lock must expire
But the timer cannot tell a dead holder from a slow one. Set the TTL short and every slow-but-alive holder (a long query, a garbage-collection pause, a busy disk) loses its lock mid-job and someone else takes over. Set it long and a real crash freezes the work for that long. There is no value that is safe: only a trade between unsafe overlaps and slow recovery.
Try a 1-second TTL with a 2-in-1,000 chance of a 5-second pause, then 60 seconds: overlaps vanish, but now a crash blocks everybody for a minute.
With a 10 s TTL, 0.025% of lock holds outlive their lock (about 2 a day at one grant every 10 seconds), and after a real crash the next worker waits up to 10 s. Making the TTL longer trades the first number for the second; it never reaches zero while pauses are possible.
60,000 seeded lock holds: work time is log-normal around the typical value; with the stall probability an exponential stall is added. Unsafe = work + stall longer than the TTL.
The stale holder
The fix has to live where the damage would happen: the resource being protected must reject the stale worker. That is the : each grant of the lock carries a number that only goes up, the worker sends it with every write, and the storage refuses any write whose token is lower than one it has already seen.
Set the pause longer than the TTL and see the old data win, then switch fencing on.
A was paused for 14 s, longer than the 10-second TTL. B got the lock and wrote; then A woke up and overwrote B's work. The lock service did exactly what it promised, and the data is still corrupt.
A walkthrough computed from your two sliders; tokens are illustrative.
Fencing
This turns the lock from a promise into an optimisation: it still keeps workers from wasting effort on the same job, but correctness no longer depends on timing. Two requirements: the lock service must hand out increasing tokens (a consensus-backed service does this naturally), and the storage must be able to compare them (a version column, an etcd revision, a ZooKeeper zxid). A storage that cannot check tokens cannot be protected this way.
Run it without fencing and count overwritten writes; switch fencing on and they become rejected stale writes instead.
6 of 500 lock holders were still working after their TTL expired. Their late writes arrived after newer ones, and 6 times old data replaced new data without any error.
Seeded chain of grants: work ~ 200 ms (log-normal) plus a stall with the chosen chance. A write is stale if it arrives after its TTL; fencing rejects any write with a token below the highest applied.
Where the lock lives
Redis's multi-node “Redlock” algorithm tries to get safety from several independent Redis instances, but it depends on bounded clock drift and bounded pauses, and Martin Kleppmann's 2016 critique argued that is not enough for correctness; Redis's author replied. The practical reading: use Redis locks to avoid duplicate work, and use a consensus store (plus fencing) when a violation would corrupt data.
With Redis, raise the lock rate and replication lag: many locks vanish at every failover. Switch to a consensus store: zero.
| Store | Redis SET NX PX |
| On failover | Failover to a replica may lose locks that were not yet copied |
| Fencing token | None built in: you must add your own counter |
| In short | Fast and simple. Fine for efficiency locks, not for correctness on its own. |
At 500 grants a second and 5 ms of replication lag, the average failover loses 2.5 locks and 0.25 of them are granted a second time. For jobs that merely avoid duplicate work that may be fine; for data integrity add fencing.
Redis row: exact expectation; each lock granted in the 5 s before the crash is lost if its copy to the replica (exponential delay) had not finished. Other rows summarise how those systems document their behaviour.
Which protection?
A lock is the first thing people reach for and often not the best. Match the protection to what a violation would cost. Each answer is worth 20 XP.
Ask: what happens if two workers act at once? If the answer is 'a bit of wasted work', a lock is enough. If it is 'corrupt data', the storage must enforce it.
Only one of ten cron workers should run the nightly report. Running it twice merely wastes CPU.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four published systems and arguments about distributed locks.
a lock service built on Paxos
The Chubby paper describes a coarse-grained lock service for loosely coupled distributed systems, replicated with Paxos. Because a lock holder can be delayed, Chubby also offers sequencers: a string naming the lock and its generation that a client passes to a server, which can check it is still valid.
lock recipe with ephemeral sequential znodes
ZooKeeper's documented lock recipe creates an ephemeral sequential znode per contender; the lowest number holds the lock and the others watch their predecessor. Ephemeral nodes vanish when the client's session expires, which is ZooKeeper's version of a TTL, and the sequence numbers are naturally increasing.
are Redlock locks safe for correctness?
Kleppmann's article 'How to do distributed locking' argued that a lock with a timeout, including Redis's Redlock, cannot be safe on its own because processes can pause and clocks can jump, and that fencing tokens are required; Redis's author published a reply defending Redlock's guarantees for its intended uses. Both are widely read in interviews.
leases with keep-alives
etcd attaches keys to leases that expire unless the client sends keep-alives, and its lock helper builds on that. Each key carries a revision number that increases across the whole cluster, which a client can send to a storage as a fencing token.
Interview angle
Six questions, each worth 20 XP. Locks come up in every design where two workers could touch the same thing.
Show that you know the lock is not enough: mention the pause, the TTL trade-off, and fencing or compare-and-set.
What does a TTL on a lock protect against?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Three defences, in increasing order of strength. A thread renews the lock while the process is alive, so only a frozen process (a long pause that also stops the renewer) loses it. A makes the second worker's side effects harmless, because the storage rejects whichever token is older (the work is still wasted). And making the job removes the harm altogether, which a later lesson covers.
Keep the TTL at 30 s and raise the job-length spread. Then compare renewal and fencing.
With only a 30-second TTL, 0.22% of runs outlive the lock and are repeated by a second worker. Each one is a real duplicate: double invoices, double emails.
50,000 seeded runs: length is log-normal around the typical value; a 2-in-1,000 chance of a stall averaging 20 s. In the renewal mode only a stall longer than the TTL loses the lock.
Where to go next