The Cache Stampede: When a Hot Key Expires
The thundering herd: why a hot key expiring causes a synchronized flood of misses, and the fixes: locking (one fetches for everyone), stale-while-revalidate (serve old, refresh behind), and probabilistic early expiration (refresh before the crowd arrives).
A dedicated look at the cache stampede, or thundering herd. Why a single hot key expiring turns thousands of harmless cache hits into a synchronized flood of database queries in the same instant, and why that spike can take a system down even when average load is fine. Then the three standard defenses, each analogy-first with a visualizer: locking and single-flight (only the first miss refetches, the rest wait), stale-while-revalidate (keep serving the stale value while one background refresh runs), and probabilistic early expiration (XFetch, where one request refreshes early before the herd forms), plus jittered TTLs for synchronized warm-ups.
We have kept a cache correct with invalidation: delete or expire the copy when the truth changes. But there is one specific moment where doing that, for one very popular key, goes badly wrong. Not because the cache is incorrect, but because everyone notices at the same instant.
Picture a busy ticket hall with one clerk and a board on the wall showing the price. All day, people glance at the board and walk to the gate; the clerk barely looks up. Now someone takes the board down for a second to reprint it. In that one second, every single person in the hall, all of them, turns and asks the clerk the price at once. The clerk, who was fine handling the occasional question, is suddenly buried under a hundred people shouting the same one. Nothing about the average changed. Everything about the timing did.
That is a cache stampede, also called the thundering herd. The board is a cached value, the clerk is your database, and the moment the board comes down is the cache entry expiring. The danger is not the total number of questions; it is that they all arrive in the same instant.
The problem: a synchronized spike
Walk through what happens with numbers. Suppose one key is read 10,000 times a second, and it is cached, so the database sees almost none of that. The key has a 60-second TTL. For 60 seconds, life is calm. Then the timer hits zero. In the very next instant, some large share of those 10,000 requests all find the key missing, and every one of them independently decides to go fetch it from the database. The database, which was comfortably handling a trickle, is hit with thousands of identical queries in the same breath. It slows down. Because it slows down, the refills take longer, so even more requests pile up behind them. A system that looked perfectly healthy a second ago is now falling over, and it was not extra traffic that did it, it was synchronization.
The hot key is cached, so all five requests hit it, cheap and fast. The database is idle.
The thing to hold onto: every fix below is really the same idea in a different disguise. Stop thousands of requests from all doing the same expensive work at the same time. Let one do it, or serve something while it happens, or spread out when it happens.
Fix 1: Locking, so one fetches for everyone
Go back to the ticket hall. The clerk puts up a small sign: "reprinting the board, one moment." Now when the board is down, people do not all shout at once; they see the sign and wait. One staff member reprints the board, puts it back, and everyone reads it again. The reprint happened once, not a hundred times.
That is locking, sometimes called single-flight. When a request misses, it takes a lock before going to the database. Any other request that misses in the same window sees the lock is held and waits, rather than launching its own duplicate query. The one holder fetches the value, fills the cache, and releases the lock; everyone who was waiting then reads the fresh value straight from the cache. The database sees one query instead of thousands.
On the miss, only the first request takes a lock and goes to the database. The other four see the lock and wait instead of piling on. The database gets one query.
The catch is that everyone waits on that one fetch, so if it is slow, they all feel it, and you have to handle the holder crashing (a lock with a timeout, so a dead holder does not freeze everyone forever). It is the most direct fix and the one most people reach for first.
Fix 2: Stale-while-revalidate, so nobody waits
Different idea. What if, instead of taking the board down to reprint it, you leave the old board up and print the new one in the back room, then swap them when it is ready? For that short while, people read a board that is a few minutes out of date, which is usually fine, and nobody ever stands and waits.
That is stale-while-revalidate. When the entry expires, you do not evict it; you mark it stale and keep
serving the stale value to everyone, instantly, while a single background refresh fetches the new value
and swaps it in. No request is ever blocked, and the database still sees just one query. The price is that
for a brief moment you are knowingly serving slightly old data, so it fits anything where a few seconds of
staleness is harmless (a feed, a count, a rendered page) and not where it is not (a bank balance). It is
common enough to be a standard HTTP cache directive, Cache-Control: stale-while-revalidate.
On expiry, keep serving the slightly stale value to everyone immediately, so nobody waits, and kick off a single background refresh to the database.
Fix 3: Refresh early, before the crowd arrives
The cleverest idea does not react to the expiry at all; it avoids it. What if, as the board gets close to its reprint time, each person glancing at it has a small and growing chance of deciding, on their own, "I will go get a fresh one now," well before it is actually due? Almost always nobody bothers. But as the deadline nears, the odds rise, and one person volunteers and refreshes it early. By the time the old board would have expired, a fresh one is already up. The crowd never forms, because there was never a moment with no board.
That is probabilistic early expiration, the idea behind an algorithm called XFetch. Each read, as the TTL approaches, rolls the dice with a probability that climbs as expiry nears; when one read wins, it recomputes the value in the background and resets the timer. No lock, no coordination, no waiting: just one lucky request doing the work slightly early so the entry is never actually empty.
The key still has plenty of time to live, so the chance any request refreshes early is tiny. Everyone just hits the cache.
There is a simpler cousin worth naming. Sometimes the problem is not one hot key but many keys that were all created together, for example when you warm a cache at startup or after a deploy, so they all share the exact same expiry time and all fall over at once. The fix is jitter: add a small random spread to each TTL (say 60 seconds plus or minus a few) so the expiries scatter across a window instead of firing on the same tick. It is one line, and it turns a synchronized cliff into a gentle trickle.
What to reach for
In practice these layer. Stale-while-revalidate is a great default for anything that tolerates a moment of staleness, because nobody ever waits. Add a lock as the fallback for a true cold miss, where there is no stale value to serve, so the very first fetch is still protected. Use early expiration or proactive refresh for the known handful of hottest keys, so they are always warm before anyone notices. And jitter your TTLs so a batch of keys never expires in lockstep. None of these is exotic; together they are the difference between a cache that quietly absorbs a spike and one that amplifies it.
Next: we leave the server side entirely. Every cache so far has lived near your database. The last one lives near your users, at the edge of the network, thousands of miles closer than your servers: the CDN. That is the next piece.
Sources: Cache stampede (Wikipedia); Vattani, Chierichetti, Lowenstein, "Optimal Probabilistic Cache Stampede Prevention" (VLDB 2015); MDN, Cache-Control stale-while-revalidate.
