Distributed locking

A distributed lock lets processes on different machines agree that only one of them may work on a shared resource at a time. Every practical one is a lease that expires, so a crashed holder cannot block everyone forever, and that same expiry lets a paused holder wake up still believing it owns the lock. How much that matters depends on what the lock protects.

Picture it first: one parcel, two riders

A delivery dispatcher assigns order 881 to rider Asha with a pickup slip valid for 15 minutes; after that, the order goes to another rider, so a dead phone never leaves food going cold.

Asha is stuck at a closed level crossing for 25 minutes with no signal. At minute 15 the order passes to Ravi with a new slip, and he collects it. At minute 25 Asha arrives, slip in hand, sure the order is hers. Nothing told her the slip had lapsed: from where she stood, time simply jumped.

If the counter staff only check “do you have a slip for 881?”, they hand the order over twice. If they number the slips and remember the highest one used (“Ravi showed 34, yours is 33”), they turn her away. That check matters most when the slip decides who collects ₹600 cash on delivery.

Map it back: the dispatcher is the lock service, the slip a lease, 15 minutes its TTL, the level crossing a GC pause or network delay, the slip number a fencing token, and staff who check it storage that enforces the token. A wasted trip is an efficiency lock failing; lost cash is a correctness lock failing.

What the lock is for, and what it must promise

Efficiency or correctness

You use a distributed lock when several machines might do the same work and only one should. Martin Kleppmann’s 2016 essay, building on Google’s Chubby paper, sorts the reasons by what happens if the lock fails:

• Efficiency locks prevent duplicate work. A failure costs extra compute or a duplicate email: one of six replicas runs the nightly report, one worker rebuilds an expired cache entry.
• Correctness locks stop concurrent processes corrupting shared state. A failure loses an update, sells a seat twice or debits a wallet twice.

A cheap lock that occasionally fails is fine for efficiency. For correctness, no lock on its own is enough.

Three properties

The Redis documentation asks three things of a lock:

1. Mutual exclusion (safety): at most one holder at any moment.
2. Deadlock freedom (liveness): someone can eventually acquire it even if the holder crashes or is cut off, so it must expire: it is a lease with a time-to-live.
3. Fault tolerance (liveness): locking keeps working while some lock servers are down.

The first two pull against each other. Without a TTL, a crashed holder blocks everyone forever; with one, exclusion lasts only until the lock service decides time is up, and nothing stops the holder at that moment.

A lock on one Redis instance

The simplest lock is a single key:

SET lock:nightly-report 7f3c9a1e5b2d NX PX 30000

NX sets the key only if it does not exist, so exactly one caller gets OK. PX 30000 expires it after 30,000 ms, so a crashed holder frees it within 30 seconds. The value is a random token unique to this acquisition (the Redis docs suggest 20 bytes from /dev/urandom); it is what makes a safe release possible.

Releasing safely

Release must delete the key only if it still holds your token, atomically:

-- KEYS[1] = lock key, ARGV[1] = the token you set when acquiring
if redis.call("get", KEYS[1]) == ARGV[1] then
  return redis.call("del", KEYS[1])
else
  return 0
end

Redis runs a script atomically, so nothing slips between the GET and the DEL; Redis 8.4 adds DELEX key IFEQ token, which does the same. A plain DEL is not equivalent: if your work overran the TTL, the key may already belong to someone else.

Choosing the TTL, and renewing it

The TTL trades two failures. Too short, and a slow but healthy holder loses the lock mid-job; too long, and everyone waits after a crash. Size it from the job’s tail: if its p99.9 is 8 s, a 30 s TTL leaves 22 s of headroom and blocks others for at most 30 s after a crash.

For jobs of unknown length, libraries renew in the background. Redisson, a widely used Java client, runs a lock watchdog: take a lock without a lease time and it sets a 30 s expiry (the lockWatchdogTimeout default), then extends it every 10 s, a third of the timeout, while the client process lives. Each renewal must be conditional on the key still holding your token.

Renewal has limits:

• A pause stops the watchdog too. Stop-the-world GC freezes every thread, so a pause longer than 20–30 s (the lease minus up to 10 s since the last renewal) still loses the lock.
• A hung process keeps its lock. A job stuck in a loop is renewed forever, so cap the total hold time.
• Renewal fails during a partition, and the holder only notices at its next check.

Failover loses locks

A replica does not remove the single point of failure, because Redis replication is asynchronous. If the primary acknowledges your SET and crashes before copying it, the promoted replica can grant the same lock again; the Redis docs call this a safety violation. Redisson now waits after each acquire until the lock reaches the replicas (checkLockSyncedSlaves, on by default), which narrows the window but is not consensus. For an efficiency lock, that is acceptable.

The pause that breaks every lease

Now take a correctness case. A client takes a lock, reads a file from shared storage, changes it and writes it back. It looks safe, and it is broken whichever lock service you use.

The client did nothing wrong; it simply was not running while its lease expired. Kleppmann lists everyday causes:

• Garbage collection. Stop-the-world pauses are usually short but have lasted minutes; HBase once had exactly this bug.
• The machine. VM live migration, a page fault served from a network-attached disk, CPU starvation, a stray SIGSTOP.
• The network. A write sent before expiry can arrive after it; in a 2012 GitHub incident, packets were delayed for about 90 seconds.

Checking the lease just before writing does not help, because the pause can strike between the check and the write; renewal cannot help either. Every lease-based lock has this window; they differ in whether they give you the means to close it.

Fencing tokens

The fix is to make the resource reject the stale holder. Each grant comes with a fencing token, larger than any issued before. The holder sends it with every write; storage remembers the highest token accepted and refuses anything lower.

Equal tokens must pass, because the current holder usually writes several times; only a token lower than the highest seen is refused. The check and the write must be one atomic step at the storage, typically a conditional update:

UPDATE documents
SET    body = $1, fence = $2
WHERE  id = $3 AND fence <= $2;   -- 0 rows updated: a newer holder exists, so abort

Three requirements make fencing work:

1. Tokens must really be monotonic, so they come from a consensus-backed counter: ZooKeeper’s zxid (your lock node’s czxid), an etcd revision, a database sequence. A counter on one Redis node can go backwards after a failover.
2. Every write path must check the token. One unguarded path reopens the window.
3. The resource must be able to check. A database row can; an outgoing SMS or a third-party payment API cannot. There you need idempotency keys on the receiving side, or you accept the risk.

Chubby’s sequencers and lock-delay

Google’s Chubby lock service (Burrows, OSDI 2006) built this in as sequencers: an opaque string holding the lock’s name, mode and lock generation number, passed by the holder to the servers it calls. Each server checks it against its own Chubby cache, or the latest sequencer it has seen, and rejects stale ones.

For servers that cannot check, Chubby offers a cruder fallback, the lock-delay: if a holder vanishes instead of releasing, nobody can take the lock for a client-chosen period of up to one minute, so delayed requests can drain. Anything delayed longer still slips through.

Redlock and the 2016 debate

Redlock, designed by Redis’s creator Salvatore Sanfilippo (antirez), removes the single point of failure without replication: N independent Redis primaries, five in the docs’ example. To acquire:

1. Read the current time.
2. Send SET key value NX PX ttl, with the same random value, to all N in parallel, each with a short timeout (5–50 ms for a 10 s TTL).
3. Read the time again. You hold the lock only if a majority (3 of 5) said OK and less than the TTL has elapsed.
4. Your usable validity is the TTL minus the elapsed time minus a clock-drift allowance.
5. On failure, release on every node and retry after a random delay.

A node that restarts without the lock on disk lets a second client assemble a new majority, so the docs call for either an fsync on every write or delayed restarts: keep a crashed node out for longer than the largest TTL.

Kleppmann’s critique

In “How to do distributed locking” (February 2016), Martin Kleppmann argued Redlock is unsafe for correctness:

• No fencing token. Its random value is unique but not ordered, and a reliable counter across five independent nodes would itself likely need consensus.
• Safety rests on timing. A clock jump: client 1 locks A, B and C; C’s clock jumps forward and expires the key; client 2 locks C, D and E, so both hold a majority. A pause: client 1 freezes while its “OK” replies sit in its network buffers, the keys expire, client 2 locks all five, and client 1 wakes to read its replies. Redlock is correct only if delays, pauses and clock error are bounded and small next to the TTL.

His verdict: “neither fish nor fowl”, too heavy for efficiency and not safe enough for correctness, where he recommends ZooKeeper or a transactional database, plus fencing.

antirez’s reply

A day later, antirez answered in “Is Redlock safe?”:

• The pause after acquiring affects every auto-releasing lock, not just Redlock. And storage that can reject old tokens is already strongly consistent; Redlock’s random value can drive a check-and-set on it instead.
• Only the clock rate must be bounded: each process must count 10 seconds as, say, 9.5 to 11.2. Operators shouldn’t step clocks, NTP should slew, and Redis should use a monotonic clock, which he conceded.
• Delays during acquisition are already caught, because step 3 rereads the clock.

A practical verdict

Both are partly right. The second clock read does catch a pause during acquisition, and a pause after it hits every lease. But clock jumps and unsafe restarts grant overlapping leases with no pause at all, and without an ordered token nothing downstream can notice. The Redis docs now tell readers who need correctness to implement fencing tokens, and warn that key expiry still uses the wall clock. Redisson has deprecated its RedLock object.

The working rule: one Redis for efficiency; a consensus store plus fencing for correctness. Redlock rarely earns its five servers.

ZooKeeper and etcd locks

Both stores run consensus (ZAB and Raft) and tie a lock to a client session or lease that ends when the client stops heartbeating, so a crashed holder is released automatically. The machinery mirrors leader election, covered in consensus and leader election; here is what is lock-specific.

ZooKeeper. Each client creates an ephemeral sequential node such as /locks/invoice-42/guid-lock-0000000117. The lowest number holds the lock; everyone else watches only the node just below their own, so a release wakes exactly one waiter (no herd effect) and waiters are served in order. Release by deleting your node or letting your session expire. The guid lets a client find its node if create succeeded but the reply was lost. Fence with the lock node’s czxid, the ID of the transaction that created it.

etcd. Grant a lease and keep it alive, then call Lock (or the Go client’s concurrency.Mutex). It writes a key bound to your lease and waits until every key with a lower creation revision is gone. The key exists only while you hold the lock, and its creation revision, from a cluster-wide counter that only increases, is your fencing token. For writes to etcd itself, add the mutex’s IsOwner() check to the transaction.

You gain locks that survive server failures, fair queues and free fencing tokens. You pay for a three- or five-node cluster and a consensus write (a majority round trip plus an fsync) per acquire and release.

Locks inside your database

A database you already run can be your lock service, with one clock and real transactions.

PostgreSQL advisory locks. pg_try_advisory_lock(42) takes an exclusive lock on an application-chosen 64-bit number, returning false instead of waiting. Session-level locks last until you unlock or the connection closes, and ignore rollback; transaction-level ones (pg_advisory_xact_lock) release at commit or rollback. There is no TTL: the lease is your connection, so a paused client with an open connection keeps the lock. Two traps: PgBouncer’s transaction pooling never supports session-level advisory locks, and all locks share one memory pool, typically good for tens to hundreds of thousands.

SELECT … FOR UPDATE. Locks the selected rows until the transaction ends. When the lock protects exactly those rows, lock and data live and die together, so there is nothing to fence.

A lease table. For long jobs, keep one row per lock with an owner, an expiry and a counter:

UPDATE leases
SET    owner = 'worker-7', token = token + 1,
       expires_at = now() + interval '30 seconds'
WHERE  name = 'nightly-report' AND expires_at < now()
RETURNING token;   -- a row back means you hold it, and token is your fencing token

Expiry is judged by the database’s own clock, so client clock skew does not matter, and the counter fences writes to that same database.

DynamoDB conditional writes. A lock is an item written only if a condition holds, such as attribute_not_exists(lock_id). Taking over an expired lock is the hard part, because comparing machines’ clocks invites skew. The DynamoDB Lock Client never compares them: the holder heartbeats by writing a new random version number, and a waiter that sees the same version after a full lease of its own elapsed time (10 s leases, 3 s heartbeats in AWS’s example) takes over with a conditional update on that version.

Avoiding the lock altogether

The most reliable distributed lock is often the one you did not need:

• Compare-and-set with versions. Read a row with its version, write … WHERE id = ? AND version = ?, and retry if no row changed. See optimistic vs pessimistic locking and the lost update problem.
• One writer per key. Partition work so each key has one owner, such as a Kafka partition read by one consumer-group member. Handing ownership over still needs a fence (an epoch number).
• Idempotency. If running twice is harmless, your correctness lock becomes an efficiency lock. Record a dedupe key in the same transaction as the effect; see the inbox pattern.
• A queue. Give each job to one consumer through a message queue; handlers stay idempotent because delivery is at-least-once.
• Constraints. A unique index stops a second “first” row more reliably than a lock around the insert.

Going deeper: granularity, contention and hot locks

Granularity. One global lock is simple but serialises everything; one lock per resource (per order, per seat) lets unrelated work run in parallel. Chubby was built for coarse-grained locks held for hours or days, such as electing a primary, and leaves fine-grained locking to application-level lock servers.

The throughput ceiling. One lock key handles at most 1 ÷ hold time operations. Hold it for 20 ms and the key manages 1,000 ÷ 20 = 50 operations per second, however many servers you add. If 10,000 shoppers a second hit one product in a sale, a per-product lock is 10,000 ÷ 50 = 200× over capacity. Use one atomic statement instead (UPDATE stock SET qty = qty - 1 WHERE sku = ? AND qty > 0) or split stock into buckets; see contention and double booking and design a flash sale.

Waiting and fairness. SET NX has no queue: losers poll, so add backoff with jitter and accept that a client can starve. ZooKeeper and etcd queue waiters in order.

Deadlock. Take multiple locks in one global order, say sorted by key. TTLs break deadlocks eventually, but only after a full lease of stalled work.

Choosing a lock

Four cases that come up again and again:

Deduplicating a nightly cron across six replicas → a single Redis lock. At 02:00 every replica runs SET cron:nightly-report:2026-10-27 <token> NX PX 3600000. One wins; the key names the date, so it never needs releasing and expires after an hour. If a failover lets two replicas run, the report overwrites a file named by date, so the duplicate is harmless.

Tatkal-style seat or inventory assignment → the database, not a lock service. Let the row decide: UPDATE seats SET status = 'HELD', held_by = $1, hold_until = now() + interval '10 minutes' WHERE train_id = $2 AND seat_no = $3 AND status = 'FREE'. One row updated means you got it; zero means someone else did. A Redis lock around it adds a hop and a failure mode, and you still need the condition.

A leader-only job writing to external storage → an etcd or ZooKeeper lease with fencing. A compaction job takes an etcd lock and reads its key’s creation revision, say 9,041. It writes output under fresh file names, then commits with a conditional update on a manifest row that stores the highest revision seen. A paused ex-leader holding 9,017 has its commit rejected.

A UPI-style wallet debit → no distributed lock. In one transaction, run UPDATE wallets SET balance = balance - 500 WHERE user_id = $1 AND balance >= 500 and insert a ledger entry keyed by the payment’s idempotency key. The row lock serialises concurrent debits; the unique key turns a retry into a no-op. See design a digital wallet.

Cheat sheet

How to say it in the interview

“First, what is the lock for? If it only stops duplicate work, like one replica running the nightly job, I’d use one Redis key: SET with NX and a 30-second PX, a random token as the value, and a compare-and-delete release. If it fails now and then, we do the work twice. For correctness I don’t trust any lock alone: every lock is a lease, and a holder paused past its TTL wakes up and still writes. So I’d take the lease from etcd, use the key’s creation revision as a fencing token, and have storage reject lower tokens. And if the data sits in one database, I skip the lock service and use a conditional update there.”

Why not check that you still hold the lock right before writing? The pause can happen between the check and the write. Only the resource, checking at write time, sees the true order.

Redis has replicas. Isn’t that enough? Replication is asynchronous, so a primary can acknowledge a lock, crash before copying it, and let the promoted replica grant it again. Waiting for replicas narrows the window but is not consensus.

Where does the fencing token come from? From something that cannot go backwards: ZooKeeper’s czxid, etcd’s revision, a database sequence. A counter on one Redis node can repeat after failover, and Redlock’s random value is not ordered.

What if the downstream can’t check tokens, like a third-party payment API? Then no lock makes it safe. Send an idempotency key so the provider drops duplicates, or route every call through one writer that can check.

Is Redlock safe? It survives single node failures and catches delays during acquisition, but clock jumps or a node restarting without its locks can grant overlapping leases, and it has no ordered token.

Where to go next

• Consensus and leader election: Raft, quorums, and elections on etcd and ZooKeeper.
• ZooKeeper and etcd: sessions, leases and watches.
• Redis: persistence and replication behind the single-node lock.
• Optimistic vs pessimistic locking: versions and row locks, often the better tool.
• Contention and double booking: many buyers, one seat.
• Heartbeats: keeping leases alive, and why GC pauses fool detectors.
• Clocks, ordering and conflict resolution: why wall clocks jump.
• Design a distributed lock: the same ideas as a design problem.

References and further reading

1. How to do distributed locking (Kleppmann, 2016)martin.kleppmann.comEfficiency versus correctness locks, the GC-pause failure, fencing tokens 33 and 34, ZooKeeper zxid as a token, and the timing critique of Redlock.
2. Is Redlock safe? (Sanfilippo, 2016)antirez.comThe reply: auto-release is unavoidable, random tokens for check-and-set, bounded clock-rate error, and the post-acquisition time check.
3. Distributed Locks with Redis (Redis documentation)redis.ioThe three lock properties, SET NX PX 30000, the compare-and-delete script and DELEX, the failover race, the Redlock steps and validity formula, and the fencing disclaimer.
4. The Chubby lock service for loosely-coupled distributed systems (Burrows, OSDI 2006)static.googleusercontent.comAdvisory coarse-grained locks, sequencers with a lock generation number, and the lock-delay of up to one minute.
5. ZooKeeper Recipes and Solutions: Lockszookeeper.apache.orgEphemeral sequential lock nodes, watching the next-lowest node to avoid the herd effect, and the GUID for recoverable create errors.
6. etcd API reference: concurrency (Lock service)etcd.ioLock returns a key that exists while the lock is held, is tied to a lease, and can guard transactions.
7. PostgreSQL documentation: Explicit Lockingpostgresql.orgSession-level and transaction-level advisory locks, the shared lock-memory limit, and SELECT … FOR UPDATE row locks.
8. PgBouncer features: SQL feature map for pooling modespgbouncer.orgSession-level advisory locks never work under transaction pooling.
9. Redisson documentation: Locks and synchronizersredisson.proThe 30 s lock watchdog default, replica-sync checks on acquire, RFencedLock tokens, and the deprecation of its RedLock object.
10. Building Distributed Locks with the DynamoDB Lock Client (AWS Database Blog)aws.amazon.comA lock item written with conditional writes, record version numbers and heartbeats, and takeover after a locally timed lease duration.