Distributed locks and leases
Mutual exclusion across machines, and why a lease needs a clock.
01The intuition
The problem it solves
A cinema has one seat 14C left. Two people, on two phones, press Buy at the same second. Two servers handle the two requests. Each reads "14C is free", each writes "14C sold", each charges a card. Two tickets, one seat, and an argument at the door. In a single program this is the classic race condition and a mutex fixes it: one thread holds the lock, the other waits. Across two machines there is no shared memory to put the mutex in.
A distributed lock is a mutex that lives in a service both machines can reach: "I hold 14C" is a record somewhere, created by one server and refused to the other. The twist that makes it hard is that a machine holding the lock can crash, or pause for thirty seconds, or lose its network, and the lock must not stay held forever, nor be handed to someone else while the first holder is still quietly working.
Build it one piece at a time
Step 1: a key that only one can create. Use a store with an atomic create-if-absent, such as Redis SET lock:14C owner=A NX, or a row with a unique constraint. Server A's command succeeds; server B's fails. A does the work and deletes the key.
Step 2: a lease, so crashes do not hold the seat forever. Add an expiry: SET lock:14C owner=A NX PX 10000, ten seconds. If A crashes, the key vanishes on its own and B can try again. A long task renews the lease periodically.
| Time | lock:14C | Server A | Server B |
|---|---|---|---|
| 0.000 s | owner=A, expires 10 s | holds, checks seat, charges | create failed, shows "someone is buying" |
| 0.400 s | deleted by A | done | retries, create succeeds, sees 14C sold |
Step 3: release only your own lock. A slow A finishes at 11 s, after its lease expired and B took the lock at 10 s. A's plain delete would remove B's lock. So the delete must check the owner: delete only if owner=A, in one atomic script. Store a random token as the owner, not just a name, so an old process of A cannot release a new A's lock.
Step 4: fence the slow holder. Step 3 stops A from releasing B's lock, but it does not stop A from writing "14C sold" at 11 s on the strength of a lock it no longer holds. The fix is a fencing token: the lock service hands out an increasing number with each grant (A gets 41, B gets 42), the holder sends the token with every write, and the seat database rejects a write whose token is lower than the last one it saw. Now A's late write with 41 is refused. Without fencing, a lease-based lock is only advisory.
Step 5: make the lock service itself survive. A single Redis is a single point of failure, and asynchronous replication can lose a lock on failover, granting it twice. For locks that guard money or data, use a consensus-backed store (ZooKeeper, etcd, Chubby), where a grant is committed to a majority before it is acknowledged. For locks that only reduce duplicate work, a single cache node is fine and cheaper.
Why it works, with the numbers
The invariant is mutual exclusion in the eyes of the protected resource: for each lock, writes accepted by the resource come from at most one holder at a time, in token order. The lease bounds the damage of a crash:
maximum time a crashed holder blocks others = lease length, typically 5–30 s; renewal interval = lease / 3
A consensus-backed lock costs a majority round trip per grant, about 1–2 ms in one data center and some thousands of grants a second, so locks are taken per seat or per order, never per request. The failure modes: a lease shorter than the work (the holder loses the lock mid-task), clocks on the holder that disagree with the lock service about when the lease ends (fencing is the cure), and a lock service that is unreachable, which stops all guarded work by design.
The trade-off you must say out loud
A lock adds a round trip and a bottleneck in exchange for correctness. Say what you lock (one seat, not the whole show), the lease length, that releases check ownership, and whether the resource checks fencing tokens. Say which store backs the lock and why. The follow-up is "can you avoid the lock", and often the answer is yes: a conditional database update, UPDATE seats SET sold=1 WHERE id='14C' AND sold=0, is atomic without any lock service, and the lock is only worth it when the work spans several steps or services.
Where it shows up in the 100 Google problems
- Ticketmaster: a ten-minute hold on a seat is a lease; the confirmation carries the token.
- Online auction: a short lock per item serialises bids that arrive in the same millisecond, or a single partition does the same job without a lock.
- Job scheduler: a claim on a run is a lock with a lease, renewed by the worker's heartbeat.
- Distributed lock service: the service itself: consensus replicas, leases, sequencers (fencing tokens) and the small-file namespace.