Cache Stampede

What happens when a popular cache entry expires and every request tries to rebuild it at once, and the tools that stop it: single-flight, locks and leases, serving stale data, probabilistic early refresh (XFetch) and background refresh.

Overview

A cache keeps the answer to an expensive question so the next request does not have to ask it again. A cache stampede (also called a thundering herd or dog-pile) happens when a popular entry disappears: it expires, is deleted after a write, or its cache node restarts. Every request that arrives before the entry is rebuilt misses, and each one runs the expensive query itself.

The damage grows with two numbers. Vattani, Chierichetti and Lowenstein, in their 2015 paper on stampede prevention, give the example of an item read 10 times a second that takes 3 seconds to recompute: 30 requests end up recomputing it. The extra load slows the database, which makes each rebuild take longer, which lets more requests pile in. That feedback is why stampedes turn into outages.

The fixes all make sure that one request, not all of them, does the rebuild, and give everyone else something to do meanwhile: wait for it, use the old value, or never see the entry expire at all.

What you will be able to do

  • Estimate how many rebuilds a hot key causes when it expires, and decide whether it needs protection.
  • Use single-flight inside a process and a lock or lease across servers, and handle the requests that lose.
  • Serve stale data safely while one request refreshes it, in the application and in an HTTP cache.
  • Explain XFetch's probabilistic early expiration and choose its parameter.
  • Combine these into a layered design for a very hot page.

Key concepts

  • Thundering herd
  • Stampede size
  • Single-flight
  • Lock or lease on rebuild
  • Stale-while-revalidate
  • Probabilistic early expiration
  • XFetch
  • Refresh ahead
  • TTL jitter

Interview questions

  • What is a cache stampede, and how would you estimate its size?
  • How does single-flight differ from a distributed lock?
  • Explain XFetch (probabilistic early expiration).
  • What is stale-while-revalidate and when is it not acceptable?
  • Design stampede protection for a product page read 50,000 times a second.
  • How did Facebook handle thundering herds in memcache?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio