Cruxly › System design › Design Exercises

Distributed Lock Service

a lock that can outlive the process holding it

Prompt: design a distributed lock service — clients across many machines acquire a named lock to ensure only one of them runs a critical section at a time (e.g. only one worker processes a given job). Locks must auto-release if the holder crashes.

40 minutes first. The auto-release requirement is where every naive design breaks.

Applying the four moves: Scope — named locks, one holder at a time, auto-release if the holder crashes; general-purpose consensus out. Estimate — acquire latency and how long a typical critical section runs, because the lease length has to exceed the latter by a safe margin. Sketch — a consensus-backed store (not a single node) issuing leases with expiry. Deep dive — auto-release is where naive designs break: a holder that pauses (GC, network stall) past its lease keeps acting as if it still holds the lock, so the lock service issues monotonically increasing fencing tokens and the protected resource rejects any request carrying a stale one.

Why a simple 'acquire, do work, release' lock is unsafe

The requirement "auto-release if the holder crashes" forces a lease with a timeout, not a lock held indefinitely — because there's no way to reliably detect "the holder crashed" versus "the holder is just slow," the same detection problem this track's rate limiter and job scheduler exercises both run into. So: a client acquires the lock for a bounded lease (say, 10 seconds), and must renew it before expiry to keep holding it.

Here is the failure this creates. Client A acquires the lock, then experiences a long pause — a garbage-collection stop-the-world pause, the OS scheduler starving it, a slow disk write, a network partition — for longer than the lease duration. The lock service, having received no renewal, expires A's lease and grants the lock to client B. Client A's pause ends, and it resumes execution with absolutely no way of knowing time passed — from A's own perspective, it still holds the lock, and it proceeds to write to the shared resource. Now A and B are both writing, believing each is the sole holder. The lease timeout did exactly what it was supposed to do, and the system is still broken.

Fencing tokens: making the protected resource reject the stale holder

The fencing token turns "which client thinks it holds the lock" into "which client has the highest token storage has already accepted" — a check the resource itself enforces, independent of the lock service.

A fencing token is a number that strictly increases with every lock grant — a simple counter maintained by the lock service, handed out alongside the lock itself. The protected resource (the database, the file store, whatever the lock is actually guarding) must check the token on every write and reject any write bearing a token lower than the highest one it has already accepted. This is the load-bearing detail: the safety guarantee does not come from the lock service or from the lease timeout at all — it comes from the resource enforcing monotonicity independently. A stale client, no matter how confidently it believes it holds the lock, gets rejected the moment it tries to actually use it, because its token is provably old.

Without fencing, no timeout value is safe. Shortening the lease doesn't fix the fundamental issue — the pause could always be longer than whatever timeout is chosen — it only makes the race window smaller, not zero. Fencing is the only mechanism that closes the gap completely rather than shrinking it.

Building the lock service itself: why single-node isn't enough

A lock service running on one node is itself a single point of failure — if that node dies, every lock in the system is stuck (or, worse, ambiguous: did the lock survive the crash or not?). Real distributed lock services (ZooKeeper, etcd, Redis with the Redlock algorithm, though the last is contested — see below) run as a small consensus-backed cluster (3 or 5 nodes) so a lock grant is only considered valid once a majority of nodes agree it happened, the same majority-quorum idea covered in this track's consensus exercise.

Redlock (multiple independent Redis instances, acquire-a-majority) is worth naming as a real, debated approach — it trades the strict correctness of a proper consensus protocol for lower operational complexity, and its critics (notably Martin Kleppmann) argue it's unsafe under certain clock and GC-pause assumptions. Mentioning this debate by name, rather than presenting Redlock as an uncontroversial standard solution, is itself a signal of depth — the underlying reason it's contested is exactly the same "process pause invalidates timing assumptions" problem this whole exercise centers on.

Session-based locks (ZooKeeper's ephemeral nodes) are the cleaner mental model. The client holds an open session with the lock service; if the session's heartbeat stops (client crash, network partition), the service detects it and releases the client's locks automatically — this still needs fencing tokens for the reason above, but it avoids clients needing to explicitly renew a lease on a timer, pushing liveness detection into the session mechanism instead.

Failure modes and the honest edges

Clock drift between the lock service and the resource checking fencing tokens is a non-issue — fencing tokens are compared as plain integers, never against wall-clock time, which is exactly why they sidestep the clock-skew problems that plague lease-timeout-based approaches elsewhere in this track.

A client that renews its lease successfully but then pauses right after is still safe, because the fencing token only changes on a new grant, and the resource-side check means even a technically-current lock holder writing very late is fine — the token comparison doesn't care about timing, only about strict ordering of grants.

Reentrant locks (the same client acquiring a lock it already holds, common in recursive code) need explicit support or explicit prohibition — decide and state which, because a lock service that silently deadlocks a client against itself is a nasty bug to track down.

What happens to work already in flight when a lease expires and gets reassigned is a question worth surfacing unprompted: if client A's critical section isn't purely a single atomic write but a multi-step operation, fencing tokens on the final write catch the unsafe case, but A may have already caused a partial side effect (sent a network call, written to a different system) before reaching that final, protected write — fencing tokens protect the resource they're checked against, not every side effect a stale holder might trigger before getting there. This is worth naming as the residual risk fencing alone doesn't close.

How to say it in the interview

"A lock that can time out is not the same primitive as the mutex everyone's intuition comes from, because the holder can be paused — by a GC pause, a slow disk, a network partition — for exactly long enough that the lock expires while it still believes it holds it, and the fix is a fencing token, not a longer timeout."

Checklist

Identified that 'auto-release on crash' forces a lease with a timeout, since crash-vs-slow can't be reliably distinguished
Named the exact failure: a paused holder resumes with no way to know a lease expired underneath it
Used a fencing token — a strictly increasing number issued with each grant, not a random ID
Put the enforcement in the protected resource, not the lock service
Explained why no lease timeout value alone is safe without fencing
Ran the lock service itself as a consensus-backed cluster, not a single node
Named the Redlock debate explicitly rather than presenting it as an uncontroversial standard
Clarified that fencing tokens compare as plain integers, sidestepping clock-skew entirely
Decided explicitly whether the lock is reentrant, rather than leaving it ambiguous
Named the residual risk: side effects a stale holder triggers before reaching the fenced write are not protected

Practice this interactively