Cache Stampede: Protecting the Database When a Hot Key Expires, Request Coalescing, Serving Stale and Early Refresh

A cache sits in front of a database to protect it. The moment a hot key expires, that protection disappears for a second: hundreds of concurrent requests find the cache empty and all of them send the same expensive query to the origin. The origin slows down, queries take longer, and every request that arrives during those longer queries also finds an empty cache. That is a cache stampede, also called the dogpile effect. It is invisible on a normal day and takes the system down at peak traffic or right after the cache restarts. This post covers where it comes from, the ways to prevent it, and which one to pick.

Three shapes of the same problem

Stampedes come in different forms, and telling them apart makes the choice of fix easier.

A single hot key. Homepage data, a popular product, a config everyone reads. When it expires, you get as many recomputations as there are concurrent requests.

Synchronized expiry. A batch job writes thousands of keys at once with the same TTL. An hour later they all fall out in the same second. None of them is hot on its own, but together they flatten the origin.

Cold start. The cache server restarts, memory is flushed, or a deploy changes the key format. Every key is empty at the same time. This is the worst case, because neither of the cheap fixes below is enough on its own.

Approach 1: add jitter to the TTL

The cheapest measure. Instead of a fixed TTL, give each key a TTL with ten to twenty percent random spread. Keys written together then expire spread out over time.

import random

def ttl_with_jitter(base_seconds, spread=0.15):
    return int(base_seconds * (1 + random.uniform(-spread, spread)))

This fixes synchronized expiry and does nothing for a single hot key: that key still expires at one instant and a hundred requests still hit the origin together. Add jitter everywhere, but do not treat it as the whole answer.

Approach 2: coalesce requests

Within one process, only one of the concurrent requests for a key goes to the origin and the rest wait for its result. In Go the ready-made tool is golang.org/x/sync/singleflight:

var group singleflight.Group

func getProduct(id string) (Product, error) {
    if p, ok := cache.Get(id); ok {
        return p, nil
    }
    v, err, _ := group.Do(id, func() (interface{}, error) {
        p, err := db.LoadProduct(id)
        if err == nil {
            cache.Set(id, p, ttlWithJitter(time.Hour))
        }
        return p, err
    })
    if err != nil {
        return Product{}, err
    }
    return v.(Product), nil
}

The effect is large, but the limit is clear: coalescing is per process. With forty replicas running, a hot key expiring still sends forty queries to the origin. For most systems forty is far better than a thousand and good enough. If it is not, move to the next approach.

Approach 3: one rebuilder via a distributed lock

If you want exactly one rebuild across all replicas, you need a shared lock. In Redis that is an atomic SET with NX and PX:

import uuid

def rebuild_with_lock(r, key, compute, ttl, lock_ms=10000):
    token = str(uuid.uuid4())
    if r.set(f"lock:{key}", token, nx=True, px=lock_ms):
        try:
            value = compute()
            r.set(key, value, ex=ttl)
            return value
        finally:
            release_if_owner(r, f"lock:{key}", token)
    return None

The real decision is what a request that fails to get the lock should do. Polling and waiting delays it by the full compute time, and the waiting requests fill your connection pool. Serving the old value is better, which leads to the next approach.

When releasing, delete only the lock you own. If the computation outlives the lock, the lock expires, another request takes it, and a plain DEL would remove their lock. Compare and delete in one step with a small Lua script:

if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
end
return 0

Approach 4: serve stale, refresh in the background

This is the default we recommend. Each cached value gets two lifetimes: a logical one and a physical one. You store a "stale after" timestamp inside the value and give the cache entry a longer TTL than that.

If the value is fresh, return it. If it is stale, return it anyway, and trigger a single refresh at the same time (through in-process coalescing or a distributed lock). Users never wait on recomputation, and the origin sees one query per hot key. Only when the physical TTL has also passed, meaning the value is truly gone, does a request compute and wait.

The price is staleness, and you should accept it deliberately. A few minutes of staleness is fine for product descriptions, counters, listings and recommendations. It is not fine for balances, stock reservations or authorization decisions. Do not cache that kind of data this way.

At the HTTP layer the same idea has a standard form. Cache-Control: max-age=60, stale-while-revalidate=300 tells caches that support it to treat the response as fresh for sixty seconds and then usable for five more minutes while it is revalidated in the background. If nginx is your cache, the equivalent configuration is:

proxy_cache_lock on;
proxy_cache_lock_timeout 5s;
proxy_cache_use_stale updating error timeout http_500 http_502 http_503;
proxy_cache_background_update on;

proxy_cache_lock lets only one request per key through to the upstream, updating serves the stale entry while it is being refreshed, and proxy_cache_background_update performs the refresh without making the client wait.

Approach 5: probabilistic early expiration

If you would rather avoid locks, you can get requests to refresh randomly before the value expires. In the method known in the literature as XFetch, each request checks:

now - delta * beta * ln(random()) >= expiry

delta is how long the last recomputation took and beta is a tuning factor, usually 1. Since ln(random()) is negative, the left side is slightly in the future, and the probability of the condition holding grows as expiry approaches. Under high traffic, one request refreshes shortly before expiry while the rest keep reading the fresh value.

It is an elegant method with two requirements: you must store the compute time alongside the value, and traffic must be high enough. At low traffic there is no early refresh, but there is no stampede either. It is harder to explain and debug than stale-while-revalidate, so unless you have a specific reason, build approach 4 first.

Pitfalls

Caching errors, or never caching them. If you write nothing when the origin fails, every request retries it during an outage and the stampede becomes the outage. If you cache error responses for long, you miss the recovery for minutes. Cache errors for a few seconds, or keep serving the stale value on error.

Unbounded staleness. A serve-stale system whose origin is down for hours will quietly serve hours-old data. Put an upper bound on how stale a value may be and track the number of keys near that bound.

Shared cancellation. If the coalesced computation runs under the first caller's context or cancellation token, everyone waiting gets a cancellation error when that first user closes the page. Run the shared work under its own context with its own timeout, not the request's.

Keys that do not exist. A lookup for an ID that is not in the database returns nothing, so nothing gets cached, and every request goes to the origin. A buggy or hostile client can exploit this with random IDs. Cache "not found" results too, with a short TTL.

Changing the key format in a deploy. A version prefix on keys is a clean invalidation tool, but the moment the new version goes live the cache is effectively empty. That is a cold start at peak hour. Do it at low traffic and warm the hottest keys first if you can.

No visibility. You only see a stampede if you measure it. A system with a 99 percent average hit rate can still crush its origin in the second the hottest key expires. Besides miss counts, track how many recomputations are running right now; that number is the real fingerprint of a stampede.

Which one to choose

Our ordering: add TTL jitter everywhere, it costs nothing. Add in-process coalescing on top; most systems can stop there. If hot keys are expensive to compute and staleness is acceptable, serve stale and refresh in the background. Add a distributed lock when you run many replicas and the origin cannot afford even a handful of duplicate queries.

There are also cases where you need none of this. If computation takes a few milliseconds, concurrency is low, or the origin scales more easily than the cache, the complexity buys you nothing. And for data that must be consistent, the fix for a stampede is not a smarter cache but keeping that data out of the cache altogether.