CacheInvalidation.org

Distributed Locks for Cache Coordination

This page shows how to use Redis locks to serialize cache recomputation and invalidation so that concurrent workers never duplicate expensive work or corrupt shared cache state.

The coordination problem shows up the instant more than one worker can rebuild the same cache entry. When a hot key expires or is explicitly busted, every request in flight sees the miss simultaneously, and without a gate they all recompute the same value — hammering the database, wasting CPU, and occasionally racing each other to write conflicting results back into the cache. A distributed lock turns that thundering herd into a single elected worker while everyone else waits or serves stale data. It is the enforcement primitive behind cache stampede prevention and behind any write-behind flush that must not run twice. These patterns are part of the broader Advanced Cache Invalidation Patterns & Synchronization reference; this page is where the mutual-exclusion mechanics are settled.

The uncomfortable truth about Redis locks is that they are a lease, not a mutex. Every lock carries an expiry so a crashed holder cannot wedge the system forever, which means the lock can vanish out from under a worker that is still running. Getting cache coordination right is mostly about designing around that expiry — choosing the right acquisition topology and making the protected work safe even when the lease is lost.

Architectural Trade-offs

Two acquisition models dominate production use: a single-instance lock held on one Redis master, and Redlock, which acquires the same logical lock on a majority of several independent masters. They sit at different points on the safety-versus-simplicity curve. A single-instance lock is trivial to reason about but inherits the availability of one node; Redlock survives the loss of a minority of nodes but pays for it with round trips, clock assumptions, and materially more code. The columns below are the axes that decide which cost your workload can absorb.

Approach Safety guarantee Liveness Complexity Behaviour under failover
Single-instance lock (SET NX PX) Mutual exclusion holds while the one master is authoritative; a token release prevents deleting someone else's lock Depends on one node — if it is down, nobody acquires until failover completes Low — one SET, one Lua release script, one token per acquisition Weak: async replication can promote a replica that never received the lock key, briefly allowing two holders
Redlock across N masters Mutual exclusion holds as long as a majority of nodes agree and clocks stay within the drift budget Survives loss of a minority of nodes; acquisition still succeeds on the remaining quorum High — N parallel acquisitions, validity-window math, release on every node, clock-skew tolerance Stronger: no single promotion can hand the lock to a second holder, because a quorum still pins it

Neither row is a true consensus lock — for that you would reach for a system built on a replicated log, not a cache. Both Redis approaches trade a small, quantifiable probability of double-execution for enormous operational simplicity, and the entire discipline of this page is about making that rare double-execution harmless rather than pretending it cannot happen. The rightmost column is where the two diverge most: a single-instance lock's correctness is only as strong as the failover story of the master it lives on.

Approach A — Single-Instance Lock

The single-instance lock is the workhorse for serializing cache recomputation inside one deployment. Acquisition is a single atomic command — SET key token NX PX ttl — which sets the key only if it does not already exist (NX), stamps it with a caller-unique token, and attaches a millisecond expiry (PX) that guarantees the lock self-releases even if the holder crashes mid-work. That auto-expiry is the safety net that keeps a dead worker from freezing every future rebuild of the key.

The subtle part is release. A naive DEL is a correctness bug: if worker A's lease expired and worker B has since acquired the lock, A's DEL on wake-up would delete B's lock and let a third worker in. The fix is a compare-and-delete executed atomically in Lua — read the stored token, and delete only if it still matches the caller's token. The token is what makes release safe, and it doubles as the fencing value discussed later. The implementation below uses redis.asyncio and registers the release script once so it dispatches as a cached EVALSHA:

import secrets
import redis.asyncio as redis

# Compare-and-delete: only the token owner may release the lock. A bare DEL
# could delete a lock a *different* worker acquired after ours expired.
_RELEASE_LUA = """
if redis.call('get', KEYS[1]) == ARGV[1] then
    return redis.call('del', KEYS[1])
else
    return 0
end
"""


class SingleLock:
    """A leased mutex on one Redis master, released by token match."""

    def __init__(self, client: redis.Redis, key: str, ttl_ms: int = 15_000):
        self.client = client
        self.key = key
        self.ttl_ms = ttl_ms
        self.token = secrets.token_hex(16)          # unique per acquisition
        self._release = client.register_script(_RELEASE_LUA)

    async def acquire(self) -> bool:
        # NX = only if absent; PX = auto-expire so a crashed holder frees it.
        acquired = await self.client.set(
            self.key, self.token, nx=True, px=self.ttl_ms
        )
        return bool(acquired)

    async def release(self) -> bool:
        # Atomic check-then-delete; never removes a lock we no longer own.
        return bool(await self._release(keys=[self.key], args=[self.token]))

Wiring the lock into a recomputation path follows a strict shape: try to acquire, skip the work entirely if another worker already holds it, and always release in a finally block so an exception cannot strand the lease for its full TTL. Note the hash-tag braces around the entity id so the lock and the cache key it protects hash to one slot on a clustered deployment, keeping both operations on the same node:

async def recompute_once(client: redis.Redis, entity_id: int) -> None:
    lock = SingleLock(client, f"lock:rebuild:{{{entity_id}}}", ttl_ms=15_000)
    if not await lock.acquire():
        return  # another worker owns the rebuild; do not duplicate the work

    try:
        value = await expensive_rebuild(entity_id)          # the guarded work
        # UNLINK-then-SET pattern via SET: repopulate the cache atomically.
        await client.set(f"cache:{{{entity_id}}}", value, ex=300)
    finally:
        # Token-checked release: a no-op if our lease already expired.
        await lock.release()

A single-instance lock is the right default when all workers talk to the same primary and a rare double-execution is merely wasteful rather than dangerous — an idempotent cache rebuild, a fan-out invalidation that is safe to repeat. Its one structural weakness is failover: Redis replication is asynchronous, so if the master dies after acknowledging the SET but before the write reaches a replica, a promoted replica comes up without the lock key, and a second worker can acquire it. That window is exactly why single-primary deployments need a deliberate failover model, covered in Sentinel vs Cluster failover.

Approach B — Redlock Across N Nodes

Redlock removes the single-master dependency by running the same acquisition against N independent Redis masters — not replicas of one another, but separate failure domains, typically five. The client tries to SET NX PX the lock on all of them in parallel and considers the lock held only if it succeeded on a majority (three of five) and did so fast enough that a useful validity window remains. Because a quorum is required, no single node's failover can silently hand the lock to a second holder: a promoted replica can only ever supply one vote, and one vote is never a majority.

The validity window is the heart of the algorithm and the part implementations most often get wrong. The lock's real lifetime is not the full TTL — it is the TTL minus the wall-clock time spent acquiring it, minus a drift allowance for clock skew between nodes. If acquiring the majority took longer than the TTL, or the remaining validity is non-positive, the acquisition has failed even though a quorum said yes, and the client must release everywhere before retrying. Releasing uses the same token-checked Lua compare-and-delete as the single-instance lock, fired at every node so partial acquisitions leave nothing behind:

import asyncio
import secrets
import time
import redis.asyncio as redis

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


class Redlock:
    """Majority-quorum lock across N independent Redis masters."""

    def __init__(self, nodes: list[redis.Redis], ttl_ms: int = 10_000,
                 clock_drift: float = 0.01):
        self.nodes = nodes                       # independent masters, not replicas
        self.ttl_ms = ttl_ms
        self.clock_drift = clock_drift           # fraction of TTL reserved for skew
        self.quorum = len(nodes) // 2 + 1        # 3 of 5, 2 of 3, ...
        self._release = [n.register_script(_RELEASE_LUA) for n in nodes]

    async def _acquire_one(self, node: redis.Redis, key: str, token: str) -> bool:
        try:
            return bool(await node.set(key, token, nx=True, px=self.ttl_ms))
        except Exception:
            return False  # an unreachable node counts as a failed acquire, not an error

    async def acquire(self, key: str) -> tuple[str | None, float]:
        token = secrets.token_hex(16)
        start = time.monotonic()
        results = await asyncio.gather(
            *(self._acquire_one(n, key, token) for n in self.nodes)
        )
        elapsed_ms = (time.monotonic() - start) * 1000

        # Real validity = TTL minus acquisition time minus a drift allowance.
        drift = self.ttl_ms * self.clock_drift + 2
        validity_ms = self.ttl_ms - elapsed_ms - drift

        if sum(results) >= self.quorum and validity_ms > 0:
            return token, validity_ms          # locked, with usable time left
        await self.release(key, token)          # roll back any partial acquisition
        return None, 0.0

    async def release(self, key: str, token: str) -> None:
        # Release on every node; token match means we only delete our own lock.
        await asyncio.gather(
            *(script(keys=[key], args=[token]) for script in self._release),
            return_exceptions=True,
        )

The caller must treat validity_ms as a hard deadline, not a suggestion: the guarded work has to finish inside that window, and if it cannot, the worker must abandon the lock rather than assume it still holds. Redlock earns its complexity when the coordinated operation crosses independent infrastructure or when a double-execution would corrupt shared state rather than merely waste a rebuild — for example, a cross-region invalidation that must fire exactly once, or a write-behind flush that would double-apply if it ran twice. The full production build, with retry jitter and per-node connection management, is walked through in Implementing Redlock with redis-py.

When to Choose Which

Resolve the decision against concrete deployment signals rather than instinct. The diagram contrasts what "held" means in each model — one authoritative write versus a majority of independent writes — and the numbered criteria refine the choice.

Single-instance lock versus Redlock majority acquisition Two panels. Left: a client box connects to one Redis master with the command SET NX PX; a caption states the lock is held when the single node acknowledges, and that a failover can lose it. Right: the same client connects to five independent masters in parallel; three are acknowledged and shaded as votes while two are shown unreachable, and a caption states the lock is held only on a majority of three of five within the validity window. Single-instance lock held when one master acknowledges Client SET NX PX Redis master single node 1 of 1 → held failover can drop the lock Redlock majority held only on a quorum of nodes Client M1 vote M2 vote M3 down M4 vote M5 down 3 of 5 → held
  1. Single node versus multi-node safety. If every worker connects to one Redis primary and you accept that its failover briefly voids the lock, the single-instance lock is the correct, cheaper choice. Only reach for Redlock when the lock must survive the loss of an individual node without any window in which two workers believe they hold it.
  2. Tolerance for rare double-execution. Ask what a second concurrent holder actually does. If the guarded work is idempotent — recomputing a cache value, re-emitting an invalidation that a downstream consumer de-duplicates — a rare overlap is harmless and a single-instance lock suffices. If a double run corrupts shared state or double-charges a side effect, you need Redlock and fencing tokens, because even Redlock cannot guarantee a single holder under an unlucky pause.
  3. Operational cost. Redlock means running and monitoring N independent masters, keeping their clocks disciplined with NTP, and carrying the validity-window logic in every client. That is real ongoing burden. Budget it against the blast radius of a double-execution: if the answer is "we retry a rebuild," the single-instance lock wins on total cost; if the answer is "we corrupt a ledger," the quorum earns its keep.

For most cache-coordination work — serializing a stampede-prone rebuild, gating a bulk invalidation — the single-instance lock with token release and a fencing check is the pragmatic default, and Redlock is reserved for the minority of operations whose double-execution is genuinely unsafe.

Failure Modes and Diagnostics

Three failure modes cause nearly every distributed-lock incident. Each has a fast diagnosis before you reach for a fix.

Lock expiring mid-work. The most common and most dangerous failure: a worker acquires the lock, then a GC pause, a slow database call, or event-loop starvation stretches the guarded work past the lease TTL. The lock auto-expires, a second worker acquires it, and now two workers run concurrently — each convinced it is the sole holder. No lock alone can prevent this; the defence is a fencing token, a value that strictly increases with each acquisition and travels with every write to the protected resource, so the resource can reject a write stamped with a stale token. The token in the SET above becomes that fence when it is monotonic. Diagnose by comparing the remaining lease against how long the work actually takes:

# Remaining validity in milliseconds; if this routinely runs negative
# against your p99 work duration, the TTL is too short for the workload.
redis-cli PTTL lock:rebuild:{42}

The sequence below shows exactly how a mid-work expiry produces two holders and where a fencing token cuts the second one off.

Lock expiring mid-work, and how a fencing token stops the stale writer Two worker lifelines over a shared time axis. Worker A acquires the lock with fencing token 41 and begins a rebuild. The lease expiry falls in the middle of that rebuild. Worker B then acquires the lock with token 42 and begins its own work, so an overlap window has both workers live. When Worker A writes with the now-stale token 41, the resource rejects the write because it has already accepted token 42; Worker B's write with token 42 is accepted. both workers live Worker A (token 41) Worker B (token 42) Resource rebuild (token 41) acquire A's lease expires rebuild (token 42) acquire write 41 ✗ write 42 ✓ time

The resource keeps the highest token it has accepted and rejects any write bearing a lower one, so Worker A's late write with token 41 is refused after Worker B's token 42 has been seen. The lock became advisory; the fence made the outcome correct anyway.

Clock drift breaking Redlock validity. Redlock's safety proof assumes bounded clock skew across nodes, because the validity window is computed from elapsed time. If one node's clock jumps — an NTP step correction, a VM migration, a suspended host resuming — its notion of the lock's expiry diverges from the client's, and the lock can expire on that node while the client still believes the window is open. Diagnose by sampling each node's server clock and confirming they agree within your drift budget:

# Sample every node's clock; the first field is Unix seconds. Timestamps
# that disagree by more than the drift allowance invalidate the safety margin.
for host in redis-a redis-b redis-c redis-d redis-e; do
  redis-cli -h "$host" TIME
done

The fix is disciplined NTP with slew rather than step corrections, a conservative clock_drift allowance in the validity math, and alerting on inter-node clock divergence so a drifting host is pulled before it breaks a lock.

Lost lock after primary failover. With a single-instance lock, replication is asynchronous: a SET acknowledged by the master may not have reached any replica when the master dies. Sentinel promotes a replica that never saw the lock key, a second worker acquires the now-absent lock, and mutual exclusion is silently broken. Diagnose by checking whether more than one holder exists across the primary and its freshly promoted replica right after a failover event:

# Immediately after a failover, inspect the holder token on each endpoint.
# Two different non-empty tokens for the same lock key means the invariant broke.
redis-cli -h redis-old-primary GET lock:rebuild:{42}
redis-cli -h redis-new-primary GET lock:rebuild:{42}

The structural fix is either fencing tokens (so the second holder's stale write is rejected downstream) or moving to Redlock, whose quorum requirement means no single promotion can produce a majority. Which failover model minimizes this window — and how quorum and promotion interact — is exactly the trade-off examined in Sentinel vs Cluster failover.

Verification

Confirm the lock behaves correctly against a live instance before trusting it to serialize production work.

First, verify that at any moment exactly one holder exists and that the stored token is the one your worker believes it holds. A present key with a matching token and a positive TTL is a healthy held lock:

redis-cli GET lock:rebuild:{42}    # the current holder's token, or (nil) if free
redis-cli PTTL lock:rebuild:{42}   # remaining validity in ms; -2 means no lock

For Redlock, count holders across every node — a correctly held lock shows the same token on a majority and nothing conflicting elsewhere. A split where two distinct tokens each appear on some nodes means acquisition raced and neither reached a clean majority:

# The same token must appear on a quorum of nodes for the lock to be valid.
for host in redis-a redis-b redis-c redis-d redis-e; do
  printf '%s: ' "$host"; redis-cli -h "$host" GET lock:rebuild:{42}
done

Next, prove that release is token-safe — that a worker cannot delete a lock it no longer owns. Acquire with one token, then attempt release with a different token and confirm the lock survives; only a matching token should remove it:

redis-cli SET lock:demo tokenA NX PX 30000     # expect OK
redis-cli EVAL "if redis.call('get',KEYS[1])==ARGV[1] then return redis.call('del',KEYS[1]) else return 0 end" 1 lock:demo tokenB   # expect (integer) 0 — wrong token, no delete
redis-cli GET lock:demo                          # expect tokenA — lock intact

Finally, instrument acquisition outcomes as first-class metrics so contention and expiry regressions surface before they become incidents. Track acquire success versus failure, lock hold duration against the TTL, and — critically — any case where hold duration approached or exceeded the lease, which is the leading indicator of a mid-work expiry:

import time
from prometheus_client import Counter, Histogram

LOCK_ACQUIRE = Counter("redis_lock_acquire_total", "Lock acquisitions", ["result"])
LOCK_HELD = Histogram("redis_lock_held_seconds", "Time a lock was held before release")


async def guarded(lock, ttl_s: float, work) -> None:
    if not await lock.acquire():
        LOCK_ACQUIRE.labels(result="contended").inc()
        return
    LOCK_ACQUIRE.labels(result="acquired").inc()
    start = time.perf_counter()
    try:
        await work()
    finally:
        held = time.perf_counter() - start
        LOCK_HELD.observe(held)
        if held > ttl_s:  # work outran the lease — a fencing token saved you
            LOCK_ACQUIRE.labels(result="expired_mid_work").inc()
        await lock.release()

A held-duration histogram whose tail crowds the TTL is the signal to lengthen the lease, shorten the work, or add a watchdog that extends the lock while the worker is demonstrably still alive — never to simply hope the pause does not happen.

Up: Advanced Cache Invalidation Patterns & Synchronization