Skip to content

Cache Stampede (Thundering Herd)

1. What is it? (2-3 lines)

A Cache Stampede (or Thundering Herd / Dogpiling) occurs when a hot, high-traffic cache key expires or is invalidated, causing thousands of concurrent read requests to simultaneously miss the cache and overwhelm the underlying database with identical compute-heavy queries.

2. Why does it exist?

In high-throughput microservices (e.g. 50,000 QPS on a trending news item), when a cache key expires, every incoming concurrent thread reads cache.get() == null in the same millisecond. Without coordination, all 50,000 threads execute expensive SQL joins simultaneously, causing CPU spikes, connection pool exhaustion, and database collapse.

3. Where is it used?

  • High-Traffic Web Systems: Breaking news homepages, e-commerce hot product sales, live sports scoreboards.
  • Distributed Caching Libraries: Redis (Redlock/Singleflight), Memcached (XFetch algorithm), Resilience4j / Guava Cache (LoadingCache).

4. How does it work? (simple flow)

  1. Key Expiration: Hot cache key product:100 expires at timestamp \(T\).
  2. Concurrent Cache Misses: 10,000 application worker threads hit Redis at \(T+1\text{ms}\); all receive cache miss.
  3. Database Flood: All 10,000 threads fire expensive DB queries to compute product:100.
  4. Cascading Failure: DB CPU hits 100%; DB connection pool exhausts; HTTP API requests time out.

5. Solutions & Mitigations

  • Singleflight / Distributed Locking: Only 1 worker thread acquires a lock/mutex to recompute the key; remaining 9,999 threads block/wait for the lock to release and read the updated cache value.
  • Probabilistic Early Expiration (XFetch Algorithm): As TTL nears expiration, requests probabilistically recompute the cache value early before hard expiration: currentTime - (beta * delta * log(rand())) > expiry.
  • Background Async Refresh: A background worker thread periodically refreshes hot cache keys before their TTL expires (Soft TTL / Hard TTL pattern).

6. Advantages & Limitations of Solutions

  • Singleflight Lock: Completely eliminates DB stampedes (\(1\) query execution); but adds minor thread wait latency for blocking callers.
  • Probabilistic Early Expiration (XFetch): Zero thread blocking/locking overhead; requires tuning the beta randomness multiplier.

7. Common interview questions (10)

  1. What is the difference between Cache Stampede, Cache Avalanche, and Cache Penetration?
  2. How does Go's singleflight package or Java's LoadingCache eliminate Cache Stampedes?
  3. Explain the math and mechanics behind the XFetch probabilistic early expiration algorithm.
  4. How do Distributed Locks (Redis SET NX) prevent Cache Stampedes across multiple application nodes?
  5. What is the Soft TTL vs Hard TTL pattern and how does it guarantee zero cache misses for hot keys?
  6. How does Cache Warming prevent stampedes during scheduled deployment rollouts?
  7. What happens if the single thread rebuilding a hot cache key crashes midway?
  8. How does Mutex locking for cache rebuilds interact with request timeout SLAs?
  9. When should you use Async Background Re-computation instead of Mutex locks?
  10. How do CDNs (Cloudflare / Fastway) prevent cache stampedes at the edge (Origin Shielding / Stale-While-Revalidate)?

8. Common misconceptions

  • Misconception: Setting long TTLs solves Cache Stampedes. Fact: Long TTL keys still expire eventually or get invalidated on data updates, triggering a stampede when invalidation occurs.
  • Misconception: Increasing database connection pool size solves stampedes. Fact: More DB connections accelerate CPU exhaustion and DB crash during a stampede.

10. 30-second cheat sheet

  • Problem: 1 Hot Key expires \(\implies\) 10,000 concurrent threads hit DB simultaneously.
  • Solution 1 (Singleflight / Lock): 1 thread rebuilds cache; 9,999 threads wait.
  • Solution 2 (XFetch): Probabilistically refresh key in background before hard TTL expires.
  • Solution 3 (Stale-While-Revalidate): Serve stale cached data immediately while 1 async worker refreshes cache.