面向SSD寿命优化的访问序列折叠缓存替换算法
|
摘要
SSD(solid state drive)的写入寿命比较有限,因此除命中率外,SSD缓存设备的写入量成为评价缓存替换算法的另一个关键指标。如何使算法提高写入数据转化为缓存命中的效率,从而延长SSD的使用寿命,具有重要的研究意义。目前,已有缓存替换算法的设计一般基于时间局部性,即刚被访问的数据短期内被访问的概率较高,因此需要频繁的数据更新和较高写入量来保证较高命中率;或是通过不低的开销屏蔽相对最差的部分数据来减少一定的写入量,还缺少用低开销获得数据长期热度规律,有效提高缓存数据质量的算法。提出了访问序列折叠的缓存替换算法,用比较低的开销定位拥有长期稳定热度的数据写入缓存,明显提高了SSD缓存数据质量,在保证命中率的同时减少了SSD的写入量。实验表明,访问序列折叠算法相比LRU(least recently used)算法可在命中率损失低于10%的情况下减少90%的写入量,与SieveStore、L2ARC(level2 adjustable replacement cache)等写入优化缓存算法相比,命中率相当时可将写入量减少50%以上,有效达到了通过缓存高质量数据,减少SSD的写入量,延长其使用寿命的目的。
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 2adjustable 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.
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 2adjustable 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.
引文
[1]Boboila S,Desnoyers P.Write endurance in flash drives:measurements and analysis[C]//Proceedings of the 8th USENIX Conference on File and Storage Technologies,San Jose,Feb 23-26,2010.Berkeley:USENIX Association,2010:115-128.
[2]Grupp L M,Davis J D,Swanson S.The bleak future of NAND flash memory[C]//Proceedings of the 10th USENIXConference on File and Storage Technologies,San Jose,Feb14-17,2012.Berkeley:USENIX Association,2012:2-2.
[3]Rajimwale A,Prabhakaran V,Davis J D.Block management in solid-state devices[C]//Proceedings of the USENIX Annual Technical Conference,San Diego,Jun 14-19,2009.Berkeley:USENIX Association,2009:21.
[4]EMC fast cache a detailed review[R/OL].(2011-11-08)[2013-12].http://www.emc.com/collateral/software/white-papers/h8046-clariion-celerra-unified-fast-cache-wp.pdf.
[5]Woods M.Optimizing storage performance and cost with intelligent caching:WP-7107[R].2010.
[6]Leventhal A.Flash storage memory[M].ACM,2008.
[7]Oracle.Exadata smart flash cache features and the oracle exadata database machine[EB/OL].(2013).http://www.oracle.com/technetwork/server-storage/engineeredsystems/exadata/exadata-smart-flash-cache-366203.pdf.
[8]Intel Corporation.Intel solid-state drive 910 series:product specification[EB/OL].(2012-06).http://www.intel.com/content/www/us/en/solid-state-drives/ssd-910-seriesspecification.htmlLeventhal.
[9]Gregg B.ZFS L2ARC[EB/OL].(2008-07-22).http://www.brendangregg.com/blog/2008-07-22/zfs-l2arc.html.
[10]Huang S,Wei Q S,Feng D,et al.Improving flash-based disk cache with lazy adaptive replacement[J].ACM Transactions on Storage,2016,12(2):8.
[11]Pritchett T,Thottethodi M.SieveStore:a highly-selective,ensemble-level disk cache for cost-performance[C]//Proceedings of the 37th International Symposium on Computer Architecture,Saint-Malo,Jun 19-23,2010.New York:ACM,2010:163-174.
[12]Zhou Y Y,Philbin J,Li K.The multi-queue replacement algorithm for second level buffer caches[C]//Proceedings of the 2001 USENIX Annual Technical Conference on General Track,Boston,Jun 25-30,2001.Berkeley:USENIX Association,2001:91-104.
[13]Blaze M.NFS tracing by passive network monitoring[C]//Proceedings of the USENIX Winter 1992 Technical Conference,1992.Berkeley:USENIX Association,1992:333-343.
[14]Wang L,Zhan J F,Luo C J,et al.Bigdatabench:a big data benchmark suite from internet services[C]//Proceedings of the 20th IEEE International Symposium on High Performance Computer Architecture,Orlando,Feb 15-19,2014.Washington:IEEE Computer Society,2014:488-499.
[15]UMASS trace repository[EB/OL].(2009-12-03).http://traces.cs.umass.edu/index.php.
[2]Grupp L M,Davis J D,Swanson S.The bleak future of NAND flash memory[C]//Proceedings of the 10th USENIXConference on File and Storage Technologies,San Jose,Feb14-17,2012.Berkeley:USENIX Association,2012:2-2.
[3]Rajimwale A,Prabhakaran V,Davis J D.Block management in solid-state devices[C]//Proceedings of the USENIX Annual Technical Conference,San Diego,Jun 14-19,2009.Berkeley:USENIX Association,2009:21.
[4]EMC fast cache a detailed review[R/OL].(2011-11-08)[2013-12].http://www.emc.com/collateral/software/white-papers/h8046-clariion-celerra-unified-fast-cache-wp.pdf.
[5]Woods M.Optimizing storage performance and cost with intelligent caching:WP-7107[R].2010.
[6]Leventhal A.Flash storage memory[M].ACM,2008.
[7]Oracle.Exadata smart flash cache features and the oracle exadata database machine[EB/OL].(2013).http://www.oracle.com/technetwork/server-storage/engineeredsystems/exadata/exadata-smart-flash-cache-366203.pdf.
[8]Intel Corporation.Intel solid-state drive 910 series:product specification[EB/OL].(2012-06).http://www.intel.com/content/www/us/en/solid-state-drives/ssd-910-seriesspecification.htmlLeventhal.
[9]Gregg B.ZFS L2ARC[EB/OL].(2008-07-22).http://www.brendangregg.com/blog/2008-07-22/zfs-l2arc.html.
[10]Huang S,Wei Q S,Feng D,et al.Improving flash-based disk cache with lazy adaptive replacement[J].ACM Transactions on Storage,2016,12(2):8.
[11]Pritchett T,Thottethodi M.SieveStore:a highly-selective,ensemble-level disk cache for cost-performance[C]//Proceedings of the 37th International Symposium on Computer Architecture,Saint-Malo,Jun 19-23,2010.New York:ACM,2010:163-174.
[12]Zhou Y Y,Philbin J,Li K.The multi-queue replacement algorithm for second level buffer caches[C]//Proceedings of the 2001 USENIX Annual Technical Conference on General Track,Boston,Jun 25-30,2001.Berkeley:USENIX Association,2001:91-104.
[13]Blaze M.NFS tracing by passive network monitoring[C]//Proceedings of the USENIX Winter 1992 Technical Conference,1992.Berkeley:USENIX Association,1992:333-343.
[14]Wang L,Zhan J F,Luo C J,et al.Bigdatabench:a big data benchmark suite from internet services[C]//Proceedings of the 20th IEEE International Symposium on High Performance Computer Architecture,Orlando,Feb 15-19,2014.Washington:IEEE Computer Society,2014:488-499.
[15]UMASS trace repository[EB/OL].(2009-12-03).http://traces.cs.umass.edu/index.php.