RishabhWrites
Back to the Library

When Caches Bite Back: Stampedes, Avalanches, and Penetration

Rishabh Singhal 8 min read Updated
Watch on YouTube Explore Short Reels

Most caching bugs make your data wrong. This post is about the worse kind: the ones that make your whole system fall over, usually at the moment you can least afford it.

What makes them nasty is that a cache working perfectly is quiet. Nobody looks at it. Then one day it expires, restarts, or gets confused, and the load it was hiding lands on a database that forgot how to carry it.

This is Part 6 of the caching series. Part 5 walked through the layers. This one is about what happens when one of them lets go.

In one minute: Three classic failures. A stampede is many requests rebuilding the same expired key at once. An avalanche is many keys expiring at the same moment. Penetration is requests for data that doesn’t exist, which no cache can ever answer. Each has a standard defense. And all three get worse when clients retry.

The Setup: Why This Is Dangerous

Quick recap of a point from Part 1. Say your database can handle 300 requests per second, and you add a cache with a 90% hit ratio. Your system now happily serves 3,000 requests per second.

You’ve also quietly become dependent on the cache. At 3,000 rps, a cold cache means 3,000 rps of misses landing on a database built for 300. That’s ten times its capacity.

This is the central idea of a family of failures researchers call metastable failures: a trigger pushes the system into a bad state, and then a feedback loop (usually retries or rebuilding work) keeps it there even after the trigger is gone (HotOS 2021). A follow-up study found metastable failures were behind a good share of published major outages at large cloud providers (OSDI 2022).

With that in mind, here are the three common triggers.

1. Cache Stampede (Thundering Herd)

What happens: A popular key expires. In the next few milliseconds, hundreds of requests all miss, and all of them go to the database to rebuild the same value. The database slows down. Slower rebuilds mean the key stays missing longer, so even more requests pile up.

Here it is happening, with a deliberately simple model (illustrative, not a measurement of any real system). Requests arrive steadily and the database shares its capacity between the queries it is running. Start with No protection, then switch to the defenses described below and compare:

Database queries in flight010203040comfortable loadkey expires▲ off the chartkeytime (illustrative units)The key is✕ missingQueries in flight121Requests waiting121
Every request that missed started its own rebuild. The database shares its capacity between all of them, so each one gets slower as more arrive, and none finishes. 121 queries were in flight at the end, still climbing, and the key never came back.

Defense A: Request coalescing (single-flight)

Let one request rebuild the value and make everyone else wait for that result. Instagram described a neat version of this: instead of caching the value, cache a Promise for it. The first miss creates the Promise and starts the backend call. Concurrent requests that miss find the same Promise and wait on it instead of making their own calls (Instagram Engineering).

In TypeScript it’s small:

const inFlight = new Map<string, Promise<Product>>();

async function getProduct(id: string): Promise<Product> {
  const cached = await cache.get(`product:${id}`);
  if (cached) return cached;

  let pending = inFlight.get(id);
  if (!pending) {
    pending = db.products.findById(id)
      .then(async (p) => { await cache.set(`product:${id}`, p, { ttl: 300 }); return p; })
      .finally(() => inFlight.delete(id));
    inFlight.set(id, pending);
  }
  return pending;   // everyone waits on the same one
}

Note this only coalesces within one server process. With 50 servers you still get up to 50 rebuilds. To go further you need a distributed lock or a lease.

Defense B: Leases

Facebook’s memcache paper handles this in the cache itself. On a miss the cache hands out a lease to one client, and tells others to back off and retry shortly (NSDI 2013). I described the mechanism in Part 4.

Defense C: Refresh before it expires

Don’t wait for the key to die. Rebuild it slightly early, at a random moment. A 2015 VLDB paper formalized this as “probabilistic early expiration”: each request, as the expiry approaches, flips a weighted coin to decide whether to refresh now. It shows an exponential distribution minimizes both stampedes and unnecessary recomputation (Vattani et al.).

The rule of thumb version, usually called XFetch:

refresh now if:  currentTime - (rebuildTime * beta * ln(random())) >= expiryTime

ln(random()) is negative, so this lets requests start refreshing a bit before the deadline, and the more expensive the rebuild, the earlier they start. Beta is a knob (1.0 is a sensible default).

Defense D: Serve stale while rebuilding

Back to stale-while-revalidate from Part 4. Keep the old value and hand it out while one background request refreshes it. The herd never sees a miss.

2. Cache Avalanche

What happens: Not one key, but many keys expire at the same time. Maybe you loaded them all together at deploy time with the same TTL of one hour. An hour later, they all die together, and the database gets hit by the combined misses. Or the whole cache restarts empty.

Defense: Jitter your TTLs

Add randomness so expirations spread out:

const ttl = 3600 + Math.floor(Math.random() * 600);   // 1 hour, plus up to 10 minutes

Here is the difference on 48 keys that were all loaded at the same moment (illustrative numbers):

48 cached keyscachedexpired, hitting the DBMisses reaching the database02550comfortable load0306090time (illustrative units; TTL = 60)✕ over the comfortable load
All 48 keys were loaded together with the same TTL, so they expired together: 48 misses landed on the database in the same moment, far above what it handles comfortably.

Defense: Warm up before you take traffic

A brand-new cache node, or a freshly deployed server with an in-memory cache, starts cold. Amazon’s Builders’ Library calls out exactly this: new servers launching with empty caches send a burst of requests to the dependency as they fill up, which can overwhelm it during a deployment. Their advice includes running load tests with caches disabled to confirm your service survives without them (Amazon Builders’ Library).

Defense: Soft and hard TTLs

Amazon also describes using two TTLs. Try to refresh at the soft TTL. If the downstream service is unavailable, keep serving the existing data until the hard TTL. A failing dependency then doesn’t instantly become failing users.

3. Cache Penetration

What happens: Requests keep arriving for keys that don’t exist. A cache can’t store “nothing,” at least not by default, so every one of these misses goes to the database, finds nothing, and returns. Whether it’s a buggy client, a crawler guessing IDs, or an attacker doing it deliberately, your cache offers zero protection.

Defense A: Negative caching

Cache the absence. Store a “not found” marker with a short TTL (say 30 to 60 seconds). The short TTL matters: if the item gets created a moment later, you don’t want to keep telling users it doesn’t exist.

Defense B: A Bloom filter in front

A Bloom filter is a compact structure that can tell you “this key is definitely not in the set” or “it might be.” Put one in front of the database holding all valid keys. Requests for keys that definitely don’t exist are rejected without touching the database. Bigtable uses the same trick internally: it creates Bloom filters for SSTables so reads for rows that aren’t there don’t cause disk seeks (Bigtable, OSDI 2006).

Defense C: Validate the input

Unglamorous, but often the best. If IDs are always positive integers under a known range, reject anything else at the edge.

Here is where each defense catches a request for a key that doesn’t exist:

validmaybemissRequestmissing keyValidateID sane?Defense CBloom filtercould exist?Defense BCache"not found"?Defense ADatabasecostly partRejectedinvalid ID404definitely not here404cached "not found"Only here doesa fake key costyou a queryA Bloom filter can say "might exist" for a key that does not, so a few fake keysstill get through. It never says "absent" for a key that is really there.

The Case Study: Facebook, September 2010

This is the best-documented example of a cache-related feedback loop, and it’s worth reading in full. Facebook was down for about 2.5 hours.

The trigger: a configuration value was changed in the persistent store and turned out to be invalid. Facebook had an automated system that checks for invalid config values in the cache and replaces them with fresh ones from the persistent store. That works for a transient cache problem. It doesn’t work when the persistent store itself holds the bad value.

So every client saw the invalid value, tried to fix it by querying the database, and the database, swamped by the flood, returned errors. And here’s the cruel part: each client interpreted a query error as another invalid value and deleted the cache key. Deleting keys caused more misses, more queries, more errors, more deletes. The databases never got room to recover.

The only way to break the loop was to stop all traffic to the database cluster, which meant turning the site off. They disabled the automated correction system afterwards (Engineering at Meta, “More Details on Today’s Outage”).

It’s not a textbook stampede. It’s something more instructive: error handling that made the problem worse. A cache miss should never be the reaction to an error. If the source is failing, hammering it harder isn’t a recovery plan.

A Defensive Checklist

  • Never let retries multiply load. Use exponential backoff with jitter, and cap retry budgets.
  • Coalesce identical misses (single-flight, leases, or promises).
  • Jitter TTLs. No synchronized expiry.
  • Cache negatives briefly.
  • Load-test with the cache off and with the cache cold. If it falls over, you know your real capacity, not your cached one.
  • Protect the origin with rate limits and circuit breakers, so that if the cache fails, the database degrades instead of dying.
  • Alert on origin load, not just hit ratio. Hit ratio can look fine while the database is on fire.

Try It Yourself

Cache Lab scenario 6 puts a hot key on a timer, with a database that can handle only so many queries.

Challenge: keep the database queue under its limit when the hot key expires at peak traffic. Try coalescing first, then early refresh, then both. Then turn on client retries and see whether your fix survives.

Summary

A cache raises your capacity, and that capacity quietly becomes load-bearing. Stampedes, avalanches, and penetration are three ways of finding out. Coalesce rebuilds, spread out expirations, cache absences, and test without the cache. And remember the 2010 lesson: when the source is struggling, the worst thing a cache layer can do is panic and ask again.

Next up: Caching at Scale: Distributed Caches, Consistent Hashing, and Hot Keys. One cache server isn’t enough anymore. What do you do when you have fifty?

References

Comments