  Many recent caching systems aim to improve miss ratios, but there is no good
sense among practitioners of how much further miss ratios can be improved. In
other words, should the systems community continue working on this problem?
Currently, there is no principled answer to this question. In practice, object
sizes often vary by several orders of magnitude, where computing the optimal
miss ratio (OPT) is known to be NP-hard. The few known results on caching with
variable object sizes provide very weak bounds and are impractical to compute
on traces of realistic length.
  We propose a new method to compute upper and lower bounds on OPT. Our key
insight is to represent caching as a min-cost flow problem, hence we call our
method the flow-based offline optimal (FOO). We prove that, under simple
independence assumptions, FOO's bounds become tight as the number of objects
goes to infinity. Indeed, FOO's error over 10M requests of production CDN and
storage traces is negligible: at most 0.3%. FOO thus reveals, for the first
time, the limits of caching with variable object sizes. While FOO is very
accurate, it is computationally impractical on traces with hundreds of millions
of requests. We therefore extend FOO to obtain more efficient bounds on OPT,
which we call practical flow-based offline optimal (PFOO). We evaluate PFOO on
several full production traces and use it to compare OPT to prior online
policies. This analysis shows that current caching systems are in fact still
far from optimal, suffering 11-43% more cache misses than OPT, whereas the best
prior offline bounds suggest that there is essentially no room for improvement.
