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

缓存，例如用于键值存储的分布式内存缓存，通常在整个系统性能中起关键作用。缺失率曲线（MRCs）将缓存缺失率与缓存大小联系起来，是一种有效的缓存管理工具。本课题开发了一种新的缓存局域性理论，可以显著减少MRC构建的时间和空间开销，从而使其适合在线分析。这项研究将影响软件和硬件的系统设计，因为几乎每个系统都涉及多种类型的缓存。因此，其结果可以使从个人桌面到大型数据中心的各种系统受益。我们将把我们的成果集成到现有的开源基础设施中，以供业界采用。此外，该项目将提供新的课程材料，以激励核心计算机科学的研究和实践。该项目研究了一种新的缓存局部性理论，将其应用于几种缓存或内存管理系统，并检查了不同在线随机抽样技术的影响。该理论引入了平均清除时间的概念，便于对缓存中的数据移动进行建模。该模型构建的MRCs具有可有效采样的数据重用分布。该模型产生恒定的空间开销和线性时间复杂度。研究的重点是理论性质和该模型的局限性，并与其他最近的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.