The whole design, in writing
Learn system design by building a distributed lock (mutual exclusion across machines) like Redis locks, Redlock, or etcd/ZooKeeper locks step by step. An interactive guide covering why a DB flag gets stuck, atomic acquire, TTL leases that auto-release a dead holder, ownership tokens and safe release, the fencing-token problem, consensus-based locks for high availability, lease renewal, and the unhappy paths (clock skew, GC pauses, split brain).
Every step of the build above, written out: the problem each piece solves, the option that was taken and the ones that were not, the numbers, and how it fails in production.
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.
What the new pieces do
- Worker Aclient
- A process on one machine that needs exclusive access to a resource — run this cron once, edit this record alone.
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?
A DB flag "locked=true" as a lock. What are the two fatal flaws?
One boolean is nothing. The fatal flaws are that a crashed holder never sets it back to false (the lock is stuck forever), and a non-atomic check-then-set lets two workers both see "false" and both acquire.
Speed isn't the issue. The real problems are a stuck lock after a crash (no auto-release) and a race where check-then-set isn't atomic, so two workers both 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.
Why this piece earns its place
The reflex patch is worth naming, because it is what most teams reach for next: keep the flag, add a locked_at column, and run a sweeper that clears any row older than some age. That is a TTL built out of the wrong materials. The sweeper is itself a process that can crash, so the thing guaranteeing liveness now needs its own liveness guarantee — and underneath it the acquire is still a read followed by a write, so the original race survives the patch completely untouched. What the sweeper is not wrong about is expiry itself: no age-based rule can tell a dead holder from a slow one, and neither can the store-side lease this design goes on to ship. That ambiguity is inherent to expiry, which is why the answer to it arrives at step 5 as a check the resource performs, rather than as a better-tuned timer. The other assumption hiding here is that the lock belongs in the application database because the database is already there. That’s convenient right up to the point where every worker on every machine depends on it for permission to start work: a table nobody thought of as infrastructure becomes the busiest coordination point you own, contended by exactly the workers you were trying to spread out.
What the new pieces do
- Worker Bclient
- A competing process, on another machine. The whole point of the lock is that only one of A and B proceeds at a time.
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?
Two workers acquire at the same instant. How do you grant to exactly one?
A single atomic operation — set the lock key only if absent — is decided by the store indivisibly, so exactly one of the racing workers succeeds and the other sees "already set". No check-then-set gap for a race to slip through.
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.
The workers can't see each other (that's the whole problem) and can't be trusted to coordinate. A single authority (the store) must grant atomically.
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.
Why this piece earns its place
Atomicity settles who wins; it says nothing about what the losers do, and that’s where this step bites under load. Every worker told already held retries, and if they all retry on the same interval they arrive together on the next tick and keep arriving together — a herd that pounds the store hardest exactly when contention is worst. Randomized backoff between attempts breaks the lockstep, and a bounded wait, after which the caller gives up and reports rather than spinning forever, keeps a pile of blocked jobs from becoming an outage. The sharper problem is that SET NX can succeed and its reply can be lost. The worker sees a timeout and has no idea whether it holds the lock. Retry blindly and it fails — the key exists, its own key — so it walks away from a lock it actually owns, which now sits held with nobody doing the work. So generate the identifier for this attempt on the client before the call, and a retry can ask whether the current holder is already me instead of guessing.
- SET NXset-if-absent
- 1 winnerper race
- atomicno check-then-set gap
What the new pieces do
- Lock Servicegateway
- Grants the lock to exactly one caller via an atomic acquire, hands back an ownership token, and releases safely.
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?
The holder crashes while holding the lock. How does it ever get released?
Manual cleanup is far too slow and error-prone for something that can happen constantly. The lock must auto-release without any live process or human.
Waiting doesn't help — a dead holder never releases, so the wait is infinite. The lock itself must expire.
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".
Why this piece earns its place
The TTL is the one number you have to defend, and it’s pulled in two directions at once. Make it short and you get false expiries: a holder that was alive and working loses the lock, a second worker starts the same job, and overlap becomes routine rather than rare. Make it long and it becomes your recovery time — when a holder really does die, everyone else waits out the whole lease before anything moves, so the TTL is the worst-case stall you sign up for on every crash. That means it should come from the tail of how long the protected work actually takes, not the average; sizing to the average guarantees that the slowest runs, which are usually the ones under load, are the runs that get cut off. Two things the lease is not: it isn’t timed by the holder — expiry is decided by the store, so a holder trusting its own stopwatch is trusting a clock nobody else agrees with — and watching your own remaining lease makes an overrun rarer, never impossible.
- TTLbounded lease
- auto-expirefrees a dead holder
- ≤ Tmax hold time
What the new pieces do
- Lock Storedata
- Holds the lock: a key, the owner's token, and a TTL so a dead holder's lock auto-expires. The contended cell.
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?
A's lease expired and B now holds the lock. A finishes and calls release. What must happen?
On acquire, the holder is given a unique token stored with the lock. Release checks "is the current token still mine?" and deletes only if so — done atomically — so A's late release can't delete B's lock. A just learns it no longer holds it.
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.
A genuinely believes it still holds the lock (it doesn't know its lease expired), so trust isn't enough. The store must verify the token so a stale owner can't release the current one.
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.
Why this piece earns its place
Two details decide whether this actually holds. First, the token has to be genuinely unique per acquisition, and the convenient choices aren’t: hostname plus process id repeats the moment a container is rescheduled onto the same host or a supervisor restarts a crashed worker into the same slot — and then a stale release matches a live lock and deletes it, the exact bug the token was added to prevent, only harder to see. A random identifier minted per attempt is the cheap correct answer. Second, the check and the delete have to be one operation on the store. Reading the token, comparing it in the client, then issuing the delete is two round trips with a gap in the middle, and that gap is precisely long enough for the lease to expire and someone else to acquire. It’s also worth saying that release is an optimization, not a requirement: if it fails, nothing is broken, because the lease still expires. A holder that can’t release should log it and move on rather than block on retries.
- unique tokenper acquire
- release if token==mineatomic
- no blind deletestale owner is safe
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?
A paused past its lease; B acquired; A wakes and writes. How does the resource reject A?
A pause can exceed ANY fixed TTL, and shorter TTLs cause more false expiries. You can't eliminate the race with timing — you need the resource itself to reject stale writers.
A can check and be told "you hold it" and then pause again before the write — the check-to-write gap reopens the hole. The resource, not the client, must enforce ordering.
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.
Why this piece earns its place
The uncomfortable part of fencing is that the lock can’t do it for you — it needs the resource to participate. A relational database can, cheaply: keep the highest accepted token in a column and make every write a conditional update that also asserts the incoming token is greater, in the same transaction as the write itself. Object stores and some queues expose a conditional-write primitive you can hang it on. But plenty of things you’d like to protect can’t: a third-party API, a shell script writing to a file share, a legacy service with no version column and no notion of an owner. For those, be honest about what you have — a lock that is usually exclusive — and move the exclusivity to a layer that can actually enforce it. The token also has to come from somewhere monotonic across failures. A counter incremented in a store that can restart from an older snapshot will hand out a number it already gave away, which silently destroys the ordering the resource is relying on.
- token↑monotonic per grant
- resourcerejects lower tokens
- safeeven across a pause
What the new pieces do
- Fencingservice
- Issues an ever-increasing fencing token with each grant, so the protected resource can reject a stale holder's writes.
- Resourcedata
- The thing the lock guards — a record, a file, a job. It checks the fencing token and rejects anything stale.
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.
Why this piece earns its place
A quorum changes the operational shape of the lock, and two decisions get made badly by default. First, membership: keep the cluster small and odd-numbered, because a majority of an even set tolerates no more failures than the odd size below it while costing another participant on every commit. Every grant has to reach a majority and be durable there, so adding members buys failure tolerance and pays for it in acquire latency — which becomes very visible in a system that takes a lock per small task instead of per batch of work. Second, placement and reads. A majority that all lives in one rack or one availability zone is a majority that disappears together, which is the failure you bought the quorum to survive. And it’s tempting to read lock state from whichever member is nearest, since reads are cheap there — but a follower can be behind, so it will happily report a holder that has already changed. Anything that decides who holds the lock has to go through the leader or a linearizable read.
- quorummajority agrees
- etcd / ZooKeeperRaft / ZAB
- no double-granton failover
What the new pieces do
- Quorumdata
- A replicated majority (etcd/ZooKeeper/Redlock) that agrees on the lock holder, so no single node failure loses 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.
Why this piece earns its place
Renewal quietly reintroduces the failure from the very first step. A watchdog on its own thread keeps extending the lease while the worker thread is wedged on a hung connection or an infinite retry, and now the lock is held indefinitely by a process that is technically alive and doing nothing — the stuck flag again, only with a pulse. So the watchdog must not renew on a timer alone: have the work publish progress, a counter it bumps as it finishes units, renew only while that counter moves, and put a ceiling on total extensions so even a plausible-looking stall eventually gives the lock back. The renewal interval has its own trap. Renewing once near the end of the lease means a single lost packet costs you the lock, so renew at a fraction of the TTL and treat a failed renewal as serious rather than routine. And the rule that matters most: when renewal fails, the holder stops working immediately. Carrying on while retrying is the choice that produces two workers.
- heartbeatextend while alive
- reentrantsame holder re-acquires
- narrowlock least, concur more
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.
Why this piece earns its place
The decision this step really asks for is one sentence long and almost never written down: what happens if two run at once? If the answer is duplicate work — a report generated twice, a cache warmed twice — the lock is an efficiency measure and is allowed to fail. If the answer is a double payment or a corrupted record, it’s a correctness requirement, and a lock alone can’t deliver it, because everything above only narrows the window. In that case the resource has to reject the duplicate on its own terms — and once it does, the lock has become an optimization on top of a guarantee that already holds without it. That same classification answers the question you’ll be asked during an incident: what do we do when the coordination store is unreachable? An efficiency lock should fail open and run anyway, accepting some duplicate work. A correctness lock has to fail closed and stall. Teams that never made the call find out which one they built at the worst possible moment, because the default is whatever the client library happens to do on a timeout.
You did it
You just designed a distributed lock.
Everything you assembled, in order
- 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.