Cache stampede: many requests reloading the same key Intermediate

Estimated reading time: 9 min read

Read first

Cache-aside pattern

Symptoms

Endpoint latency and database query count rise periodically while the request rate stays roughly flat. If the period matches the TTL of a hot key (say 5 minutes), many requests are reloading that key at the same time.

A cache miss is not a stampede. One request missing and reloading is normal. A stampede is when many requests miss together before the first one finishes loading, so the same work runs many times.

Reproduction

examples/src/cache-stampede/naive.ts: cache-aside without request coalescing. The simulated DB query takes 300 ms; 20 concurrent requests run against an empty cache.

async function naiveCacheAside(key: string): Promise<string> {
  const cached = await redis.get(key);
  if (cached) return cached;
  const value = await expensiveQuery(key); // simulated DB, takes 300ms
  await redis.set(key, value, 'EX', 5);
  return value;
}

await Promise.all(Array.from({ length: 20 }, () => naiveCacheAside(key)));

Actual output:

20 concurrent requests, empty cache (cache miss) — cache-aside without a lock:
  [DB] Starting query for "stampede:naive" (DB call #1)
  [DB] Starting query for "stampede:naive" (DB call #2)
  ... (18 similar "Starting query" lines, almost simultaneous) ...
  [DB] Starting query for "stampede:naive" (DB call #20)
  [DB] Finished query #1
  ... (19 similar "Finished query" lines) ...

Actual DB calls: 20 (expected in practice: only 1)
Distinct values among the 20 results: 7

20 requests produce 20 queries for one key. All 20 passed the if (cached) check before any SET happened, so the first SET does not pull the other 19 requests onto the hit path.

Root cause

Cache stampede when many requests miss the same key

Request 1 · Request 2 · Request 3 · Cache

Step 1/4

Three requests hit the application and read the same expired key. All three miss the cache.

Three common situations:

A hot key with a fixed TTL expires: every request in flight at that moment misses.
Cache restart or flush: every key disappears at once.
Many instances start at once (deploy, autoscale) and all warm the cache.

How many requests fit in a 300 ms window

The number of duplicate loads is roughly request rate × load time. A key receiving 100 requests/second with a 0.3-second load:

t = 0 ms     key expires
t = 0..300   ~30 requests arrive, all see a miss
             ███████████████████████████████  30 identical queries to the DB
t = 300 ms   first request finishes SET; hits from here on

This is an estimate, not a measurement: the real number also depends on arrival pattern and the connection pool. The slower the query, the wider the window, and because the DB slows down under overload, the window widens itself.

Raising the TTL from 5 to 30 minutes makes the event rarer but does not remove it. TTL jitter spreads the expiry times of many keys; it does not coalesce the requests loading one key.

How to detect it

Correlate within the same time window: cache miss rate, query count by fingerprint, connection pool load. Many requests missing the same key and producing identical queries is direct evidence.

Rule out batch jobs and cache warming first. Add a “loaders in flight per key group” metric to tell a stampede apart from a real traffic increase.

Immediate mitigation

Four ways to prevent it

	Per-key lock (Redis)	Singleflight (in-process)	XFetch (early refresh)	Stale-while-revalidate
Scope	Across instances	One process	Each request decides	One background loader
Remaining requests	Wait with a deadline	Wait on a shared Promise	Keep reading the cached value, no wait	Get the stale value immediately
Stale data	No	No	No (refreshes before expiry)	Yes, temporarily
Latency at expiry	High for waiting requests	High for waiting requests	Nearly unchanged	Unchanged
Complexity	High (token, lease, deadline)	Low	Low, needs load-time measurement	Medium

Default: singleflight per instance, plus XFetch or stale-while-revalidate for hot keys. Use a distributed lock only when loading is expensive enough that one load per instance is still too many.

Singleflight: 8 lines

const inflight = new Map<string, Promise<string>>();

function load(key: string, loader: () => Promise<string>): Promise<string> {
  let p = inflight.get(key);
  if (!p) {
    p = loader().finally(() => inflight.delete(key));
    inflight.set(key, p);
  }
  return p; // every request for the same key shares one Promise
}

Each process loads each key only once. With 10 instances, the DB receives at most 10 queries instead of hundreds.

Token lock with compare-and-delete

The with-lock.ts demo in the repo cuts 20 queries down to 1:

20 concurrent requests, empty cache (cache miss) — cache-aside with a SET NX PX lock:
  [DB] Starting query for "stampede:with-lock" (DB call #1)
  [DB] Finished query #1

Actual DB calls: 1 (expected: exactly 1)
Distinct values among the 20 results: 1

The demo uses a fixed token, a DEL that does not check ownership, and an unbounded wait loop, so it is not for production. A safer version (illustrative, not run in the repo):

const RELEASE = `if redis.call('get', KEYS[1]) == ARGV[1]
                 then return redis.call('del', KEYS[1]) else return 0 end`;

async function getOrLoad(key: string, loader: () => Promise<string>) {
  const hit = await redis.get(key);
  if (hit) return hit;

  const lockKey = `lock:${key}`;
  const token = randomUUID();
  if ((await redis.set(lockKey, token, 'PX', 5000, 'NX')) === 'OK') {
    try {
      const again = await redis.get(key);          // re-read after acquiring the lock
      if (again) return again;
      const value = await loader();
      await redis.set(key, value, 'EX', 300 + Math.floor(Math.random() * 60));
      return value;
    } finally {
      await redis.eval(RELEASE, 1, lockKey, token); // delete only if it is still our lock
    }
  }

  const deadline = Date.now() + 2000;               // wait with a deadline
  while (Date.now() < deadline) {
    await sleep(30 + Math.random() * 20);
    const v = await redis.get(key);
    if (v) return v;
  }
  throw new Error('cache busy');                    // or return a stale value if available
}

Why the token must be compared on release: A holds the lock for 2 seconds but the query takes 3; the lock expires and B acquires a new one; if A runs an unconditional DEL, A deletes B’s lock.

A lease with a TTL does not guarantee that only one loader runs in every situation; see Redis’s lock guide.

XFetch: probabilistic early refresh

The paper by Vattani et al. (PVLDB 2015) gives each request a probability of refreshing that grows as the key nears expiry. A request refreshes when:

now - delta * beta * ln(rand()) >= expiry

delta: how long the most recent load took (stored with the cached value).
beta: a factor, default 1.0; larger means earlier refresh.
rand(): a random number in (0, 1]; ln(rand()) is negative, so the left side is always greater than now.

The slower the load (larger delta), the earlier the refresh; usually only one request “wins” before expiry, so duplicate loads are rare. It needs no lock, but delta and the expiry must be stored with the value.

Stale-while-revalidate

On expiry, return the old value immediately and trigger a single background refresh. A good fit when slightly stale data is acceptable and latency must stay stable.

Production checklist

Hot keys: in-process singleflight, plus XFetch or stale-while-revalidate.
TTLs have jitter; keys loaded in bulk do not expire in the same second (see expiration and eviction).
If you use a lock: random token, release via compare-and-delete, re-read the cache after acquiring the lock, waiting requests have a deadline.
The loader has its own timeout and an error path (stale value or fail fast), never an unbounded wait.
After a flush/restart/deploy: warm important keys in a controlled way; don’t let every instance warm at once.
Metrics: loaders in flight per key group, miss rate, DB queries by fingerprint.
Base pattern: cache-aside.

Summary

Self-check: (1) Why doesn’t raising the TTL cure a stampede? (2) What goes wrong if the lock expires midway and DEL is unconditional? (3) What does XFetch need to store alongside the cached value?

References

#cache #redis #cache-stampede #thundering-herd