基于塊更新序號的NAND閃存垃圾回收算法

陳 琳， 嚴 華

(四川大學電子信息學院， 成都 610065)

伴隨發展迅猛的信息化技術，存儲數據所需介質在容量、種類等方面不斷增長。與傳統機械硬盤相比，NAND閃存具有體積小、無噪聲、功耗低、訪問速度快、防震抗摔性好等諸多優點，因此得到廣泛應用，逐漸成為主要的存儲介質[1-2]。NAND閃存由一定數量的物理塊(block)構成，而每個物理塊又由一定數量的物理頁(page)構成。閃存的讀取操作與寫入操作以頁為單位進行，但擦除操作只能在包含了多個頁的塊上來完成[3]。當系統請求頁重寫時，NAND閃存不能在同一物理頁上進行“本地更新”，通常采用“異地更新”策略以滿足寫前擦除的特性，即新數據不能直接在舊頁上改動，而需寫入另一空閑物理頁，并將舊頁標記為無效頁[4-5]。當無效頁積累到一定數量時，就形成了無用的垃圾(garbage)。為充分利用閃存的存儲空間，需要選擇回收塊(victim block)進行垃圾回收將無效頁擦除。但由于NAND閃存擦除的基本單位是塊，因此在擦除前需要將回收塊中的全部有效頁復制到另一空閑塊。對閃存而言，擦除操作的速度比讀寫操作慢很多，且需要更大的功耗[6]。此外，閃存可支持的每個塊的擦除次數具有上限。因此，在考慮減少物理塊的擦除次數與回收代價的同時，提高閃存磨損均衡程度，是提高閃存讀寫性能并延長使用壽命的研究重點。

為了提升NAND閃存垃圾回收的效率與性能，中外學者們提出了諸多垃圾回收算法，這些算法的管理粒度主要分為塊、頁。

GR(GReedy)算法[7]、CB(cost-benefit)算法[8]、CAT(cost-age-time)算法[9]、WOGC(write order-based garbage collection)算法[10]是經典的以塊為管理粒度的垃圾回收算法。GR算法將有效頁最少的塊選為回收塊，以降低回收代價，但未考慮塊的磨損均衡度。CB算法在考慮塊中無效頁占比的同時將物理塊的年齡納入考量，以獲得更好的磨損均衡。CAT算法在CB算法的基礎上考慮了物理塊的擦除次數，在讀寫性能和磨損均衡取得了較好的平衡。但CAT仍存在不足，一是CAT算法需利用絕對時間來計算年齡，設備斷電后可能導致年齡信息丟失；二是其年齡計算對時間敏感，針對不同工作負載需要試探性地確定計算方法[10]；WOGC算法用寫序號代替CAT算法中的年齡，以避免上述不足。

為了進一步提高算法性能，需要更準確地計算數據熱度，因此基于頁的垃圾回收算法的提出，如FaGC(file-aware garbage collection)算法[11]證明以邏輯頁為管理粒度能大幅提升算法性能。FaGC算法基于文件結構，對邏輯頁熱度進行準確定義，并將熱數據存儲到擦除次數最少的塊中，而將冷數據存儲到擦除次數最多的塊中，有效實現數據的冷熱分離，在磨損均衡方面增加考慮了最冷塊的回收。該算法在性能方面獲得了很大提升，但為了保存邏輯頁熱度需額外占用大量內存空間。為減少內存消耗，LRGC(logic region-based garbage collection)算法[12]， LRGC+(logic region-based garbage collection plus)算法[13]。LRGC與LRGC+算法考慮了訪問的空間局部性，將連續邏輯地址空間劃分為同一個熱度區間，用邏輯區間熱度替代邏輯頁熱度，以減少額外的內存消耗。與FaGC算法相比，這兩種算法在減少內存消耗的同時，進一步提升了垃圾回收的性能，但在邏輯區間較大時，冷頁與熱頁可能被強行劃分在一個區間中，造成數據熱度判斷失誤。另外，FaGC、LRGC與LRGC+算法的熱度計算仍然基于邏輯頁或邏輯區間前后兩次更新操作的時間間隔，因此存在時間敏感的局限性，以及在實際使用中可能存在的無操作休眠時間會對熱度計算造成影響。

針對當前垃圾回收算法占用大量內存與性能不足的問題，提出一種基于塊更新序號的垃圾回收算法，即UsnGC(update sequence number based garbage collection)算法。該算法將管理粒度定位到塊，基于塊更新順序對塊進行熱度計算，以對有效數據進行冷熱分離；同時，給出了新的回收塊選擇策略以兼顧磨損均衡效果和減少垃圾回收代價。

1 UsnGC算法

1.1 算法概述

考慮到NAND閃存擦除操作的基本單位為塊，且基于頁的垃圾回收算法勢必帶來大量內存消耗，UsnGC算法將管理粒度重新定位到塊，提出以塊更新序號來計算塊更新周期和系統平均更新周期，并結合系統平均更新周期來計算塊的熱度值。根據分散度來觸發垃圾回收，同時采用混合回收策略選出回收塊，然后將回收塊中的有效頁進行有效的冷熱分離，最終提升垃圾回收效率和磨損均衡效果。

為了區分新舊數據頁的寫操作，我們把新數據的寫操作定義為新寫操作，把舊數據的寫操作定義為更新操作，二者統稱為寫操作。同時，為避免重復描述參數定義，列出本文中主要使用的參數及其定義，如表1所示。

表1 主要使用的參數及其定義

1.2 更新序號

本文中提出一個稱為更新序號(update sequence number, USN)的計數器來記錄塊的更新情況。USN為全局變量。同時，設置一張單獨的塊信息表來存儲每個物理塊的當前更新序號USNi(i=1, 2,…,Nblock)。如圖1所示為塊更新序號確定算法示例。

圖1 塊更新序號確定算法示例

“異地更新”策略將舊數據所在的頁(稱為舊頁)標記為無效頁，將新數據寫入另一空閑物理頁，因此USN會隨著數據寫入塊(即寫操作)而遞增。最初，USN被設置為0，每當NAND閃存的塊完成1次寫操作時，該變量加1。若該寫操作為更新操作，則在寫操作完成后，將新的全局USN值賦值給舊頁所在塊的USNi。同時，若寫入塊為首次寫入，新的全局USN值同樣賦值給寫入塊的USNi。需要強調的是，當連續的頁寫操作是對同一個塊的更新操作時，USN僅遞增一次。如圖1所示，假設已存在7個數據頁，當前全局USN為10，塊1、2、3的當前USNi分別為3、7、8，即USN1=3，USN2=7，USN3=8。依次更新頁2、3、5、4。按照上述算法，由于頁2、3連續更新且源自同一個塊，Step1完成后USN僅增加1后為11，USN1則由3變為11。Step2先更新頁5，那么USN加1后為12，則USN2也為12；接著更新頁4，USN加1后為13，然后USN1為13。依次更新頁2、3、5、4后的全局USN和塊1、2和3的數值如圖1中Step3所示。

1.3 塊熱度定義

UsnGC算法以塊為單位計算熱度，當且僅當物理塊進行1次或連續多次更新操作時才觸發1次塊熱度計算。為避免塊內少數頁更新造成整個塊熱度的驟升而導致塊內大部分頁的熱度誤判，考慮用上一次塊熱度值與當前塊更新周期共同決定當前塊的熱度。定義全局變量n、S，n記錄熱度計算次數，初始值為0，每次觸發熱度計算后遞增1；S記錄更新周期的累計和。假設對物理塊i(i=1, 2,…,Nblock)的更新引起了第n次熱度計算，則塊熱度的計算步驟如下。

首先，計算當前物理塊i的更新周期Ti，Ti為臨時變量，在完成本次熱度計算后即可釋放，計算公式為

(1)

然后，計算更新周期的累計和S，以及系統的平均更新周期Tavg，計算公式為

S→S+Ti

(2)

(3)

最后，為了準確計算塊的當前熱度以更好地進行數據冷熱分離，將式(3)得出的平均更新周期Tavg作為分段計算依據，再結合塊的上一次熱度計算出塊的當前熱度。基于式(1)～式(3)的物理塊熱度分段計算函數為

(4)

式(4)中：Ht+1和Ht分別表示塊的當前熱度值、塊的上一次熱度值。把塊熱度值限定在[Hmin,Hmax]的范圍內。一般地，Hmin取1，Hmax取每個物理塊所包含頁數的4倍；c是一個常量，一般取1。

1.4 回收塊選擇策略

NAND閃存系統進行垃圾回收時，為了提高回收效率，要考慮選中的回收塊有效頁少，以減少垃圾回收引起的拷貝次數。由于NAND閃存的塊擦除次數具有上限，磨損均衡度影響其使用壽命，因此在回收塊選擇策略中，采取包含了常規回收策略與最冷塊回收策略的混合策略。

(1)常規回收策略采用一種綜合考慮回收效率和磨損均衡的回收代價函數，即

(5)

式(5)中：u表示一個物理塊中有效頁的占比；εi和εmin分別表示當前物理塊的已擦除次數、當前系統中物理塊的最小擦除次數。塊的有效頁占比越小、擦除次數越少、最近一次更新周期越小，則C值越小。顯然，UsnGC算法選擇C值最小的塊為回收塊。該回收代價函數可很好地避免在只考慮有效頁占比與擦除次數時，閃存中出現較多最冷塊，最冷塊的有效頁比例高甚至全為有效頁且最冷塊長時間未更新，這些最冷塊的存在會導致磨損均衡較差。

(2)最冷塊回收策略用于進一步減少最冷塊的存在并改善磨損均衡效果，該策略選擇擦除次數最少的塊為回收塊。

(3)混合策略設置動態變化的閾值Te控制在常規回收策略與最冷塊回收策略之間的合理切換，其定義為

(6)

(7)

式中：Twl表示控制混合策略切換的初始閾值；Nvalid表示全為有效頁或只有一頁為無效頁的塊數；δ為Nvalid在系統中所占比例，在垃圾回收過程結束時對δ進行更新；εmax和εmin分別表示當前系統中物理塊的最大、最小擦除次數。在觸發垃圾回收后，計算系統當前擦除次數與上一次啟動最冷塊回收策略時系統擦除次數的差值，若差值大于閾值Te，則啟動最冷塊回收策略，記錄本次啟動的系統擦除次數并重新計算Te；否則，采用常規回收策略進行回收塊的選擇。

1.5 垃圾回收的啟動時機

為選擇合適的時機來進行垃圾回收，以避免不必要的回收操作，引入分散度[3]的概念為

(8)

式(8)中：Nf表示當前所有物理塊的空閑頁總數目；Nb表示當前NAND閃存中的空閑物理塊數目；Np表示每個物理塊上包含的物理頁數目。分散度越高，表明當前系統中空閑塊越少且空閑頁的分布越分散，啟動垃圾回收帶來的效益才越大。選取適當閾值Fth，當Fsc達到該閾值時才啟動垃圾回收，可減少垃圾回收次數。

1.6 數據冷熱分離

由于NAND閃存的“異地更新”策略，為了減少擦除次數以及垃圾回收過程中對回收塊中有效頁的拷貝操作，需對數據進行冷熱分離。恰當的冷熱分離后，同一個物理塊上的數據擁有相似的熱度值即相近的更新頻率，一般情況下這些數據有更大的概率同時變為無效，由此有更多的無效頁、更少的有效頁。UsnGC算法將有效數據分為熱數據、次熱數據、次冷數據和冷數據四類，分別存儲到不同的空閑塊中，以提高回收效率。具體的數據冷熱分離步驟如下。

(1)根據有效頁數據所在物理塊編號，結合式(1)～式(4)計算出該物理塊熱度Ht，即為該有效頁熱度。

(2)若Ht>3Hmax/4，則有效頁為熱數據頁，數據遷移目標為擦除次數最少的空閑塊。

(3)若Hmax/2

(4)若Hmax/4

(5)若Ht≤Hmax/4，則有效頁為冷數據頁，數據遷移目標為擦除次數最多的空閑塊。

2 實驗環境

對于操作系統框架中的NAND閃存管理體系，目前主要可分為以下兩種類型：一是基于閃存專用文件系統(圖2)，如JFFS、YAFFS；二是基于閃存轉換層(flash translation layer, FTL)。

圖2 基于專用文件系統的NAND閃存系統結構

由于閃存專用文件系統對閃存存儲特性更具針對性，相關算法能直接進行地址映射、垃圾回收、磨損均衡的管理，比FTL文件管理系統更高效可靠，因此本文選擇在VMware和Ubuntu14.0的環境下，基于Linux和QEMU搭建嵌入式仿真平臺，NAND閃存借助NANDSim模擬，并通過對文件系統YAFFS2的移植以進行閃存管理。

如表2所示實驗對象選取存儲容量為64 MB的NAND閃存，其共有512個物理塊，每個物理塊由64個物理頁組成，每頁的容量為2 048 B。測試文件由測試程序隨機創建，單個文件的大小在16～1 024 KB，測試文件總體對NAND閃存存儲空間的占用率為90%，完成測試文件創建后，對其中15%的數據按照齊夫分布[3]進行更新。為了對不同算法的性能進行公平客觀的比較，取消后臺垃圾回收并關閉緩存功能，且YAFFS2文件系統的垃圾回收都采用aggressive模式。仿真實驗中各項參數如表2所示。

表2 實驗參數設定值

3 實驗結果與分析

選取GR、CB、CAT、FaGC、LRGC和LRGC+算法為本文提出UsnGC算法的實驗對比算法，對比指標包括垃圾回收效率與磨損均衡效果兩個方面。垃圾回收效率包括NAND閃存物理塊總的擦除次數、總的拷貝次數，磨損均衡效果包括系統中所有物理塊擦除次數的最大差值、物理塊擦除次數標準差。其中，擦除次數與拷貝次數越少，表明垃圾回收效率越高；物理塊擦除次數的最大差值與擦除次數標準差越小，表明磨損均衡效果越好。

LRGC和LRGC+算法的邏輯區間長度記作M，由于UsnGC算法的管理粒度為塊，可類比于M=64，參照圖3、圖4中M=64的情況可知，UsnGC算法在總擦除次數、總拷貝次數兩個指標下的表現明顯好于對比的6種算法。LRGC和LRGC+算法的總擦除次數與總拷貝次數隨著M的取值增大而增大，這是由于邏輯區間增大后，極有可能將更新頻率不同的邏輯頁強行劃分為同一熱度，導致冷熱分離不準確。UsnGC算法考慮到NAND閃存特性，以物理塊管理，隨著更新的進行，不同更新頻率的頁將逐漸聚集到相近頻率的塊上。即使在LRGC和LRGC+算法M=1的情況下，UsnGC算法在這兩個指標上的性能表現依然更好。原因在于UsnGC算法采取動態閾值對塊更新頻率進行分段處理，并結合塊的歷史熱度線性地計算當前熱度，可根據系統使用情況動態調整熱度計算，減少熱度誤判，優化冷熱分離效果。同時，將有效數據分為冷、次冷、次熱、熱四類，進一步提高了冷熱分離的精度，確保遷移進同一物理塊的數據具有相近更新頻率，減少回收塊中有效頁占比，從而降低回收代價。

圖3 總的擦除次數對比

圖4 總的拷貝次數對比

由于LRGC和LRGC+算法在M=1時，與UsnGC算法的擦除次數和拷貝次數接近，為了更合理比較不同算法的磨損均衡效果，對比LRGC和LRGC+算法時選取M=1。如圖5和圖6分別展示了各個算法的最大最小擦除次數的差值和物理塊擦除次數的標準差。可以看出FaGC、LRGC、LRGC+和UsnGC算法的磨損均衡表現明顯優于其他算法。這是因為GR、CB和CAT算法雖然已在回收塊有效頁數目少的標準下逐步增加對物理塊年齡、物理塊擦除次數的考量，但未進行冷熱數據分離；FaGC算法在不觸發最冷塊回收策略時仍選取無效頁最多的塊為回收塊；LRGC和LRGC+算法分別采用固定比重因子和動態權重來調節回收效率與磨損均衡的影響，但使用固定閾值計算有效頁當前熱度；而UsnGC算法的回收代價函數兼顧回收效率與磨損均衡，有效數據熱度計算采取動態閾值分段處理且數據分類更加精確，因而在磨損均衡方面取得了更好的表現。

圖5 擦除次數的最大差值對比

圖6 擦除次數的標準差對比

3.1 內存消耗

如表2所示以存儲容量為64 MB的NAND閃存為例，其物理塊總數為512，每塊有64個物理頁，則物理頁總數為512×64=32 768，存儲每個信息需消耗4 B內存。GR算法不需要占據額外內存；CB算法消耗512×4 B=2 kB以存儲每個物理塊的年齡信息；CAT算法在CB基礎上增加記錄擦除次數，因此需消耗內存512×8 B=4 kB；FaGC、LRGC和LRGC+算法在記錄每個塊的擦除次數之外，還需構建熱度表以存儲每個邏輯頁或每個邏輯區間的更新時間和熱度值，因此需要消耗內存32 768×8 B+512×4 B=258 kB；UsnGC算法則只需在記錄每個塊的擦除次數之外，記錄每個塊的更新序號和熱度值，因此僅消耗內存512×12 B=6 kB。

表3 內存消耗

4 結論

最初垃圾回收算法的管理粒度為塊，無需占用大量內存，但算法性能有限。后續研究考慮基于頁管理，以額外消耗內存為代價獲得了性能的大幅提升。為了提升垃圾回收算法的性能，并減少NAND閃存內存的犧牲，提出了一種基于塊更新序號的動態閾值數據冷熱分離的垃圾回收算法UsnGC。UsnGC算法將管理粒度重新定位到塊，基于塊的更新序號定義有效數據熱度的分段計算，提出一種兼顧回收效率與磨損均衡的回收代價函數，實現對數據的冷熱分離。實驗結果表明，與主流垃圾回收算法相比，UsnGC算法在大幅減少系統內存消耗的同時，在磨損均衡效果與垃圾回收效率兩方面都取得了更好的表現。