Cache stampede: an interactive thundering herd simulator
A cache stampede, also called a thundering herd or dog-pile, happens when a popular cache entry expires and every request that arrives before it is rebuilt misses the cache and queries the database itself. A key read thousands of times a second turns one expiry into hundreds of identical queries at once, enough to slow or topple the database the cache was there to protect.
The playground sends a steady stream of requests to one hot key that lives 10 seconds in the cache. Rebuilding it is a 200 ms query. Pick a defence and a traffic level, and watch the database.
2,000 requests a second for one hot key that lives 10 s in the cache. The key expires at 10 s. For the 200 ms it takes to rebuild, every request misses and queries the database itself: about 391 queries at once against a database that handles 20 at full speed. They slow each other down, so the pile takes seconds to drain and the slowest requests wait 900 ms. Every expiry does it again.
Why one expiry becomes a stampede
Three things combine: a key that is read very often, a value that is slow to rebuild, and nothing stopping requests from rebuilding it at the same time. At 2,000 requests a second and 200 ms to rebuild, about 400 requests miss before the first rebuild lands, and each starts its own query. The database can only work on so many at once, so they slow each other down: in the first preset the queries peak at 412 in flight, the slowest requests wait 900 ms, and the database is busy for seconds clearing the pile, slowing every other query it serves.
The same thing happens on a larger scale when many keys expire together, because they were all cached at deploy time with the same TTL, or when a cache restarts empty and every key misses at once.
Four ways to prevent it
| Defence | How it works | The cost |
|---|---|---|
| Request coalescing | The first miss rebuilds; later misses wait for its result (a lock, or single-flight) | Requests wait for the rebuild; the lock needs a timeout in case its holder dies |
| Serve stale while refreshing | Keep the old value past its soft expiry and return it while one request refreshes in the background | Some responses are briefly out of date |
| Probabilistic early refresh | Each request near expiry refreshes early with a small, rising probability, so one does it before the key expires | A few extra rebuilds; needs to know how long a rebuild takes |
| Jitter the TTLs | Add a random spread to each key’s TTL so keys cached together expire apart | None worth mentioning; it does not help a single hot key |
In the playground at 2,000 requests a second, all three of the first defences bring the database down from 781 queries to two or three. Coalescing makes the requests that arrive during a rebuild wait for it, 49 ms at p99. Serving stale makes nobody wait, at the price of 781 responses that were up to 200 ms old. Early refresh rebuilds about a second before expiry, so the key never expires at all. HTTP has the stale option built in: Cache-Control: max-age=10, stale-while-revalidate=30.
Coalescing across many servers
Single-flight inside one process removes duplicates only within that process: with 50 application servers, a hot key still gets 50 rebuilds at once. To coalesce across servers, take a short lock in the cache itself, such as Redis SET key:lock 1 NX PX 2000, and have the losers serve the stale value or wait briefly and read again. Give the lock an expiry, so a server that dies holding it does not block the rebuild for good.
Probabilistic early refresh in code
import math, random, time
def get(key, recompute, ttl, beta=1.0):
"""Probabilistic early refresh (XFetch): no lock, and the key never expires under load."""
entry = cache.get(key) # (value, seconds the last recompute took, expiry)
if entry:
value, delta, expiry = entry
# -log(random()) is a positive random number, usually small, occasionally large
if time.time() - delta * beta * math.log(random.random()) < expiry:
return value # fresh enough, and this request was not picked
start = time.time()
value = recompute()
delta = time.time() - start
cache.set(key, (value, delta, time.time() + ttl), ttl=ttl)
return valueThis is the XFetch algorithm from Vattani, Chierichetti and Lowenstein’s 2015 paper on cache stampede prevention. A larger beta refreshes earlier; busier keys refresh earlier on their own, because more requests get a chance to be picked.
In a system design interview
Raise it whenever a single key is very hot: a celebrity’s profile, a viral link, the home page. “That key is read 50,000 times a second from the cache. To stop a stampede when it expires, entries have a soft TTL: past it, readers get the cached value while one of them, holding a short lock in Redis, rebuilds it. TTLs carry random jitter so keys cached together do not expire together.” Then expect the follow-ups: what happens when the cache itself restarts, and how stale is acceptable.
Read the guide to caching or cache invalidation, see LRU caches for what gets evicted, or watch a strong candidate design a URL shortener, where a viral link is a hot key.
Questions people ask
What is a cache stampede?
A burst of identical database queries that happens when a popular cache entry expires: every request that arrives before the entry is rebuilt misses the cache and recomputes it. For a key read thousands of times a second, one expiry can send hundreds of queries to the database at once. It is also called a thundering herd or dog-pile.
How do you prevent a cache stampede?
Make sure only one request rebuilds an expired entry. Request coalescing has the others wait for that one result; stale-while-revalidate serves them the old value while it refreshes; probabilistic early refresh rebuilds the entry shortly before it expires; and random jitter on TTLs stops many keys from expiring at the same moment.
What is request coalescing?
Combining concurrent requests for the same missing key into one fetch: the first request starts it and the rest wait for its result. Within one process it is often called single-flight; across many servers it needs a shared short-lived lock, for example in Redis with SET NX and an expiry, so only one server rebuilds the key.
What is stale-while-revalidate?
A caching policy in which an entry past its freshness lifetime can still be served for a while, as long as a refresh is started in the background. Readers never wait for a rebuild and the backend sees one refresh per key. HTTP supports it as a Cache-Control directive, and application caches can implement it with a soft and a hard TTL.
What is probabilistic early expiration?
A technique, known as XFetch, in which each read of a cached entry decides at random whether to refresh it early, with a probability that rises as expiry approaches and with how long a rebuild takes. Under load, one request refreshes the entry shortly before it expires, so it never actually expires and no lock is needed.
Why add jitter to cache TTLs?
Keys written at the same time with the same TTL also expire at the same time, for example everything cached right after a deploy or a cache restart. Adding a random spread of, say, plus or minus 10% to each TTL spreads those expiries out so the database sees a steady trickle of rebuilds rather than a spike.
What is the difference between a cache stampede and a cache avalanche?
A stampede is many requests rebuilding one hot key at once. An avalanche is many keys missing at once, because they expire together or because the cache node holding them fails, so the database suddenly takes a large share of all traffic. Coalescing handles the first; TTL jitter, replication of the cache and warming it before use handle the second.