Thundering herd and cache stampede simulator

Requests arrive at random at the rate you set, spread evenly over the hot keys. Every key starts cached, as just after a cache warm-up, and expires after its TTL; rebuilding it takes the recompute time. The chart shows how many recomputes are running at each moment; the table runs all four strategies on the same traffic. Raise the number of keys and add TTL jitter to see expiries that line up and spread out.

A thundering herd is many waiters woken or released at once for work only one of them needs to do. In caching it is called a cache stampede or dogpile: a popular value expires, the requests that arrive in the next moments all miss, and each one goes to the database or service behind the cache to rebuild the same value. The backend, sized for the cache’s normal hit rate, suddenly sees a burst of identical expensive queries, slows down, and so stretches the window in which more requests miss.

Every request that arrives while the first recompute is still running finds the cache empty, so one expiry causes roughly 1 + rate × recompute time rebuilds. At 2 requests per millisecond and a 100 ms recompute, that is about 200. The simulation of one key with a 1-second TTL over 20 seconds:

A lock, or single flight. The first request to miss takes a lock and recomputes; later ones wait for its result instead of starting their own. One recompute per expiry, at the cost of waiting: in the run above 3,580 requests waited an average of 50 ms. Go’s singleflight package does this within one process; across many servers it needs a distributed lock or a lease.

Serve stale while revalidating. Keep the expired value, return it to everyone, and let one request refresh it in the background. Nobody waits, and the backend sees one recompute, but requests get data up to one recompute time older than the TTL promised. HTTP caches can do this with the stale-while-revalidate directive of RFC 5861.

Probabilistic early expiration. In the XFetch algorithm of Vattani, Chierichetti and Lowenstein, each request refreshes the value early when now − Δ·β·ln(rand) ≥ expiry, where Δ is how long the last recompute took and β (1 here unless you change it) tunes how eager it is. Refreshes become likelier as expiry approaches, so usually one request rebuilds the value before it expires and nobody misses. The busier the key, the earlier the refresh: at 2 requests per millisecond it fired about 574 ms before expiry on average, refreshing 38 times in 20 seconds instead of 18. At 0.05 requests per millisecond it refreshed 22 times and 1 requests still met an expired value.

TTL jitter doesn’t help one key, but stops many keys from expiring together, as the next section shows.

Keys written at the same moment with the same TTL expire at the same moment: after a deploy, a cache restart or a bulk load. With 200 hot keys sharing 20 requests per millisecond, a 2-second TTL and a 100 ms recompute, the most recomputes running at once were:

The term is older than caching. When many processes block waiting for the same event, such as a connection arriving on a listening socket they share, the kernel can wake all of them though only one can accept the connection; the others wake, find nothing to do and sleep again, wasting a context switch each. Since version 4.5, Linux’s epoll offers the EPOLLEXCLUSIVE flag so that an event wakes one of several waiters instead of all of them.