Abstract: Abstract: Because of the limited write endurance of solid state drives (SSDs), the write amount of SSD cache becomes another important critical metric to measure cache replacement algorithms except for the cache hit rates. Therefore, how to improve the overall quality of the cached data for longer lifetime of SSDs, i.e., promoting the efficiency of transforming cache writes into cache hits, is very important for the cache replacement algorithms. At present, most of the existing cache replacement algorithms reply on temporal locality, i.e., the recently accessed data usually have a high possibility to be requested soon with the result of requiring frequent data updates and a high write pressure for SSDs to ensure a high hit rate. Some improved algorithms prevent some least accessed data reducing write amounts through a high cost. A solution aiming at improving the overall quality of cached data based on the observed long-term law of data popularity with low overhead is required. This paper proposes a cache replacement algorithm called folded access sequence (FAS) for the SSD read cache. FAS is designed to identify the long-term hot data with only a low overhead, leading to higher quality of cached data in SSDs, high hit rates, reduced amounts of written data to SSDs, and longer SSD lifetime. The experimental results show that FAS can reduce the SSD writes by 90% compared with the traditional LRU (least recently used) algorithm and the hit rate loss does not exceed 10%. Compared with the improved cache algorithms like SieveStore and L2ARC (level 2 adjustable replacement cache), FAS's write amount is reduced for more than 50% with similar hit rates. The results exhibit that the proposed FAS can effectively keep high-quality cached data, reduce the written amounts to SSDs, and extend the SSD lifetime.

Key words: solid state drive (SSD), cache, SSD lifetime, folded access sequence, cache replacement

摘要： SSD（solid state drive）的写入寿命比较有限，因此除命中率外，SSD缓存设备的写入量成为评价缓存替换算法的另一个关键指标。如何使算法提高写入数据转化为缓存命中的效率，从而延长SSD的使用寿命，具有重要的研究意义。目前，已有缓存替换算法的设计一般基于时间局部性，即刚被访问的数据短期内被访问的概率较高，因此需要频繁的数据更新和较高写入量来保证较高命中率；或是通过不低的开销屏蔽相对最差的部分数据来减少一定的写入量，还缺少用低开销获得数据长期热度规律，有效提高缓存数据质量的算法。提出了访问序列折叠的缓存替换算法，用比较低的开销定位拥有长期稳定热度的数据写入缓存，明显提高了SSD缓存数据质量，在保证命中率的同时减少了SSD的写入量。实验表明，访问序列折叠算法相比LRU（least recently used）算法可在命中率损失低于10%的情况下减少90%的写入量，与SieveStore、L2ARC（level 2 adjustable replacement cache）等写入优化缓存算法相比，命中率相当时可将写入量减少50%以上，有效达到了通过缓存高质量数据，减少SSD的写入量，延长其使用寿命的目的。

关键词: 固态硬盘（SSD）, 缓存, SSD寿命, 访问序列折叠, 缓存替换