Courses › System Design › Question Breakdowns

Design a Distributed Lock Service

Consensus, sessions and ephemeral nodes, the lock recipe, fencing tokens and why Redis locks fall short.

Design a distributed lock and coordination service like Google's Chubby, ZooKeeper or etcd: other services use it to elect leaders, hold locks, store small critical configuration, and get notified when something changes. It's a question about consensus (Raft/Paxos), sessions and leases, fencing tokens, watches, and why a lock built on a cache is not safe.

Requirements

Functional

  • Clients can acquire and release locks (exclusive), and elect a leader among a group of processes
  • Locks are tied to a session; if a client dies, its locks are released automatically
  • Clients can store small values (config, membership) in a hierarchical namespace
  • Clients can watch a key and get notified when it changes or is deleted

Out of scope: storing large data (values ≤ ~1 MB), high-throughput key-value workloads (use a Key-Value Store).

Non-functional

  • Safety above all: two clients must never both believe they hold the same lock
  • Availability: tolerates the failure of a minority of servers (e.g. 2 of 5)
  • Modest scale: thousands of clients, ~10k writes/second, many more reads and watches
  • Low latency: lock acquisition in milliseconds within a region

[!TIP] Safety needs consensus — and fencing A lock is only as correct as the system that grants it: the state must be agreed by a majority of servers (consensus), so a network partition can never produce two holders. And even then, a client can believe it holds a lock after losing it (a long GC pause). The protected resource must check a fencing token. Say both.

Capacity estimates

Core Entities

  • Node (key) — path (/locks/orders-db), value, version, ephemeral flag, owner session
  • Session — client, lease timeout, last heartbeat
  • Watch — session, path, event types
  • Log entry — term/epoch, index, operation (the replicated state machine's input)

API

createSession(ttl = 10s) → sessionId               (kept alive by heartbeats)
create("/locks/job-7", ephemeral = true, sequential = true) → "/locks/job-7/lock-0000000042"
getChildren("/locks/job-7", watch = true)
delete(path, expectedVersion)
get(path, watch = true) / set(path, value, expectedVersion)

High-Level Design

c1 = client "Client A" @0,0
c2 = client "Client B" @0,2
leader = service "Leader\n(accepts writes)" @1,1
f1 = service "Follower" @2,0
f2 = service "Follower" @2,2
log = store "Replicated Log +\nIn-memory Tree" @3,1
res = store "Protected Resource\n(checks fencing token)" @1,3
c1 -> leader : acquire lock
c2 -> f1 : read / watch
leader -> f1 : replicate
leader -> f2 : replicate
f1 -> log
c1 -> res : write + token 42
  • Servers form a consensus group (Raft/Zab/Paxos) with one leader. Every write is appended to the leader's log and committed once a majority has it, then applied to an in-memory tree on every server.
  • Clients hold a session with heartbeats; ephemeral nodes (locks, membership) disappear when the session expires.
  • Watches notify clients of changes so they don't poll.
  • Lock holders pass a fencing token (a monotonically increasing number from the service) to the resources they protect.

Deep Dives

1. Consensus

Raft in brief: the leader appends entries and replicates them; an entry is committed when a majority stores it. If the leader fails, followers time out and elect a new leader — only a candidate with the most up-to-date log can win, so committed entries are never lost. With 5 servers, the system keeps working with 3 up; a minority partition can't commit anything, so it can't grant a conflicting lock.

2. Locks with ephemeral sequential nodes

ZooKeeper's lock recipe avoids a thundering herd:

[Create ephemeral sequential child] -> [Lowest number?] -> [Hold the lock]
[Lowest number?] -> [Watch only the next-lower child] -> [Notified on its delete] -> [Lowest number?]

Each waiter watches only its predecessor, so a release wakes exactly one client, and the queue is FIFO. If the holder crashes, its session expires and its node is deleted — releasing the lock automatically. Leader election is the same recipe: the lowest sequence number is the leader.

3. Sessions, leases and timing

A session lives while heartbeats arrive within its timeout. The service waits the full timeout before expiring it; the client, if it can't reach the service, must assume it may have lost its locks after the timeout (minus a safety margin for clock drift) and stop acting.

4. Fencing tokens

A client pauses for 30 seconds (GC, VM migration); its session expires, another client takes the lock, then the first client wakes up and writes — two writers.

[!WARNING] A lock alone can't stop a paused client Give every lock grant a fencing token (e.g. the node's creation sequence or the log index — always increasing). The protected resource (database, storage) remembers the highest token it has seen and rejects writes with older tokens. This is what actually makes the lock safe.

5. Why not a Redis lock?

SET lock value NX PX 10000 on a single Redis instance is fine as an efficiency lock (avoid duplicate work), but not for correctness: asynchronous replication means a failover can lose the lock and grant it twice, and there's no fencing token. Redlock across several instances relies on timing assumptions (bounded clock drift and pauses) that real systems violate. For correctness-critical locks, use consensus + fencing.

6. Scaling reads and watches

Writes must go through the leader, but reads can be served by followers (possibly slightly stale; use a sync/linearizable read when needed). Watches are registered on the server the client connects to. To scale further, add observers (non-voting replicas) for read traffic, and keep writes small — a coordination service is not a database.

What's expected at each level

  • Mid-level: a lock service with acquire/release, timeouts so dead clients release locks, and replication of its state.
  • Senior: consensus with majority commits and leader election, sessions with ephemeral nodes, watches, the predecessor-watch lock recipe.
  • Staff: fencing tokens and why leases alone aren't safe, the Redis/Redlock debate, linearizable vs. follower reads, and scaling with observers while keeping the service small.