Design a Distributed Lock / Coordination Service (ZooKeeper/etcd)

Why a naive lock is unsafe

A coordination service (ZooKeeper, etcd, Consul) gives a cluster the primitives it cannot build safely on its own: mutual exclusion (a distributed lock), leader election, and shared configuration that stays correct across process pauses and network partitions. The interview tests whether you understand why a naive lock is unsafe and how leases, fencing tokens, watches, and consensus combine into a correct one.

Why a single Redis SETNX with TTL is unsafe

It looks like a lock: SET key if not exists, with an expiry so a dead holder does not deadlock forever. It is unsafe for two reasons. First, a single Redis node is a single point of failure, and Redis replication is asynchronous, so a failover can lose the lock key and grant the lock twice. Second, and more fundamental, the TTL creates a correctness hole: the holder can pause (a long GC, a scheduler preemption, a network partition) past the TTL, the lock expires, a second client acquires it, and then the first client wakes up still believing it holds the lock. Now two clients act in the critical section at once. No amount of tuning the TTL fixes this, because you cannot bound a pause.

Interview nuance: the two-part answer that impresses: (1) put the lock state in a consensus-backed store so it is linearizable and survives node failure, and (2) hand out a fencing token so a stale holder's writes are rejected. Miss the fencing token and you have not actually made the lock safe.

Consensus, leases, fencing, watches

Build on a store whose state is replicated by a consensus protocol (Raft in etcd and Consul, Zab in ZooKeeper). A write commits only when a majority (quorum) of nodes agree, so the lock state is linearizable and survives minority failures. Under a partition only the majority side can make progress. This is the CP corner of CAP: during a partition the minority side becomes unavailable rather than returning possibly-wrong state.

A client holds a lock via a session with a TTL that it must renew by heartbeat. If the client dies or partitions away, it stops heartbeating, the session lease expires, and the lock is released automatically. ZooKeeper models this as an ephemeral znode; etcd as a lease attached to the key.

Fencing tokens are what make leasing safe. Each lock grant includes a monotonically increasing token (etcd's key revision, ZooKeeper's zxid). Every write the lock holder makes to the protected resource carries its token, and the resource remembers the highest token it has accepted and rejects any lower one. So when a paused old holder wakes up and tries to write with an old token, the resource fences it off.

Instead of polling "is the lock free yet," clients register a watch on the lock or leader key and receive a callback when it changes, giving fast failover. Leader election: candidates each create an ordered ephemeral key (a sequence number); the candidate with the lowest number is the leader; each other candidate watches only its immediate predecessor, so when the leader dies exactly one candidate is notified and takes over, avoiding a herd.

acquire: create ephemeral seq key under /lock  -> get number
   lowest number holds the lock; token = key revision
   others watch predecessor (no polling)
protected resource: accept write only if token >= max_seen_token   (fencing)
partition: only majority quorum can grant -> minority is unavailable, not wrong

Recap: a Redis SETNX-with-TTL lock is unsafe because a single node can fail over and a paused holder can outlive its TTL; build on a consensus-backed store (etcd, ZooKeeper) for linearizable lock state, auto-release via session leases and heartbeats, defeat the stale-holder double-run with monotonic fencing tokens, notify clients with watches instead of polling, and elect leaders with ordered ephemeral keys where each watches its predecessor.