Designing a distributed lock service

The problem

Design a distributed lock service: a way for processes on different machines to agree that only one of them holds a lock on a resource at a time (leader election, exclusive access to a file, preventing duplicate work). On a single machine a mutex does this; across a network, locks are surprisingly treacherous — this problem is really about understanding why.

Step 1 — Requirements

Functional: acquire(resource, owner, ttl), release(resource, owner), optionally renew. Only one owner holds a given lock at a time.

Non-functional: correctness/safety (never two holders — the whole point), liveness (a crashed holder’s lock is eventually released), availability, and low latency. Safety usually beats availability here (CP).

Step 2 — Why network locks are hard

Three failure modes make naive locks unsafe:

• The holder crashes while holding the lock → without a timeout, the lock is stuck forever. → Locks need a TTL/lease.
• The TTL expires while the holder is still working (a long GC pause or slow network) → the lock is granted to someone else, and now two processes act on the resource. → Need fencing (below).
• The lock service itself partitions → must not grant the same lock on both sides. → Need consensus/quorum.

Acknowledging these up front is the senior signal — most candidates draw a naive lock and miss them.

Step 3 — A simple lease lock (and its flaw)

The common starting point: a lock in Redis with a TTL.

SET lock:resource <owner> NX PX 30000     # set if absent, expire in 30s
release: delete only if value == my owner  (atomic via Lua)

NX gives mutual exclusion; PX (TTL) handles a crashed holder. But if the holder pauses past the TTL, a second holder acquires it — two holders. This lease lock is fine for efficiency (“usually only one runs”) but not safe for correctness without fencing.

Step 4 — Fencing tokens (making it safe)

Each lock grant returns a monotonically increasing fencing token. The protected resource (DB, storage) rejects any write with a token lower than the highest it has seen. So even if an old, paused holder thinks it still holds the lock, its writes are rejected because a newer holder has a higher token. This converts a lease lock into a safe one — name it explicitly.

Step 5 — Making the lock service itself reliable

A single lock node is a SPOF. Production lock services run on a consensus cluster:

• ZooKeeper — ephemeral sequential znodes: each client creates a node; the lowest sequence holds the lock; ephemeral means a crashed client’s node vanishes (auto-release); others watch their predecessor (no busy-wait).
• etcd — leases + compare-and-swap on a Raft-replicated key.
• Redlock — a multi-node Redis algorithm (acquire on a majority); controversial for strict correctness — prefer consensus-based locks when safety matters.

These use a quorum so a partition can’t grant the lock twice (CP).

Trade-offs to raise

• Safety vs availability — a strict lock is CP; during a partition it may refuse to grant rather than risk two holders.
• Lease length — too short → spurious expiry under load; too long → slow recovery from a crashed holder.
• Efficiency locks vs correctness locks — a Redis lease lock is fine to avoid duplicate work; only correctness-critical resources need fencing + consensus.

The interview cue

“A lease with TTL handles crashes; but a paused holder can outlive its lease, so for correctness I add fencing tokens that the resource enforces. The lock service runs on a consensus cluster (ZooKeeper ephemeral znodes / etcd) so a partition can’t double-grant — it’s CP.” Surfacing the TTL-expiry-while-working hazard and fencing is exactly what this problem tests.