Miss penalty and the percentile you promised

Why does a cache's value scale with the miss penalty, and why can it not improve the tail?

Mean latency is h·t_hit + (1 − h)·t_miss. Differentiate with respect to h: d(mean)/dh = −(t_miss − t_hit). So the marginal value of hit rate is constant in h and proportional to the miss penalty, while the marginal cost of hit rate is multiplicative (The popularity exponent). The optimum is where the two cross.

The design guidance is the opposite of what teams usually do: cache in front of the slowest thing, not the most-requested thing.

The first saves about 105 times more time, even though its hit rate is less than half.

The tail rule

At hit rate h, every percentile above h is made entirely of misses. A cache at 95% cannot improve p99. It cannot even improve p95. The full statement is:

If your promise is p99, you need h > 0.99. By the same exchange rate, that is usually unaffordable. Therefore tail latency is not a caching problem. It is fixed by shrinking t_miss (adding a tier), by hedging the miss (sending a duplicate request to a second replica after a short wait and using whichever answer returns first), or by shedding (refusing some work under overload). A great deal of wasted cache spend comes from attacking a p99 target with a mean-latency instrument.

Hits are not free

There is an assumption nobody states: a hit costs time. For a distributed cache, t_hit is a network round trip of 0.3–1 ms. That is slower than a local NVMe read (~100 µs) and about three orders of magnitude slower than a warm buffer-pool page (~100 ns). A remote cache placed in front of a fast local store loses on hits and loses again on misses (a miss pays the cache round trip and then the store read). This inversion is common in practice, and a naive drawing of the hierarchy encourages it (A distributed cache is not a latency tier).

In one sentence: value scales with the miss penalty, not the request count; a cache cannot improve any percentile above h; and hits cost a round trip.