一种针对非易失内存读缓存的写高效缓存算法
MacroTrend: A Write-Efficient Cache Algorithm for NVM-Based Read Cache
-
摘要: 1、研究背景（context）：
近年来非易失内存已经开始实际应用，闪存、相变存储器已经应用非常广泛，ReRAM、STT-MRAM等也在逐渐接近产品化。这些非易失内存由于访问速度快，但价格较为昂贵，非常适合作为下层慢速存储设备的读缓存。但是这些非易失内存的写操作一般都存在一些挑战，包括写操作一般显著慢于读操作、写操作过多会提前损耗设备、写操作能耗过大等。因此，传统的缓存替换算法，如LRU和LFU等，会给非易失内存读缓存造成过大的写入压力，并不适合非易失内存。
2、目的（Objective）：
我们研究的目的是为非易失内存读缓存提出一种写高效的缓存算法，通过对长期热门数据的准确识别，在读缓存中长期保存长期热门数据，减少缓存数据块的交换，从而减小读缓存的写入压力，但同时能够保持较高的缓存命中率。
3、方法（Method）：
我们提出了一个长期热门数据的预测框架MacroTrend，追踪数据块在过去多个历史周期内的访问量变化规律，来准确挖掘长期热门数据。在对企业访问记录进行大量分析中，我们发现一些长期热门数据的历史访问量变化趋势的典型模式，包括稳定性模式S-pattern、连续性模式C-pattern、不规则模式I-pattern。如果数据块的历史访问量变化趋势符合越多的模式，那么它们越可能是长期热门数据。有别于已有缓存替换算法大都使用LRU等短期热门数据识别方法来选择数据，我们提出的新型写高效缓存替换算法MT采用了这种长期热门数据预测框架，从而比传统方法用更少的写入量得到更好的缓存命中率。
4、结果（Result & Findings）：
在基于实际企业访问记录的实验中，MT算法相对于经典的LRU算法可以减少平均95.3%的非易失内存读缓存的写入压力，同时缓存命中率比LRU提高24.0%。相对于同样提高缓存写效率的SieveStore算法，MT可以减少85.2%的写压力，同时将缓存命中率提升50.2%。
5、结论（Conclusions）：
结果说明MT算法在提升读缓存的写效率方面非常有效，主要原因是从热门数据选择方法上相对传统方法有了本质性的提升，通过准确识别长期热门数据，不需要频繁更新缓存数据，就可以得到更高的缓存命中率。MT算法在企业级存储系统中有广泛的应用场景，非常适应目前多种非易失内存器件快速发展、混合存储在企业中广泛应用的情况，有助于提升混合存储性能、延长非易失内存设备的使用寿命，以及降低其能耗。Abstract: The future storage systems are expected to contain a wide variety of storage media and layers due to the rapid development of NVM (non-volatile memory) techniques. For NVM-based read caches, many kinds of NVM devices cannot stand frequent data updates due to limited write endurance or high energy consumption of writing. However, traditional cache algorithms have to update cached blocks frequently because it is difficult for them to predict long-term popularity according to such limited information about data blocks, such as only a single value or a queue that reflects frequency or recency.In this paper, we propose a new MacroTrend (macroscopic trend) prediction method to discover long-term hot blocks through blocks' macro trends illustrated by their access count histograms. And then a new cache replacement algorithm is designed based on the MacroTrend prediction to greatly reduce the write amount while improving the hit ratio. We conduct extensive experiments driven by a series of real-world traces and find that compared with LRU, MacroTrend can reduce the write amounts of NVM cache devices significantly with similar hit ratios, leading to longer NVM lifetime or less energy consumption.
下载: