Cache Stampede and Thundering Herd: How to Fix
On this page
Learning Objective
Explain the two distinct ways a cache miss turns into an origin overload, single-key stampede and synchronized mass expiry, and compare the four standard mitigations, distributed locking, request coalescing, probabilistic early expiration, and background refresh, on latency, complexity, and failure behaviour.
Concept Explanation
A cache stampede happens when the cache stops absorbing load at exactly the moment the origin is least able to take it. The mechanism is unpleasantly simple. A popular key expires. Between the instant it expires and the instant someone finishes recomputing it and writing it back, every request for that key is a miss, and every one of those misses goes to the origin. If the key is served a thousand times a second and the recomputation takes two seconds, roughly two thousand identical queries hit the database, all computing precisely the same answer. That surge often makes the recomputation slower, which extends the window, which admits more misses, which is the feedback loop that turns a momentary blip into a sustained outage.
It is worth separating two failure shapes that get discussed together. The first is the single hot key case just described, where one entry is so popular that losing it briefly is enough to saturate the origin on its own. The second is synchronized mass expiry, where a large number of unrelated keys were all populated at roughly the same moment, typically after a deployment, a cache flush, a failover to a cold node, or a nightly batch warm-up, and were all given the same TTL. They therefore all expire within the same second, and the origin receives a broad, simultaneous miss storm across the whole keyspace rather than a spike on one key. The mitigations differ: the single-key case is solved by ensuring only one recomputation runs, and the mass-expiry case is solved by ensuring the expiries are not correlated in the first place, which is what TTL jitter does. Adding a random spread of, say, ten percent to every TTL is close to free and removes an entire class of incident.
For the single-key case the crudest effective mitigation is a distributed lock. The first request to miss acquires a lock on that key, recomputes, and populates the cache; everyone else either waits for the lock or immediately returns a stale value if one is retained. This guarantees exactly one origin query, which is the desired property, but it introduces a lock to operate: it needs a timeout so that a crashed holder does not block the key forever, it needs a decision about what waiters do while they wait, and under high concurrency the waiters themselves can exhaust connection pools and threads. Request coalescing, sometimes called single-flight or request collapsing, achieves the same outcome inside one process without a distributed lock: concurrent callers for the same key are attached to a single in-flight promise, and when it resolves they all receive the same result. It is dramatically simpler and has no distributed failure modes, but it only deduplicates within a process, so with a hundred application instances you get a hundred origin queries rather than one. In practice this is usually a perfectly acceptable reduction, and combining in-process coalescing with a shorter distributed lock at the cache tier covers both scales.
The more elegant family of mitigations avoids the miss entirely rather than managing it. Probabilistic early expiration, formalized in the 2015 VLDB paper on optimal probabilistic cache stampede prevention and often called XFetch, stores the recomputation cost alongside the value and has each reader compute, as the TTL approaches, a small probability of voluntarily refreshing early. The probability rises as expiry nears and scales with how expensive the value is to recompute, so an expensive key is very likely to be refreshed by some single unlucky reader well before it actually expires, while cheap keys mostly just expire normally. The cache effectively never goes empty for hot expensive keys, and because the decision is randomized per reader, no coordination is needed at all. Background refresh takes the same idea and makes it explicit: a scheduled job or a refresh-ahead policy recomputes hot entries before expiry, which gives the most predictable latency of any option but requires knowing which keys are hot and burns origin capacity on keys that may have stopped being read.
Two supporting behaviours matter as much as the primary mitigation. Serving stale while revalidating means the cache retains the expired value and continues returning it to readers while exactly one refresh runs in the background, converting a latency spike into a brief window of slightly old data. For the overwhelming majority of cached content that is an obviously correct trade, and it is the default behaviour of well-configured CDNs for good reason. The second is admission control at the origin: the cache tier should never be the only thing standing between the internet and a database. A concurrency limit on origin queries means that when a stampede does occur, the excess requests are rejected or queued quickly instead of all being admitted to saturate the database, so the system degrades along a boundary you chose instead of the one the database picks for you.
| Mitigation | Origin Queries per Miss Event | Added Latency for Waiters | Main Cost |
|---|---|---|---|
| Nothing | One per concurrent request | None until the origin saturates, then everything | The outage |
| Distributed lock | Exactly one | Full recompute time, or immediate stale if retained | A lock to operate, with timeouts and crashed-holder handling |
| In-process coalescing | One per application instance | Full recompute time | Only deduplicates within a process |
| Probabilistic early expiration | Usually zero; refreshed before expiry | None; readers get a warm value | Needs recompute cost tracked per key |
| Background refresh ahead | One, on a schedule | None | Must know which keys are hot; wastes work on keys that cooled |
| Stale-while-revalidate | One, in the background | None | Readers see slightly stale data during the refresh |
Worked Example: Probabilistic Early Expiration Versus a Lock
The XFetch formula looks odd at first, so it is worth seeing what it actually does to the refresh time. The key insight is that each reader independently rolls a weighted die, so the expected number of readers who decide to refresh early is close to one regardless of how many readers there are.
# Stored alongside every value: when it was computed, how long the
# recomputation took (delta), and its absolute expiry.
entry = { value, delta, expiry }
# XFetch: refresh early if this holds, where beta >= 1 tunes eagerness
# and rand() is uniform on (0,1]. log(rand()) is negative, so the left
# side is a positive number that grows with delta.
#
# now - delta * beta * log(rand()) >= expiry
read(key):
e = cache.get(key)
if e is None:
return recompute_and_store(key) # true miss
if now() - e.delta * BETA * log(random()) >= e.expiry:
return recompute_and_store(key) # volunteer to refresh early
return e.value
# Why this behaves well:
# delta large (expensive key) -> the term is large -> refreshes much
# earlier, because a miss here is costly
# delta small (cheap key) -> the term is tiny -> effectively just
# expires normally, no wasted work
# many concurrent readers -> each rolls independently, so roughly
# ONE of them crosses the threshold first
# and repopulates; the rest read the warm
# value on their very next request
# No lock, no coordination, no waiting. The key is rarely ever empty.
# --- Compare: distributed lock ---
read_with_lock(key):
v = cache.get(key)
if v: return v
if cache.set_nx(f"lock:{key}", token, ttl=5): # exactly one winner
try:
v = origin.compute(key)
cache.set(key, v, ttl=300)
return v
finally:
cache.delete_if_owner(f"lock:{key}", token)
else:
stale = cache.get_stale(key)
if stale: return stale # best case: no waiting
sleep(50ms); return read_with_lock(key) # worst case: pile-up
# --- TTL jitter: the fix for SYNCHRONIZED MASS EXPIRY, not for hot keys ---
# Without jitter, 50,000 keys warmed by one deploy all expire in the same
# second and the origin takes 50,000 simultaneous misses.
ttl = BASE_TTL * (0.9 + 0.2 * random()) # spread over a 10% band
# Costs nothing. Removes an entire incident class.Real-World Examples
- Facebook 2010 outage was a textbook stampede driven by an automated system: a configuration value was mistakenly marked invalid, and every client that noticed the invalid value deleted its cached copy and went to the authoritative store to re-fetch it, which then returned the same invalid value again, causing the cycle to repeat. Facebook published a post-mortem describing hundreds of thousands of queries per second arriving at the database and explaining that the only way to stop the feedback loop was to take the site offline entirely, because the load was being generated by the recovery mechanism itself.
- The probabilistic early expiration technique used across the industry comes from a specific, citable source: the 2015 VLDB paper "Optimal Probabilistic Cache Stampede Prevention" by Vattani, Chierichetti, and Lowenstein, which proved that scaling the early-refresh probability by the recomputation cost is optimal and gave the formula now implemented in numerous caching libraries. Nginx offers the related behaviour operationally through proxy_cache_lock, which admits one request to the origin per key, and through proxy_cache_use_stale updating, which serves the stale response to everyone else while the single refresh runs.
Review Questions & Answers
A single-key stampede is a concurrency problem on one entry: one very popular key expires and every concurrent reader misses simultaneously, so the fix is to ensure only one of them recomputes, through a lock, coalescing, or early refresh. Synchronized mass expiry is a correlation problem across many entries: thousands of unrelated keys were populated at the same instant with the same TTL and therefore expire together, producing a broad miss storm where no individual key is especially hot. Per-key coalescing does almost nothing there, because each key genuinely does need its own recomputation and there is only one or a few requests per key. The fix is to break the correlation by adding randomness to the TTL so the expiries spread out over a window, which in turn does nothing for the single hot key. They share a symptom, a spike in origin load, and have unrelated causes.
Because the damage done by a miss is proportional to how expensive the value is to rebuild, so the effort spent avoiding a miss should be proportional too. A key that takes two milliseconds to recompute can be allowed to simply expire, since even a full stampede on it costs little, and refreshing it early would be wasted work. A key that takes four seconds and locks a table while it runs must never be allowed to go empty under load, so readers should start volunteering to refresh it well before its nominal expiry. Weighting by the measured recomputation time gives that behaviour automatically and adaptively, without anyone having to classify keys by hand or maintain a list of expensive ones, and the VLDB paper result is that this specific weighting is the optimal choice rather than merely a reasonable heuristic.
When waiters block. If the recomputation takes several seconds and hundreds of requests per second arrive for that key, the lock successfully limits origin queries to one but leaves every other request holding a thread, a connection, and possibly an upstream socket while it waits. Those resources are finite, so the application tier exhausts its pool, requests for entirely unrelated keys start queuing behind them, and a problem confined to one key becomes a whole-service outage. The lock also needs a timeout, and if the holder crashes or is slow, everyone waits for that timeout before anyone retries. A lock is only safe when waiters do something cheap instead of blocking, such as immediately returning a retained stale value or failing fast with a degraded response, which is why stale-while-revalidate is the natural companion to locking rather than an optional refinement.
Because those mitigations reduce the probability of a stampede but cannot bound the consequences of the cases they do not cover, and they can themselves fail. A cache node can be lost, taking a portion of the keyspace to zero hit rate instantly. A deployment can change a key format and orphan the entire cache at once. Traffic can shift onto a keyspace region that was never warm. In all of those, the coalescing is working perfectly and the origin still receives far more concurrent work than it can serve. An explicit concurrency limit or admission control at the origin means that excess load is shed quickly and cheaply at a boundary you defined, so the database keeps serving the requests it admits at normal latency instead of accepting everything and degrading into timeouts for all of them. It converts an uncontrolled collapse into a controlled partial failure.