Many recent caching systems aim to improve hit ratios, but there is no good sense among practitioners of how much further hit 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. Most prior work assumes that objects have the same size, but in practice object sizes often vary by several orders of magnitude  . The few known results for variable object sizes provide very weak guarantees and are impractical to compute on traces of realistic length. We propose a new method to compute the offline optimal hit ratio under variable object sizes . 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 show that, under simple independence assumptions and Zipf popularities , FOO's bounds become tight as the number of objects goes to infinity. From FOOwe develop fast, practical methods to compute nearly tight bounds for the optimal hit ratio, which we call practical flow-based offline optimal (P-FOO). P-FOO enables the first analysis of optimal caching on realistic traces with hundreds of millions of requests. We evaluate P-FOO on several production traces, where results show that recent caching systems are  still far from optimal  .
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 .
R
hit
miss
R
hit
miss
R
Most prior work assumes that objects have the same size, but in practice
In practice,
A
, where computing the optimal miss ratio (OPT) is known to be NP-hard
R
for
on caching with
R
guarantees
bounds
R
the offline optimal hit ratio under variable object sizes
upper and lower bounds on OPT
R
show
prove
D
and Zipf popularities
R
From FOOwe develop fast, practical methods to compute nearly tight bounds for the optimal hit ratio, which we call practical flow-based offline optimal (P-FOO). P-FOO enables the first analysis of optimal caching on realistic
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
R
evaluate P-FOO on several production traces, where results show that recent
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
A
in fact
A
, suffering 11-43\% more cache misses than OPT, whereas the best prior offline bounds suggest that there is essentially no room for improvement