Cost-aware eviction: the policy family that can be badly wrong

When miss costs differ by orders of magnitude, why is hit rate the wrong objective?

When entries differ in size and in miss cost, the right quantity to maximize is value density:

Two well-known policies use it:

• GreedyDual-Size evicts the entry with the minimum of (c/s + L), where c is the miss cost, s the size, and L an inflation term that rises over time and so ages old entries.
• GDSF (GreedyDual-Size-Frequency) adds the access frequency f and evicts the minimum of f · c / s.

This is the knapsack problem: maximize the value kept subject to a capacity. It is NP-hard (no known efficient exact method), and "greedy by density" is the standard approximation. This is the rule that exact answers are too expensive, so use sound approximations, in its textbook form.

The sharper point is about objective functions. A policy that is optimal for hit rate is, at worst, k-competitive on hits. A cost-blind policy, on a workload whose miss costs vary by three orders of magnitude, can be arbitrarily bad in time while being optimal in hit rate. It will happily evict the entry that takes 400 ms to rebuild in order to keep one that takes 100 µs to refetch, and it will report an excellent hit rate while doing so.

This matters more in data engineering than almost anywhere, because one system spans a warm in-memory page (~100 ns), a local NVMe disk (~100 µs), an object store (~50 ms) and a recompute (~400 ms): six orders of magnitude of miss cost inside one process. The practical rule is blunt: never share one LRU across entry types with different miss costs. Partition by cost class.

This is the third independent argument that arrives at partitioned capacity, after the unbounded negative-key space (The derivation ladder) and the marginal hit-rate allocation (What makes data cacheable). When three unrelated derivations arrive at the same structure, that structure carries the load.

One honest caveat. Cost-aware policies need measured costs, and the measured origin latency depends on the cache's own hit rate. The policy is a controller in a feedback loop with the quantity it measures, and such loops can oscillate (the same shape as autoscaling that flaps between sizes). To damp it, use a slow-moving average of the cost, not the instant value.

Compression: Value density f · c / s is a knapsack, so use greedy. With six orders of magnitude of miss cost in one system, hit rate is the wrong objective, and one shared LRU is a mistake.