一种新型缓存模型的理论及其应用研究

Caching is ubiquitous across different layers of software and hardware stack. Cache performance is thus critical for all computer systems from a single device to a large scale data center. Modeling and predicting cache performance can have a substantial impact. Unfortunately, caching has not been well-understood yet despite numerous efforts in the past. The reason is that there lacks an effective new theory behind cache modeling and a systematic theoretical and experimental study to verify the hypotheses and limitations of the existing caching theories and compare their effectiveness in practice. Our proposed research will introduce a new theory to model cache and construct miss ratio curves (MRC). This new theory can lead to an accurate MRC with minimal time and space overhead. Specifically, this research will develop: a new cache model based on average eviction time (AET) to construct miss ratio curves effectively; a systematic comparison of recent cache models, including AET; theory and practice for hardware cache partitioning, memory management in a virtualized system; and key-value memory cache management. We expect both the theory and practice developed in this proposal will significantly advance our understanding of locality and cache modeling. The applications of the AET model will help improve all levels of caches from processor caches to storage buffers and thus benefit all computer systems.

各类计算机系统中都有缓存的身影，其性能对整个系统的性能至关重要。对缓存性能进行建模和预测是一项有重要影响的研究。但到目前为止还没有非常有效的缓存建模理论。本研究希望引入一种新的缓存建模理论（AET模型）并据此构建缓存失效率曲线（MRC），该理论以平均淘汰时间为基础，可实现用最小化时间代价和空间开销来准确推算MRC。本研究将把该模型与近年来各种新型模型进行系统化地全面对比研究，并通过实验来检验这些模型所基于的启发策略与分布假设，并研究不同的采样技术与策略对各种模型精度的影响。同时研究如何将AET模型应用于对硬件缓存划分的指导、虚拟化机内存需求的预测与管理，以及键值对的内存缓存管理等应用场景之中。本申请中的理论和技术将显著提升我们对局部性和缓存建模的理解。AET模型的应用也将会帮助提升从处理器缓存到外存缓存等各个级别的缓存性能，进而有益于各类计算机系统的优化。

本项目围绕AET缓存模型的理论性质和应用特性，重点研究了该模型在各类软硬件系统的优化中的适用性和效果。.AET、CounterStack和SHARD等模型是最新的三种最好的局部性模型，它们都是基于统计方法的预测模型。AET模型独具可组合性，可用于共享缓存的建模分析，在空间开销和时间开销也有一定优势。AET模型适合于采用随机采样（精确度高）或蓄水池采样（常数空间开销）等采样方法。.键值对缓存与传统硬件缓存相比，存在对象大小跨度大、访问缺失惩罚变化幅度大、并且存在删除等特殊操作等差异。我们提出了更适用于键值对缓存的增强AET模型（EAET），并以此为基准优化了Redis系统的内存管理，实现了一个局部性和缺失惩罚感知的键值对缓存系统（pRedis），在平均访问延迟上有显著改善。.我们利用PEBS采样实现了应用程序末级缓存缺失率曲线的在线分析，并利用AET缓存模型的可组合性，实现了对多核上的程序在不同末级缓存划分方案下的总体性能的在线分析，求得最优方案，并利用Intel CAT技术对末级缓存进行划分。我们提出的基于部分共享的末级缓存划分方法相比完全共享和完全划分都具有更好的性能和适应性。.基于统计的模型都要求在关键点附近有足够多的采样数据，但高效的虚拟机内存需求预测与调控需要基于大页内存进行预测和调控，达不到AET模型对关键点附近采样规模的要求，因此我们采用了精确的基于重用距离的局部性模型来分析大页内存需求，并通过动态热页集过滤，大幅降低了大页监控开销（仅1.5%），预测误差不超过10%。在准确预测虚拟机内存需求的基础上，结合我们提出的内存分配大页对齐优化和内存气球驱动大页优化技术，我们实现了高效的虚拟机内存工作集预测和动态调控系统。.本项目研究表明，AET模型在处理器共享高速缓存划分优化、键值对缓存内存管理优化等方面应用效果显著；但其应用范围会受到对采样规模要求的限制。