CSR: Small: Effective Sampling-based Miss Ratio Curves: Theory and Practice

缓存，如用于键值存储的分布式内存缓存，通常对整体系统性能起着关键作用。将高速缓存未命中率与高速缓存大小联系起来的未命中率曲线(MRC)是高速缓存管理的有效工具。该项目开发了一种新的缓存局部性理论，可以显著减少MRC构建的时间和空间开销，从而使其适合于在线评测。这项研究将从软件和硬件两个方面影响系统设计，因为几乎每个系统都涉及多种类型的缓存。因此，结果可以使从个人台式机到大型数据中心的各种系统受益。我们将把我们的成果集成到现有的开源基础设施中，供业界采用。此外，该项目将提供新的课程材料，以激励核心计算机科学的研究和实践。该项目调查了一种新的缓存局部性理论，将其应用于几个缓存或内存管理系统，并检查不同的在线随机抽样技术的影响。该理论引入了平均回收时间的概念，便于对缓存中的数据移动进行建模。该模型构造了可有效采样的数据重用分布的MRC。该模型产生了恒定的空间开销和线性时间复杂度。重点研究了该模型的理论性质和局限性，并与现有的MRC模型进行了比较。通过这个轻量级模型，该项目寻求指导硬件缓存分区，改进虚拟系统中的内存需求预测和管理，并优化键值内存缓存分配。

Caches, such as distributed in-memory cache for key-value store, often play a key role in overall system performance. Miss ratio curves (MRCs) that relate cache miss ratio to cache size are an effective tool for cache management. This project develops a new cache locality theory that can significantly reduce the time and space overhead of MRC construction and thus makes it suitable for online profiling. The research will influence system design in both software and hardware, as nearly every system involves multiple types of cache. The results can thus benefit a wide range of systems from personal desktops to large scale data centers. We will integrate our results into existing open source infrastructure for the industry to adopt. In addition, this project will offer new course materials that motivate core computer science research and practice.The project investigates a new cache locality theory, applies it to several caching or memory management systems, and examines the impact of different online random sampling techniques. The theory introduces a concept of average eviction time that facilitates modeling data movement in cache. The new model constructs MRCs with data reuse distribution that can be effectively sampled. This model yields a constant space overhead and linear time complexity. The research is focused on theoretical properties and limitations of this model when compared with other recent MRC models. With this lightweight model, the project seeks to guide hardware cache partitioning, improve memory demand prediction and management in a virtualized system, and optimize key-value memory cache allocation.