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

陳 琳， 嚴(yán) 華

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

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

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

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

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

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

1 UsnGC算法

1.1 算法概述

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

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

表1 主要使用的參數(shù)及其定義

1.2 更新序號

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

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

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

1.3 塊熱度定義

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

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

(1)

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

S→S+Ti

(2)

(3)

最后，為了準(zhǔn)確計算塊的當(dāng)前熱度以更好地進行數(shù)據(jù)冷熱分離，將式(3)得出的平均更新周期Tavg作為分段計算依據(jù)，再結(jié)合塊的上一次熱度計算出塊的當(dāng)前熱度?；谑?1)～式(3)的物理塊熱度分段計算函數(shù)為

(4)

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

1.4 回收塊選擇策略

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

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

(5)

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

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

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

(6)

(7)

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

1.5 垃圾回收的啟動時機

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

(8)

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

1.6 數(shù)據(jù)冷熱分離

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

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

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

(3)若Hmax/2

(4)若Hmax/4

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

2 實驗環(huán)境

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

圖2 基于專用文件系統(tǒng)的NAND閃存系統(tǒng)結(jié)構(gòu)

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

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

表2 實驗參數(shù)設(shè)定值

3 實驗結(jié)果與分析

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

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

圖3 總的擦除次數(shù)對比

圖4 總的拷貝次數(shù)對比

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

圖5 擦除次數(shù)的最大差值對比

圖6 擦除次數(shù)的標(biāo)準(zhǔn)差對比

3.1 內(nèi)存消耗

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

表3 內(nèi)存消耗

4 結(jié)論

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