Design a distributed lock

A distributed lock lets many machines agree that only one of them does something right now: run tonight’s settlement job, send merchant 48213’s payout batch, rebuild search shard 17, or lead partition 9 of a stream. On one machine that is a mutex. Across a network it has to become a lease — a lock that expires on its own, because the holder might die — and every hard question follows from that. What if the holder is not dead, only frozen in a 20-second garbage-collection pause, and wakes up still believing it holds the lock? What if the lock server fails over and forgets a grant? What if a clock jumps? In this problem you design a shared lock service that many teams use, at about 50,000 operations a second, and you meet the uncomfortable fact at its centre: no lock service can guarantee mutual exclusion on its own, so the resource you protect has to help.

Understand the problem

Start with one question: what goes wrong if two workers hold the same lock at the same moment? The answer splits the problem in two. If the damage is duplicate work — a report built twice, an SMS sent twice — you need an efficiency lock, and almost anything will do. If the damage is corrupt data — a merchant paid twice, a search shard with two writers — you need a correctness lock, and the bar is far higher. The distinction goes back to Google’s Chubby paper and was sharpened by Martin Kleppmann. This design serves both, but it is built for the second.

Also say out loud what a distributed lock really is: a lease. The service can only promise “nobody else holds this name until the lease runs out”. Turning that promise about time into a guarantee about data needs help from the holder and from the storage it writes to.

Functional requirements

1. Workers should be able to acquire a named lock with a lease — try once and return at once, or wait up to a timeout — and get a fencing token with every grant.
2. Holders should be able to extend and release their locks, and nobody but the holder may extend or release them.
3. A lock should free itself if its holder dies, within one lease period, with no human involved.
4. Waiters should be served in order: a blocked acquire joins a queue and is woken when it reaches the front, without polling.

Shared (reader) locks and semaphores with N holders are natural extensions; we touch on both later.

Non-functional requirements

• Safety first. The service’s own records never show two holders of one name, and losing a server, a zone or the leader never loses or duplicates a grant. Every grant carries a token that only increases, so storage can reject a stale holder.
• Throughput. About 50,000 lock operations a second at peak — acquires, releases, keepalives and reads — across millions of distinct lock names, with about 1 million held at once.
• Latency. An uncontended acquire in the same region at about 2 ms p50 and under 10 ms p99.
• Availability. 99.99% for acquire and renew in a region, about 4.3 minutes of downtime a month. When the service is down, work pauses; it must never carry on unsafely.
• Recovery. A crashed holder’s locks free within one lease, 15 s by default (5–60 s allowed). A lock-server leader failover finishes in seconds and loses no locks.
• Fairness. Waiters for one name are served first come, first served, and nobody starves.

Out of scope

• Transactions across services. Atomic changes across several systems are a job for two-phase commit or sagas; a lock gives isolation, not atomicity.
• Row locks inside one database. The database already does that better; we discuss when to prefer it.
• Service discovery and group membership, although the same machinery could offer them.
• Locks across regions. One region first; cross-region locks are a follow-up.
• Malicious clients. We assume clients run our library and follow the protocol.

The set-up

Plan the approach

Name the shape early: a client library, a lock service, a replicated store underneath it — and the part most people forget, the protected resource, which checks tokens. Build the four requirements on a single lock server, then spend the deep dives on what breaks it: the server failing, the holder pausing, clocks lying, and one lock name getting too hot.

Core entities

• Lock. A name such as payouts/merchant-48213, a mode (exclusive or shared), the holder (session ID plus an owner ID), the fencing token, a re-entry count, and a FIFO queue of waiters.
• Session. One per client process: an ID, a TTL, and the locks and waits that hang off it. When a session expires, every lock it holds is released together.
• Waiter. A session queued for a name, with a deadline after which it gives up.
• Fencing token. A 64-bit number handed out with each grant that only ever increases for a given name.
• Namespace. A team’s slice of lock names, with limits — maximum TTL, maximum waiters, operations per second — and a declared safety class.

A held lock looks like this:

{
  "name": "payouts/merchant-48213",
  "mode": "exclusive",
  "holder": { "session": "s_9f3c", "owner": "payout-worker-17/batch-2210" },
  "token": 7340291,
  "reentry": 1,
  "waiters": ["s_51aa", "s_0c7e"]
}

API

In production this is gRPC, with one bidirectional stream per session for keepalives and wake-ups. It is shown as HTTP for readability.

Open a session. The server picks the TTL it will honour and tells the client how often to keep it alive.

POST /v1/sessions
Content-Type: application/json

{ "client": "payout-worker-17", "ttl_s": 15 }

{ "session_id": "s_9f3c", "ttl_s": 15, "keepalive_every_s": 5 }

Acquire. wait_ms: 0 is a try-lock; a positive value waits in the queue for up to that long.

POST /v1/locks/payouts%2Fmerchant-48213:acquire
Content-Type: application/json

{ "session_id": "s_9f3c", "owner": "payout-worker-17/batch-2210", "mode": "exclusive", "wait_ms": 2000 }

{ "acquired": true, "token": 7340291, "lease_ttl_ms": 15000 }

{ "acquired": false, "holder": "payout-worker-02/batch-2207", "queue_position": 3 }

Keep alive, release and inspect.

POST /v1/sessions/s_9f3c:keepalive            extends every lock held by the session
POST /v1/locks/{name}:release                 body: session_id, token; only the holder succeeds
GET  /v1/locks/{name}                         holder, token, held_for_ms, waiters (for debugging)
DELETE /v1/sessions/s_9f3c                    clean shutdown: releases everything at once

And one convention outside the service: every write a holder makes under the lock carries its token, so the storage can check it. The deep dives explain why that matters more than anything above.

Back-of-envelope estimates

These numbers decide whether one consensus group is enough and how leases must be renewed. (For the method, see back-of-envelope estimation.)

Clients. About 20,000 worker processes across teams: payout and settlement workers, job schedulers, search indexers, booking services and partition leaders.

Operations. Assume 20k acquires/s at peak — the minute a tatkal window opens, or midnight when batch jobs start — and as many releases. Add about 4k session keepalives/s (derived below) and 6k reads such as lock status and try-locks that find the lock taken: 20k + 20k + 4k + 6k = 50k ops/s.

Locks held at once. Holds range from 2 s (allocating berths) to hours (owning a shard). With an average of 50 s, Little’s law gives locks held = arrival rate × time held = 20k/s × 50 s = 1M locks held at once, about 50 per process.

One lease per process, not one TTL per lock. If every lock carried its own TTL renewed every 5 s, that alone would be 1M ÷ 5 s = 200k renewals/s, each a replicated write and four times the whole budget. If locks hang off one session per process, renewals become 20,000 ÷ 5 s = 4k keepalives/s, and the leader can track them in memory rather than writing each to the replicated log, as Chubby’s master does.

Replicated writes. Acquires and releases change state: 20k + 20k = 40k writes/s. etcd’s published benchmark reaches about 44–50k writes/s on one three-member cluster, but at about 20 ms average latency — that is saturation. To keep p99 in single-digit milliseconds, budget about 10k writes/s per group: 40k ÷ 10k = 4 groups, doubled for headroom and failover = 8 groups. At five replicas each, that is 40 small replica processes.

Memory. A lock record is about 200 bytes (name, holder, token, timestamps, queue pointer): 1M × 200 B = 200 MB in total, 25 MB per group. Memory is a rounding error.

Latency. Worker to leader in the same zone, about 0.25 ms. The leader sends the entry to followers in other zones — about 1 ms round trip, our assumption for zones in one region — and each follower fsyncs, which etcd’s guidance puts under 1 ms on SSDs. Apply and reply, 0.25 ms. That is about 2 ms at p50; batching, queueing and slow disks push p99 towards 10 ms.

Token space. Tokens are 64-bit. Even if one group did all 40k writes a second forever: 2⁶³ ≈ 9.2 × 10¹⁸ ÷ 40,000/s ≈ 2.3 × 10¹⁴ s, about 7 million years. Compare ZooKeeper’s sequential-node suffix, a signed 32-bit counter per parent node: a hot lock taking 1,000 acquisitions a second would overflow it after 2,147,483,647 ÷ 1,000 ≈ 2.1M s, about 25 days.

High-level design

Build the four requirements on one lock server first. For concreteness, picture a single Redis instance, because that is where most teams start. The deep dives then replace whatever breaks.

Workers should be able to acquire a named lock

An acquire is one atomic step: create the lock record only if the name is free, with an expiry. In Redis that is a single command, SET lock:payouts:merchant-48213 <owner-token> NX PX 15000. NX sets the key only if it does not exist; PX 15000 expires it after 15,000 ms. The value is a random owner token — the Redis documentation suggests 20 bytes from /dev/urandom — unique to this acquisition, so the holder can later prove the lock is still its own. Our server also returns a numeric fencing token; deep dive three explains why it must exist and where it should come from.

1. The worker asks for payouts/merchant-48213 with a 15 s lease.
2. The server creates the record only if the name is free, in one atomic step, so two simultaneous requests cannot both win.
3. It returns the grant and a token. If the name is taken and the caller said wait_ms: 0, it answers “taken” at once.
4. The worker processes the payout batch and writes the result to the payouts database.

Name locks hierarchically, by namespace and resource (payouts/merchant-48213, search/shard-17, leader/orders-stream/9), so one team’s names never collide with another’s and limits can be set per namespace.

Holders should be able to extend and release their locks

The obvious release is DEL lock:…. It is wrong, and the reason is the first sign of everything difficult in this problem.

The fix is to make release and renewal conditional on ownership, checked and applied in one atomic step. Redis runs a Lua script without interleaving other commands, so two short scripts do it:

-- release.lua: delete the lock only if it is still ours.
-- KEYS[1] = lock key, ARGV[1] = our owner token
if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
end
return 0

-- renew.lua: push the expiry out only if the lock is still ours.
-- KEYS[1] = lock key, ARGV[1] = our owner token, ARGV[2] = new TTL in ms
if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("PEXPIRE", KEYS[1], ARGV[2])
end
return 0

A return of 0 is information: the lock is no longer yours, so stop. Redis 8.4 added DELEX key IFEQ value, which does the release in one command; the script works on any version.

Notice what the fix does not do. Worker A still did its work after its lease ran out; it simply no longer deletes B’s lock. Stopping A from writing is a different problem, solved in the deep dives.

Renewal also has a cost problem at our scale. Per-lock TTLs mean a renewal per lock, and the estimate showed that is 200k writes a second. So in our service the TTL belongs to a session, and locks hang off it.

This is how the consensus-backed lock services work. Chubby’s clients send KeepAlive calls that extend the session lease — 12 s per extension by default — and an etcd lock is a key attached to a lease that the client library refreshes every third of its TTL. Each session is one stream, so a keepalive costs the leader a timer update, not a disk write.

A lock should free itself if its holder dies

The lease is what makes a distributed lock usable at all. Without it, one worker that crashes while holding payouts/merchant-48213 blocks that merchant’s payouts until someone notices. With it, the server sees the session miss its keepalives, ends the session one TTL after the last renewal, deletes every lock it held, and grants each to its next waiter.

The expiry is decided by the server, on its own clock, never by the client. The worst-case unavailability after a crash is one TTL; we pick 15 s as the default and let namespaces choose 5–60 s. A clean shutdown deletes the session explicitly, so the common case — a deploy restarting workers — frees locks at once rather than after 15 seconds.

This is also the root of every hard problem that follows. The server cannot tell a dead holder from a slow one. When it expires a lease, it is betting that the holder is gone, and sometimes it loses that bet.

Waiters should be served in order

The simplest way to wait is to retry a try-lock in a loop. With 50 workers waiting for search/shard-17 and each retrying every 100 ms, that is 500 calls a second for a lock that changes hands rarely, and every release starts a stampede in which 49 lose. So the server keeps the queue instead.

The record keeps a FIFO list of waiting sessions. On release or expiry the server grants the lock to the head of the queue and pushes one message down that session’s stream. ZooKeeper’s lock recipe gets the same effect without server help: each waiter creates a sequential node and watches only the node just ahead of it, so a release wakes exactly one client, which the recipe calls avoiding the herd effect. Waiters whose wait_ms passes drop out, and the server skips waiters whose sessions have expired rather than handing a lock to a ghost.

You now have a working lock service: atomic acquire, owner-checked release, session leases and a fair queue. It runs on one server, which can die, and it trusts that a holder whose lease has expired stops writing. The deep dives take both apart.

Deep dives

How do we decide how strong the lock must be?

Every later decision depends on the answer, so make it explicit. Chubby’s authors drew a related line between coarse-grained locks, held for hours to elect a primary, and fine-grained ones held for seconds; Kleppmann’s sharper question is what a lock failure costs.

Bad: one lock design for every caller, chosen by habit. Teams reach for whatever is installed. A Redis lock guarding payouts is a correctness bug waiting for a failover; a five-node consensus lock guarding a nightly thumbnail job is cost and latency for nothing.

Good: two products, a cheap one and a strict one. A Redis-backed tier for efficiency, a consensus tier for correctness. You gain the right price for each use. You pay with two systems to run, and teams pick the cheap tier for correctness work because it is faster.

Great: one strict service, and a declared safety class per namespace. At 50k ops/s the strict service costs eight small consensus groups, which is cheap. Efficiency users simply ignore the token. Correctness namespaces must declare how their resource checks tokens before they get one — “payouts DB, conditional update on fence” — and the service team reviews it. You gain one system and a forcing function for the conversation that matters. You pay 2 ms instead of 0.3 ms per acquire, which no efficiency user has ever noticed. Teams that truly need sub-millisecond, best-effort locks can still run their own Redis — Kleppmann’s advice for that case is exactly one node, not five.

How do we keep locks when the lock server fails?

Bad: a Redis primary with an asynchronous replica. Add a replica and let failover promote it. Redis replicates asynchronously, so the primary acknowledges a write before any replica has it. The Redis documentation spells out the race.

Even WAIT, which blocks until replicas acknowledge a write, is documented as best effort: a write that reached a replica can still be lost if a different replica is promoted. You gain simplicity and sub-millisecond locks. You pay with an occasional double grant on every failover — fine for efficiency locks, wrong for ours.

Good: Redlock across five independent masters. Salvatore Sanfilippo’s Redlock uses N independent Redis masters, with no replication between them; five is the suggested N. To acquire:

1. Read the current time in milliseconds.
2. Send SET key token NX PX ttl with the same key and random token to all five in parallel, each with a short timeout — for a 10 s TTL, somewhere in the 5–50 ms range — so a dead node cannot stall you.
3. Read the time again. The lock is yours only if a majority (three) said yes and the elapsed time is less than the TTL.
4. The lock is then valid for the TTL minus the elapsed time, minus an allowance for clock drift.
5. If you failed, release on all five, including those that seemed not to answer.

The drift allowance in the figure, 1% of the TTL plus 2 ms, is our assumption; the Redis page asks only for “a few milliseconds”. Restarts need care: a node that crashes and comes back empty can let a second client assemble a majority, so the documentation asks you either to fsync every write or to keep a crashed node out for longer than the longest TTL. Extending a Redlock means running a compare-and-extend script on all five and again needing a majority. You gain tolerance of two failed nodes with no consensus software, at Redis speed. You pay five round trips per operation, a safety argument that rests on timing assumptions, and no fencing token — the next deep dive explains why those last two matter.

Great: a consensus group. Run each lock store as a replicated state machine — Raft as in etcd, Zab as in ZooKeeper, Paxos as in Chubby. One leader orders all writes into a log; an entry counts as committed only when a majority of replicas has it on disk, and only a replica holding every committed entry can become leader. A grant is a log entry, so before any client hears “granted”, a majority has it, and every future leader inherits it. Failover cannot forget a lock.

There is a deeper reason to prefer consensus. The Chubby paper puts it in one line: “Paxos maintains safety without timing assumptions.” Timeouts in Raft or Zab only decide when to elect a new leader — a liveness question — never whether two leaders can both commit. A consensus store also gives you, for free, a counter that only goes up: the log position. You gain locks that survive any minority failure and a ready-made fencing token. You pay about 2 ms per write instead of 0.3 ms; a ceiling of tens of thousands of writes a second per group, since one leader orders everything (etcd’s benchmark peaks near 50k/s, at 20 ms latency); and pauses during leader elections, which Chubby measured at 4–6 s and occasionally 30 s.

How do we stop a paused holder from corrupting data?

Now the uncomfortable part. Suppose the lock service is perfect. A worker acquires the lock, reads the payout batch, and then stops — a stop-the-world garbage collection, a VM migrated by the hypervisor, a page fault on a congested network disk. Kleppmann notes that HBase once had exactly this bug, and that GitHub once saw packets delayed for about 90 seconds. The lease expires, another worker gets the lock and pays the batch, and then the first one wakes up and pays it again. It never “knew” it had lost the lock; no check it could have made between waking and writing is immune to another pause in between.

Bad: check the lease just before each write. It narrows the window and never closes it — a pause can land between the check and the write, or the write can sit in the network after it has been sent.

Good: lock-delay. Chubby’s answer for servers that cannot check anything: when a lock is freed because its holder failed, rather than released cleanly, the lock server keeps it unavailable for a lock-delay, which clients may set up to a bound of one minute. Late messages from the old holder have time to drain. You gain protection for unmodified resources. You pay longer unavailability after every crash, and it is still a guess about how late a message can be.

Great: fencing tokens. Every grant returns a number that is larger than every earlier grant for that name, and the holder attaches it to every write. The resource remembers the highest token it has accepted and refuses anything lower.

For a database, the check is one conditional write in the same statement as the change:

-- The batch row remembers the highest token that has ever written it.
UPDATE payout_batches
   SET status = 'sent', sent_at = now(), fence = :token
 WHERE batch_id = 2210
   AND fence <= :token;   -- 0 rows updated: a newer holder exists, so stop

Object stores and key-value stores offer the same shape through conditional writes on a version, and etcd itself can guard a write with a transaction that compares the lock key’s create revision. The token must come from somewhere that never goes backwards, even across failover:

• ZooKeeper: the zxid, a total order over every change, so the lock node’s creation zxid works. Kleppmann also suggests the znode version.
• etcd: the lock key’s create revision, from a 64-bit counter bumped on every change to the store; Jepsen recommends exactly this.
• Chubby: a sequencer, an opaque string holding the lock name, mode and lock generation number, which the receiving server validates.
• Our service: the group’s log revision at the moment of the grant.

Two limits are worth saying. The resource has to take part — Kleppmann stresses that the storage must actively reject tokens that go backwards — so each correctness namespace names its fenced resource up front. And fencing gives isolation, not atomicity: a holder that crashes halfway through a three-step update leaves the first two steps behind, as Jepsen also points out. Make multi-step work resumable (a follow-up below).

How real is the danger? Jepsen tested etcd 3.4.3 and found its key-value operations strict-serializable under every fault they injected, yet its locks failed: with 1–3 s lease TTLs, two clients held the same lock within minutes even in healthy clusters, and with 2 s TTLs and regular process pauses about 18% of acknowledged updates to a lock-protected set were lost. Their conclusion is that distributed locks in general do not provide mutual exclusion; the store’s ordering — a fencing token — does.

The Redlock debate, from both sides. In February 2016 Kleppmann argued that Redlock fails on two counts. It has no fencing token — the random value is not monotonic, a counter on one Redis node dies with that node, and counters on several nodes drift apart, so you would need consensus just to make tokens. And its safety rests on timing: bounded network delay, bounded pauses and bounded clock error. He showed a clock on one of five nodes jumping forward, expiring its key early and letting a second client form a different majority; Redis expires keys using wall-clock time, which NTP or an administrator can step. His verdict: too heavy for efficiency locks, not safe enough for correctness.

The next day Sanfilippo replied. If your resource can reject stale tokens, he argued, it is already a linearizable store and could issue its own numbers; failing that, the random token supports check-and-set — mark the resource with your token, and write only if it is still there. Many locks guard things that can check nothing at all, such as an external API, where no token helps. On timing, Redlock needs clocks that count time at about the same rate — 5 s measured within 10%, say — not synchronised clocks; he agreed Redis should move to monotonic time. And a pause or delay during acquisition is caught, because the client reads its clock again after reaching a majority and discards a lock that took too long; a pause after that hits every lock with auto-release equally.

Where they agree matters most: no lease-based lock stops a holder that keeps working after expiry, so something at the resource must check. Where they differ is whether safety may rest on timing bounds. Our verdict follows the comparison table. For efficiency, one Redis node; Redlock adds availability you rarely need. For correctness, a consensus store plus fencing, because a monotonic token needs a linearizable counter anyway, and consensus keeps its safety when clocks and pauses misbehave. The Redis documentation now says as much in its own disclaimer: implement fencing tokens, and note that Redis does not use a monotonic clock for key expiry.

How do we choose lease timings when clocks and pauses lie?

Fencing protects the data; good timing keeps fencing rejections rare. Three numbers matter: the TTL, the renewal interval, and the holder’s safety margin.

Bad: wall-clock expiry timestamps. Storing “expires at 10:00:15” and comparing it on another machine’s clock. NTP steps, an administrator, or a VM resumed after migration can move a wall clock by seconds in either direction.

Good: server-side TTLs on a monotonic clock. The leader measures each lease with a clock that only moves forward, and only the leader decides expiry; machines exchange durations, never timestamps. Holders renew at a third of the TTL — etcd’s client library does exactly this — so two lost renewals in a row are survivable.

Great: the holder also keeps its own, earlier deadline. Before sending an acquire or a keepalive, the holder notes its monotonic time. When the reply arrives, it sets its deadline to send time + TTL − margin. Measuring from the send, not the reply, means a slow reply only makes it more cautious. Chubby’s client works the same way: it keeps a local lease timeout that is a conservative estimate of the master’s, and assumes the master’s clock runs no more than a known factor faster than its own.

At its deadline the holder stops: no new writes, cancel calls in flight, record that the work needs recovery, and re-acquire from scratch for a new token if it still wants the lock. It must never “just finish this last write”. A pause can still strike after the check, which is why fencing stays.

Picking the TTL is a straight trade. Short leases free a dead holder’s locks quickly but expire live holders during ordinary GC pauses and network blips — Jepsen saw 1–3 s TTLs fail within minutes. Long leases are safe but leave the lock idle after a crash. A 15 s default with 5 s renewals and a 3 s margin suits jobs that last seconds to hours.

Two more rules. Disconnected is not expired, but treat it as if it were. ZooKeeper’s guide is explicit that the cluster, not the client, decides when a session expires, and a partitioned client is only told when it reconnects; so a holder that cannot reach the service pauses its work as soon as its local deadline passes. A new leader keeps old leases. After a fail-over, Chubby’s new master extends every session lease to the longest the old master might have granted, and makes clients present a new epoch number so stale packets are refused. We do the same: recovery is slower by one election, and no lease ends early.

How do we scale to 50k operations a second and tame hot locks?

Sharding. One group tops out well below our 40k writes a second at acceptable latency, so split the name space. Hash each name into one of 4,096 buckets and keep a small, versioned shard map from buckets to groups in its own consensus store; frontends and client libraries cache it. Chubby’s paper suggests the same structure for fine-grained locks: partition locks into groups and use a coarse-grained lock to assign each group to a lock server, which needs only a monotonically increasing acquisition counter.

Three details keep sharding honest. Sessions are per group: a client opens one lazily for each group it touches. Even if every process touched all eight, that is 20,000 × 8 ÷ 5 s = 32k keepalives a second, 4k per leader, handled in memory. Tokens stay monotonic when a bucket moves: the receiving group raises its revision above the sending group’s before accepting the bucket. No atomic multi-group locks: a job that needs two names takes them in sorted order, so two jobs never wait on each other in a cycle.

Hot locks. Sharding spreads names, not traffic on one name. A lock serialises its holders, which sets a hard ceiling. If allocating berths for one train, date and class takes 20 ms under the lock, plus two lock writes of about 3 ms each, at most 1 ÷ (20 + 6) ms ≈ 38 holders a second get through. At the 10:00 tatkal rush that one bucket might see 2,000 attempts a second, so 98% of callers wait or time out.

• Bad: everyone retries in a tight loop. Each release triggers a stampede, and timed-out callers retry on top — a retry storm aimed at one group leader.
• Good: a bounded FIFO queue plus jittered backoff. The server hands the lock to the next waiter, caps the queue (say 500) and rejects the rest immediately with a hint to come back later; try-lock callers back off exponentially with full jitter. It is fair and cheap, but the ceiling is still 38 a second.
• Great: stop using a lock for that resource. Let one holder serve many requests per acquisition — grab the lock once, allocate a batch of 200 bookings, release. Better still, turn the bucket into a single-writer queue or an atomic conditional update, as the next deep dive shows.

The same record supports the usual refinements. Re-entrancy is an owner ID plus a count, so the same task can acquire twice and must release twice; offer it opt-in, because it hides bugs. Shared locks let many readers hold a name while writers wait, and FIFO order stops writer starvation: a reader that arrives behind a waiting writer queues behind it, as in ZooKeeper’s shared-lock recipe.

How do we avoid needing a lock at all?

The best distributed lock is the one you do not take. Before a team gets a namespace, ask whether its problem has a simpler shape.

Bad: a lock around every write. Each operation pays two replicated writes and a lease, the lock service becomes a dependency of every request, and the data still needs fencing.

Good: let the store that holds the data do the locking. When all the state lives in one relational database, its own locks are the lock and the fence, because the write happens in the same transaction. SELECT … FOR UPDATE locks a row until commit, and a connection that dies releases it. FOR UPDATE SKIP LOCKED lets workers claim jobs without waiting on each other (see isolation levels in practice). For a named lock with no row to hang it on, PostgreSQL advisory locks can be held per transaction or per session and are released automatically when the session ends. Session-level ones misbehave behind a transaction-pooling proxy, where your next statement may run on a different connection. Where contention is low, optimistic concurrency is simpler still: read a version, write only if it is unchanged, retry on conflict — a conditional put or a WHERE version = :v clause, with no lock at all. Under heavy contention the retries pile up; see optimistic vs pessimistic locking.

Great: one writer per key, by construction. If work arrives as a stream, route everything for a key to a single consumer. Publish payout jobs to a Kafka-style topic keyed by merchant ID; each partition has exactly one consumer in the group, so merchant 48213’s jobs run one at a time, in order, without a lock call.

Ownership still changes when consumers come and go, and a slow old consumer can overlap briefly with the new one. Kafka handles that the way this article recommends: each rebalance bumps the group’s generation, and commits from an older generation are rejected — a fencing token under another name (see the Kafka design). Outputs written outside Kafka still need to be idempotent. You gain ordering and exclusivity with no lock traffic. You pay with a pipeline built around partitions, and per-key throughput limited to one consumer.

The final design

Put the pieces together. The hot path is client library, frontend and one group leader; the protected stores do the fencing; everything else is off to the side.

Follow one payout batch through the system:

1. Session. The worker’s client library opens a session with each group it uses, with a 15 s lease kept alive every 5 s over one stream.
2. Route. It asks for payouts/merchant-48213. A frontend authenticates the team, checks the namespace quota, hashes the name to bucket 1300, finds group 3 in the cached shard map and forwards to that group’s leader.
3. Grant. If the name is free, the leader commits the grant through a majority of five replicas in about 2 ms and returns the log revision as the token. If not, the session joins the name’s FIFO queue and is woken when it reaches the front.
4. Work. Every write the worker makes carries the token; the payouts table applies it only if fence <= token.
5. Renew or stop. Keepalives extend the lease. If they fail, the worker stops at its local deadline — send time + 15 s − 3 s — and re-acquires later for a new token.
6. Release or expire. A release is checked against the owner. If the session dies instead, the leader frees its locks one TTL after the last keepalive, applies the namespace’s lock-delay if it has one, and hands each lock to its next live waiter.
7. Observe. Every grant, release, expiry and fencing rejection goes to an event stream. The metric that matters most is lease expired while the holder was still working: each one is a fencing check that saved you, and a rising count means TTLs are too short or holders too slow.

Check it against the requirements: grants survive any two of five replicas failing and are never doubled; tokens rise monotonically per name, and stores reject stale ones; eight groups at about 5k writes a second each leave half the budget spare; uncontended acquires take about 2 ms; dead holders free their locks within 15 s; waiters are served first come, first served.

What interviewers look for by level

Follow-up questions

What if the lock must work across regions?

Then every grant pays a cross-region quorum. A group spread over three regions commits only when a second region has the entry, which costs tens of milliseconds within one country and 100 ms or more between continents; etcd’s documentation quotes up to 400 ms between continents. Prefer giving each lock name a home region where its group lives, so callers there stay fast and others pay a remote call; if the home region is down, those names are unavailable rather than doubled. Better still, partition the work by region so cross-region locks are rare. See multi-region and active-active.

What if the protected resource can’t check fencing tokens?

An external payment API will not compare your tokens. Use an idempotency key derived from the work itself — payout-batch-2210, not the token — so a second holder sending the same batch is deduplicated by the provider. Before retrying, ask the provider for that key’s status. Record intent in your own database first, fenced by the token, so only the current holder can move a batch from “sending” to “sent”. Add a lock-delay to that namespace to drain stragglers.

What if we need a semaphore rather than a mutex?

Allow N holders: in the queue, the first N live waiters hold the lock. On ZooKeeper or etcd you would build it the same way: the N lowest sequence numbers or create revisions hold it. Each holder still gets its own token, but fencing gets harder, because the resource must accept N current tokens; semaphores therefore suit capacity limits such as “at most 10 exports per tenant”, not exclusive writes.

What if a holder crashes halfway through its work?

The lock gives isolation, not atomicity, so the next holder inherits whatever was left. Make the work resumable: record progress against the batch (“items 1–400 sent, token 7340291”), make each step idempotent, and have the next holder read that record and either finish or roll back. Where steps span services, use a saga with compensations.

What if lock traffic is dominated by one hot key?

Do the arithmetic first: a lock admits at most one holder per critical-section time, so 26 ms per holder caps it at about 38 a second. Then shrink the critical section, batch many requests per acquisition, or split the resource — book berth blocks per coach instead of per train. If the key is inherently hot, give it a single owner: one process holds the lock for hours as its leader and serves every request through an in-memory queue. That is leader election, and the lock is taken once, not 2,000 times a second.

How to say it in the interview

“I’d start by asking what the lock protects. If two holders only cause duplicate work, I’d use one Redis node: SET with NX and a TTL, a random owner token, and a compare-and-delete script to release. If two holders could pay a merchant twice, the lock alone can’t prevent it, so the design changes.

For correctness I’d build on consensus: groups of five replicas over three zones, Raft or Zab underneath, so a grant is on a majority before anyone hears about it and failover never forgets it. A primary with an async replica can, and Redlock leans on timing assumptions and has no fencing token.

Clients open one session per process with a 15 second lease and renew every 5 seconds; locks hang off the session, so a dead process loses them all within one TTL, and renewals are 4,000 a second instead of 200,000. Every grant returns a fencing token, the group’s log revision, and the payouts table applies a write only if its token is at least the highest it has seen. That is what makes a paused holder harmless.

Holders measure their own deadline on a monotonic clock from when they sent the renewal, minus a 3 second margin, and stop there. Waiters queue first in, first out, and only the next one is woken.

Scale: 50,000 operations a second is about 40,000 replicated writes. At 10,000 per group with headroom, that’s eight groups, with names hashed to buckets through a shard map. A hot lock caps at one holder per critical section, about 38 a second in my example, so I’d batch, split the resource, or replace the lock with a single-writer partition or a conditional update.”

Concepts used in this design

• Distributed locking — leases, fencing tokens and their limits.
• Consensus and leader election — why a majority-committed log never forgets a grant.
• ZooKeeper and etcd — the sessions, ephemeral nodes, leases and revisions the design borrows.
• Redis — SET NX PX, Lua scripts and asynchronous replication.
• Data replication — why an asynchronous replica can lose an acknowledged lock.
• CAP theorem and PACELC — choosing unavailable over doubled locks.
• Clocks, ordering and conflict resolution — monotonic time and logical counters.
• Heartbeats — keepalives and why missing ones cannot prove death.
• Concurrency control — locks, isolation and conflicts inside one database.
• Optimistic vs pessimistic locking — version checks as an alternative to a lock.
• Idempotency — protecting resources that can’t check tokens.
• Timeouts, retries and backoff with jitter — polite waiting for a busy lock.
• Contention and double booking — hot resources such as seats and berths.
• Consistent hashing — another way to spread lock names over groups.
• Kafka — partitions and consumer generations as a single-writer alternative.
• Design a job scheduler — a heavy user of locks and leader election.

References and further reading

1. How to do distributed locking (Martin Kleppmann, 2016)martin.kleppmann.comEfficiency versus correctness locks, the paused-client problem, fencing tokens, and the argument that Redlock depends on timing assumptions.
2. Is Redlock safe? (Salvatore Sanfilippo, 2016)antirez.comThe Redlock author’s reply: unique tokens with check-and-set, clocks that only need to count time at a similar rate, and why delays during acquisition are caught.
3. Distributed locks with Redis (Redis documentation)redis.ioSET NX PX, safe release, why failover breaks single-instance locks, the Redlock steps, delayed restarts, and the advice to add fencing tokens.
4. The Chubby lock service for loosely-coupled distributed systems (Mike Burrows, OSDI 2006)research.google.comCoarse-grained advisory locks, sequencers, lock-delay, session leases and KeepAlives, grace periods and what a new master does after fail-over.
5. ZooKeeper recipes and solutionszookeeper.apache.orgThe ephemeral-sequential lock recipe, watching only the predecessor to avoid the herd effect, shared locks and the GUID trick.
6. ZooKeeper programmer’s guidezookeeper.apache.orgzxid ordering, the 32-bit sequential counter, ephemeral nodes, and why the cluster, not the client, decides when a session has expired.
7. etcd API: revisions, transactions and leasesetcd.ioThe 64-bit store revision, create and mod revisions, If/Then/Else transactions, and leases refreshed over a keep-alive stream.
8. etcd performanceetcd.ioCommit latency is network round trip plus fdatasync; benchmark write and read throughput for a three-member cluster.
9. Jepsen: etcd 3.4.3 (Kyle Kingsbury)jepsen.ioStrict-serializable key-value operations, yet locks that two clients held at once — and the lock key’s revision as a fencing token.
10. PostgreSQL documentation: explicit lockingpostgresql.orgRow-level locks and advisory locks held per session or per transaction, released automatically when the session ends.