Cache Stampede

A cache stampede (also called thundering herd) happens when a popular cache entry expires and hundreds of concurrent requests all miss the cache simultaneously, all hitting the database at once. The database, designed to handle 100 QPS because the cache handles the other 9,900, suddenly receives 10,000 queries for the same key. It crashes, the cache never repopulates, and the stampede continues. This pattern has caused outages at Facebook, Reddit, and Twitter. The three main defenses are locking (only one request fetches, others wait), probabilistic early expiration, and stale-while-revalidate.

Why This Matters

Cache stampedes are among the most common causes of database overload in high-traffic systems. A single popular key expiring can trigger enough concurrent database queries to crash the backend. Reddit's front page is a famous example — the front page cache expires, thousands of requests hit the database, the database dies, and users see errors. Understanding stampede prevention is essential for any caching design in a system design interview.

The Building Blocks

• Mutex/Lock Pattern: When a cache miss occurs, the first request acquires a lock (Redis SETNX) and fetches from the database. Subsequent requests see the lock and wait or return stale data instead of hitting the database.
• Probabilistic Early Expiration: Each request has a small probability of refreshing the cache before it expires. As TTL approaches, the probability increases. Statistically, one request refreshes the cache before mass expiration.
• Stale-While-Revalidate: Serve the expired cache entry while asynchronously refreshing it in the background. Users get fast (possibly stale) responses, and the cache is eventually updated without a stampede.
• TTL Jitter: Add random variation to cache TTLs. Instead of all entries expiring at exactly 300s, expire at 270-330s. This prevents synchronized mass expiration that causes stampedes across many keys.
• External Refresh: A background job proactively refreshes popular cache entries before they expire. The cache never goes empty, so stampedes cannot occur. Requires knowing which keys are hot.

Under the Hood

The lock-based approach works like this: Request A arrives and finds the cache empty. It sets a Redis lock (SETNX "lock:product:123" with a 5-second TTL) and queries the database. Requests B through Z arrive, find the lock active, and either wait (spin-loop with backoff) or return a stale cached value. When Request A completes, it writes to the cache and releases the lock. Requests B-Z then read from the fresh cache.

Probabilistic early expiration (also called XFetch) uses the formula: should_refresh = (time_remaining / ttl) < random(). As the TTL approaches, the probability of refreshing increases. With 1000 requests per second and a 300-second TTL, about one request will trigger a refresh 5-10 seconds before expiration. The key insight: only one request refreshes, not all 1000.

Facebook's lease mechanism combines both: when a cache miss occurs, memcached issues a "lease" (a token) to the first requester. Other requesters are told to wait briefly. If the lease holder does not populate the cache within 10 seconds, the lease expires and another requester gets a new lease. This prevents both stampedes and stuck locks.

How Companies Actually Do This

Facebook pioneered the lease mechanism in their Memcache infrastructure. Their TAO layer uses lease-based stampede prevention for the social graph — profile data, friend lists, and news feed entries.

Reddit experienced front-page stampedes when the homepage cache expired. They implemented stale-while-revalidate so users always see cached content while the background refresh occurs.

Cloudflare uses request coalescing at the CDN edge. When multiple users request the same uncached resource, only one request goes to the origin. Others wait for that single response and are served from the edge cache.

Common Pitfalls

1. Using distributed locks without TTL — if the lock holder crashes, the lock is never released and no request can repopulate the cache
2. Setting identical TTLs across all cache entries — everything expires at the same time, causing a stampede for every key, not just hot ones
3. Not warming the cache after a cold start or deployment — the first traffic wave hits an empty cache and every request goes to the database

Interview Questions Worth Practicing

1. How would you prevent a cache stampede for a product page viewed 10,000 times per second?
2. What are the tradeoffs between lock-based and probabilistic stampede prevention?
3. How does Facebook's lease mechanism work, and why is it better than a simple mutex?

The Tradeoffs

• Freshness vs Availability: Stale-while-revalidate serves possibly outdated data to prevent database overload. If freshness is critical (pricing, inventory), you need lock-based refresh instead.
• Simplicity vs Robustness: Lock-based prevention is simple but introduces a single point of contention. Probabilistic approaches are more resilient but harder to tune and reason about.
• Proactive vs Reactive: Background refresh prevents stampedes entirely but requires knowing hot keys and wastes resources refreshing rarely-accessed data. Reactive approaches only refresh on demand.

How to Explain This in an Interview

Here is how I would explain Cache Stampede in a system design interview:

A cache stampede happens when a popular cache key expires and hundreds of requests simultaneously miss the cache and hit the database. I would prevent this with three techniques depending on the scenario. First, a Redis-based lock (SETNX with TTL) — the first request acquires the lock and fetches from the database, others wait or return stale data. Second, TTL jitter — instead of all keys expiring at exactly 5 minutes, I add random variation (270-330 seconds) to prevent synchronized expiration. Third, for the most critical keys (homepage, popular products), I use background refresh — a scheduled job repopulates the cache 30 seconds before expiration so it never goes empty. The key tradeoff is freshness vs availability: stale-while-revalidate is the safest default.

Related Topics

• Caching Strategies
• Cache Warming
• Rate Limiting
• CDN

Original DosiBridge notes for Cache Stampede

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Cache Stampede is to connect the concept to a read-heavy path where the cache can either protect the database or serve confusing stale data. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Freshness Window: For Cache Stampede, decide the freshness window before choosing tools; otherwise the design looks clean but fails when cache changes.
• Eviction Pressure: For Cache Stampede, decide the eviction pressure before choosing tools; otherwise the design looks clean but fails when stampede changes.
• Hot Key Behavior: For Cache Stampede, decide the hot-key behavior before choosing tools; otherwise the design looks clean but fails when cache changes.
• Cache Stampede: For Cache Stampede, decide the cache stampede before choosing tools; otherwise the design looks clean but fails when stampede changes.
• Invalidation Owner: For Cache Stampede, decide the invalidation owner before choosing tools; otherwise the design looks clean but fails when cache changes.

Production review question

If a team adopts Cache Stampede, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track cache-stampede health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Cache Stampede, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.