Cache stampede

A cache stampede, also called a thundering herd, happens when many requests miss the same key at the same moment. Each one runs the same expensive query. The database slows down, which makes every query slower, which makes the herd bigger. The cache was supposed to protect the database, and at this moment it's the reason the database falls over.

The big idea

Think of a shop that closes its doors for restocking. When it reopens, everyone rushes in at once. A stampede is the same crowd, reaching for the same item at the same time.

The fix is to let only one person through. The rest wait for that person's result, or they take the slightly old version and leave.

Walking through it

A hot key serves 5,000 requests per second. It expires. In the next 10 ms, before anyone repopulates it, about 50 requests miss and each runs the same query. If that query takes 2 seconds under load, requests keep piling up. The database saturates, and the query gets slower still.

Four fixes are common.

• Request coalescing. Only one request recomputes the value. The others wait for its result. In one process, that's a map of pending promises. Across servers, it's a short Redis lock, SET key:lock 1 NX PX 5000. The PX 5000 makes the lock expire on its own, so a crashed worker can't hold it forever.
• Probabilistic early expiration. Each reader may recompute slightly before expiry. The chance rises as expiry gets closer, so one request refreshes early and the herd never forms. This is the XFetch algorithm from Vattani and colleagues (2015).

// Recompute if a random early-refresh window has opened.
// `deltaMs` is how long a recompute takes. `beta` ≥ 1 refreshes earlier.
function shouldRecomputeEarly(expiresAt, deltaMs, beta = 1) {
  return Date.now() - deltaMs * beta * Math.log(Math.random()) >= expiresAt
}

Math.log(Math.random()) is negative, so subtracting it adds a random head start. The head start scales with how expensive the recompute is. A slow query starts refreshing earlier.

• Serve stale while revalidating. Keep the old value past its soft expiry, and refresh it in the background. HTTP supports this with Cache-Control: max-age=60, stale-while-revalidate=300.
• Jitter TTLs. Keys written together shouldn't expire together. Add a random offset, as in 300 + random(0..59) seconds.

Common mistakes

• Locks with no expiry. A worker that crashes while holding the lock blocks everyone. Always set a timeout.
• Relying on jitter for one hot key. Jitter spreads keys written together. It does nothing for a single key that everyone reads.
• Recomputing without a limit. If every waiting request also runs the query, you've rebuilt the stampede.

Check yourself

1. A hot key expires and 5,000 requests per second arrive. What does request coalescing do? Only one request recomputes the value, and the others wait for its result or serve stale data.
2. How does early probabilistic refresh prevent a stampede? One reader refreshes before expiry, so the value is already new when the herd would have arrived.

Key takeaways

• A stampede is many misses on one key at once, and each runs the expensive work.
• Coalesce recomputes so one request does the work.
• Refresh early or serve stale to avoid the expiry moment altogether.
• Always give locks an expiry, and jitter TTLs for keys written together.

Further learning

Optimal Probabilistic Cache Stampede Prevention (Vattani et al.) proves the early-refresh rule and compares it with simpler options.

Next, read about cache failure modes, which covers hot keys, missing keys and cold starts.