Start here: one machine must win#
TL;DRthe 30-second version
- A distributed lock lets only one machine at a time do something — run a job, write a file — when the machines share no memory to coordinate through.
- The usual build is a lease: a shared key that says 'taken', with a time-to-live so a crashed holder's lock expires on its own instead of jamming forever.
- The trap: a holder can pause (a garbage-collection freeze, a slow disk) long enough for its lease to expire. The lock service then hands the lock to a second machine, and the paused one wakes up still thinking it holds the lock. Now two machines act at once.
- The fix is a fencing token: the lock service hands out a number that only ever goes up, and the resource being protected rejects any write carrying a token lower than the highest it has already seen. The stale holder's late write is refused.
- Locks built on a timeout depend on clocks and pauses staying bounded, which they don't. Locks built on a consensus service (ZooKeeper, etcd) plus a fencing token are the safe version.
You're running a background job on a fleet of servers — say, a nightly task that charges every customer's saved card once. It must run on exactly one machine. If two servers both pick it up, every customer gets charged twice. On a single computer you'd guard the task with a mutex, a lock the operating system hands to one thread and makes everyone else wait for. But your servers don't share an operating system, or memory, or anything except the network between them. There is no mutex that spans machines. So the question is: how do a dozen servers, each unable to see the others' memory, agree that only one of them holds the right to run this job?
The shape of the answer is to move the lock off any one machine and into a service they can all reach. Put a single key somewhere every server can read and write — a row in a database, or an entry in Redis (an in-memory key-value store often used for this). The rule is simple: whoever manages to write the key first owns the lock, and everyone else sees it's taken and backs off. That one shared key is the whole idea of a distributed lock. Everything hard about the topic is what happens to that key when a machine crashes, pauses, or a clock lies.
Build it: a key, a lease, and a token#
Start with the naive version and let it break. To take the lock, a server writes the shared key only if nobody else has — an operation most stores give you directly (Redis calls it SET-if-not-exists). If the write succeeds, you hold the lock. If it fails, someone else does, so you wait and retry. To release, you delete the key. This works right up until the holder dies.
Picture the holder crashing after it took the lock but before it deleted the key. The key is still there, still saying 'taken', and nobody is coming back to delete it. The lock is now stuck forever, and every other server waits on a holder that no longer exists. A lock that a crash can jam permanently is useless in a system where machines crash all the time.
The fix is to make the lock expire on its own. When you write the key, attach a time-to-live — a countdown, say ten seconds, after which the store deletes the key automatically. Now a crashed holder's lock cleans itself up: ten seconds after it dies, the key vanishes and the next server can take it. A lock that carries its own expiry like this is called a lease. You don't hold it forever; you hold it for a bounded stretch of time, and you must finish your work and release it before it expires.
Now walk the dangerous timeline one step at a time. This is the whole reason the topic exists, so go slowly:
- Server A takes the lease on the job. The lease is good for 10 seconds.
- Server A starts working, then its garbage collector freezes the process for 30 seconds. Server A is paused and doesn't know it.
- 10 seconds in, the lease expires. The lock service deletes the key. As far as the lock service is concerned, nobody holds the lock now.
- Server B asks for the lock, gets it cleanly, and starts doing the job. This is correct behavior — the lease expired, so the lock was free.
- The 30-second pause ends. Server A wakes up exactly where it left off, still holding a lease it thinks is valid, and finishes writing to the resource.
- Now Server A and Server B have both acted on the same resource, each certain it was the only one. The lock did its job and still let two machines in.
Notice that nothing was buggy. The lease worked. The lock service worked. Server B did everything right. The failure is structural: a lease can expire while its holder is frozen, and a frozen holder can't know its lease is gone. Making the lease longer doesn't fix it — a longer lease just means a longer jam when a holder really does crash, and a pause can always outlast whatever number you pick. You need something that stops the stale holder's late write even after its lease is gone.
Here is the fix. Each time the lock service grants the lock, it also hands out a number that only ever increases. Server A gets token 33. When the lease expires and Server B takes the lock, Server B gets token 34 — strictly higher, because the lock service never reuses or lowers a number. Now the trick: every write to the protected resource must carry the token, and the resource remembers the highest token it has ever accepted and refuses any write carrying a lower one. This number is called a fencing token.
Trace the dangerous timeline again with tokens. Server A holds token 33 and freezes. Server B takes the lock, gets token 34, and writes to the resource, which records 34 as the highest it has seen. Server A wakes and writes with token 33. The resource compares 33 against the 34 it already accepted, sees the token has gone backwards, and rejects the write. The stale holder is fenced off. The lease can still expire early, two machines can still briefly believe they hold the lock, but only one of their writes can ever land — the one carrying the newest token.
Why timeouts and clocks are shaky ground#
A lease is a deadline, and a deadline is only as trustworthy as the clock measuring it. Two different kinds of clock trouble undermine a timeout-based lock, and it's worth separating them.
- Pauses break the holder's sense of time. The holder assumes that if it checks the lease, does a little work, and writes, only a few milliseconds passed. A garbage-collection freeze or a scheduling delay can make that a few seconds or minutes, and the holder never sees the gap. This is the fencing scenario above.
- Clock drift and jumps break the lock service's sense of time. A lease's expiry is computed against a wall clock, and wall clocks drift, get corrected by time-sync in sudden jumps, and can even be set backwards by an operator. If the lock service's clock jumps forward, it can expire a lease early, while a holder that is still working believes it has time left. The clock-synchronization simulator (/clocksync/sim) shows why clocks drift and why they can never be perfectly aligned.
The uncomfortable truth is that a timeout-based lock is only safe if you can bound three things: how long a process can pause, how far a clock can drift, and how long the network can delay a message. Real systems bound none of them. Network delays of tens of seconds have been observed in production, and a full garbage-collection pause has lasted minutes. When any of those exceeds the lease, the lock can be held by two machines at once. This is exactly why the fencing token matters: it makes the lock's safety depend on the order of tokens, which is exact, rather than on clocks and pauses staying within a budget, which they don't.
PredictYour lease is 10 seconds. Your servers occasionally suffer garbage-collection pauses of up to 20 seconds. Without fencing tokens, what's the worst case — and does making the lease 60 seconds fix it?
Hint: A longer lease survives a longer pause — but what does it cost when a holder actually crashes, and can any fixed number cover every possible pause?
Worst case: a holder takes the lease, pauses for 20 seconds, its 10-second lease expires at second 10, a second holder takes the lock at second 10 and starts working, and at second 20 the first holder wakes and writes to the resource — two writers on the same resource, exactly the corruption the lock was supposed to prevent. Making the lease 60 seconds does not fix it. A 60-second lease means a 20-second pause now fits inside the lease, so this particular pause is survived — but it costs you: if a holder truly crashes, the lock is now jammed for a full 60 seconds before anyone else can proceed. And a longer pause (a 90-second network stall, a multi-minute garbage-collection pause) still blows past 60 seconds and reopens the same hole. Any fixed lease is a bet that no pause exceeds it, and you lose that bet eventually. The only real fix is a fencing token, which makes the late write get rejected no matter how long the pause was.
Pitfalls & gotchas
Isn't a lock service holding the key enough on its own?
No, and this is the core mistake. Even a perfectly correct lock service can only tell you who it believes holds the lock right now. It cannot stop a holder that was granted the lock earlier, then paused past its lease, from waking up and writing anyway. Safety has to be enforced at the resource, by rejecting stale writes, because that's the only place the late write actually lands. The lock service grants; the fencing token enforces.
Is the random value some locks attach the same as a fencing token?
No — this was the heart of the Redlock critique. A random value (a unique string the client stores in the key so it only deletes its own lock) proves identity: it lets a holder check 'is this still my lock before I release it'. But it isn't ordered — random value 33 isn't 'older' than random value 34 — so a resource can't use it to reject a stale write. A fencing token must be monotonic, meaning it only ever increases, so 'this token is lower than one I've seen' means 'this holder is stale'. Identity and ordering are different jobs.
Efficiency lock or correctness lock — how do I tell which I need?
Ask what happens if the lock briefly fails and two machines act at once. If the answer is 'we waste some work, no harm done', it's an efficiency lock, and a plain lease is fine — the occasional double-run is cheap. If the answer is 'we corrupt data or double-charge someone', it's a correctness lock, and a lease alone is not safe; you need fencing tokens, and if the resource can't check tokens you need to rethink the design. Using an efficiency-grade lease where correctness was required is the single most common way this goes wrong.
Can't I just avoid the pause by checking the lease right before I write?
No. Checking the lease and then writing are two separate steps, and the pause can land in the gap between them: you check, see the lease is valid, then the garbage collector freezes you for 30 seconds, then you write with a lease that expired 20 seconds ago. There is no way to make 'check the lease' and 'write' one atomic action across the network, which is exactly why the enforcement has to move to the resource via the token.
QuizA team protects a shared file with a Redis lease. Each client stores a random value in the lock key so it only deletes its own lock, and always checks that value before writing. They still occasionally see the file corrupted by two writers. What's the fix?
- Make the lease longer so pauses fit inside it.
- A fencing token: an increasing number the file store checks, rejecting any write whose token is lower than the highest it has seen.
- Add more Redis nodes so the lock is more available.
- Check the random value twice before writing instead of once.
Show answer
A fencing token: an increasing number the file store checks, rejecting any write whose token is lower than the highest it has seen. — The random value proves identity but carries no order, so it can't tell the file store which of two writers is stale — a paused client can pass its own value check and still write after its lease expired. A longer lease only widens the pause it survives and lengthens the jam on a real crash; more Redis nodes improve availability, not this safety hole; checking the value twice still leaves the pause-after-check gap. The fix is a fencing token: the lock service hands out a strictly increasing number, and the file store records the highest it has accepted and rejects anything lower. The paused writer's older token is refused, so only the current holder's write lands — regardless of pauses or clocks.
When to reach for a lock at all
A distributed lock is a heavy tool, and the strongest engineers often avoid needing one. Before adding a lock, it's worth asking whether the coordination can be designed away.
- If the operation can be made idempotent — safe to run more than once with the same effect — you may not need mutual exclusion at all. Two machines running the same idempotent job just converge to the same result. This is often cheaper and safer than any lock.
- If the resource supports a compare-and-set (write only if the value is still what I last read), you can often coordinate through the resource directly and skip the separate lock. This is the same ordering idea as a fencing token, folded into the write itself.
- If you genuinely need a correctness lock, budget for fencing tokens from the start, and confirm the protected resource can actually check them. If it can't, a lock will not make the operation safe, and you should redesign rather than pretend it does.
- If it's only an efficiency lock — dedup work, avoid a thundering herd — a simple lease on Redis or a database row is fine, and the occasional slip is acceptable by definition.
The three ways people build it
Distributed locks in the wild come in three broad flavors, trading simplicity for safety. The table lines them up on what actually matters: does a machine crash jam the lock, and does the design defend against the paused-holder problem.
| Approach | How the lock is held | Guards the paused-holder problem? |
|---|---|---|
| Single-node lease (Redis SET-if-not-exists + TTL) | One key with an expiry on one Redis node | No — no fencing token; unsafe for correctness, fine for efficiency |
| Redlock (lease across 5 Redis nodes) | Majority of independent nodes grant the lease | Still no ordered fencing token; the Kleppmann critique below |
| Consensus lock (ZooKeeper, etcd) | A key in a consensus-replicated store, tied to a session | Better: sessions expire cleanly and give a monotonic version you can use as a fencing token |
Go deeperThe Redlock debate: Kleppmann vs antirez
Redlock is an algorithm from the Redis author (antirez) for making a lease safer by not trusting a single node. Instead of one Redis instance, you run five independent ones, and to take the lock a client must acquire the lease on a majority (three of five) within a short time budget. Losing one or two nodes doesn't lose the lock. It's the majority-acquisition idea you can watch in the quorum simulator (/quorum/sim), applied to locking.
Martin Kleppmann, a distributed-systems researcher, argued Redlock is unsafe for correctness in a widely-read 2016 critique. His two points: first, Redlock has no fencing token — its unique value is random, not monotonic, so a resource can't use it to reject a stale write, which leaves the paused-holder hole wide open. Second, Redlock's timing depends on bounded clock drift and bounded pauses across all five nodes; a clock jump or a long GC pause can let two clients hold the lock at once. Adding more nodes doesn't close a hole that comes from time itself.
antirez replied that Redlock targets efficiency locks, not correctness locks, and that its timing needs only relative time measured with bounded error, not perfectly synced clocks. He also made a sharp counter-point about fencing: if your resource can enforce an ordered token, it is already a store with enough ordering that you could generate the increasing IDs there and may not need the distributed lock at all — and most real resources (a physical device, a third-party API) can't check any token. The honest takeaway both sides share: if correctness depends on the lock and the resource can enforce a fencing token, use one; Redlock alone doesn't give you that.
In the wild
- ZooKeeper is the classic lock service: to take a lock, each client creates an ephemeral sequential node under a lock path — 'ephemeral' means it vanishes automatically when the client's session drops (a cleaner death signal than a timeout), and 'sequential' means ZooKeeper stamps it with an ever-increasing number. The lowest number holds the lock; everyone else watches the node just ahead of them and wakes when it disappears. That increasing number is a ready-made fencing token.
- etcd, the store behind Kubernetes, offers the same shape: a lease with a keep-alive heartbeat, a lock tied to that lease, and a monotonically increasing revision number on every key that works as a fencing token. Kubernetes leader election is built on exactly this.
- Google's Chubby, described in a 2006 paper, is the lock service that inspired most of these. It coined the idea of pairing a lock with a sequencer — a fencing token by another name — precisely because the authors saw holders pause past their leases in practice.
- Underneath every safe lock service is a consensus algorithm keeping the replicated lock state agreed across nodes, so no single machine's failure loses or forks the lock. etcd and Consul use Raft; you can watch that replicated log elect a leader and commit entries in the Raft simulator (/raft/sim).
In an interview
Distributed locks are a favorite because the naive answer sounds complete and is quietly wrong. The interviewer is usually probing whether you know why a lease alone isn't safe. Lead with the failure, then the fix.
- State the build fast: a shared key that says 'taken', with a TTL so a crashed holder's lock auto-expires. That's a lease.
- Name the trap before you're asked: a holder can pause (GC, slow disk) past its lease, the lock gets reassigned, and the paused holder wakes and writes anyway — two holders, one resource. Say 'garbage-collection pause' out loud; it signals you've hit this in practice.
- Give the fix: a fencing token, a monotonically increasing number the resource checks, rejecting any write with a lower token. Stress that enforcement lives at the resource, not the lock service.
- Draw the efficiency-vs-correctness line: a plain lease is fine to dedup work; a correctness lock (money, file writes) needs fencing, and needs a resource that can check the token.
- If Redlock comes up, know the trap: more Redis nodes improve availability but still give no ordered fencing token, and clock/pause assumptions remain. For correctness, reach for a consensus-backed lock (ZooKeeper, etcd) whose version number doubles as a fencing token.
PredictAn interviewer says: 'You're using etcd for locks, and etcd already gives every key a monotonically increasing revision. Do you still need a separate fencing token?' What's the strong answer?
Hint: What is a fencing token actually for, and does etcd's revision already do that job?
No — and recognizing why is the point. The whole job of a fencing token is to give the resource an ordered number it can use to reject stale writes, and etcd's revision (the version it stamps on the lock key when you acquire it) already is that number: it only ever increases, and a later acquisition always gets a higher revision than an earlier one. So the strong move is to read the lock key's revision at acquire time and pass it to the resource as the fencing token, rather than inventing a second counter. The nuance to name: this only helps if the protected resource actually checks the token and rejects lower ones — etcd handing you a good token does nothing if the thing you're writing to ignores it. That's the same limit as everywhere else: the lock service can hand out a perfect fencing token, but safety is only real once the resource enforces it.
References
- How to do distributed locking — Martin Kleppmann (2016) — The critique that popularized fencing tokens and the GC-pause failure timeline.
- Is Redlock safe? — antirez — The Redis author's rebuttal: efficiency vs correctness locks, and the fencing-token counter-argument.
- The Redlock algorithm — Redis docs — The five-node majority-lease algorithm itself.
- ZooKeeper Recipes — Locks — Ephemeral sequential znodes: the classic lock recipe with a built-in fencing number.
- etcd — distributed locks and leases — Lease keep-alive, lock, and the revision number that serves as a fencing token.
- The Chubby lock service — Burrows, Google (2006) — The lock service that introduced pairing a lock with a sequencer (a fencing token).
- Designing Data-Intensive Applications, Ch. 8 — Kleppmann's book treatment of leases, fencing, and the unreliable-clocks argument.