Distributed locks and their limits — Redis and Caching

Several instances of a service want to make sure only one of them sends invoice 1041. A lock in Java only coordinates threads in one process, so the natural reach is for a lock in Redis: a key that one instance sets and the others find already taken.

It works most of the time, and the way it fails is instructive — because the failure is not a bug in Redis. It is a property of any lock that expires, and it means a Redis lock can reduce duplicate work but cannot, on its own, guarantee that only one process acts.

Every timeline below was recorded against Redis 7.4 with three Java workers in another container.

The lock with an expiry

Acquiring is one atomic command: set the key only if it does not exist, with an expiry so that a crashed holder does not hold it forever:

plaintext

SET lock:invoice-1041 <owner> NX PX 1000

NX makes it succeed for exactly one caller; PX 1000 makes it disappear after a second. The expiry is not optional — without it, an instance that crashes while holding the lock blocks everyone until someone deletes the key by hand. And the expiry is the source of every problem that follows.

Losing the lock without knowing

Worker A acquires the lock and starts work. The work — or a garbage-collection pause, a slow disk, a network hiccup — takes 1.5 seconds, longer than the lock's one-second expiry. The lock expires while A is still inside its "critical section". Worker B acquires it. Worker C arrives later. Each worker writes the invoice and then releases the lock with a plain DEL:

plaintext

     19 ms  worker-A  acquired the lock (1 s expiry)
   1122 ms  worker-B  acquired the lock (1 s expiry)
   1530 ms  worker-A  wrote the invoice
   1531 ms  worker-A  released the lock
   1624 ms  worker-C  acquired the lock (1 s expiry)
   1729 ms  worker-B  wrote the invoice
   1731 ms  worker-B  released the lock
   1927 ms  worker-C  wrote the invoice
   1929 ms  worker-C  tried to release: it was no longer ours, nothing deleted
  final invoice:1041 = sent by worker-C

Read it carefully, because there are two separate failures:

Two holders. From 1,122 ms, A and B both believe they hold the lock. A never learned it had expired — nothing tells a process that its lock is gone.
Deleting someone else's lock. At 1,531 ms, A's DEL removed B's lock. C acquired it at 1,624 ms while B was still working, and B's later DEL removed C's. Three workers wrote the invoice.

The second failure has a simple fix: store a unique value when acquiring, and release only if the value is still yours — atomically, in a Lua script, since a GET followed by a DEL is itself a race:

plaintext

if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('DEL', KEYS[1])
else
  return 0
end

With that release, the same timings:

plaintext

     22 ms  worker-A  acquired the lock (1 s expiry)
   1132 ms  worker-B  acquired the lock (1 s expiry)
   1534 ms  worker-A  wrote the invoice
   1540 ms  worker-A  tried to release: it was no longer ours, nothing deleted
   1734 ms  worker-B  wrote the invoice
   1736 ms  worker-B  released the lock
   1780 ms  worker-C  acquired the lock (1 s expiry)
   2081 ms  worker-C  wrote the invoice
   2082 ms  worker-C  released the lock

A no longer deletes B's lock, and C correctly waits until B has finished. But A still wrote the invoice at 1,534 ms, while B held the lock. The first failure — a holder that does not know its lock expired — is untouched, because nothing in the lock can reach into a paused process.

The stale write

That first failure does damage in a specific way. Worker A acquires the lock and pauses; B acquires it after the expiry, does its work quickly, writes, and releases; then A wakes up and writes what it computed before the pause:

plaintext

     29 ms  worker-A  acquired the lock (1 s expiry)
   1141 ms  worker-B  acquired the lock (1 s expiry)
   1347 ms  worker-B  wrote the invoice
   1349 ms  worker-B  released the lock
   1540 ms  worker-A  wrote the invoice
   1542 ms  worker-A  tried to release: it was no longer ours, nothing deleted
  final invoice:1041 = sent by worker-A

The final state is A's stale result, overwriting B's newer one, and every worker followed the locking protocol correctly. A longer expiry makes this rarer, not impossible: pauses have no upper bound. Stop-the-world GC, a VM migrated between hosts, a process suspended by the operating system, a network partition that delays a request for seconds — any of them outlasts any expiry you are willing to set.

Fencing tokens

The fix, described by Martin Kleppmann, moves the check to the only place that can enforce it: the resource being written. Each time the lock is granted, the holder also gets a fencing token — a number that only ever increases, here from INCR lock:tokens. Every write to the resource carries the token, and the resource refuses any token lower than the highest it has already accepted:

plaintext

local last = tonumber(redis.call('GET', KEYS[2]) or '0')
if tonumber(ARGV[1]) < last then return 0 end
redis.call('SET', KEYS[2], ARGV[1])
redis.call('SET', KEYS[1], ARGV[2])
return 1

The same stale-write timing, with tokens:

plaintext

     41 ms  worker-A  acquired the lock (1 s expiry), token 1
   1153 ms  worker-B  acquired the lock (1 s expiry), token 2
   1360 ms  worker-B  wrote the invoice
   1362 ms  worker-B  released the lock
   1562 ms  worker-A  write REFUSED: token 1 is older than one already used
   1563 ms  worker-A  tried to release: it was no longer ours, nothing deleted
  final invoice:1041 = sent by worker-B

A woke up, tried to write with token 1, and was refused — the resource had already accepted token 2. The final state is B's.

Two limits on what fencing does:

It orders writes; it does not prevent overlap. In a first run with tokens, using the three-worker timings from earlier (not shown above), A — holding token 1 — still wrote at a moment when B held token 2, because B had not written yet, so the resource had not seen token 2. What fencing guarantees is that an older holder can never overwrite a newer holder's write.
The resource has to cooperate. A database can check the token in a WHERE clause; a Redis key can check it in a script; an email provider or a payment gateway cannot check anything. For those, fencing is unavailable, and the protection has to come from idempotency — the same key sent twice has one effect.

Redlock and its critics

A single Redis instance is a single point of failure: if it fails over to a replica that had not yet received the lock key, a second client can acquire the lock. Redlock, proposed by Redis's creator, acquires the lock on a majority of independent Redis nodes to survive that.

Martin Kleppmann's critique, How to do distributed locking, argued that Redlock depends on bounded pauses, bounded network delay and clocks that do not jump — exactly the assumptions the timelines above break — and that it provides no fencing token. Salvatore Sanfilippo published a response defending its assumptions for practical systems. The debate is worth reading in full; the practical conclusion most engineers draw from it is:

For efficiency — avoiding duplicate work that is harmless if it occasionally happens twice, such as rebuilding a cache entry — a single-instance Redis lock is fine.
For correctness — where two holders would corrupt data or double-charge a customer — a lock that expires is not enough on its own, whatever its algorithm. Use a coordination service that provides fencing tokens (ZooKeeper, etcd), or better, design the write so that the lock is not what guarantees correctness.

The design that does not need the lock

Most "we need a distributed lock" problems are really "we need this change to happen once", and a database can guarantee that directly:

A conditional update: UPDATE invoices SET status = 'SENT', sent_by = ? WHERE id = 1041 AND status = 'PENDING'. Exactly one instance gets 1 row affected; the others get zero and stop. No lock, no expiry, no pause problem.
A unique constraint on the thing that must happen once — an invoice_sent row keyed by invoice id. The second insert fails.
An idempotency key passed to the external system, so a duplicate call has no second effect.
Partitioning the work so that each item has one owner — a Kafka partition consumed by one member of a group, or a job claimed by a conditional update — and no two instances ever compete for it.

A Redis lock is then what it is good at: a cheap way to make duplicate work rare. The guarantee lives in the data.

Key takeaways

SET key value NX PX acquires a lock atomically with an expiry; the expiry is necessary and is where every problem comes from.
A 1.5 s pause outlived a 1 s lock: two workers held it at once, and a plain DEL removed another worker's lock, letting a third in.
Releasing only your own lock (a Lua compare-and-delete) fixes the second problem, not the first. A paused holder still wrote while another held the lock — and its stale write became the final state.
Fencing tokens let the resource refuse older holders: token 1's late write was refused after token 2's. They order writes; they do not prevent overlap, and the resource must check them.
Use a Redis lock for efficiency. For correctness, make the write itself safe: a conditional update, a unique constraint, or an idempotency key.

#The lock with an expiry

#Losing the lock without knowing

#The stale write

#Fencing tokens

#Redlock and its critics

#The design that does not need the lock

The lock with an expiry

Losing the lock without knowing

The stale write

Fencing tokens

Redlock and its critics

The design that does not need the lock