Part 2 of 8 · 2 min read
Stampede: many misses for one key
What happens when a popular entry expires and a crowd asks for it at once.
Think of a shop where the shelf of a popular item runs empty. Fifty customers walk to the storeroom at once, each asking for the same box. The storeroom door jams. One person fetching a box for everyone would have been enough.
The book "Understanding Distributed Systems" calls this the thundering herd. It happens when many clients ask the same missing item at the same time, and every one of them reaches the dependency. It gives the case of a service that has just started or scaled out, so its new instances have empty caches, and the case of an item that suddenly becomes popular. Level 1 met the same problem at the CDN.
Cache stampede (thundering herd)
A cache stampede is a burst of identical requests to the database caused by one popular entry expiring or being missing, so that every waiting request misses at once.
Example: the home page entry expires at 12:00:00. In the next 200 ms, 400 requests miss and each runs the same 300 ms database query.
A worked example. The home page is read 2,000 times a second. The query takes 300 ms. When the entry expires, all requests during the 300 ms reload window miss: 2,000 × 0.3 = 600 requests run the same query together. The database does 600 times the needed work. If it can take 50 queries at once, the rest queue, the wait grows, and more requests pile up.
Fixes:
- Request coalescing. The book describes the idea: allow at most one outstanding request for a given item per cache, so that if 10 concurrent requests need a missing record, only one request goes out to the dependency. The other 9 wait for its answer. In the example, 1 query runs instead of 600.
- Locking on a miss. The first request takes a short lock on the key and reloads. The others wait or briefly use the old value. The same effect, across servers.
- Refresh before expiry. A background job reloads popular keys a little before the TTL ends, so that readers always hit.
- Serve slightly old data while refreshing. One request reloads while the rest get the expired value. This is the lazy expiry from module 3.
- Hiding the origin. The book "Building Microservices" describes a design in which requests never go to the origin directly. A miss only raises an event, and the origin refills the cache in the background. The request fails fast, instead of piling load on the origin. This protects the origin during a large cache loss.
| Fix | Database queries in the example | Cost |
|---|---|---|
| None | 600 | None |
| Coalescing | 1 | A waiting list in the cache layer |
| Early refresh | 1, no waiting | A job and a list of hot keys |
| Serve stale while refreshing | 1 | Some readers get older data |
Check yourself:
- A key is read 500 times a second and a reload takes 200 ms. How many requests miss at once at expiry?
- How does request coalescing change the number of database queries?