Loading…
Loading…
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.
Q: Why do locks need leases (expiry) rather than being held until released? A: A client can crash, or become partitioned, while holding a lock, and never release it. A lease expires automatically after a set time, so the lock becomes available again. Clients holding a lock renew it periodically while they're still working.
Q: If locks expire, how do you stop a paused client from acting after its lease is gone? A: Use fencing tokens. Each successful acquisition returns a monotonically increasing number, and the protected resource (database, storage) rejects writes carrying a token lower than the highest it has already seen. A client that paused (from GC or network delay), and lost its lease, can no longer corrupt data, even if it wakes up and tries to write.
Q: Why build on a consensus system like etcd or ZooKeeper? A: Lock ownership must be agreed on by a majority, and must survive node failures without two clients believing they hold the same lock. Consensus protocols (Raft, ZAB) provide linearizable writes and leader election. Building an equally safe system yourself is very hard.
Q: Is a Redis-based lock good enough?
A: For efficiency locks, where a rare double execution only wastes work (for example, avoiding duplicate cache rebuilds), a single Redis instance with SET key value NX PX ttl is fine. For correctness locks, where two holders would corrupt data, use a consensus-backed service plus fencing tokens, because Redis replication is asynchronous, and failover can lose a lock.
Q: How do waiting clients learn that a lock has been released without polling? A: They watch the lock key. ZooKeeper uses ephemeral sequential nodes, where each waiter watches only its predecessor, avoiding a thundering herd. etcd offers watches on key revisions. When the holder releases or its session expires, the next waiter is notified and acquires the lock in order.