Notesfoundations🌱 seedling

Cache Stampede

Also: Thundering Herd · Dog-Piling · Cache Miss Storm

When a hot key expires or the cache empties, every concurrent reader misses at once and recomputes the same value, flooding the backend. If those recomputations time out, nobody refills the cache and the overload sustains itself.

Why it exists

A cache hides how many identical reads there are. At the moment a hot entry disappears, all of them reach the backend together.

How it works

  • Trigger: TTL expiry of a hot key, eviction, a cache restart or failover, or a deploy that flushes keys.
  • Amplification: N concurrent misses become N copies of an expensive query.
  • Self-sustaining: timeouts mean no fill, so misses continue. This is a Metastable Failure.
  • Defences:
    • One recomputes, others wait or serve stale: a lease or lock per key.
    • Stale-while-revalidate: keep serving the old value during refresh.
    • Probabilistic early refresh (XFetch): each reader refreshes before expiry with a probability that rises as expiry nears, scaled by how long recomputing takes.
    • TTL jitter, so keys don't expire together.
    • Gradual warm-up and throttling after a cold start.

Trade-offs

Defence Gains Costs
lease / lock one backend query per key waiters add latency; lock-holder failure needs a timeout
serve stale no latency spike briefly stale data
early refresh no cliff at expiry some extra recomputation

In practice

  • Facebook memcache: leases issued at most once per 10 s per key cut the peak database query rate on herd-prone keys from 17K/s to 1.3K/s.
  • Slack, February 2022: a rolling Consul agent upgrade emptied memcached nodes, and an expensive boot-time query fanned out to every database shard. The overload only cleared once client boots were throttled.

Pitfalls

  • Trusting the average hit ratio: one hot key can stampede while the dashboard says 99%.
  • Retrying failed recomputations immediately, which multiplies the herd.

Recall

These cards are also in your review deck, scheduled with spaced repetition.