The Break-Even Hit Rate for Adding a Cache

Adding a cache is the most frequently proposed optimization and the one whose break-even condition is most often left unstated. The intuition is that a hit is cheap and a miss is the same cost as before, so the cache can only help. The intuition omits the hit check on the miss path, which is the majority of the accesses whenever the hit rate is low, and it omits the change in the backing system when the cache is present.

Written out, the arithmetic is short and it produces a threshold that can be compared against a measured hit rate before any code is written.

Two costs and one threshold

Let $c_h$ be the cost of a hit (the lookup plus the delivery of the cached value), $c_m$ the cost of a miss (the lookup plus the original operation), and $m$ the miss rate, so the hit rate is $1 - m$. The expected cost per access is

$$E[c] = (1-m),c_h + m,c_m = c_h + m,(c_m - c_h)$$

Without the cache the cost is the original operation’s cost $c_0$. The cache wins when $c_h + m(c_m - c_h) < c_0$, which rearranges to a condition on the miss rate:

$$m < \frac{c_0 - c_h}{c_m - c_h}$$

Since $c_m = c_h + c_0$ when a miss is a hit check followed by the original operation, this simplifies to $m < (c_0 - c_h)/c_0$, or a hit rate above $c_h/c_0$. The threshold is the ratio of the lookup cost to the cost of the operation being cached. Caching an operation that takes a hundred nanoseconds with a lookup that takes ten has a break-even hit rate of ten percent; caching an operation that takes a hundred nanoseconds with a lookup that takes eighty has a break-even hit rate of eighty percent, and is nearly pointless.

The formula is exact only for a single-cache scenario with an unchanged backing cost, which is a useful fiction rather than a description. Its value is in making the threshold explicit: the question is no longer “will a cache help?” but “is the hit rate above $\rho_{\min}$, and is the lookup below $\rho_{\min} c_0$?”

What a lookup really costs

The cost $c_h$ is not a constant. It is a composition of the address computation, the hash and its probe sequence, the memory access to the entry, and the validation of the entry’s freshness. At the scale of a CPU cache, the lookup is a few cycles and the ratio $c_h / c_0$ is small only when the operation being cached is a memory access of a few tens of cycles; caching a multiply is a loss because the multiply is a cycle and the lookup is several.

At the scale of a remote cache — a Redis instance, a memcached cluster, a CDN — the lookup involves a network round trip, and the ratio is entirely different. A cache hit that costs a network round trip of a fraction of a millisecond is cheap only if the thing it replaced cost several milliseconds. This is the reason remote caches are heavily favoured for data whose source is a query over a disk-backed store and heavily disfavoured for data whose source is a local in-memory computation.

At the scale of a process-local cache, the cost includes the memory the entries occupy, which is charged not to the lookup but to the whole program: every byte of cache displaces a byte of something else, and on a machine near its memory bandwidth or near its cache capacity, the displacement has a cost that appears in unrelated code. This is the first of several cost shifts a cache makes, and the reason a cache that measures well in isolation can slow down a system that was already bandwidth-bound.

Why a miss can cost more than the original

The formula above assumes that a miss costs exactly what the uncached operation cost. Three effects break that assumption in the wrong direction.

The first is that the original operation now competes with the cache for the memory it uses. A cache that occupies a large fraction of a shared working set reduces the hit rate of the hardware cache for everything else, and the cost of that reduction is spread across the program. This is not hypothetical: an application-level cache of intermediate results frequently evicts the data the hot loop was walking, and the hot loop slows down while the cache appears to pay for itself.

The second is stampede behaviour. When a popular entry expires, the requests that would have hit it now miss simultaneously, and the backing store sees a burst equal to the request rate rather than the miss rate for a short interval. The average cost model does not see the burst; the system sees it as a latency spike and, if the backing store is near saturation, as a queue that takes time to drain. The mitigation — early refresh, request coalescing, jittered expiry — adds cost to the hit path, raising $c_h$ and therefore the break-even hit rate. The economics are circular: protecting against the burst is itself an optimization with its own threshold.

The third is invalidation. In a system where the cached value can change, the cache must be told, and the telling costs a message or a poll on every write. That cost is not on the read path, so it does not appear in the break-even formula, but it is part of the total. A cache whose invalidation traffic equals its saving traffic has moved cost from the read path to the write path, which is the fourth kind of cost shift and not an improvement in total cost.

The conditions under which the hit rate is what it looks like

Even a cache with a favourable hit rate has to be measured under the distribution that will be served. Several properties of the access distribution determine whether the measured hit rate transfers.

Skew determines the achievable hit rate for a given capacity: an access distribution weighted heavily toward a small set of keys yields high hit rates at small capacity, and a near-uniform distribution yields essentially none regardless of capacity. A cache sized by memory budget and evaluated on a synthetic workload with uniform keys will appear to fail while a real workload with the same average request rate hits well.

Reuse distance determines which of the evicted entries would have been needed. A cache that evicts exactly the entry needed next has a hit rate near zero while holding a full complement of recently used, never again used entries. Workloads that scan large ranges exhibit this pattern precisely, which is why the common advice about ordering keys for locality is really advice about reuse distance.

Capacity determines the asymptote. A cache that holds a smaller working set than the hot set has a hit rate that does not improve with more traffic, only with more capacity. Increasing the capacity has a cost that is not in the formula at all: memory, eviction work, and warmer start-up transients after each restart. A cache that takes minutes to warm after a deploy has an availability cost paid at the worst time.

Deciding with the model rather than after the implementation

Run in advance, the break-even arithmetic does two useful things. It disqualifies the caches that cannot pay — an operation costing under a hundred nanoseconds that would need a distributed lookup, a data set with a uniform distribution and a capacity below the hot set — without the cost of building them. And it converts the hit rate from a goal into a specification: the implementation must achieve a hit rate above $\rho_{\min}$ on the traffic mix that will be served, and the measurement plan is designed around that number rather than around an overall “did it help” comparison.

Where the threshold lands close to the achievable hit rate, the cache is not a win but a coin flip, and the interaction with everything else in the profile dominates. That situation is best treated as a cost-shifting question — where does the saved time re-emerge — and as a candidate whose expected payoff must carry a probability that reflects how little margin the threshold leaves.