For the few milliseconds between a hot key expiring and the first refill landing, there is no cache. Every request that arrives in that window misses and is forwarded, and by Little’s Law the number of them is λ·d — a rate times a time. Single-flight coalescing reduces it to one, which is the difference between a cache that protects a backend and a cache that merely usually does.
Core ideas
Three ideas, and the first one is a change of timescale: everything so far on this course was an average over a long window, and this is about one hundred-millisecond window.
A cache entry expires. The next request misses and starts a fill that takes d milliseconds. Every request for that key arriving before the fill lands also finds nothing, also misses, and is also forwarded. For d milliseconds the hit rate for that key is zero, and (1 − h)λ describes none of it.
The number of requests in flight is the arrival rate times the time each spends in flight — the identity of “Little’s Law from a Trace”, applied to one key over one window. At 5 000 reads a second and a 100 ms fill that is 500 requests, all asking the backend for the same value at the same moment.
Single-flight coalescing lets the first miss start the fill and makes every subsequent request for that key wait on the same in-flight fill. The backend sees exactly one request per key instead of λ·d. Nothing about the cache changed; what changed is what happens to the requests that miss together.
The material
Where the burst comes from, how large it gets, and why a bigger cache does not help.
The miss window d of a key is the time from a miss being detected to the refilled value being available to serve — the backend call plus the write back. A stampede is the set of requests for that key which arrive during the miss window and are therefore all forwarded to the backend. Its size is λ_key·d.
λ_key is the read rate of the one key, not of the service. A service at 50 000 rps whose hottest key takes ten per cent of the traffic has λ_key = 5 000.
The formula is a rate times a time and nothing else. It does not depend on the hit rate, the cache size, the policy or the catalogue — those all describe steady state, and this is a transient. That independence is the uncomfortable part: a cache with a 99.9% hit rate has exactly the same stampede as a cache with a 50% one, for the same key at the same read rate.
λ_key = 5 000 reads a second, d = 100 ms. The stampede is 5 000 × 0.1 = 500 requests. Against a backend that can hold 200 concurrent fills that is 5/2 = 2.50 times its capacity: the backend does not absorb this, and the requests it cannot take either queue or fail.
Scale either input and it scales linearly. The same key at a 1 ms fill sends 5 requests through; at 500 ms it sends 2 500; at 2 s, 10 000. And the fill time is the one thing you least control, because a slow fill is exactly what happens when the backend is already under pressure — which is a feedback loop, not a coincidence.
A bigger cache does not help: the key was in the cache and the problem is the moment it left. A longer TTL does not help either; it makes the expiry rarer, not smaller, and TTL and Staleness has already priced what a longer TTL costs in wrongness. Nor does a higher hit rate: the hit rate is an average over a window that contains this one, and the average is fine.
Two things do help. Coalescing — also called single-flight or request collapsing — makes one request per key per window reach the backend and parks the rest on the result. And early refresh, where a request arriving near the end of a TTL refreshes the entry while continuing to serve the old value, removes the window altogether at the cost of a little more staleness.
Without coalescing, λ_key·d requests reach the backend per expiry. With it, exactly one does, per key. The reduction factor is λ_key·d itself.
So coalescing is worth the most precisely where the stampede is worst: the hotter the key and the slower the fill, the larger the factor. At 5 000 reads a second and a 100 ms fill it is a factor of 500.
A fleet that sets the same TTL on everything at deploy time expires everything together. Then k hot keys each send λ_key·d requests in the same window, and the burst is k times as large while coalescing still reduces it to k — one per key. Jittering the TTLs spreads the expiries out, and it is the cheapest of the three fixes on this page.
One limit on the model: λ·d counts arrivals in the window and assumes the backend keeps accepting them. A backend that starts queueing will make d longer, which lets more requests into the window, which makes d longer still. The formula gives the first step of that loop and not the rest of it, and the first step is already enough to size the problem.
Interactive
What arrives at the backend in the window after a hot key expires
Method
Two inputs, one multiplication, and then the comparison that decides whether it matters.
Not the service’s rate: one key’s. If you know the total rate and the skew, Popularity Is Skewed: Zipf gives you the top key’s share — at N = 50 and s = 2 it is 61.53% of all requests, which makes λ_key most of λ.
From miss detected to value available, including the write back. Use a high percentile of the fill time rather than the mean: the stampede you care about is the one that happens when the backend is slow.
λ_key·d requests arrive in the window. Divide by the backend’s concurrent capacity. Above 1 the backend does not absorb the burst, and the cache’s excellent hit rate will not appear anywhere in the incident review.
Coalescing takes the burst to one per key. Early refresh removes the window and costs a little staleness. Jitter stops many keys expiring together. They address different parts of the same failure and a busy system usually wants all three.
The multiplication takes a line. The table under it is the same multiplication at six fill times, which is where the shape lives.
Read the table as a warning about d rather than about λ. The read rate of a hot key is a fact about your users; the fill time is a property of your backend, and it grows exactly when you can least afford it to.
For a faded rehearsal, take a service at 20 000 rps whose hottest key is 10% of traffic, with a 50 ms fill and a backend that holds 200 concurrent requests. The supplied first move is that λ_key = 2 000; compute the burst and the ratio to capacity, then say what the ratio becomes if 12 hot keys expire together because they share a deploy-time TTL. State which of the three fixes you would reach for first and why.
In the lab the burst is drawn as a rectangle against the backend’s capacity line from Queues and Utilisation, with the coalesced version beside it. Raise the number of keys expiring together and watch the red rectangle grow while the green one does not.
You should be able to compute λ_key·d for a hot key, express it as a multiple of the backend’s concurrent capacity, state what coalescing reduces it to and by what factor, and say why a larger cache and a higher hit rate change neither number.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.