Stampedes, Penetration and Avalanche
The three ways a cache takes down the database it was protecting, and the standard fixes: coalescing, negative caching, jittered TTLs.
SET lock:<key> <token> NX EX 10All three of these failures are caused by the cache rather than by the database behind it, and all three appear only under load, which is why they ship.
Stampede (thundering herd)
One hot key expires. Every concurrent request for it misses, and all of them reach the database at once to compute the same value. The fix is to let exactly one caller compute: an in-process map of in-flight promises handles one process, a short lock (SET lock NX EX 10) handles the cluster, and serving the stale value while one caller refreshes handles the latency. nginx spells those last two proxy_cache_lock on and proxy_cache_use_stale updating; HTTP spells the second stale-while-revalidate (RFC 5861). Facebook's memcache paper reports leases — one token per key per 10 seconds — cutting a peak database query rate from 17K/s to 1.3K/s.
Penetration
Requests for keys that do not exist populate nothing, so every one reaches the database. A crawler or an attacker enumerating IDs turns your cache into a pass-through. Cache the miss itself, with a short TTL, and put a Bloom filter in front if the key space is attacker-controlled.
Avalanche
A warm-up job writes ten thousand keys with EX 600 in the same second, and ten minutes later they all expire in the same second. Add jitter to every TTL so expiry is spread out.
Shorthand and longhand
SET key 1 NX EX 10 is one atomic command. The longhand SETNX followed by EXPIRE looks equivalent and is not: a crash between the two leaves a lock with no TTL, and the stampede becomes a permanent outage.
Example
// Request coalescing: one database read per key per process, and one per
// cluster thanks to a short Redis lock.
import { randomUUID } from 'node:crypto';
const inflight = new Map(); // key -> Promise, this process only
// Spread expiry so a batch of keys written together does not expire together.
const jitter = (ttl, spread = 0.2) =>
Math.round(ttl * (1 - spread / 2 + Math.random() * spread)); // 600 -> 540..660
export async function getCoalesced(key, loader, ttl = 60) {
const cached = await redis.get(key);
if (cached !== null) return JSON.parse(cached);
const pending = inflight.get(key);
if (pending) return pending; // same process: wait, do not start a second read
const work = (async () => {
const token = randomUUID();
// Atomic. SETNX + EXPIRE is NOT the same: a crash in between leaves a
// lock with no TTL and the key is never recomputed again.
const gotLock = await redis.set(`lock:${key}`, token, { NX: true, EX: 10 });
if (!gotLock) {
await new Promise((r) => setTimeout(r, 50)); // give the winner a moment
const second = await redis.get(key);
if (second !== null) return JSON.parse(second);
return loader(); // winner died or is slow: degrade to a direct read
}
try {
const value = await loader();
await redis.set(key, JSON.stringify(value), { EX: jitter(ttl) });
return value;
} finally {
// Release only our own lock, or a slow caller deletes the next holder's.
if ((await redis.get(`lock:${key}`)) === token) {
await redis.del(`lock:${key}`);
}
}
})().finally(() => inflight.delete(key));
inflight.set(key, work);
return work;
}When to use it
- A homepage query that spikes the database to 100% CPU every time its cache entry expires.
- An endpoint being enumerated by IDs that do not exist, pushing every request to Postgres.
- A deploy that warms the cache and then falls over ten minutes later.
- Keeping a dashboard responsive while one caller recomputes an expensive aggregate.
More examples
Negative caching with a sentinel
Reach for this the first time a log shows thousands of database queries returning no rows. The TTL is the tuning knob and it is a product decision: too long and newly created records appear to be missing, too short and the protection disappears under a determined crawler.
// A distinct value for "we checked, it does not exist". Without it, a cached
// miss is indistinguishable from an absent key and buys you nothing.
const MISSING = '__missing__';
export async function getProfile(handle) {
const key = `profile:${handle}`;
const hit = await redis.get(key);
if (hit === MISSING) return null; // cached miss: no database call
if (hit !== null) return JSON.parse(hit);
const row = await db.profileByHandle(handle);
if (!row) {
// Deliberately short: a 404 today is often a signup tomorrow, and this
// TTL is how long that new account stays invisible.
await redis.set(key, MISSING, { EX: 30 });
return null;
}
await redis.set(key, JSON.stringify(row), { EX: 600 });
return row;
}Probabilistic early expiration, instead of locks
Use this when a lock-based approach is awkward — many application instances, no appetite for lock cleanup, values whose compute cost varies a lot. It never fully serialises recomputation, so it suits values that are expensive but not catastrophic to compute twice.
// XFetch, from "Optimal Probabilistic Cache Stampede Prevention"
// (Vattani, Chierichetti, Lowenstein; VLDB 2015). No locks, no coordination:
// each reader independently volunteers to refresh, slightly before expiry,
// and the more expensive the value was to compute, the earlier it volunteers.
const BETA = 1; // > 1 refreshes earlier and more often
function shouldRefresh({ delta, expiry }) {
// delta = ms the last recomputation took
// expiry = absolute ms at which the entry becomes stale
// Math.random() is in (0,1), so the log term is negative and the product
// is a positive slack that grows with delta.
return Date.now() - delta * BETA * Math.log(Math.random()) >= expiry;
}
export async function getWithEarlyExpiry(key, loader, ttl = 60) {
const h = await redis.hGetAll(key); // fields: value, delta, expiry
if (h.value && !shouldRefresh({ delta: Number(h.delta), expiry: Number(h.expiry) })) {
return JSON.parse(h.value);
}
const started = Date.now();
const value = await loader();
const delta = Date.now() - started;
await redis
.multi()
.hSet(key, {
value: JSON.stringify(value),
delta: String(delta),
expiry: String(Date.now() + ttl * 1000),
})
.expire(key, ttl * 2) // keep the entry around past expiry so it can be reused
.exec();
return value;
}Serving stale while one caller refreshes
This is the pattern for an expensive aggregate on a page that must never block: p99 latency stops depending on how long the recomputation takes. The trade is explicit staleness, up to the grace window, and it also gives you a last-known-good value to serve when the loader is failing.
// Two TTLs per entry: fresh until `expiry`, servable until the Redis key dies.
// Readers after `expiry` get the old value immediately and one of them
// refreshes in the background. This is stale-while-revalidate in application
// code; at the HTTP layer the same behaviour is a response header:
// Cache-Control: public, max-age=60, stale-while-revalidate=30, stale-if-error=600
export async function getStaleOk(key, loader, ttl = 60, graceSeconds = 600) {
const raw = await redis.get(key);
if (raw === null) return getCoalesced(key, loader, ttl); // true miss: coalesce
const entry = JSON.parse(raw);
if (entry.expiry > Date.now()) return entry.value; // fresh
// Stale but usable. Try to win the refresh; if another process has it,
// just serve the stale value.
if (await redis.set(`refresh:${key}`, '1', { NX: true, EX: 30 })) {
void (async () => {
try {
const value = await loader();
await redis.set(
key,
JSON.stringify({ value, expiry: Date.now() + ttl * 1000 }),
{ EX: ttl + graceSeconds },
);
} finally {
await redis.del(`refresh:${key}`);
}
})();
}
return entry.value; // nobody waits on the database
}
Discussion