Cache Stampedes (Dogpiles)

Scenario

Example app: the home page's "deals of the day" block is cached for 60 seconds. Building it takes a 700 ms query. The home page gets 5,000 requests per second.

What you see in production

Every minute, the database shows a burst of hundreds of identical deals queries; p99 spikes and occasionally the pool is exhausted, failing unrelated requests.

The naive code

def deals():
    if (hit := r.get("home:deals")) is not None:
        return json.loads(hit)
    data = expensive_deals_query()         # every concurrent miss runs this
    r.set("home:deals", json.dumps(data), ex=60)
    return data

$deals = Cache::remember('home:deals', 60, fn () => $this->expensiveDealsQuery());

Reproduce it

During the 700 ms rebuild, every request that arrives also misses. Compare the database calls with plain misses, with a lock (request coalescing), and with stale-while-revalidate:

RPS, REBUILD_MS = 5000, 700
arrivals = int(RPS * REBUILD_MS / 1000)         # requests during one rebuild window

def plain():
    return arrivals                              # every miss queries the database

def with_lock():
    return 1                                     # one lock holder rebuilds; the others wait briefly and re-read

def stale_while_revalidate():
    return 1                                     # everyone gets the stale value; one background refresh

for name, fn in (("plain misses", plain), ("lock / coalescing", with_lock), ("stale-while-revalidate", stale_while_revalidate)):
    print(f"{name:24} database queries per expiry: {fn()}")
print(f"(requests arriving during the {REBUILD_MS} ms rebuild: {arrivals})")

plain misses             database queries per expiry: 3500
lock / coalescing        database queries per expiry: 1
stale-while-revalidate   database queries per expiry: 1
(requests arriving during the 700 ms rebuild: 3500)

Root cause

When a popular key expires, all concurrent requests see a miss at the same moment and all recompute the value. The database receives request rate × rebuild time copies of an expensive query. Facebook's memcache paper describes this as a thundering herd and addresses it with leases: each memcached server "return[s] a token only once every 10 seconds per key", and other requesters are told to wait briefly and retry (Scaling Memcache at Facebook).

The fix

Choose one or combine them:

1. Request coalescing / lock: only one caller rebuilds (SET lock NX PX); others wait briefly and re-read, or serve stale.
2. Stale-while-revalidate: keep a soft expiry inside the value; after it, serve the stale value and refresh in the background.
3. Probabilistic early expiration (XFetch): each reader refreshes slightly before expiry with a probability that rises as expiry approaches (Vattani et al.).
4. Proactive refresh of known hot keys by a background job.

def deals():
    raw = r.get("home:deals")
    entry = json.loads(raw) if raw else None
    if entry and time.time() < entry["soft_expiry"]:
        return entry["data"]                                     # fresh
    if r.set("lock:home:deals", "1", nx=True, px=5000):          # one rebuilder
        try:
            data = expensive_deals_query()
            r.set("home:deals", json.dumps({"data": data, "soft_expiry": time.time() + 60}), ex=600)
            return data
        finally:
            r.delete("lock:home:deals")
    if entry:
        return entry["data"]                                     # someone else is rebuilding: serve stale
    time.sleep(0.05)
    return deals()                                               # cold: wait for the rebuilder

LoadingCache<String, Deals> cache = Caffeine.newBuilder()
    .refreshAfterWrite(Duration.ofSeconds(60))   // serve current value, refresh asynchronously
    .expireAfterWrite(Duration.ofMinutes(10))
    .build(key -> dealsRepository.load());       // concurrent misses for a key share one load

// Laravel 11+: stale-while-revalidate helper — fresh for 60 s, then stale for up to 600 s while refreshing
$deals = Cache::flexible('home:deals', [60, 600], fn () => $this->expensiveDealsQuery());
// or an explicit lock: Cache::lock('lock:home:deals', 5)->get(fn () => ...)

const inflight = new Map<string, Promise<unknown>>();
async function once<T>(key: string, load: () => Promise<T>): Promise<T> {
  const running = inflight.get(key) as Promise<T> | undefined;
  if (running) return running;                       // join the in-flight load
  const p = load().finally(() => inflight.delete(key));
  inflight.set(key, p);
  return p;
}

Trade-offs

• Locks need timeouts (a crashed rebuilder must not block forever) and add latency for waiters on a cold key.
• In-process coalescing (singleflight, Caffeine) deduplicates per instance — with 50 pods you still get up to 50 rebuilds; combine with a distributed lock for very expensive values.
• Stale-while-revalidate serves slightly old data by design — fine for deals, not for stock at checkout.
• XFetch is elegant but needs the recompute time stored with the value.

Detect it in production

• Identical query bursts in pg_stat_statements deltas aligned with TTL boundaries.
• Count concurrent misses per key (e.g. lock contention counters); latency spikes every TTL interval.

Key points

• Hot key expiry → every concurrent request recomputes → database spike.
• Coalesce rebuilds (locks, singleflight), serve stale while refreshing, or refresh early.
• Make lock holders time out and combine per-process and distributed coalescing for the hottest keys.