Cache stampede and the thundering herd problem

A cache stampede happens when a popular cached value expires or is evicted and many requests miss it at the same moment, so they all run the same expensive query or render at once and overload the database behind the cache. You prevent it by letting only one request rebuild the value (a lock or request coalescing), refreshing hot keys before they expire, adding random jitter to TTLs, and serving the slightly stale copy while the rebuild runs. The thundering herd problem is the wider family it belongs to: many waiting clients all acting at the same instant.

What a cache stampede looks like

Take an illustrative live class at 7 p.m. with 30,000 students. The class page reads a cached "class details" entry, requested 5,000 times a second as students join. Building it takes a 200 ms query. At 7:00:05 the entry's TTL runs out.

1. Every request arriving during the rebuild misses. At 5,000 a second and 200 ms per rebuild, that's about 1,000 requests, each starting the same query.
   
   
2. The database now runs 1,000 copies of one query. If the application's pool has 100 database connections, 900 requests wait for a connection.
   
   
3. Say that under this load the query takes two seconds instead of 200 ms. The miss window grows tenfold, and about 10,000 requests pile in behind it.
   
   
4. Application workers fill up waiting, unrelated pages start timing out, and clients retry, adding more load.
   
   

The cache didn't fail; it did exactly what it was told. The problem is that expiry turned one query into a thousand, and the slowdown fed on itself. The same thing happens when a hot key is evicted, when someone runs a purge, or when a cache server restarts empty.

Stampede vs thundering herd

Treat a cache stampede as a thundering herd aimed at your database. The fixes overlap: randomness to break synchronisation, and a single leader doing the work while others wait. Reconnect storms after a live class drops are the same pattern; see scaling WebSockets.

Locks and request coalescing

The most direct fix is to let one request rebuild a missing value while the rest wait for it. In Redis, a lock is a key set only if absent, with a timeout so a crashed rebuilder can't hold it forever:

def get_or_rebuild(r, key, ttl, rebuild, wait=0.05, tries=40):
    for _ in range(tries):
        value = r.get(key)
        if value is not None:
            return value
        if r.set(f"lock:{key}", 1, nx=True, ex=10):  # one caller wins
            try:
                value = rebuild()
                r.set(key, value, ex=ttl)
                return value
            finally:
                r.delete(f"lock:{key}")
        time.sleep(wait)                              # the rest wait briefly
    raise TimeoutError(key)                           # or serve a fallback

Here r is a redis-py client. With this, 1,000 misses produce one query, and the other 999 requests wait about 50 ms per retry. Redis's SET documentation describes this pattern and its limits: a lock can expire while its holder is still working, and a plain DEL can then remove another client's lock, which is why the docs show a release that checks a random token first. For a cache, the worst case is an extra rebuild, which is fine. Where two holders would be a real problem, use a stronger scheme.

You rarely need to write this for HTTP responses, because proxies and CDNs coalesce requests already. Nginx's proxy_cache_lock lets one request fill a missing entry while the others wait (our Nginx proxy_cache guide covers it), Varnish coalesces automatically, Cloudflare holds duplicate misses at each data centre behind a cache lock, and CloudFront collapses simultaneous requests that share a cache key.

Facebook built the idea into memcache itself. Its NSDI 2013 paper describes leases: on a miss, the cache hands out a token to one client at most every 10 seconds per key and tells the others to wait briefly and retry. For a set of keys prone to thundering herds, the paper reports that leases cut the peak database query rate from 17,000 to 1,300 a second.

Probabilistic early refresh

Locks handle the miss once it happens. Early refresh avoids the miss altogether: requests arriving shortly before expiry occasionally rebuild the value, so a busy key is refreshed while the old copy is still being served.

The best-known version is XFetch, from a 2015 VLDB paper by Vattani, Chierichetti and Lowenstein. Each value is stored with delta, the time its last rebuild took. On every read, a request rebuilds early if:

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

random() is uniform between 0 and 1, so the logarithm is negative and the left side is now plus a random head start that scales with delta. beta defaults to 1; raise it to refresh earlier. Worked through, the chance that a single request triggers a refresh when it arrives g seconds before expiry is e^(−g ÷ (delta × beta)). With a 200 ms rebuild and beta = 1:

On a key read 5,000 times a second, some request almost certainly refreshes it a second or more before expiry, and the others keep reading the current copy. On a key read twice a minute, nobody wastes work. Slow rebuilds start earlier because delta is larger. XFetch needs no coordination between servers, which makes it a good partner for a lock rather than a replacement: the early refresh keeps hot keys from expiring, and the lock catches the misses that remain.

TTL jitter

Entries created together expire together. Warm 400 question keys at 9:55 a.m. with a ten-minute TTL and all 400 expire at 10:05, in the middle of the test. Add random jitter of ±10% (a TTL between 540 and 660 seconds) and the expiries spread over two minutes, about three keys a second instead of 400 at once.

Jitter does nothing for a single hot key, which still expires at one moment. It solves the "many keys" version of the problem. For planned events, go further: warm the cache before the event, as part of your exam-day scaling runbook, and give entries a TTL that outlasts the test window.

Serving stale while revalidating

Often the cheapest fix is to never make anyone wait: keep serving the old value while one request fetches the new one. Every layer has a version of this:

• HTTP: Cache-Control: max-age=60, stale-while-revalidate=30, from RFC 5861, lets browsers and CDNs serve a stale copy for 30 seconds while revalidating in the background. Cloudflare reports these requests as UPDATING.
  
  
• Nginx: proxy_cache_use_stale updating with proxy_cache_background_update on.
  
  
• Varnish: grace mode.
  
  
• Your application: store a soft expiry inside the cached value and give the Redis key a longer hard TTL, say twice as long. A request that finds the value past its soft expiry takes the lock, rebuilds, and meanwhile everyone else is served the old value.
  
  

Serving stale is a product decision as much as a technical one. A leaderboard 30 seconds old is fine. A fee that changed a minute ago may not be, so those keys get deleted on write, as described in our guide to cache invalidation.

Two more causes deserve a line each. Eviction can drop a hot key just as easily as expiry; the allkeys-lfu policy keeps frequently used keys longer (our guide to Redis eviction policies covers the options). And a cache server that restarts empty stampedes every key at once, so persistence or a warming script after restarts is worth having before a big event.

If you run a coaching institute rather than an engineering team, Upclass offers institutes an LMS and branded app that are ready to use.

Key takeaways

• A stampede is many simultaneous misses on one hot key; the rebuild slows under load, widening the miss window.
  
  
• Let exactly one request rebuild: Redis SET NX locks in the app, proxy_cache_lock in Nginx, request collapsing at the CDN.
  
  
• Refresh hot keys early and probabilistically (XFetch), so they rarely expire under load.
  
  
• Add ±10% TTL jitter to keys created together, and warm caches before known events.
  
  
• Serve stale while one request revalidates, wherever a few seconds of staleness is acceptable.
  
  

Frequently asked questions

What is cache stampede problem?

It is the overload that follows when a frequently read cache entry disappears and many requests miss it at the same moment. Each one goes to the database or backend to rebuild the same value, so a single expensive query suddenly runs hundreds or thousands of times at once. The rebuild slows under that load, more requests miss while it runs, and the database or application servers can tip into timeouts.

What is cache stampede protection?

Cache stampede protection is any technique that stops simultaneous misses from all reaching the backend. The main ones are a lock or request coalescing so only one request rebuilds the value, probabilistic early refresh so hot keys are renewed before they expire, random jitter on TTLs so related keys don't expire together, and serving stale data while one request revalidates. Most production systems combine two or three of these.

What is cache stampede in Redis?

With Redis as a cache, a stampede happens when a hot key expires, is evicted or vanishes in a restart, and many application servers miss at once and hit the database together. Redis itself usually copes; the database behind it doesn't. Guard hot keys with a SET key value NX EX lock so only one server rebuilds, refresh them early or serve stale values, jitter TTLs, and consider the allkeys-lfu eviction policy.