论文部分内容阅读
摘要：为了提升磨损均衡算法的性能，该文提出一种基于擦除上限的动态阈值磨损均衡算法。首先，该算法通过块的擦除上限来调整磨损均衡的执行频率，在闪存寿命前期较少触发磨损均衡，后期较频繁触发磨损均衡；其次，该算法优化了冷热数据迁移和候选块的选取条件，保证了候选块是擦除次数较少的年轻块，并且存储的数据为冷数据。仿真表明该算法不仅降低了磨损均衡的损耗，同时有效地提升闪存的寿命。
关键词：磨损均衡；动态阈值；数据迁移；候选块
中图分类号：TP3 文献标识码：A
文章编号：1009-3044（2019）12-0223-03
Dynamic Threshold Wear Leveling Algorithm based on the Upper Limit of Erasure
ZHU Zeng-chang
（School of Information Engineering， Guangdong University of Technology， Guangzhou 510000， China）
Abstract： In order to improve the performance of wear leveling algorithm， A dynamic threshold wear leveling algorithm based on the upper limit of erasure is proposed in this paper. Firstly， the proposed algorithm adjusts the execution frequency of wear leveling by upper limit of erasure of blocks， which triggers wear leveling less in the early stage of flash memory and that more frequently in the later stage. Secondly，the proposed algorithm optimizes data migration and victim block selection， thus ensuring that the victim blocks is young blocks with fewer erase counts and the stored data is cold data. The simulations show that the proposed algorithm not only reduces the performance overheads of wear leveling， but also effectively extend the lifetime of flash memory.
Key words： wear leveling； dynamic threshold； data migration； victim block
磨損均衡算法分为动态磨损和静态磨损两大块。动态磨损均衡算法是在NAND flash 进行垃圾回收的过程中触发的，它根据NAND flash存储器所有块的擦除次数选取擦除次数较少的块的。其主要目的是在SSD中找到擦除次数较少的块，然后等待数据写入更新时优先使用这些擦除次数少的块。动态磨损这种算法思想比较简单，不会因为数据的搬移造成数据的额外写入，但是因为在固态硬盘中考虑到大量的闪存块中是存储冷数据的，这样使用动态磨损就无法更新冷数据，而是只在存储热数据块进行动态磨损，这样会导致这些存储热数据的块很快损坏。静态磨损算法[1-3]会更好地解决这些问题，静态磨损均衡算法根据设定触发的条件将NAND flash 存储器上的冷热数据迁移[4-6]，主要目的是为了将磨损程度较大的块中存入冷数据。这样就会使得磨损程度较大的块近期不会进行数据更新擦除导致该块损坏。静态磨损均衡算法在存储大量冷数据时性能提升非常显著，本文提出基于擦除上限的动态阈值磨损均衡算法，本文算法在现有的渐进式磨损均衡算法[7]（Progressive Wear Leveling，PWL）上进行改进利用算法降低闪存块的擦除次数和擦除次数均方差。
1 PWL算法介绍
PWL算法是一种混合的磨损均衡算法，主要的特点是在静态数据迁移部分，提出动态阈值来控制磨损均衡机制的触发频率，实现前期少触发磨损均衡算法，后期频繁触发磨损均衡算法，保证前期闪存的性能。PWL算法流程图如图1所示。
1.1 动态阈值
PWL算法采用特定的动态阈值触发磨损均衡算法，PWL算法定义的动态阈值（threshold，TH）表达式为：
[TH=eraseavg*BLKendurance-THRinitBLKendurance THRinit] （1）
其中[eraseavg]为SSD所有块的平均擦除次数，[BLKendurance]是闪存块的擦除上限，[THRint]是设定触发磨损均衡的最小值。
由阈值公式1可知，该公式针对所有块的平均擦除次数来衡量是否触发磨损均衡算法，这反应的是所有块的普遍擦除情况，但是会出现固态硬盘中某些块擦除次数相对其他块擦除次数较高的情况，这和磨损均衡算法是相悖的。
1.2 冷热数据识别
PWL算法提出一种识别冷热数据的方法，通过使用一个bit数组WriteArray记录所有闪存块存储的数据冷热性，在选取候选块的时候，不使用存储热数据的块作为候选块，数组中一开始所有数据都为0，表示为冷数据；当某个闪存块被更新数据后，将此闪存块对应的bit数组位设为1，标记该闪存块存储的数据为热数据，不使用该块作为候选块，直到数组WriteArray全部为1，重置WriteArray为0，开始新的一轮。数组WriteArray对冷热数据的选取进行识别。 1.3 候选块选取
PWL算法选取候选块流程图如图2所示。
由表1可以看出， Block根据自身擦除情况和存储数据的情况有几种情况：
1）老块不合适，擦除次数较多的块不适合作为候选块；
2）热块不合适，存储热数据的块不适合用来存储其他的热数据；
3）冷数据和年轻块合适，该类块适合用来存储热数据。
由上面的候选块条件，提出候选块的选取表达式为：
[eraseblock 其中[eraseblock]表示更新块的擦除次数，[eraseavg]表示所有闪存块的平均擦除次数，用来定义块中数据的时效性（冷热性），初始值为0；目的是用来防止上次刚进行冷热数据替换的块再次进行冷热数据替换。判断公式2是否成立，如果成立，则更新块被定义为存放冷数据的年轻块。
2 改进的动态阈值算法
在现有算法中的动态阈值使用所有块的平均值触发磨损均衡机制，在闪存后期，块的擦除次数不集中，所有块的均方差很大，损害了闪存的寿命。另外，在选取候选块时，使用所有块擦除次数的平均值选取存放冷数据的块不合理，选择的块的擦除次数可能和所有块的平均擦除次数接近，导致选取的候选者块不是最优的，该块擦除次数也较大，不适合定义为候选块。
2.1 改进动态阈值设计
提出动态阈值公式为：
[TH=λ*（eraselimit-erasemax）] （3）
其中[λ]是调节因子；综合性能和寿命本文[λ]取1，[eraselimit]表示所有块的擦除上限，[erasemax]表示所有块中最大的擦除次数。系
图3表明了[erasemax]与[TH]的关系，由图2可知，在前期，[TH>erasemax]，不触发磨损均衡机制，直到[TH 基于擦除上限的动态阈值磨损均衡算法的动态阈值与PWL的动态阈值相比较，它改进了PWL中触发磨损均衡算法的动态阈值定义，不使用所有块的平均擦除次数作为触发磨损均衡算法的条件，而使用擦除次数最大的块和块的擦除上限进行控制动态阈值大小，从而使得所有块在前期较少触发磨损均衡算法，减少磨损损耗；在后期较频繁触发磨损均衡算法，所有块都同时达到擦除上限。
2.2 改进候选块的选取条件
基于擦除上限的动态阈值磨损均衡算法对选取候选块的区域改进，PWL算法选取的闪存块擦除次数可能和所有块的平均擦除次数接近，选取的候选块不是最优的，也就是说选到的候选块存储的数据不是冷数据，或者该块擦除次数也较大，这不符合候选块的定义，所以针对这个问题，对其进行优化，将选择的区域进行改进，使得被选的块一定是存储冷数据的块，且该块擦除次数相对较少。设计出一个更优的选择出符合要求的候选块：
[ eraseblock-eraseminerasemax-erasemin<δ WriterArray==0] （4）
其中[erasemin]是闪存中所有块中擦除次数的最小值。[δ]是调节因子，调节存储冷数据块的范围，[δ∈0，0.5]。该公式选取的候选块的擦除次数[erase∈[erasemin， δ*（erasemax-erasemin）]]。
3 性能仿真比较
对闪存中存储不同比例的冷数据仿真比较，配置环境，SSD包含32个Block，每个块中有64个页，即SSD容量为32×64=2048，块的擦除上限为500，其中令[δ=0.1]（后面将解释为什么这样做）。随机更新写入数据为[7×105]。通过比较各个环境下两种算法闪存块擦除次数的均方差，来判定算法的性能优劣，其中两种算法平均块擦除次数相差不大，但是块擦除均方差不同。
由图4和图5可以看出，在冷数据占比高达70%以上的时候，WL1算法的性能明显比PWL算法好。由此可以证明在大量冷数据存在的固态硬盘中，WL1算法的性能更好，使得所有塊的擦除更加的均衡。
在冷数据占比70%以上时，从图4和图5仿真结果可以看出，WL1算法和PWL算法在触发磨损均衡机制上有些不同。前期两种算法触发磨损均衡机制的频率相差不大，中后期WL1算法触发磨损均衡机制的频率上升速度更加的快，使得后期触发磨损机制更频繁，写入放大比例更小。
从图4和图5仿真结果也可以看出，在冷热数据迁移的过程中，WL1算法能选取更佳的候选者块进行数据迁移和等待下次数据的更新。
由公式4中可以看出，调节因子的选取很重要，为了确认公式4中的[δ=0.1]是最优的，将调节因子[δ]在（0，0.5）之间取值，图6是[δ]在不同取值下，本文算法的性能比较，由图中可以看得出，在0.1附近值的性能都没有更好，而且调节因子太小，对选取到的候选块的范围会更加的严格，影响到算法的性能。
因此选取候选块的公式简化为公式5所示：
[ eraseblock-eraseminerasemax-erasemin<0.1 WriterArray==0] （5）
4 结语
本文提出的算法中主要是改进了触发磨损均衡算法的动态阈值公式和候选者块的选取范围。得出以下结论：1）对比PWL算法的动态阈值，该方案的动态阈值设计得更加合理，磨损均衡机制触发的频率更加合适，减少了磨损均衡的开销；2）对比PWL算法的候选块选取条件，该优化方案保证了选取的候选块是存储冷数据的年轻块。证明在大量的冷数据环境下，本文算法的性能更佳，有效地提升了SSD的使用寿命。
参考文献： [1] Xu G， Wang M， Liu Y. Swap-aware garbage collectio algorithm for NAND flash-based consumer electronics[J]. Consumer Electronics IEEE Transactions on， 2014，60（1） ：60-65.
[2] Murugan M， Du D H C. Rejuvenator： Astatic wear leveling algorithm for NAND flash memory with minimized overhead[C] // IEEE， Symposium on MASS Storage Systems and Technologies. IEEE Computer Society， Washington， DC， USA， 2011：1-12.
[3] Chang Y H， Chang L P. Efficient wear leveling in NAND flash memory[M]. Inside Solid State Drives（SSDs）， Springer Netherlands， 2013： 233-257
[4] X. Ye and Z. Zhai， Cold-warm-hot block wear-leveling algorithm for a NAND flash storage system， International Conference on Systems and Informatics （ICSAI）， Hangzhou， 2017： 762-767.
[5] 温雷.基于固態硬盘的磨损均衡算法的研究与设计[D].湖南大学，2017：17-22
[6] 蔡红卫.混合固态硬盘的磨损均衡算法研究[D].湖南大学，2018： 35-37
[7] 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. Design， Automation and Test in Europe. 2015：1209-1212
【通联编辑：代影】
关键词：磨损均衡；动态阈值；数据迁移；候选块
中图分类号：TP3 文献标识码：A
文章编号：1009-3044（2019）12-0223-03
Dynamic Threshold Wear Leveling Algorithm based on the Upper Limit of Erasure
ZHU Zeng-chang
（School of Information Engineering， Guangdong University of Technology， Guangzhou 510000， China）
Abstract： In order to improve the performance of wear leveling algorithm， A dynamic threshold wear leveling algorithm based on the upper limit of erasure is proposed in this paper. Firstly， the proposed algorithm adjusts the execution frequency of wear leveling by upper limit of erasure of blocks， which triggers wear leveling less in the early stage of flash memory and that more frequently in the later stage. Secondly，the proposed algorithm optimizes data migration and victim block selection， thus ensuring that the victim blocks is young blocks with fewer erase counts and the stored data is cold data. The simulations show that the proposed algorithm not only reduces the performance overheads of wear leveling， but also effectively extend the lifetime of flash memory.
Key words： wear leveling； dynamic threshold； data migration； victim block
磨損均衡算法分为动态磨损和静态磨损两大块。动态磨损均衡算法是在NAND flash 进行垃圾回收的过程中触发的，它根据NAND flash存储器所有块的擦除次数选取擦除次数较少的块的。其主要目的是在SSD中找到擦除次数较少的块，然后等待数据写入更新时优先使用这些擦除次数少的块。动态磨损这种算法思想比较简单，不会因为数据的搬移造成数据的额外写入，但是因为在固态硬盘中考虑到大量的闪存块中是存储冷数据的，这样使用动态磨损就无法更新冷数据，而是只在存储热数据块进行动态磨损，这样会导致这些存储热数据的块很快损坏。静态磨损算法[1-3]会更好地解决这些问题，静态磨损均衡算法根据设定触发的条件将NAND flash 存储器上的冷热数据迁移[4-6]，主要目的是为了将磨损程度较大的块中存入冷数据。这样就会使得磨损程度较大的块近期不会进行数据更新擦除导致该块损坏。静态磨损均衡算法在存储大量冷数据时性能提升非常显著，本文提出基于擦除上限的动态阈值磨损均衡算法，本文算法在现有的渐进式磨损均衡算法[7]（Progressive Wear Leveling，PWL）上进行改进利用算法降低闪存块的擦除次数和擦除次数均方差。
1 PWL算法介绍
PWL算法是一种混合的磨损均衡算法，主要的特点是在静态数据迁移部分，提出动态阈值来控制磨损均衡机制的触发频率，实现前期少触发磨损均衡算法，后期频繁触发磨损均衡算法，保证前期闪存的性能。PWL算法流程图如图1所示。
1.1 动态阈值
PWL算法采用特定的动态阈值触发磨损均衡算法，PWL算法定义的动态阈值（threshold，TH）表达式为：
[TH=eraseavg*BLKendurance-THRinitBLKendurance THRinit] （1）
其中[eraseavg]为SSD所有块的平均擦除次数，[BLKendurance]是闪存块的擦除上限，[THRint]是设定触发磨损均衡的最小值。
由阈值公式1可知，该公式针对所有块的平均擦除次数来衡量是否触发磨损均衡算法，这反应的是所有块的普遍擦除情况，但是会出现固态硬盘中某些块擦除次数相对其他块擦除次数较高的情况，这和磨损均衡算法是相悖的。
1.2 冷热数据识别
PWL算法提出一种识别冷热数据的方法，通过使用一个bit数组WriteArray记录所有闪存块存储的数据冷热性，在选取候选块的时候，不使用存储热数据的块作为候选块，数组中一开始所有数据都为0，表示为冷数据；当某个闪存块被更新数据后，将此闪存块对应的bit数组位设为1，标记该闪存块存储的数据为热数据，不使用该块作为候选块，直到数组WriteArray全部为1，重置WriteArray为0，开始新的一轮。数组WriteArray对冷热数据的选取进行识别。 1.3 候选块选取
PWL算法选取候选块流程图如图2所示。
由表1可以看出， Block根据自身擦除情况和存储数据的情况有几种情况：
1）老块不合适，擦除次数较多的块不适合作为候选块；
2）热块不合适，存储热数据的块不适合用来存储其他的热数据；
3）冷数据和年轻块合适，该类块适合用来存储热数据。
由上面的候选块条件，提出候选块的选取表达式为：
[eraseblock
2 改进的动态阈值算法
在现有算法中的动态阈值使用所有块的平均值触发磨损均衡机制，在闪存后期，块的擦除次数不集中，所有块的均方差很大，损害了闪存的寿命。另外，在选取候选块时，使用所有块擦除次数的平均值选取存放冷数据的块不合理，选择的块的擦除次数可能和所有块的平均擦除次数接近，导致选取的候选者块不是最优的，该块擦除次数也较大，不适合定义为候选块。
2.1 改进动态阈值设计
提出动态阈值公式为：
[TH=λ*（eraselimit-erasemax）] （3）
其中[λ]是调节因子；综合性能和寿命本文[λ]取1，[eraselimit]表示所有块的擦除上限，[erasemax]表示所有块中最大的擦除次数。系
图3表明了[erasemax]与[TH]的关系，由图2可知，在前期，[TH>erasemax]，不触发磨损均衡机制，直到[TH
2.2 改进候选块的选取条件
基于擦除上限的动态阈值磨损均衡算法对选取候选块的区域改进，PWL算法选取的闪存块擦除次数可能和所有块的平均擦除次数接近，选取的候选块不是最优的，也就是说选到的候选块存储的数据不是冷数据，或者该块擦除次数也较大，这不符合候选块的定义，所以针对这个问题，对其进行优化，将选择的区域进行改进，使得被选的块一定是存储冷数据的块，且该块擦除次数相对较少。设计出一个更优的选择出符合要求的候选块：
[ eraseblock-eraseminerasemax-erasemin<δ WriterArray==0] （4）
其中[erasemin]是闪存中所有块中擦除次数的最小值。[δ]是调节因子，调节存储冷数据块的范围，[δ∈0，0.5]。该公式选取的候选块的擦除次数[erase∈[erasemin， δ*（erasemax-erasemin）]]。
3 性能仿真比较
对闪存中存储不同比例的冷数据仿真比较，配置环境，SSD包含32个Block，每个块中有64个页，即SSD容量为32×64=2048，块的擦除上限为500，其中令[δ=0.1]（后面将解释为什么这样做）。随机更新写入数据为[7×105]。通过比较各个环境下两种算法闪存块擦除次数的均方差，来判定算法的性能优劣，其中两种算法平均块擦除次数相差不大，但是块擦除均方差不同。
由图4和图5可以看出，在冷数据占比高达70%以上的时候，WL1算法的性能明显比PWL算法好。由此可以证明在大量冷数据存在的固态硬盘中，WL1算法的性能更好，使得所有塊的擦除更加的均衡。
在冷数据占比70%以上时，从图4和图5仿真结果可以看出，WL1算法和PWL算法在触发磨损均衡机制上有些不同。前期两种算法触发磨损均衡机制的频率相差不大，中后期WL1算法触发磨损均衡机制的频率上升速度更加的快，使得后期触发磨损机制更频繁，写入放大比例更小。
从图4和图5仿真结果也可以看出，在冷热数据迁移的过程中，WL1算法能选取更佳的候选者块进行数据迁移和等待下次数据的更新。
由公式4中可以看出，调节因子的选取很重要，为了确认公式4中的[δ=0.1]是最优的，将调节因子[δ]在（0，0.5）之间取值，图6是[δ]在不同取值下，本文算法的性能比较，由图中可以看得出，在0.1附近值的性能都没有更好，而且调节因子太小，对选取到的候选块的范围会更加的严格，影响到算法的性能。
因此选取候选块的公式简化为公式5所示：
[ eraseblock-eraseminerasemax-erasemin<0.1 WriterArray==0] （5）
4 结语
本文提出的算法中主要是改进了触发磨损均衡算法的动态阈值公式和候选者块的选取范围。得出以下结论：1）对比PWL算法的动态阈值，该方案的动态阈值设计得更加合理，磨损均衡机制触发的频率更加合适，减少了磨损均衡的开销；2）对比PWL算法的候选块选取条件，该优化方案保证了选取的候选块是存储冷数据的年轻块。证明在大量的冷数据环境下，本文算法的性能更佳，有效地提升了SSD的使用寿命。
参考文献： [1] Xu G， Wang M， Liu Y. Swap-aware garbage collectio algorithm for NAND flash-based consumer electronics[J]. Consumer Electronics IEEE Transactions on， 2014，60（1） ：60-65.
[2] Murugan M， Du D H C. Rejuvenator： Astatic wear leveling algorithm for NAND flash memory with minimized overhead[C] // IEEE， Symposium on MASS Storage Systems and Technologies. IEEE Computer Society， Washington， DC， USA， 2011：1-12.
[3] Chang Y H， Chang L P. Efficient wear leveling in NAND flash memory[M]. Inside Solid State Drives（SSDs）， Springer Netherlands， 2013： 233-257
[4] X. Ye and Z. Zhai， Cold-warm-hot block wear-leveling algorithm for a NAND flash storage system， International Conference on Systems and Informatics （ICSAI）， Hangzhou， 2017： 762-767.
[5] 温雷.基于固態硬盘的磨损均衡算法的研究与设计[D].湖南大学，2017：17-22
[6] 蔡红卫.混合固态硬盘的磨损均衡算法研究[D].湖南大学，2018： 35-37
[7] 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. Design， Automation and Test in Europe. 2015：1209-1212
【通联编辑：代影】