0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 算法描述

1.1 算法原理

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

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

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

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

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

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

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

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

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

1.2 回收塊選擇策略

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

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

    同時(shí),，算法采用一種自適應(yīng)策略對(duì)最冷塊進(jìn)行回收。自適應(yīng)最冷塊回收策略啟動(dò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)一個(gè)塊的擦除次數(shù)超過T_erase值時(shí),，最冷塊回收策略被調(diào)用,。該策略將選擇有最小擦除次數(shù)的塊作為回收塊，以增加選中有較低更新頻率的邏輯頁(yè)的塊的幾率,。如果有多個(gè)塊具有最小擦除次數(shù)，則選擇其中含有最少有效頁(yè)的塊作為回收塊,。在每次冷塊回收策略被調(diào)用時(shí),，T_erase值會(huì)被計(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)邏輯頁(yè)兩次更新操作的時(shí)間差值大于特定值時(shí)，邏輯頁(yè)熱度被強(qiáng)制歸零,，因此不能細(xì)分部分?jǐn)?shù)據(jù)的冷熱程度,。此外，GCbAH也采用預(yù)先設(shè)置的特定閾值作為判斷冷熱數(shù)據(jù)的標(biāo)準(zhǔn),。

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

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

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

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

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

1.4 算法步驟

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

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

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

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

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

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

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

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

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

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

2.2 算法性能分析

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

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

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

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

3 結(jié)論

    針對(duì)NAND閃存的特點(diǎn),，提出一種基于邏輯頁(yè)平均更新頻率的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:一種閃存上的塊頁(yè)混合緩存管理方法[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)華.考慮物理塊年齡和邏輯頁(yè)熱度的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)