基于擦除上限的動態(tài)閾值磨損均衡算法

朱增昌

摘要：為了提升磨損均衡算法的性能，該文提出一種基于擦除上限的動態(tài)閾值磨損均衡算法。首先，該算法通過塊的擦除上限來調(diào)整磨損均衡的執(zhí)行頻率，在閃存壽命前期較少觸發(fā)磨損均衡，后期較頻繁觸發(fā)磨損均衡；其次，該算法優(yōu)化了冷熱數(shù)據(jù)遷移和候選塊的選取條件，保證了候選塊是擦除次數(shù)較少的年輕塊，并且存儲的數(shù)據(jù)為冷數(shù)據(jù)。仿真表明該算法不僅降低了磨損均衡的損耗，同時有效地提升閃存的壽命。

關(guān)鍵詞：磨損均衡；動態(tài)閾值；數(shù)據(jù)遷移；候選塊

中圖分類號：TP3 文獻(xiàn)標(biāo)識碼：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

磨損均衡算法分為動態(tài)磨損和靜態(tài)磨損兩大塊。動態(tài)磨損均衡算法是在NAND flash 進(jìn)行垃圾回收的過程中觸發(fā)的，它根據(jù)NAND flash存儲器所有塊的擦除次數(shù)選取擦除次數(shù)較少的塊的。其主要目的是在SSD中找到擦除次數(shù)較少的塊，然后等待數(shù)據(jù)寫入更新時優(yōu)先使用這些擦除次數(shù)少的塊。動態(tài)磨損這種算法思想比較簡單，不會因為數(shù)據(jù)的搬移造成數(shù)據(jù)的額外寫入，但是因為在固態(tài)硬盤中考慮到大量的閃存塊中是存儲冷數(shù)據(jù)的，這樣使用動態(tài)磨損就無法更新冷數(shù)據(jù)，而是只在存儲熱數(shù)據(jù)塊進(jìn)行動態(tài)磨損，這樣會導(dǎo)致這些存儲熱數(shù)據(jù)的塊很快損壞。靜態(tài)磨損算法[1-3]會更好地解決這些問題，靜態(tài)磨損均衡算法根據(jù)設(shè)定觸發(fā)的條件將NAND flash 存儲器上的冷熱數(shù)據(jù)遷移[4-6]，主要目的是為了將磨損程度較大的塊中存入冷數(shù)據(jù)。這樣就會使得磨損程度較大的塊近期不會進(jìn)行數(shù)據(jù)更新擦除導(dǎo)致該塊損壞。靜態(tài)磨損均衡算法在存儲大量冷數(shù)據(jù)時性能提升非常顯著，本文提出基于擦除上限的動態(tài)閾值磨損均衡算法，本文算法在現(xiàn)有的漸進(jìn)式磨損均衡算法[7]（Progressive Wear Leveling，PWL）上進(jìn)行改進(jìn)利用算法降低閃存塊的擦除次數(shù)和擦除次數(shù)均方差。

1 PWL算法介紹

PWL算法是一種混合的磨損均衡算法，主要的特點是在靜態(tài)數(shù)據(jù)遷移部分，提出動態(tài)閾值來控制磨損均衡機制的觸發(fā)頻率，實現(xiàn)前期少觸發(fā)磨損均衡算法，后期頻繁觸發(fā)磨損均衡算法，保證前期閃存的性能。PWL算法流程圖如圖1所示。

1.1 動態(tài)閾值

PWL算法采用特定的動態(tài)閾值觸發(fā)磨損均衡算法，PWL算法定義的動態(tài)閾值（threshold，TH）表達(dá)式為：

[TH=eraseavg*BLKendurance-THRinitBLKendurance+THRinit] （1）

其中[eraseavg]為SSD所有塊的平均擦除次數(shù)，[BLKendurance]是閃存塊的擦除上限，[THRint]是設(shè)定觸發(fā)磨損均衡的最小值。

由閾值公式1可知，該公式針對所有塊的平均擦除次數(shù)來衡量是否觸發(fā)磨損均衡算法，這反應(yīng)的是所有塊的普遍擦除情況，但是會出現(xiàn)固態(tài)硬盤中某些塊擦除次數(shù)相對其他塊擦除次數(shù)較高的情況，這和磨損均衡算法是相悖的。

1.2 冷熱數(shù)據(jù)識別

PWL算法提出一種識別冷熱數(shù)據(jù)的方法，通過使用一個bit數(shù)組WriteArray記錄所有閃存塊存儲的數(shù)據(jù)冷熱性，在選取候選塊的時候，不使用存儲熱數(shù)據(jù)的塊作為候選塊，數(shù)組中一開始所有數(shù)據(jù)都為0，表示為冷數(shù)據(jù)；當(dāng)某個閃存塊被更新數(shù)據(jù)后，將此閃存塊對應(yīng)的bit數(shù)組位設(shè)為1，標(biāo)記該閃存塊存儲的數(shù)據(jù)為熱數(shù)據(jù)，不使用該塊作為候選塊，直到數(shù)組WriteArray全部為1，重置WriteArray為0，開始新的一輪。數(shù)組WriteArray對冷熱數(shù)據(jù)的選取進(jìn)行識別。

1.3 候選塊選取

PWL算法選取候選塊流程圖如圖2所示。

由表1可以看出， Block根據(jù)自身擦除情況和存儲數(shù)據(jù)的情況有幾種情況：

1）老塊不合適，擦除次數(shù)較多的塊不適合作為候選塊；

2）熱塊不合適，存儲熱數(shù)據(jù)的塊不適合用來存儲其他的熱數(shù)據(jù)；

3）冷數(shù)據(jù)和年輕塊合適，該類塊適合用來存儲熱數(shù)據(jù)。

由上面的候選塊條件，提出候選塊的選取表達(dá)式為：

[eraseblock

其中[eraseblock]表示更新塊的擦除次數(shù)，[eraseavg]表示所有閃存塊的平均擦除次數(shù)，用來定義塊中數(shù)據(jù)的時效性（冷熱性），初始值為0；目的是用來防止上次剛進(jìn)行冷熱數(shù)據(jù)替換的塊再次進(jìn)行冷熱數(shù)據(jù)替換。判斷公式2是否成立，如果成立，則更新塊被定義為存放冷數(shù)據(jù)的年輕塊。

2 改進(jìn)的動態(tài)閾值算法

在現(xiàn)有算法中的動態(tài)閾值使用所有塊的平均值觸發(fā)磨損均衡機制，在閃存后期，塊的擦除次數(shù)不集中，所有塊的均方差很大，損害了閃存的壽命。另外，在選取候選塊時，使用所有塊擦除次數(shù)的平均值選取存放冷數(shù)據(jù)的塊不合理，選擇的塊的擦除次數(shù)可能和所有塊的平均擦除次數(shù)接近，導(dǎo)致選取的候選者塊不是最優(yōu)的，該塊擦除次數(shù)也較大，不適合定義為候選塊。

2.1 改進(jìn)動態(tài)閾值設(shè)計

提出動態(tài)閾值公式為：

[TH=λ*（eraselimit-erasemax）] （3）

其中[λ]是調(diào)節(jié)因子；綜合性能和壽命本文[λ]取1，[eraselimit]表示所有塊的擦除上限，[erasemax]表示所有塊中最大的擦除次數(shù)。系

圖3表明了[erasemax]與[TH]的關(guān)系，由圖2可知，在前期，[TH>erasemax]，不觸發(fā)磨損均衡機制，直到[TH

基于擦除上限的動態(tài)閾值磨損均衡算法的動態(tài)閾值與PWL的動態(tài)閾值相比較，它改進(jìn)了PWL中觸發(fā)磨損均衡算法的動態(tài)閾值定義，不使用所有塊的平均擦除次數(shù)作為觸發(fā)磨損均衡算法的條件，而使用擦除次數(shù)最大的塊和塊的擦除上限進(jìn)行控制動態(tài)閾值大小，從而使得所有塊在前期較少觸發(fā)磨損均衡算法，減少磨損損耗；在后期較頻繁觸發(fā)磨損均衡算法，所有塊都同時達(dá)到擦除上限。

2.2 改進(jìn)候選塊的選取條件

基于擦除上限的動態(tài)閾值磨損均衡算法對選取候選塊的區(qū)域改進(jìn)，PWL算法選取的閃存塊擦除次數(shù)可能和所有塊的平均擦除次數(shù)接近，選取的候選塊不是最優(yōu)的，也就是說選到的候選塊存儲的數(shù)據(jù)不是冷數(shù)據(jù)，或者該塊擦除次數(shù)也較大，這不符合候選塊的定義，所以針對這個問題，對其進(jìn)行優(yōu)化，將選擇的區(qū)域進(jìn)行改進(jìn)，使得被選的塊一定是存儲冷數(shù)據(jù)的塊，且該塊擦除次數(shù)相對較少。設(shè)計出一個更優(yōu)的選擇出符合要求的候選塊：

[ eraseblock-eraseminerasemax-erasemin<δ WriterArray==0] （4）

其中[erasemin]是閃存中所有塊中擦除次數(shù)的最小值。[δ]是調(diào)節(jié)因子，調(diào)節(jié)存儲冷數(shù)據(jù)塊的范圍，[δ∈0，0.5]。該公式選取的候選塊的擦除次數(shù)[erase∈[erasemin， δ*（erasemax-erasemin）]]。

3 性能仿真比較

對閃存中存儲不同比例的冷數(shù)據(jù)仿真比較，配置環(huán)境，SSD包含32個Block，每個塊中有64個頁，即SSD容量為32×64=2048，塊的擦除上限為500，其中令[δ=0.1]（后面將解釋為什么這樣做）。隨機更新寫入數(shù)據(jù)為[7×105]。通過比較各個環(huán)境下兩種算法閃存塊擦除次數(shù)的均方差，來判定算法的性能優(yōu)劣，其中兩種算法平均塊擦除次數(shù)相差不大，但是塊擦除均方差不同。

由圖4和圖5可以看出，在冷數(shù)據(jù)占比高達(dá)70%以上的時候，WL1算法的性能明顯比PWL算法好。由此可以證明在大量冷數(shù)據(jù)存在的固態(tài)硬盤中，WL1算法的性能更好，使得所有塊的擦除更加的均衡。

在冷數(shù)據(jù)占比70%以上時，從圖4和圖5仿真結(jié)果可以看出，WL1算法和PWL算法在觸發(fā)磨損均衡機制上有些不同。前期兩種算法觸發(fā)磨損均衡機制的頻率相差不大，中后期WL1算法觸發(fā)磨損均衡機制的頻率上升速度更加的快，使得后期觸發(fā)磨損機制更頻繁，寫入放大比例更小。

從圖4和圖5仿真結(jié)果也可以看出，在冷熱數(shù)據(jù)遷移的過程中，WL1算法能選取更佳的候選者塊進(jìn)行數(shù)據(jù)遷移和等待下次數(shù)據(jù)的更新。

由公式4中可以看出，調(diào)節(jié)因子的選取很重要，為了確認(rèn)公式4中的[δ=0.1]是最優(yōu)的，將調(diào)節(jié)因子[δ]在（0，0.5）之間取值，圖6是[δ]在不同取值下，本文算法的性能比較，由圖中可以看得出，在0.1附近值的性能都沒有更好，而且調(diào)節(jié)因子太小，對選取到的候選塊的范圍會更加的嚴(yán)格，影響到算法的性能。

因此選取候選塊的公式簡化為公式5所示：

[ eraseblock-eraseminerasemax-erasemin<0.1 WriterArray==0] （5）

4 結(jié)語

本文提出的算法中主要是改進(jìn)了觸發(fā)磨損均衡算法的動態(tài)閾值公式和候選者塊的選取范圍。得出以下結(jié)論：1）對比PWL算法的動態(tài)閾值，該方案的動態(tài)閾值設(shè)計得更加合理，磨損均衡機制觸發(fā)的頻率更加合適，減少了磨損均衡的開銷；2）對比PWL算法的候選塊選取條件，該優(yōu)化方案保證了選取的候選塊是存儲冷數(shù)據(jù)的年輕塊。證明在大量的冷數(shù)據(jù)環(huán)境下，本文算法的性能更佳，有效地提升了SSD的使用壽命。

參考文獻(xiàn)：

[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] 溫雷.基于固態(tài)硬盤的磨損均衡算法的研究與設(shè)計[D].湖南大學(xué)，2017：17-22

[6] 蔡紅衛(wèi).混合固態(tài)硬盤的磨損均衡算法研究[D].湖南大學(xué)，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

【通聯(lián)編輯：代影】