System Design Interview Guide · Post 2
Design a Distributed Lock Manager (Redlock / ZooKeeper-style)
A mutual-exclusion service that lets independent processes on independent hosts safely agree "only one of us touches this resource right now" — even when nodes crash, clocks drift, and garbage collectors freeze the world.
1. Requirements & scope
Clarify these out loud before drawing boxes — a lock manager's entire value proposition rests on the guarantees it makes under failure, not on its happy path.
Functional
Non-functional
2. Capacity estimation
Lock services are read/write-light per operation but latency-critical, and the sizing question that actually matters is "how many independent lock nodes, and what quorum" — not raw throughput.
| Dimension | Estimate | Why it matters |
|---|---|---|
| Acquisitions / sec (peak) | ~50,000 ops/sec across all resource keys | Each op is a handful of SETNX-style calls fanned out to N nodes — cheap, but fan-out multiplies node-side QPS by N. |
| Lock nodes (Redlock) | 5 independent masters, majority = 3 | Odd N tolerates ⌈N/2⌉-1 node failures while a majority can still agree; 5 is the common sweet spot between fault tolerance and fan-out cost. |
| Lease / TTL duration | 10s default, configurable 1s–300s | Must comfortably exceed expected clock drift + network round trip + client pause time, or a live holder can be declared dead too early. |
| Concurrently held locks | ~200,000 active sessions | Drives memory footprint on each lock node (a lock record is tiny: key, token, expiry) and heartbeat fan-in rate. |
| Latency budget / acquisition | <10ms P99 | Must stay well under the TTL and under the caller's own SLA, since the caller blocks (or backs off) waiting on the result. |
3. High-level design
Five moving parts: the caller, a client-side library that owns quorum logic, N independent lock nodes, a fencing-token issuer, and a background renewal loop.
What each box owns
Lock client library
Owns the actual algorithm: it fans an acquire attempt out to all N nodes in parallel, waits for acknowledgements within a time budget well under the TTL, and declares success only if a strict majority answered "granted" before that budget expires. It also owns exponential backoff on contention and a random jitter to avoid thundering-herd retries.
Lock nodes (Redis instances or ZooKeeper/etcd servers)
Each node is independent and holds no replica of any other node's state (for Redlock) or is one voting member of a single consensus ensemble (for ZooKeeper/etcd). A node grants a lock via an atomic conditional write (SET key token NX PX ttl) and nothing more — it does not need to know about the other nodes.
Fencing-token issuer
A strictly increasing counter, one per resource key, incremented on every successful acquisition. The token rides along with every write the lock holder makes to the protected resource, so the resource itself can reject any write carrying a token lower than the highest it has already seen.
Heartbeat / lease-renewal loop
A background thread on the client side that extends the lease (re-issues the conditional SET with a fresh TTL, only if the token still matches) roughly every TTL/3. If the holder process is paused or dies, renewal simply stops and the lease is left to expire naturally — no separate liveness protocol is needed.
4. Deeper architecture & failure domains
The detail that actually decides safety: are the N lock nodes truly independent (Redlock) or are they one replicated state machine (ZooKeeper/etcd)? Both are legitimate, but they fail differently.
| Decision | Choice & when it applies |
|---|---|
| Redlock vs ZooKeeper/etcd | Redlock (5 independent Redis nodes): lowest latency, no consensus round trip, good when the cost of a rare double-grant is tolerable (e.g. cache stampede protection). ZooKeeper/etcd: strict linearizable consensus with ephemeral/lease-backed nodes and watches, correct choice when the protected action is destructive or irreversible (e.g. leader election, schema migration). |
| TTL length | Short TTL (1–5s) recovers fast from a dead holder but risks the lease expiring under a real holder's transient pause; long TTL (30s+) is safer against false expiry but slows recovery and lengthens contention. Pick TTL ≫ (max GC pause + max clock drift + network RTT). |
| Fencing token implementation | Monotonic per-resource counter, persisted alongside the lock record so a node restart doesn't reset it; the protected resource (database row, S3 object, etc.) stores "highest token seen" and rejects anything lower — this is enforced outside the lock service entirely. |
| Clock-dependency risk | Redlock's safety proof assumes bounded clock drift and bounded pauses, which async systems cannot fully guarantee; mitigate with NTP-disciplined clocks, conservative TTLs, and treating fencing tokens (not the lock itself) as the actual safety mechanism. |
5. Sequence walkthroughs
Two flows matter more than any other diagram in this design: the quorum acquisition happy path, and the fencing-token check that saves you when the happy path assumptions break.
5.1 Lock acquisition with lease / TTL
The client library never waits for all 5 nodes — only a majority, and only within a time budget short enough that the sum of "time spent acquiring" plus "time already elapsed on the TTL" leaves a safe margin before expiry. If the budget is exceeded, the client releases whatever partial grants it got and retries after a random backoff, so contention resolves without a thundering herd.
5.2 Fencing token preventing a stale-lock write
This is the mechanism that actually makes a distributed lock safe: the lock service can never fully rule out a false expiry under async networks and pausable processes, so safety is pushed one layer down to the storage system, which only needs to remember one integer per resource. Client A's write is not blocked by the lock — it is rejected by storage because it arrives with a token the storage layer has already superseded.
6. Data model (the lock service's own control plane)
This ER diagram is not the application's data — it models what the lock service itself persists (or holds in memory) to track who owns what, for how long, and with which fencing token.
Key modeling decisions
| Storage backend | Trade-off |
|---|---|
| In-memory Redis + TTL (Redlock) | Fastest, simplest; safety depends on the 5-node quorum assumption and bounded clock drift, and is the design Kleppmann's critique targets directly. |
| ZooKeeper ephemeral znodes | Linearizable via ZAB consensus; a znode is auto-deleted when the owning session's heartbeat stops, giving lock release "for free" on crash, at the cost of a consensus round trip per write. |
| etcd leases | Raft-backed, same linearizability class as ZooKeeper; leases are a first-class primitive (attach a lease to a key, key vanishes when the lease expires), often simpler operationally than ZK. |
7. Deep-dive Q&A
"Isn't Redlock provably unsafe? Didn't Kleppmann write a takedown of it?"
Yes, and it's worth knowing the argument, not just the headline. Martin Kleppmann's 2016 critique showed that Redlock's safety proof implicitly assumes bounded process pauses and bounded clock drift — assumptions that async, GC-managed, virtualized systems cannot fully guarantee. His worked example: Client A acquires the lock, then a long GC pause (or VM migration, or swap) freezes it well past the TTL; the lock expires and Client B legitimately acquires it and writes; A wakes up and, still believing it holds the lock, writes too — two "lock holders" both wrote.
Salvatore Sanfilippo (Redis's author) responded that Redlock was never claiming to solve this class of problem alone — the fix he and Kleppmann both converge on is fencing tokens: the lock grants exclusivity in the common case, but the actual safety guarantee against a false-expiry race is enforced by the protected resource checking a monotonic token, not by the lock service's timing assumptions.
"Why are fencing tokens necessary rather than a nice-to-have?"
Because a lock, on its own, is a piece of advice: it tells a client it may proceed, but nothing physically stops a client that has been descheduled and later resumes from also proceeding, unaware time has passed. Without a token, the only way to try to fix this is by shrinking TTLs and hoping pauses never exceed them — which is a bet, not a guarantee. A fencing token converts "please don't write" into "your write will be mechanically rejected if you're late," because the check happens at the point of actual effect (the database write, the file append, the API call), where a simple integer comparison is trivial to enforce correctly.
"Walk me through how a stop-the-world GC pause is actually handled."
The lock service does nothing special for it — that's the point. The lease simply expires on schedule because the paused client's renewal heartbeat silently stops arriving; there is no separate "detect the pause" step. What handles the pause safely is downstream: when the paused client resumes and tries to act as if it still holds the lock, its fencing token is now stale, and the resource it's writing to rejects the write. The lock's TTL bounds how long an orphaned lock can block others; the fencing token bounds what damage a resurrected holder can do.
"How would you build leader election on top of this?"
Every candidate node attempts to acquire a well-known lock key (e.g. leader/order-service) at startup and on any failure. The winner renews it continuously as its heartbeat, and treats "renewal failed / lease lost" as an immediate signal to step down and stop performing leader-only actions — before a competing node can even try to acquire. All leader-only writes must carry the fencing token from that acquisition, so that if two nodes ever briefly believe they're leader (the same GC-pause scenario above), only the writes from the higher token succeed.
// storage-side fencing check, language agnostic
function applyWrite(resourceKey, token, payload) {
const lastSeen = getLastToken(resourceKey); // persisted, not from the lock service
if (token <= lastSeen) {
throw new StaleTokenError(`rejected: token ${token} <= last seen ${lastSeen}`);
}
setLastToken(resourceKey, token);
persist(resourceKey, payload);
}"What happens under a network partition or split-brain?"
For Redlock, if a partition splits the 5 nodes such that no side can see a majority, no side can acquire — the system fails toward unavailability, not toward two holders, which is the correct trade-off for a mutual-exclusion primitive. If the partition heals right at a TTL boundary, it is possible (per Kleppmann's critique) for both sides to have briefly believed they held the lock; fencing tokens are what make that survivable. For ZooKeeper/etcd, the consensus layer itself refuses to make progress without a quorum, so the same "unavailable over unsafe" property holds, plus you get a linearizable, single history of who held the lock and when — useful when you need an audit trail, not just mutual exclusion.
8. Summary
A distributed lock manager is deceptively small in surface area — acquire, renew, release — but the entire interview is really about what backs those three calls: a quorum of independent nodes or a consensus ensemble, a TTL that bounds the blast radius of a dead holder, and a fencing token that is the actual, mechanically-enforced safety net once you accept that no timing assumption is ever airtight.
Post a Comment
Add