方才華，劉景寧，童 薇，高 陽(yáng)，雷 霞，蔣 瑜

(1.武漢光電國(guó)家實(shí)驗(yàn)室(華中科技大學(xué)), 武漢 430074; 2.信息存儲(chǔ)系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室(華中科技大學(xué)), 武漢 430074)

全程優(yōu)化的固態(tài)硬盤(pán)垃圾回收方法

方才華1,2，劉景寧1,2，童 薇1,2*，高 陽(yáng)1,2，雷 霞1,2，蔣 瑜1,2

(1.武漢光電國(guó)家實(shí)驗(yàn)室(華中科技大學(xué)), 武漢 430074; 2.信息存儲(chǔ)系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室(華中科技大學(xué)), 武漢 430074)

(*通信作者電子郵箱Tongwei@hust.edu.cn)

由于NAND閃存的固有限制，寫(xiě)前擦除和擦除粒度較大，基于NAND Flash的固態(tài)硬盤(pán)(SSD)需要執(zhí)行垃圾回收以重用失效頁(yè)。然而垃圾回收帶來(lái)的高開(kāi)銷(xiāo)會(huì)顯著降低SSD的性能，也會(huì)直接影響SSD的壽命。特別是對(duì)于頻繁使用的有數(shù)據(jù)碎片的SSD，垃圾回收帶來(lái)的性能下降問(wèn)題將更為嚴(yán)重，現(xiàn)有的垃圾回收(GC)算法各自側(cè)重垃圾回收操作的某個(gè)步驟，并沒(méi)有給出全面考慮各步驟對(duì)整體影響的綜合方案。針對(duì)該問(wèn)題，在詳細(xì)剖析垃圾回收過(guò)程的基礎(chǔ)上，提出了一種全程優(yōu)化的垃圾回收方法WPO-GC，在數(shù)據(jù)初始放置、垃圾回收目標(biāo)塊的選擇、有效數(shù)據(jù)的遷移、觸發(fā)回收的時(shí)間點(diǎn)以及中斷處理方式上，盡可能全面地考慮各步驟對(duì)SSD正常讀寫(xiě)請(qǐng)求和壽命的影響。通過(guò)開(kāi)源模擬器SSDsim上的WPO-GC的有效性驗(yàn)證表明，同典型GC算法相比，WPO-GC可以減少SSD讀請(qǐng)求延遲20%～40%和寫(xiě)請(qǐng)求延遲17%～40%，均衡磨損近30%。

閃存；固態(tài)盤(pán)；垃圾回收；磨損均衡；使用壽命

0 引言

近年來(lái)，基于NAND Flash的固態(tài)硬盤(pán)(Solid-State Drive, SSD)因其性能高、功耗低、抗震性好等諸多優(yōu)點(diǎn)獲得廣泛的應(yīng)用。由于NAND閃存異地更新的特點(diǎn)，寫(xiě)更新產(chǎn)生的無(wú)效頁(yè)需經(jīng)由垃圾回收操作才能重新成為可用頁(yè)。SSD的垃圾回收操作涉及到目標(biāo)塊的選擇、有效數(shù)據(jù)的遷移和塊的擦除操作[1-3]，因而對(duì)SSD的讀寫(xiě)性能和壽命都有很大的影響。

根據(jù)采用fio[4]對(duì)Intel SSD DC P3700固態(tài)盤(pán)的測(cè)試結(jié)果，當(dāng)執(zhí)行讀寫(xiě)請(qǐng)求大小為4 KB、讀寫(xiě)請(qǐng)求比例為 7∶3的隨機(jī)I/O時(shí)，若SSD是空盤(pán)，其每秒進(jìn)行讀寫(xiě)操作的次數(shù)(Input/Output Operations Per Second, IOPS)能達(dá)到20萬(wàn)次，讀、寫(xiě)延遲分別為180 μs和2 000 μs；但對(duì)SSD進(jìn)行數(shù)據(jù)預(yù)埋和碎片化處理后再進(jìn)行相同的測(cè)試，其IOPS下降到6萬(wàn)次/s，讀寫(xiě)延遲上升了3～7倍, 造成這種性能差距的直接原因是SSD內(nèi)部的垃圾回收(Garbage Collection, GC)操作。當(dāng)SSD中用于容納異地更新的預(yù)留空間越來(lái)越少，就會(huì)頻繁地觸發(fā)垃圾回收，導(dǎo)致正常的讀寫(xiě)訪問(wèn)被阻塞。由于垃圾回收需通過(guò)塊擦除獲得可用頁(yè)，因此垃圾回收操作的執(zhí)行頻率也會(huì)對(duì)SSD的壽命造成影響。

全程優(yōu)化的垃圾回收方法(Whole Process Optimized Garbage Collection, WPO-GC)，從數(shù)據(jù)初始放置、垃圾回收目標(biāo)塊的選擇、有效數(shù)據(jù)的遷移位置、觸發(fā)回收的時(shí)間點(diǎn)以及中斷處理方式上，全面優(yōu)化與垃圾回收方面相關(guān)的各個(gè)步驟，有效減少了SSD正常讀寫(xiě)的響應(yīng)延遲，同時(shí)提升了SSD的壽命。

1 背景與動(dòng)機(jī)

1.1 SSD的架構(gòu)

SSD主要由SSD控制器和閃存芯片構(gòu)成, 如圖1所示。SSD中的閃存控制器控制多個(gè)通道(Channel)，每個(gè)通道上掛載多顆閃存芯片(Chip)[5-6]。如圖2所示，閃存芯片由多個(gè)晶圓(Die)組成，每個(gè)晶圓又由多個(gè)分組(Plane)組成，每個(gè)分組包含多個(gè)塊(Block)。塊是芯片擦除的基本單位，每個(gè)塊包含多個(gè)頁(yè)(Page)，頁(yè)是芯片讀寫(xiě)的基本單位。

圖1 SSD的整體架構(gòu)Fig. 1 Overall architecture of SSD

圖2 閃存芯片的架構(gòu)Fig. 2 Architecture of flash chip

1.2 垃圾回收的機(jī)制

閃存芯片具有寫(xiě)前擦除的特性，更新數(shù)據(jù)時(shí)要采用異地更新方式(舊數(shù)據(jù)成為無(wú)效頁(yè))[7]。為保證SSD的正常使用，需要對(duì)無(wú)效頁(yè)進(jìn)行垃圾回收操作，即擦除選定的目標(biāo)塊以供用戶(hù)再次使用。由于閃存芯片的讀寫(xiě)粒度(頁(yè)單位)和擦除粒度(塊單位)不同，在擦除一個(gè)目標(biāo)塊之前，垃圾回收首先需要遷移其有效數(shù)據(jù)頁(yè)到其他塊中。如圖3所示，一次完整的垃圾回收操作包括3個(gè)步驟：①選擇要回收的目標(biāo)塊；②遷移有效數(shù)據(jù)到其他塊中；③擦除目標(biāo)塊。在數(shù)據(jù)遷移時(shí)，數(shù)據(jù)的源物理頁(yè)和目的物理頁(yè)所處的芯片和通道均會(huì)被占用，在隨后執(zhí)行塊擦除操作時(shí)，雖然不會(huì)占用通道資源，但被擦除塊所處的芯片也會(huì)被占用。因此在SSD內(nèi)部執(zhí)行垃圾回收操作過(guò)程中，上層向SSD發(fā)出的讀寫(xiě)請(qǐng)求若要訪問(wèn)垃圾回收占用的芯片或者通道資源[3, 8]，其響應(yīng)時(shí)間和吞吐率都會(huì)受到較大影響。另外由于閃存芯片擦除次數(shù)有限的特性，垃圾回收的執(zhí)行頻率會(huì)直接影響SSD的壽命。

在設(shè)計(jì)垃圾回收算法時(shí)通常需要考慮如下幾個(gè)問(wèn)題： 1)何時(shí)觸發(fā)垃圾回收操作？2) 如何選擇目標(biāo)塊？3)怎樣安置和遷移數(shù)據(jù)？

圖3 垃圾回收操作的示意圖Fig. 3 Schematic diagram of garbage collection operation

1.3 相關(guān)工作

針對(duì)上述問(wèn)題，現(xiàn)有垃圾回收算法提出不同的解決方法。

對(duì)于何時(shí)觸發(fā)垃圾回收操作，文獻(xiàn)[9]設(shè)置了一個(gè)表示SSD空閑頁(yè)比例的固定閾值，當(dāng)空閑頁(yè)比例小于該閾值時(shí)，觸發(fā)垃圾回收。這種方法的缺點(diǎn)在于：當(dāng)垃圾回收被觸發(fā)時(shí)，系統(tǒng)中的空閑頁(yè)比例已經(jīng)很低，此時(shí)容易造成垃圾回收的頻繁執(zhí)行。為避免垃圾回收的頻繁觸發(fā)，文獻(xiàn)[10]在SSD空閑時(shí)根據(jù)SSD當(dāng)前的多個(gè)狀態(tài)和統(tǒng)計(jì)值，如塊擦除次數(shù)、頁(yè)的狀態(tài)等，確認(rèn)是否觸發(fā)垃圾回收操作。該方法能夠讓垃圾回收操作避開(kāi)正常讀寫(xiě)請(qǐng)求，最小化垃圾回收對(duì)SSD性能的影響；其缺點(diǎn)在于：針對(duì)讀寫(xiě)訪問(wèn)密集的應(yīng)用，垃圾回收操作始終不能有效進(jìn)行，此外對(duì)SSD空閑時(shí)間的準(zhǔn)確預(yù)測(cè)也很難實(shí)現(xiàn)。文獻(xiàn)[11]提出的GC算法允許用戶(hù)I/O請(qǐng)求中斷正在執(zhí)行的GC操作，待用戶(hù)I/O請(qǐng)求完成后再恢復(fù)執(zhí)行被中斷的GC進(jìn)程，但是針對(duì)I/O密集型應(yīng)用，垃圾回收操作可能會(huì)被連續(xù)的I/O請(qǐng)求多次中斷，難以及時(shí)有效回收SSD空間。為避免垃圾回收的頻繁觸發(fā)，文獻(xiàn)[12]設(shè)計(jì)了一個(gè)兩級(jí)閾值的方式，既能充分利用SSD的空閑時(shí)間進(jìn)行垃圾回收，從而避免后期垃圾回收的頻繁觸發(fā)，針對(duì)密集型應(yīng)用，又能設(shè)計(jì)強(qiáng)制GC保證SSD的空閑空間。

對(duì)于如何選擇垃圾回收的目標(biāo)物理塊。貪婪算法選取該垃圾回收請(qǐng)求對(duì)應(yīng)Plane中無(wú)效頁(yè)最多的塊作為回收塊。該算法優(yōu)點(diǎn)是能夠最大限度地減少數(shù)據(jù)遷移量，提高垃圾回收的效率；缺點(diǎn)是沒(méi)有考慮回收塊的擦除次數(shù)，容易導(dǎo)致塊被過(guò)早地擦穿，縮短固態(tài)盤(pán)的使用壽命。另一方面，基于損耗均衡的GC算法選擇最少磨損的塊作為回收塊[13]，但會(huì)增加GC遷移數(shù)據(jù)的開(kāi)銷(xiāo)。在GC過(guò)程中同時(shí)考慮回收塊的無(wú)效頁(yè)比例和擦除次數(shù)常常是一對(duì)矛盾，為達(dá)到二者的平衡，文獻(xiàn)[14]利用塊的有效頁(yè)比例和擦除次數(shù)計(jì)算加權(quán)分，來(lái)選擇合適的回收塊。但是其回收塊選擇機(jī)制是基于特定的Flash文件系統(tǒng)(Flash File System, FFS)，不具有普遍性。WECO(WEar COnscious)[15]在文獻(xiàn)[14]評(píng)分機(jī)制的基礎(chǔ)上，對(duì)評(píng)分公式作了優(yōu)化并將其擴(kuò)展到塊設(shè)備，但是對(duì)有大量空閑頁(yè)的塊，其評(píng)分機(jī)制不準(zhǔn)確，會(huì)導(dǎo)致有較多空閑頁(yè)和無(wú)效頁(yè)的塊被選中回收，這樣造成了低下的回收效率。

有效數(shù)據(jù)遷移的關(guān)鍵在于確定數(shù)據(jù)遷移安放的位置，一個(gè)好的GC算法應(yīng)通過(guò)分析遷移數(shù)據(jù)的溫度等特點(diǎn)，重新規(guī)劃遷移數(shù)據(jù)的安放，使相近溫度的數(shù)據(jù)聚集到一塊中，提高垃圾回收的效率。WECO提出一種數(shù)據(jù)分離策略，在數(shù)據(jù)遷移過(guò)程中，能夠分離冷熱數(shù)據(jù)。該方法優(yōu)點(diǎn)是提高垃圾回收的效率和保護(hù)磨損嚴(yán)重的塊，以增加使用壽命；其不足之處在于冷熱數(shù)據(jù)分離的算法復(fù)雜，開(kāi)銷(xiāo)較大。

文獻(xiàn)[16]提出緩存感知的垃圾回收算法，當(dāng)緩存進(jìn)行替換往下寫(xiě)時(shí)，考慮下層通道是否進(jìn)行垃圾回收操作，避免對(duì)正在進(jìn)行的通道進(jìn)行分發(fā)請(qǐng)求，以此減少響應(yīng)等待時(shí)延, 但這不能從根本上減少垃圾回收帶來(lái)的影響。

1.4 動(dòng)機(jī)

現(xiàn)有的GC算法[9-15]，都不能很好地解決垃圾回收對(duì)正常讀寫(xiě)請(qǐng)求的影響，都是針對(duì)垃圾回收的某一個(gè)步驟中的問(wèn)題作優(yōu)化，例如只針對(duì)垃圾回收的觸發(fā)條件[9-12]或者回收目標(biāo)塊的選擇[13-15]，缺乏對(duì)GC的整體優(yōu)化改進(jìn)，更沒(méi)有針對(duì)數(shù)據(jù)的訪問(wèn)頻率(溫度)特點(diǎn)，防患于未然，在數(shù)據(jù)放置和遷移時(shí)就提前考慮如何減少垃圾回收帶來(lái)的影響問(wèn)題。

為了更進(jìn)一步地減少GC對(duì)用戶(hù)正常讀寫(xiě)請(qǐng)求響應(yīng)延時(shí)的影響，更好地提升SSD的性能和壽命，針對(duì)現(xiàn)有GC算法的缺陷，深入分析GC的每一步操作，探討其優(yōu)化策略，從而達(dá)到全過(guò)程的優(yōu)化，提出一種全面的WPO-GC策略。WPO-GC主要工作是在其他研究者的工作上進(jìn)行優(yōu)化，包括以下4點(diǎn)：

1)分離放置冷熱數(shù)據(jù)。依據(jù)數(shù)據(jù)訪問(wèn)頻度，確認(rèn)數(shù)據(jù)冷熱溫度，在數(shù)據(jù)放置時(shí)就考慮數(shù)據(jù)的特點(diǎn)，使溫度相近的數(shù)據(jù)聚集一起，便于達(dá)到全盤(pán)整體均衡，提高垃圾回收的效率。

2)建立兩級(jí)閾值引入一種可中斷GC策略，依據(jù)SSD當(dāng)前的工作狀態(tài)，控制垃圾回收的觸發(fā)條件，采用不同的中斷方式處理，進(jìn)一步減少GC對(duì)SSD讀寫(xiě)性能的影響。其中提出中斷開(kāi)放策略，即垃圾回收中的每次有效頁(yè)遷移結(jié)束后開(kāi)放系統(tǒng)中斷，既可以利用不同請(qǐng)求到來(lái)的時(shí)間間隔進(jìn)行垃圾回收，又可以及時(shí)響應(yīng)用戶(hù)請(qǐng)求，減少用戶(hù)讀寫(xiě)操作的等待延時(shí)，提高系統(tǒng)的平均響應(yīng)時(shí)間。

3)選擇適當(dāng)?shù)睦厥漳繕?biāo)塊。采用綜合考慮塊中無(wú)效頁(yè)所占比例和擦除次數(shù)的均衡策略， 提高垃圾回收的效率，延長(zhǎng)閃存壽命。

4)在數(shù)據(jù)遷移時(shí)，進(jìn)一步依據(jù)數(shù)據(jù)冷熱程度選擇數(shù)據(jù)的放置位置，減少垃圾回收中不必要的反復(fù)遷移。

2 設(shè)計(jì)和實(shí)現(xiàn)

WPO-GC主要目標(biāo)是減少GC對(duì)用戶(hù)正常讀寫(xiě)延時(shí)的影響，其設(shè)計(jì)思路是全面考慮與GC相關(guān)的各個(gè)方面，并對(duì)GC每一步驟進(jìn)行全局優(yōu)化，以兼顧SSD性能和壽命的提升。WPO-GC主要包括以下部分：1)產(chǎn)生不同優(yōu)先級(jí)的垃圾回收請(qǐng)求; 2)控制垃圾回收的觸發(fā)條件，允許中斷開(kāi)放策略; 3)平衡性能和壽命的目標(biāo)塊選擇; 4)通過(guò)冷熱數(shù)據(jù)分離提高垃圾回收效率。

2.1 產(chǎn)生垃圾回收請(qǐng)求

目前關(guān)于垃圾回收請(qǐng)求響應(yīng)時(shí)機(jī)，有不同的研究：文獻(xiàn)[9]通過(guò)設(shè)置較低的空閑空間閾值來(lái)作為觸發(fā)條件，但這會(huì)導(dǎo)致使用后期垃圾回收的頻繁觸發(fā)，嚴(yán)重影響性能; 文獻(xiàn)[10]采用在SSD空閑時(shí)間進(jìn)行垃圾回收，但是無(wú)法準(zhǔn)確預(yù)測(cè)空閑時(shí)間; 文獻(xiàn)[11]提出可被I/O請(qǐng)求中斷的GC算法，但是這會(huì)導(dǎo)致垃圾回收操作被連續(xù)到來(lái)的I/O請(qǐng)求多次中斷，難以有效回收SSD空間。

WPO-GC根據(jù)SSD空閑空間的多少，設(shè)置兩級(jí)閾值，賦予垃圾回收操作不同的緊迫程度，采用文獻(xiàn)[12]提出的方法和公式，分別是不可中斷閾值H和可中斷閾值T，用于區(qū)分垃圾回收操作的緊迫級(jí)別。當(dāng)Plane的空閑空間比例FP低于不可中斷閾值H時(shí)，需立刻執(zhí)行垃圾回收，因而產(chǎn)生不可中斷垃圾回收請(qǐng)求; 當(dāng)FP的值在不可中斷閾值H和可中斷閾值T之間時(shí)，產(chǎn)生可中斷垃圾回收請(qǐng)求，當(dāng)FP高于T時(shí)不產(chǎn)生垃圾回收請(qǐng)求?；诠虘B(tài)盤(pán)中每個(gè)Plane的狀態(tài)(空閑頁(yè)數(shù)、無(wú)效頁(yè)數(shù)、有效頁(yè)數(shù))，采用式(1)和(2)動(dòng)態(tài)計(jì)算得出H和T的值。

H=aE+B(1-Vp)

(1)

T=AE+B(1-Vp)+cIp

(2)

其中：E表示SSD預(yù)留空間比例，由SSD廠商設(shè)定;Vp是有效頁(yè)比例;Ip是無(wú)效頁(yè)比例;a、b、c、A、B均為權(quán)值系數(shù)，滿(mǎn)足具體取值為：a取0.3～0.5，b取0.1～0.3，A取0.5～0.7，B取0.1～0.4，c取0.1～0.3，且0

為平衡SSD計(jì)算資源和及時(shí)產(chǎn)生垃圾回收請(qǐng)求，WPO-GC以每個(gè)Plane為單位，每消耗一定數(shù)量的頁(yè)空間，進(jìn)行一次垃圾回收請(qǐng)求判斷。產(chǎn)生的GC請(qǐng)求同正常的讀寫(xiě)請(qǐng)求一起掛載到通道請(qǐng)求隊(duì)列上。為了減少SSD正常的讀寫(xiě)請(qǐng)求和兩類(lèi)垃圾回收請(qǐng)求之間的相互干擾，設(shè)定這三類(lèi)請(qǐng)求的服務(wù)優(yōu)先級(jí)由高到低依次為：1)不可中斷垃圾回收請(qǐng)求; 2)正常讀寫(xiě)請(qǐng)求; 3)可中斷的垃圾回收請(qǐng)求。

當(dāng)通道上有不可中斷垃圾回收請(qǐng)求時(shí)，立即響應(yīng)不可中斷垃圾回收請(qǐng)求，否則優(yōu)先處理讀寫(xiě)請(qǐng)求; 當(dāng)通道空閑時(shí)執(zhí)行可中斷垃圾回收請(qǐng)求。對(duì)于可中斷垃圾回收請(qǐng)求，在其執(zhí)行過(guò)程中可能會(huì)被SSD的正常讀寫(xiě)請(qǐng)求中斷，以減小GC對(duì)正常讀寫(xiě)請(qǐng)求響應(yīng)時(shí)延的影響。

2.2 目標(biāo)回收塊的選擇

在垃圾回收的目標(biāo)塊選擇研究方面，貪婪算法只注重回收的效率，會(huì)造成塊磨損的不均衡; 文獻(xiàn)[13]采用回收磨損次數(shù)最少的塊進(jìn)行回收，但會(huì)增加GC遷移數(shù)據(jù)的開(kāi)銷(xiāo)。文獻(xiàn)[15]綜合考慮了塊磨損和回收效率的考慮，相對(duì)其他策略有了很大的改進(jìn)。

WPO-GC為了保證固態(tài)盤(pán)的使用壽命和回收效率，對(duì)文獻(xiàn)[15]作進(jìn)一步的優(yōu)化改進(jìn)，選用式(3)計(jì)算每個(gè)塊得分，得分最低的作為回收塊。式(3)是在Tjioe等[15]提出的公式基礎(chǔ)上提出的，缺乏對(duì)特殊情況塊的考慮，會(huì)選擇主要包含空閑頁(yè)和無(wú)效頁(yè)的塊，這是不合理的。

式(3)由兩部分相加而成。第一部分強(qiáng)調(diào)GC操作的性能，即塊中無(wú)效頁(yè)越多，越可能被回收。

(3)

其中：invalid(i)表示第i塊中無(wú)效頁(yè)數(shù)量；page_block表示一塊中的物理頁(yè)數(shù)；erasure(i)表示第i塊的擦除次數(shù)；max表示所有塊中，塊擦除次數(shù)最大的值；min表示所有塊中，塊擦除次數(shù)最小的值。

第二部分強(qiáng)調(diào)磨損均衡，即塊的擦除次數(shù)越少，越可能被回收。兩部分的比重由系數(shù)a決定，a是塊磨損次數(shù)極差Δε的單調(diào)遞增函數(shù)(圖4)。kε是表征系統(tǒng)響應(yīng)能力的常數(shù)，kε越小，系統(tǒng)平均響應(yīng)時(shí)間越短，磨損越不均衡，kε取10時(shí)，a約為0.5，即兩部分權(quán)重相同。特別地，當(dāng)a為0時(shí)，算法不考慮磨損均衡，即選取有效數(shù)據(jù)最少的塊回收(貪婪策略); 當(dāng)a為1時(shí)，算法為純磨損均衡，即選取磨損次數(shù)最少的塊回收。回收塊的選擇在更好地考慮SSD性能的同時(shí)，能夠兼顧SSD的磨損均衡，提高SSD的壽命。

圖4 a-Δε的單調(diào)遞增曲線Fig. 4 Monotone increasing curve of a-Δε

2.3 有效數(shù)據(jù)遷移策略

在垃圾回收過(guò)程中有效頁(yè)的遷移方面，閃存芯片手冊(cè)指出可以使用高級(jí)命令copy-back進(jìn)行有效數(shù)據(jù)的遷移，但是這有很多限制條件[17-18]；部分GC算法[11,13]直接將回收塊中的有效數(shù)據(jù)遷移到空閑塊，沒(méi)有考慮數(shù)據(jù)的特性；文獻(xiàn)[15]提出考慮數(shù)據(jù)的特性，將其進(jìn)行冷熱分離，來(lái)減少后續(xù)的GC開(kāi)銷(xiāo)。

WPO-GC在文獻(xiàn)[15]的基礎(chǔ)上，增加了對(duì)“頁(yè)溫度”和“塊溫度”的逐級(jí)考慮，提出冷熱數(shù)據(jù)分離及遷移放置算法，盡可能使冷熱程度(訪問(wèn)頻度)相近的數(shù)據(jù)聚集到同類(lèi)的塊中，避免后續(xù)垃圾回收時(shí)冷數(shù)據(jù)頁(yè)的無(wú)效遷移，提高垃圾回收的效率，也減少了寫(xiě)放大，延長(zhǎng)閃存的壽命。為了實(shí)現(xiàn)這一策略，在SSD固件中維護(hù)了一張邏輯頁(yè)碼(Logical Page Number, LPN)溫度表，用于記錄每個(gè)LPN對(duì)應(yīng)的溫度，一個(gè)表項(xiàng)及其各個(gè)字段的含義見(jiàn)表1。

表1 LPN溫度表項(xiàng)Tab. 1 LPN thermometer

每當(dāng)有寫(xiě)子請(qǐng)求到來(lái)時(shí)，按照?qǐng)D5所示流程更新LPN溫度表。其中:ct是系統(tǒng)的當(dāng)前時(shí)間;u是用于界定是否是最近訪問(wèn)的時(shí)間間隔門(mén)限，當(dāng)本次訪問(wèn)時(shí)間(即系統(tǒng)當(dāng)前時(shí)間)距離最近訪問(wèn)時(shí)間大于u時(shí)，將最近訪問(wèn)次數(shù)置為1。更新TemLPN的方法為T(mén)emLPN=Luc，LPN的溫度由最近寫(xiě)訪問(wèn)次數(shù)決定。

圖5 更新LPN溫度表流程Fig. 5 Flowchart of updating LPN thermometer

一個(gè)塊中有3種頁(yè)溫度，其中:1)有效頁(yè)的溫度就是其對(duì)應(yīng)的LPN的溫度值TemLPN; 2)無(wú)效頁(yè)的溫度值顯示為其過(guò)期前對(duì)應(yīng)的LPN的溫度值; 3)空閑頁(yè)的溫度值為0。為了更好地考慮塊中的數(shù)據(jù)情況，將頁(yè)更準(zhǔn)確地放到溫度相近的塊中。提出用塊溫度(記為T(mén)emBlock)來(lái)表示一個(gè)塊的訪問(wèn)頻度，TemBlock的計(jì)算公式：

其中各符號(hào)的意義見(jiàn)表2。TemBlock的值由其中的有效頁(yè)溫度和無(wú)效頁(yè)溫度計(jì)算得到，溫度相近的頁(yè)聚集一起，失效速率也會(huì)大體相當(dāng)，以便于減少回收塊時(shí)的數(shù)據(jù)遷移。溫度越高的塊更加容易失效，提高回收效率。

表2 塊溫度計(jì)算所涉及的符號(hào)Tab. 2 Symbols about block temperature computing

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

WPO-GC的測(cè)試平臺(tái)是開(kāi)源的SSDsim[19]，首先分析所用負(fù)載trace的特點(diǎn)，然后描述了測(cè)試方案及測(cè)試過(guò)程，最后分析實(shí)驗(yàn)結(jié)果。

3.1 測(cè)試環(huán)境

測(cè)試使用SSDsim，一個(gè)經(jīng)過(guò)驗(yàn)證的固態(tài)盤(pán)模擬器，它可以根據(jù)測(cè)試具體需要修改其配置文件。本方案測(cè)試所用SSDsim模擬的硬件配置參數(shù)見(jiàn)表3，SSD物理總?cè)萘浚?×2×2×2×1 024×64×2 KB=4 GB；用戶(hù)可用容量：4 GB×0.8=3.2 GB。

表3 設(shè)備容量設(shè)置Tab. 3 Device capacity setting

3.2 測(cè)試負(fù)載分析

測(cè)試使用4種trace： Exchange、Financial、 IntelSSD_1和IntelSSD_2，特性統(tǒng)計(jì)如表4。其中，Exchange是從一臺(tái)供5 000企業(yè)用戶(hù)使用的Microsoft Exchange 2007 SP1郵件服務(wù)器上采集的trace[20-21]，以小的隨機(jī)訪問(wèn)的讀請(qǐng)求為主。Financial是在線事務(wù)處理(On-Line Transaction Processing, OLTP)應(yīng)用程序運(yùn)行在一個(gè)大型金融機(jī)構(gòu)產(chǎn)生的I/O trace[21]； IntelSSD_1和IntelSSD_2是用fio在服務(wù)器上生成請(qǐng)求，并利用block_trace工具采集得到的。

表4 trace特性統(tǒng)計(jì)Tab. 4 Characteristic statistics of trace

3.3 測(cè)試方案介紹

本文選用一種典型的垃圾回收算法Basic-GC，以及文獻(xiàn)[12]提出的DT-GC作為WPO-GC的測(cè)試對(duì)照組。Basic-GC采用的策略如下：1)目標(biāo)回收塊的選取采用貪婪策略，即回收無(wú)效數(shù)據(jù)最多的塊;2)有效數(shù)據(jù)遷移采用WECO中的冷熱數(shù)據(jù)分離方案;3)垃圾回收過(guò)程不可被中斷。

本文主要測(cè)量了以下4個(gè)指標(biāo)來(lái)評(píng)估WPO-GC方案：

1)平均響應(yīng)時(shí)間。即請(qǐng)求從提交給Flash SSD到被響應(yīng)的平均時(shí)間，用于評(píng)估WPO-GC方案的讀寫(xiě)響應(yīng)性能。

2)擦除次數(shù)的標(biāo)準(zhǔn)偏差。記錄每個(gè)閃存分組在實(shí)驗(yàn)過(guò)程中被擦除的次數(shù)的標(biāo)準(zhǔn)偏差，用于評(píng)估WPO-GC方案的磨損均衡性能。

3)擦除次數(shù)。記錄同一trace下兩種策略分別引發(fā)的回收次數(shù)，用于評(píng)估WPO-GC方案減少的磨損。

4)總寫(xiě)頁(yè)數(shù)。垃圾回收會(huì)造成寫(xiě)放大，記錄固態(tài)盤(pán)全部的寫(xiě)頁(yè)次數(shù)，進(jìn)一步評(píng)估WPO-GC方案減少的磨損。

3.4 測(cè)試結(jié)果分析

本文以Basic-GC和DT-GC方案為對(duì)照方案，對(duì)WPO-GC方案的整體性能進(jìn)行了評(píng)估。

通過(guò)比較4種負(fù)載下三者的平均響應(yīng)時(shí)間，可以看到WPO-GC方案相對(duì)于Basic-GC在性能上有很大的提升，讀/寫(xiě)平均響應(yīng)時(shí)間減少了接近20%，特別是對(duì)于分時(shí)間段密集請(qǐng)求的負(fù)載(如Financial)，讀/寫(xiě)平均響應(yīng)時(shí)間減少達(dá)40%；相對(duì)于DT-GC在性能上的提升不是很明顯，最高提升10%左右。

圖6、7分別顯示了以Basic-GC方案為基準(zhǔn)對(duì)照，歸一化后的讀、寫(xiě)平均響應(yīng)時(shí)間，縱坐標(biāo)對(duì)應(yīng)為三種方案平均讀、寫(xiě)響應(yīng)時(shí)間與Basic-GC方案平均讀、寫(xiě)響應(yīng)時(shí)間的比值。從圖6中可以看出，WPO-GC對(duì)4種trace的讀平均響應(yīng)時(shí)間相對(duì)于Basic-GC均有較大提升，提升最少的接近20%，最多的達(dá)到40%。從圖7中可以看出，WPO-GC方案相對(duì)于Basic-GC對(duì)所有trace測(cè)試的結(jié)果表現(xiàn)出寫(xiě)平均響應(yīng)時(shí)間均有很大提升，提升最少的也有17%，最多的達(dá)到40%；但是相對(duì)于DT-GC 方案，WPO-GC在性能上的提升并不明顯，最高提升10%，而且對(duì)于IntelSSD_1負(fù)載，讀寫(xiě)平均響應(yīng)性能均有所下降，約2%。

通過(guò)對(duì)SSDsim的輸出信息進(jìn)行分析，發(fā)現(xiàn)三種方案在處理一些請(qǐng)求所花費(fèi)的響應(yīng)時(shí)間是一致的，但是有些請(qǐng)求，Basic-GC方案的響應(yīng)時(shí)間遠(yuǎn)大于WPO-GC和DT-GC方案，這應(yīng)該是導(dǎo)致圖6、7結(jié)果的原因。造成這種情況是因?yàn)锽asic-GC方案在寫(xiě)請(qǐng)求到來(lái)時(shí)還在執(zhí)行垃圾回收操作，無(wú)法及時(shí)響應(yīng)，造成時(shí)延，并對(duì)后續(xù)請(qǐng)求造成累計(jì)時(shí)延。而在WPO-GC和DT-GC方案中，產(chǎn)生的是可中斷的垃圾回收請(qǐng)求，當(dāng)寫(xiě)請(qǐng)求到來(lái)時(shí)垃圾回收操作還未完成，就中斷垃圾回收操作，及時(shí)響應(yīng)，不造成時(shí)延。

圖6 歸一化的讀請(qǐng)求平均響應(yīng)時(shí)間Fig. 6 Normalized average response time of read requests

圖7 歸一化的寫(xiě)請(qǐng)求平均響應(yīng)時(shí)間Fig. 7 Normalized average response time of write requests

圖8顯示了以Basic-GC方案為基準(zhǔn)對(duì)照，歸一化的總擦除次數(shù)，縱坐標(biāo)為三種方案擦除總次數(shù)與基準(zhǔn)方案Basic-GC擦除總次數(shù)的比值。對(duì)于不同的trace，塊擦除的總次數(shù)有很大不同，且跟Basic-GC方案配置文件中垃圾回收閾值的設(shè)定有關(guān)。

圖8 歸一化的總擦除次數(shù)Fig. 8 Normalized total erasing times

圖9顯示了以Basic-GC方案為基準(zhǔn)對(duì)照，歸一化的寫(xiě)放大造成的總寫(xiě)頁(yè)次數(shù)對(duì)比情況。由于IntelSSD trace寫(xiě)請(qǐng)求的總量偏小，進(jìn)行異地更新操作次數(shù)有限，在垃圾回收次數(shù)有限的情況下，使用WPO-GC方案中目標(biāo)塊選取策略，相對(duì)于原方案中選取無(wú)效頁(yè)最多的塊進(jìn)行回收，新方案優(yōu)異性并不明顯。另外3種trace進(jìn)行更新的次數(shù)較多，盡管在目標(biāo)塊選取的回收效率上沒(méi)有貪婪算法好，但由于考慮了冷熱數(shù)據(jù)的分離，在長(zhǎng)時(shí)間的使用中彌補(bǔ)了回收效率的欠缺。測(cè)試結(jié)果表明，WPO-GC方案與Basic-GC方案在總寫(xiě)頁(yè)次數(shù)方面相比差異性不大，WPO-GC方案稍微優(yōu)異一點(diǎn)。

圖9 歸一化的總寫(xiě)頁(yè)數(shù)Fig. 9 Normalized total number of writing pages

由于WPO-GC中觸發(fā)垃圾回收時(shí)是參考DT-GC的，所以?xún)烧咴诓脸螖?shù)針對(duì)每個(gè)trace大致相同，其中的細(xì)微差異是由于WPO-GC采用冷熱數(shù)據(jù)分離算法，減少了一些有效頁(yè)的多次遷移，從而減少了寫(xiě)放大。從圖9可以看到WPO-GC方案在總寫(xiě)頁(yè)數(shù)上始終保證低于DT-GC方案，尤其對(duì)負(fù)載Exchage更是減少了20%的寫(xiě)操作。

圖10表現(xiàn)了三種方案導(dǎo)致的磨損均衡差異。當(dāng)Flash SSD所有塊擦除次數(shù)的標(biāo)準(zhǔn)差較低時(shí)，表明磨損均勻分布。圖10顯示了以Basic-GC方案為基準(zhǔn)對(duì)照，歸一化的塊擦除次數(shù)標(biāo)準(zhǔn)差，縱坐標(biāo)為三種方案塊擦除次數(shù)標(biāo)準(zhǔn)差與Basic-GC方案塊擦除次數(shù)標(biāo)準(zhǔn)差的比值。從圖中可得，在各個(gè)trace下，DT-GC方案的分組的擦除次數(shù)標(biāo)準(zhǔn)差與Basic-GC方案近似相等，而WPO-GC方案的分組的擦除次數(shù)標(biāo)準(zhǔn)差均小于其他兩種方案，其中3種trace的測(cè)試結(jié)果的標(biāo)準(zhǔn)差降低近30%，表現(xiàn)出優(yōu)異的磨損均衡性能。本文提出的新方案兼顧效率和磨損均衡，在塊擦除次數(shù)分布不均時(shí)，傾向于選擇擦除次數(shù)小的塊進(jìn)行回收，使各個(gè)塊的擦出次數(shù)趨向于相同。同時(shí)由于SSDsim的垃圾回收機(jī)制是基于分組的，各分組中塊的擦除次數(shù)實(shí)際上更為平均，有利于提升固態(tài)盤(pán)的壽命。

4 結(jié)語(yǔ)

本文在詳細(xì)剖析垃圾回收過(guò)程的基礎(chǔ)上，提出了一種全程優(yōu)化的垃圾回收方法WPO-GC，盡可能全面地考慮各步驟對(duì)SSD正常讀寫(xiě)請(qǐng)求和壽命的影響。在開(kāi)源的模擬器SSDsim上實(shí)現(xiàn)并驗(yàn)證了WPO-GC的有效性。實(shí)驗(yàn)結(jié)果表明，同典型GC算法相比，WPO-GC可以減少SSD讀請(qǐng)求延遲20%～40%，寫(xiě)請(qǐng)求延遲17%～40%，并能將均衡磨損近30%，從而延長(zhǎng)其使用壽命；同DT-GC策略比較，在性能方面的優(yōu)化不是很明顯，最高提升10%，但是在減少寫(xiě)放大和均衡磨損上有了近30%的優(yōu)化。如何在保證讀寫(xiě)性能的情況下，進(jìn)一步延長(zhǎng)SSD的壽命，是一個(gè)值得深入研究的課題。本文提出的方案主要是優(yōu)化并結(jié)合前人的工作，接下來(lái)的工作重心將放在如何將垃圾回收與緩存有效結(jié)合，在進(jìn)行有效數(shù)據(jù)遷移時(shí)，判斷該數(shù)據(jù)所對(duì)應(yīng)的邏輯地址是否在緩存已經(jīng)被更新，從而減少遷移耗時(shí)。

References)

[1] LEE S W, PARK D J, CHUNG T S, et al. A log buffer-based flash translation layer using fully-associative sector translation[J]. ACM Transactions on Embedded Computing Systems, 2007, 6(3): 150-151.

[2] TANG X, MENG X. ACR: an adaptive cost-aware buffer replacement algorithm for Flash storage devices[C]// Proceedings of the 2010 11th International Conference on Mobile Data Management. Piscataway, NJ: IEEE, 2010: 33-42.

[3] SOGA A, SUN C, TAKEUCHI K. NAND flash aware data management system for high-speed SSDs by garbage collection overhead suppression[C]// Proceedings of the 2014 IEEE 6th International Memory Workshop. Piscataway, NJ: IEEE, 2014: 1-4.

[4] fio[EB/OL].[2016-05-22].http://freecode.com/projects/fio.

[5] 郭御風(fēng), 李瓊, 劉光明, 等. 基于 NAND 閃存的固態(tài)盤(pán)技術(shù)研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2009, 46(2): 328-328.(GUO Y F, LI Q, LIU G M, et al. Research and development of solid state disk technology based on NAND flash memory[J]. Journal of Computer Research and Development, 2009, 46(2): 328-328.)

[6] 馬宇川. 拒絕掉速閃迪 Extreme Pro480GB 固態(tài)硬盤(pán)深度體驗(yàn)[J].微型計(jì)算機(jī), 2014(21): 71-74.(MA Y C. Rejected SanDisk Pro480GB extreme solid state hard disk depth experience[J]. Micro Computer, 2014(21): 71-74.)

[7] BEAK S,AHN S, CHOI J. Uniformity improving page allocation for flash memory file systems[C]// Proceedings of the 7th ACM & IEEE International Conference on Embedded Software. New York: ACM, 2007:154-163.

[8] KIM Y, ORAL S, SHIPMAN G M, et al. Harmonia: a globally coordinated garbage collector for arrays of solid-state drives[C]// Proceedings of the 2011 IEEE 27th Symposium on Mass Storage Systems and Technologies. Washington, DC: IEEE Computer Society, 2011: 1-12.

[9] HA K, KIM J. A program context-aware data separation technique for reducing garbage collection overhead in NAND flash memory[C]// Proceedings of the 7th IEEE International Workshop on Storage Network Architecture and Parallel I/Os. Piscataway, NJ: IEEE, 2011:1-10.

[10] GALAND E,TOLEDO S. Algorithms and data structures for flash memories[J]. ACM Computing Surveys, 2005, 37(2):138-163.

[11] LEE J, KIM Y, SHIPMAN G, et al. A semi-preemptive garbage collector for solid state drives[C]// Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software. Piscataway, NJ: IEEE, 2011:12-21.

[12] QIN Y, FENG D, LIU J, et al. DT-GC: adaptive garbage collection with dynamic thresholds for SSDs[C]// Proceedings of the 2014 International Conference on Cloud Computing and Big Data. Piscataway, NJ: IEEE, 2014: 182-188.

[13] KWON O, LEE J, KOH K. EF-Greedy: a novel garbage collection policy for flash memory based embedded systems[C]// Proceedings of the 7th International Conference on Computational Science. Berlin: Springer, 2007: 913-920.

[14] KIM H, LEE S. An effective flash memory manager for reliable flash memory space management[J]. IEICE Transactions on Information & Systems, 2002, E85D(6): 950-964.

[15] TJIOE J, BLANCE A, XIE T, et al. Making garbage collection wear conscious for flash SSD[C]// Proceedings of the 2012 IEEE 7th International Conference on Networking, Architecture and Storage. Washington, DC: IEEE Computer Society, 2012: 114-123.

[16] WU S, LIN Y, MAO B, et al. GCaR: garbage collection aware cache management with improved performance for flash-based SSDs[C]// Proceedings of the 2016 International Conference on Supercomputing. New York: ACM, 2016: Article No. 28.

[17] MOMODOMI M, ITOH Y, SHIROTN R, et al. An experimental 4-Mbit CMOS EEPROM with a NAND-structured cell[J]. IEEE Journal of Solid-State Circuits, 1989, 24(5): 1238-1243.

[18] XIE W, CHEN Y. An adaptive separation-aware FTL for improving the efficiency of garbage collection in SSDs[C]// Proceedings of the 2014 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Piscataway, NJ: IEEE, 2014: 552-553.

[19] HU Y, JIANG H, FENG D, et al. Performance impact and interplay of SSD parallelism through advanced commands，allocation strategy and data granularity[C]// Proceedings of the 2011 International Conference on Supercomputing. New York: ACM, 2011: 96-107.

[20] KAVALANCKER S, WORTHINGTON B, ZHANG Q, et al. Characterization of storage workload traces from production Windows servers[C]// Proceedings of the 2008 IEEE International Symposium on Workload Characterization. Piscataway, NJ: IEEE, 2008: 119-128.

[21] SNIA IOTTA Repository[EB/OL].[2016-05-22].http://iotta.snia.org/traces/130.

This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2015AA016701, 2015AA015301), the National Natural Science Foundation of China (61303046, 61402189, 61472153).

FANG Caihua, born in 1994, M. S. candidate. His research interests include big data storage, solid state storage, data deduplication.

LIU Jingning, born in 1957, Ph. D., professor. Her research interests include solid state storage, data mining, distributed storage.

TONG Wei,born in 1977, Ph.D., lecturer. Her research interests include non-volatile memory device, input/output virtualization.

GAO Yang, born in 1992, M. S. candidate. His research interests include big data storage, key-value storage.

LEI Xia, born in 1993, M. S. candidate. Her research interests include big data storage, secure data deletion.

JIANG Yu, born in 1993, M. S. candidate. His research interests include solid state storage, novel non-volatile memory device.

Whole process optimized garbage collection for solid-state drives

FANG Caihua1,2，LIU Jingning1,2，TONG Wei1,2*，GAO Yang1,2，LEI Xia1,2，JIANG Yu1,2

(1.WuhanNationalLaboratoryforOptoelectronics(HuazhongUniversityofScienceandTechnology),WuhanHubei430074,China;2.KeyLaboratoryofInformationStorageSystemofMinistryofEducation(HuazhongUniversityofScienceandTechnology),WuhanHubei430074,China)

Due to NAND flash’ inherent restrictions like erase-before-write and a large erase unit, flash-based Solid-State Drives (SSD) demand garbage collection operations to reclaim invalid physical pages. However, the high overhead caused by garbage collection significantly decrease the performance and lifetime of SSD. Garbage collection performance will be more serious, especially when the data fragments of SSD are frequently used. Existing Garbage Collection (GC) algorithms only focus on some steps of the garbage collection operation, and none of them provids a comprehensive solution that takes into consideration all the steps of the GC process. On the basis of detailed analysis of the GC process, a whole process optimized garbage collection algorithm named WPO-GC (Whole Process Optimized Garbage Collection) was proposed, which integrated optimizations on each step of the GC in order to reduce the negative impact on normal read/write requests and SSD’ lifetime at the greatest extent. Moreover, the WPO-GC was implemented on SSDsim which is an open source SSD simulator to evaluate its efficiency. The experimental results show that the proposed algorithm can decreases read I/O response time by 20%-40% and write I/O response time by 17%-40% respectively, and balance wear nearly 30% to extend the lifetime, compared with typical GC algorithm.

flash memory; Solid-State Drive (SSD); Garbage Collection (GC); wear-leveling; lifetime

2016-07-15;

2016-11-25。

國(guó)家863計(jì)劃項(xiàng)目(2015AA016701, 2015AA015301)；國(guó)家自然科學(xué)基金資助項(xiàng)目(61303046, 61402189, 61472153)。

方才華(1994—)，男，浙江三門(mén)人，碩士研究生，主要研究方向：大數(shù)據(jù)存儲(chǔ)、固態(tài)存儲(chǔ)、數(shù)據(jù)去重； 劉景寧(1957—)，女，湖北武漢人，教授，博士,主要研究方向：固態(tài)存儲(chǔ)、數(shù)據(jù)挖掘、分布式存儲(chǔ)； 童薇(1977—)，女，湖北黃陂人，講師，博士，主要研究方向：非易失性存儲(chǔ)器、輸入/輸出虛擬化； 高陽(yáng)(1992—)，男，湖北廣水人，碩士研究生，主要研究方向：大數(shù)據(jù)存儲(chǔ)、鍵值對(duì)存儲(chǔ)； 雷霞(1993—)，女，湖北仙桃人，碩士研究生，主要研究方向：大數(shù)據(jù)存儲(chǔ)、安全刪除； 蔣瑜(1993—)，男，江蘇常州人，碩士研究生，主要研究方向：固態(tài)存儲(chǔ)、非易失存儲(chǔ)器。

1001-9081(2017)05-1257-06

10.11772/j.issn.1001-9081.2017.05.1257

TP333.35

A