Distributed Lock

The problem

"Design a lock service." Thousands of servers ask it for named locks, such as account-42, and at most one server may hold each lock: billing jobs that must never work on the same account at once, a scheduler that must run on exactly one machine.

The interview is about what goes wrong: a holder that crashes and never releases, a holder that freezes and wakes up after its lock has passed to someone else, and a lock server that dies. Shared read-write locks and fair queues of waiting servers are extras to park.

The numbers

From the interviewer: 20,000 workers, each starting about 3 jobs a minute, and every job takes one lock and releases it when done. That is 60,000 jobs a minute, so 1,000 jobs a second, each writing twice (take and release): about 2,000 writes a second. Most jobs finish within a second or two, before their first renewal at 3 s, so renewals add little.

One Redis node handles about 100,000 operations a second; a consensus group, where every write waits for a majority, say about 10,000 writes a second. Both have room, so the choice is about correctness, not speed.

Leases: a lock that frees itself

call                                     answer
acquire("account-42", lease = 10 s)      granted, token 33
renew("account-42", token 33)            lease ends 10 s from now
release("account-42", token 33)          free

A crashed holder never releases its lock, and a finally block doesn't help: it runs when the job throws an error, not when the machine dies. So every lock gets a lease: it ends after 10 s unless the holder renews it. Renewing every 3 s lets a renewal or two fail, and a job can run for an hour by renewing.

A lease as long as the longest job, an hour, would block an account for up to an hour after a crash; a very short one means more renewals and more short pauses that lose the lock. Seconds is the usual middle. Renew and release name the token, so a holder that lost its lock can't free the next holder's.

The paused holder and fencing tokens

A holder can freeze, in a long garbage-collection pause, while its lease runs out:

time   event
0 s    Server 1 takes account-42: token 33, lease to 10 s
3 s    Server 1 renews: lease to 13 s
4 s    Server 1 freezes (garbage collection)
13 s   Server 1's lease runs out
14 s   Server 2 takes account-42: token 34, lease to 24 s
15 s   Server 2 writes the invoice with token 34: accepted
19 s   Server 1 wakes up, writes with token 33: refused

Without that check, Server 1's write would replace Server 2's invoice with a stale one. Server 1 can't prevent it: a frozen server renews nothing, and checking the lease just before writing leaves a gap a pause can fall into. Nor can the lock service, because the write goes straight to the billing database.

So the place the data lands must check. Every grant carries a fencing token, a number that only goes up, and the database refuses a lower token than it has seen. The write becomes a conditional update, UPDATE invoices SET …, token = 33 WHERE account = 42 AND token <= 33, which changes 0 rows once 34 is stored.

One Redis node or a consensus group

A first draft keeps each lock as a Redis key, set only if nobody holds it: fast, but one machine. If it saves to disk only every second or so, a common setup, a restart can forget locks it just granted; while it is down, nobody can take or renew a lock. A replica doesn't fix it: it gets each change after Redis has answered, so a lock granted just before a crash is missing there and is granted again. Two holders, and even token 33 handed out twice.

For locks that protect correctness, use a consensus group of 3 or 5 servers that grants a lock only once a majority has stored it. Any later leader of the group has every such lock, so nothing is granted twice; 3 servers survive 1 down, 5 survive 2. etcd and ZooKeeper are groups like this: they free a lock when its holder stops checking in, and number every change, a ready fencing token. One Redis node is still fine when a lock only saves work, and a job now and then done twice harms nothing.

When you don't need a lock

A lock service is one more system to run. When one row decides, the database settles the race in one step, as in Concurrency and Locks. Selling one of a flash sale's last 10 items is UPDATE … SET left = left - 1 WHERE left > 0; taking $50 from a wallet is WHERE balance >= 50. A unique key turns away a second user named neo, or a retried payment's idempotency key. Keep the lock service for work that spans many steps or systems.

Same pattern as Consensus and Leader Election

A lock is a leader for one job. The rule carries over (never two at once), and so does what makes it hard: a crashed, frozen or cut-off holder all look the same. So do the answers: a majority, and a number that only grows, checked by whoever receives the request, as terms stop an old leader.

Summary

• Scope: thousands of named locks, one holder each, freed when a holder dies.
• Numbers: about 2,000 lock writes a second.
• Leases: 10 s, renewed every 3 s while working.
• Fencing: every grant gets a token; the storage refuses a lower one.
• Where locks live: a group of 3 or 5 servers; a majority stores each lock.
• No lock: a conditional update or a unique key when one row decides.