Cache Stampede: Preventing Thundering Herds on Cache Expiry

In this tutorial, you will learn about Cache Stampede: Preventing Thundering Herds on Cache Expiry. We cover key concepts, practical examples, and best practices to help you master this topic.

A cache stampede occurs when a popular cache key expires and many concurrent requests simultaneously miss the cache, all hitting the origin database or service at once. This thundering herd can overwhelm the backend, causing cascading failures and extended downtime.

flowchart LR
    subgraph Without Protection
        A1[Request 1] --> DB[(Database)]
        A2[Request 2] --> DB
        A3[Request 1000] --> DB
    end
    subgraph With Protection
        B1[Request 1] -->|Lock| C[Single DB Query]
        B2[Request 2] -->|Wait for Lock| C
        B3[Request 1000] -->|Wait for Lock| C
    end

What You'll Learn

• How cache stampedes occur and their impact on system stability
• Prevention techniques: request coalescing, probabilistic early expiration, jittered TTLs
• Lock-based and lock-free approaches to stampede prevention

Why It Matters

A cache stampede can take down a database or external API in seconds. Popular keys that expire simultaneously during traffic spikes are the most common cause of cascading failures in cache-heavy systems.

Real-World Use

A video streaming platform's homepage cache expired at the top of the hour when a popular show was released. Millions of concurrent cache misses hit the origin API simultaneously, overwhelming it. Adding probabilistic early expiration prevented recurrence.

Stampede Prevention Techniques

Request Coalescing (Dedup)

class StampedeProtector {
  constructor() {
    this.inFlight = new Map();
  }

  async execute(key, loader) {
    const cached = await cache.get(key);
    if (cached) return JSON.parse(cached);

    const existing = this.inFlight.get(key);
    if (existing) return existing;

    const promise = loader()
      .then(async (data) => {
        await cache.setEx(key, 3600, JSON.stringify(data));
        return data;
      })
      .finally(() => this.inFlight.delete(key));

    this.inFlight.set(key, promise);
    return promise;
  }
}

Expected output:

1000 concurrent requests for key 'homepage': only 1 executes loader, the other 999 wait for the same promise and share the result.

Probabilistic Early Expiration (XFetch)

function shouldRecompute(ttlMs, elapsedMs, beta = 1) {
  const remaining = ttlMs - elapsedMs;
  const probability = Math.max(0, 1 - remaining / (beta * ttlMs));
  return Math.random() < probability;
}

async function getWithXFetch(key, loader, ttlMs = 60000) {
  const entry = await cache.get(key);
  if (!entry) {
    const data = await loader();
    await cache.setEx(key, Math.ceil(ttlMs / 1000), JSON.stringify(data));
    return data;
  }

  const parsed = JSON.parse(entry);
  const age = Date.now() - (parsed._cachedAt || Date.now());

  if (shouldRecompute(ttlMs, age)) {
    loader().then(async (data) => {
      await cache.setEx(key, Math.ceil(ttlMs / 1000), JSON.stringify({
        ...data,
        _cachedAt: Date.now()
      }));
    }).catch(() => {});
  }

  return parsed;
}

Expected output:

As the cache entry ages, the probability of triggering early recomputation increases. Requests probabilistically refresh the cache before expiry, preventing mass simultaneous misses.

Jittered TTLs

function jitteredTTL(baseTTL, jitterPercent = 0.1) {
  const jitter = baseTTL * jitterPercent * (Math.random() * 2 - 1);
  return Math.floor(baseTTL + jitter);
}

async function getWithJitter(key, loader) {
  const cached = await cache.get(key);
  if (cached) return JSON.parse(cached);

  const data = await loader();
  const ttl = jitteredTTL(3600, 0.2);
  await cache.setEx(key, ttl, JSON.stringify(data));
  return data;
}

Expected output:

Entries with a base TTL of 3600s are cached with TTLs between 2880-4320s. Expiry times are spread out, preventing simultaneous mass expiry.

Common Mistakes

• Only implementing request coalescing without early recomputation — coalescing helps only for truly concurrent requests, not for requests arriving over a short window.
• Using a single lock or mutex that becomes a bottleneck for many different keys.
• Not adding jitter when initializing caches on service startup — all instances cache the same keys at the same time, leading to synchronized expiry.
• Implementing early recomputation without error handling — a background refresh failure should not block the current request.
• Setting jitter too high, causing some entries to expire too early and reducing cache hit rate.

Practice Questions

1. What is a cache stampede and how does it happen?
2. How does request coalescing differ from probabilistic early expiration?
3. Why is jittered TTL better than fixed TTL for preventing stampedes?
4. What is the beta parameter in XFetch?
5. How do cache stampedes affect downstream services beyond the database?

Challenge

Design a stampede prevention system for a news website's homepage API that receives 50,000 requests/second. The homepage content is generated from 10 different data sources and takes 2 seconds to compute. Use a combination of jittered TTL, request coalescing, and probabilistic early expiration.

FAQ

Mini Project

Extend the blog API with cache stampede protection. Implement request coalescing for hot keys, probabilistic early expiration for frequently read data, and jittered TTLs for all cache entries. Write a simulation that starts 100 concurrent requests for the same expired key and verifies only one DB query executes.

What's Next

Continue with Distributed Cache to learn about cache Sharding, Replication, and consistency in Distributed Systems.