基于數據更新間隔的NAND 閃存垃圾回收算法

余 進，嚴 華

（四川大學 電子信息學院，成都 610065）

0 概述

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

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

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

1 基于數據更新間隔的垃圾回收算法

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

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

1.1 分散度判斷

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

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

算法1分散度判斷算法

1.2 回收塊選擇

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

1.2.1 動態回收塊選擇

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

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

1.2.2 靜態回收塊選擇

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

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

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

算法2回收塊選擇算法

1.3 數據分離

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

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

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

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

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

算法3數據分離算法

2 實驗結果與分析

2.1 實驗環境

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

表2 實驗參數Table 2 Experimental parameters

2.2 結果分析

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

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

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

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

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

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

圖5 各算法擦除次數標準差對比Fig.5 Comparison of standard deviation of erasure times of each algorithm

3 結束語

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