Caching
Keep answers close so the database does not have to give them again: cache-aside, hit ratios, TTLs, invalidation, eviction, and the stampede when a hot key expires.
An interactive System Design lesson: 23 steps, about 32 minutes, on a live simulation in your browser.
The profile page of a social app shows a user's name. client asks app for user:7, and app asks the database, db, which spends 20 ms finding the row. The answer, Ken, comes back after 46 ms.
Of those 46 ms, 20 are the query. The network hops are short; the database is the slow part. And it is the same answer every time: user:7 has been Ken for years.
What you will learn
Every read hits the database
- Every read goes to the database: The slowest hop in a read is usually the database doing work it has already done before.
- Break it: the database saturates: When the database is the bottleneck, every request pays for its queue. Reads of data that has not changed are the cheapest load to remove.
Cache-aside
- Cache-aside: the first read misses: In cache-aside the application does the work: check the cache, fall back to the database on a miss, and fill the cache with what it found.
- The second read: A hit costs one hop to the cache instead of a query; its latency is mostly the network you cannot remove.
- What cache-aside looks like in code: Cache-aside is read-from-cache, else read-from-database-and-fill. The cache is an optimisation the application manages, never the source of truth.
- Drill: fill the cache with a TTL
Why a small cache works
- A small cache, skewed traffic: Hit ratio depends on the traffic, not only on the cache size. Under skewed popularity a cache holding a fifth of the keys absorbs over half of the reads.
- Same cache, flat traffic: A cache works because popularity is skewed. Size it by the working set that gets reused, and check that the misses left over fit under the database's capacity.
Stale data and writes
- TTL: every answer has an expiry date: A TTL is the longest you are willing to serve an answer without checking it. It trades freshness for hit ratio, one key class at a time.
- A write, then a read: A cache that nobody tells about writes serves stale data for up to one TTL, silently. The TTL is the upper bound on your staleness, not a fix for it.
- Invalidate on write: Invalidate on write: update the database, then delete the cached key. Keep a TTL anyway; it is the safety net for the races invalidation cannot close.
- Drill: invalidate by hand
- Write-through: the cache writes the database: Write-through keeps the cache current by writing through it, at the cost of slower writes and caching things nobody reads.
- Break it: write-behind loses writes: Write-behind acknowledges before the database has the data. A cache crash inside the flush window loses writes the users were told were saved.
When the cache is full
- Full: who gets evicted?: LRU bets that what was used recently will be used again soon. It evicts by last use, so reading a key keeps it alive.
- LFU, FIFO, and the scan that flushes LRU: LRU evicts by recency, LFU by frequency, FIFO by age. A one-off scan flushes an LRU cache; a formerly hot key clogs an LFU one.
Cold caches and stampedes
- Break it: the cache restarts cold: A cache hides how much load the database would carry without it. Restart the cache and the database gets that load back until the cache warms up.
- The hot key expires: A thundering herd is many requests missing on the same key at once. Its size is the request rate times the time it takes to refill the key.
- Single flight: one miss fetches: Single flight collapses concurrent misses for one key into one fetch. The database sees one query per expiry, however hot the key.
- Serve stale while you refresh: Stale-while-revalidate trades a sliver of freshness for zero waiting: an expired entry is served while one request refreshes it in the background.
Recap & playground
- What to cache, and what not to: Cache what is read often, changes rarely, costs a lot to produce and may be slightly stale. Everything else pays the staleness bill for no gain.
- Cheat sheet
- Playground