0 引言

    NAND閃存具有體積小、抗震性能好、功耗低、無運行噪聲、存取速度快、便攜性好等特點，同時還具有遠超傳統機械硬盤的讀寫速度。因此，NAND閃存在各種電子產品中被廣泛應用，如手機、U盤、固態硬盤^[1-5]。

    NAND閃存具有如下特點：

    (1)NAND閃存的讀寫操作以頁(page)為單位，擦除操作以塊(block)為單位。NAND閃存的寫操作耗時遠大于讀操作，擦除操作耗時遠大于寫操作。

    (2)NAND閃存具有“寫前擦除”的特點，即在進行重復寫操作之前，必須先對寫入的存儲區進行擦除操作。

    (3)NAND閃存具有“異地更新”的特點。NAND閃存在對一個頁進行數據更新時，需要先將要更新的數據寫入新的空閑頁，然后將原數據頁標為無效頁。

    (4)NAND閃存具有有限的塊擦除次數。當某個塊的擦除次數超過一定值時，該塊將無法進行數據存儲，成為“壞塊”。

    NAND閃存中，會根據情況啟動回收塊選擇策略，對滿足回收塊選擇策略要求的塊進行擦除操作，用以回收無效頁所占的存儲空間，得到足夠的空閑空間來進行數據更新操作。

    在設計垃圾回收算法時應將減少垃圾回收代價、提高垃圾回收效率作為主要考慮點。同時，還要盡可能使每個物理塊均衡地參與到擦除操作中，從而提升閃存磨損均衡程度、延長使用壽命。

    MICHAEL W等提出了GR(Greedy)算法^[6]。GR算法選擇有效頁最少的塊進行回收。該算法的拷貝代價小，可回收較多的無效頁空間。其特點是算法實現簡單，回收效率較高。然而，當且僅當文件更新頻率均勻時，磨損均衡效果較好。若數據更新頻率相差較大，塊之間的擦除次數差別較大，磨損均衡效果較差。

    KAWAGUCHI A等提出了CB(Cost-Benefit)算法^[7]。該算法采用age×(1-u)/2u公式進行回收塊選擇，其值最大的塊將被選擇成為回收塊。其中u表示有效頁在單個塊中的比例，即物理塊更新的時間差，age表示塊的年齡。該算法考慮了塊的年齡，因此獲得比GR算法更好的效果。

    CHIANG M L等提出了CAT(Cost-Age-Times)算法^[8]。該算法采用age×(1-u)/(2u×n)公式進行回收塊選擇。其中u表示單個塊中的有效頁比例，age表示塊的年齡，n表示塊擦除次數。該算法在CB基礎上考慮了塊擦除次數，比CB具有更好的磨損均衡效果。

    Yan Hua等提出了FaGC(File-aware Garbage Collection)算法^[9]。該算法沿用GR算法的回收塊選擇策略，且根據邏輯頁更新頻率進行冷熱數據的劃分。數據冷熱分離時，冷數據分配到擦除次數最多的塊，而熱數據則分配到擦除次數最少的塊。

    石樂健等提出了一種基于物理塊年齡和邏輯頁熱度的磨損均衡算法GCbAH(GC based Age and Hot)^[10]。該算法選擇無效頁年齡和最大的塊作為回收塊。同時，采用了與FaGC不同的熱度計算公式來進行冷熱數據的劃分。在回收時，使用熱數據回收策略回收熱塊，使用冷數據回收策略回收冷塊。

    綜上所述，相較于GR、CB、CAT等經典算法，FaGC和GCbAH考慮了邏輯頁的冷熱分離，進一步減少了垃圾回收代價，取得了更好的磨損均衡效果。但是，FaGC和GCbAH均采用固定的預設閾值來作為判定冷熱數據的標準，并不能準確反映邏輯頁的冷熱程度。針對這個問題，本文提出了一種基于邏輯頁平均更新頻率的閃存垃圾回收算法AUFbGC(Average Update Frequency based Garbage Collection Algorithm)。該算法采用了一種新的熱度計算公式，并采用邏輯頁平均更新頻率取代固定閾值作為冷熱數據的判定依據，取得了更好的效果。

1 算法描述

1.1 算法原理

    NAND閃存進行垃圾回收時有如下操作：

    (1)根據回收塊選擇策略，進行回收塊選擇；

    (2)拷貝回收塊中的有效數據至空閑塊；

    (3)將被拷貝的有效數據所對應的原數據頁標記為無效頁；

    (4)對選中的回收塊進行擦除操作；

    (5)回收塊被擦除后成為空閑塊。

    如圖1所示，AUFbGC算法選擇無效頁年齡和最大的塊作為回收塊，根據熱度計算公式和新的冷熱判定依據，對回收塊的有效數據進行冷熱分離，并將有效數據存入擦除次數最少的空閑塊中。

    和垃圾回收過程類似，AUFbGC算法在進行數據異地更新時也采用了冷熱分離策略以獲得更好的磨損均衡效果。

    AUFbGC算法主要包括三種策略：回收塊選擇策略、冷熱數據分離策略和空閑塊分配策略。

1.2 回收塊選擇策略

    AUFbGC算法在挑選回收塊時有兩種策略：采用無效頁年齡和選擇策略^[10-11]和自適應最冷塊選擇策略[9]。

其中，n為物理塊中的無效頁數目，agei為物理塊中第i頁變為無效頁的時長。CwA即物理塊中無效頁的年齡和。CwA值最大的塊將被選擇成為回收塊。采用年齡和進行選擇可以兼顧無效頁比例高的塊和有少量無效頁但長期未被回收的塊，可獲得更好的磨損均衡效果。

    同時，算法采用一種自適應策略對最冷塊進行回收。自適應最冷塊回收策略啟動條件如下：

其中，T_wl是先前被設置好用于控制磨損均衡程度的閾值，e_max是所有塊的最大擦除次數，e_min是所有塊的最小擦除次數。當e_max和e_min之間的差值增大，T_erase值越小，冷塊選擇策略越容易被調用。若T_erase值小于零，則將T_erase置零。當一個塊的擦除次數超過T_erase值時，最冷塊回收策略被調用。該策略將選擇有最小擦除次數的塊作為回收塊，以增加選中有較低更新頻率的邏輯頁的塊的幾率。如果有多個塊具有最小擦除次數，則選擇其中含有最少有效頁的塊作為回收塊。在每次冷塊回收策略被調用時，T_erase值會被計算和更新。

1.3 數據熱度定義

    在熱度判定上，FaGC以更新頻率作為判定數據熱度的標準，大于預先設置的特定閾值則為熱數據，反之則為冷數據。

    GCbAH通過上一次判定的熱度與熱度調節因子相乘作為本次熱度的計算標準。當邏輯頁兩次更新操作的時間差值大于特定值時，邏輯頁熱度被強制歸零，因此不能細分部分數據的冷熱程度。此外，GCbAH也采用預先設置的特定閾值作為判斷冷熱數據的標準。

    AUFbGC算法采用更新頻率作為衡量冷熱數據的指標^[12]，每個邏輯頁的更新頻率可通過如下公式進行計算。

其中，CurrentT是當前時間，IWT_i是該邏輯頁i的初始寫入時間。UPDC_i是邏輯頁i的更新次數。因此，FREQ_i代表邏輯頁i寫操作的更新間隔。

    衡量冷熱數據的標準如下：

其中，n是物理塊的總數，CurrentT是當前時間，AllocT是編號為i的塊被分配使用時的時間，u_i是該塊中有效頁的百分比。因此AverF_i代表有效頁的平均更新頻率。而每當回收塊選擇策略選中回收塊后，平均更新頻率AverFi會被立刻計算。

    當邏輯頁的更新頻率FREQ_i小于平均更新頻率AverF_i，則該邏輯頁包含的數據是為熱數據；當邏輯頁更新頻率時間FREQ_i大于平均更新頻率時間AverF_i，則為冷數據。

1.4 算法步驟

    使用無效頁年齡和與自適應最冷塊回收策略選擇到回收塊之后，根據回收塊中有效頁對應的熱度對數據進行冷熱分離，具體步驟如下：

    (1)根據邏輯頁i的當前更新時間CurrentT和初始寫入時間IWT_i及更新次數UPDC_i，根據式(3)得到該邏輯頁的更新頻率FREQ_i。

    (2)若邏輯頁的更新頻率FREQ_i小于平均更新頻率AverF_i，則該邏輯頁包含的數據為熱數據；反之則為冷數據；

    (3)將數據根據熱度進行冷熱分離，具有相似熱度的有效頁將會被存入同一個物理塊；

    (4)修改更新次數UPDC_i，用于下一次熱度的計算和更新操作。

2 實驗及分析

2.1 實驗環境

    實驗中使用VMware和Ubuntu 12.04平臺，使用QEMU搭建嵌入式Linux仿真環境，使用NANDSim來模擬NAND閃存，基于NAND閃存專用文件系統YAFFS2進行測試。

    測試程序隨機生成16 KB到1 024 KB大小的測試文件，所有測試文件總量占NAND閃存容量的90%。創建文件后，按照齊夫分布^[13]對其中15%的文件進行更新操作。

    實驗中，NAND閃存容量被設置為64 MB，包含512個物理塊，由512×64個頁組成，其中每個頁為2 048 B。為了公平對比不同算法，實驗時YAFFS2文件系統的緩存功能被關閉，且都采用aggressive模式以完成垃圾回收。自適應最冷塊回收策略采用的閾值和FaGC、GCbAH算法完全一樣。

2.2 算法性能分析

    本文將AUFbGC算法與GR、CB、CAT、FaGC及GCbAH算法在垃圾回收代價和磨損均衡效果兩個方面進行了比對。其中，垃圾回收代價主要考慮塊總擦除次數、頁總拷貝次數這兩個指標，磨損均衡效果主要考慮塊最大最小擦除次數差值、塊擦除次數標準差這兩個指標。同時，通過擦除次數分布圖也可直觀地觀察不同算法的磨損均衡效果。

    從圖2和圖3中可以看出FaGC、GCbAH和AUFbGC算法獲得了相對更小的塊總擦除次數和頁總拷貝次數。這是由于GR、CB、CAT算法中未考慮冷熱數據分離，而FaGC、GCbAH和AUFbGC考慮了較為準確的基于邏輯頁的冷熱分離。在這三種算法當中，FaGC和GCbAH在數據熱度進行定義時，均通過與事先設定的閾值進行比較，以劃分冷熱數據。AUFbGC算法有更準確的熱度計算公式和判據，可將熱度相近的邏輯頁更加準確地放在同一個空閑塊中。由于熱度相近，這些邏輯頁有更大可能同時被更新而變為無效，從而使該數據塊有盡可能少的有效頁，最終減少有效頁拷貝次數和塊擦除次數。

    在磨損均衡方面，從圖4對比中不難看出，GR算法的物理塊擦除次數最為分散，CB、CAT算法次之。FaGC、GCbAH和AUFbGC算法相對集中地分布在一個較小區域。其中，AUFbGC算法得到了較為良好的磨損均衡效果，擦除次數分布集中，且分布在較低值。

    不同算法的塊最大最小擦除次數差值如圖5所示，不同算法的擦除次數標準差如圖6所示。從圖5和圖6中可以得出，FaGC、GCbAH和AUFbGC算法在磨損均衡方面相對GR、CB、CAT有更優異的表現。一方面，FaGC、GCbAH和AUFbGC算法獲得了遠小于GR、CB、CAT算法的塊最大最小擦除次數差值；另一方面，這三種算法的擦除次數標準差呈收斂趨勢。這是因為GR算法僅考慮回收有效頁最少的物理塊，未考慮磨損均衡。盡管CB算法考慮了物理塊的年齡和有效頁的比例，CAT算法在CB算法的基礎上增添了塊擦除次數的考量，但CB、CAT算法既沒有考慮冷熱數據分離，對最冷塊的回收也不及時。FaGC、GCbAH和AUFbGC算法均采用了冷熱數據分離和自適應最冷塊回收策略，因此取得了更好的磨損均衡效果。同時，在這三種算法中，FaGC在回收塊選擇策略上沿用了GR算法，而GCbAH和AUFbGC算法的無效頁年齡和回收塊選擇策略可兼顧對無效頁比例高及無效頁比例不高但是很長時間未被回收的物理塊的回收，讓回收塊的選擇更加均衡。相較于GCbAH算法，AUFbGC算法在定義數據熱度時采用動態變化的平均更新頻率取代固定閾值作為比較標準，對冷熱數據的劃分更準確，分類效果更好，且AUFbGC算法不斷地將有效數據分配至擦除次數最少的塊，以減少不同塊擦除次數的差異。因此，AUFbGC算法的磨損均衡效果最好。

3 結論

    針對NAND閃存的特點，提出一種基于邏輯頁平均更新頻率的NAND閃存垃圾回收算法AUFbGC。該算法在FaGC和GCbAH算法基礎之上，重新定義了數據熱度計算公式和冷熱判斷依據。實驗結果表明，相較于GR、CB、CAT、FaGC和GCbAH算法，AUFbGC算法在NAND閃存垃圾回收代價和磨損均衡方面均取得了更好的效果。

參考文獻

[1] KIM J，KIM J M，NOH S H，et al.A space-efficient flash translation layer for CompactFlash systems[J].IEEE Transactions on Consumer Electronics，2002，48(2)：366-375.

[2] 白石，廖學良，胡事民.HFB:一種閃存上的塊頁混合緩存管理方法[J].清華大學學報(自然科學版)，2012(5)：688-693.

[3] CHEN R，LIN M.Energy-aware buffer management scheme for NAND and flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics，2015，61(4)：484-490.

[4] JIN X，JUNG S，SONG Y H.Write-aware buffer management policy for performance and durability enhancement in NAND flash memory[J].IEEE Transactions on Consumer Electronics，2010，56(4)：2393-2399.

[5] LEE S，JUNG S，SONG Y H.An efficient use of PRAM for an enhancement in the performance and durability of NAND storage systems[J].IEEE Transactions on Consumer Electronics，2012，58(3)：825-833.

[6] WU M.The architecture of eNVy，a non-volatile, main memory storage system[C].The Workshop on Workstation Operating Systems.IEEE，1994：116-118.

[7] KAWAGUCHI A，NISHIOKA S，MOTODA H.A flash-memory based file system[C].USENIX 1995 Technical Conference Proceedings.USENIX Association，1994：13-13.

[8] CHIANG M L，CHANG R C.Cleaning policies in mobile computers using flash memory[J].Journal of Systems & Software，1999，48(3)：213-231.

[9] Yan Hua，Yao Qian.An efficient file-aware garbage collection algorithm for NAND Flash-based consumer[J].IEEE Transactions on Consumer Electronics，2014，60(4)：623-627.

[10] 石樂健，嚴華.考慮物理塊年齡和邏輯頁熱度的NAND閃存磨損均衡算法[J].小型微型計算機系統，2015，36(11)：2618-2621.

[11] KWON O，KOH K，LEE J，et al.FeGC：an efficient garbage collection scheme for flash memory based storage systems[J].Journal of Systems & Software，2011，84(9)：1507-1523.

[12] HWANG S H，CHOI J H，KWAK J W.Migration cost sensitive garbage collection technique for non-volatile memory systems[J].IEICE Transactions on Information & Systems，2016，99(12)：3177-3180.

[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.

作者信息：

黃敏媛，嚴  華

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