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

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

0 概述

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

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

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

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

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

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

1.1 分散度判斷

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

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

算法1分散度判斷算法

1.2 回收塊選擇

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

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

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

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

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

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

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

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

算法2回收塊選擇算法

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

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

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

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

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

表1 有效頁(yè)類型劃分Table 1 Type division of valid pages

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

表2 實(shí)驗(yàn)參數(shù)Table 2 Experimental parameters

2.2 結(jié)果分析

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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