The big idea
What is a distributed lock?
On one machine, "only one thread at a time" is a mutex — trivial. Now the workers live on different machines with no shared memory: two servers both want to run a nightly job once, or edit the same record. They can't see each other. How do you guarantee that exactly one proceeds, even when a holder crashes mid-task?
A distributed lock provides mutual exclusion across machines. It's deceptively hard: unlike a local mutex, the holder can die (leaving the lock stuck), the network can lie, and clocks and pauses can betray you. The design adds TTL leases, ownership tokens, fencing, and consensus to make it safe.
How to read this: Each step opens with a real design decision — make the call before I show you what ships. Watch the design grow, and at the end kill the store and remove fencing to see why "usually exclusive" isn't "safe". Hit Begin.
Step 1 · The stuck flag
A "locked = true" row
The naive version: a row lock: locked=true. To acquire, set it true; to release, set it false. What breaks the moment a holder crashes — or two workers race?
Design decision: A DB flag "locked=true" as a lock. What are the two fatal flaws?
The call: A crashed holder never releases it (stuck forever), and a non-atomic check-then-set lets two acquire. — If the holder dies before setting locked=false, the lock is held forever and no one can proceed. And "if not locked, lock it" as two steps races — both workers read false and both set true. You need atomic acquire AND automatic release on death.
Two fatal flaws. No auto-release: if the holder crashes before unlocking, the flag stays true forever and the resource is deadlocked. Not atomic: "check if free, then set" is two steps, so two workers can both read "free" and both acquire. A real lock needs an atomic acquire and a way to release a dead holder's lock automatically.
The two hard parts: Distributed locking is really two problems: atomicity (grant to exactly one, even under a race) and liveness (don't deadlock forever when a holder dies). The naive flag fails both. Everything below fixes them.
Step 2 · Grant to exactly one
Atomic acquire
First fix the race: two workers ask for the lock at the same instant. Only one can win, decided in a single indivisible step. How?
Design decision: Two workers acquire at the same instant. How do you grant to exactly one?
The call: Whoever's request arrives first (by timestamp) wins. — Timestamps race and clocks disagree across machines; deciding by arrival time isn't atomic and can grant to two. The store must decide with one indivisible conditional operation.
Use an atomic conditional write: "set the lock key only if it doesn't exist" (Redis SET key token NX, or a unique-constraint insert). The store decides this in one indivisible step, so exactly one racing worker succeeds and every other gets "already held". No check-then-set window for a race to slip through.
Atomicity from the store: You don't build the atomicity yourself — you borrow it from a store that offers an atomic compare-and-set / set-if-absent. That single primitive is what turns "two might both win" into "exactly one wins", deterministically.
Step 3 · Don't deadlock on death
TTL leases
Atomic acquire still leaves the second flaw: if the holder crashes while holding the lock, it never releases, and the lock is stuck forever. You can't rely on a dead process to clean up. How does the lock free itself?
Design decision: The holder crashes while holding the lock. How does it ever get released?
The call: Give the lock a TTL (a lease): it auto-expires after a time, so a dead holder's lock frees itself. — The lock is granted for a bounded lease (TTL). If the holder dies, the store expires the key automatically and another worker can acquire. The holder must finish (or renew) within the lease, turning "held forever" into "held for at most T".
Make the lock a lease with a TTL: it's granted for a bounded time and auto-expires. If the holder dies, the store removes the key when the TTL elapses, and another worker can acquire — no dead process or human needed. The holder must complete its work (or renew, step 7) within the lease. "Held forever" becomes "held for at most T".
Leases, not locks: A distributed lock is really a time-bounded lease. The TTL is the safety valve against crashes: it guarantees liveness (the lock always frees eventually) at the cost of a hard question — what if the holder is alive but slow, and the lease expires anyway? (That's the fencing problem.)
Step 4 · Only the owner unlocks
Ownership tokens
With TTLs, here's a nasty bug: Worker A acquires, runs slow, its lease expires; Worker B acquires. Then A finishes and calls "release" — and deletes B's lock, which A no longer owns. How do you make release safe?
Design decision: A's lease expired and B now holds the lock. A finishes and calls release. What must happen?
The call: Release always deletes the lock key. — Blind delete is exactly the bug: A's stale release wipes B's valid lock, and now two workers think they can proceed. Release must verify ownership first, atomically.
Give each acquisition a unique ownership token stored with the lock. Release is conditional: "delete the lock only if its token still equals mine" — executed atomically (a small Lua script / compare-and-delete). So A's late release finds the token now belongs to B and does nothing; A simply learns it no longer holds the lock. Never a blind delete.
Check-and-delete: The token turns release from "delete the key" into "delete my key if it's still mine". Without it, an expired holder silently frees someone else's lock — a classic, dangerous distributed-lock bug. Ownership must be verified atomically on release.
Step 5 · The safety hole
The fencing-token problem
Now the deepest issue. Worker A holds the lock, then pauses — a long GC, a VM stall — past its lease. The lock expires; Worker B legitimately acquires. Then A wakes up, still believing it holds the lock, and writes to the resource. TTLs plus tokens didn't stop this: for a moment, two workers act as holder. How do you make the resource reject the stale one?
Design decision: A paused past its lease; B acquired; A wakes and writes. How does the resource reject A?
The call: Issue a monotonically increasing fencing token per grant; the resource rejects any write with a token lower than the highest it has seen. — Each lock grant carries an ever-increasing number (a fencing token). B's token is higher than A's. The resource remembers the highest token it has accepted, so when stale A writes with its old, lower token, the resource rejects it. Safety is enforced at the resource, not by hoping the lock never overlaps.
Add a fencing token: every grant carries a monotonically increasing number, and the protected resource records the highest token it has accepted and rejects any write with a lower one. B's grant has a higher token than A's; when paused-A wakes and writes with its old, lower token, the resource refuses it. Correctness is enforced at the resource, not by praying the lease never overlaps a pause.
Fencing = real safety: This is the crucial insight (Kleppmann's point): a lease can always be overrun by a pause, so a lock alone is never truly safe. The only robust fix is fencing — the resource orders writes by an increasing token and ignores stale ones. Without it, you have "usually exclusive"; with it, you have correct.
Step 6 · Don't trust one node
Consensus for high availability
So far the lock lives in one store — which is a single point of failure for all coordination, and a naive replicated Redis can even grant the lock twice during failover (the primary dies after granting, a replica that never saw the grant is promoted). How do you make the lock both highly available and correct?
Base correctness-critical locks on a consensus system — etcd or ZooKeeper (Raft/ZAB) — where a majority quorum must agree on the lock holder, so a single node failure never loses or duplicates the lock, and a promoted node already knows the current state. For Redis specifically, Redlock acquires on a majority of independent Redis nodes to reduce single-node risk (though it's debated). The rule: if the lock guards something whose correctness matters, put it on a quorum, and still use fencing.
Quorum over single-node: A single lock store trades away either availability (it dies → all coordination stalls) or safety (async replica failover can double-grant). Consensus (majority agreement) gives both: no single failure loses the lock, and there's one agreed holder. Consensus is slower — which is why you only pay for it when correctness demands it.
Step 7 · Living with the lock
Renewal, reentrancy & granularity
Practical questions remain: a legitimate task that runs longer than one TTL, a holder that needs the lock again recursively, choosing what the lock actually protects, and whether waiters should queue fairly.
Support lease renewal (a heartbeat/watchdog that extends the TTL while the holder is alive and working, so long tasks don't lose the lock — but stop renewing if the work stalls). Allow reentrancy if the same holder may re-acquire (track a count). Choose granularity: lock the narrowest resource (one record, not the whole table) to maximize concurrency. Offer fairness where needed via a queue (ZooKeeper's sequential ephemeral nodes give ordered, fair locks) instead of a thundering-herd retry.
Renew, but honestly: Renewal lets a lease outlast a long job, but it must reflect real progress — a watchdog that blindly extends a stalled holder's lease is dangerous. Narrow granularity buys concurrency; queued (fair) locks avoid starvation and stampedes. These make the lock usable, not just correct.
Step 8 · The sharp edges
Clocks, pauses & "do you even need it?"
Distributed locks live on a bed of dangerous assumptions: clocks drift, processes pause unpredictably (GC, VM migration), networks partition (split brain), and sometimes a lock is the wrong tool entirely.
Don't trust wall clocks for lease timing across machines (skew) — rely on the store's expiry and monotonic tokens, not client clocks. Accept that pauses can exceed any TTL, which is exactly why fencing is mandatory for correctness. Survive partitions with a quorum (a minority side can't grant). And first ask whether you need a lock at all: often idempotency (make the operation safe to run twice), optimistic concurrency (compare-and-swap on a version), or a single-writer partition is simpler and safer than mutual exclusion. Use a lock only when you truly need one-at-a-time.
Design for the unhappy path: Clock skew → don't time by wall clocks. Pause > TTL → fence, always. Partition → quorum. Maybe-don't-lock → idempotency / CAS / single-writer. A distributed lock is a sharp tool built on shaky ground; use fencing and consensus when you must, and avoid it when a cheaper pattern gives the same guarantee.
You did it
You just designed a distributed lock.
- A "locked=true" flag fails twice: it deadlocks when a holder dies, and its check-then-set races.
- Atomic acquire (set-if-absent / SET NX) grants to exactly one racing worker.
- A TTL lease auto-expires a dead holder's lock, so it never deadlocks forever.
- A unique ownership token makes release safe — delete only if the token is still mine.
- A pause can overrun any lease, so fencing tokens let the resource reject stale writers — real safety.
- Correctness-critical locks live on a consensus quorum (etcd/ZooKeeper), never one node.
- Lease renewal, reentrancy, narrow granularity and fairness make it usable; often idempotency/CAS is better.