Art of Codeartofcode
Lesson 2 of 15

13. Caching at Scale

1
The picture to keep in your head
2
13.1 What is a cache stampede, and how do you stop one?
3
13.2 What is cache penetration?
4
13.3 What is a cache avalanche?
5
13.4 What is a hot key, and why can't sharding fix it?
6
13.5 How do you spread a cache across many machines?
7
13.6 What is cache warming?
8
13.7 How does HTTP caching work in browsers and CDNs?
9
13.8 How do you know your cache is healthy?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
13. Caching at Scale

13.1 What is a cache stampede, and how do you stop one?

3 min read+10 XP

When caches fail

At the wedding: The milk runs out at 1 pm. Fifty helpers notice at the same moment and all run to the shop to buy milk. The shop is swamped, and fifty cartons come back when one would have done. A sensible kitchen sends one person and tells everyone else to wait a minute at the fridge.

In the system: A cache stampede (also called a thundering herd or a dog-pile) happens when a popular key expires or is deleted, and many requests miss at the same moment. Each one goes to the database for the same data.

no protection: 100 requests send 100 queries; single flight: one loads, the rest wait.

Figure: with single flight, 100 simultaneous misses become 1 database query.

How bad: if the milk page gets 5,000 requests a second and rebuilding it takes 200 ms, about 1,000 requests arrive before the first one refills the cache (5,000 × 0.2, Little's law, Chapter 5). That's 1,000 identical queries at once, on the busiest key, at the busiest time.

Fixes:

  1. Single flight (request coalescing): the first request to miss becomes the leader and loads the data; others asking for the same key wait for the leader's result. Inside one server this is a small lock per key; across many servers it's a short-lived lock in the cache itself (for example a Redis key set only if it doesn't exist, with an expiry so a crashed leader doesn't block everyone forever).
  2. Leases: the cache hands out a token to the one client allowed to refill a missing key; others wait briefly or take a slightly stale value. Facebook described using leases in its memcache system for exactly this.
  3. Serve stale while refreshing: keep the old value a little past its TTL; when it's "soft-expired", return the old value immediately and let one request refresh it in the background.
  4. Refresh early, at random: let each request, with a small and growing probability as expiry approaches, refresh the value before it expires, so expiry never arrives for everyone at once (described as "probabilistic early expiration").

In the chapter's code, 100 concurrent misses on one key cause 1 database call with single flight. A subtle bug, where waiting requests query the database anyway after the leader finishes, brings it back to 100 (the Level 4 bug).

Memory code: "One person goes to the shop; everyone else waits at the fridge."