Beating OPT with Statistical Clairvoyance and Variable Size Caching
Beating OPT with Statistical Clairvoyance and Variable Size Caching
复制标题
DOI：
10.1145/3297858.3304067
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Pengcheng Li;Colin Pronovost;William D. Wilson;B. Tait;Jie Zhou;C. Ding;J. Criswell
中科院分区：
文献类型：
--
作者：
Pengcheng Li;Colin Pronovost;William D. Wilson;B. Tait;Jie Zhou;C. Ding;J. Criswell
缓存技术在当今的计算基础架构中广泛使用，从虚拟内存管理到服务器缓存和内存缓存。本文以两个观察为基础。首先，可以根据动态应用程序需求改变缓存大小来改进缓存中的空间利用率。其次，从统计学上预测应用程序行为比精确预测应用程序更容易。本文提出了一个新的变量大小缓存，该缓存使用程序行为的统计知识来最大程度地提高缓存性能。我们使用实际工作负载中的数据访问轨迹来衡量性能，包括来自Facebook的MEMCACH TRACE和Microsoft Research的存储跟踪。在离线设置中，新的缓存被证明超过了OPT，即最佳的固定尺寸缓存，它利用了程序行为的精确知识。
Caching techniques are widely used in today's computing infrastructure from virtual memory management to server cache and memory cache. This paper builds on two observations. First, the space utilization in cache can be improved by varying the cache size based on dynamic application demand. Second, it is easier to predict application behavior statistically than precisely. This paper presents a new variable-size cache that uses statistical knowledge of program behavior to maximize the cache performance. We measure performance using data access traces from real-world workloads, including Memcached traces from Facebook and storage traces from Microsoft Research. In an offline setting, the new cache is demonstrated to outperform even OPT, the optimal fixed-size cache which makes use of precise knowledge of program behavior.