Distributed Locking

In a single application, we use locks (like mutexes) to stop two threads touching the same resource at once, avoiding the race conditions that appear when both read a value before either writes back. But what if the "threads" are different servers, reaching for one shared resource — a file in a storage system, or an action only one process may perform at a time? An in-memory lock is local to one process on one machine, so it does nothing here.

What a distributed lock is

A distributed lock enforces mutual exclusion for a shared resource among processes on different machines: at any given moment, only one process across the whole system holds the lock and runs the critical section. "At any given moment" is a claim about a global clock nobody has, so every implementation below only approximates it — with messages, timeouts and version numbers, and each one differently.

Why this is harder than a mutex

• Network partitions: a client acquires the lock, is cut off from the lock service, and the service decides it died and gives the lock away. Two clients hold a lock meant to be exclusive, and neither is misbehaving.
• Lock service failure: the service loses lock state or goes unavailable, and every writer either blocks or proceeds unprotected.
• Clock skew: machines disagree about what time it is — assume tens of milliseconds between NTP-synced nodes in one datacenter, and far worse under a degraded NTP, a stalled VM or a clock stepped backwards — so "expires at 12:00:30" names a different instant on each node.
• Process pauses: a stop-the-world garbage collection pause freezes a holder for seconds — not dead, not reachable, and awake later still believing it holds the lock.
• Deadlocks: the same cycles as local deadlocks, harder to detect across machines where a waiting party may be slow rather than stuck.

Common implementations

1. Using a database

Create a locks table with a unique constraint on a resource_name column. To acquire, INSERT a row: the constraint lets only the first client succeed, and the violation everyone else gets is the "already taken" signal. To release, DELETE it.

Pros: free if the database is already there, and the guarantee comes from the same transaction machinery as the rest of your writes. (ACID's C, "the transaction preserves invariants", is unrelated to CAP's C, "every read sees the latest write".) Cons: every acquire and release is a write on the leader, so the database is a bottleneck and a single point of failure, and a crashed holder leaves its row behind forever unless you add an expiry column and a sweeper — a lease, built by hand.

2. Using a coordination service (ZooKeeper, etcd)

The usual recommendation when the lock protects something that matters. A client creates an ephemeral znode at a known path, say /locks/my_resource; ZooKeeper's consensus protocol lets only one client create it, and that client holds the lock until it deletes the node. Others watch the path instead of polling. If the holder crashes, its session times out and ZooKeeper deletes the znode itself — the "ephemeral" part is what earns the operational cost.

Pros: lock state is replicated by consensus (Raft, or ZAB in ZooKeeper's case), so it survives node loss and client death with no operator involved. Cons: another distributed system to run, and every acquire pays a quorum round trip. When a partition occurs, a quorum system chooses consistency over availability: the minority side stops granting locks rather than risk a second holder. PACELC covers the rest of the time — with no partition it still pays that round trip rather than answer from the nearest replica, spending latency to buy consistency.

3. Using a distributed cache (Redis)

One atomic command: SET resource_name random_value NX PX 30000. NX sets the key only if it does not exist, which makes acquisition atomic. PX 30000 expires it after 30 seconds — a lease, so the lock releases itself if the client dies. random_value is known only to this client, and release must compare it before deleting, or a client whose lease already expired deletes a lock somebody else now holds.

Pros: fast, one round trip, no quorum. Cons: less safe — in a leader-follower setup a lock granted by the leader is lost if the leader fails before replicating it, and the promoted follower hands the same lock to a second client. Redlock attacks this with several independent nodes, but it is contested and not trivial to implement correctly.

The lease, and why the lease is not enough

Every practical lock is a lease — ZooKeeper's session-bound ephemeral node, Redis's PX 30000 — so a holder that dies cannot block the resource forever. It solves the crashed-holder problem and quietly creates a second one.

A Redis lease: acquire with an expiry, mint an ordered token, and fence the stale writer100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Worker A takes the lease and starts work. A garbage collection pause freezes it for 35 seconds, Redis expires the key on schedule, and worker B acquires the lock and writes. A resumes — a pause is invisible from inside the process — and writes too. Two writers in one critical section, no bug in either client, no failure in Redis.

No lease duration fixes this: the bound you would need is the longest pause the runtime can ever take, which nobody has. The fix lives at the resource. The lock service issues a monotonically increasing fencing token with each grant, the client sends it with every write, and storage rejects any token below the highest it has accepted — A arrives with 33 after B wrote 34, so the write is refused. ZooKeeper's zxid and etcd's revision are already ordered by the consensus that granted them, so they serve as tokens directly; a Redis random value does not, being unique but not ordered. A Redis lease has to mint the token separately — an INCR on a counter key beside the lock, whose reply carries the ordering the SET NX reply never did — and that counter is then one more thing whose failover has to not lose count. Fencing needs cooperation from the resource, which is why the sturdier answer is usually idempotency: it demotes the lock from a correctness requirement to an optimisation against duplicate work.

What a lock costs

A lock serialises everything touching its key, so throughput per key is the reciprocal of hold time: 10 ms held allows 1 ÷ 0.010 = 100 operations per second, and adding servers does not move that number. Coordination is not free either — acquire is a leader round trip plus quorum replication, two datacenter hops at 0.5 ms, and release costs the same again: 20% overhead on a 10 ms critical section, ten times the work protected on a 200 µs one.

So the keyspace decides the design. Per-user or per-order contention spreads wide, every key sees a fraction of a QPS, and locking is cheap. When everything contends on one key — a global counter, one inventory row — 100 ops/s caps the feature, and the fix is splitting the key or using an atomic operation the store already has (INCR, a conditional update on a version column).

In an interview

What is being tested is whether you recognise cross-process mutual exclusion as the requirement, pick the cheapest mechanism that meets it, and know what that mechanism still does not give you.

Name the requirement before the tool: "these servers contend on one resource, so I need mutual exclusion across processes — a mutex is local." Then choose out loud, defaulting to a coordination service: "etcd or ZooKeeper, because lock state is replicated by consensus and an ephemeral node releases the lock when the holder's session dies." Price the alternatives in a line each, never offer to build one from scratch, and treat Redlock as contested rather than default.

Then say what the lock does not cover. The mistake that loses points is presenting a lease as a safety guarantee — "SET key value NX PX 30000, so only one client is ever in the critical section." It is not, and an interviewer who has debugged this will push. One sentence recovers it: "the lease bounds how long a crash blocks the resource, but it cannot prevent two holders — a paused holder never learns it expired — so the write path needs a fencing token, or the operation has to be idempotent."

Check yourself

1. One million payment captures a day, each holding a per-account lock for 40 ms, and one merchant is 30% of the traffic. Does per-account locking hold?

1M/day ÷ 86,400 s ≈ 12 QPS average, ~36 at 3x peak. One key does 1 ÷ 0.040 = 25 operations per second, and the hot merchant wants 0.30 × 36 ≈ 11 of them — 44% utilisation of something whose concurrency is pinned at 1, so p99 queues while the mean still looks fine. It holds now and fails before traffic doubles: shrink the critical section or split the key, because a faster lock service does not move the 25.

2. The lease is 30 seconds, the critical section takes 200 ms, and one key sees 3 QPS. What does raising the lease to 5 minutes buy, and what does it cost?

Check the key first: 1 ÷ 0.200 = 5 operations per second is the ceiling, so 3 QPS is 60% utilisation and 2 ops/s of slack — it holds, and Little's Law agrees that 3 × 0.2 = 0.6 concurrent operations fits under the one the lock allows. The longer lease buys tolerance of long pauses: it stops expiring under a holder that is frozen rather than dead, which is the double-write above. It costs recovery. A crash now blocks the key for the full 300 seconds, queueing 3 × 300 = 900 operations, and the queue drains only at the slack — 900 ÷ 2 = 450 seconds more — so one crash is 750 seconds of degraded service against 75 at a 30-second lease, ten times worse for the same arrival rate. Neither end of the dial is safe alone — with fencing tokens an early expiry is a rejected write rather than corruption — so tune the lease for recovery time and let the token carry safety.

3. A nightly reconciliation job runs on three replicas and must not run twice. The job is idempotent. etcd, or a row in the database you already operate?

The row. A double run wastes CPU rather than producing a wrong answer, so the lock is an optimisation, and the cheapest sufficient one beats a consensus cluster you would have to operate. Change one input and it flips: if the job moved money, "idempotent" stops being true at the boundary, and you need a fencing token or a deduplication key downstream — not a better lock.