全程優化的固態硬盤垃圾回收方法

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

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

全程優化的固態硬盤垃圾回收方法

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

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

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

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

閃存；固態盤；垃圾回收；磨損均衡；使用壽命

0 引言

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

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

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

1 背景與動機

1.1 SSD的架構

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

圖1 SSD的整體架構Fig. 1 Overall architecture of SSD

圖2 閃存芯片的架構Fig. 2 Architecture of flash chip

1.2 垃圾回收的機制

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

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

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

1.3 相關工作

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

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

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

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

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

1.4 動機

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

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

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

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

3)選擇適當的垃圾回收目標塊。采用綜合考慮塊中無效頁所占比例和擦除次數的均衡策略， 提高垃圾回收的效率，延長閃存壽命。

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

2 設計和實現

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

2.1 產生垃圾回收請求

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

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

H=aE+B(1-Vp)

(1)

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

(2)

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

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

2.2 目標回收塊的選擇

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

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

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

(3)

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

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

圖4 a-Δε的單調遞增曲線Fig. 4 Monotone increasing curve of a-Δε

2.3 有效數據遷移策略

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

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

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

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

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

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

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

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

3 實驗結果與分析

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

3.1 測試環境

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

表3 設備容量設置Tab. 3 Device capacity setting

3.2 測試負載分析

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

表4 trace特性統計Tab. 4 Characteristic statistics of trace

3.3 測試方案介紹

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

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

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

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

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

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

3.4 測試結果分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結語

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

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] 郭御風, 李瓊, 劉光明, 等. 基于 NAND 閃存的固態盤技術研究[J]. 計算機研究與發展, 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 固態硬盤深度體驗[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)；國家自然科學基金資助項目(61303046, 61402189, 61472153)。

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

1001-9081(2017)05-1257-06

10.11772/j.issn.1001-9081.2017.05.1257

TP333.35

A