Caching: cache-aside, eviction, stampede
Why a cache's hit rate comes from key skew, how it sets database load, how to keep it fresh, and why a cold restart can take the database down.
25 min9 steps
By the end you can
- Explain why the hit rate emerges from key popularity skew and cache size
- Predict database load from request rate and hit rate, and the hit rate a database needs
- Trace the cache-aside read path on a miss and say who fills the cache
- Choose between TTL expiry and explicit invalidation for a freshness requirement
- Explain the stampede after a cache restart and how request coalescing prevents it
A database that cannot keep up
A database answers in about 5 ms and saturates at a few thousand reads/s. A cache answers in under 1 ms, for keys it holds. Hit rate = share of reads the cache answers.
- Cache hit0.5 ms
- Database read5 ms
Log scale: each gridline step is 10×.
Move the sliders: compare a 90% and a 99% hit rate.
Database load
Within capacity: 40%
- Mean read latency
- 1 ms
- If hit rate drops 1 point
- DB load +10%
Assumes a 500 µs cache lookup and a 5 ms database read; a miss pays both.
Predict the database load
database reads/s = request rate × (1 − hit rate)
- 90% hit rate1,000 reads/s
- 98% hit rate200 reads/s
- 99% hit rate100 reads/s
Loading question…
Follow a miss through cache-aside
Cache-aside: the application owns the cache. On a miss, the service reads the database and fills the cache itself.
Put the steps of a cache miss in order.
- 1Service writes the row to the cache with a TTL
- 2Service sends GET user:42 to the cache
- 3Cache replies that the key is missing
- 4Service reads user:42 from the database
- 5Service returns the response to the caller
Where the hit rate comes from
Key popularity makes hits. Reads are roughly Zipf: the top k of N keys get about H(k) / H(N) of requests. A cache of 1% of keys can serve over half the reads, and LRU nearly holds them.
Loading question…
Size the hit rate to the database
Turn the formula around: peak request rate and the database's limit give the minimum hit rate, including after a deploy or node loss.
Min hit rate
95%
1 − 500 / 10,000
After a cold restart
≈ 0%
Loading question…
Keep cached data fresh
A cached value is a copy and can go stale. TTL bounds staleness by time. Invalidation: the writer deletes the key after the database write.
Long TTL
- Cheap
- Old data for hours
Delete on write + TTL
- Fresh within delete latency
- TTL is the safety net
Very short TTL
- Always misses
- More DB load
The stampede after a restart
A node restarts empty. Every hot key misses at once; a database sized for 95% hits sees nearly all traffic: a stampede.
t0
Cache node restarts empty
t0 + 1 s
Every request misses; DB saturates
Later
Cache refills, hit rate recovers
Loading question…
Prevent the stampede
Leases (Facebook memcache) or request coalescing: the first miss fills the key, others wait and retry the cache.
Check your mastery, then build it
Score 80% or more. A wrong answer links back to its step.
Mastery check
5 questions on fresh variants. One attempt each, no time limit. Score 80% or more to master the lesson.
Run it in the cache-aside sandbox and watch the hit rate climb. Then take the challenge: keep reads fast through a cache restart.
Answer this step to continue.