A New Upper Bound on Cache Hit Probability for Non-anticipative Caching Policies
A New Upper Bound on Cache Hit Probability for Non-anticipative Caching Policies
复制标题
非预期缓存策略的缓存命中概率的新上限
DOI：
10.1145/3453953.3453985
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
D. Towsley
中科院分区：
文献类型：
--
作者：
Nitish K. Panigrahy;P. Nain;G. Neglia;D. Towsley
长期以来，缓存系统对于提高各种网络和基于Web的在线应用程序的性能至关重要。在这样的系统中，端到端应用程序的性能在很大程度上取决于从缓存传输的对象的比例，也称为缓存命中概率。为了提高命中概率，已经提出并实施了许多缓存驱逐策略。在这项工作中，我们提出了一种新的方法来计算所有非预期缓存策略的命中概率上限，即对于不知道未来请求的策略。在每个对象请求到达时，我们使用基于危险率(HR)函数的排序来将请求分类为命中或非命中。在一定的统计假设下，我们证明了我们提出的基于HR的排序模型计算了最大可实现的命中概率，并且作为所有非预期缓存策略的上限。给出了仿真结果，验证了其正确性，并与Belady的上界进行了比较。我们发现它几乎总是比贝拉迪的界限更紧。
Caching systems have long been crucial for improving the performance of a wide variety of network and web based online applications. In such systems, end-to-end application performance heavily depends on the fraction of objects transfered from the cache, also known as the cache hit probability. Many cache eviction policies have been proposed and implemented to improve the hit probability. In this work, we propose a new method to compute an upper bound on hit probability for all non-anticipative caching policies, i.e. for policies that have no knowledge of future requests. At each object request arrival, we use hazard rate (HR) function based ordering to classify the request as a hit or not. Under some statistical assumptions, we prove that our proposed HR based ordering model computes the maximum achievable hit probability and serves as an upper bound for all non-anticipative caching policies. We also provide simulation results to validate its correctness and to compare it to Belady's upper bound. We find it to almost always be tighter than Belady's bound.
可变对象大小的最佳缓存的实际界限
DOI：
10.1145/3224427
发表时间：
2018
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Berger, Daniel S.;Beckmann, Nathan;Harchol-Balter, Mor
通讯作者：
Harchol-Balter, Mor