混合映射方式下NAND閃存垃圾回收算法

張靖君，王 玲

(湖南師范大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410006)E-mail：417583212@qq.com

1 引 言

如今，NAND 閃存已廣泛應(yīng)用于各種嵌入式設(shè)備中[1]，例如手機(jī)、U盤(pán)、固態(tài)硬盤(pán)等.它具有體積小、速度快、功耗低、抗震等優(yōu)點(diǎn).與磁盤(pán)、軟盤(pán)這些磁介質(zhì)存儲(chǔ)器相比，NAND閃存具有以下特點(diǎn)：

1)NAND閃存的物理結(jié)構(gòu)主要分為物理塊和物理頁(yè)，整個(gè)閃存設(shè)備由多個(gè)物理塊組成，每一個(gè)物理塊又是由一定數(shù)目的物理頁(yè)組成.每一頁(yè)由兩部分組成分別是數(shù)據(jù)段(Data Field)和附加段(Spare Field)，數(shù)據(jù)段用于存儲(chǔ)數(shù)據(jù)，附加段用于保存閃存的管理數(shù)據(jù)，包括：ECC碼、映射表信息和壞塊信息[2].

2)NAND閃存讀寫(xiě)數(shù)據(jù)是以物理頁(yè)為單位，擦除操作則以物理塊為單位[3].讀取一個(gè)物理頁(yè)的速度較快，寫(xiě)入一頁(yè)數(shù)據(jù)的時(shí)間則較慢，而擦除一個(gè)物理塊的時(shí)間遠(yuǎn)遠(yuǎn)大于寫(xiě)的時(shí)間.

3)不能直接對(duì)物理塊保存的數(shù)據(jù)進(jìn)行修改，必須先進(jìn)行擦除操作才能寫(xiě)入新的數(shù)據(jù)[4].

4)物理塊的擦除次數(shù)有限SLC(Single-Level Cell 單層單元)通常在10萬(wàn)次左右，MLC(Multi-Level Cell多層單元)通常在1萬(wàn)次左右[5].

由于這些特性，傳統(tǒng)的文件系統(tǒng)無(wú)法在閃存設(shè)備上正常工作.為了將閃存設(shè)備模擬成標(biāo)準(zhǔn)的磁盤(pán)設(shè)備以兼容傳統(tǒng)的文件系統(tǒng)，通常使用閃存轉(zhuǎn)換層FTL (Flash Translation Layer)作為中間層管理閃存設(shè)備[6].FTL的主要功能包括：地址映射、垃圾回收、磨損均衡和壞塊管理[7].其中地址映射是FTL中最重要的一個(gè)功能，不同的地址映射方式必須要有與之相匹配的垃圾回收、磨損均衡算法，才能發(fā)揮其性能.

目前NAND 閃存的垃圾回收算法主要是針對(duì)頁(yè)級(jí)地址映射設(shè)計(jì)的，如GR(GReedy)算法[8]，GR算法為了減少有效頁(yè)拷貝造成的性能損失，會(huì)選擇有效頁(yè)最少的物理塊進(jìn)行垃圾回收.目標(biāo)是用最少的性能損失來(lái)獲得更多的空閑空間，但是，GR算法未考慮到各塊的擦除情況，因此磨損均衡度較差.CAT(Cost-Age-Time)算法[9]，考慮了擦除次數(shù)對(duì)均衡度的影響，選擇更新頻率最低、無(wú)效頁(yè)最多且擦除次數(shù)最少的物理塊進(jìn)行回收.由于考慮到了物理塊的更新頻率和擦除次數(shù)，所以磨損均衡效果優(yōu)于GR算法.SACATA (Swap-Aware Cost-Age-Time Age-sort)算法[10]在linux交換系統(tǒng)技術(shù)上考慮了所有塊的最大和最小擦除次數(shù)，因此磨損均衡度較好.以上三種算法在頁(yè)級(jí)地址映射上能夠取得較好的效果，但在混合映射上效果并不理想，造成這種結(jié)果的原因主要是物理塊之間關(guān)聯(lián)程度不同.頁(yè)級(jí)地址映射上物理塊之間都是獨(dú)立的，而混合映射上物理塊被分為數(shù)據(jù)塊和日志塊，數(shù)據(jù)塊和日志塊之間的數(shù)據(jù)存在關(guān)聯(lián).單獨(dú)考慮日志塊中有效頁(yè)數(shù)量在混合映射上并不能獲得最好的回收性能.FAST轉(zhuǎn)換層[11]是基于混合映射的轉(zhuǎn)換層，轉(zhuǎn)換層將日志塊共享給多個(gè)數(shù)據(jù)塊，提高了日志塊的利用率[12]，但冷熱數(shù)據(jù)混合在一個(gè)日志塊中，垃圾回收將頻繁觸發(fā)全合并這將會(huì)占用極大的資源[13].垃圾回收作為FTL一個(gè)重要部分，不僅要考慮閃存的壽命也要考慮其性能[14].

通過(guò)對(duì)基于混合映射的FAST算法的深入研究，針對(duì)其算法存在的不足，考慮邏輯塊的冷熱度、日志塊無(wú)效頁(yè)占比和數(shù)據(jù)塊的擦除次數(shù)，設(shè)計(jì)基于循壞隊(duì)列的邏輯塊熱度計(jì)算方法和數(shù)據(jù)塊選擇策略，并提出一種基于混合映射的垃圾回收算法即：HMSGC(Hybrid Mapping Scheme With Garbage Collection)算法.

2 算法描述

2.1 閃存設(shè)備基本結(jié)構(gòu)

在Linux系統(tǒng)下基于NAND 閃存存儲(chǔ)結(jié)構(gòu)可以分為：操作系統(tǒng)API、文件系統(tǒng)層、閃存轉(zhuǎn)換層和FLASH設(shè)備.系統(tǒng)結(jié)構(gòu)如圖1所示.

圖1 NAND FLASH 存儲(chǔ)系統(tǒng)結(jié)構(gòu)Fig.1 NAND FLASH storage system structure

操作系統(tǒng)層會(huì)提供給應(yīng)用程序讀寫(xiě)數(shù)據(jù)的程序接口，文件系統(tǒng)提供管理數(shù)據(jù)的方法.FTL(Flash Translation Layer)層是一種軟件中間層，它把NAND FLASH設(shè)備虛擬成傳統(tǒng)的硬盤(pán)設(shè)備，使得NTFS、EXT2等針對(duì)傳統(tǒng)硬盤(pán)設(shè)計(jì)的文件系統(tǒng)可以在不經(jīng)過(guò)修改的情況下正常使用[4].FTL層主要包含了壞塊管理、地址映射、磨損均衡、垃圾回收等幾個(gè)方面[5,6].

2.2 FAST算法垃圾回收方式

在基于混合映射的FAST算法中數(shù)據(jù)塊使用塊級(jí)映射而日志塊使用頁(yè)級(jí)映射，當(dāng)日志塊的空閑頁(yè)都被耗盡后，由于日志塊中還包含有效頁(yè)，所以并不能像頁(yè)級(jí)映射那樣，簡(jiǎn)單的把當(dāng)前的日志塊標(biāo)記為無(wú)效塊，之后再申請(qǐng)一個(gè)新的日志塊來(lái)接收數(shù)據(jù).此時(shí)我們必須進(jìn)行回收操作，把日志塊和數(shù)據(jù)塊的有效數(shù)據(jù)合并到一個(gè)新的數(shù)據(jù)塊中才能繼續(xù)申請(qǐng)新的日志塊并接收數(shù)據(jù).在FAST算法中存在三種合并方式：全合并、交換合并、部分合并[7].

全合并，當(dāng)數(shù)據(jù)塊和日志塊中的有效數(shù)據(jù)頁(yè)分布分散難以整理成有序的數(shù)據(jù)塊存儲(chǔ)使用，此時(shí)必須另外尋找一個(gè)新的物理塊，依次讀入日志塊和數(shù)據(jù)塊中的有效數(shù)據(jù)成為新的數(shù)據(jù)塊，并回收舊的數(shù)據(jù)塊和日志塊.這種合并方式要拷貝所有的有效數(shù)據(jù)，因此開(kāi)銷最大.

交換合并，當(dāng)只存在順序數(shù)據(jù)更新，數(shù)據(jù)塊中的數(shù)據(jù)全部順序更新到日志塊中，數(shù)據(jù)塊中無(wú)有效數(shù)據(jù)，此時(shí)只需要把日志塊轉(zhuǎn)換成數(shù)據(jù)塊，將數(shù)據(jù)塊擦除即可.

部分合并，當(dāng)只存在順序數(shù)據(jù)更新，數(shù)據(jù)塊中有部分?jǐn)?shù)更新到日志塊中.此時(shí)需要將數(shù)據(jù)塊中未被更新的有效數(shù)據(jù)順序拷貝到日志塊中，再把日志塊轉(zhuǎn)換成數(shù)據(jù)塊即可.

2.3 基于循環(huán)隊(duì)列的熱塊識(shí)別算法

CAT算法中冷熱塊的識(shí)別主要集中在數(shù)據(jù)的寫(xiě)訪問(wèn)次數(shù)方面[8]，當(dāng)通過(guò)長(zhǎng)時(shí)間的積累使地址A被訪問(wèn)到了100次和在短時(shí)間內(nèi)地址B被訪問(wèn)到了100次，此時(shí)根據(jù)CAT的計(jì)算公式A、B將計(jì)算出同樣的熱度值.但由于B是在短時(shí)間的頻繁訪問(wèn)，地址B的熱度值應(yīng)該更高.

為了有效的反應(yīng)邏輯地址的被訪問(wèn)的次數(shù)隨著時(shí)間的變化關(guān)系，可以在閃存設(shè)備接收到寫(xiě)命令時(shí)使用循環(huán)隊(duì)列統(tǒng)計(jì)該塊地址的熱度值，并利用隊(duì)列的先入先出特性刪除過(guò)時(shí)的數(shù)據(jù).具體方法如下：

建立固定長(zhǎng)度的循環(huán)隊(duì)列，長(zhǎng)度為len，從隊(duì)頭到隊(duì)尾為每一個(gè)位置分配一個(gè)遞增的熱度權(quán)值，當(dāng)一個(gè)寫(xiě)命令來(lái)時(shí)，將LBA入隊(duì)，此時(shí)LBA的熱度為len，原隊(duì)列各元素向隊(duì)頭移動(dòng)一個(gè)位置，對(duì)頭元素出列.由于是循環(huán)隊(duì)列，元素入隊(duì)、出隊(duì)、移位只需要修改隊(duì)頭和隊(duì)尾指針，提高了運(yùn)算速度.隊(duì)列狀態(tài)如圖2所示.

圖2 熱度循環(huán)隊(duì)列狀態(tài)圖Fig.2 Heat queue state diagram

當(dāng)計(jì)算某個(gè)邏輯塊地址的熱度值Hoti時(shí)，通過(guò)對(duì)隊(duì)列中該地址的熱度權(quán)值求和，便得到該邏輯塊地址的熱度值.

2.4 磨損均衡策略

在混合映射中日志塊采用的是頁(yè)級(jí)映射方式，一個(gè)日志塊可以接收多個(gè)數(shù)據(jù)塊的更新數(shù)據(jù).當(dāng)冷熱數(shù)據(jù)混合在一個(gè)日志塊的時(shí)候，由于熱數(shù)據(jù)頻繁的更新，日志塊中的空閑頁(yè)很快就被耗盡，合并操作會(huì)同時(shí)拷貝熱數(shù)據(jù)和冷數(shù)據(jù).為了避免冷數(shù)據(jù)和熱數(shù)據(jù)混合在一塊日志塊導(dǎo)致冷數(shù)據(jù)過(guò)多沒(méi)必要的拷貝，需要根據(jù)數(shù)據(jù)的冷熱值將相似熱度的有效頁(yè)分配在同一日志塊上，以達(dá)到減少塊合并操作的目的.

本文采用一種基于邏輯塊熱度的冷熱分離，通過(guò)有效頁(yè)所對(duì)應(yīng)的邏輯塊熱度來(lái)決定寫(xiě)入的日志頁(yè)的狀態(tài).具體步驟如下：

1) 設(shè)定冷熱塊的閾值HotTh，通過(guò)累加循環(huán)隊(duì)列中目標(biāo)邏輯塊的權(quán)值，計(jì)算出當(dāng)前邏輯塊的熱度值.

2)若寫(xiě)入數(shù)據(jù)對(duì)應(yīng)邏輯塊的熱度≥HotTh，該數(shù)據(jù)寫(xiě)入的邏輯塊被定義為熱塊，這時(shí)將分配空閑塊中擦寫(xiě)次數(shù)最小的兩個(gè)物理塊作為其數(shù)據(jù)塊和日志塊，此時(shí)該日志塊不共享給其他數(shù)據(jù)塊.

3)若寫(xiě)入數(shù)據(jù)對(duì)應(yīng)邏輯塊的熱度< HotTh，該數(shù)據(jù)對(duì)應(yīng)邏輯塊被定義為冷塊，這時(shí)將分配空閑塊中擦寫(xiě)次數(shù)最大的兩個(gè)物理塊作為其數(shù)據(jù)塊和日志塊，此時(shí)該日志塊共享給其他數(shù)據(jù)塊.

2.5 回收塊的選擇

系統(tǒng)在進(jìn)行垃圾回收時(shí)，首先需要考慮垃圾回收的效率，應(yīng)盡量選擇能夠交換合并和部分合并的數(shù)據(jù)塊進(jìn)行回收避免性能最差的全合并[9,10].由于NAND 閃存設(shè)備擦除次數(shù)有限，無(wú)效頁(yè)回收還要考慮閃存塊的磨損均衡度和資源的合理利用.所以回收策略結(jié)合了擦除次數(shù)、有效頁(yè)比例和熱度值.具體公式如公式(1)所示：

(1)

其中：v表示順序日志塊中有效頁(yè)比例；εmin表示FLASH設(shè)備中塊的最小擦除次數(shù)；εmax表示FLASH設(shè)備中塊的最大擦除次數(shù)；εi表示該物理塊被擦除的次數(shù)；HotTh表示判定冷熱塊的閾值；Hoti表示該塊的熱度值.對(duì)于混合映射來(lái)說(shuō)由于垃圾回收必然會(huì)執(zhí)行數(shù)據(jù)塊合并操作，當(dāng)順序日志塊上有效頁(yè)越多執(zhí)行部分合并時(shí)效率就越高，同時(shí)冷熱程度也作為資源合理利用的依據(jù)，冷數(shù)據(jù)塊所對(duì)應(yīng)的日志塊會(huì)被長(zhǎng)期占用，由于冷數(shù)據(jù)塊可能在接下來(lái)很長(zhǎng)一段時(shí)間無(wú)數(shù)據(jù)寫(xiě)入，因此也無(wú)法通過(guò)數(shù)據(jù)寫(xiě)滿日志塊觸發(fā)合并回收日志塊，此時(shí)日志塊將被一直無(wú)法被其他塊使用，這對(duì)空間的利用和磨損均衡都是不利的[10]，所以應(yīng)該優(yōu)先回收冷數(shù)據(jù)塊的日志塊.回收機(jī)制會(huì)選擇數(shù)據(jù)塊的順序日志塊有效頁(yè)最多、擦除次數(shù)最少且熱度值最低的數(shù)據(jù)塊進(jìn)行回收.

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)參數(shù)

在linux 2.6下使用disksim磁盤(pán)仿真平臺(tái)模擬NAND閃存.測(cè)試數(shù)據(jù)使用同等大小的RAM虛擬磁盤(pán)設(shè)備在實(shí)際運(yùn)行下的讀寫(xiě)記錄生成tarce文件.通過(guò)在disksim中添加測(cè)試算法并使用生成的tarce測(cè)試數(shù)據(jù)進(jìn)行測(cè)試獲得性能數(shù)據(jù).其中RAM虛擬磁盤(pán)格式化為FAT32文件系統(tǒng)，在文件系統(tǒng)中創(chuàng)建1KB～2MB文件，所有文件大小總和占RAM虛擬磁盤(pán)設(shè)備85%.文件創(chuàng)建完后對(duì)文件進(jìn)行更新.測(cè)試數(shù)據(jù)通過(guò)記錄系統(tǒng)對(duì)虛擬磁盤(pán)的I/O生成可用于Flashsim 的trace測(cè)試數(shù)據(jù)[11-13].模擬出來(lái)的NAND 閃存和RAM磁盤(pán)大小都為64M，NAND 閃存頁(yè)大小為8KB，塊大小為1MB，總?cè)萘繛?4MB.實(shí)驗(yàn)與同樣使用混合映射的CAT、SACATA算法進(jìn)行性能比較.HMSGC算法中參數(shù)HotTh設(shè)為128，熱度鏈表長(zhǎng)度為128.

3.2 算法性能比較

論文在FAST轉(zhuǎn)換層的基礎(chǔ)上實(shí)現(xiàn)了CAT、SACATA、HMSGC三種垃圾回收算法并進(jìn)行了實(shí)驗(yàn)比較.性能比較采用的指標(biāo)包括：所有物理塊的擦除總數(shù)、全合并總數(shù)、擦除次數(shù)的標(biāo)準(zhǔn)差曲線、擦除次數(shù)最大差值比和響應(yīng)時(shí)間.

由圖3、圖4可知，隨寫(xiě)入數(shù)據(jù)的增加，使用HMSGC算法的總擦除次數(shù)始終比CAT、SACATA算法少50%以上，全合并次數(shù)要少84%.這主要是因?yàn)镠MSGC對(duì)冷熱數(shù)據(jù)塊進(jìn)行了識(shí)別，并且將冷熱塊的更新數(shù)據(jù)分開(kāi)存儲(chǔ)到不同擦除次數(shù)的日志塊中，減少了垃圾回收觸發(fā)頻率以及全合并次數(shù).

圖3 擦除總次數(shù)對(duì)比圖Fig.3 Totalnumberoferaseoperation圖4 全合并次數(shù)對(duì)比圖Fig.4 Totalnumberofmergers

由圖5可知，HMSGC算法的塊最大擦除次數(shù)和最小擦除次數(shù)差值要比CAT和SACATA算法少70%.這是因?yàn)榛厥沾鷥r(jià)函數(shù)中引入了塊的熱度值，回收了更新數(shù)據(jù)較慢的冷數(shù)據(jù)塊，改善了磨損均衡度，提高了塊空間了利用.

圖5 擦除次數(shù)最大差值對(duì)比Fig.5 Maximumdifferentoferasecycles圖6 擦除次數(shù)的標(biāo)準(zhǔn)差對(duì)比Fig.6 Standdeviationofblockerasecycles

由圖6可知，隨著擦除次數(shù)的增加，CAT和SACATA算法的標(biāo)準(zhǔn)差逐漸增加且增速變快，而HMSGC算法的標(biāo)準(zhǔn)差雖然隨著擦除次數(shù)的增加也在增加，但其增速卻比CAT和SACATA算法要慢，并且標(biāo)準(zhǔn)差更趨近于穩(wěn)定.這是由于HMSGC算法選擇合適的物理塊進(jìn)行回收，同時(shí)以邏輯塊的熱度對(duì)日志塊數(shù)據(jù)進(jìn)行冷熱分離.把擦除次數(shù)最少的物理塊作為熱邏輯塊的數(shù)據(jù)塊和日志塊，把擦除次數(shù)最多的物理塊作為冷邏輯塊的數(shù)據(jù)塊和日志塊.這種策略有助于平衡各物理塊的擦除次數(shù)，從而改善了塊的磨損均衡度.

表1 算法讀寫(xiě)性能Table 1 Algorithm read and write performance

由表1可知，I/O的平均響應(yīng)時(shí)間和最大響應(yīng)時(shí)間HMSGC算法要明顯小于SACATA和CAT算法.這是由于HMSGC算法使用冷熱數(shù)據(jù)分離大量減少了全合并的次數(shù)，同時(shí)為熱數(shù)據(jù)塊分配單獨(dú)的日志塊避免熱數(shù)據(jù)塊頻繁觸發(fā)合并操作，縮短了響應(yīng)時(shí)間.

4 結(jié) 語(yǔ)

針對(duì)NAND閃存的硬件特性，改進(jìn)FAST轉(zhuǎn)換層提出了一種基于混合映射的垃圾回收算法.首先，提出一種基于循環(huán)隊(duì)列的熱塊識(shí)別算法計(jì)算邏輯塊熱度，其次選擇對(duì)應(yīng)順序日志塊有效頁(yè)最多、擦除次數(shù)最少且熱度值最低的數(shù)據(jù)塊進(jìn)行回收.最后將熱數(shù)據(jù)存入擦除次數(shù)最少的數(shù)據(jù)塊或日志塊中，冷數(shù)據(jù)存入擦除次數(shù)最大的數(shù)據(jù)塊或日志塊中.實(shí)現(xiàn)在日志塊中冷熱數(shù)據(jù)的分開(kāi)存儲(chǔ).實(shí)驗(yàn)結(jié)果表明，與CAT和SACATA算法比較，磨損均衡度方面取得了較好的性能，同時(shí)全合并觸發(fā)次數(shù)和擦除總次數(shù)減少了50%以上.在I/O性能上也有較大的提升.該算法能夠延長(zhǎng)NAND 閃存的壽命，并優(yōu)化其性能.