Design a distributed lock service (Chubby)

01The design, in the six-step framework

1. Requirements

Chubby is Google's lock service; the interview version asks for coarse-grained locks and leases that many services use to elect leaders and guard shared resources. The emphasis is correctness under partitions, not raw throughput.

Functional

• Acquire and release a named lock, exclusive or shared, with a lease that must be renewed.
• Store small pieces of metadata next to a lock (who holds it, an address), readable by everyone.
• Notify watchers when a lock changes hands or a value changes.
• Fencing: every lock grant carries a monotonically increasing token that protected resources can check.
• Out of scope: fine-grained locks taken thousands of times a second per key; that belongs in the application's database.

Non-functional

• Scale: 100,000 client processes, 50,000 locks, a few thousand lock operations a second, 10 million reads a second of lock metadata through client caches.
• Latency: acquire under 50 ms within a region; reads from cache under 1 ms.
• Safety: at no instant do two clients believe they hold the same exclusive lock in a way that can corrupt a protected resource.
• Availability: survives the loss of any two of five servers; failover under 30 seconds.

2. Core entities

• Node: a path in a namespace (/services/payments/leader), with a small value, an ACL and a version.
• Lock: a node in locked mode: holder session, mode (exclusive or shared), fencing token (the lock's generation number), acquired at.
• Session: client id, lease expiry, the handles it holds; the unit of liveness.
• Watch: session, node path, event types (lock change, value change, deletion).

3. API

• open(path) → handle; acquire(handle, mode) → fencing token or waits; release(handle).
• get(handle), set(handle, value, expected_version) for metadata with compare-and-swap.
• watch(handle, events) and keep_alive(session) (the client library sends these automatically).
• Administrative: GET /sessions, POST /sessions/{id}/kill.

4. High-level design

1. Five replicas form a Paxos group and elect a leader with a lease; clients find the leader through DNS and a redirect.
2. An acquire is a write: the leader proposes "lock L held by session S, generation g+1" to the group, and replies once a majority has logged it, returning g+1 as the fencing token.
3. Reads come from the client library's cache; the leader tracks which clients cache which nodes and sends invalidations before acknowledging a change, so caches are consistent.
4. The library sends keep-alives; the session lease is extended on the leader and, at a coarser interval, written to the log so a new leader knows which sessions are alive.

5. Deep dives

How is mutual exclusion kept safe when clocks and networks lie?

A client holds a lock only while its session lease is valid by its own clock, which it treats conservatively (it assumes its lease expires earlier than the server's view by the maximum clock drift and message delay). When it cannot reach the leader to renew, it enters a grace period and then assumes the lock is lost, stopping work on the protected resource. The server, in turn, only expires a session after the lease plus a margin. The remaining gap, a paused process that wakes up believing it holds a lock, is closed by fencing: every grant carries a generation number, protected resources store the highest number they have seen and reject writes with a lower one. Say that leases alone are not enough and that fencing tokens make the resource the final arbiter (locks and leases).

What happens during leader failover?

Followers detect a dead leader when its lease expires and elect a new one through leader election in the Paxos group. The new leader rebuilds lock state from the replicated log, but sessions and their keep-alives were only partially logged, so it starts a grace period: clients reconnect, present their session ids, and the leader honours any session whose lease has not expired by its own conservative clock; those that do not reconnect within the grace period are expired and their locks released with watchers notified. Clients observe a failover as a brief stall (10 to 30 seconds) during which they keep their locks but cannot acquire new ones. The clock assumption is bounded drift, not synchrony; the design works with drift of hundreds of milliseconds because leases are seconds long.

Why coarse-grained locks and a caching client library?

A consensus write costs a few milliseconds and a majority round trip; a system taking fine-grained locks at 100,000 a second would need a different design (locks in the application's sharded database with leases, or optimistic concurrency). Chubby-style locks are meant to be held for hours (a leader lease, a partition assignment), so thousands of operations a second suffice and the critical path is reads: a service's address stored next to its leader lock, read by every caller on every request. The client cache with leader-driven invalidation makes those reads local and consistent, and watches turn polling into push. This is the design decision that makes a single Paxos group enough for a whole data centre.

How do leader election and configuration storage build on it?

Leader election is just an exclusive lock: every candidate tries to acquire /services/x/leader; the one that succeeds writes its address into the node's value and the others watch it. When the leader's session dies, the lock releases, watchers wake, and the next acquirer wins. The fencing token doubles as the epoch number the new leader uses in its own protocol. Small configuration (a few KB per node) lives in node values with compare-and-swap, which gives atomic updates and lets a rollout tool flip a value that a million cached readers see within a second through invalidations. Watch delivery is at-least-once and ordered per session; clients reconcile by reading the current value after an event rather than trusting event contents (failure detection and recovery stay simple).

6. What a strong answer sounds like

• Say early that the write rate is small and reads are huge, so it is one consensus group plus a consistent client cache.
• Explain leases with conservative client clocks and fencing tokens together; one without the other is a known bug.
• Walk through failover with the session grace period and what clients observe.
• Show leader election and configuration as applications of the primitive.
• Follow-ups to expect: scaling beyond one group (partition the namespace across several Paxos groups by path prefix), cross-region use (one group per region; cross-region locks are rare and slow by design), and ACLs (per-node, checked on the leader).
• A common mistake is to implement a lock as a key in a cache with an expiry and no fencing; the interviewer will ask about a paused client.

02Where this question was reported

• Blind · Google can dive very deeply; harder than other companies
• GitHub · 'Design Google Chubby Locking service' (Hard).