Engineering Atlas › System Design Interviews

Design a distributed lock service

21 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional

Non-functional

Out of scope: row-level or per-request locks at millions of operations per second (use the database's own row locks), Byzantine clients, and a single lock name that must be writable from every region with local latency.

Back-of-envelope

Assumed numbers for a large company's internal coordination service.

API

A gRPC service. Heartbeats run on a long-lived bidirectional stream; everything else is unary.

OpenSession(client_id, ttl_ms)                 -> { session_id, ttl_ms }
KeepAlive(stream { session_id })               -> stream { ttl_ms_remaining }
Acquire(session_id, name, mode: EXCLUSIVE|SHARED,
        wait_ms, request_id)                   -> { status: GRANTED|QUEUED|TIMED_OUT,
                                                    token, holders }
Release(session_id, name, token)               -> { ok }
CheckToken(name, token)                        -> { current: bool, latest_token }
GetLock(name)                                  -> { mode, holders: [{session, token}],
                                                    waiters: [{session, mode}] }
Watch(name, since_revision)                    -> stream { revision, event, lock }
CloseSession(session_id)                       -> { released: [name] }

request_id makes Acquire idempotent: a retry after a timeout returns the original result rather than queueing a second request. Release carries the token so a stale client that lost its session and somehow still runs cannot release a lock that now belongs to someone else. wait_ms = 0 is a try-lock.

Data model

State lives in memory on every replica, rebuilt from the latest snapshot plus the log tail. It is a small keyed map, not a table in a general database.

sessions/{session_id} holds client_id, ttl_ms and the set of lock names it holds or waits on. The expiry deadline is not stored in the log: only the leader tracks it, on a monotonic clock, and appends an ExpireSession entry when it passes. Writing every heartbeat to the log would multiply write volume by ten.

locks/{name} holds mode, holders as a list of (session_id, token), and waiters as a FIFO list of (session_id, mode, request_id, deadline). A lock record is deleted when it has no holders and no waiters, so the map size tracks live locks only.

dedupe/{session_id}/{request_id} holds the result of the last few requests per session, so retries are answered from state. It is dropped with the session.

Tokens are the Raft log index of the entry that granted the lock. The log index is already strictly increasing across leader changes, so there is no extra counter to replicate and no way for a new leader to reuse a number.

Partition key: the top-level path segment, such as /ls/payments/..., maps to a cell through a small routing table. Placing by team namespace rather than by hash keeps one team's locks and incidents in one cell, and moving a tenant is one routing row.

High-level design

flowchart LR
  C["Client library"] -->|"KeepAlive stream"| P["Session proxy"]
  C -->|"Acquire / Release"| R["Cell router"]
  P --> L
  R --> L["Cell leader"]
  L <-->|"AppendEntries"| F1["Follower 1"]
  L <-->|"AppendEntries"| F2["Follower 2..4"]
  L --> W["Watch fan-out"]
  W --> C
  C -->|"write + token"| S[("Protected resource")]
  S -->|"CheckToken (optional)"| R
  L --> B[("Snapshots in object storage")]

Write path (acquire).

  1. The cell router forwards Acquire to the cell's current leader.
  2. The leader checks the dedupe map, appends an Acquire entry and sends AppendEntries to the four followers.
  3. Once three of five replicas have the entry on disk, it is committed and every replica applies it in log order. If the lock is free and nobody is queued, the entry's index becomes the token; otherwise the request joins the queue.
  4. The leader replies GRANTED with the token, or holds the call open until a later Release or ExpireSession entry promotes it. If wait_ms runs out first, the leader appends a CancelWait entry.

Read path.

  1. GetLock and CheckToken must not see stale state, so the leader uses a read index: note the commit index, confirm leadership with one heartbeat round, wait until applied, then read memory. No log write. One catch: a newly elected leader must first commit a blank entry in its own term, or it cannot know which entries are committed, so reads wait for that (Raft paper).
  2. Watchers subscribe to the apply stream; each event carries its log index as a revision, so a reconnecting watcher resumes from since_revision without gaps.

Deep dives

1. What a lock actually guarantees: leases, pauses and fencing

The tempting promise is "only one client holds the lock at a time". No lock service can deliver that. A holder can stop for 30 seconds in a garbage-collection pause or a VM live migration, then wake up and write as though nothing happened, while the service has already expired its session and granted the lock to someone else.

Options considered: long TTLs (only lowers the odds, and slows recovery from real crashes); lock-delay, which Chubby offers, where a lock whose holder died without releasing cannot be regranted for a while (up to a minute) so stray writes drain (Chubby paper); and fencing tokens, where every grant carries a strictly increasing number that the client sends with each write, and the resource rejects any token lower than the highest it has seen (Kleppmann). With ZooKeeper the zxid or znode version serves as the token; etcd's maintainers say its locks cannot protect an external resource by themselves and name the lock key's revision as the token (etcd docs).

I choose fencing as the contract (the Distributed Locks lesson shows why Redis-style leases cannot provide it), with lock-delay as the fallback for resources that cannot check tokens. The Raft log index gives monotonic tokens for free. The resource should check with a conditional write such as UPDATE ... WHERE fence < :token; a remote CheckToken call is still racy unless check and write are atomic. The client library also keeps a local deadline shorter than the server TTL, measured on a monotonic clock from when the heartbeat was sent, and stops writing once it passes. That covers the common case cheaply; fencing covers the case where the client's own scheduler lies.

2. Sessions and heartbeats at 50,000 per second

Options considered: a TTL on each lock (Redis SET NX PX style), or a TTL on a session that owns many locks. Per-lock TTLs mean a client holding 500 locks refreshes 500 keys, each a replicated write. Sessions cut that to one heartbeat per process, held in the leader's memory, as etcd leases and ZooKeeper sessions do.

The hard part is failover: heartbeats were never logged, so a new leader does not know when each session last checked in. The safe rule is to give every session a fresh full TTL when a new leader takes over. A session may then live one TTL too long, which delays waiters, but never dies earlier than its owner believes, which would break safety. Chubby adds a client-side grace period (45 s by default against a 12 s lease) during which clients block new operations but keep their locks, so a quick failover is invisible to applications. Under heavy load its master stretches leases toward about 60 s, trading slower expiry for fewer KeepAlives (Chubby paper).

For fan-in, session proxies terminate the heartbeat streams and forward one batched heartbeat per second to each cell leader, turning 50,000 small messages into a few hundred larger ones. A proxy holds no truth, so losing one only means its clients reconnect elsewhere.

3. Waiting without a herd, and fairness between modes

Option one is client polling with backoff: a lock with 2,000 waiters generates thousands of failed attempts per second, and whoever polls at the right millisecond wins. Option two is the ZooKeeper recipe, where each waiter watches only the sequential node just below its own, so a release wakes exactly one client (ZooKeeper recipes); no herd, but the queue logic lives in every client library. Option three keeps a FIFO queue inside the lock record and has the leader push a grant to the next waiter. I choose option three: the queue becomes replicated state, inspectable and identical for every client language.

Shared and exclusive modes need one more rule. If readers may jump a waiting writer whenever other readers hold the lock, a steady stream of readers starves the writer forever. So the queue is strict FIFO: a shared request is granted only if no exclusive holder exists and nobody is ahead of it. Promotion walks from the head, granting consecutive shared requests together and stopping at the first exclusive request it cannot grant. Cancellation also runs promotion, because a writer leaving the head can unblock the readers behind it at once.

Down the stack

Layer 1The contract

  • Grant. A GRANTED reply with token t means the grant is committed on a majority of replicas at log index t. At index t no other session holds the lock exclusively, and any later grant of the same name has a token greater than t.
  • Expiry. A session that sends no successful heartbeat for its TTL may be expired at any time after that, never before, as measured by the leader's monotonic clock. After a leader change, the earliest expiry moves forward by up to one TTL.
  • Release. Release with a stale token is a no-op. Release and expiry both promote waiters in FIFO order.
  • Reads. GetLock and CheckToken are linearizable: they reflect every grant committed before the call began.
  • Retries. The same request_id in the same session yields the same outcome.

Layer 2The mechanism

The core is Raft. The leader appends an entry, sends AppendEntries(term, prevLogIndex, prevLogTerm, entries, leaderCommit) to followers, and advances commitIndex once a majority acknowledges. Election uses randomized timeouts; etcd's defaults are a 100 ms heartbeat interval and a 1,000 ms election timeout, and its tuning guide asks for an election timeout of at least 10 round trips (etcd tuning). That is why clients see roughly one to two seconds of unavailability on leader loss, and why a cell spread across regions needs much longer timeouts. Linearizable reads use Raft's ReadIndex: confirm leadership with a heartbeat round, then read once lastApplied >= readIndex.

etcd builds locks from smaller primitives. A lease is created with LeaseGrant, kept alive with a LeaseKeepAlive stream, and attached to keys. The concurrency Lock call creates a key under the lock's prefix bound to the caller's lease, then waits for deletion of the key with the next-lower create_revision; that revision works as a fencing token. Chubby's token is a sequencer: lock name, mode and generation number, verified with CheckSequencer (Chubby paper). Chubby also runs five replicas per cell and needs three of them up, the same shape as this design. Our design puts the queue in the lock record instead, so promotion is one step in the apply function.

That apply function runs on every replica, so it must be deterministic and must never read wall-clock time. Waiter deadlines and session expiry are decided by the leader and enter the log as explicit CancelWait and ExpireSession entries.

Layer 3The machine

  • Commit latency is one round trip to the second-fastest follower plus one fsync. Across three availability zones the round trip is about 0.5 to 2 ms; fsync costs tens of microseconds on datacenter NVMe with power-loss protection and about a millisecond on cloud block volumes. An uncontended acquire takes 2 to 5 ms.
  • Group commit. Entries that arrive while an fsync is in flight ride the next one. At 5,000 writes/s and 1 ms per fsync, each flush carries about five entries, so throughput grows with load until disk bandwidth or leader CPU runs out.
  • Clocks. TTLs use CLOCK_MONOTONIC, which never jumps when NTP steps the wall clock, but it can still be slewed: Linux clamps the frequency adjustment to ±500 parts per million (adjtimex(2)), which is 6 ms over a 12 s TTL. Amazon's guidance is the same: leases should be measured as local elapsed time, never wall-clock time (Amazon Builders' Library). The client library subtracts a drift margin from its deadline.
  • Pauses. etcd, written in Go, sees stop-the-world pauses well under a millisecond; a JVM client with a large heap can pause for seconds. A leader pause longer than the election timeout triggers a needless election, so cell replicas run on small, dedicated machines. Applying an entry to 50 MB of in-memory state takes about a microsecond, so disk and network, not CPU, set the ceiling.

Why it's built this way

  1. Machines crash and pause unpredictably, so locks must expire on their own, which makes every lock a lease.
  2. Leases need one authority on who holds what, even when nodes fail, so the lock table sits on a consensus log with a majority quorum.
  3. A quorum write costs a round trip plus an fsync, so only state changes go in the log, and heartbeats stay in memory.
  4. Expiry cannot reach into a paused client, so safety moves to the resource, using a token that only grows, and the log index already has that property.
  5. One leader and one disk cap a group's write rate, so growth comes from more cells and coarser locks, not from bigger groups.

Failure modes

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Consensus-backed lock service (this design)Correct across failover, fencing tokens, sessions, fair queuesFive replicas per cell, write rate bounded per cellLocks protect correctness across many teams
etcd or ZooKeeper run per teamMature, well understoodEach team runs its own quorum, no shared queue semanticsA single system needs coordination and has an operator
Single Redis key with SET NX PXSub-millisecond, trivialLost on failover with async replication, no fencing by defaultEfficiency locks, such as avoiding duplicate cache rebuilds
Redlock across independent Redis nodesNo single node failureDepends on bounded clock drift and pauses; still no fencingRarely; prefer one of the rows above
Database advisory or row lockSame transaction as the data, no new systemTied to one database connection, does not span servicesThe protected data lives in that database

Leadership lens

Check yourself

  1. A lock holder pauses for 30 seconds in garbage collection, its session expires, and the lock is granted to another client. What stops the first client's writes from corrupting the resource?

    Show answer

    Every grant carries a fencing token, the Raft log index of the granting entry, which only grows. The resource applies writes with a conditional check such as UPDATE ... WHERE fence < :token, so the paused client's older token is rejected; lock-delay is the fallback for resources that cannot check tokens.

  2. After a leader failover, why does the new leader give every session a fresh full TTL, and what does that cost?

    Show answer

    Heartbeats were never written to the log, so the new leader does not know when each session last checked in. A fresh TTL means a session may live up to one TTL too long, which delays waiters, but it never expires earlier than its owner believes, which would break safety.

  3. Why does the design use session TTLs with heartbeats in leader memory instead of a TTL on each lock?

    Show answer

    Per-lock TTLs mean a client holding 500 locks refreshes 500 keys, each a replicated log write. A session needs one heartbeat per process, kept in memory, so 50,000 heartbeats per second never touch the log, and every lock the session holds or waits for dies with it.

  4. Using the lesson's numbers, why does the fleet run 8 cells rather than one bigger Raft group?

    Show answer

    Steady state is about 6,700 log writes per second, but a reconnect storm after a deploy pushes peak to about 33,000, and one Raft group with batched fsync handles around 5,000 to 10,000 writes per second. Adding replicas does not help because one leader and one disk cap a group's write rate, so 33,000 / 5,000 is about 7, rounded up to 8 cells for headroom.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →