Sizing a cache for a target hit ratio under Zipf popularity: an interactive calculator
How much memory a cache needs depends on how skewed the reads are. Popularity in real systems usually follows a power law, Zipf’s law: the item ranked i is read in proportion to 1 / is. With a strong skew a small cache absorbs most reads; with a long tail, each extra point of hit ratio costs a lot of memory. And a real LRU cache does worse than a perfect one, because one-off reads of unpopular items push popular ones out.
The playground reads 100 million items of 1 KB at 100,000 reads a second. Pick a skew and drag the cache size; the x axis is logarithmic.
100K reads a second over 100 million items of 1 KB, with typical popularity (s = 0.9). Caching 1% of the items, 1 GB, an LRU cache hits 46% of reads and leaves 54K a second for the database; a perfect cache of the same size would hit 57%. Reaching 90% takes 54 GB, 54% of the data.
What the curves say
- Skew decides everything. A 1 GB cache, 1% of the data, hits 86% of reads when s = 1.1, 46% when s = 0.9 and 13% when s = 0.7.
- The 80/20 rule is a special case. Caching the most popular 20% of items catches about 83% of reads at s = 0.9 and 97% at s = 1.1. Measure the skew from an access log instead of assuming it.
- The last few points are the most expensive. At s = 0.9 an LRU cache needs about 27 GB for 80% hits, 54 GB for 90% and 94 GB for 99%, almost the whole dataset.
- LRU is not a perfect cache. At the same size it trails the ideal by up to 14 points here, and much more under scans or one-off bulk reads. Admission policies such as TinyLFU, used in Caffeine, close much of the gap by refusing to cache items seen only once.
A back-of-the-envelope estimate
reads: 100K/s, items: 100M, item size: 1 KB → 100 GB of data
measured skew: s ≈ 0.9 (fit a line to log(rank) vs log(reads) in an access log)
target: 90% hit ratio → database sees 10K reads/s
LRU memory for 90%: ~54 GB (perfect top-k would need ~41 GB)
with overhead: ×1.5 for keys, pointers, fragmentation → ~80 GB
cluster: 3 nodes × 32 GB, plus a replica each for failover
sanity check: if the database can take 20K reads/s, an 80% hit ratio (~27 GB) is enoughIn a system design interview
Size the cache from the database, not from a rule of thumb: “The database can serve about 10,000 reads a second comfortably, and we expect 100,000, so the cache must hit at least 90%. With a typical Zipf skew, that needs roughly half of the data set in memory, about 54 GB plus overhead, so three 32 GB nodes with replicas.” Then mention what changes it: viral items that make the head hotter, scans that pollute LRU, and how the hit ratio drops after a restart while the cache is cold.
Read the guide to caching or back-of-the-envelope estimation, see LRU vs LFU vs FIFO and hot keys, or watch a strong candidate design a distributed cache.
Questions people ask
How do you estimate cache size?
Work back from the load the database can take: the hit ratio needed is one minus database capacity over total reads. Then use the popularity skew, measured from access logs, to find what share of items must be cached to reach that hit ratio, and multiply by item size plus overhead.
What is a Zipf distribution?
A power law in which the item ranked i is accessed in proportion to 1 / i^s. Web pages, videos, products and cache keys typically follow it with s between about 0.6 and 1.2: a few items get most of the traffic and a long tail gets the rest.
Does the 80/20 rule hold for caches?
Only for some skews. Caching the most popular 20% of items catches about 80% of reads when the Zipf exponent is near 0.9, far more when it is higher and far less when the tail is long. Measuring the actual distribution beats assuming the rule.
Why is an LRU hit ratio lower than expected?
LRU caches whatever was used recently, including items read only once, which evict popular ones. Its hit ratio is below that of a cache holding exactly the most popular items, and drops further under scans. Admission filters such as TinyLFU improve it.
What is Che’s approximation?
A method to estimate the hit ratio of an LRU cache under independent requests: each item stays cached if it is requested again within a characteristic time T, chosen so the expected number of cached items equals the cache size. It is accurate for large caches.
How much overhead does a cache add per item?
Beyond the value, each entry stores its key, pointers for the eviction structure and allocator overhead, often tens of bytes. For small values this can double memory use, so estimates usually add 30 to 100 percent on top of the raw data.
What happens to the hit ratio after a cache restart?
It starts at zero and climbs as popular items are read and cached, so the database briefly sees most of the traffic. Warming the cache before taking traffic, restarting nodes one at a time and keeping replicas avoid overwhelming the database.