← CatZep/Engineering Guides/System Design/Coordination, Money & Markets

Designing a Distributed Lock

A system design interview guide to mutual exclusion and single-leader selection across many machines — making sure that only one process at a time holds a lock or acts as the leader, even when nodes crash, pause, or get cut off from the network.

On a single machine, mutual exclusion is a solved problem: the operating system gives you a mutex, and the hardware guarantees that only one thread holds it. Spread the same job across many machines and that guarantee evaporates. There is no shared memory to put the mutex in, the machines can fail independently, and their clocks do not agree. A distributed lock tries to recreate "only one holder at a time" on top of that hostile environment, and a closely related problem — leader election — is just the special case of "exactly one machine should be in charge." This guide explains why these are genuinely hard, builds a lock from a store with a lease, adds fencing tokens to make it safe, walks through the famous pitfalls of naive lock implementations, and then covers leader election and split-brain avoidance.

Concepts to understand first

Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.

1. Requirements & Clarifying Questions

"Design a distributed lock" is vague on purpose. Ask these first:

• What does the lock protect? If two holders at once only waste work, this is an efficiency lock. If it corrupts data or money, it is a correctness lock. This one answer decides most of the design.
• How long is it held? Milliseconds (a counter update) or minutes (a batch job)? This sets the TTL and whether you need renewal.
• How many locks, how often? A few leader roles, or one lock per order at thousands per second?
• Can the protected resource check a token? If it cannot, you cannot fence, and you must say so.
• Do waiters queue, or just try again? Fair FIFO queues need more machinery than try-lock.

2. Back-of-Envelope Estimation

Take a busy job system: 50K acquires/s, each lock held about 10 s, TTL 30 s with renewal every 10 s.

3. API & Data Model

acquire(key, ttl_ms, wait_ms=0) -> { lease_id, fencing_token, expires_at } | LOCKED
renew(key, lease_id, ttl_ms)    -> { expires_at } | LOST
release(key, lease_id)          -> OK | NOT_OWNER

# one record per lock
lock_key       string   # e.g. "order:1842"
owner          string   # random lease id, unique per acquire
fencing_token  int64    # strictly increasing per key
expires_at     time     # judged by the lock service's clock only

Clients should not compare expires_at with their own wall clock. Clocks drift. A client should track time left with a local monotonic timer that starts before it sends the request, so it always underestimates what it has.

4. Why It Is Hard

The difficulty of distributed locking comes from three facts about distributed systems that simply are not true on one machine. Any design that ignores them will look correct in a demo and corrupt data in production.

• No shared memory. There is no single piece of RAM that all the machines can compare-and-swap on. The "lock" has to live in some external service that everyone agrees to consult, which means acquiring it is a network call that can be slow, lost, or duplicated.
• Partial failure. A node that holds the lock can crash, hang, or be partitioned away at any instant — and the rest of the system cannot tell the difference between "the holder is dead" and "the holder is just slow." If you wait forever for a dead holder, the system stalls; if you assume it is dead too eagerly, you may hand the lock to a second holder while the first is still alive.
• Clock skew. Machines disagree about what time it is, and clocks can jump (NTP corrections, virtualization pauses). Any scheme that relies on different machines having the same notion of "now" — including naive timeouts — is fragile.

Put together, these mean you can never build a distributed lock that is simultaneously perfectly safe and perfectly live. The honest goal is a lock that is safe by construction — it never lets two holders both successfully mutate the protected resource — and reasonably live, recovering automatically when a holder dies. The mechanisms in the rest of this guide are all in service of that "safe even under partial failure" property.

5. A Lock with a Lease

The first building block is to put the lock in a shared store (a key-value store, a database, a coordination service) and give it a lease: a time-to-live after which the lock automatically expires. A client acquires the lock by atomically creating a key only if it does not already exist, with a TTL attached. If the holder dies without releasing, the key expires on its own and the lock becomes available again — no human has to clean up after a crashed process.

The lease is what makes the lock live in the face of partial failure. Without it, a holder that crashes would keep the lock forever and the whole system would deadlock. The TTL is, in effect, the system's answer to "how long do we wait before assuming the holder is dead?" Set it too short and a slow-but-alive holder loses its lock; set it too long and recovery after a real crash is sluggish. There is no perfect value, which is exactly why the lease alone is not enough for safety — and why fencing tokens, covered next, are needed.

# acquire: atomic create-if-absent with a TTL lease
function acquire(lock_key, owner_id, ttl):
  ok = store.set_if_absent(lock_key, owner_id, expire=ttl)
  return ok          # true only if we created the key

function release(lock_key, owner_id):
  # must be ONE atomic step: compare the owner, then delete
  store.compare_and_delete(lock_key, expected=owner_id)

-- Redis: EVAL this with KEYS[1]=lock key, ARGV[1]=owner id
if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
else
  return 0
end

The owner id must be unique per acquire (a random token), not just the host name. Otherwise a restarted process on the same host could release a lock that a different run of it took.

6. Fencing Tokens

A durable authority issues a monotonic, nonreused grant token. The resource atomically compares it with its durable highest accepted token and applies the effect. Check and write cannot be separate calls.

UPDATE resource SET data=:data, fence=:token
 WHERE id=:id AND fence <= :token;
-- Check affected rows; persist fence and effect together.

Activation boundary: granting 34 does not instantly update a separate resource. Old 33 can pass until the new fence is installed there. If exclusion begins at the new grant, synchronize resource activation or check authoritative ownership on each effect. Fencing orders recognized grants, not proof of unexpired lease validity.

Equal tokens support multiple holder writes, but delayed same-holder operations need their own ordering/idempotency. A random release token is not a monotonic fence. etcd revisions and ZooKeeper recipes require proper transaction/session scope and nonreuse across restored/recreated namespaces; do not assume every counter is globally eternal.

7. Naive Locks and Redlock

A very common interview answer is "just use a single Redis key with SET key value NX PX ttl." That is a fine starting point and works for the happy path, but it has two well-known weaknesses. First, on a single Redis node the lock is only as durable as that node — if the primary fails over to a replica that had not yet received the lock write, two clients can hold the "lock" at once. Second, and more fundamentally, a single-key lock provides no fencing token, so it cannot survive the paused-holder scenario from the previous section.

The Redlock algorithm was proposed to address the durability gap by acquiring the lock on a majority of several independent Redis nodes, so the loss of any one node does not lose the lock. With five nodes, the client tries SET NX PX on each in turn with a short timeout. It holds the lock only if at least three said yes and the whole attempt took less than the TTL. Its remaining validity is the TTL minus the time spent, minus an allowance for clock drift. If it fails, it releases on every node. Redlock then became the subject of a famous debate. Critics argued that it still relies on bounded clock drift and bounded pauses for its safety guarantee, and that a lock used to protect a resource must be backed by fencing tokens regardless of how many nodes you spread it across — at which point the multi-node ceremony buys you little for correctness. The practical takeaway for an interview is not which side won, but the underlying lesson:

• A lock store gives you liveness and convenience, not safety on its own.
• Safety comes from fencing at the protected resource, not from the lock implementation.
• If you genuinely need correctness under failures, prefer a system designed for it (a consensus-based coordination service) over a lock bolted onto a cache.

8. Renewal and Heartbeats

A fixed TTL forces an awkward tradeoff: long-running work needs a long lease, but a long lease means slow recovery after a crash. The way out is lease renewal. The holder runs a background heartbeat that periodically extends the lease while it is still alive and making progress, so you can keep the TTL short (fast recovery) while still supporting work that runs much longer than one TTL.

The heartbeat is also how the system detects death. As long as renewals keep arriving, the holder is presumed alive and keeps the lock. The instant they stop — because the holder crashed, hung, or was partitioned — no further extensions occur, the lease runs out, and the lock is freed for someone else. This same heartbeat-or-expire pattern is exactly what leader election uses, which is why the two topics are so closely linked.

# background heartbeat keeps a short lease alive while we work
function heartbeat_loop(lock_key, owner_id, ttl):
  while still_working:
    sleep(ttl / 3)                      # renew well before expiry
    ok = store.extend(lock_key, owner_id, ttl)
    if not ok:                          # we lost the lock
      stop_work()                       # do not keep mutating
      break

Like release, extend must be an atomic compare-and-extend: only push the expiry out if the key still holds our owner id. In Redis, that is the same Lua pattern with PEXPIRE in place of DEL.

9. Leader Election

Use a reviewed coordination service recipe rather than treating standalone Redis SET-NX as consensus. A session/lease expires at its authority, but a paused holder may remain unaware. Raft terms are logical epochs, not fixed TTL intervals; timeouts suspect failure rather than prove death.

A new leader commits only through quorum/log rules. Protect downstream effects with installed monotonic fences and linearizable reads with current-authority/applied-state barriers. Lease loss should stop cooperative work as an extra defense, not the sole safety proof.

10. Split-Brain Avoidance

Raft elects at most one leader per term. An older-term partitioned leader can remain unaware while a newer-term leader exists. Safety comes from durable election/log rules: the old side cannot commit conflicting history without a quorum. Linearizable reads require current authority and applied state, not merely is_leader.

Quorums apply to the agreed membership configuration and protocol. Odd counts are common because 2f+1 tolerates f unavailable nodes; an even count is not inherently unsafe. Membership changes follow the coordinator's safe transition protocol. Fence external job/storage effects, which are not automatically covered by the consensus log.

11. Tradeoffs

How much machinery you need depends entirely on what the lock protects. An interviewer wants to see you match the mechanism to the cost of getting it wrong.

The pragmatic rule: if a brief double-acquire merely wastes work (two workers process the same job, idempotently), a simple lease lock is fine. If a double-acquire corrupts data or money, you need fencing tokens and, for leadership, a consensus-backed coordination service with majority quorum. Reach for the heavy machinery only when the cost of being wrong justifies it.

12. Failure Modes

Worked example: writer 33 returns after writer 34

A pauses beyond its lease; B receives a new grant.

Run a small, testable model

Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:

python3 concepts.py fencing
python3 concepts.py test

The model tests stale-token rejection and the boundary before a newly granted token reaches the resource.

The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.

13. A 45-Minute Interview Walkthrough

14. Common Mistakes

• Release by get-then-delete. It can delete another client's lock. Use an atomic compare-and-delete.
• Owner id = host name. Use a random id per acquire.
• Trusting the TTL for safety. Any pause can outlast any TTL. Fence.
• Believing heartbeats fix pauses. The heartbeat thread freezes too.
• Checking the fencing token and writing in two steps. The check and the write must be atomic.
• Using a lock where a conditional write would do. UPDATE … WHERE version = ? needs no lock service at all.

15. Summary

A distributed lock recreates mutual exclusion on top of a system with no shared memory, independent failures, and unsynchronized clocks. The design is a stack of mechanisms, each covering a gap the previous one leaves open:

16. Check Yourself

1. Why is if get(k) == me: delete(k) unsafe as a release?
   Answer

   The lease can expire between the get and the delete. Another client then takes the lock, and your delete removes their lock. The compare and the delete must be one atomic step, such as a Lua script in Redis.

2. Client 1 holds token 33 and freezes. Client 2 gets token 34 and writes. Client 1 wakes and writes. What must the storage do, and how?
   Answer

   Reject Client 1's write, because 33 is lower than the highest token seen (34). It must check and write atomically, for example UPDATE … WHERE fence <= :token.

3. A lock is held for 10 s on average and acquired 50K times per second. How many locks are held at once, and how many renewals per second if each lock renews every 10 s?
   Answer

   Little's law: 50K × 10 = 500K locks held. Each renews once every 10 s, so 500K ÷ 10 = 50K renewals/s.

4. Why does a cluster of 5 nodes tolerate 2 failures but a cluster of 4 tolerates only 1?
   Answer

   A majority of 5 is 3, so 2 can fail. A majority of 4 is also 3, so only 1 can fail. The fourth node adds cost but no fault tolerance, which is why clusters use odd sizes.

5. A worker renews its lease every 10 s with a 30 s TTL. Why can it still end up writing after it lost the lock?
   Answer

   A long GC pause or VM freeze stops the whole process, heartbeat thread included. If the pause lasts over 30 s, the lease expires and another worker takes over. The frozen worker wakes up and writes before it notices. Only a fencing check at the resource stops that write.

6. When is a plain single-Redis-key lock good enough?
   Answer

   When it is an efficiency lock: a rare double grant only wastes work, and the work is idempotent. Example: stopping two workers from rebuilding the same cache entry.

17. Key Terms

Mutual exclusion

At most one holder at a time.

Lease

Time-limited permission issued by an authority. Expiry lets new work proceed after a client stops renewing; it does not prove that the previous holder is dead or unable to act. Example and limits above.

TTL

Time to live: how long until the lease expires.

Fencing token

A strictly increasing grant number attached to operations. The protected resource atomically compares it with its durable highest accepted token and rejects older operations, making superseded clients unable to overwrite newer effects. Example and limits above.

Compare-and-delete

Delete a key only if it still holds the expected value, atomically.

Redlock

Acquire on a majority of independent Redis nodes.

Quorum

A set of replicas whose responses are sufficient for an operation. In a fixed set of N replicas, read size R and write size W overlap whenever R+W>N. A majority is one particular quorum, not the definition of every quorum. Example and limits above.

Split-brain

Two sides of a partition each believe they lead.

Ephemeral node

A ZooKeeper node deleted when its client session ends.

Efficiency vs correctness lock

Double grant wastes work vs corrupts data.

Liveness / safety

Something good eventually happens / nothing bad ever happens.

18. Further Reading

• M. Kleppmann, Designing Data-Intensive Applications, chapter 8 ("The Trouble with Distributed Systems"), sections on process pauses and fencing tokens.
• M. Kleppmann, "How to do distributed locking," blog post, February 2016.
• S. Sanfilippo (antirez), "Is Redlock safe?" blog reply, February 2016; and the Redis documentation page "Distributed Locks with Redis."
• M. Burrows, "The Chubby lock service for loosely-coupled distributed systems," OSDI 2006.
• P. Hunt et al., "ZooKeeper: Wait-free coordination for Internet-scale systems," USENIX ATC 2010; and the ZooKeeper "Recipes and Solutions" docs (locks, leader election).
• D. Ongaro, J. Ousterhout, "In Search of an Understandable Consensus Algorithm" (Raft), USENIX ATC 2014.