Size a cache

For each access, count the distinct other items accessed since the previous access to the same item: its reuse distance. Under LRU an access hits exactly when its reuse distance is smaller than the cache, so one histogram gives the miss ratio for every cache size at once. Sample by hashing keys (keep a fixed share of keys), never by time window. If you cannot instrument it: count distinct items per window and fit how popularity falls with rank.

Fit the popularity exponent α: how steeply request share falls from the most popular item to the next. Above 1: the size needed for a given hit rate does not depend on how much data you have. At 1 or below (typical for web objects and analytic query shapes, 0.6–0.8): a fixed cache over growing data loses hit rate silently; budget for growth, or document the decay. At α = 0.8, a 90% hit rate needs about 59% of the corpus cached, which is replication, not caching.

Separate items that stay popular, items hot for a while (a session, a job's working set), and items touched once (scans, backfills). If the touched-once share is large: you need admission control that refuses those items, not a bigger cache. One scan larger than the cache evicts everything useful.

Miss-ratio curves have plateaus, where more capacity returns nothing, and cliffs, where a little more captures a whole working set. Land just past a cliff, never on a plateau. Do not believe "we doubled it and nothing happened" until you have looked at where on the curve you were. For a shared cache: split capacity so each tenant's miss ratio falls equally fast per extra gigabyte.

A new tier helps only if its hit rate beats its latency relative to the tier below: hit rate > its lookup time ÷ the lower tier's time. A tier 10× faster needs over 10%; local NVMe over object storage needs only 0.2%. Run the money version separately: with per-request storage pricing, an SSD tier over object storage pays at hit rates latency alone would not justify.

A cached result or view is worth keeping only if reads per version exceed cost to compute ÷ saving per hit. Reads per version is read rate ÷ invalidating writes, and for an object built from many inputs the writes are the sum over all of them. Many inputs is what usually fails this.

At hit rate h, the store sees only a share (1 − h) of the load, so the cache gives leverage of 1 ÷ (1 − h): 20 to 1 at 95%, 100 to 1 at 99%, and a one-point drop at 99% doubles the store's load. If the store cannot survive the cache being empty: the cache is a dependency, not an optimization. Plan for restarts: a warm-up ramp, or a cache that survives the process restarting.

A cache with hit rate h leaves every percentile above h exactly where it was: at 95% it cannot improve p95 or p99. If the promise is p99 and the hit rate is below 99%: caching is the wrong instrument. Shrink the miss cost instead (another tier), send a duplicate request to a second replica after a short wait (hedging), or shed load. Cache in front of the slowest thing, not the most-requested one: the saving per request is hit rate × miss penalty.