基于邏輯頁冷熱分離的NAND閃存磨損均衡算法

王晉陽 嚴(yán)華

摘要：針對現(xiàn)有的NAND閃存垃圾回收算法對磨損均衡考慮不足的問題，提出了一種基于邏輯頁冷熱分離的NAND閃存磨損均衡算法。算法同時考慮了無效頁的年齡、物理塊的擦除次數(shù)以及物理塊更新的頻率，采用混合模式選擇回收符合條件的物理塊。同時，推導(dǎo)了一種新的邏輯頁熱度計算方法，并將回收塊上有效頁數(shù)據(jù)按照邏輯頁的熱度進行了冷熱分離。實驗結(jié)果表明，與GR算法、CB算法、CAT算法以及FaGC算法相比，該算法不僅在磨損均衡上取得了很好的效果，而且總的擦除次數(shù)與拷貝次數(shù)也有了明顯減少。

關(guān)鍵詞：NAND閃存；磨損均衡；垃圾回收；物理塊；邏輯頁

中圖分類號：TP316 文獻標(biāo)志碼：A

Abstract： According to the problem of the existing garbage collection algorithm for NAND flash memory， an efficient algorithm， called AWGC （Age With Garbage Collection）， was presented to improve wear leveling of NAND flash memory. A hybrid policy with the age of invalid page， erase count of physical blocks and the update frequency of physical blocks were redefined to select the returnable block. Meanwhile， a new heat calculation method logic pages was deduced， and coldhot separating of valid pages in returnable block was conducted. Compared with the GReedy （GR） algorithm， CostBenefit （CB） algorithm， CostAgeTime （CAT） algorithm and Fileaware Garbage Collection （FaGC） algorithm， not only some good results in wear leveling have been got， but also the total numbers of erase and copy operations have significantly been reduced.

Key words：NAND flash； wearleveling； garbage collection； physical block； logic page

0 引言

閃存（flash memory）由于具有非易失、存儲容量大、體積小、抗震性好以及多次擦寫等優(yōu)點，已經(jīng)成為嵌入式系統(tǒng)一種常見的存儲介質(zhì)[1-2]。NAND和NOR是當(dāng)前主流的閃存技術(shù)，NAND寫和擦除操作快，但隨機存取慢；而NOR隨機存取快，但擦除慢。NAND相對于NOR而言，存儲單元密度高、成本相對較低、性價比好，所以被廣泛采用。NAND Flash內(nèi)部分為多個塊（Block物理塊），每個塊由多個頁（Page物理頁）組成。頁是寫入數(shù)據(jù)的最小單元，塊是擦除的最小單元。每個閃存物理塊的擦除次數(shù)一般在10萬次到100萬次，若超過擦除次數(shù)的上限，會影響閃存數(shù)據(jù)存儲的性能[3]。NAND閃存管理系統(tǒng)對數(shù)據(jù)的更新操作采用的是“異地更新”的策略[4]，即將最新的數(shù)據(jù)寫入到別處，同時將原來的數(shù)據(jù)標(biāo)注為無效。對于存在大量實時數(shù)據(jù)的嵌入式系統(tǒng)而言，會頻繁地執(zhí)行讀寫和更新操作，導(dǎo)致無效的數(shù)據(jù)會變得越來越多。為了回收這些無效數(shù)據(jù)，釋放更多的可用空間，垃圾回收策略被提出，目的是從這些含有無效數(shù)據(jù)的塊中選擇出最符合條件的塊進行擦除，以最優(yōu)的方式釋放更多的可用空間。好的垃圾回收算法不僅能大幅度減少拷貝和擦除次數(shù)，而且能有效改善磨損均衡的效果[5]。所以，磨損均衡的核心就是回收策略的選擇。

近些年來，為了改善磨損均衡的效果，提出了很多的垃圾回收算法。如GR（GReedy）算法[6]，主要的策略是選擇有效頁最少的物理塊進行回收，因為有效頁的數(shù)量越少，拷貝的次數(shù)就會越少，算法核心是以最小的拷貝次數(shù)來獲取更多的可用空間，但是，GR算法基本未考慮磨損均衡。CB （CostBenefit）算法[7]利用公式Age*（1-u）*2u選擇回收塊，Age表示物理塊的年齡，即更新的時間間隔，u表示有效頁的比例。選擇公式值最大的物理塊作為回收塊，考慮到了物理塊更新的時間間隔和有效頁的比例，使得長期不更新的物理塊被回收的可能性增大，所以磨損均衡的效果在一定程度上要好于貪心算法。CAT（CostAgeTime）算法[8]是對CB算法的改進，考慮了擦除次數(shù)對磨損均衡的影響，選擇更新時間最長、有效頁數(shù)量最少且擦除次數(shù)最少的塊進行回收，并且CAT算法以物理塊的擦除次數(shù)對有效頁數(shù)據(jù)進行了冷熱分離，所以磨損均衡效果要優(yōu)于前兩種算法。但是，以上三種算法僅僅只考慮了最近一次物理塊的更新時間，不能準(zhǔn)確反映物理塊年齡，并且以擦除次數(shù)定義數(shù)據(jù)熱度，其冷熱分離的效果并不好。FaGC（Fileaware Garbage Collection）算法[9]提出了一種基于文件熱度的磨損均衡算法，在磨損均衡方面取得了很大的突破，但是FaGC在回收策略上主要用到的是貪心算法，其回收的代價很大，而且計算熱度的方法并不能夠準(zhǔn)確地反映當(dāng)前邏輯頁的熱度，所以仍然有可以改進的地方。

通過對NAND閃存的磨損均衡機制進行更為深入的研究與分析，針對上述垃圾回收算法存在的問題，考慮邏輯頁的熱度以及無效頁的年齡，重新定義了熱度計算方法和回收策略，提出了一種基于邏輯頁冷熱分離的NAND閃存磨損均衡算法，即AWGC （Age With Garbage Collection）算法。實驗基于Linux系統(tǒng)和Qemu嵌入式仿真開發(fā)板，從4個方面與上述算法作了對比，證明了該算法在磨損均衡應(yīng)用中的優(yōu)越性。

1 算法的實現(xiàn)

1.1 基本原理

如圖1所示，NAND Flash存儲設(shè)備的系統(tǒng)結(jié)構(gòu)主要由文件系統(tǒng)、FTL（Flash Translation Layer）層、MTD（Memory Technology Driver）層和NAND閃存設(shè)備這4個部分構(gòu)成。

FTL層和MTD層是文件系統(tǒng)與NAND閃存設(shè)備的中間層[10]。FTL層，又稱為閃存轉(zhuǎn)換層，是NAND閃存芯片與基礎(chǔ)文件系統(tǒng)之間的一個轉(zhuǎn)換層，它使操作系統(tǒng)和文件系統(tǒng)能夠像訪問硬盤一樣訪問NAND閃存設(shè)備，這里主要提供了三個重要的功能，分別是地址映射表、磨損均衡算法以及垃圾回收的策略[11]。MTD層，即內(nèi)存技術(shù)設(shè)備（Memory Technology Device），主要功能是將文件系統(tǒng)與底層NAND閃存設(shè)備進行隔離，為上層的文件系統(tǒng)提供統(tǒng)一的接口。

文件系統(tǒng)管理的是一個邏輯空間，而NAND閃存設(shè)備則是物理空間，在頁級映射的地址映射表中，邏輯地址對應(yīng)邏輯頁，物理地址對應(yīng)物理頁，邏輯頁與物理頁是一對一的關(guān)系。文件系統(tǒng)所操作的基本單位是邏輯頁，只在需要進行更新操作時才進行邏輯頁到物理頁的映射，邏輯頁作為一個抽象的概念，它必然要映射到具體的物理頁上去，所以用邏輯頁的更新頻率來定義有效頁的熱度更為準(zhǔn)確。

1.2 數(shù)據(jù)熱度的定義

目前，大部分定義數(shù)據(jù)冷熱的方式為物理頁的更新頻率或者物理塊的擦除次數(shù)，然而這兩種方式并不足以準(zhǔn)確反映數(shù)據(jù)的熱度。所以，為了能準(zhǔn)確定義數(shù)據(jù)的冷熱，有效地進行冷熱分離，提出了一種新的熱度計算方式，即考慮邏輯頁更新的時間間隔和上一次的熱度值，以這兩個參數(shù)來推導(dǎo)出當(dāng)前邏輯頁的熱度。

式（1）中，當(dāng)權(quán)值w為0時，當(dāng)前邏輯頁熱度的確定就只考慮了邏輯頁更新的時間間隔；隨著w的不斷增大，更新的時間間隔的權(quán)重就會不斷降低，相反，上一次邏輯頁的熱度值被考慮。為了平衡兩個參數(shù)對熱度值的影響，默認(rèn)w的值為0.5，同時考慮邏輯頁更新的時間間隔和上一次的熱度值。

式（2）中，Tdiff表征的主要內(nèi)容是邏輯頁更新的時間間隔對熱度值的影響。顯然，當(dāng)邏輯頁更新的時間間隔比較大時，就說明已經(jīng)有很長時間沒有對它進行操作了，故熱度值應(yīng)該變小。所以，邏輯頁更新的時間間隔與熱度值成反比例的關(guān)系。這里加入Hmax參數(shù)，利用最大的熱度值來調(diào)整邏輯頁更新的時間間隔與熱度值的關(guān)系，Hmax一般設(shè)定為10，故整個熱度區(qū)間在0～10。由于初次數(shù)據(jù)的寫入沒有初始熱度，所以設(shè)定了一個初始熱度值Th，其值一般選定為Hmax的一半。

熱度公式還解決了由于邏輯頁更新時間間隔很長無法得出熱度值的問題。若更新的時間很長，則式（2）中Tdiff的值可能為0，這時本次邏輯頁的熱度可以由上一次邏輯頁的熱度決定，這樣就不會影響對于熱度值的計算了。

1.3 數(shù)據(jù)的冷熱分離

由于NAND閃存“異地更新”的特性，對選中物理塊的有效頁數(shù)據(jù)會先拷貝到空閑塊上，然后進行擦除操作。數(shù)據(jù)的冷熱分離是在有效頁被拷貝之前，主要是為了將具有相近熱度的有效頁匯聚在指定的物理塊上，以達到減少拷貝和擦除次數(shù)的目的。由于在進行冷熱分離之后，頁的熱度相似，同時為無效或者有效的概率會增大，那么這些頁所在的塊，要么有效頁多，要么無效頁多，在下一次進行垃圾回收時，就可大大減少拷貝和擦除次數(shù)。

本文采用了一種基于邏輯頁熱度的冷熱分離，通過有效頁所對應(yīng)邏輯頁的熱度來決定其物理頁中數(shù)據(jù)寫入的對象。這里的對象分別指代的是擦除次數(shù)最多的物理塊和擦除次數(shù)最少的物理塊。具體的冷熱分離步驟如下：

1）設(shè)定判斷冷熱分離的閾值Th，并通過式（1）計算出當(dāng)前邏輯頁的熱度值。

2）若當(dāng)前邏輯頁的熱度≥Th，則該邏輯頁所對應(yīng)的有效頁被定義為熱頁，這時應(yīng)該將有效頁寫入擦除次數(shù)最少的物理塊中。

3）若當(dāng)前邏輯頁的熱度

4）完成有效頁的冷熱分離后，更新邏輯頁的熱度值以及操作的時間，用于下一次的熱度計算和更新操作。

1.4 新的垃圾回收策略

數(shù)據(jù)的冷熱分離減少了擦除和拷貝次數(shù)，但是在研究過程中發(fā)現(xiàn)，要提高NAND閃存的使用壽命，對于磨損均衡的要求比較高，所以一個好的回收策略很有必要。AWGC算法首先考慮了以無效頁年齡[12]和擦除次數(shù)作為回收的條件，具體公式如下：

其中：n表示物理塊中無效頁的數(shù)目，Tc表示當(dāng)前的時間，Ti表示變?yōu)闊o效頁的時間，Agei則表示第i個無效頁的年齡，ε表示物理塊的擦除次數(shù)。對時間進行歸一化處理，采用將時間取對數(shù)的方式，降低時間對算法的影響。

式（3）的主要思想是計算出每個塊中無效頁的年齡，然后用每個物理塊中無效頁的年齡之和來代表該物理塊的年齡。顯然，AWGC算法選擇的是AWT值最大的物理塊，即物理塊年齡最大且擦除次數(shù)最少的塊。因為影響物理塊年齡的原因主要是兩點：第一，無效頁的比例較多；第二，變?yōu)闊o效頁的時間間隔較長。所以這兩種情況都是有可能被選中的，若選中的是無效頁較多的物理塊，則可以減少拷貝有效頁的次數(shù)；若選中變?yōu)闊o效頁時間較長的塊，則說明該物理塊長期沒有得到回收更新，所以選擇這類型的塊能提高磨損均衡的效果。

2 實驗及分析

2.1 實驗環(huán)境

實驗環(huán)境由兩個主要步驟搭建完成。首先，通過Vmware工具安裝Linux虛擬機，并移植Yaffs2文件系統(tǒng)；然后在Linux下安裝Qemu嵌入式仿真開發(fā)板。利用NANDsim來模擬NAND Flash存儲設(shè)備。用于測試的文件由已編寫好的測試程序創(chuàng)建，大小為16kb～1024kb，測試的數(shù)據(jù)占整個NAND閃存設(shè)備容量的90%，并對15%的數(shù)據(jù)按照齊夫分布[13]進行更新操作。

實驗選取NAND Flash的總?cè)萘繛?4MB，包括512個塊，每個塊由64個頁組成。為了保證實驗結(jié)果的客觀性，關(guān)閉了Yaffs2文件系統(tǒng)的緩存功能，并選擇在急迫（aggressive）模式下進行垃圾回收，并且設(shè)置FaGC的初始閾值與AWGC的初始閾值相等。AWGC算法在實驗中所選取參數(shù)的值如表1所示。其中Fth表示磨損均衡的初始閾值；Hmax表示最大的熱度值；w表示熱度計算公式的權(quán)值；p表示時間的修正因子；Th表示判斷冷熱分離的閾值；Tscat表示分散度的閾值。

2.2 算法性能的分析

實驗主要的對比對象為4種現(xiàn)存的算法，分別是GR算法、CB算法、CAT算法以及FaGC算法，并從總的擦除次數(shù)、總的拷貝次數(shù)、物理塊最大擦除次數(shù)與最小擦除次數(shù)的差值和物理塊擦除次數(shù)的標(biāo)準(zhǔn)差這四方面進行對比分析。其中，總的擦除次數(shù)和拷貝次數(shù)代表的是在整個回收過程中所要花費的總代價；物理塊最大擦除次數(shù)與最小擦除次數(shù)的差值代表著磨損均衡兩極分化的情況；而物理塊擦除次數(shù)的標(biāo)準(zhǔn)差則代表整個回收過程中磨損均衡的穩(wěn)定程度，若標(biāo)準(zhǔn)差的曲線越穩(wěn)定且收斂，則表示磨損均衡穩(wěn)定程度越好，反之則穩(wěn)定程度越差。

由圖2和圖3可以得出，AWGC算法在總的擦除次數(shù)和總的拷貝次數(shù)上明顯低于前四種算法，得到了很好的優(yōu)化。

原因在于AWGC算法利用邏輯頁的更新頻率定義了數(shù)據(jù)的熱度，比較準(zhǔn)確對有效物理頁數(shù)據(jù)進行了冷熱分離，使得被定義為熱數(shù)據(jù)的有效頁匯聚到擦除次數(shù)最少的物理塊上，被定義為冷數(shù)據(jù)的有效頁匯聚到擦除次數(shù)最多的物理塊上。這樣在進行垃圾回收時，不僅大大減少拷貝有效頁的次數(shù)，而且提高了垃圾回收的效率，從而減少了總的擦除次數(shù)。FaGC算法雖然也進行了數(shù)據(jù)的冷熱分離，但是計算熱度的方法并不是很準(zhǔn)確，算法雖然同時考慮了邏輯頁更新的時間間隔和上一次的熱度值，但是當(dāng)前邏輯頁的熱度值還是由上一次的熱度乘以一個固定的系數(shù)所得，并不能完整準(zhǔn)確地反映整個熱度變化情況。而AWGC算法采用加權(quán)和的方式，平衡了兩個參數(shù)對熱度值的影響，使得計算出的當(dāng)前熱度值更為準(zhǔn)確，所以冷熱分離的效果要好， 因此，在擦除次數(shù)和拷貝次數(shù)的效果上要優(yōu)于FaGC算法。

圖4和圖5代表的是物理塊最大擦除次數(shù)和最小擦除次數(shù)的差值和物理塊擦除次數(shù)的標(biāo)準(zhǔn)差，體現(xiàn)的是幾種算法磨損均衡的整體效果。由圖5可以看出隨著擦除次數(shù)的不斷增大，GR算法、CB算法和CAT算法都不斷增大，呈現(xiàn)出非收斂的趨勢；而AWGC算法和FaGC算法隨著擦除次數(shù)的增大，曲線比較穩(wěn)定，呈現(xiàn)收斂的趨勢。這是因為AWGC算法和FaGC算法都引入了控制磨損均衡的閾值，采用混合的回收策略，對長期為冷的塊進行了回收處理，磨損均衡的穩(wěn)定程度要明顯優(yōu)于前三種算法。但是FaGC算法的混合回收策略主要采用是貪心算法，而AWGC算法考慮了無效頁的時間以及物理塊的擦除次數(shù)，從這兩個方面限定了回收塊的條件，使得回收的效率得到了很大提升，所以在如圖4中可以看出，AWGC算法最大擦除次數(shù)與最小擦除次數(shù)的差值比其他幾種算法小很多，說明磨損均衡兩極分化較小。實驗結(jié)果表明，隨著擦除次數(shù)的不斷增加，AWGC算法的分化情況能夠基本保持穩(wěn)定，而FaGC算法的分化情況會有所上升， 因此，AWGC算法整體的磨損均衡效果要好于前面四種算法，證明了AWGC算法在磨損均衡應(yīng)用中的優(yōu)越性。

3 結(jié)語

本文重新定義了冷熱數(shù)據(jù)的計算方法，實現(xiàn)了對數(shù)據(jù)的冷熱分離，并形成了新的垃圾回收策略。實驗結(jié)果表明，與GR算法、CB算法、CAT算法以及FaGC算法相比，AWGC算法不僅磨損均衡的整體效果很好，而且在總的擦除次數(shù)和總的拷貝次數(shù)上也有明顯的減少。雖然算法需要一定的內(nèi)存開銷，但是算法以最小的回收代價，取得了很好的回收效果，提高了回收的效率，改善了磨損均衡的效果，可在很大程度上延長NAND閃存的壽命。

參考文獻：

[1]LI H， YANG C， TSENG H. Energyaware flash memory management in virtual memory system[J]. IEEE Transactions on Very Large Scale Integration Systems，2008，16（8）：952-964.

[2]XU G， LIN F， XIAO Y. CLRU： a new page replacement algorithm for NAND flashbased consumer electronics[J]. IEEE Transactions on Consumer Electronics， 2014，60（1）：38-44.

[3]CHUNG C C， SHENG D， HSUEH N. A highperformance wearleveling algorithm for flash memory system[J]. IEICE Electronics Express， 2012，9（24）：1874-1880.

[4]SHIN L. Hot/cold clustering for page mapping in NAND flash memory[J]. IEEE Transactions on Consumer Electronics， 2011，57（4）：1728-1731.

[5]時正，紀(jì)金松，陳香蘭，等.一種基于差分進化的Flash文件系統(tǒng)垃圾回收算法[J]. 電子學(xué)報， 2011， 39（12）：280-284.（SHI Z， JI J S，CHEN X L， et al. A garbage collection algorithm for flash file system based on differential evolution[J]. Acta Electronica Sinica， 2011， 39（12）：280-284.）

[6]WU M， ZWAENEPOEL W. eNvy： A nonvolatile main memory storage system[C]// Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. New York： ACM， 1994：86-97.

[7]KAWAGUCHI A， NISHIOKA S， MOTODA H. A flash memory based file system[C]// Proceedings of the USENIX 1995 Technical Conference. Berkeley： USENIX， 1995：155-164.

[8]CHIANG M， CHANG R. Cleaning policies in mobile computers using flash memory[J]. Journal of Systems and Software， 1999， 48（3）：213-231.

[9]YAN H， YAO Q. An efficient fileaware garbage collection algorithm for NAND flashbased consumer electronics[J]. IEEE Transactions on Consumer Electronics， 2014， 60（4）：623-627.

[10]KIM H， SHIN D. Clustered pagelevel mapping for flash memorybased storage devices[J].IEEE Transactions on Consumer Electronics，2015，61（1）：47-55.

[11]張琦，王林章，張?zhí)?，?一種優(yōu)化的閃存地址映射方法[J].軟件學(xué)報， 2014，25（2）：314-325.（ZHANG Q， WANG L Z， ZHANG T， et al. Optimized address translation method for flash memory[J]. Journal of Software， 2014， 25（2）：314-325.）

[12]KWON O， KOH K， LEE J. FeGC： An efficient garbage collection scheme for flash memory based storage systems[J].Journal of Systems and Software， 2011， 84（9）：1507-1523.

[13]LIN M， CHEN S. Efficient and intelligent garbage collection policy for NAND flash based consumer electronics[J]. IEEE Transactions on Consumer Electronics， 2013， 59（3）：538-543.