Distributed Locks & Leases

The gossip lesson ended at a door this course has been circling for a long time: "you need to hold something, exclusively, right now, and safely let go of it even if you die holding it." Way back in Fundamentals of System Design, the race-conditions lesson drew the ladder in one sentence: "The in-memory lock becomes a database transaction, which becomes a distributed lock, which becomes a consensus protocol like Raft." You are now standing on the top rung, and this lesson is about why it wobbles.

On a single machine, a lock is a solved problem, because the operating system is a little god: if a thread dies holding a mutex, the OS knows: it cleans up, the lock frees, life goes on. Cross the network and the god is gone. A worker that grabs a distributed lock and then dies doesn't release anything. It doesn't report anything. It just goes silent, and you spent an entire section learning that silence is unreadable: dead, slow, or unreachable, no one can say. A lock whose holder might be any of those three is a lock nobody else can ever safely take.

So distributed locks get rebuilt around one honest admission: the lock must be able to outlive its owner's death — and take itself back. That one requirement drags in everything this section taught: clocks (an expiry is a bet on physical time), failure detection (a missed renewal is a heartbeat verdict), and finally the fencing token from the split-brain lesson, which has been waiting nine lessons for this exact moment. By the end you'll know why the obvious lock deadlocks, why the fixed lock races, which of two very different jobs your lock is actually doing, and the one mechanism that makes the dangerous job safe.

Build the obvious thing first and let it fail honestly.

Version one: a key in a store. Whoever writes lock:invoices = worker-A first holds the lock; delete it to release. (This is SET key NX — you used exactly this in the caching lessons to stop a stampede.) It works right up until worker A dies mid-job. Nobody deletes the key. The lock is held by a corpse, forever, and every other worker queues politely behind a ghost. You've built a deadlock with extra steps.

Version two: add a clock. Give the key an expiry: lock:invoices = worker-A, expires in 10 seconds. Now death cures itself — a dead holder stops mattering ten seconds after it stops breathing. This lock-plus-clock has a proper name and a birthday: the lease, from Gray and Cheriton's 1989 paper, which framed it as the fundamental time-based tool for surviving failures, and noted the dial you're already reaching for: shorter leases bound the damage a dead holder can do, at the price of more renewal traffic.

Because of course there's renewal. Real jobs outlive any sensible expiry, so a healthy holder renews: every few seconds, a little watchdog thread extends the lease. Notice what you've just rebuilt: renewal is a heartbeat, the expiry is a failure detector's timeout, and the familiar bet from the heartbeats lesson comes with it: renew aggressively and a network hiccup steals your lock; renew lazily and a real death holds the door long after the wake.

You've also already operated this machine in production without ceremony: the Postgres failover codelab's supervisor, Patroni, holds a leader key in a consensus store and demotes any Postgres whose lease has expired: a lease deciding who gets to be primary. And notice which clock all of this runs on. This lease is valid for ten seconds is physical time, the wall-clock kind the time lessons taught you to hold with suspicion. File that thought; it comes back armed.

Version two feels finished. It has one flaw, and the flaw has a shape you can't patch away.

Here is the most famous failure story in distributed locking, and by now you own every part needed to tell it.

Worker A acquires the lease on the invoice job — ten seconds, renewing every three. It reads the data, computes, and reaches for the write. And then A stops. Not crashes: stops. A garbage-collection pause. A virtual machine getting migrated. Swap. A laptop lid, a SIGSTOP, a kernel hiccup — the timing failures from the failure-models lesson, any of them. A is frozen mid-stride with the write queued in its hand.

The watchdog is frozen too, so nothing renews. Ten seconds pass. The lease expires — honestly and correctly: from the lock service's view, the holder went silent past its deadline, which is the one signal it has, and the whole point of version two was that silence frees the lock. Worker B asks, and the service says yes. B holds the lease, legitimately. B does the job. B writes.

Then A wakes up. And here is the sentence the whole lesson turns on: A has no idea it was ever asleep. A pause doesn't feel like anything from the inside — the next instruction simply runs. The next instruction is the write. It lands on top of B's work, and the invoice data is now an interleaving of two runs that each believed, with valid paperwork at the time, that they were alone.

Before reaching for a patch, notice that the patches dissolve. Check the lease before writing? The pause can land between the check and the write: the gap you're patching is inside the patch. Renew more often? A frozen watchdog renews exactly as often as a dead one: never. Longer leases? Now real deaths hold the door longer, and the pause can outlast any number you pick anyway. The uncomfortable truth is structural: a lease plus a pause equals two holders, sooner or later, and no client-side cleverness closes the window, because the client is precisely the thing that can't be trusted to know what time it is. You proved this in the time lessons; here it is with an invoice attached.

So two holders will eventually happen. The engineering question — the one an interviewer is actually probing when locks come up — is: what does it cost when it does? That question forks every lock in production into one of two species.

Efficiency locks. The lock exists to avoid duplicate work. Two cron runners both firing the nightly report; two cache fillers both recomputing the same page (the stampede lock from the caching lessons was exactly this). If the window opens and both run, you burn some CPU and maybe send an email twice. Annoying, costed in dollars, self-healing. For this species, version two is the right engineering: one Redis key, SET NX, an expiry, done. Adding consensus-grade machinery here is buying a bank vault for a coat check.

Correctness locks. The lock is the only thing standing between you and corrupted state: two workers writing the same invoice file, two migrations mutating the same schema, two chargers billing the same card. If the window opens here, you don't lose CPU, you lose truth — and the section's founding rule, one answer never taken back, is violated by your own infrastructure.

Be brutally honest about which species you're holding, because the fork decides everything downstream: the efficiency branch is allowed to be cheap and slightly wrong; the correctness branch is not allowed to lean on a lease alone, no matter how the lease is implemented: ten Redis nodes or a perfect consensus cluster, the pause story above never once blamed the lock service. The lease did its job. The client is the liar. Which means the fix cannot live in the client.

The fix lives where the damage happens: at the resource itself. You met it nine lessons ago guarding a database against a zombie primary, and it transfers to locks without changing a single idea: the fencing token — authority as a number that only goes up.

Two small changes. First, the lock service stamps every grant with a counter: A's lease arrives as token 33, and when B acquires after the expiry, B's lease says token 34. Monotonic, never reused: the split-brain lesson's rising number, the Lamport clock you later learned it secretly was, now dispensed by a lock service like tickets at a deli. Second, the storage — the file, the database, the API taking the writes — records the highest token it has seen and refuses anything lower.

Replay the disaster against the gate. A freezes at token 33. B acquires at 34 and writes; the gate stamps 34 into its memory. A wakes and its late write walks up carrying 33, and the gate doesn't negotiate: it has seen 34, so 33 bounces. The pause still happened. The lease still expired. There were still, briefly and unavoidably, two holders. Fencing doesn't prevent the second holder; it makes the second holder safe: the overlap is defused instead of denied, which is exactly the trade the split-brain lesson promised: quorum stops the second history; fencing stops the old one from coming back.

Pay the honest bill too, the same one as last time: fencing is invasive. Every resource the lock protects must store a number and run a comparison — your storage layer becomes part of the locking protocol. When the resource can check (databases with conditional writes, object stores with preconditions, your own APIs), arm it, always. When it truly can't, you're back on the efficiency branch whether you like it or not, plus the failure-detection lesson's consolation prizes: idempotent writes so replays are harmless, and jobs designed so a double-run collides softly. And note the one exception you already know: consensus systems don't bolt this gate on, because — as the Raft lesson put it, the door check is built into the protocol itself; every message carries the term. A lock service built on consensus is a machine for exporting that discipline to things that never learned it.

The story deserves to be lived once. Below is the whole cast: two workers with jobs you write yourself, one lease with a visible pulse, and one storage gate with the only toggle that matters.

Break it like this:

1. Run the happy path. Give worker A a value, acquire, and watch the lease bar drain and snap back with each renewal. Write. Release. Boring, correct, exactly what version two promised.
2. Now stage the disaster. Acquire with A — and pause it mid-job. Watch the renewals stop and the bar run all the way out. The lease expires honestly: the service isn't broken, it's doing precisely what expiry is for.
3. Hand the world to B. Acquire with B — note its token is one higher — and write. Everything B did is legitimate.
4. Wake the zombie with fencing OFF. A finishes the write it was holding all along. Watch the ledger turn red: interleaved runs, corrupted truth, and not one component malfunctioned. That's the part to sit with.
5. Reset, replay, fencing ON. Same pause, same expiry, same two holders — but this time the gate reads 33, remembers 34, and the stale write bounces off the door. The ledger stays whole. The toggle didn't prevent the overlap; it made the overlap cost nothing.

One more thing to notice while you're in there: at no point can worker A discover it lost the lease before the gate tells it. Every fix that works lives on the resource's side of the wall. That asymmetry is the lesson.

Now you're equipped for the most instructive argument in this corner of the field, because in 2016 two people you've already met had it in public.

Redis ships a recipe called Redlock: acquire the lock by winning a majority of five independent Redis nodes (majorities — you know why five and why majority), with expiry times doing the lease work and a large random value identifying each holder. It's clock-dependent by design, and it's deployed all over the industry.

Martin Kleppmann — whose fencing-token treatment this course has been carrying since the split-brain lesson — published a critique with two blades. First, Redlock's safety leans on timing assumptions: bounded network delay, bounded pauses, well-behaved clocks. You've spent a whole course learning what those assumptions are worth; a long GC pause defeats Redlock the same way it defeated version two. Second, and sharper: Redlock hands out random tokens, not rising ones, and randomness can't fence. Two random values don't tell the gate which holder is stale; only a number that goes up does. No fencing, no correctness lock.

Salvatore Sanfilippo — antirez, Redis's creator — pushed back with a practitioner's argument: for the workloads people actually reach for Redlock, mutual exclusion is an optimization, and in many real deployments there's no gate-capable resource to fence anyway; when the resource can't check tokens, the extra machinery buys little.

Here's the grown-up resolution, and notice it's not diplomacy: it's the fork from two sections ago doing its job: they were answering different questions. For efficiency locks, antirez is right: Redlock (or one Redis node, honestly) is fine, because the failure mode was priced in dollars from the start. For correctness locks, Kleppmann is right and it isn't close: no fencing, no safety, and no quantity of independent Redis nodes changes that, because the vulnerability was never in the lock — it was in the sleeping client. Ask the fork's question first, and the controversy answers itself.

The shapes you'll actually meet:

• Google's Chubby is the ancestor: the lock service whose war stories gave you Paxos Made Live. Its design is instructive in every choice — locks are coarse-grained (held for hours or days, guarding who is the leader of this service, not who touches this row), advisory (honest clients check; the lock doesn't physically bar anyone, which is why fencing still matters), and served through sessions: a client's whole relationship with Chubby is one big lease, kept alive by keep-alives, everything it holds evaporating together if the session dies. Built on consensus underneath, tuned for availability over speed.
• ZooKeeper carries the same soul: locks as ephemeral nodes that vanish when the holder's session dies, and its transaction counter — the zxid you met in the split-brain lesson — is a ready-made token fountain.
• etcd, Raft wearing an API as the roll call had it, grants leases as first-class objects that keys can be attached to; everything a dead client held disappears at expiry.
• Patroni, from the failover codelab, is what it looks like when this machinery earns its keep: the leader key in a consensus store, a lease deciding which Postgres may call itself primary — a distributed lock quietly running your database's succession.

Squint at the list and the pattern is loud: every serious lock service is a consensus cluster wearing a lock-shaped API. Chubby is Paxos; ZooKeeper runs its own Paxos-family protocol; etcd is Raft. The ladder from the fundamentals course really did end where it said it would — your lock.acquire() at the top rung is a replicated log underneath, doing elections and majority commits so that the word acquire can mean something on a network that lies. How you actually drive these services — the recipes, the watches, the patterns — is exactly the next lesson: ZooKeeper & etcd in Practice.

• A distributed lock must outlive its owner's death. No OS cleans up after a dead holder, so the lock takes itself back: lock + clock = lease (1989), renewed by a watchdog heartbeat, expiring on the wall clock you rightly distrust.
• A lease plus a pause equals two holders. The frozen client can't renew, can't check, and can't know it slept — the write in its hand lands late and no client-side patch closes the window.
• Ask the fork's question first. Efficiency lock (double-run wastes work): one key, SET NX, expiry: done, correctly cheap. Correctness lock (double-run corrupts): a lease alone is never enough.
• Fencing makes the second holder safe. Rising tokens from the lock service, a comparison at the resource: 33 bounces off a gate that has seen 34. It doesn't prevent the overlap — it defuses it. And yes, it's invasive: the resource joins the protocol.
• The Redlock affair is the fork in costume. Timing assumptions plus random tokens mean Redlock can't fence: fine for efficiency, disqualified for correctness. Both sides of the famous argument were right about different species.
• Every serious lock service is consensus underneath. Chubby (coarse, advisory, sessions), ZooKeeper (ephemeral nodes, zxid tokens), etcd (leases on Raft), Patroni's leader key. The top rung of the ladder stands on everything this section built.

You now know what a coordination service must be on the inside: a consensus core, sessions and leases at the rim, a token fountain for the honest resources. What's left is to actually hold the steering wheel — the znodes and watches, the recipes for locks and elections and configuration, the operational habits that keep the coordinator itself from becoming your outage. That's next: ZooKeeper & etcd in Practice.