Design a Distributed Lock Service

A Chubby-style lock service for 50 k processes: leases, leader election, fencing tokens and watched config, never letting two holders act at once.

Last updated 2026-10-26. Difficulty: hard. Patterns: consensus, leases, fencing-tokens, leader-election, watches. Reported at Google, Amazon, Microsoft, Meta, Uber, Databricks.

Functional requirements

• Acquire and release a named lock. Exclusive or shared, blocking or try-lock with a timeout. Locks are advisory: they coordinate cooperating processes, they do not stop anyone touching the data.
• Sessions kept alive by KeepAlives. Every lock and ephemeral node belongs to a client session. When the KeepAlives stop for a full lease, the session ends and everything it held is released.
• A fencing token with every grant. A number that only goes up, so the protected resource can reject a holder that lost the lock without noticing.
• Leader election and membership. Built from ephemeral sequential nodes: the lowest number leads, its node holds the leader’s address, and the set of nodes is the live membership.
• Small configuration values. Values up to 64 KB with a version, read by many and written rarely, with compare-and-set on the version.
• Watches. A one-shot notification when a node’s value changes, its children change or it is deleted, delivered on the client’s session.
• Consistent client caching. Clients cache values and the service invalidates them before a write completes, so a cached read is never stale while the session is healthy.
• Out of scope. Storing application data or large blobs, a general-purpose key-value store, locks replicated across regions beyond one small global cell, and the service-mesh side of service discovery.

Non-functional requirements

• Safety (never two holders acting). The requirement that drives the hardest trade-off: when the service cannot be sure, it waits (a lock stays held up to a lease after its holder dies, a cell without a majority stops granting) rather than ever granting twice. Fencing makes the guarantee hold even against paused clients.
• Availability (99.99 % per cell). Survives two replica failures or the loss of a zone. Every leader election in the company depends on it, so clients must also ride through short outages without dropping their locks.
• Acquire latency (p99 < 50 ms). One Raft commit is ~5 ms in a region; the budget absorbs fsync tails. Tens of milliseconds is fine for a call each client makes rarely.
• Scale per region (50 k sessions · 20 k locks). Load is dominated by 12.5 k KeepAlives a second and ~50 k reads a second before caching. Real writes are about 200 a second.
• Takeover after a holder dies (< 15 s). The 12 s lease plus a margin. Shorter would expire healthy clients during GC pauses and during the cell’s own leader failovers.
• Cell failover (< 3 s, no sessions lost). A new Raft leader in 1 to 2 s plus reconnects. It must stay well inside the lease so that clients do not notice.
• Linearizable (lock ops, writes, lock-path reads). Everything on lock paths is ordered by one log. Cached config reads are kept consistent by invalidation, not by a TTL.
• Small state (< 1 GB in memory). Values ≤ 64 KB and ~100 MB in total today. Keeping it small is what lets every replica hold it all in memory and snapshot it in a second.

Back-of-envelope estimates

• KeepAlives per second: ~12.5 k/s. 50 k sessions renewing every 4 s (a third of a 12 s lease) = 12.5 k/s. This is the biggest stream in the system, which is why renewals stay in the leader’s memory and never touch the log.
• Reads reaching the cell: ~500/s. 50 k processes reading a config value about once a second = 50 k reads/s. With a client cache that the leader invalidates and a ~99 % hit rate, ~500/s reach the cell. The cache, not the replicas, carries the read load.
• Writes through consensus: ~200/s avg · ~2 k/s peak. 5 k short-lived locks taken about once a minute = ~83 acquires and ~83 releases a second, plus ~10 config writes and ~20 session creates and expiries: ~200/s. Mass restarts reach ~2 k/s. One cell sustains ~10 k/s, so writes are not the hard part.
• Commit latency of an acquire: ~5 ms. Client to proxy to leader ~1 ms, then the leader’s own fsync (1–2 ms) in parallel with a cross-zone round trip to two followers and their fsync (~3 ms), then the reply ~1 ms: ~5 ms. fsync tails push p99 toward tens of milliseconds, still inside the 50 ms target.
• State in memory: ~100 MB. ~100 k nodes (20 k locks, 50 k ephemeral membership nodes, ~30 k config values) at ~1 KB each with metadata = ~100 MB, plus 50 k sessions at ~100 B. Every replica holds all of it in memory and snapshots it in about a second.
• Proxies needed: ~25. 50 k client connections at ~2 k per proxy = 25 proxies, spread over three zones. The leader sees 25 batched KeepAlives a second instead of 12.5 k, and a change watched by every process fans out 25 ways from the cell.
• Raft log written per day: ~3.5 GB/day. 200 writes/s × 86 400 s ≈ 17 M entries × ~200 B ≈ 3.5 GB/day. A snapshot every 100 k entries (about every 8 minutes) truncates it, so only ~20 MB of log is ever on disk.
• Herd on one release: 2 000 events vs 1. With 2 000 waiters all watching the lock node, one release sends 2 000 events and triggers up to 2 000 re-lists and creates: a fifth of a second of the cell’s entire write capacity for one handoff. Watching only the predecessor makes it 1 event.

Components

• Protected resource (rejects stale tokens): Whatever the lock protects: a database shard, a storage bucket, a partition of work. It stores the highest fencing token it has accepted for each lock and refuses any write carrying a lower one, which is the only thing that stops a paused former holder.
• Client cache (invalidated before writes): Values the library has read, held in process memory and valid only while the session lease is. The leader keeps a list of who caches each node and invalidates them before any write commits, so a cached read is never stale while the session is healthy. When the lease is in doubt, the cache is switched off.
• Session manager (leader-only lease timers): Runs on the leader and tracks every session’s lease expiry in memory, extending it on each KeepAlive without writing to the log. When a lease runs out it commits one expiry entry through Raft, which deletes the session’s ephemeral nodes and frees its locks at a log position every replica agrees on.
• Client + library (session · recipes · local lease): A service process that needs a lock, a leader or a config value. Its library does the protocol work: it holds one session, sends KeepAlives, runs the lock and election recipes, and keeps a conservative local lease clock. It tells the application to stop acting the moment that lease is in doubt.
• Proxy tier (~25 · KeepAlive fan-in): About 25 proxies, each terminating ~2 k client connections. They batch KeepAlives into one RPC a second per proxy, serve cached reads, register one watch per path on behalf of all their clients and fan events back out. Sessions belong to the cell, not the proxy, so a client whose proxy dies reconnects to another and keeps its locks.
• Leader replica (Raft leader · 1 of 5): The one replica of five that orders everything: it appends writes to the log, replicates them, commits on a majority, and serves lock-path reads after a ReadIndex check. It also owns sessions, the cacher list and watch delivery, which is why proxies and client caches exist to keep load off it.
• Follower replicas (4 of 5 · across 3 zones): The other four replicas, placed so the cell has two in each of two zones and one in a third, and any zone can be lost. They persist and acknowledge entries, apply committed ones to their own copy of the state, and stand for election if the leader’s heartbeats stop for 1 to 2 s.
• Cell directory (prefix → cell · cached): Maps each top-level prefix of the namespace (/payments, /indexer) to the cell that owns it, with each cell’s proxy addresses. A few hundred entries that change a few times a month and are cached by every library, so it is never on the lock path.
• Watch table (one-shot events · invalidations): Who is watching which node and who is caching it, kept on the leader (and, for their own clients, on each proxy). After a change commits it emits one-shot events; before a write to a cached node commits it sends invalidations and waits for the acknowledgements.
• State machine (nodes · sessions · in memory): The namespace every replica rebuilds by applying the log in order: nodes with data, versions and flags (ephemeral, sequential), the sessions that own them, and the last request id and result per session so a retried request is never applied twice. About 100 MB, all in memory.
• Raft log (WAL · fsync · group commit): Each replica’s write-ahead log of creates, deletes, value writes and session expiries, fsynced before an entry is acknowledged. Group commit puts many entries in one fsync. A p99 fsync above 10 ms is the warning sign that slow disks will start causing elections.
• Other cells (independent 5-replica groups): Other independent five-replica groups in the region, each with its own proxies and its own slice of the namespace. No operation spans two cells, so they share nothing and fail independently. A small global cell with replicas in several regions handles the rare truly global lock.
• Snapshots (every 100 k entries): A point-in-time copy of the state machine taken every 100 k entries, after which the log before it is discarded. Lagging and replacement replicas start from one, and an hourly copy in object storage in another region is the disaster-recovery backup.

User flows

1. Acquire a lock and write with its token. The core write path. One Raft commit puts the client in line, the lowest node holds the lock, and the grant comes back with a fencing token that the protected resource checks on every write.
   1. The library maps the lock’s path to the cell that owns its prefix. The directory is tiny (a few hundred prefixes), changes a few times a month and is cached by every library for minutes, so it is never on the lock path. A prefix lives in exactly one cell, which is what keeps cells independent: no operation ever spans two consensus groups.
   2. It opens a session through a proxy and starts sending KeepAlives. Creating a session is one Raft write, so every replica knows it exists; renewing it is not, which is why 12.5 k KeepAlives a second cost almost nothing. The lease is 12 s and the library renews every 4 s, starting its local lease clock when it sends the request, so its idea of the expiry is always earlier than the leader’s.
   3. To acquire, the library creates an ephemeral sequential node under the lock’s path. Ephemeral means it belongs to the session and is deleted when the session ends. Sequential means the cell appends a counter that only goes up, so waiters are ordered by arrival. It is a write, so the proxy forwards it to the leader rather than answering it.
   4. The leader appends the create, replicates it, and commits once three of five replicas have it on disk. The leader fsyncs its own copy while AppendEntries is in flight to the four followers, so the commit waits for the second-fastest follower, not the slowest. A cross-zone round trip of ~1 ms plus a 1 to 2 ms fsync puts the commit at ~3 ms, and entries that arrive together share one fsync (group commit).
   5. The entry is applied, and the library lists the lock’s children to see whether its node is the lowest. The lowest sequence number holds the lock. The list is a read through the leader, which first confirms it still leads with a ReadIndex round (a heartbeat acknowledged by a majority), so the answer cannot come from a deposed leader’s stale memory. If its node is lowest, the library has the lock with no further write.
   6. The library returns the grant with a fencing token: the create index of its node. The token is 918204, the Raft index of the create. It is unique and only goes up over the cell’s life, across leader changes too, because Raft indexes do. Every later holder of this lock has a higher token, since waiters are served in creation order.
   7. The holder sends the token with every write, and the resource rejects any token lower than the highest it has seen. The resource stores the highest token per lock next to the data and makes each write conditional on it, in the same transaction. This is the step that makes the lock safe against a holder that paused: the lock service cannot reach into a process and stop it, but the resource can refuse it.
   8. On release, the library deletes its node; the delete commits and the next waiter is notified. A clean release frees the lock in one commit, about 5 ms. If the client crashes instead, its session expires after the 12 s lease and the leader deletes the node itself. That timing is the only difference between a clean and an unclean release.
2. Cached config reads and an invalidating write. The read path. Most reads never leave the client, and a write is held until every cache that might hold the old value has dropped it, so cached reads stay consistent without polling or TTLs.
   1. A process reads a config value; on a miss, the library fetches it through its proxy. The leader answers from memory and records that this proxy and session now cache the node. The proxy keeps its own copy, so the next of its ~2 k clients to ask is answered without reaching the cell at all.
   2. Later reads are served from the client cache with no RPC. At 50 k processes reading about once a second, the cache turns 50 k reads a second into roughly 500 misses a second at the cell. A cached value is usable only while the session lease is; when the library’s lease is in doubt it switches the cache off, so a partitioned client cannot keep serving an old value.
   3. An operator writes a new value; the leader marks the node uncachable and sends invalidations to every cacher. This is Chubby’s rule: the write waits until every session that may cache the node has acknowledged the invalidation or let its lease run out. Reads in the meantime go to the leader and return the old value, which is still the committed one, so no reader can see the new value and then the old one.
   4. Each proxy drops its copy and passes the invalidation only to its clients that hold the node. With 20 k processes caching this flag behind 25 proxies, the cell sends 25 invalidations instead of 20 k, and each proxy sends ~800. Acknowledgements come straight back on the session stream, so a healthy fleet has acknowledged within tens of milliseconds.
   5. Once every cacher has acknowledged or expired, the write commits and the leader replies. The worst case is a cacher that is partitioned: the write waits up to its 12 s lease, because until then the leader cannot prove that client has stopped reading the old value. That is the price of consistent caching, and it is why values that change every second do not belong in this service.
   6. Watchers get a one-shot event, re-read the value and re-arm the watch in the same call. The event says only that the node changed, not what it changed to. Reading with watch=true sets the next watch atomically with the read, so no change can slip through a gap. A client may skip intermediate values, but it never misses that a newer one exists.
3. 2 000 contenders and a paused leader. The scale-breaking case and the failure that matters most. Two thousand processes contend for one leadership; when the leader stalls, exactly one waiter is woken, and the old leader’s late write is refused by its token.
   1. Each of 2 000 workers creates an ephemeral sequential node under the election path and lists the children. 2 000 creates is 2 000 small Raft writes, a burst of a fraction of a second for a cell that sustains ~10 k writes a second. The worker with the lowest number is leader and writes its address into its node, so anyone can find the leader with one read.
   2. Every other worker watches only the node just below its own. Worker 42 watches 41, 43 watches 42, and so on: 1 999 watches on 1 999 different nodes. If they all watched the leader’s node, its deletion would wake 1 999 processes that would all re-list and most would re-create, thousands of operations for a handoff only one of them can win.
   3. The leader stalls in a 20-second garbage-collection pause, and its KeepAlives stop. From the cell’s side a paused process and a dead one look identical: no renewals. Its library cannot react either, because it is paused too, which is exactly why a lease alone cannot make a lock safe.
   4. When the 12-second lease runs out, the session manager commits the session’s expiry. Expiry is a replicated entry, not a timer firing separately on each replica, so all five agree on the exact log position at which the session ended. Applying it deletes every ephemeral node the session owned, here n-0000000041.
   5. The delete fires one watch, and only worker 42 is notified. One event instead of 1 999. Worker 42 re-lists the children rather than assuming it is now lowest, because the node it watched might have been a waiter that gave up; if so, it simply watches the next lower node.
   6. Worker 42 confirms it is lowest, becomes leader, and fences the resource with its token. Its token is the create index of n-0000000042, higher than 41’s. Its first act as leader is a write carrying that token, which raises the resource’s high-water mark before it reads any state, so nothing from the old leader can land after the new one has started work.
   7. The old leader wakes and sends a write it prepared before the pause; the resource rejects it. Its library will notice the expired lease within moments and raise "session expired", but the write was already on its way. 7703120 is below 7703188, so the resource refuses it, and the old leader learns it is no longer leader from the rejection.
4. The cell’s leader replica crashes. The failure case for the service itself. A new leader is elected in about two seconds, sessions survive because their leases outlast the failover, and clients flush their caches because an invalidation may have been lost.
   1. The leader’s machine dies, and the followers stop receiving heartbeats. Heartbeats go out every 100 ms, and each follower waits a randomised election timeout of 1 to 2 s before standing. Long enough that a slow fsync or a short network blip does not start an election, short enough that the gap stays well inside a 12 s lease.
   2. A follower times out first, asks for votes, and wins a majority with an up-to-date log. A replica votes only for a candidate whose log is at least as complete as its own, so the winner holds every committed grant and expiry. It needs three votes from the four survivors, so even a second failure during the election would leave a majority.
   3. The new leader commits a no-op, treats every session as renewed now, and accepts KeepAlives again. It knows which sessions exist, because they are in the state machine, but not when each last renewed, since renewals were never logged. So it gives every session a full lease from the moment it took over: nobody is expired because of the failover, at the cost of a client that died during it holding its locks up to one lease longer.
   4. Proxies find the new leader and resend requests that had no reply; sessions are intact. A proxy asks any replica who leads and reconnects in milliseconds. A request whose outcome is unknown is resent with the same session and request id, and the state machine returns the stored result instead of applying it again, so a retried create cannot put a second waiter node in line.
   5. Clients receive a fail-over event and flush their caches. The list of who caches what lived in the old leader’s memory and is gone, so an invalidation could have been lost in the crash. Flushing costs a burst of re-reads, mostly absorbed by the proxies’ own caches, and keeps every cached value honest. Watches are re-registered with the last index each client saw, so any change in the gap fires at once.
   6. A client whose lease ran out locally while it waited enters jeopardy, stops acting, and resumes when its session is confirmed. With a 2 to 3 s failover and a KeepAlive every 4 s, most clients never get this far. Those that do pause their lock-protected work and keep retrying through a 45 s grace period, ending in either "safe" (the session survived and its locks are still held) or "expired" (start again, with new tokens).
5. Snapshots, a replacement replica, a new cell. The background work that keeps a cell healthy: snapshots bound the log, a dead replica is replaced without ever allowing two majorities, and a prefix that outgrows its cell moves to a new one.
   1. Every 100 k entries, each replica snapshots its state machine and truncates its log. At ~200 writes a second that is about every eight minutes, and with ~100 MB of state a snapshot takes about a second in the background (copy-on-write, or a fuzzy snapshot made consistent by replaying idempotent log entries, as ZooKeeper does). An hourly copy goes to object storage in another region for disaster recovery.
   2. A replacement machine joins as a non-voting learner and receives the latest snapshot from the leader. 100 MB at 10 Gb/s takes a fraction of a second, and the leader then streams the log since the snapshot. As a learner it receives everything but does not count toward the majority, so a slow catch-up cannot stall commits.
   3. Once it has caught up, membership changes one server at a time: remove the dead replica, then promote the learner. Changing one voter per configuration means the old and new majorities always overlap, so two leaders can never be elected in two halves of a half-changed cluster. Between the two steps the cell has four voters and still tolerates one failure.
   4. A team’s prefix outgrows its cell, and the directory points it at a new cell. The triggers are sustained writes above ~2 k a second, more than ~100 k sessions, or simply blast radius: one team’s runaway client should not cost every other team its locks. The prefix is frozen for a few seconds, its subtree is copied, the directory flips and bumps the prefix’s epoch, and clients reconnect with a fail-over event.
   5. Dashboards track commit latency, fsync p99, session expiries per minute and the oldest unacknowledged invalidation. A rise in expiries without a deploy to explain it means clients are pausing or KeepAlives are being dropped, and it comes before outages in the services that depend on locks. fsync p99 above 10 ms, etcd’s published guidance, is the earliest sign a disk will start causing elections.

Deep dives

The theory behind it

• Raft leader election and log replication: an interactive playground. Watch a five-server Raft cluster elect a leader, stop the leader and see a new term begin, send writes that commit on a majority, and break the quorum.
• Fencing tokens: an interactive playground. Pause a lock holder past its lease and watch two clients both believe they hold the lock, then see how fencing tokens stop the stale write.
• Distributed locks, leases and fencing tokens: When you need mutual exclusion across machines and how to get it safely: lock services, leases with expiry, why Redis locks can fail, fencing tokens, leader election, optimistic alternatives, and avoiding locks altogether.
• Consensus, leases and coordination: Leader election, Raft and Paxos at interview depth, ZooKeeper and etcd, distributed locks and why they are fencing tokens, plus how to avoid needing coordination at all.
• How Raft consensus works: Raft explained for system design interviews: replicated state machines, leader election with terms and randomised timeouts, log replication and commit rules, safety, membership changes, snapshots, read consistency and where Raft is used in practice.
• The best system design books and papers for interviews: The books worth reading for system design interviews and what each is for (Designing Data-Intensive Applications, Alex Xu's System Design Interview, Understanding Distributed Systems, Database Internals and more), the dozen papers behind the classic questions, and the order to read them in.

Related

• Design a Distributed Job Scheduler
• Design a Unique ID Generator
• Design AWS Step Functions
• Design a Container Orchestrator
• All 83 system design interview questions
• Run this question for a friend: the interviewer kit