基于數(shù)據(jù)更新間隔的NAND 閃存垃圾回收算法

余 進(jìn)，嚴(yán) 華

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

0 概述

NAND 閃存具有體積小、速度快、價格低、非易失等優(yōu)點，在電子設(shè)備的數(shù)據(jù)存儲中被廣泛應(yīng)用［1-2］。NAND 閃存在結(jié)構(gòu)上由若干個物理塊組成，每個物理塊又由若干個物理頁組成。在NAND 閃存中，數(shù)據(jù)讀寫以頁為單位進(jìn)行，數(shù)據(jù)擦除以塊為單位進(jìn)行，數(shù)據(jù)更新則采用異地更新策略［3-4］。NAND 數(shù)據(jù)在進(jìn)行更新時，不能直接將新數(shù)據(jù)覆寫在原數(shù)據(jù)位置，需要將原始數(shù)據(jù)標(biāo)記為無效，再將新數(shù)據(jù)寫到其他空閑頁［5-6］。異地更新策略會導(dǎo)致NAND 閃存中產(chǎn)生大量無效頁，無效頁需要經(jīng)過擦除操作變?yōu)榭臻e頁后才可再次使用，因此，合理地處理無效頁可以大幅提高NAND 閃存的存儲效率，這一過程也被稱為垃圾回收［7-8］。同時，NAND 閃存每個塊的擦除次數(shù)存在上限［9-10］，為避免某些塊被頻繁擦除而導(dǎo)致無法使用，在擦除過程中應(yīng)盡量使操作均勻分布在各個塊上，這一過程被稱為磨損均衡［11］。磨損均衡效果好的垃圾回收算法是提高NAND 閃存使用效率、延長其使用壽命的關(guān)鍵［12］。

近年來，研究人員提出了許多垃圾回收算法。WU 等提出一種GR 算法［13］，該算法選取有效頁比例最小的塊進(jìn)行回收，垃圾回收效率較高，但是其未考慮磨損均衡效果。KAWAGUCHI 等提出一種CB（Cost-Benefit）算法［14］，該算法選取有效頁比例小且距上一次更新時間長的塊進(jìn)行回收，其磨損均衡效果較GR 算法有一定提升。CHIANG 等提出一種CAT（Cost-Age-Time）算法［15］，其在CB 算法的基礎(chǔ)上選擇擦除次數(shù)最小的塊進(jìn)行回收，同時將回收塊中冷熱數(shù)據(jù)分開存儲在不同塊中，磨損均衡效果有了進(jìn)一步提升，但該算法依據(jù)塊的擦除次數(shù)區(qū)分?jǐn)?shù)據(jù)冷熱，準(zhǔn)確性不高。YAN 等提出一種FaGC（Fileaware Garbage Collection）算法［16］，該算法基于GR 算法進(jìn)行回收塊選取，根據(jù)頁的更新頻率區(qū)分回收塊中有效頁的冷熱，其能取得較好的磨損均衡效果。HUANG 等提出FaGC+算法［17］，其在FaGC 算法的基礎(chǔ)上，選擇各邏輯頁更新間隔累加和最大的塊進(jìn)行回收，同時使用邏輯頁更新序號改進(jìn)回收塊中有效頁熱度的計算公式，進(jìn)一步提升了磨損均衡效果，但是該算法僅考慮邏輯頁上一次的更新序號，并以此進(jìn)行回收塊選取和熱度計算，缺少對邏輯頁整體更新情況的考慮。

本文考慮閃存中數(shù)據(jù)整體的更新情況，提出一種基于數(shù)據(jù)更新間隔的垃圾回收（UIGC）算法。UIGC 算法綜合考慮塊中無效頁年齡累計和以及塊中有效頁比例，結(jié)合物理塊磨損均衡效果選取回收塊，并根據(jù)回收塊中有效頁熱度和數(shù)據(jù)更新穩(wěn)定性，將有效頁數(shù)據(jù)進(jìn)行分塊存儲，從而提高塊中數(shù)據(jù)的同步更新概率。

1 基于數(shù)據(jù)更新間隔的垃圾回收算法

UIGC 算法進(jìn)行垃圾回收的過程由分散度判斷、回收塊選擇、數(shù)據(jù)分離3 個部分組成，算法整體流程如圖1 所示：首先，計算閃存中空閑頁分散度，判斷是否進(jìn)入回收塊選擇階段；在回收塊選擇階段，根據(jù)閃存狀態(tài)選擇合適的策略進(jìn)行回收塊選擇；最后處理回收塊中的有效頁，將不同類型的有效頁數(shù)據(jù)遷移至不同的塊中。在數(shù)據(jù)分離完成后，將原有效頁標(biāo)記為無效，對全為無效頁的塊進(jìn)行塊擦除操作，從而完成一次垃圾回收過程。

圖1 基于數(shù)據(jù)更新間隔的垃圾回收算法流程Fig.1 Procedure of garbage collection algorithm based on data update interval

1.1 分散度判斷

為了提高垃圾回收效率，UIGC 算法使用分散度的概念作為回收塊選擇過程的觸發(fā)條件［18］。分散度計算公式如式（1）所示：

其中：Nfc為閃存中空閑頁的總數(shù)；Nfb為空閑塊的總數(shù)；Nc為單個物理塊中頁的數(shù)量。分散度S表示閃存中空閑頁的分布情況，空閑頁分布越分散，S值越大，反之S值越小。當(dāng)S大于閾值fsc時，啟動回收塊選擇策略。當(dāng)閃存中空閑頁分布比較分散時，文件系統(tǒng)需要頻繁尋找可用塊，降低了閃存使用效率，此時進(jìn)行垃圾回收，在降低分散度的同時也能產(chǎn)生更多的空閑頁，從而提高垃圾回收的效率。分散度判斷過程描述如算法1 所示。

算法1分散度判斷算法

1.2 回收塊選擇

在回收塊選擇策略上，大部分研究考慮塊中無效頁比例以及物理塊上一次更新時間間隔，此為垃圾回收效率上的考量。本文回收塊選擇策略由常規(guī)狀態(tài)下的動態(tài)回收塊選擇策略以及特定狀態(tài)下的靜態(tài)回收塊選擇策略組成，分2 個部分綜合考慮閃存的回收效率以及磨損均衡效果。

1.2.1 動態(tài)回收塊選擇

本文基于頁序號概念設(shè)計動態(tài)回收塊選擇策略［17］，綜合考慮回收塊中有效頁比例以及無效頁年齡，最終使用的動態(tài)回收塊選擇公式如式（2）所示：

其中：u為塊中有效頁比例；n為塊中無效頁數(shù)量；Snow為啟動垃圾回收時的頁序號；Si為對應(yīng)的物理頁變成無效頁時的頁序號；Snow-Si表示對應(yīng)的無效頁年齡。式（2）計算塊中所有無效頁年齡累加和，同時考慮塊中有效頁比例，綜合選取塊中無效頁年齡大且有效頁比例小的塊進(jìn)行回收，即最終選擇CCB值最大的塊作為回收塊，以此降低回收塊中有效頁的數(shù)量，減少垃圾回收時遷移有效數(shù)據(jù)帶來的頁拷貝操作開銷，提高垃圾回收效率。

1.2.2 靜態(tài)回收塊選擇

在數(shù)據(jù)非隨機(jī)寫入時，存在部分物理塊中有效頁比例較高但長期未得到更新的情況，此時使用動態(tài)回收塊選擇策略將無法選擇到該塊進(jìn)行回收，從而影響算法整體的磨損均衡效果。針對此類情況，本文在動態(tài)回收塊選擇策略的基礎(chǔ)上，設(shè)計靜態(tài)回收塊選擇策略，以改善算法的磨損均衡效果。

啟動靜態(tài)回收塊選擇策略的條件為閃存中物理塊的最大擦除次數(shù)和最小擦除次數(shù)之差大于閾值Te，閾值Te的計算公式如式（3）所示：

其中：Nblock為閃存系統(tǒng)中物理塊總數(shù)；Nvalid為全是有效頁的塊的數(shù)量；Twl為初始設(shè)置閾值。靜態(tài)回收塊選擇策略直接選擇擦除次數(shù)最少的塊進(jìn)行回收，當(dāng)擦除次數(shù)一樣時，優(yōu)先選擇塊中有效頁比例小的塊進(jìn)行回收。算法每進(jìn)行一次垃圾回收過程，則更新閃存系統(tǒng)中的Nvalid值，重新計算策略選擇閾值Te。通過2 種策略切換的回收塊選擇方式，在保證閃存系統(tǒng)垃圾回收效率的同時，使塊擦除操作均勻分布在各個物理塊上，從而提升算法的磨損均衡效果?；厥諌K選擇具體處理流程如算法2 所示。

算法2回收塊選擇算法

1.3 數(shù)據(jù)分離

若回收塊中存在有效頁，回收時需要先將塊中存在的有效頁數(shù)據(jù)遷移到其他空閑頁中，并將該有效頁置為無效頁。若將更新間隔相近的數(shù)據(jù)遷移到同一塊中，則該塊中有效頁將有較大概率同時變?yōu)闊o效頁，從而降低回收塊中有效頁比例，提高垃圾回收效率［19］。在FaGC+算法的基礎(chǔ)上，本文重新設(shè)計數(shù)據(jù)熱度計算公式，根據(jù)回收塊中有效頁更新間隔判斷熱度，相關(guān)計算公式如式（4）、式（5）所示：

其中：Di為對應(yīng)物理塊被分配使用時的頁序號；ui為對應(yīng)物理塊中有效頁比例；Slast為回收塊中有效頁數(shù)據(jù)上一次更新時的頁序號。式（4）計算得到的AAI表示垃圾回收時閃存中有效頁數(shù)據(jù)全局平均更新間隔，式（5）計算得到的UUI表示回收塊中有效頁當(dāng)前更新間隔。當(dāng)回收塊中有效頁當(dāng)前更新間隔UUI大于全局平均更新間隔AAI時，有效頁數(shù)據(jù)定義為熱數(shù)據(jù)，反之定義為冷數(shù)據(jù)。本文將冷熱數(shù)據(jù)做了進(jìn)一步劃分，分別以AAI/2 和AAI×3/2 為界限，將數(shù)據(jù)依次劃分為冷頁、次冷頁、次熱頁、熱頁4 種類型。

閃存系統(tǒng)在實際使用過程中，由于數(shù)據(jù)使用情況的不同，存在定期更新和不定期更新數(shù)據(jù)，即各數(shù)據(jù)前后更新間隔的變化幅度存在差異，本文將這種數(shù)據(jù)更新間隔變化幅度定義為數(shù)據(jù)更新穩(wěn)定性。為進(jìn)一步提升垃圾回收效率，本文在根據(jù)回收塊中有效頁更新間隔進(jìn)行熱度劃分的同時，判斷有效頁中數(shù)據(jù)更新穩(wěn)定性，將穩(wěn)定更新數(shù)據(jù)和不穩(wěn)定更新數(shù)據(jù)分塊存儲，相關(guān)計算公式如式（6）～式（8）所示：

其中：Sinit為有效頁數(shù)據(jù)初次寫入時的頁序號；c為有效頁數(shù)據(jù)更新次數(shù)；Iave為有效頁數(shù)據(jù)平均更新間隔；Spred為利用平均更新間隔預(yù)測得到的當(dāng)前更新序號值；DDF為當(dāng)前實際序號與預(yù)測序號之間的絕對差值。當(dāng)計算得到的DDF值大于Iave/2 時，說明該有效頁當(dāng)前更新間隔與其平均更新間隔差距過大，數(shù)據(jù)前后更新間隔幅度變化劇烈，處于不穩(wěn)定更新狀態(tài)，反之?dāng)?shù)據(jù)則為穩(wěn)定更新狀態(tài)。算法將穩(wěn)定更新的數(shù)據(jù)按熱度分塊存儲，使得塊中數(shù)據(jù)擁有穩(wěn)定且相近的更新間隔，從而進(jìn)一步提高塊中數(shù)據(jù)同步更新的概率以及垃圾回收效率。結(jié)合數(shù)據(jù)熱度和更新穩(wěn)定性進(jìn)行有效頁類型劃分，結(jié)果如表1 所示，數(shù)據(jù)分離過程如算法3 所示。

表1 有效頁類型劃分Table 1 Type division of valid pages

算法3數(shù)據(jù)分離算法

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

2.1 實驗環(huán)境

本文在Ubuntu20.04 平臺上使用QEMU（Quick EMUlator）搭建基于Linux2.6 的嵌入式仿真系統(tǒng)［20］，并使用NANDsim 模擬NAND 閃存，在移植Yaffs2 文件系統(tǒng)后［21］編寫程序進(jìn)行測試。模擬出的NAND 閃存容量為64 MB，其中物理塊的大小為128 KB，物理頁的大小為2 KB。測試程序隨機(jī)創(chuàng)建出大小為16～1 024 KB 的文件，創(chuàng)建文件的總和占NAND 總?cè)萘康?0%，隨后對其中15%的內(nèi)容按齊夫分布進(jìn)行更新操作［22-23］。本文選取GR、CB、CAT、FaGC、FaGC+這5 種算法與UIGC 算法進(jìn)行對比測試。為了保證對比測試的公平進(jìn)行，實驗關(guān)閉Yaffs2 文件系統(tǒng)的緩存功能和后臺垃圾回收，所有實驗均在aggressive模式下完成。實驗相關(guān)參數(shù)設(shè)定如表2 所示。

表2 實驗參數(shù)Table 2 Experimental parameters

2.2 結(jié)果分析

本文主要從塊擦除操作總數(shù)、頁拷貝操作總數(shù)、塊擦除次數(shù)標(biāo)準(zhǔn)差等方面分析比較垃圾回收算法性能，根據(jù)擦除和拷貝操作總數(shù)考察算法垃圾回收效率，根據(jù)塊擦除次數(shù)標(biāo)準(zhǔn)差考察算法磨損均衡能力。

圖2 和圖3 分別對比使用不同算法進(jìn)行測試時閃存中塊擦除次數(shù)和頁拷貝次數(shù)。從中可以看出：UIGC 算法在垃圾回收時實現(xiàn)了更低的塊擦除次數(shù)和頁拷貝次數(shù)；CAT 算法在GR、CB 算法的基礎(chǔ)上進(jìn)行數(shù)據(jù)冷熱分離，磨損均衡效果有了較大提升，由于回收塊選擇部分改進(jìn)不大，且僅以擦除次數(shù)來區(qū)分?jǐn)?shù)據(jù)冷熱，不夠準(zhǔn)確，造成了一些額外的擦除和拷貝操作，因此，其在提升磨損均衡效果的同時反而增加了擦除和拷貝次數(shù)；FaGC 算法改進(jìn)了數(shù)據(jù)分離算法，以數(shù)據(jù)更新頻率區(qū)分?jǐn)?shù)據(jù)的冷熱，進(jìn)一步提升了磨損均衡效果，降低了擦除和拷貝操作次數(shù)；FaGC+算法在FaGC 算法的基礎(chǔ)上提出頁序號的概念，同時改進(jìn)回收塊選擇策略，提高了回收塊選擇和數(shù)據(jù)冷熱劃分的準(zhǔn)確性；UIGC 算法在選取回收塊時，考慮塊中無效頁年齡累計和以及塊中有效頁比例，選取無效頁多且年齡和大的塊作為回收塊，有效減少了處理回收塊時造成的頁拷貝操作次數(shù)，UIGC 算法從全局角度對回收塊中有效頁數(shù)據(jù)進(jìn)行熱度劃分，避免了自定義熱度參數(shù)導(dǎo)致的局限性，此外，該算法提出數(shù)據(jù)更新穩(wěn)定性的概念，根據(jù)數(shù)據(jù)熱度和更新穩(wěn)定性將回收塊中有效頁數(shù)據(jù)分塊存儲，提高同一塊中數(shù)據(jù)的同步更新概率，配合分散度判斷，大幅降低了垃圾回收程序被觸發(fā)的次數(shù)，有效減少了塊擦除次數(shù)，進(jìn)一步提高了算法的垃圾回收效率。

圖2 各算法塊擦除次數(shù)對比Fig.2 Comparison of block erasure times of each algorithm

圖3 各算法頁拷貝次數(shù)對比Fig.3 Comparison of page copy times of each algorithm

圖4 對比了使用不同算法進(jìn)行測試時每個物理塊的擦除次數(shù)分布情況，圖5 顯示了各塊擦除次數(shù)標(biāo)準(zhǔn)差隨著擦除次數(shù)的變化情況。從圖4、圖5 可以看出：UIGC 算法得到的各塊擦除次數(shù)分布均勻，維持在一個較低水平，且隨著擦除次數(shù)的增加，各塊擦除次數(shù)標(biāo)準(zhǔn)差始終保持穩(wěn)定，與FaGC+算法塊擦除次數(shù)標(biāo)準(zhǔn)差變化曲線基本重合；UIGC 算法在動態(tài)回收塊選擇的基礎(chǔ)上結(jié)合靜態(tài)回收塊選擇策略，在有效提升垃圾回收效率的同時，仍具有和FaGC+算法相近的磨損均衡效果，即具有更優(yōu)的垃圾回收性能。

圖4 物理塊擦除次數(shù)分布情況Fig.4 Distribution of erasure times of physical blocks

圖5 各算法擦除次數(shù)標(biāo)準(zhǔn)差對比Fig.5 Comparison of standard deviation of erasure times of each algorithm

3 結(jié)束語

為了優(yōu)化NAND 閃存在進(jìn)行垃圾回收時的性能表現(xiàn)，本文提出一種基于數(shù)據(jù)更新間隔的垃圾回收算法UIGC。選擇無效頁多且存在時間長的塊進(jìn)行回收，判斷回收塊中有效頁熱度以及數(shù)據(jù)更新穩(wěn)定性狀態(tài)，將不同類型的有效頁數(shù)據(jù)分塊存儲，同時以分散度作為回收塊選擇過程的觸發(fā)條件，從而在有效提高垃圾回收效率的同時保持較高的磨損均衡能力。實驗結(jié)果表明，UIGC 算法的垃圾回收效率以及磨損均衡效果優(yōu)于GR、CB 等算法。但是，UIGC 算法在實現(xiàn)過程中引入了額外的內(nèi)存空間來存儲數(shù)據(jù)更新的頁序號等信息，下一步考慮使用邏輯區(qū)間的方式減少額外存儲的數(shù)據(jù)量，以在保證垃圾回收性能的前提下降低額外的內(nèi)存空間消耗。