Design a distributed lock service

I would run the lock service as five servers that agree on every change using a Raft-style log. One server leads. Acquiring a lock appends an entry, which counts as committed once three of the five have stored it, about 3 ms in a region. The entry is then applied to a lock table in the same order on every server, so no failover can forget a lock or grant it twice, and two servers can fail without loss.

Clients open a session with a 10-second lease and send a heartbeat every 3 seconds. All of a client's locks hang off the session, so the load is about 33,000 heartbeats a second rather than 333,000. The leader times sessions on its own monotonic clock, and a new leader gives every session a fresh lease, which can only delay a release, never hasten it. Leases alone are not enough, because a client can pause after checking its lease.

So each grant carries a fencing token that grows with every grant, and the client sends it with every write. The protected resource keeps the highest token it has seen and rejects lower ones. The trade-off is that the resource must support a token check, in exchange for safety that does not depend on timing.

These numbers are assumptions for the exercise, not facts about a real system:

• 1 million locks are held at once by 100,000 client sessions. A lock entry (name, owner, token, expiry) takes about 100 bytes.
• A session has a 10-second time to live, and clients send a heartbeat every 3 seconds.
• The service runs on 5 servers. In one region a network round trip takes 1 ms and a disk sync takes 2 ms.

The arithmetic:

Lock table size

1,000,000 locks × 100 B

100 MB, held in memory on every server

Heartbeats if each lock had its own lease

1,000,000 locks ÷ 3 s

≈ 333,000/s, too many for a consensus leader

Heartbeats with one lease per session

100,000 sessions ÷ 3 s

≈ 33,000/s, ten times fewer

Time to commit a write

Followers: 0.5 ms there + 2 ms sync + 0.5 ms back (a 1 ms round trip) = 3 ms; the leader's own 2 ms sync runs in parallel

≈ 3 ms, well inside the 20 ms target

Quorum and failures

5 servers; a majority is 3, so up to 2 can fail

Writes need 3 of 5 servers, and 2 may be down

Heartbeats a client may miss

Heartbeats at 3, 6 and 9 s of a 10 s lease

2 in a row can be lost before the session expires

The simplest lock is a key in a fast in-memory store: set it only if it does not exist, with an expiry. It is fine for saving effort, such as avoiding two copies of an email. It is not safe for protecting data. If that one node fails, every lock is gone. If you add a replica that copies the data asynchronously, a failover can promote a replica that never heard about a recent lock, and a second client acquires it while the first still believes it holds it. Two holders, with no error anywhere.

Schemes that take the lock on a majority of independent nodes and trust time limits improve on a single node, but their safety still depends on timing assumptions. A process pause or a clock jump can break them. When correctness matters, use agreement, not timing.

A consensus-replicated state machine. Run 3 or 5 servers that use a protocol such as Raft. One server is the leader. Each change (open a session, acquire, release, expire a session) is an entry in a log. The leader sends the entry to the others and counts it committed only when a majority has stored it on disk. Every server applies committed entries in the same order, so every copy of the lock table is the same. Any one failure leaves a majority alive, so nothing is lost.

Leaders can be wrong. A server that was the leader may be cut off from the others, while a new leader is elected by the majority. The old one cannot commit anything, because it cannot reach a majority. It must also not answer "this lock is free" from its stale copy, so lock reads go through the leader with a check that it still leads, or are themselves put through the log.

What it costs. Each write takes a round trip to a majority plus disk syncs, about 3 ms in a region. Adding servers does not add throughput. It makes each commit wait for more acknowledgements, and buys tolerance for more failures. Five servers tolerate two failures and three tolerate one. To scale, split lock names across several independent groups by a hash of the name, so a lock always lives in one group. Keep the group inside one region across three zones, since long distances make every commit slow.

A lock with no expiry is held forever by a crashed client. So every lock is a lease: valid for a limited time and extended by the holder while it is alive.

Sessions. If each lock had its own lease, 1 million locks renewed every 3 seconds is about 333,000 renewals a second, each a write through the consensus leader. Instead, a client opens one session with a 10-second time to live, and all its locks are tied to it. One heartbeat renews them all, so the load is 100,000 sessions ÷ 3 s, about 33,000 a second. Heartbeats do not need a log entry each. The leader can keep session timers in memory and only write a log entry when a session is created or expires.

Who measures time. The leader times each session on its own monotonic clock, as the time since the last heartbeat. Nobody compares wall clocks between machines. The client does the same on its side: it counts 10 seconds on its own clock from the moment it sent the last heartbeat that succeeded, and subtracts a safety margin. The scheme assumes only that clocks tick at roughly the same speed, which is a much weaker claim than synchronised time.

A new leader. After a failover, the new leader does not know how long ago each session last sent a heartbeat. It gives every session a full fresh time to live. That can only make a session last longer than it should, never shorter, so a lock is never granted to a second client early. The cost is that a dead holder's locks may take up to 10 seconds longer to free.

Choosing the time to live. A short lease frees a dead holder's locks quickly, and it expires healthy clients that hit a garbage-collection pause or a network blip. A long lease is calmer and slower to recover. With a 10-second lease and 3-second heartbeats, a client can lose two heartbeats in a row and still renew.

A client that cannot renew in time must stop acting as the holder. Even so, no client can be fully trusted to do that, since a freeze can come right after it checks its lease and before it writes. That gap is what the next topic closes.

The danger is a gap between checking and acting. Client A checks that it still holds the lock, then a garbage-collection pause, a stalled virtual machine or a slow network holds it for 15 seconds. Its lease expires, client B gets the lock and writes. Then A wakes up, believes it still has the lock, and writes over B's work. No amount of checking inside A can close this gap, because the freeze can happen between any two instructions.

The fix is to move the final check to the one place that cannot be paused out of order: the resource being protected. Every time the lock service grants a lock, it issues a fencing token, a number that increases with each grant of that lock. It can come from the log index or a counter kept with the lock entry. Because the log is ordered and replicated, tokens stay strictly increasing even across a leader change.

The client sends the token with every write. The resource remembers the highest token it has accepted for the object, and rejects any request with a lower one. In the example, A holds token 8,412 and B gets 8,413. When A's late write arrives with 8,412, the resource has seen 8,413 and refuses it.

What the resource needs. A way to compare and store a number atomically with the write. A database can do that with a conditional update that checks a version column. An object store can use a conditional write. A file service can keep the token in a small metadata field. The resource never contacts the lock service, so there is no extra failure path.

When fencing is not possible. Some resources cannot check a token, such as a third-party service. Then the lock only reduces the chance of two holders, and it should be used for efficiency, not correctness. Say so in the interview.

The same idea gives leader election. Use a lock named for the role, and treat the token as the leader's epoch. Followers and downstream systems reject any message carrying an older epoch.