Walkthrough: Designing a Distributed Lock

The problem

You’re asked to design a distributed lock service — the coordination primitive behind Chubby, ZooKeeper recipes, and SET key NX in Redis. The interviewer says something like: “Multiple service instances must not run the same job twice / write the same file concurrently. Design the lock that guarantees only one holds it at a time.”

Sounds like SETNX with a TTL. It isn’t. The trap is that the easy design is almost correct: it works in every demo and fails precisely during the failures it exists for — a leader failover, a GC pause, a clock jump. This question tests whether you know where the unsafe windows are, and that closing them takes consensus on one side and fencing on the other.

Below is how I’d walk through this, start to finish.

1. Requirements

First 3–5 minutes. Questions I’d ask to pin down what we’re building:

Functional requirements

• R1. acquire(lock_name) / release(lock_name) — named, exclusive locks.
• R2. Auto-release — a crashed holder’s lock frees without operator action.
• R3. Mutual exclusion holds under failures — two clients must never both believe they hold the same lock and have the resource accept both.
• R4. Fencing — each grant carries a token the protected resource can use to reject stale holders.
• R5. Leader election — long-lived “who is primary?” built from the same primitives (the most common production use).

Scope

Explicitly out of scope:

• Consensus algorithm internals (Raft/Paxos message flow — I name the guarantee I’m buying, not re-derive it)
• Read-write locks, fairness queues, reentrancy (variants, not the core question)
• Distributed transactions (a lock is not atomic multi-resource commit; see the distributed transactions reference)
• Quotas/multi-tenancy for the lock service itself

Non-functional requirements

• Efficiency or correctness? The Kleppmann distinction: is the lock avoiding duplicate work (waste, but harmless) or duplicate writes (corruption)? The answer changes how much machinery is justified.
• Hold duration. Milliseconds (hot mutex) or minutes-to-forever (leader election)? Long holds make liveness detection the design center.
• Throughput. Locks/sec? Coordination services are small-data, low-QPS by design — confirm nobody expects 1M acquires/sec.
• Availability bias. During a partition, should the lock service refuse grants (safe) or keep granting (fast, unsafe)? For locks the answer is nearly always CP — worth saying explicitly.

Say the interviewer confirms: correctness locks (protecting writes to shared storage), holds from seconds to hours (leader election included), ~10K lock ops/sec peak, p99 acquire < 50 ms, and during a partition the service must refuse rather than double-grant.

2. Capacity estimate

• Lock operations: 10K/sec peak — trivial QPS.
• State: even 1M concurrently held locks × ~200 bytes ≈ 200 MB. The entire dataset fits in one process’s memory.
• The real cost: every grant must be linearizable, which means a consensus round — a majority round-trip (~1–2 ms same-region) per state change. The ceiling on a 5-node consensus group is tens of thousands of writes/sec.

I’d say out loud: “This is the inverse of every scaling question: the data is tiny and the QPS is low, but every single byte needs the strongest consistency that exists. The design problem isn’t capacity — it’s that correctness here is binary, and the failure modes are the entire question. One consensus group of five nodes serves this; the interesting work is the protocol on top.”

3. High-level architecture

Three logical pieces:

1. Lock service — a small replicated state machine (5 nodes, consensus- backed) holding lock ownership, sessions, and the fencing counter.
2. Clients — acquire, renew their session heartbeat, and watch for changes.
3. Protected resources — storage/services that verify fencing tokens. Making the resource a participant, not a bystander, is the design’s distinguishing move.

flowchart TD
  C1[Client A] --> LS[Lock service · 5-node consensus]
  C2[Client B] --> LS
  LS --> State[(Lock state machine)]
  C1 -->|write + fencing token| Res[Protected resource]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class State store

The state machine decides the system’s character: every acquire, release, and expiry is a command agreed by majority, in one order, on all replicas.

4. Architecture evolution

Each level narrows the unsafe window; only Level 4 closes it — and notably, it closes it outside the lock service.

I’d say out loud: “I’m designing Levels 3 plus 4 together, because Level 3 alone still has the GC-pause hole. And I’d flag that Level 1 remains the right answer for efficiency locks — I’m building the heavier thing because we said correctness.”

Target architecture (Levels 3–4)

Every section that follows explains one part of this diagram:

flowchart TD
  C1[Client A] -->|acquire / heartbeat| Leader[Lock service leader]
  C2[Client B] -->|watch lock| Leader
  Leader -->|consensus replication| F1[Follower]
  Leader -->|consensus replication| F2[Follower]
  Leader --> State[(Lock state machine)]
  F1 --> S1[(Replica state)]
  F2 --> S2[(Replica state)]

  C1 -->|"write(data, token=34)"| Res[Protected resource]
  Res --> Check{token ≥ last seen?}

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class State,S1,S2 store

5. Core design choice: where safety comes from

Three options:

(a) Single Redis. SET lock NX PX ttl with a unique value; release via a Lua compare-and-delete. Mechanically sound on one healthy node. The hole: replication is async. Primary acknowledges the lock, dies; replica — which never saw it — promotes; the next client acquires the “same” lock. Two holders, each with a legitimate grant.

(b) Redlock. Acquire on a majority of 5 independent Redis nodes, count the elapsed time against the TTL. Removes the single failover hole. The remaining assumptions — clocks drift within bounds, clients don’t pause between check and use — are exactly what Kleppmann’s critique attacks: a GC pause after the safety check defeats the safety check.

(c) Consensus-backed sessions. Lock state lives in a replicated state machine (Raft/ZAB). Clients hold sessions kept alive by heartbeats; a lock is an ephemeral record owned by a session; session expiry deletes it — atomically, in the state machine, in one agreed order. This is Chubby, ZooKeeper, and etcd — and it’s the choice here, because the always-refuse- rather-than-double-grant requirement is a linearizability requirement, and quorum-flavored Redis doesn’t provide that (the same R+W>N caveat from the KV-store walkthrough: overlap shrinks staleness; it doesn’t create consensus).

The honest caveat, named immediately: (c) still doesn’t close the stale-holder window. Session expiry is judged by the service’s clock; the holder’s process can be paused, its packets delayed. Fencing (§7) is not an optimization — it’s the other half of correctness.

Tradeoff matrix

Architecture decisions

Core data structures

6. Acquire path [R1, R2, R3]

The slice of the target architecture an acquire touches:

flowchart TD
  C1[Client A] -->|"1 · acquire(jobs/reindex)"| Leader[Lock service leader]
  Leader -->|2 · commit via consensus| F1[Follower]
  Leader -->|2 · commit via consensus| F2[Follower]
  Leader --> State[(Lock state machine)]
  Leader -->|"3 · granted, token=34"| C1
  C1 -->|4 · heartbeat every 3s| Leader

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class State store

Step by step:

1. Client A opens a session (one per process, not per lock) and sends acquire("jobs/reindex").
2. The leader proposes the command through consensus; a majority commits it. The state machine applies it deterministically: lock free → assign to A’s session, increment the fencing counter (33 → 34), append nothing to the wait queue.
3. Grant returns {token: 34}. If the lock was held, A’s request joins the wait queue instead, and A sets a watch — no polling.
4. A’s session heartbeats every ~3 s. Miss the session timeout (~10 s) and the state machine expires the session, releasing all its locks and notifying the head of each wait queue — this is R2, auto-release, with crash cleanup as a single atomic state transition.

Why a wait queue with ordered grants: on release, exactly one waiter (the queue head) is granted and notified. The alternative — notify everyone, race to re-acquire — is the thundering herd, and at leader-election scale (every instance of every service watching its lock) it produces grant storms on every blip. ZooKeeper’s lock recipe encodes the same idea as sequential ephemeral nodes, each watching its predecessor.

7. Fencing: the other half of correctness [R3, R4]

The worked failure, on a timeline:

t0   A acquires "jobs/reindex", token=34. Begins work.
t1   A hits a 25-second stop-the-world GC pause.
t2   A's session misses heartbeats; service expires it; lock released.
t3   B acquires the lock, token=35. Begins work.
t4   A's GC ends. A believes it holds the lock — its last 25 seconds
     never happened, from its point of view. A writes to the resource.

Without fencing, t4 corrupts the resource — and every component behaved correctly: the service expired a dead-looking session; A was merely slow. No tuning of timeouts fixes this; longer timeouts just trade t2’s promptness against t4’s window.

With fencing: every write to the protected resource carries the grant’s token. The resource tracks the highest token it has seen — B’s first write recorded 35 — and rejects anything lower. A’s t4 write arrives with 34 → refused → A learns it lost the lock the only way a paused process ever can: by being told after the fact.

The mechanism is one integer compare, but it relocates the guarantee: mutual exclusion stops being a promise the lock service makes about the future (“nobody else holds this” — unknowable under pauses) and becomes a check the resource makes in the present (“this token is stale” — a fact).

8. Leader election [R5]

Election is the acquire path with a longer lease and a different failure posture:

1. Every candidate instance tries acquire("election/orders-primary").
2. The winner is leader; losers watch and wait. The fencing token doubles as the epoch number — every action the leader takes downstream (writes, replication messages) carries it.
3. Leader death = session expiry = next-in-queue promotion, carrying epoch+1. Downstream systems reject epoch n once they’ve seen n+1 — the same fencing compare, which is why split-brain (two instants of overlapping self-believed leadership) is tolerable: the old leader’s actions bounce.

The detail interviewers probe: a leader that loses connectivity to the lock service must stop acting before its session would expire — step down at session_timeout − safety_margin by its own clock. That margin is the one place a clock assumption legitimately remains, and it errs toward unavailability (a leaderless gap) rather than unsafety (two leaders), which matches the CP bias chosen in §1.

9. API design [R1, R4]

POST /v1/sessions                                  [R2]
  returns: { session_id, timeout_ms }              # heartbeat deadline

POST /v1/sessions/{id}/heartbeat                   [R2]

POST /v1/locks/{name}/acquire                      [R1, R4]
  body:    { session_id, wait: true|false }
  returns: { granted, fencing_token }              # or queued position

POST /v1/locks/{name}/release                      [R1]
  body:    { session_id, fencing_token }

GET  /v1/locks/{name}/watch                        [R1]
  long-poll / stream: fires on state change

Two non-obvious decisions:

Every grant returns a fencing token, and release requires it. The token in the release call makes stale releases harmless (a paused client releasing the lock B now holds is rejected by token mismatch) — the same monotonic compare protecting the resource protects the service.

wait: true queues server-side instead of client retry loops. The queue position comes back immediately, the watch fires on grant — acquire-under- contention costs one request, not a poll storm.

The API hides the consensus topology entirely; clients talk to any node, which forwards to the leader. What it deliberately does not hide is the token — the one piece of lock-service internals the outside world must see, because correctness happens at the resource.

10. Data model and storage

Requirements → components

Access frequency

Storage technology choices

Access pattern matrix

Schemas

lock (state machine):
  name:           "jobs/reindex"
  holder_session: session_id | null
  fencing_token:  monotonic uint64        # increments on every grant, never resets
  wait_queue:     [session_id, ...]       # grant order on release

session (state machine):
  session_id:     uuid
  deadline:       leader-clock heartbeat deadline
  owned_locks:    [lock name, ...]        # cascade on expiry

11. Failure modes

Grouped by what they threaten. The pattern: name what fails, name what degrades, name what doesn’t.

Safety failures

Holder pauses (GC, VM migration, swap)

Fails: the holder’s belief about time. Degrades: nothing at the service — the session expires and the next waiter proceeds; the paused client’s late writes are rejected by fencing (§7’s timeline). Doesn’t degrade: the resource. Without fencing this is the catastrophic case, and it’s why §5 called fencing half of correctness rather than an add-on.

Clock skew

Fails: any design whose safety argument cites wall clocks (Redlock’s TTL accounting). In this design, clocks affect only heartbeat timing — skew makes sessions expire early or late, a liveness wobble, never a double-grant. The one residual: the leader’s step-down margin in §8, which errs unavailable by construction.

Liveness failures

Lock service loses quorum

Fails: all acquires, releases, and session renewals — the service refuses writes. Degrades: deliberately and predictably — current holders keep working until their sessions would expire (the state machine that would expire them can’t commit either; pick the convention and document it), new work queues up. Doesn’t degrade: safety — refusing is the CP promise from §1 doing its job. The mitigation is blast-radius hygiene: many small consensus groups (per-domain lock services) rather than one company-wide one.

Session flapping

Fails: a healthy-but-slow client’s locks, repeatedly — released, reacquired, each cycle incrementing tokens and thrashing downstream epoch checks. Degrades: the jobs it runs (constant restarts). Mitigations: separate the heartbeat thread from the work thread (a busy CPU shouldn’t look dead), size session timeouts above worst-case GC, and back off reacquisition after expiry. Doesn’t degrade: other sessions; correctness anywhere.

Scale failures

Watch herd on a popular lock

Fails: latency, when thousands of candidates watch one election lock and the leader dies — a notification burst followed by an acquire burst. Degrades: acquire latency for seconds. The §6 queue already prevents the worst (only the head is granted); the remaining burst is notification fan-out, bounded by queue-position-only notifications. Doesn’t degrade: the state machine — consensus throughput is untouched because only one grant commits.

12. What I’d skip, and say I’m skipping

Time check — five minutes left. Things I’d explicitly defer:

• Consensus internals. I’m buying linearizable state transitions from Raft; re-deriving leader election inside the lock service is a different interview.
• Read-write locks, semaphores, barriers. Recipes on the same primitives (ZooKeeper’s docs list them); no new failure modes.
• Hierarchical lock namespaces and ACLs. Real services need them (Chubby is practically a filesystem); orthogonal to correctness.
• Cross-region locks. A lock spanning regions pays cross-region consensus latency on every grant — usually the requirement to push back on, not engineer for. Per-region locks with region-scoped resources is the answer to name.
• Whether you need a lock at all. The best designs often replace the lock with idempotency or conditional writes (compare-and-set at the resource). I’d say this out loud at the end — it reframes the whole question — but designing lock-free alternatives is its own conversation.

Saying “I’d skip this, and here’s why” is a strong signal. It shows you know the full surface and are making deliberate scoping choices.

Interview flow summary

Architecture at a glance

ACQUIRE PATH                            STALE-HOLDER DEFENSE

Client opens session                    Holder pauses (GC)
 ↓ heartbeat every ~3s                   ↓
acquire(name)                           Session expires → lock released
 ↓ consensus commit                      ↓
granted + fencing token (n)             Next waiter granted, token n+1
 ↓                                       ↓ writes with n+1
work: every write carries token         Resource records n+1
 ↓                                       ↓
release(name, token)                    Old holder wakes, writes with n
                                         ↓
                                        REJECTED (n < n+1) — safety holds

The walkthrough order for your whiteboard

1. Requirements           — efficiency vs correctness lock; CP bias
2. Capacity               — tiny data, low QPS: correctness is the problem
3. Evolution              — Redis → Redlock → consensus → fencing
4. Core choice            — where safety lives; commit to consensus + fencing
5. Acquire path           — sessions, ephemeral ownership, wait queue, watches
6. Fencing                — the GC-pause timeline; token check at the resource
7. Leader election        — long-lease acquire; token as epoch; step-down margin
8. API                    — token on every grant; server-side wait
9. Data model             — state machine schemas; token = log index
10. Failure modes         — safety / liveness / scale groups

If the interviewer pushes deeper

13. Wrap-up

One crisp sentence before the interviewer’s next question:

This design accepts that no service can promise a paused client isn’t acting, so it splits the guarantee: consensus makes lock grants linearizable, and a monotonic fencing token lets the protected resource itself reject any holder the world has moved past — agreement on the inside, enforcement at the edge.

What separates levels on this question

• SDE II reaches SET NX PX with a TTL and a compare-and-delete release — a correct single-node mutex — and treats node failure as “Redis is HA.”
• SDE III names the failover double-grant, weighs Redlock and its clock assumptions, chooses consensus sessions with watches and ordered grants, and — the differentiator — walks the GC-pause timeline unprompted and closes it with fencing tokens.
• Staff/Principal opens with efficiency-vs-correctness and right-sizes the machinery; knows fencing needs the resource’s cooperation and substitutes idempotency where it can’t get it; derives tokens from the consensus log index; treats the lock service’s blast radius as an operational design input (many small groups); and asks whether a conditional write at the resource could delete the lock from the design entirely.

The difference isn’t knowledge. It’s locating the guarantee — weaker answers make the lock service promise the future; stronger ones make the resource verify the present.

Further reading

• The Chubby lock service for loosely-coupled distributed systems — Google’s paper: why a lock service (not a library), coarse-grained leases, and a decade of operational scar tissue.
• How to do distributed locking — Kleppmann. The fencing-token argument and the Redlock critique this walkthrough leans on; read the Redlock response too and form a view.
• Designing Data-Intensive Applications — Kleppmann. Chapter 8 (truth, clocks, and pauses) and Chapter 9 (linearizability and consensus) are the theory under every section here.
• ZooKeeper recipes: locks and elections — the sequential-ephemeral-node constructions, including the herd-avoiding watch-your-predecessor queue.
• etcd documentation: concurrency API — sessions, leases, and revision-derived tokens in a modern consensus store.
• Redis distributed locks (Redlock) — the primary source for the design this walkthrough deliberately doesn’t pick; know it well enough to say why.