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

缓存，例如用于键值存储的分布式内存缓存，通常在整体系统性能中起着关键作用。未命中率曲线（MRCs）将高速缓存未命中率与高速缓存大小联系起来，是高速缓存管理的有效工具。这个项目开发了一个新的缓存局部性理论，可以显着减少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.