Cache stampede: how one expired key takes down the database

A product listing endpoint serves 3,000 requests per second from a single cached key. The TTL is five minutes. At 14:35:00 the key expires.

Three thousand requests miss in the same millisecond. All 3,000 issue the same aggregation query against the same database. The query normally takes 400ms, which is why it was cached in the first place. Under 3,000 concurrent copies of itself it takes considerably longer, and while it is running, another 3,000 requests arrive, miss, and join.

The database saturates. The connection pool exhausts. The endpoint that was comfortably serving 3,000 requests per second from memory is now down, and it went down at a moment when nothing changed: no deploy, no traffic spike, no dependency failure. A timer ran out.

Expiry is a synchronised event

The thing that makes this different from ordinary cache misses is simultaneity.

Under normal operation, misses are spread out. Different keys expire at different times, requests arrive at random, and the origin sees a trickle. A single hot key with a single TTL converts that trickle into a step function, because every consumer of that key becomes a consumer of the origin at exactly the same instant.

Then it gets worse, because the recompute is not instant.

sequenceDiagram
    participant R as Requests
    participant C as Cache
    participant DB as Database

    Note over C: 14:35:00.000 key expires
    R->>C: 3000 concurrent reads
    C-->>R: all miss
    R->>DB: 3000 identical queries
    Note over DB: query normally 400ms,<br/>now contending with 2999 copies
    R->>C: next 3000 requests arrive
    C-->>R: still empty, all miss
    R->>DB: 3000 more
    Note over DB: pileup grows faster than it drains

The window between expiry and the first successful write-back is the danger zone, and its length is a function of how loaded the origin already is, which the stampede itself is increasing. That feedback loop is why this fails hard rather than degrading.

Jitter is the fix with the best ratio

If keys expire in lockstep, stop making them expire in lockstep.

import random

BASE_TTL = 300

def ttl_with_jitter(base=BASE_TTL, spread=0.2):
    # +/- 20 percent, so a population of keys expires over a minute
    # instead of in the same millisecond.
    return int(base * random.uniform(1 - spread, 1 + spread))

cache.set(key, value, ex=ttl_with_jitter())

One line, no coordination, no new infrastructure. It does not help a single hot key that genuinely has one value, but it does help the far more common case: a population of keys that were all populated at the same time, such as after a deploy, a cache flush, or a cold start.

That last case is worth stating plainly. Restarting Redis, or failing over to an empty replica, produces a 100 percent miss rate across every key simultaneously. It is the same failure as a stampede, at full scale, and no per-key TTL strategy helps because nothing has a TTL yet. Warming the cache before taking traffic, or failing over to a replica that already holds the data, is the only thing that does.

The related failure is losing a cache node rather than all of them, where modulo based sharding remaps almost every key and sends the resulting miss storm straight at the database. Consistent hashing bounds how much of the keyspace moves. It does not remove the miss, it caps its size.

Coalescing: one recompute, everyone else waits

Jitter spreads a population out. It does nothing for one expensive key with heavy concurrent traffic, where the answer is to ensure only one caller does the work.

def get_with_coalescing(key, compute, ttl=300, lock_ttl=10):
    value = cache.get(key)
    if value is not None:
        return value

    lock_key = f"lock:{key}"
    # Only one caller wins. The lock TTL bounds the damage if it dies.
    got_lock = cache.set(lock_key, "1", nx=True, ex=lock_ttl)

    if got_lock:
        try:
            value = compute()
            cache.set(key, value, ex=ttl_with_jitter(ttl))
            return value
        finally:
            cache.delete(lock_key)

    # Lost the race. Wait briefly for the winner rather than
    # piling onto the origin.
    for _ in range(50):
        time.sleep(0.05)
        value = cache.get(key)
        if value is not None:
            return value

    # Winner is slow or died. Falling through to compute is a
    # deliberate choice: correctness over protection.
    return compute()

The lock_ttl matters more than it looks. Without an expiry, a process that dies holding the lock blocks every other caller until someone notices. With one, the worst case is a second stampede after the TTL, which is survivable.

The last three lines are the part worth arguing about. Falling through to compute means that under a slow origin you get the stampede anyway. Returning an error instead protects the database and fails the request. Which is correct depends on whether a failed request or a slower database is worse for that endpoint, and it should be a decision rather than a default.

Serving stale is usually better than waiting

Waiting for a recompute means the user waits. Serving the previous value means they do not, and for most cached data a value that is five seconds past its TTL is fine.

The trick is storing the value with a longer physical TTL than its logical freshness:

def get_stale_while_revalidate(key, compute, fresh_for=300, keep_for=3600):
    entry = cache.get(key)          # {"value": ..., "fresh_until": ...}

    if entry is None:
        return compute_and_store(key, compute, fresh_for, keep_for)

    if time.time() < entry["fresh_until"]:
        return entry["value"]

    # Stale but usable. Refresh in the background, serve immediately.
    if cache.set(f"lock:{key}", "1", nx=True, ex=10):
        background.submit(compute_and_store, key, compute, fresh_for, keep_for)

    return entry["value"]

Nobody waits, one worker recomputes, and the origin sees exactly one query. The cost is that a value can be served up to keep_for old if the refresh keeps failing, which is a failure mode worth alerting on rather than discovering.

Probabilistic early expiry, if you want no lock at all

There is a neater answer that avoids both locking and staleness, described in Vattani, Chierichetti and Lowenstein’s 2015 VLDB paper on optimal probabilistic cache stampede prevention.

Each read decides whether to refresh early, with a probability that rises as the TTL approaches and scales with how expensive the value was to compute.

import math, random

def should_recompute(delta, expiry, beta=1.0):
    # delta: seconds the last recompute took
    # expiry: unix time the entry expires
    return time.time() - delta * beta * math.log(random.random()) >= expiry

Expensive values (large delta) start refreshing earlier, cheap ones refresh close to expiry, and because each caller rolls independently only one is likely to trigger. No lock, no stale window, and the value is replaced before anybody misses.

I like this more than it deserves, because it is the rare case where a small amount of maths removes a coordination problem entirely rather than managing it.

What to do, in order of effort

Put jitter on every TTL you set. It is one line, it has no downside, and it removes the synchronised component from every cache in the system rather than the one you happened to notice.

Add coalescing to the keys where a single recompute is genuinely expensive. You do not need it everywhere and the lock has its own failure modes, so apply it where a miss actually hurts.

Decide explicitly what happens when the origin is slow during a miss storm, because the default of every caller falling through to the database is the behaviour that turns a slow query into an outage. A bounded wait, a circuit breaker, or serving stale are all defensible, and failing fast rather than queueing indefinitely is the same reasoning that applies to a saturated connection pool.

Never flush a hot cache in one operation. FLUSHALL on a production Redis is a self-inflicted stampede across every key at once, and the recovery is entirely at the mercy of whether the origin can absorb a cold start at full traffic.