What Is Distributed Locking for Cache Rebuilds, and How Does It Prevent Cache Stampedes

A distributed lock stops a cache stampede by making the first request that sees an expired key atomically claim a shared marker (in Redis, SET lock:key <token> NX PX ttl); because only one writer can create a key that does not yet exist, exactly one process is elected to hit the database while every other concurrent request either waits briefly or serves the stale copy — so N simultaneous misses collapse into a single recompute.

The problem it solves: the stampede (dogpile)

A cache stampede (also called the dogpile effect or cache miss storm) happens when a hot key expires and many in-flight requests all miss at the same instant. Each one falls through to the origin — a database, an API, an expensive aggregation — and they all recompute the same value at once. The redundant load spikes the backend, latency climbs, more requests pile up behind the slow ones, and the extra load pushes recompute time even higher: a feedback loop that can take down the origin (the classic thundering herd).

This is not merely theoretical. Facebook's own paper Scaling Memcache at Facebook (NSDI 2013) describes exactly this failure and their production fix — a token mechanism they call leases, which is functionally a per-key rebuild lock. (Note: the widely-repeated claim that Facebook's September 2010 outage was a four-hour cache stampede is inaccurate — that ~2.5-hour outage was a configuration-cache invalidation feedback loop, a related but distinct failure. The honest reference point for stampede prevention at scale is the leases mechanism in the memcache paper.)

The mechanism, and the correct minimal recipe

Coordination lives in a shared store (Redis, Memcached, or a database row) so that all nodes agree on who is rebuilding. The single atomic operation that makes it work is set-if-absent: the winner creates the lock key, does the one expensive rebuild, writes the fresh value, and releases the lock; losers see the key already present and back off.

Why the naive version is wrong

The textbook SETNX-then-EXPIRE-then-DEL sketch has two real bugs:

• No atomic TTL. Setting the lock and its expiry as two commands means a crash between them leaves a lock with no TTL — stuck forever. Every future request now blocks or serves stale indefinitely for that key.
• Blind release. If the rebuild overruns the lock's TTL, the lock expires and another worker legitimately acquires it. A plain DEL then deletes that other worker's lock, re-opening the stampede.

The fix is a single atomic SET ... NX PX with a unique token, and a compare-and-delete release via a Lua script so you only unlock what you still own:

token = uuid4()
ok = redis.set("lock:feed", token, nx=True, px=5000)   # atomic: claim + 5s TTL

if ok:                                 # we are the sole regenerator
    try:
        data = rebuild_from_db()       # the ONE expensive query
        redis.set("feed", data, px=600000)   # cache fresh value, 10 min
    finally:
        redis.eval(RELEASE, 1, "lock:feed", token)  # release-if-owner
else:                                  # someone else is rebuilding
    return cache.get_stale("feed")     # serve stale, or short backoff+retry

-- RELEASE (Lua): delete only if the token still matches
if redis.call('get', KEYS[1]) == ARGV[1] then
  return redis.call('del', KEYS[1])
else
  return 0
end

The get+del must be one Lua script because it runs atomically on the Redis server — a read-then-delete in application code has the same lost-race as blind DEL.

Worked example: a 3-second report at 10 rps

A dashboard report costs 3,000 ms to compute from the database and is requested 10 times per second. Its cache entry has just expired at t=0. Without a lock, the 30 requests that arrive during the rebuild window each miss and fire their own 3-second query — 30 concurrent expensive queries, exactly when the DB can least afford it. With the lock:

Result: 1 database query instead of 30 — a 30× reduction in origin load at the worst moment — and the 29 waiters paid roughly zero extra latency because they served stale rather than queuing behind a 3-second query. The lock collapsed the herd into a single recompute per expiration interval.

Pitfalls

• Stuck lock from non-atomic acquire. SETNX + a separate EXPIRE can crash in between, leaving a permanent lock. Always claim and expire in one command (SET ... NX PX).
• Deleting someone else's lock. A blind DEL on release will unlock a lock a different worker acquired after yours expired. Use the token compare-and-delete Lua script.
• TTL shorter than the rebuild. A 3-second rebuild under a 2-second lock TTL means the lock expires mid-rebuild, a second worker acquires it (duplicate query), and the first worker's release then nukes the second's lock. Set TTL comfortably above p99 rebuild time, or run a watchdog that extends the lock while work is ongoing.
• A herd on the lock itself. If the 29 losers busy-poll Redis every few milliseconds waiting for release, you have just moved the stampede onto Redis and the CPU. Prefer serve-stale immediately; if you must wait, use jittered exponential backoff.
• Synchronized expiry across many keys. A per-key lock only serializes one key. If thousands of keys share the same TTL they all expire together and each rebuilds — still a fleet-wide storm. Add random TTL jitter so expirations spread out.
• Treating it as a correctness lock. Per Martin Kleppmann's critique of Redlock, a Redis lock is not safe under GC pauses, clock skew, or network partitions — two holders can briefly coexist. For cache rebuilds that is fine (worst case: a rare duplicate query). Do not reuse this pattern where mutual exclusion must be guaranteed (e.g. moving money); use a fencing-token or consensus-backed lock there.
• Lock store as a new dependency/SPOF. Every miss now round-trips the lock store. If Redis is down, decide up front whether you fail open (allow rebuild, risk stampede) or fail closed (serve stale only).

When to use a distributed lock — and when not to

Reach for a distributed rebuild lock when all of these hold: the recompute is genuinely expensive (heavy query, fan-out, or an external API you are billed for); you need fleet-wide at-most-one, so per-node deduplication is not enough; and a few hundred milliseconds of coordination latency plus an operational dependency on the lock store are acceptable. The signal is: "one key, many nodes, and each redundant rebuild really hurts the origin."

Weigh it against the main lock-free alternatives:

• Probabilistic early expiration (XFetch). Store the value with its recompute cost delta and expiry; each reader independently recomputes early with probability that rises as expiry nears — refresh if now − delta × beta × ln(rand()) ≥ expiry (Vattani, Chierichetti & Lowenstein, VLDB 2015). Usually a single lucky reader refreshes just before the mass expiry, so nobody ever hits a cold miss and no lock or coordination store is involved. Gain: no lock, no round-trip, no SPOF, scales to millions of keys. Cost: only probabilistic — you may occasionally get 2–3 duplicate rebuilds, and you must track per-key recompute cost.
• Stale-while-revalidate (serve-stale + async refresh). On a near-miss, return the stale value immediately and kick off one background refresh. Gain: best possible latency — users never wait. Cost: requires storing values past their logical TTL and tolerating brief staleness; you still typically pair it with a lock or single-flight to dedupe the background refresh.
• Single-flight / request coalescing (in-process). Go's singleflight or a per-process in-memory map collapses concurrent calls for the same key into one. Gain: zero external dependency, sub-microsecond. Cost: only dedupes within one process — a fleet of 50 nodes still produces up to 50 rebuilds.

Choose the distributed lock when a single rebuild across the whole fleet is worth a coordination round-trip and the recompute is expensive enough that even a handful of duplicates is unacceptable. Prefer XFetch when you want lock-free simplicity across many keys and can tolerate rare duplicates. Prefer single-flight when one node (or per-node dedup) is enough. Prefer stale-while-revalidate whenever a few seconds of staleness beats making any user wait — and combine it with one of the others to dedupe the refresh.

Takeaways

• The entire trick is one atomic conditional write electing a single regenerator; the minimum correct recipe is SET NX PX + a unique token + a Lua compare-and-delete release. The naive SETNX/EXPIRE/DEL version has a stuck-lock bug and a wrong-owner-delete bug.
• A lock converts N rebuilds into 1, but it adds latency and a dependency, and it can create a new herd on the lock store — mitigate with serve-stale on contention, TTL > p99 rebuild time (or a watchdog), and jittered backoff.
• It is a performance guard, not a correctness guard: under partitions two holders can coexist, which is fine for caches but disqualifies it for money-movement style mutual exclusion.
• Often a lock-free approach — probabilistic early expiration, stale-while-revalidate, or single-flight — is simpler and safer; save the distributed lock for expensive recomputes that truly need fleet-wide at-most-one.

Re-authored and deepened for this guide. Sources: Redis documentation on SET, distributed locks and Redlock; Martin Kleppmann, "How to do distributed locking" (2016) and Salvatore Sanfilippo's rebuttal; Nishtala et al., "Scaling Memcache at Facebook" (NSDI 2013) for the leases mechanism; Vattani, Chierichetti & Lowenstein, "Optimal Probabilistic Cache Stampede Prevention" (VLDB 2015) for XFetch; and the Go golang.org/x/sync/singleflight package. The unverified "Facebook 2010 four-hour stampede" claim from the original page was removed and replaced with the accurate leases reference.