The Cache Stampede: when your safety net becomes the avalanche
A 2-second TTL expiry on a popular key. Fifty million users. What looks like a caching bug is actually a fundamental concurrency problem, and most teams discover it only when their database is already on fire.
This is called a cache stampede, also known as a thundering herd problem, or a dogpile effect. And it is one of the most under-appreciated failure modes in high-traffic systems.
"Designing distributed locking mechanisms to prevent that is a level of scale 99% of startups will never face."
He's right about the scale. But he's underselling how often this pattern appears in disguise. Let's break it down completely.
What actually happens during a stampede
Consider a homepage feed endpoint. You cache the result in Redis with a TTL of 60 seconds. At any given moment, 50,000 users per second hit that endpoint. While the cache is warm, Redis serves them all instantly, your database sees essentially zero traffic for this query.
Then the TTL expires.
t = 0.000s Cache key expires
t = 0.001s Thread A: cache MISS → begins DB query (slow)
t = 0.001s Thread B: cache MISS → begins DB query (slow)
t = 0.001s Thread C: cache MISS → begins DB query (slow)
...
t = 0.001s Thread N: cache MISS → begins DB query (slow)
(N = all concurrent users at that instant)
DB receives: O(concurrent_users) identical queries
DB response time: 200ms → 14,000ms
DB CPU: 12% → 100%
Cache repopulated: ✓ (by whichever thread finishes first)
Damage already done: ✓
The database eventually responds. One thread writes the result back to cache. The other N-1 threads get their results too, but they've already done the damage. Latency has spiked. Connection pools are exhausted. Downstream services that depend on yours start timing out.
This is the thundering herd: the moment the barn door opens, every animal runs through it at once.
Why standard TTLs make this worse
Here's the trap most engineers don't see. If your cache TTL is 60 seconds and you have high traffic, the stampede happens every single minute on a rotating schedule, one for each popular key as its TTL expires. In a system with thousands of popular keys, you're effectively scheduling regular mini-outages.
The naive fix is "just use a longer TTL." This works until you need to serve fresh data. Staleness and stampede resistance are in direct tension.
The three real solutions
1. Probabilistic Early Expiry (XFetch algorithm)
Instead of letting the cache expire at TTL and letting all threads discover the miss simultaneously, you proactively recompute the value before it expires. But you don't do it for every request, you do it probabilistically, with higher probability as the TTL countdown gets closer to zero.
def fetch_with_xfetch(key, recompute_fn, ttl, beta=1.0):
"""
XFetch: probabilistic early cache expiry.
beta > 1 causes earlier recomputation (less stampede risk).
beta < 1 recomputes later (more stale-data risk).
"""
value, delta, expiry = cache.get_with_metadata(key)
if value is None:
# Full miss — compute and cache immediately
value = recompute_fn()
cache.set(key, value, ttl=ttl, delta=time.now())
return value
# time_to_live = how many seconds left on this key
time_to_live = expiry - time.now()
# The probability of early refresh increases as TTL approaches 0
# and as the last recomputation took longer (high delta)
if -beta * delta * math.log(random.random()) >= time_to_live:
# This thread voluntarily refreshes early
value = recompute_fn()
cache.set(key, value, ttl=ttl, delta=time.now())
return valueKey insightThe XFetch algorithm doesn't eliminate stampedes, it makes them statistically impossible at scale by distributing the recomputation load across time, proportional to how expensive the recomputation is (the delta parameter).
2. Mutex / distributed lock on cold key
When a cache miss is detected, only one thread should be allowed to run the expensive database query. All other threads either wait or serve a stale value while the refresh is in progress.
async def get_with_mutex(key, recompute_fn, ttl):
value = await cache.get(key)
if value is not None:
return value
lock_key = f"lock:{key}"
lock_acquired = await cache.set(
lock_key,
"1",
nx=True, # Only set if not exists (atomic)
ex=10 # Lock expires in 10s (avoid deadlock)
)
if lock_acquired:
try:
value = await recompute_fn()
await cache.set(key, value, ex=ttl)
return value
finally:
await cache.delete(lock_key)
else:
# Another thread has the lock — wait briefly, then retry
# In production: use exponential backoff or serve stale
await asyncio.sleep(0.05)
return await get_with_mutex(key, recompute_fn, ttl)The downside: if the holding thread crashes after acquiring the lock but before populating the cache, all other threads wait for the lock TTL (10 seconds). This is why the lock expiry must be set carefully.
3. Background refresh with stale-while-revalidate
This is the most production-friendly pattern for read-heavy workloads. You serve the stale cached value immediately to every request, and simultaneously trigger a background job to refresh the value.
STALE_TTL = 3600 # Keep stale value available for 1 hour
FRESH_TTL = 60 # Mark as "fresh" for 60 seconds
async def get_with_background_refresh(key, recompute_fn):
metadata = await cache.get_with_ttl(key)
if metadata is None:
# True cold miss — must wait for fresh data
value = await recompute_fn()
await cache.set_with_dual_ttl(key, value, FRESH_TTL, STALE_TTL)
return value
value, remaining_ttl = metadata
if remaining_ttl < STALE_TTL - FRESH_TTL:
# Value is stale — serve it, but schedule background refresh
asyncio.create_task(refresh_in_background(key, recompute_fn))
return value # Always returns immediatelyHTTP caches expose this natively via the Cache-Control: stale-while-revalidate=N header, CDNs like Fastly and Cloudflare implement it out of the box.
Which pattern to use when
Decision framework
High read volume, can tolerate briefly stale data: stale-while-revalidate is your default choice. Zero stampede risk, zero wait time.
Must serve fresh data, expensive recomputation: mutex lock + serve stale on lock-wait.
Unpredictable traffic bursts (viral content, flash sales): XFetch probabilistic expiry, combined with request coalescing at the application layer.
All of the above: These patterns compose. Use SWR as the outer layer, mutex as the inner guard on true cold misses.
The operational angle: what to monitor
Cache stampedes show up in metrics before they show up in alerts, if you know where to look:
Cache hit rate per key, not just aggregate. An aggregate hit rate of 95% masks a popular key that's getting 0% hits every 60 seconds.
DB connection pool wait time. A stampede instantly saturates connection pools. This appears as
pool_wait_msspikes, not as DB query slowness.P99 latency divergence. During a stampede, p50 stays flat (most requests hit cache) but p99 explodes (unlucky requests hit cold cache). Track both.
A cache hit rate dashboard showing 99.7% can hide a stampede that's simultaneously melting your database. The aggregate lies. Drill to per-key, per-second granularity.
What Twitter, Facebook, and Cloudflare actually do
At extreme scale, the patterns above aren't enough. Facebook's Memcache paper (2013) describes lease tokens: when a client gets a cache miss, instead of immediately querying the database, it receives a lease token. The lease tells it: you're allowed to populate this key. All other clients who miss on the same key wait until the leaseholder populates it.
Cloudflare's edge cache uses a variant they call request coalescing: all requests for the same uncached resource within a short time window are collapsed into a single origin request. The response is fanned back out to all waiting clients simultaneously. This is transparent to the application layer.
The common thread: the database should never see O(concurrent_users) queries for the same resource. The answer is always some form of serialization or early refresh, applied at the right layer.