基于权重堆排序的NAND Flash静态磨损均衡机制
|
摘要
磨损均衡机制作为闪存转换层的基础机制之一,其主要功能是延长闪存块使用寿命和提高存储数据的可靠性。现有的磨损均衡机制着重于减少闪存块的擦除次数,忽略了在磨损均衡操作过程中选择擦除脏块的不合理所带来的不必要数据迁移开销,从而影响了固态硬盘的整体读写性能。针对该问题,提出了一种基于权重堆排序的NAND Flash静态磨损均衡机制WHWL。首先,提出一种基于页数据访问频率和块擦除次数的权重的热度计算方法,有效地提高擦除次数少(冷块)且数据访问频率低(冷数据)的目标块命中率,避免了多余的数据迁移操作;其次,提出了一种基于权重的堆排序目标块选择算法,以加快目标块的筛选。实验结果表明,与现有的PWL和BET算法相比,在使用相同映射机制的条件下,WHWL能够分别提升固态硬盘寿命1.28、5.83倍,数据迁移次数也有明显的降低。
As one of the basic mechanisms of the flash translation layer, the wear leveling mechanism is a software algorithm that is applied to extend the life of the flash disk and improve the reliability of stored data. However, existing wear leveling mechanisms are too aggressive to balance the erasure counts of the entire flash memory and ignore the unnecessary data migration overhead due to the unreasonable selection of victim blocks during wear leveling operations, thereby affecting the overall read and write performance of the solid state disk. To solve this problem, we firstly propose a NAND Flash static wear leveling mechanism based on weighted heap sort, namely WHWL. We introduce a weight calculation method based on page data access frequency and the weight of erase counts of the block, which can effectively improve the hit rate of the target blocks with a small number of erases(cold blocks) and a low frequency of data access(cold data), and avoid redundant data migration operations. Secondly, we also propose a victim block selection algorithm based on weighted heap sort to speed up the selection of victim blocks. Experimental results show that compared with the existing PWL and BET algorithms, using the same mapping mechanism, the WHWL can increase the life span of solid state disks by 1.28 and 5.83 times, and also greatly decrease the number of migrations.
As one of the basic mechanisms of the flash translation layer, the wear leveling mechanism is a software algorithm that is applied to extend the life of the flash disk and improve the reliability of stored data. However, existing wear leveling mechanisms are too aggressive to balance the erasure counts of the entire flash memory and ignore the unnecessary data migration overhead due to the unreasonable selection of victim blocks during wear leveling operations, thereby affecting the overall read and write performance of the solid state disk. To solve this problem, we firstly propose a NAND Flash static wear leveling mechanism based on weighted heap sort, namely WHWL. We introduce a weight calculation method based on page data access frequency and the weight of erase counts of the block, which can effectively improve the hit rate of the target blocks with a small number of erases(cold blocks) and a low frequency of data access(cold data), and avoid redundant data migration operations. Secondly, we also propose a victim block selection algorithm based on weighted heap sort to speed up the selection of victim blocks. Experimental results show that compared with the existing PWL and BET algorithms, using the same mapping mechanism, the WHWL can increase the life span of solid state disks by 1.28 and 5.83 times, and also greatly decrease the number of migrations.
引文
[1] Xu Shu-tao,Huang Kai,Huang Kai-jie,et al.Fast hardware implementation of on-chip Nor Flash wear leveling based on heap-sort[J].Computer Engineering & Science,2017,39(11):1971-1979.(in Chinese)
[2] Bai Jie,Ma Hai-bing.Analysis of the application of SSD in storage system[J].China Science and Technology Information,2010(6):69-71.(in Chinese)
[3] Why SSDs are awesome [EB/OL].[2017-12-15]. http://www.samsung.com/global/business/semiconductor/minisite/SSD/global/html/about/whitepaper01.html.
[4] Jia Xin,Zhang Shao-ping.Research on wear leveling algorithm of NAND FLASH memory based on greedy strategy[J].Computer Science,2017,44(IIA):312-316.(in Chinese)
[5] Yao Ying-biao,Wang Fa-kuan.Wear leveling aware FTL for hybrid solid state disks[J].Chinese Journal of Computers,2017,41(10):2379-2393.(in Chinese)
[6] Chang Y H,Hsieh J W,Kuo T W.Improving flash wear-leveling by proactively moving static data[J].IEEE Transactions on Computers,2009,59(1):53-65.
[7] Murugan M,Du D H C.Rejuvenator:A static wear leveling algorithm for NAND flash memory with minimized overhead[C]//Proc of IEEE Symposium on MASS Storage Systems and Technologies,2011:1-12.
[8] Chang L P, Chou T Y, Huang L C.An adaptive,low-cost wear-leveling algorithm for multichannel solid-state disks[J].ACM Transactions on Embedded Computing Systems,2013,13(3):1-26.
[9] Chen F H,Yang M C,Chang Y H,et al.PWL:A progressive wear leveling to minimize data migration overheads for NAND flash devices[C]//Proc of Design,Automation & Test in Europe Conference & Exhibition,2015:1209-1212.
[10] Ye X,Zhai Z.Cold-warm-hot block wear-leveling algorithm for a NAND flash storage system[C]//Proc of 2017 4th International Conference on Systems and Informatics(ICSAI),2017:762-767.
[11] Lee S,Shin D,Kim Y J,et al.LAST:Locality-aware sector translation for NAND flash memory-based storage systems[J].ACM SIGOPS Operating Systems Review,2008,42(6):36-42.
[12] Yang M C,Chang Y H,Kuo T W,et al.Reducing data msigration overheads of flash wear leveling in a progressive way[J].IEEE Transactions on Very Large Scale Integration Systems,2016,24(5):1808-1820.
[13] Hu Y,Jiang H,Feng D,et al.Performance impact and interplay of SSD parallelism through advanced commands,allocation strategy and data granularity[C]//Proc of International Conference on Supercomputing,2011:96-107.附中文参考文献:
[1] 徐书韬,黄凯,黄凯杰,等.基于堆排序的片上Nor Flash损耗均衡硬件快速实现[J].计算机工程与科学,2017,39(11):1971-1979.
[2] 白洁,马海兵.固态硬盘在存储系统中的应用分析[J].中国科技信息,2010(6):69-71.
[4] 贾鑫,张少平.基于贪婪策略的NAND FLASH存储器的磨损均衡算法研究[J].计算机科学,2017,44(IIA):312-316.
[5] 姚英彪,王发宽.具有磨损均衡意识的混合固态硬盘FTL算法[J].计算机学报,2017,41(10):2379-2393.
[2] Bai Jie,Ma Hai-bing.Analysis of the application of SSD in storage system[J].China Science and Technology Information,2010(6):69-71.(in Chinese)
[3] Why SSDs are awesome [EB/OL].[2017-12-15]. http://www.samsung.com/global/business/semiconductor/minisite/SSD/global/html/about/whitepaper01.html.
[4] Jia Xin,Zhang Shao-ping.Research on wear leveling algorithm of NAND FLASH memory based on greedy strategy[J].Computer Science,2017,44(IIA):312-316.(in Chinese)
[5] Yao Ying-biao,Wang Fa-kuan.Wear leveling aware FTL for hybrid solid state disks[J].Chinese Journal of Computers,2017,41(10):2379-2393.(in Chinese)
[6] Chang Y H,Hsieh J W,Kuo T W.Improving flash wear-leveling by proactively moving static data[J].IEEE Transactions on Computers,2009,59(1):53-65.
[7] Murugan M,Du D H C.Rejuvenator:A static wear leveling algorithm for NAND flash memory with minimized overhead[C]//Proc of IEEE Symposium on MASS Storage Systems and Technologies,2011:1-12.
[8] Chang L P, Chou T Y, Huang L C.An adaptive,low-cost wear-leveling algorithm for multichannel solid-state disks[J].ACM Transactions on Embedded Computing Systems,2013,13(3):1-26.
[9] Chen F H,Yang M C,Chang Y H,et al.PWL:A progressive wear leveling to minimize data migration overheads for NAND flash devices[C]//Proc of Design,Automation & Test in Europe Conference & Exhibition,2015:1209-1212.
[10] Ye X,Zhai Z.Cold-warm-hot block wear-leveling algorithm for a NAND flash storage system[C]//Proc of 2017 4th International Conference on Systems and Informatics(ICSAI),2017:762-767.
[11] Lee S,Shin D,Kim Y J,et al.LAST:Locality-aware sector translation for NAND flash memory-based storage systems[J].ACM SIGOPS Operating Systems Review,2008,42(6):36-42.
[12] Yang M C,Chang Y H,Kuo T W,et al.Reducing data msigration overheads of flash wear leveling in a progressive way[J].IEEE Transactions on Very Large Scale Integration Systems,2016,24(5):1808-1820.
[13] Hu Y,Jiang H,Feng D,et al.Performance impact and interplay of SSD parallelism through advanced commands,allocation strategy and data granularity[C]//Proc of International Conference on Supercomputing,2011:96-107.附中文参考文献:
[1] 徐书韬,黄凯,黄凯杰,等.基于堆排序的片上Nor Flash损耗均衡硬件快速实现[J].计算机工程与科学,2017,39(11):1971-1979.
[2] 白洁,马海兵.固态硬盘在存储系统中的应用分析[J].中国科技信息,2010(6):69-71.
[4] 贾鑫,张少平.基于贪婪策略的NAND FLASH存储器的磨损均衡算法研究[J].计算机科学,2017,44(IIA):312-316.
[5] 姚英彪,王发宽.具有磨损均衡意识的混合固态硬盘FTL算法[J].计算机学报,2017,41(10):2379-2393.