The whole course ▾
System Design · Lesson 8 of 39 · Week 2
Caching at scale: invalidation, hot keys and stampedes
A celebrity chef joins QuickBite, and one menu gets a million views in an hour. Today: what breaks in a cache at scale.
Got a doubt? Ask in the comments under the video.Subscribe
A celebrity chef's restaurant goes viral on QuickBite.
QuickBite is the food delivery app we grow through the course, from one server to millions of orders.
One cache for everyone
Yesterday, QuickBite's menus started loading from Redis in about a millisecond. Today, a famous chef opens a restaurant on QuickBite, and we find out what a cache does under real pressure.
First, a quick reminder of why the cache is shared. Customers reach any of the app servers. If each server kept its own private cache, the same menu would sit in four places, possibly in four different versions. So all servers share one cache, Redis, in front of the orders DB. One copy of each menu, one place to update it.
A shared cache gives three things. Every server sees the same data. There's one place to delete an entry when a menu changes. And memory is used once, instead of four times. The price is one network hop to Redis, about half a millisecond, which is still forty times faster than the database.
Stale data
There's an old joke that the hardest problem in computing is cache invalidation. It isn't really a joke.
There are three ways to keep cached data fresh. Expire every entry with a TTL: simple, but the data can be stale until it runs out. Delete the entry when the data changes: fresh, if you do it in the right order. Or update the entry on every write: fresh, but you pay the cost of writing twice, even for data nobody reads.
And the order matters. Write the database first, then delete the cache key. If you delete first, a reader can slip in between: it misses, reads the old price from the database, and puts it back in the cache, just before your write lands. Now the cache holds the old price until the TTL saves you. Database first, delete second.
Hot keys
Now the chef's launch. One menu, menu seven-seven-seven, gets a million views in an hour.
Our Redis isn't one machine anymore. Big caches are split across several machines, and each key lives on exactly one of them. So every one of those million reads lands on the same Redis machine, the one node holding menu seven-seven-seven, while the other machines sit almost idle. That's a hot key: one key with so much traffic that its home machine melts.
There are three standard fixes. Copy the hot key to several replicas, and read from any of them. Keep a tiny local copy inside each app server for about five seconds, so most reads never leave the server at all. Or spread it: store eight copies under eight different keys, and pick one at random. All three trade a few seconds of staleness for not falling over.
The stampede
The worst moment of the launch comes exactly ten minutes in, when the menu's TTL runs out.
The cached menu expires. In the next second, ten thousand requests ask for it, and every one is a miss. Every one goes to the database to rebuild the same menu at the same moment. The database, which was quietly handling a tenth of the reads, suddenly gets ten thousand identical queries, and falls over. This is called a stampede, or the thundering herd.
Three fixes. Coalesce requests: the first miss takes a short lock and rebuilds the menu, while the others wait a few milliseconds and read the fresh copy. Refresh early: when a hot key is close to expiring, one request quietly rebuilds it before anyone misses. And add jitter: random TTLs, like ten minutes plus or minus one, so thousands of keys don't all expire in the same second.
Warming the cache
Some of this can be avoided entirely, because QuickBite knew about the launch a week in advance.
A cold cache is empty, so its first minutes are all misses. Warming it means loading the menu into the cache before the launch, so the very first customer gets a hit. Teams do the same after restarting a cache, or before a big sale: they pre-load the keys they know will be popular.
So QuickBite's launch checklist looks like this. Warm the keys that will be hot. Add replicas or local copies for them before the traffic arrives, not during. And watch the hit rate live, because a falling hit rate is the first sign of a stampede, a full minute before the database alarms go off.
In the interview
These three problems come up as follow-ups whenever you add a cache. Have the answers ready.
Say this: on a write, I'll update the database and then delete the cache key; I'll spread hot keys across replicas; and I'll coalesce misses, so a single expiry can't stampede the database. That's freshness, hot keys and stampedes, covered in one breath.
Expect these. Why not update the cache on every write? Because most written data isn't read soon, so you'd do the work for nothing. What happens when a hot key expires? Without coalescing, a stampede. And one key gets a thousand times the traffic of the others? Replicas, a local copy, or spreading it across keys.
The common mistake is treating a cache as pure upside. Interviewers want to hear that you know how a cache fails: stale data, hot keys and stampedes.
Quick check
At exactly 1:00 PM, the database CPU jumps to 100%, while the cache looks fine. What happened?
Show the answer
Stampede: a hot key expired, and every request missed at once. Coalesce the refill.
You delete the cache key, then write the database. What can go wrong?
Show the answer
A reader can refill the old value in between, and the cache stays stale until its TTL.
Remember three things. Database first, then delete the key. Hot keys need replicas or local copies. And stampedes are stopped by coalescing, refreshing early and jitter. The chef's launch went fine, by the way. The photos, though, are another story.
Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.