0 引言

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

    NAND閃存具有如下特點(diǎn)：

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

    (2)NAND閃存具有“寫前擦除”的特點(diǎn)，即在進(jìn)行重復(fù)寫操作之前，必須先對寫入的存儲區(qū)進(jìn)行擦除操作。

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

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

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

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

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

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

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

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

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

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

1 算法描述

1.1 算法原理

    NAND閃存進(jìn)行垃圾回收時有如下操作：

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

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

    (3)將被拷貝的有效數(shù)據(jù)所對應(yīng)的原數(shù)據(jù)頁標(biāo)記為無效頁；

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

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

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

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

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

1.2 回收塊選擇策略

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

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

    同時，算法采用一種自適應(yīng)策略對最冷塊進(jìn)行回收。自適應(yīng)最冷塊回收策略啟動條件如下：

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

1.3 數(shù)據(jù)熱度定義

    在熱度判定上，F(xiàn)aGC以更新頻率作為判定數(shù)據(jù)熱度的標(biāo)準(zhǔn)，大于預(yù)先設(shè)置的特定閾值則為熱數(shù)據(jù)，反之則為冷數(shù)據(jù)。

    GCbAH通過上一次判定的熱度與熱度調(diào)節(jié)因子相乘作為本次熱度的計(jì)算標(biāo)準(zhǔn)。當(dāng)邏輯頁兩次更新操作的時間差值大于特定值時，邏輯頁熱度被強(qiáng)制歸零，因此不能細(xì)分部分?jǐn)?shù)據(jù)的冷熱程度。此外，GCbAH也采用預(yù)先設(shè)置的特定閾值作為判斷冷熱數(shù)據(jù)的標(biāo)準(zhǔn)。

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

其中，CurrentT是當(dāng)前時間，IWT_i是該邏輯頁i的初始寫入時間。UPDC_i是邏輯頁i的更新次數(shù)。因此，F(xiàn)REQ_i代表邏輯頁i寫操作的更新間隔。

    衡量冷熱數(shù)據(jù)的標(biāo)準(zhǔn)如下：

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

    當(dāng)邏輯頁的更新頻率FREQ_i小于平均更新頻率AverF_i，則該邏輯頁包含的數(shù)據(jù)是為熱數(shù)據(jù)；當(dāng)邏輯頁更新頻率時間FREQ_i大于平均更新頻率時間AverF_i，則為冷數(shù)據(jù)。

1.4 算法步驟

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

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

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

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

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

2 實(shí)驗(yàn)及分析

2.1 實(shí)驗(yàn)環(huán)境

    實(shí)驗(yàn)中使用VMware和Ubuntu 12.04平臺，使用QEMU搭建嵌入式Linux仿真環(huán)境，使用NANDSim來模擬NAND閃存，基于NAND閃存專用文件系統(tǒng)YAFFS2進(jìn)行測試。

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

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

2.2 算法性能分析

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)

[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] 白石，廖學(xué)良，胡事民.HFB:一種閃存上的塊頁混合緩存管理方法[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，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] 石樂健，嚴(yán)華.考慮物理塊年齡和邏輯頁熱度的NAND閃存磨損均衡算法[J].小型微型計(jì)算機(jī)系統(tǒng)，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.

作者信息：

黃敏媛，嚴(yán)  華

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