Stampedes, penetration and avalanches

Critical cache failure modes at scale

When running at tens of thousands of requests per second, caching anomalies can instantly cascade into catastrophic database outages:

1. Cache Stampede (Thundering Herd)

The Problem

A hot key (e.g. Flash Sale product or viral news article) expires its TTL while 5,000 concurrent requests arrive simultaneously. All 5,000 requests detect a cache miss at the exact same millisecond and bombard the database with identical heavy queries, exhausting connection pools and causing cascading timeouts.

Solutions

1. A lock, so only one request recomputes (request coalescing): Only the first worker to take a short-lived lock (Redis: SET lock:key token NX PX 5000, which succeeds only if the key does not exist and expires after 5 seconds) queries the database and repopulates the cache; the others wait briefly and re-check the cache. Redis notes this simple lock is best effort: store a random token and only delete the lock if it still holds your token, so you never release someone else's lock. Facebook's memcache gets the same effect by handing out a refill lease for a key only once in a while.

2. Probabilistic early expiration (XFetch): Vattani, Chierichetti and Lowenstein (VLDB 2015) let each request decide at random to recompute a little before the key expires. A request recomputes when

   $$t_{\text{now}} - \Delta \cdot \beta \cdot \ln(\text{rand}()) \ge t_{\text{expiry}}$$

   where $\Delta$ is how long the last recomputation took, $\beta$ (default $1$) sets how eager it is, and $\text{rand}() \in (0, 1]$, so $-\ln(\text{rand}()) \ge 0$. Early on the chance is tiny; as expiry approaches it rises toward certainty, and one request typically refreshes the value while the others still read the cached copy. The paper shows this drastically shrinks stampedes without having to tune for the request rate; it does not promise to eliminate them.

2. Cache Penetration (Malicious / Non-Existent Keys)

The Problem

An attacker queries millions of non-existent keys (e.g. GET /user/-999999). Because non-existent keys are not in the cache, 100% of malicious requests bypass the cache and trigger expensive table scans in the database.

Solutions

1. Bloom filter of existing keys: A compact in-memory filter of every key that exists, checked before the cache. It answers "maybe present" or "definitely absent"; a "definitely absent" skips both cache and database. This only holds if the filter is kept up to date with every key that is inserted.
2. Negative caching: When the database finds nothing (or returns an error), cache that result too, with its own, shorter TTL than normal entries (for example, a minute). Repeated requests for the missing key are then answered from the cache.

3. Cache Avalanche (Mass Concurrent Expirations)

The Problem

Thousands of cache keys are initialized simultaneously at system startup with identical 1-hour TTLs (TTL = 3600s). At exactly $t = 3600\text{s}$, all keys expire at once, routing massive uncached traffic to the database.

Solution: Randomized TTL Jitter

Always add uniform random jitter to expiration times:

A related case: a server that launches with an empty cache sends a burst of misses to the services behind it. Request coalescing (only one request in flight per uncached key) limits the damage.