A cache can't hold everything, and it doesn't need to. How big it should be depends on how concentrated the traffic is, and on what the misses cost you.
The working set
A cache works because a few items get most of the requests. The items that are asked for often enough to be worth keeping are the working set. If the cache holds the working set, most requests hit; if it holds only part of it, the rest miss and go to the database.
So the useful question is never "how big is the data?" but "how many items get most of the traffic?" A catalog of 50 000 products can be served mostly from a cache of a few thousand.
Eviction
When the cache is full and a new item arrives, something has to go. Most caches use LRU (least recently used): they drop the item nobody has asked for in the longest time.
| Cache holds 3 items | Request | Cache after (most recent first) |
|---|---|---|
| A, B, C | D (miss) | D, A, B (C evicted) |
| D, A, B | A (hit) | A, D, B |
| A, D, B | C (miss) | C, A, D (B evicted) |
Popular items keep getting requested, so they stay near the front; rarely asked-for ones drift to the back and fall out. LRU keeps roughly the working set without anyone having to say what it is.
Bigger caches, dearer hits
Doubling the cache doesn't double the hits. The first slots hold the most popular items, which bring the most hits; each later slot holds something less popular than the last, so it catches fewer reads. Under a typical skew, each doubling adds about the same number of points, but each doubling also costs twice as much memory as the one before.
A catalog of 10 000 items below, read with a typical skew. Move the cache size along, and then change how concentrated the reads are.
Skew decides
How concentrated the traffic is matters as much as the cache's size. With strong skew, a small cache already holds most of what's asked for. With traffic spread out, even a large cache misses a lot.
With nearly even reads, the same cache of 500 items catches under 10%. With strong skew, it catches about 93%. Look at the traffic before deciding how big a cache needs to be.
Paying for a cache
Memory costs far more per gigabyte than the disks a database keeps its data on, but it's cheap per read served: a hit takes a fraction of the work a database read does. A cache that takes half the reads off the database can let you run a smaller database, and the two together cost less than a big database alone. The catch: when the cache is cold (just after a restart) or fails, the full load lands on that smaller database, so it has to survive that, or the cache has to warm up before it takes traffic. But past the working set, every extra bit of cache costs more than the few misses it saves.
In the wild
The ideas in this chapter, and where you'll meet them in real systems and interviews:
| Idea | Where you'll meet it |
|---|---|
| Eviction | Redis maxmemory-policy allkeys-lru, Memcached's LRU |
| Watching hit rates | Redis INFO stats (hits and misses), cache dashboards in Datadog or CloudWatch |
Your practice
Inkwell Shop's catalog has grown to 50 000 products, served by a slow catalog database. Product pages have to load fast, and finance has a budget. Pick the cache and database that make most pages fast for the least money.