Skip to content

Cache Stampede Protection

1. Decision

Prevent Cache Stampedes (Thundering Herd problem where concurrent requests hit an expired cache key simultaneously and overwhelm the database) by implementing Mutex Locking (Single Flight pattern), Probabilistic Early Expiration (XFetch algorithm), or Background Cache Warming.

2. 30-Second Answer

A Cache Stampede (or Thundering Herd / Cache Breakdown) occurs when a popular, high-traffic cache key expires or is invalidated. Hundreds or thousands of concurrent application threads detect the cache miss at the exact same millisecond, and all attempt to compute the expensive query against the backend database simultaneously. This sudden traffic spike exhausts database connection pools, spikes CPU to 100%, and causes cascading system failures. Mitigate Cache Stampedes using three primary patterns: (1) Mutex Locking / Single Flight (only one thread computes DB query while others wait), (2) Probabilistic Early Expiration / XFetch (asynchronously refresh key before TTL hits 0), or (3) Background Cache Warming (cron/worker updates cache independent of user requests).

3. Decision Matrix

Option Best For Avoid When Latency Scalability Consistency Operational Complexity
Mutex Locking (Single Flight / Distributed Lock) High-cost database queries, low-to-medium latency tolerance Ultra-strict sub-millisecond SLAs where waiting threads cannot afford lock latency Low for winner thread; Brief wait latency for loser threads Protects DB completely (Only 1 query hits DB) Strong (Single fresh DB compute) Medium
Probabilistic Early Expiration (XFetch Algorithm) High-traffic read-heavy keys, seamless user experience without lock waiting Low-traffic keys where probabilistic calculation overhead is wasteful Sub-millisecond (Zero client wait time) High (Async background refresh) High (Cache stays continuously warm) Medium
Background Worker Cache Warming Predictable static datasets, homepages, top-category product listings Dynamic long-tail user-specific keys with millions of unpredictable combinations Sub-millisecond (Reads hit pre-warmed cache) High High (Background job controls freshness) Medium

4. Selection Rules

Requirement Best Choice Rationale / Example
Ensure Only 1 Thread Queries DB on Cache Miss Mutex Lock (Single Flight) First thread acquires lock; remaining N-1 threads wait for lock release & read updated cache
Zero Client Latency Penalty on Expiration Probabilistic Early Refresh (XFetch) Asynchronously recompute cache in background before key TTL expires
Protect Database from Heavy Aggregations Background Cache Warming Scheduled worker recomputes heavy analytics every 5 mins independent of HTTP traffic
Go / Microservice Single Flight Pattern golang.org/x/sync/singleflight Deduplicates duplicate in-flight function calls across local goroutines
Serve Stale Content During DB Refresh Stale-While-Revalidate Return stale cache value instantly while triggering background DB update job

5. Tradeoffs

  1. Mutex Locking (Single Flight) vs Thundering Herd
  2. Gain: Reduces 10,000 DB queries down to exactly 1 DB query.
  3. Lose: Threads waiting for the lock experience increased latency; if lock holder crashes, waiters time out.
  4. Probabilistic Early Expiration (XFetch) vs Fixed TTL
  5. Gain: Eliminates cache misses entirely for active hot keys; zero client wait time.
  6. Lose: Additional background write traffic; requires tuning probability parameters (\(\beta\)).
  7. Background Worker Cache Warming vs On-Demand Lazy Loading
  8. Gain: Cache is always warm; zero database load spikes from user requests.
  9. Lose: Wastes compute and memory warming keys that may never be read by users.
  10. Stale-While-Revalidate vs Strict Consistency
  11. Gain: Instant sub-millisecond response latency even during cache refreshes.
  12. Lose: Clients temporarily observe slightly outdated data while background refresh completes.
  13. Distributed Lock (Redis Redlock) vs In-Process Single Flight
  14. Gain (Distributed Lock): Collapses DB queries across all application server nodes globally.
  15. Lose (Distributed Lock): Network overhead acquiring/releasing distributed locks in Redis.

6. Interview Counter Questions

  1. What is the mathematical formula behind the XFetch Probabilistic Early Expiration algorithm?
  2. How does Go's singleflight package work internally to prevent cache stampedes?
  3. How do you implement Mutex Locking using Redis SET key value NX PX timeout?
  4. What happens if the worker thread holding the Mutex lock crashes while querying the database?
  5. What is the difference between Cache Stampede, Cache Breakdown, and Cache Avalanche?
  6. How does Stale-While-Revalidate HTTP directive solve cache stampedes at the CDN layer?
  7. Why is setting a TTL fallback essential when using Mutex locks for cache stampede protection?
  8. How do you combine Local In-Memory Caching (L1) and Single Flight to protect a Distributed Cache?
  9. When is Background Cache Warming an anti-pattern?
  10. How do you handle cache stampedes for user-personalized dashboards?

7. Gold Standard Answers

  1. XFetch evaluates: \(-\beta \cdot \delta \cdot \log(\text{rand}()) > \text{TTL} - \text{expiry}\). If true, the read request triggers an asynchronous background recomputation before the key actually expires, where \(\delta\) is computation time and \(\beta > 0\) is aggressiveness.
  2. singleflight uses a mutex map tracking active in-flight request keys. If Call A for key1 is active, Call B blocks and registers on Call A's channel. When Call A finishes, it broadcasts the result to all waiters, executing the DB query once.
  3. SET lock:key rand_token NX PX 5000. If acquired, query DB, update cache, and release lock via Lua script verifying rand_token. If lock fails, sleep 50ms and retry reading cache.
  4. Set a short lock TTL (e.g., 5 seconds). If the worker crashes, the lock automatically expires after 5 seconds, allowing another waiting thread to acquire the lock and complete the DB refresh.
  5. Cache Stampede / Breakdown = Concurrent reads slam DB when 1 hot key expires. Cache Avalanche = Millions of keys expire at the same time. Cache Penetration = Queries for non-existent keys bypass cache to hit DB.
  6. stale-while-revalidate instructs CDN/browser to immediately return the stale cached asset while asynchronously triggering a single background fetch to origin to update the cache.
  7. Without a lock TTL, a crashed thread leaves a permanent deadlock lock key, causing all future client requests to block indefinitely and fail.
  8. Use L1 in-process singleflight first to collapse requests on the local application node, then use a Redis distributed lock to collapse requests across nodes, ensuring exactly 1 DB query globally.
  9. Anti-pattern for long-tail datasets (millions of obscure items). Pre-warming 10 million products when only 1,000 are daily active wastes memory and CPU. Use lazy loading with Mutex locks instead.
  10. Personalized dashboards cannot be pre-warmed easily. Use singleflight per user ID (lock:user:123) combined with Stale-While-Revalidate to return stale dashboard metrics while updating in background.

8. Common Mistakes

  • Allowing thousands of concurrent requests to hit the database on a cache miss without any locking or deduplication.
  • Implementing Mutex locks without setting a lock TTL, causing permanent deadlocks when worker threads crash.
  • Using DEL to release a lock without verifying the random token payload, accidentally releasing another thread's lock.
  • Pre-warming entire long-tail database datasets in background cron jobs, exhausting RAM and compute.
  • Confusing Cache Stampede (1 hot key expired) with Cache Penetration (non-existent key queried repeatedly).

9. Keywords

Cache Stampede, Thundering Herd, Cache Breakdown, Mutex Lock, Single Flight, XFetch Algorithm, Probabilistic Early Expiration, Stale-While-Revalidate, Background Cache Warming, Redlock, SET NX PX, Deadlock.

10. Cheat Sheet

  • Core Problem: Hot key expires \(\rightarrow\) 10,000 requests miss cache simultaneously \(\rightarrow\) DB crashes from Thundering Herd.
  • Solution 1: Mutex Lock (Single Flight): 1st request acquires lock and queries DB; remaining 9,999 requests wait and read updated cache.
  • Solution 2: XFetch (Probabilistic Expiration): Asynchronously refresh cache in background before TTL hits 0 based on read probability.
  • Solution 3: Stale-While-Revalidate: Return stale cache value immediately to client while updating cache asynchronously in background.
  • Lock Safety Rule: Always set a TTL (e.g., 5s) on locks and release via Lua script checking random token.
  • Go Helper: Use golang.org/x/sync/singleflight to collapse duplicate in-flight DB calls in memory cleanly.

11. Related Decisions