The Thundering Herd on Cache Invalidation: Stale-While-Revalidate vs Probabilistic Early Expiration (XFetch)

When a key holding a heavily requested item—like a trending product page or top news feed—expires in Redis or Memcached, every incoming request at that exact millisecond experiences a cache miss. In a system handling thousands of queries per second, hundreds or thousands of worker threads simultaneously attempt to compute or fetch the missing value from the primary database. This is the classic cache stampede or thundering herd problem.

The Anatomy of a Thundering Herd Crash

In a standard naive caching implementation, the flow looks like this:

val = redis.get(key)
if val is None:
    val = db.query_expensive_data() # Takes 300ms
    redis.setex(key, 60, val)
return val

If key homepage_feed expires at 14:00:00.000 and the server receives 500 requests per second, all 500 threads check Redis, receive None, and issue 500 identical complex SQL queries to the database. The database CPU spikes to 100%, query latency inflates from 300ms to 15 seconds, and worker threads exhaust the connection pool, creating a total outage.

Strategy 1: Distributed Mutex Locking (Single-Rebuilder)

The first common attempt to fix this is introducing a distributed lock (e.g. SET key:lock uuid NX PX 5000). Only the thread that successfully acquires the lock executes the expensive database query, while all other threads sleep briefly and retry fetching from Redis.

val = redis.get(key)
if val is None:
    if redis.set("lock:" + key, my_id, nx=True, px=5000):
        try:
            val = db.query_expensive_data()
            redis.setex(key, 60, val)
        finally:
            release_lock("lock:" + key, my_id)
    else:
        time.sleep(0.05)
        return get_with_lock(key) # Retry read
return val

Pros: Guarantees exactly one database query per cache expiration.
Cons: Waiting threads experience added latency spikes equal to the database query execution time plus retry polling delays. If the locking worker crashes before releasing the lock, waiting threads hang until the lock TTL expires.

Strategy 2: Background Stale-While-Revalidate (SWR)

Instead of letting a key expire hard, the data payload includes a stale_at timestamp alongside a longer TTL. When a request reads data past stale_at but before full TTL expiration, it returns the stale value instantly to the user while asynchronously enqueueing a background worker to re-generate the fresh cache entry.

payload = redis.get(key) # { data: {...}, stale_at: 1720000000 }
if payload is None:
    return fetch_blocking_and_cache(key)

if now() > payload.stale_at:
    if redis.set("revalidate_lock:" + key, "1", nx=True, ex=10):
        async_queue.enqueue(revalidate_task, key)

return payload.data # Instant response even when stale

Pros: Zero user-facing latency spikes; response time remains flat.
Cons: Requires background task queues (Celery/BullMQ) and consumes memory by holding stale data longer.

Strategy 3: Probabilistic Early Expiration (XFetch Algorithm)

Formulated by Vattani et al. in 2015, the XFetch algorithm uses probability to make worker threads trigger cache re-computation before the key actually expires, scaling with current request load.

The probability of recomputing early increases as the current time approaches expiration, weighted by the computation cost ($delta$) and a tuning constant ($eta > 0$):

$$ ext{Recompute if } -Delta cdot eta cdot ln( ext{rand}()) > ext{ttl_remaining}$$

import math, random, time

def xfetch_read(redis, key, beta=1.0):
    val, delta, ttl_remaining = redis.get_with_ttl_and_compute_cost(key)
    
    if val is None or (-delta * beta * math.log(random.random()) > ttl_remaining):
        start = time.time()
        new_val = db.query_expensive_data()
        compute_delta = time.time() - start
        
        redis.set_with_metadata(key, new_val, ttl=60, compute_delta=compute_delta)
        return new_val
        
    return val

Under heavy traffic, the random log function ensures that exactly one worker thread probabilistically decides to recompute the cache slightly before expiration while the key is still valid. The new entry overwrites the old key seamlessly, so the cache never drops to zero or misses hard.

Comparison Summary

• Mutex Locking: Best for write-heavy or low-traffic systems where stale data is strictly unacceptable.
• Stale-While-Revalidate: Best for high-traffic web applications (e.g., e-commerce, news feeds) where serving slightly stale content for a few seconds is completely fine.
• XFetch: Best for high-concurrency microservices with expensive computations where you want zero background queue overhead and optimal cache hit ratios.