Distributed Locks with a Key-Value Store: The Safe Pattern and Where It Breaks

Two workers wake up on the same cron tick, both decide the nightly export has not run yet, and both run it. Or two requests both try to deduct the last unit of inventory. The usual reach is for a distributed lock, and a key-value store is the natural place to put one. The acquire is one atomic write, the lock is one key, and the release is a delete. That much is easy. The part that bites is everything after the happy path: releasing safely, handling a holder that stalls past the expiry, and being honest about whether the lock is protecting an optimization or protecting correctness. Those are different problems, and the second one a single lock cannot fully solve.

The lock as a single key

A lock is a key whose existence means "someone holds this." Acquiring it is a conditional write that only succeeds if the key is absent. Holding it is the key continuing to exist. Releasing it is deleting the key. Because the access pattern is a point write keyed by the resource name, with a create-only condition, it is a textbook key-value workload. No ranges, no joins, no indexes.

The whole correctness of the acquire rests on one property: the check for absence and the write must be a single atomic operation. If your code reads the key, sees it missing, and then writes, two contenders both read "missing" and both write, and both believe they hold the lock. Same shape as the idempotency claim race, same fix.

Acquiring the lock

In Redis the acquire is one command:

SET lock:export my_random_value NX PX 30000

NX sets the key only if it does not already exist, so exactly one contender wins. PX 30000 attaches a 30-second expiry in the same operation. The reply is OK if you took the lock and nil if someone already holds it. The two decisions, take-if-free and set-the-timeout, happen together with no window between them.

Two details in that command are not optional.

The expiry is mandatory, not a nicety. If the holder crashes, is killed, or loses the network before it can release, the key has to disappear on its own or the resource is locked forever. The TTL is the dead-man's switch. Set it longer than the worst-case duration of the work you expect to do under the lock, with margin.

The my_random_value is a unique token per acquisition, not a constant. It is what makes the release safe, which is the next problem.

Releasing the lock without stealing someone else's

The naive release is "delete the key." It has a race that is easy to miss. Picture this sequence:

1. Worker A acquires the lock with a 30-second TTL.
2. Worker A's task runs long. At 30 seconds the key expires and the lock is now free.
3. Worker B acquires the lock. The key now belongs to B.
4. Worker A finishes, runs DEL lock:export, and deletes B's lock.

A just released a lock it no longer owned, and now a third worker can acquire it while B is still working. A plain DEL cannot tell whose lock it is deleting.

The fix is to sign each acquisition with the random token and only delete if the token still matches. The compare and the delete must themselves be atomic, because if you GET the value in your code, compare it, and then DEL, the key can expire and be re-acquired in the gap between your read and your delete, and you are back to deleting someone else's lock. The Redis docs give a Lua script that runs the compare-and-delete server-side as one unit:

if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

You pass the lock key as KEYS[1] and your random token as ARGV[1]. The delete only fires if the stored token is still yours. Redis 8.4 added a DELEX key IFEQ my_random_value command that does the same conditional delete without a script. Either way, the rule is identical: release is a compare-and-delete, not a delete, and it must be one atomic operation.

The general principle is that any store you use for this needs a create-only write for the acquire and an atomic compare-and-delete for the release. If your store cannot do the conditional release atomically, you can only build a lock that is safe to take, not safe to release, which is a half a lock.

Efficiency locks versus correctness locks

Before extending the pattern, decide which job the lock is doing, because the answer changes how much you should trust it. The distinction comes from Martin Kleppmann's analysis of Redis locking and it is the single most useful idea in this whole topic.

An efficiency lock saves you from doing the same work twice. Two workers both want to regenerate a cache or send the same digest email. If the lock occasionally fails and both run, you waste some compute or send a duplicate, and that is the entire cost. For this, a single-instance SET NX PX lock is completely fine. You do not need anything fancier.

A correctness lock prevents two holders from corrupting shared state, like two processes both writing to the same file or both decrementing the same balance. Here a double acquisition is a real bug, and this is where a lock alone, KV-backed or otherwise, runs into a hard limit.

Why the TTL can betray a correctness lock

The expiry that protects you from a crashed holder also creates a failure mode. Consider:

1. Worker A acquires the lock with a 30-second TTL and starts the critical section.
2. Worker A hits a long stop-the-world garbage-collection pause, or its host freezes, or a network partition delays it. It is paused, not crashed, and it does not know any time has passed.
3. The 30 seconds elapse. The key expires. The lock is free.
4. Worker B acquires the lock and enters the critical section.
5. Worker A's pause ends. It still believes it holds the lock and proceeds to write.

Now A and B are both in the critical section. The lock did exactly what you told it to and you still got a violation, because the holder was suspended for longer than the TTL without realizing it. No tuning of the timeout removes this. A pause can always exceed any fixed expiry. Kleppmann's writeup walks through this with the GC-pause example, and it applies to any lease-based lock, not just Redis.

Fencing tokens close the gap

The fix is not in the lock; it is at the resource the lock protects. The lock service hands out a number that strictly increases on every acquisition, a fencing token. Worker A gets token 33. After its pause, worker B acquires and gets token 34. Every write to the protected resource carries the holder's token, and the resource rejects any write whose token is lower than the highest it has already accepted. When A's stale write arrives stamped 33, the resource has already seen 34 and refuses it.

This works regardless of pauses, clock skew, or network delay, because it never trusts the lock to still be valid at write time. It trusts a monotonic number. The catch is that the protected resource has to participate by checking and remembering the token. If it cannot, fencing is not available to you, and you should treat the lock as an efficiency optimization rather than a correctness guarantee, and design so that a rare double-execution is survivable. With a KV store you can mint a monotonic token cheaply with an atomic increment on a counter key (INCR) at acquire time, but the enforcement still has to live at the resource.

Single instance, replicas, and Redlock

A lock on one Redis node is a single point of failure. The obvious fix, a replica for failover, quietly breaks the lock. Replication is asynchronous, so this can happen:

1. Client A acquires the lock on the master.
2. The master crashes before the write replicates.
3. The replica is promoted to master, with no record of A's lock.
4. Client B acquires the same lock on the new master.

Both hold it. The Redis docs call this out as a safety violation, and it is inherent to async replication rather than a bug you can configure away.

Redlock is the multi-node answer: run N independent masters, typically five, and acquire the same key with the same random token on all of them, accepting the lock only if a majority grant it within the validity window. Losing one or two nodes no longer loses the lock. Redlock is more robust against node failure than a single instance, but it is also contested. Kleppmann argues it still leans on timing assumptions, bounded clock error and bounded pauses, and that it does not produce fencing tokens, so it does not by itself give you the correctness guarantee that fencing does. Antirez's rebuttal is worth reading alongside it. The honest summary is that for correctness-critical locking, the multi-node setup raises availability but the fencing token is what actually makes the writes safe.

A practical decision tree

For most application-level needs you do not need Redlock. The decision goes like this.

If the lock is an efficiency optimization, use a single-instance SET NX PX with a generous TTL and the compare-and-delete release. Accept that a rare double-run can happen and make the work tolerate it. This covers the large majority of "don't run this twice at once" needs.

If the lock protects correctness, the lock alone is not enough at any level of Redis topology. Add fencing tokens enforced at the resource, or design the protected operation to be idempotent so a second entry is harmless, which sidesteps the whole problem. Reach for multi-node Redlock only when you also need the lock service itself to survive node failures, and even then keep the fencing.

In all cases: always set a TTL, always release with an atomic compare against your token, and never assume the lock is still valid by the time your code gets around to using it.

The takeaway

A distributed lock on a KV store is one create-only key for the acquire and one atomic compare-and-delete for the release, both of which a key-value store does well. The traps are not in those two operations. They are in the release that deletes the wrong owner's lock, in the TTL that expires under a stalled holder, and in the assumption that a lock that protects an optimization can be reused to protect correctness. Sign every lock with a random token, release with compare-and-delete, decide up front whether you need efficiency or correctness, and reach for fencing tokens, not a bigger Redis cluster, when correctness is on the line.

---

Related: Idempotency Keys with a Key-Value Store, Building a Global Rate Limiter for Your OpenAI Wrapper, Key-Value vs Redis.