Stampedes and request coalescing

The problem: one expiry, a thousand queries

The viral link x7Kp gets 50,000 redirects a second. Its Redis entry has a one-hour TTL. When the hour is up, the entry vanishes, and the next request misses and asks the database. That query takes about 20 ms. During those 20 ms, another 1,000 requests arrive, find the entry still missing, and each sends its own query for the same row.

The database slows down under the burst, so the refill takes longer, so more requests miss, which slows it further. That feedback loop is a cache stampede (also called a thundering herd or dogpile). It has three common triggers:

Fix 1: let one request do the work (coalescing)

The simplest fix: when a key is already being loaded, later requests wait for that load instead of starting their own. In one process this takes a few lines: keep a map of in-flight loads, keyed by cache key.

type Entry<V> = { value: V; delta: number; expiresAt: number };

const cache = new Map<string, Entry<unknown>>(); // stands in for Redis in this sketch
const inFlight = new Map<string, Promise<unknown>>();

/** Run load() at most once at a time per key in this process; everyone else waits for the same answer. */
function coalesce<V>(key: string, load: () => Promise<V>): Promise<V> {
  const running = inFlight.get(key);
  if (running) return running as Promise<V>;
  const p = load().finally(() => inFlight.delete(key));
  inFlight.set(key, p);
  return p;
}

/** XFetch: refresh early, with a chance that rises as expiry nears and as the load gets slower. */
function shouldRefreshEarly(e: Entry<unknown>, beta = 1, now = Date.now()) {
  return now - e.delta * beta * Math.log(Math.random()) >= e.expiresAt;
}

export async function cached<V>(key: string, ttlMs: number, load: () => Promise<V>): Promise<V> {
  const e = cache.get(key) as Entry<V> | undefined;
  if (e && !shouldRefreshEarly(e)) return e.value;
  return coalesce(key, async () => {
    const start = Date.now();
    const value = await load();
    const delta = Date.now() - start; // how long a refill takes
    cache.set(key, { value, delta, expiresAt: Date.now() + ttlMs });
    return value;
  });
}

Tested with 1,000 concurrent misses on one key, the loader runs once and all 1,000 callers get the same value; if the load fails, every waiter gets the error and the next call tries again. Go ships this as singleflight, and proxies offer it as a setting: nginx's proxy_cache_lock lets only one request at a time fill a cache entry, while the others wait (up to 5 seconds by default).

Per-process coalescing caps the burst at one query per app server: 40 servers, 40 queries, instead of 1,000. That's usually enough. For a fleet-wide cap of one, the cache itself has to coordinate.

Fix 2: leases, coordinated by the cache

With leases, a miss doesn't just return "not found". The first client to miss gets a token and the job of refilling; others that miss shortly after are told to wait briefly and retry, by which time the entry is usually there. Facebook's memcache hands out a token for a key at most once every 10 seconds, and the same token, cancelled by a delete, stops the stale sets of 06.04 Invalidation and staleness. A simpler home-made version is a short lock in Redis: SET lock:x7Kp 1 NX PX 2000, where only the request that wins the lock queries the database.

Fix 3: serve the old value while refreshing

For most data, a copy a few seconds past its TTL is better than a slow page or a dead database. So keep two lifetimes:

• Soft TTL: after this, the entry is stale. The next request triggers a refresh in the background (coalesced), but is answered immediately with the stale value.
• Hard TTL: after this, the entry is too old to use at all.

No request ever waits for the refill except after the hard TTL. HTTP caches have the same idea built in: stale-while-revalidate (06.07 CDNs in depth), and nginx's proxy_cache_use_stale updating with proxy_cache_background_update. Serving stale is also what keeps Snip up when the database itself is down: stale-if-error.

Fix 4: refresh before expiry

Instead of waiting for the expiry, refresh a hot entry slightly early, at a random moment, so it never actually expires under load. The shouldRefreshEarly check above is the XFetch rule from a 2015 paper: each read refreshes early with a probability that grows as expiry approaches, scaled by delta (how long a refill takes) and beta (1 by default; larger refreshes earlier). With a 50 ms refill, a read 50 ms before expiry refreshes with probability about 37%; a read 500 ms before, about 0.005%. Hot keys, read thousands of times a second, are almost certain to be refreshed by one request just before they expire; cold keys rarely bother.

Fix 5: spread the expiries

Synchronised expiry is a self-inflicted stampede. Add jitter to TTLs (an hour plus or minus 10%, at random, 06.03 Eviction: LRU, LFU and TTL) so entries filled together expire apart.

Cold caches

When a whole cache is empty, none of the above is enough: every key misses at once. The options are to warm it first (copy the hottest keys from a warm replica or region before taking traffic), bring it in gradually (send it 1% of traffic, then 10%, and so on), and limit misses at the database with a concurrency cap so excess requests fail fast or wait rather than piling on (03.11 Backpressure and load shedding).

Recap

Interview questions