Design a distributed locking service that lets multiple independent processes across different machines coordinate exclusive access to a shared resource — e.g. ensuring only one instance of a scheduled job runs at a time across a fleet of servers.
Distributed locks are typically a low-volume, high-criticality operation (unlike, say, a cache) — a fleet of 1,000 application servers each attempting a handful of lock acquisitions per minute is roughly 1,000 × 5 / 60 ≈ 83 acquire operations/sec, trivial load for a well-provisioned coordination service. The design challenge here is correctness under failure, not raw throughput — this is the opposite profile from most systems in this course.
Option A — Single Redis instance with SET NX:
SET lock:resource123 <clientId> NX PX 30000
— simple, fast, but a SINGLE POINT OF FAILURE: if that Redis instance fails over to a
replica before the SET is replicated, two clients could both believe they hold the lock
Option B — Redlock (multiple independent Redis instances, e.g. 5):
Client acquires the lock on a MAJORITY (3 of 5) of independent Redis instances
— survives any single instance failing, but has real, debated edge cases under clock drift
Option C — Consensus-based (ZooKeeper / etcd, using Raft/ZAB):
Lock is an ephemeral node; the consensus protocol itself guarantees only one client can
hold it at a time, even across leader failover — the strongest correctness guarantee
The interview-relevant tension: Redis-based approaches are faster and simpler but rely on timing assumptions (clock synchronization, bounded network delay) that can theoretically be violated; consensus-based systems (built on Raft or ZAB, the same class of algorithm underlying leader election in many distributed systems) give a stronger, provable mutual-exclusion guarantee at the cost of higher latency per operation and more operational complexity to run.
Client A acquires lock, gets fencing token = 33
Client A experiences a long GC pause ("stop the world"), lock EXPIRES while A is paused
Client B acquires lock, gets fencing token = 34
Client A wakes up, still believes it holds the lock, tries to write to the resource
WITHOUT fencing tokens: A's write succeeds, corrupting data B is also writing to
WITH fencing tokens: the resource itself REJECTS A's write because token 33 < 34
(the last token it accepted), even though A doesn't know its lock already expired
A lock alone is not sufficient for correctness under this specific failure mode (a paused client that doesn't know its lock expired) — a monotonically increasing fencing token, issued on every lock acquisition and checked by the protected resource itself (not just trusted from the client), is what closes this gap. This is a genuinely subtle, frequently-missed point even among experienced engineers, and naming it explicitly is a strong interview signal.
POST /locks/{resourceKey}/acquire
Body: { "clientId": "worker-7", "leaseDurationMs": 30000 }
→ 200 { "acquired": true, "fencingToken": 34, "expiresAt": "..." }
→ 409 { "acquired": false } (already held by another client)
POST /locks/{resourceKey}/renew
Body: { "clientId": "worker-7", "fencingToken": 34 }
→ 200 { "renewed": true, "newExpiresAt": "..." }
DELETE /locks/{resourceKey}
Body: { "clientId": "worker-7", "fencingToken": 34 }
→ 200 { "released": true }
/locks/{resourceKey} → ephemeral node, value = { clientId, fencingToken }
automatically removed if the holding client's session expires
(client disconnects, crashes, or fails to heartbeat)
The ephemeral node concept (tied to a client session, auto-removed on session expiry) is what handles crash recovery automatically — a lock holder that crashes doesn't need to explicitly release anything; its session simply expires and the coordination service removes the lock, making it available again without manual intervention.
Consensus-based coordination services (ZooKeeper, etcd) are deliberately NOT horizontally scaled for throughput the way a typical stateless service is — they scale by running a small, fixed-size cluster (typically 3 or 5 nodes) using a consensus protocol, where adding more nodes actually REDUCES write throughput (more nodes to reach consensus with) even as it improves fault tolerance. This is a fundamentally different scaling shape from most systems in this course, and worth naming explicitly: more nodes here buys resilience, not throughput.
The consensus protocol's leader is the practical bottleneck for write throughput (all lock acquisitions typically route through the current leader) — this is inherent to consensus algorithms' correctness guarantees, not a flaw to engineer around; it's why this class of system is deliberately kept small and used for coordination metadata (locks, config, leader election), never as a general-purpose high-throughput data store.
Network partition splits the coordination cluster: a minority partition cannot elect a leader or grant locks (by design — this is what prevents split-brain, where two partitions could otherwise both believe they're authoritative); clients in the minority partition simply cannot acquire locks until the partition heals, a deliberate availability-for-consistency tradeoff (CAP theorem, CP side).
A lock holder crashes without releasing: the ephemeral node mechanism (or lease expiry, for Redis-based) handles this automatically — no manual cleanup needed, the lock becomes available again once the session/lease expires.
A paused client wakes up after its lock has already expired and been reacquired by another client: fencing tokens are the defense — the protected resource rejects the stale client's write because its token is lower than the last-accepted one.