Cache Stampede — How to Prevent Thundering Herd on Cache Expiry

Introduction

Why This Matters

Cache stampede — also called thundering herd — is one of the most dangerous failure modes in high-traffic backend systems. The moment a popular cache key expires, every concurrent request that misses the cache races to recompute the same expensive value and write it back. The result is a sudden spike of database load that can cascade into a full outage.

Systems serving millions of requests per day are especially vulnerable: a single expired key can trigger hundreds of identical queries within milliseconds, overwhelming a database that was comfortably idle moments before.

What is Cache Stampede?

A cache stampede happens when:

A cached key expires (TTL reached)
Many requests arrive simultaneously before the key is repopulated
All of them find a cache miss and independently query the database
The database is overwhelmed by N identical expensive queries

Timeline:
T=0    → Key expires
T=1ms  → Request 1 misses cache, queries DB
T=2ms  → Request 2 misses cache, queries DB
T=3ms  → Request 3 misses cache, queries DB
...
T=10ms → 500 identical DB queries running concurrently
T=15ms → DB CPU hits 100%, latency spikes, on-call fires

Solution 1: Probabilistic Early Expiry (XFetch Algorithm)

The XFetch algorithm adds randomness to cache reads so some requests refresh the cache before it expires:

import Redis from 'ioredis';
 
const redis = new Redis();
 
interface CacheEntry<T> {
  value: T;
  delta: number;  // time taken to compute (seconds)
  expiry: number; // unix timestamp when it expires
}
 
async function xfetch<T>(
  key: string,
  ttl: number,
  beta: number,
  compute: () => Promise<T>
): Promise<T> {
  const raw = await redis.get(key);
 
  if (raw) {
    const entry: CacheEntry<T> = JSON.parse(raw);
    const now = Date.now() / 1000;
    // Probabilistic early expiry
    const earlyExpiry =
      entry.expiry - entry.delta * beta * Math.log(Math.random());
 
    if (now < earlyExpiry) {
      return entry.value;
    }
  }
 
  // Recompute
  const start = Date.now();
  const value = await compute();
  const delta = (Date.now() - start) / 1000;
 
  const entry: CacheEntry<T> = {
    value,
    delta,
    expiry: Date.now() / 1000 + ttl,
  };
 
  await redis.setex(key, ttl, JSON.stringify(entry));
  return value;
}
 
// Usage
const result = await xfetch(
  'product:123:recommendations',
  3600,
  1.0, // beta: higher = more aggressive early refresh
  () => computeRecommendations(123)
);

Solution 2: Mutex Lock (Single-Flight Pattern)

Use a distributed lock so only one process recomputes while others wait:

async function getWithMutex<T>(
  key: string,
  ttl: number,
  compute: () => Promise<T>,
  lockTtl = 5000
): Promise<T> {
  // Fast path: cache hit
  const cached = await redis.get(key);
  if (cached) return JSON.parse(cached);
 
  const lockKey = `lock:${key}`;
  const lockToken = `${Date.now()}-${Math.random()}`;
 
  // Try to acquire lock
  const acquired = await redis.set(lockKey, lockToken, 'PX', lockTtl, 'NX');
 
  if (acquired) {
    try {
      // Double-check after acquiring lock
      const recheck = await redis.get(key);
      if (recheck) return JSON.parse(recheck);
 
      const value = await compute();
      await redis.setex(key, ttl, JSON.stringify(value));
      return value;
    } finally {
      // Release only if we still own it
      const current = await redis.get(lockKey);
      if (current === lockToken) {
        await redis.del(lockKey);
      }
    }
  } else {
    // Wait and retry — another process is computing
    await new Promise((r) => setTimeout(r, 100));
    return getWithMutex(key, ttl, compute, lockTtl);
  }
}

Solution 3: Stale-While-Revalidate with Background Refresh

Serve stale data immediately while refreshing in the background:

interface StaleEntry<T> {
  value: T;
  freshUntil: number; // timestamp ms
  staleUntil: number; // timestamp ms (grace period)
}
 
async function staleWhileRevalidate<T>(
  key: string,
  freshTtl: number,  // e.g., 60 seconds
  staleTtl: number,  // e.g., 300 seconds grace
  compute: () => Promise<T>
): Promise<T> {
  const raw = await redis.get(key);
  const now = Date.now();
 
  if (raw) {
    const entry: StaleEntry<T> = JSON.parse(raw);
 
    if (now < entry.freshUntil) {
      return entry.value; // fresh — return immediately
    }
 
    if (now < entry.staleUntil) {
      // Stale — serve immediately, refresh in background
      refreshInBackground(key, freshTtl, staleTtl, compute);
      return entry.value;
    }
  }
 
  // Fully expired — compute synchronously
  return computeAndStore(key, freshTtl, staleTtl, compute);
}
 
async function refreshInBackground<T>(
  key: string,
  freshTtl: number,
  staleTtl: number,
  compute: () => Promise<T>
): Promise<void> {
  const refreshLock = `refresh:${key}`;
  const acquired = await redis.set(refreshLock, '1', 'PX', 10000, 'NX');
  if (!acquired) return; // another process is already refreshing
 
  try {
    await computeAndStore(key, freshTtl, staleTtl, compute);
  } finally {
    await redis.del(refreshLock);
  }
}

Solution 4: TTL Jitter

The simplest fix — add randomness to TTL so keys never all expire simultaneously:

function ttlWithJitter(baseTtl: number, jitterPct = 0.15): number {
  const jitter = baseTtl * jitterPct * Math.random();
  return Math.floor(baseTtl + jitter);
}
 
// Before (dangerous — all keys expire at the same time):
await redis.setex(key, 3600, value);
 
// After (safe — expiry spread over 3600–4140 seconds):
await redis.setex(key, ttlWithJitter(3600), value);

This prevents synchronized cache invalidation when many keys are set in bulk — for example after a cold start or a full cache flush.

Common Mistakes

Not double-checking after acquiring a lock. Always re-read the cache after acquiring the mutex. Another process may have already computed and stored the value between your cache miss and lock acquisition.

No try/finally on lock release. An unhandled exception that skips lock release leaves all waiting requests spinning until the lock TTL expires.

Beta too low in XFetch. A beta of 0 makes XFetch behave like a plain TTL with no early refresh. Start with beta = 1.0 and tune upward.

Identical TTLs across related keys. If you cache 1000 product pages with TTL 3600 and set them all at startup, every key expires simultaneously one hour later.

Recursive retry without backoff. In the mutex approach, naive recursive retry without delay creates a retry storm while the lock holder is computing.

Best Practices

Use XFetch for compute-heavy values where near-expiry refreshes are acceptable
Use mutex locking when stale data is never acceptable and strict consistency is required
Use stale-while-revalidate for user-facing data where low latency matters more than perfect freshness
Always add 10–20% TTL jitter when setting keys in bulk
Monitor cache_miss_rate and alert on sudden spikes — they precede stampedes
Set lockTtl slightly longer than worst-case compute time to avoid premature expiry

Key Takeaways

Cache stampede occurs when an expired key causes N concurrent requests to simultaneously hit the database, potentially cascading into full system failure.
The XFetch algorithm adds probabilistic early expiry so a fraction of requests refresh the cache before it actually expires, spreading the load naturally.
Mutex locking (single-flight pattern) uses Redis SET NX to ensure only one process recomputes a value while all others wait for the result.
Stale-while-revalidate serves slightly stale data instantly and triggers a background refresh, keeping latency low without sacrificing freshness.
TTL jitter (randomizing expiry by 10–20%) prevents synchronized cache invalidation when many keys are set at the same time.
Always use try/finally when holding distributed locks to guarantee release even when exceptions occur.
Monitor cache miss rate as a leading indicator — a sudden spike typically signals an impending stampede or recent cache flush.
Combining strategies (jitter at write + XFetch at read + background refresh) provides defense-in-depth for critical high-traffic cache keys.

Introduction#

Why This Matters#

What is Cache Stampede?#

Solution 1: Probabilistic Early Expiry (XFetch Algorithm)#

Solution 2: Mutex Lock (Single-Flight Pattern)#

Solution 3: Stale-While-Revalidate with Background Refresh#

Solution 4: TTL Jitter#

Common Mistakes#

Best Practices#

Key Takeaways#

Related reading