Practical Bounds on Optimal Caching with Variable Object Sizes
Practical Bounds on Optimal Caching with Variable Object Sizes
复制标题
可变对象大小的最佳缓存的实际界限
DOI：
10.1145/3224427
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Harchol-Balter, Mor
中科院分区：
文献类型：
--
作者：
Berger, Daniel S.;Beckmann, Nathan;Harchol-Balter, Mor
许多最近的缓存系统旨在提高未命中率，但有没有良好的感觉，从业者有多少进一步的未命中率可以改善。换句话说，系统社区是否应该继续解决这个问题？目前，对这个问题没有原则性的答案。在实践中，对象大小通常会变化几个数量级，其中计算最佳未命中率（OPT）已知是NP困难的。少数已知的结果缓存与可变的对象大小提供了非常弱的界限，是不切实际的计算上的痕迹的现实长度。我们提出了一种新的方法来计算上下限的OPT. Our关键的洞察力是代表缓存作为一个最小成本的流问题，因此，我们称我们的方法为基于流的离线最优（FOO）。我们证明，在简单的独立性假设下，FOO的界限变得紧密的对象的数量趋于无穷大。事实上，FOO在1000万次生产CDN和存储跟踪请求上的错误可以忽略不计：最多0.3%。因此，FOO第一次揭示了可变对象大小缓存的局限性。虽然FOO非常准确，但在具有数亿请求的跟踪上，它在计算上是不切实际的。因此，我们扩展FOO，以获得更有效的界限OPT，我们称之为实用的基于流的离线最优（PFOO）。我们评估PFOO的几个完整的生产跟踪，并使用它来比较OPT以前的在线政策。这个分析表明，目前的缓存系统实际上仍然远远不是最佳的，遭受11- 43%以上的缓存未命中比OPT，而最好的先验离线界限表明，基本上没有改进的余地。
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.
登录
查看更多内容
DOI：
10.1109/tnet.2018.2793581
发表时间：
2016-04
期刊：
IEEE/ACM Transactions on Networking
影响因子：
--
作者：
Stratis Ioannidis;E. Yeh
通讯作者：
Stratis Ioannidis;E. Yeh
DOI：
10.1016/s0166-5316(01)00045-1
发表时间：
2001-10
期刊：
Perform. Evaluation
影响因子：
--
作者：
D. Starobinski;David Tse
通讯作者：
D. Starobinski;David Tse
具有马尔可夫相关请求的自组织列表的前移规则·
DOI：
10.1007/978-1-4612-0801-3_5
发表时间：
1995
期刊：
--
影响因子：
--
作者：
R. Dobrow;J. A. Fill
通讯作者：
J. A. Fill
使用马尔可夫调制请求序列的移至前端算法的性能
DOI：
10.1016/s0167-6377(99)00037-1
发表时间：
1999
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
E. Coffman;P. Jelenkovic
通讯作者：
P. Jelenkovic
DOI：
10.1145/2896377.2901459
发表时间：
2016-06
期刊：
Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science
影响因子：
--
作者：
Andrés Ferragut;Ismael Rodríguez;F. Paganini
通讯作者：
Andrés Ferragut;Ismael Rodríguez;F. Paganini