Stampedes, Thundering Herds & Cache Warming

On September 23, 2010, Facebook went dark for about two and a half hours — at the time, its worst outage in four years. No hack, no data-center fire. An automated system pushed a bad configuration value, and every client that read it did the "responsible" thing: treated its cached copy as invalid, deleted the cache key, and queried the database for a fresh one. Every client. At once.

Hundreds of thousands of identical queries per second slammed the databases. The databases began returning errors — and here's the beautiful, horrible part: the clients interpreted those errors as more bad data, so they deleted the cache again and asked again. A perfect feedback loop. Even after engineers fixed the original config value, the loop kept feeding itself — the fix couldn't get a word in. The only way out was the nuclear option: turn off Facebook, let the herd disperse, and bring traffic back slowly onto warm caches.

Everything in that disaster is this lesson. For three lessons now we've said, almost casually, "a miss just reloads from the database" — and that's true when one request misses. But your cache exists precisely because the database can't handle the full load. So the real question — the one this lesson answers — is: when the cache stops shielding the database, even for a second, what happens to the flood? And more importantly: who's standing in front of the database when it does?

Scope: one cache, one database, and a flood of identical misses. Spreading a cache across many nodes is the next lesson; the planet-sized version of this problem (CDNs) comes right after.

Here's the mental model, and it's worth being precise: a stampede is not "too much traffic." Your traffic didn't change at all. A stampede is amplification — the same traffic suddenly costing wildly more.

Picture one blazing-hot key — the viral listing, cached, serving ten thousand reads a second from memory. Its TTL ends. For the next half-second, until somebody finishes recomputing it, every one of those reads is a miss — and in naive cache-aside, every miss independently goes to the database and runs the same expensive query. If the rebuild takes 500 ms at 10,000 requests/second, that's five thousand copies of the same query for a value the database only needed to produce once. That's the amplification: 1 expired key × N concurrent readers = N identical queries, of which N−1 are pure waste.

And it gets worse on its own, because the loop feeds itself:

more queries → the database slows down → the rebuild takes longer → the miss window stays open longer → even more requests pile in → the database slows further…

That's the death spiral, and it's the same self-reinforcing shape you met with retry storms back in the async chapter — the system's own reaction to load becomes the load. Facebook's outage was exactly this loop wearing a config-change costume; it outlived its own trigger. Notice the cruel irony: the cache made your database look infinitely fast for months — and then, in one expiry, became the amplifier that killed it. The better your cache (the higher the hit rate), the bigger the cliff on the other side.

Every stampede you'll meet in production is one of three shapes — worth recognizing on sight, because the cure differs by shape.

1. The hot-key dogpile. One very hot key expires (or gets invalidated) while under heavy read load, and every concurrent reader piles onto the database to rebuild the same value. This is the classic cache stampede, also called the dogpile effect — and when people say thundering herd they usually mean this too (the name is borrowed from an old OS problem where waking all waiting processes for one event let them trample each other). Trigger: a TTL ending, or a careless invalidation of something popular.

2. Mass synchronized expiry. Nobody key is hot, but thousands of keys were cached at the same moment with the same TTL — a deploy warmed them together, a batch import filled them together, a cron refreshed them at midnight. Sixty minutes later, they all expire in the same instant, and the database takes a wall of misses across the whole keyspace. No single key did anything wrong; the cohort is the problem.

3. The cold cache. A restart, a deploy, a failover, a Redis crash — and the cache comes back empty. Hit rate: zero. For the next several minutes, the database faces 100% of the traffic, something it may not have seen in years — and since traffic has grown comfortably behind the cache's shield, the database was probably never sized for it. The most dangerous minute of a cache's life is its first.

Same amplification underneath, three different triggers: one hot key · one synchronized cohort · one empty box. Now let's break each of them with your own hands.

Below is live traffic flowing through a cache into a database, with the database's load gauge underneath — and a hard capacity line it must not cross.

Do this in order:

1. Start with HOT-KEY EXPIRY, no protections. Watch the healthy green flow — then the TTL hits, and every request pours past the dead key straight into the database. The gauge pins past capacity; rebuilds slow down; the miss window stretches. That red mountain is the amplification loop from two sections ago.
2. Flip on the single-flight lock and replay: one request rebuilds, everyone else waits a beat, and the mountain collapses to a single blip. Then try stale-while-revalidate instead — same single blip, but now nobody even waits: users get the slightly-old copy instantly while one refresh runs in the background.
3. Switch to MASS EXPIRY, no protections — a thousand keys die at once and the wall of misses buries the gauge. Now turn on TTL jitter and replay: same keys, same TTLs on average, but the expirations scatter, and the wall becomes a drizzle the database barely notices.
4. Finally, COLD RESTART — the cache comes back empty and the flood is total. Turn on pre-warming and replay: the hottest keys are loaded before traffic arrives, and the flood never forms.

Watch the counters as you go — peak concurrent queries is the one that kills databases; total queries is the waste; stale served and average wait are what your users actually felt. Every cure buys the same peak reduction with a different currency.

The hot-key stampede has a laughably simple observation at its core: N requests are racing to compute the same answer. All three per-key cures just enforce, in different ways, that only one of them actually does.

The per-key lock (single-flight / request coalescing). On a miss, the first request takes a short lock on that key and rebuilds; the other N−1 wait for its result instead of querying. N database queries become one. This pattern is everywhere: Go ships it as the singleflight package; with Redis you take the lock with a SET key NX and a short expiry; and Facebook's leases — the same tokens that killed the stale-set race last lesson — are exactly this idea, with memcache handing out roughly one rebuild token per key per ten seconds and telling everyone else "retry in a moment." The cost is honest: the waiters wait (a few hundred milliseconds behind the one rebuild), and the lock needs its own TTL so a crashed rebuilder doesn't wedge the key forever.

Stale-while-revalidate. Don't make the waiters wait — serve them the expired copy. The entry keeps living past its soft TTL; when it "expires," the next reader triggers one background refresh while everyone — including that reader — gets the stale value instantly. Database sees one query, users see zero added latency, and freshness lags by seconds at most. This is the soft-TTL idea from last lesson wearing its real purpose: herd armor. (HTTP even standardizes it: stale-while-revalidate.)

Probabilistic early refresh (XFetch). The cleverest one: make the expiry never happen under load. As a hot key approaches its TTL, each reader independently rolls a weighted die — the closer to expiry (and the costlier the rebuild), the likelier a "refresh now." One lucky reader refreshes ahead of time, the TTL resets, and a busy key simply never dies in public. The remarkable part: the paper behind it (Vattani et al., VLDB 2015) proved the exponential-weighted version optimal, with no parameters to tune — and it needs no locks at all. Cloudflare runs variants of this at the edge.

Three cures, one principle, different currencies: the lock spends waiting, stale-while-revalidate spends freshness, and XFetch spends a few early refreshes. All three turn N into 1.

The other two shapes aren't about one key — they're about a population of keys behaving in sync. Different problem, different cures.

TTL jitter — never let keys synchronize. If a deploy caches a thousand keys at 12:00 with TTL = 3600, you've scheduled a stampede for 13:00. The fix costs one line: TTL = base ± random(10–20%). Now the cohort's expirations smear across a twelve-minute window instead of one shared instant — the wall of misses becomes a drizzle the database absorbs without noticing. Jitter is so cheap and so effective that it shouldn't be a technique you reach for — it should be the default on every cache write, the same way you learned to jitter retry backoff in the async chapter. Synchronized anything is how herds form.

Cache warming — never open the doors on an empty cache. The cold-start flood happens because traffic arrived before the cache had anything to say. So invert it:

• Pre-warm on deploy: make "load the top N hottest keys" a step in the deploy pipeline, before the instance joins the load balancer. You know your hot keys — your metrics have been telling you for weeks.
• Replay traffic: mirror a slice of production reads at the new instance until its hit rate climbs, then cut it in.
• Ramp gradually: send the new instance 1% of traffic, then 10%, then all — letting the cache fill organically from real requests while the old warm one still carries the load.

And a note from the Facebook story worth keeping: their outage wasn't triggered by an expiry at all, but by invalidation logic run amok — aggressive "self-healing" clients deleting and re-querying in a loop. Stampede thinking applies to every path that can generate synchronized misses: expiries, deploys, failovers, and your own too-clever error handling. If ten thousand clients can decide to do the same thing at the same moment, someday they will.

• "A miss is cheap — it just reloads from the database." One miss is cheap. Ten thousand concurrent misses on the same key are ten thousand copies of the same query, 9,999 of them waste. Stampedes are amplification, not addition.
• "The database handled all the traffic before we added the cache — worst case, we're back to that." Traffic has grown behind the cache, and the database was probably re-sized for the post-cache trickle. A cold cache exposes it to load it has literally never seen.
• "Stampedes are a hot-key problem." That's one shape of three. Synchronized cohorts (same-TTL walls) and cold starts (empty cache after a deploy) stampede without any single key being hot.
• "A lock on the read path? That'll slow everything down." One rebuild plus N−1 brief waits is enormously faster than N rebuilds that push the database into the death spiral — and stale-while-revalidate and XFetch give you the same protection with zero waiting.
• "If the query fails, retry — and clear the cache to be safe." That reflex, at fleet scale, is precisely how Facebook took itself down: errors triggering deletes triggering queries triggering errors. Retries and "self-healing" invalidation during overload are the herd. Back off, jitter, and serve stale instead.
• "We added jitter, we're safe." Jitter kills the synchronized cohort shape only. The hot-key dogpile needs single-flight/SWR/XFetch, and the cold start needs warming. Match the cure to the shape.

• A stampede is amplification: one dead cache entry × N concurrent readers = N identical database queries, N−1 of them waste — self-reinforcing into a death spiral, because overload slows rebuilds, which widens the miss window, which adds load. The better the cache, the bigger the cliff.
• Three shapes, on sight: the hot-key dogpile (one popular key expires under load), the synchronized cohort (thousands of same-TTL keys expire together), and the cold cache (restart/deploy → 100% misses).
• Per-key cures make N into 1: a single-flight lock (one rebuilds, the rest wait), stale-while-revalidate (serve the old copy, refresh once in background), or XFetch (probabilistically refresh before expiry — provably optimal, lock-free). Same peak-killing effect; they differ only in whether you pay with waiting, freshness, or early refreshes.
• Population cures: TTL jitter on every write (± 10–20% — synchronized expiry is a scheduled outage), and cache warming before traffic (pre-warm on deploy, replay, or ramp). And remember Facebook 2010: aggressive retry/invalidate logic can be the herd.

Next — Distributed Caching (+ Consistent-Hashing Intuition). Everything so far assumed one cache box. But one box has a ceiling — memory, bandwidth, and a blast radius of "everything" when it dies (as this lesson made painfully clear). The obvious move is many cache nodes sharing one keyspace — which immediately raises a deceptively hard question: which key lives on which node, and what happens when a node joins or leaves? The answer is one of the most elegant ideas in distributed systems.