方才華，劉景寧，童 薇，高 陽，雷 霞，蔣 瑜

(1.武漢光電國家實驗室(華中科技大學(xué)), 武漢 430074; 2.信息存儲系統(tǒng)教育部重點實驗室(華中科技大學(xué)), 武漢 430074)

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

方才華1,2，劉景寧1,2，童 薇1,2*，高 陽1,2，雷 霞1,2，蔣 瑜1,2

(1.武漢光電國家實驗室(華中科技大學(xué)), 武漢 430074; 2.信息存儲系統(tǒng)教育部重點實驗室(華中科技大學(xué)), 武漢 430074)

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

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

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

0 引言

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

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

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

1 背景與動機(jī)

1.1 SSD的架構(gòu)

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

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

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

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

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

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

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

1.3 相關(guān)工作

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

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

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

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

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

1.4 動機(jī)

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

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

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

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

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

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

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

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

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

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

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

H=aE+B(1-Vp)

(1)

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

(2)

其中：E表示SSD預(yù)留空間比例，由SSD廠商設(shè)定;Vp是有效頁比例;Ip是無效頁比例;a、b、c、A、B均為權(quán)值系數(shù)，滿足具體取值為：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計算資源和及時產(chǎn)生垃圾回收請求，WPO-GC以每個Plane為單位，每消耗一定數(shù)量的頁空間，進(jìn)行一次垃圾回收請求判斷。產(chǎn)生的GC請求同正常的讀寫請求一起掛載到通道請求隊列上。為了減少SSD正常的讀寫請求和兩類垃圾回收請求之間的相互干擾，設(shè)定這三類請求的服務(wù)優(yōu)先級由高到低依次為：1)不可中斷垃圾回收請求; 2)正常讀寫請求; 3)可中斷的垃圾回收請求。

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

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

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

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

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

(3)

其中：invalid(i)表示第i塊中無效頁數(shù)量；page_block表示一塊中的物理頁數(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)時間越短，磨損越不均衡，kε取10時，a約為0.5，即兩部分權(quán)重相同。特別地，當(dāng)a為0時，算法不考慮磨損均衡，即選取有效數(shù)據(jù)最少的塊回收(貪婪策略); 當(dāng)a為1時，算法為純磨損均衡，即選取磨損次數(shù)最少的塊回收?；厥諌K的選擇在更好地考慮SSD性能的同時，能夠兼顧SSD的磨損均衡，提高SSD的壽命。

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

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

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

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

表1 LPN溫度表項Tab. 1 LPN thermometer

每當(dāng)有寫子請求到來時，按照圖5所示流程更新LPN溫度表。其中:ct是系統(tǒng)的當(dāng)前時間;u是用于界定是否是最近訪問的時間間隔門限，當(dāng)本次訪問時間(即系統(tǒng)當(dāng)前時間)距離最近訪問時間大于u時，將最近訪問次數(shù)置為1。更新TemLPN的方法為TemLPN=Luc，LPN的溫度由最近寫訪問次數(shù)決定。

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

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

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

表2 塊溫度計算所涉及的符號Tab. 2 Symbols about block temperature computing

3 實驗結(jié)果與分析

WPO-GC的測試平臺是開源的SSDsim[19]，首先分析所用負(fù)載trace的特點，然后描述了測試方案及測試過程，最后分析實驗結(jié)果。

3.1 測試環(huán)境

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

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

3.2 測試負(fù)載分析

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

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

3.3 測試方案介紹

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

本文主要測量了以下4個指標(biāo)來評估WPO-GC方案：

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

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

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

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

3.4 測試結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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)盤技術(shù)研究[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)硬盤深度體驗[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。

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

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

1001-9081(2017)05-1257-06

10.11772/j.issn.1001-9081.2017.05.1257

TP333.35

A