One key expires
A popular page is slow to build: it needs a heavy database query. So the result is kept in a cache, and every request reads the cached copy. The database is barely touched.
A cached value does not stay forever. It has an expiry time, after which it is thrown away so that it cannot get too far out of date. The next request finds nothing, runs the query, and fills the cache again.
That works when one request arrives at a time. Now picture a busy site.
The cached value expires
Nothing is wrong yet. This is what an expiry time is for.
Many requests arrive before it is rebuilt
Rebuilding takes a moment. During that moment every request finds the cache empty.
Each one runs the same slow query
None of them knows the others are doing the same thing. The database goes from no work to dozens of copies of its heaviest query.
The database slows down, so the rebuild takes longer
The longer it takes, the more requests arrive and pile on. The problem feeds itself.
This is a cache stampede. It is also called a thundering herd or dog-piling.
Watch it happen
Three requests arrive every tick. The database can run 4 queries at full speed. The cached value expires every 14 ticks.
Requests
3 per tickCache: homepage
fresh for 6Database
0 running · handles 4Database queries running, tick by tick
The rule: Every request that misses runs its own database query. The cached value expires every 14 ticks.
- Requests
- 0
- Database queries
- 0
- Most at once
- 0
- Made to wait
- 0
Look at the numbers when it finishes. Only one query was needed each time the value expired. Everything above that was the same answer, computed again and again.
Fix 1: one rebuilds, the rest wait
The cheapest fix is to make sure only one request does the work.
The first request to miss takes a lock
A lock is a marker that says "someone is already rebuilding this".
It runs the query and fills the cache
One query, at full speed.
Everyone else waits, then reads the cache
A request that finds the lock taken does not go to the database. It waits a moment and reads the fresh value.
Requests
3 per tickCache: homepage
fresh for 6Database
0 running · handles 4Database queries running, tick by tick
The rule: The first request to miss rebuilds the value. The others wait for it. The cached value expires every 14 ticks.
- Requests
- 0
- Database queries
- 0
- Most at once
- 0
- Made to wait
- 0
def get_homepage():
page = cache.get("homepage")
if page is not None:
return page
if cache.add("lock:homepage", "1", ttl=10): # only one caller succeeds
page = build_homepage() # the slow query
cache.set("homepage", page, ttl=300)
cache.delete("lock:homepage")
return page
time.sleep(0.05) # someone else is building it
return get_homepage()The lock has its own short expiry time. If the request holding it crashes, the lock disappears by itself and someone else can try.
Good at
- The database runs one query instead of dozens
- Simple to add around an existing cache
Where it bites
- Requests that arrive during the rebuild still have to wait for it
Fix 2: serve the old value while rebuilding
Why make anyone wait? The old value is a few seconds out of date. For most pages that is fine.
Keep the expired value, hand it out, and rebuild in the background. The first request to notice the expiry starts one rebuild. Every request, including that one, gets the old value at once. When the rebuild finishes, the new value replaces it. This is often called stale-while-revalidate.
Requests
3 per tickCache: homepage
fresh for 6Database
0 running · handles 4Database queries running, tick by tick
The rule: Requests keep getting the old value while one rebuild runs in the background. The cached value expires every 14 ticks.
- Requests
- 0
- Database queries
- 0
- Most at once
- 0
- Made to wait
- 0
A close relative is early refresh: rebuild a little before the expiry time, so the value never actually runs out.
Good at
- Nobody waits, and the database runs one query
- The site stays up even if the rebuild is slow or fails
Where it bites
- Readers get a slightly old value during the rebuild
- Needs a cache that can keep a value past its expiry time
Fix 3: do not let keys expire together
A stampede does not need one hot key. It also happens when many keys expire at the same moment. A common cause: the site restarts, fills its cache within a few seconds, and gives everything the same expiry time. Five minutes later all of it expires at once.
Add a little randomness to every expiry time. This is called jitter.
Example
Spreading out the expiry
Instead of 300 seconds for every key, use 300 plus a random number from 0 to 60. A thousand keys that were cached in the same second now expire across a whole minute, about 17 per second instead of 1,000 at once.
import random
cache.set(key, value, ttl=300 + random.randint(0, 60))Compare them yourself
Requests
3 per tickCache: homepage
fresh for 6Database
0 running · handles 4Database queries running, tick by tick
The rule: Every request that misses runs its own database query. The cached value expires every 14 ticks.
- Requests
- 0
- Database queries
- 0
- Most at once
- 0
- Made to wait
- 0
| Fix | Database queries per expiry | Do requests wait? | Use it when |
|---|---|---|---|
| Nothing | One per request that misses | Yes, and longer as load grows | Never, for a busy key |
| One rebuilds, the rest wait | 1 | Yes, for one rebuild | The value must never be stale |
| Serve stale, rebuild behind | 1 | No | A slightly old value is acceptable |
| Jitter on expiry times | Spread out over time | No | Always, for every key |
The fixes combine. A common setup is jitter on every key, plus serve-stale for the handful of keys that are both popular and slow to build.
Key takeaways
- A stampede happens when a popular cached value expires and many requests rebuild it at the same time.
- It feeds itself: more queries make each query slower, which leaves the cache empty for longer.
- A lock lets one request rebuild while the others wait.
- Serving the old value during the rebuild means nobody waits at all.
- Random jitter on expiry times stops many keys from expiring together.