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

王晉陽 嚴華

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

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

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

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

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

1 算法的實現

1.1 基本原理

如圖1所示，NAND Flash存儲設備的系統結構主要由文件系統、FTL（Flash Translation Layer）層、MTD（Memory Technology Driver）層和NAND閃存設備這4個部分構成。

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

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

1.2 數據熱度的定義

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

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

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

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

1.3 數據的冷熱分離

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

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

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

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

3）若當前邏輯頁的熱度

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

1.4 新的垃圾回收策略

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

其中：n表示物理塊中無效頁的數目，Tc表示當前的時間，Ti表示變為無效頁的時間，Agei則表示第i個無效頁的年齡，ε表示物理塊的擦除次數。對時間進行歸一化處理，采用將時間取對數的方式，降低時間對算法的影響。

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

2 實驗及分析

2.1 實驗環境

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

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

2.2 算法性能的分析

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

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

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

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

3 結語

本文重新定義了冷熱數據的計算方法，實現了對數據的冷熱分離，并形成了新的垃圾回收策略。實驗結果表明，與GR算法、CB算法、CAT算法以及FaGC算法相比，AWGC算法不僅磨損均衡的整體效果很好，而且在總的擦除次數和總的拷貝次數上也有明顯的減少。雖然算法需要一定的內存開銷，但是算法以最小的回收代價，取得了很好的回收效果，提高了回收的效率，改善了磨損均衡的效果，可在很大程度上延長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]時正，紀金松，陳香蘭，等.一種基于差分進化的Flash文件系統垃圾回收算法[J]. 電子學報， 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]張琦，王林章，張天，等.一種優化的閃存地址映射方法[J].軟件學報， 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.