基于頁面寫相關的閃存轉換層策略

陳金忠，姚念民，蔡紹濱，戰福瑞，孫美玲

（哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001）

1 引言

過去幾十年，機械硬盤的機械特性帶來了隨機讀寫的低性能和高功耗[1～3]。近年來，閃存的體積小、低功耗和抗震性等特點，使得閃存技術被廣泛應用于MP3、PDA和移動電話[4]。隨著固態硬盤價格逐年降低，不久的將來，固態硬盤將成為企業級存儲系統的重要組成部分[5]。與機械硬盤不同，固態硬盤是基于半導體芯片，主要包括2種類型的閃存芯片、NOR和NAND[6]。NOR類似于內存，容量小，它允許通過地址訪問任何的一個閃存單元，數據的寫入和擦除速度慢。NAND容量大，數據的寫入和擦除的速度較快，但需要經過I/O地址轉換才能訪問。因此，NAND更適用于固態硬盤。大多數的硬盤廠商都支持和傳統硬盤相同的接口，例如SATA和SCSI接口。雖然固態硬盤的讀寫速度比傳統的機械硬盤快，但無論是基于NOR或NAND類型的固態硬盤都不支持“就地更新”，在更新某一塊上的數據頁之前，必須先把整個數據塊擦除，稱為“寫前擦除”。相對讀寫操作，塊擦除的代價非常高。為了避免這種昂貴的擦除開銷，固態硬盤引入閃存轉換層(FTL)。FTL通過預留一些空閑的日志塊，把需要更新的數據寫入空閑日志塊，從而避免了“寫前擦除”。

經典的FTL策略有2種，分別是基于塊相聯的BAST[7]策略和基于全相聯日志緩存的 FAST[8]策略。BAST為每個數據塊指定唯一的日志塊，更新的數據只能寫入對應的日志塊。BAST適合順序存取。對于隨機存取，BAST會造成存儲空間的浪費。FAST采用全相聯的映像方式，更新的數據可以寫入到任何的日志塊，不會造成存儲空間的浪費。FAST還將日志塊劃分為順序緩存日志塊與隨機緩存日志塊，分別用于優化順序存取與隨機存取。然而，在 FAST策略中，一個日志塊可能關聯多個數據塊，增加了垃圾回收的成本。為了克服BAST、FAST等策略的缺點，本文提出了一種基于頁面“寫相關”的FTL策略PWRST。PWRST統計 I/O請求的歷史信息，將“寫相關”的頁面存儲在同一數據塊。PWRST減少了頁面復制開銷與塊的擦除成本，降低了垃圾回收的成本，提高了固態硬盤的性能。

2 相關工作

2.1 NAND內部結構

NAND閃存芯片由若干個邏輯單元組成，每個邏輯單元包括多個存儲平面，每個存儲平面由多個存儲塊構成。假設每個閃存芯片由2個邏輯單元組成，每個邏輯單元由2個存儲平面構成，每個存儲平面由4個存儲塊構成。如圖1所示，按照存儲塊在每個存儲平面上的分布方式，將固態硬盤分為 3種不同的架構，分別是無條帶化架構、部分條帶化架構和全條帶化架構。圖1(a)顯示無條帶化架構的NAND閃存，將存儲塊按順序存放在每個存儲平面上，這種結構不支持并行讀寫。圖1(b)顯示了部分條帶化架構的NAND閃存。這種結構的特點是將存儲塊分散存放在成對存儲平面上，同一個邏輯單元內部的2個存儲平面可以并行讀寫。全條帶化架構的NAND閃存如圖1(c)所示。存儲塊分散存放在每一個存儲平面上，2個邏輯單元可以并行讀寫。

2.2 NAND閃存轉換層

由于 NAND閃存在更新存儲頁時必須擦除整個存儲塊，這大大地降低了 NAND的性能。FTL通過預留一些日志塊，將更新的數據寫入空閑日志塊，從而避免擦除整個數據塊。閃存轉換層主要功能如下。

圖1 SSD的3種不同的內部架構

1) 映射機制(mapping mechanism)：按照映射的粒度，分為頁面級別映射與塊級別映射。頁面級別映射的優點是容易實現且高效，缺點是需要大量的空間存儲頁面映射表。塊級別映射節省了存儲映射表的空間，但在垃圾回收時需要大量的頁面復制操作，增加了垃圾回收的開銷。許多FTL策略采用混合映射機制，大量的數據塊采用塊級別映射，少量的日志塊采用頁面級別映射[9,10]。這種混合映射機制提高了固態硬盤的性能。

2) 垃圾回收(garbage collection)：當固態硬盤的空閑塊數量少于某個下限值時(通常小于總塊數的15%)，垃圾回收算法掃描整個固態硬盤以回收存儲塊。文獻[11,12]通過減少垃圾回收過程中擦除塊數來延長固態硬盤的使用壽命。

3) 損耗均衡(wear-leveling)：由于程序的局部性原理，固態硬盤的某些存儲塊會被頻繁的更新和擦除，導致這些塊的損耗加快。閃層轉換層通常采用“冷塊”與“熱塊”的交換的方法來達到所有存儲塊損耗均衡的目的。文獻[13]提出了FeGC機制，優先回收失效頁數量多和失效時間長的數據塊，達到了減少垃圾回收開銷和損耗均衡的目的。針對閃存陣列，文獻[14]提出了FAP策略，通過交換擦除次數多和擦除次數少的塊，達到NAND閃存芯片之間的損耗均衡的目標。

2.3 塊相聯(BAST)策略

BAST的基本思想是每一個數據塊關聯唯一的日志塊，更新時，頁面寫入相應的日志塊。如果日志塊沒有空閑的頁面，即使其他的日志塊有空閑頁面，也不能寫入。假設LPN表示I/O請求的邏輯頁號，data表示寫入的數據，每個塊的大小為S。寫操作定義為 write(LPN, data)。在寫操作之前，需要將邏輯頁號轉換成邏輯塊號(LBN)，計算公式為LBN=LPNmodS。然后，根據LBN查找邏輯塊的物理塊號(PBN)，最后，將數據data寫入數據塊PBN。假設每個存儲塊包括4個頁面，日志塊數為2。I/O請求的邏輯頁面向量為V={0,1,2,3,4,5,6,7,2,3,2,3,7,1,1,2}。邏輯塊0對應數據塊0，為數據塊0分配日志塊0。邏輯塊1對應數據塊1，為數據塊1分配日志塊1。BAST的操作流程如圖2所示。由于頁 0、1、2、3的邏輯塊號為 0，寫入對應的數據塊0。頁4、5、6、7的邏輯塊號為1，寫入對應的數據塊1。當更新邏輯頁2、3、2、3時，寫入對應的日志塊 0。當更新邏輯頁 7、1、1、2，邏輯頁7寫入到日志塊1。此時數據塊0對應的日志塊已經寫滿，邏輯頁1、1、2不能寫入日志塊 0，需要執行擦除操作。從圖 2可以看出，日志塊1還有空閑的頁面，但不能將數據塊0的頁面寫入日志塊 1。BAST造成了日志塊空間的浪費，其主要原因是在BAST策略中，一個數據塊只關聯唯一的日志塊，更新的頁面只能寫入對應的日志塊。

圖2 BAST策略寫操作流程

2.4 全相聯(FAST)策略

FAST策略的基本思想是數據塊可以共享日志塊。更新的數據可以寫入任何日志塊的空閑頁面。FAST策略的操作流程如圖3所示。FAST策略更新邏輯頁1、1、2時，由于日志塊1還有空閑頁，把邏輯頁1、1、2寫入日志塊1。FAST策略充分利用存儲空間，減少不必要的擦除開銷和提高日志塊的空間利用率。如圖3所示，日志塊1的邏輯頁7對應數據塊 1，邏輯頁 1、1、2對應數據塊 0。如果回收日志1，需要將日志塊1與數據塊0，數據塊1合并，進行多次頁面復制和塊擦除。這是FAST的主要缺點。其原因是在FAST策略中，一個日志塊關聯了多個數據塊。因此，FAST策略雖然克服了BAST策略的缺點，但也帶來了昂貴的頁面復制與塊擦除開銷，從而降低了固態硬盤的性能和縮短了固態硬盤的使用壽命。在2.5節將具體分析3種垃圾回收的開銷。

圖3 FAST策略寫操作流程

2.5 垃圾回收開銷的分析

垃圾回收分為3種形式，全合并(full-merge)回收、部分合并(partial-merge)回收和交換合并(switch-merge)回收。如圖4(a)所示，全合并回收需要復制大量的有效頁(valid)和多次塊擦除(erase)。如圖 4(b)所示，部分合并回收需要復制少量的有效頁和2次塊擦除。如圖 4(c)所示，交換合并回收不需要復制頁面，僅需2次塊擦除。因此，應該盡可能地增加部分合并回收與交換回收的次數，減少全合并回收的次數。假設Cc表示復制一頁的開銷，Ce表示擦除數據塊的開銷，N表示數據塊包含頁的數量，Nv表示數據塊包含有效頁的數量，Na表示日志塊所關聯的數據塊的數量，Wf、Wp和Ws分別表示全合并回收，部分合并回收和交換合并回收的開銷，則有

圖4 3種全合并回收過程

由式(1)～式(3)可知，在全合并回收時，日志塊所關聯的數據塊數量Na＞1，在部分合并和交換合并時，日志塊關聯的數據塊數量Na=1。因此，減少垃圾回收開銷的關鍵是減小Na。由2.4節可知，FAST的一個日志塊可能關聯多個數據塊，即Na＞ 1 。在垃圾回收時，需要復制大量的頁面和多次擦除塊，使得固態硬盤性能的下降。

3 PWRST策略

針對BAST和FAST的缺點，PWRST根據I/O請求的歷史特性，將“寫相關”的頁面存儲到同一數據塊。所謂“寫相關”是指I/O請求訪問頁面A之后，在最近一段時間內將會訪問頁面B，稱頁面A與頁面B是“寫相關”。例如，文件系統在更新文件時，對應的元數據也會被更新，這2次操作的頁面是“寫相關”。如果數據塊的頁面都是“寫相關”，這些頁面可能都是失效的，在垃圾回收時，只需要進行交換合并回收。

3.1 系統架構

SSD的系統架構如圖5所示。PWRST分為3個模塊，分別是 I/O請求歷史收集模塊(RHC)、頁面寫相關分析模塊(WRA)和頁面聚類模塊(PC)。首先，I/O請求歷史收集模塊負責記錄負載最近一段時間內訪問的邏輯頁號。其次，頁面寫相關分析模塊根據I/O請求歷史找出“寫相關”的頁面。最后，頁面聚類模塊將具有“寫相關”的頁面存儲到同一數據塊。

圖5 SSD的系統架構

3.2 I/O請求歷史收集模塊(RHC)

首先，文件系統發出的 I/O請求將邏輯扇區(LBA)號映射為邏輯頁號(LPN)，FTL根據邏輯頁號得到邏輯塊號(LBN)和塊內偏移(offset)，然后通過查詢塊映射表得到物理塊號(PBN)。RHC模塊使用散列表對I/O請求的時刻T和訪問的邏輯頁號進行記錄。其中，T和LPN分別表示了I/O請求的時間和空間特性。散列表可以實現對I/O請求的快速查找，更新以及刪除操作，其維護非常方便。因此，散列表可以有效地維護I/O請求的歷史信息。

3.3 頁面寫相關分析模塊(WRA)

圖6 I/O請求訪問的頁面序列

3.4 頁面聚類模塊

從3.3節可知，“寫相關”的頁面具有訪問時間的關聯性，如果將這些頁面存儲到SSD的同一數據塊，那么在垃圾回收時，數據塊包含的頁面可能都是失效的頁面，只需要一次擦除操作。從而避免了昂貴的頁面復制開銷，提高了垃圾回收的效率。頁面聚類的模塊功能是將“寫相關”的頁面存儲到同一個數據塊，其基本原理是利用了數據挖掘中的層次聚類的方法。即初始時將每個頁面劃分為一個單獨的組，在接下來的迭代中，把那些“寫相關”的頁面合并成一個組，直到這個組的大小等于數據塊的大小，然后將這些頁面寫入空閑塊。圖7給出了具體的操作流程。首先，從I/O請求的歷史集合RHC找出訪問頻率最高的頁面pi，放入組iA。然后，根據頁面寫相關分析模塊，找出與頁面pi“寫相關”的頁面pj，并將頁面pj放入iA，組中的頁面數ci加1。如果iA中頁面的數量等于塊的大小，聚類完成。否則，繼續聚類。對于某些系統公共頁面來說，可能有許多與其寫相關系數較大的頁面。這些公共頁面可以使用頁面映射的方式，那么在垃圾回收時，就不會引起全合并操作。

4 性能分析

實驗分別測試了 BAST、FAST和 PWRST在Postmark[15]、IOzone[16]和 TPC-C[17]負載下的垃圾回收開銷和I/O請求的響應時間。

圖7 頁面聚類算法

4.1 測試環境

本實驗所使用的模擬器是建立DiskSim之上的SSD模擬器[18]。該模擬器提供了對垃圾回收機制與交叉讀寫機制的模擬。表1給出了SSD模擬器的配置參數，包括SSD基本組成部分、頁面的讀寫時延、擦除塊的時延、擦除模式等。

表1 SSD模擬器配置參數

4.2 測試負載和參數設置

測試的負載包括 Postmark、IOzone和TPC-C。其中，Postmark和IOzone是I/O密集型的文件系統測試集，包括大量的隨機讀寫操作。IOzone負載是對大文件的測試。Postmark負載則是頻繁、大量地存取小文件。TPC-C負載是數據庫測試集。模擬實驗中的2個重要的參數：THs和θth。其中，THs表示系統空閑塊數占總存儲塊的比例。θth表示“寫相關”的門限值，分別設置為0.5、0.7和0.9，對應的PWRST策略表示為 PWRST(0.5)、PWRST(0.7)和 PWRST(0.9)。

4.3 垃圾回收開銷

SSD垃圾回收主要包括兩方面：頁面遷移數和擦除塊數；其中頁面遷移數是指在全合并回收和部分合并回收過程中復制的頁面數量。而擦除塊數是指在全合并、部分合并和交換合并回收過程擦除的塊數總和。SSD模擬器分別對 Postmark、IOzone和TPC-C 3種負載，生成106個讀寫請求進行測試。

4.3.1 頁面遷移數

表2～表4分別給出了THs的值為0.15、0.10和0.05時，3種算法垃圾回收時的頁面遷移數。PWRST(0.7)在Postmark和IOzone負載下的頁面遷移數比BAST減少了30%，比FAST減少了20%。在TPC-C負載下，PWRST(0.7)頁面遷移數比BAST減少15%,比FAST減少了12%。主要原因是BAST數據塊對應唯一的日志塊，當關聯的日志塊沒有空間時，即使其他的日志塊有空閑頁時，也會觸發垃圾回收機制。FAST的日志塊可能關聯多個數據塊，增加了全合并的次數，從而增加了頁面遷移數。另外，3種策略的頁面遷移數都隨著THs值的減小而增加，這是由于隨著空閑塊數目的減少，執行垃圾回收的概率增大。另外，PWRST(0.7)的頁面遷移數量少于 PWRST(0.5)和 PWRST(0.9)。PWRST(0.9)只將歸一化概率大于0.9的頁面寫入同一數據塊，因而會遺漏一些頁面。而PWRST(0.5)可能將一些不相關的頁面寫入同一數據塊，因此會增加頁面遷移數。

4.3.2 塊擦除次數

表5～表7給出了BAST、FAST和PWRST在3種負載下的塊擦除次數。BAST、FAST和PWRST這3種策略塊擦除次數隨著THs的減小而增加。在Postmark和IOzone負載下，PWRST(0.7)的塊擦除次數比BAST減少10%,比FAST減少8%。相比于BAST和FAST，PWRST利用頁面“寫相關”減少了全合并回收的次數和塊的擦除次數。對于固態硬盤，擦除次數不僅與性能相關，而且影響固態硬盤的使用壽命。因此，PWRST策略能夠有效地提高固態硬盤的性能和延長固態硬盤的使用壽命。

表2 當THs=0.15時，BAST、FAST和PWRST的頁面遷移數

表3 當THs=0.10時，BAST、FAST和PWRST的頁面遷移數

表4 當THs=0.05時，BAST、FAST和PWRST的頁面遷移數

表5 THs=0.15時，3種策略的塊擦除數

表6 THs=0.10時，3種策略的塊擦除數

表7 THs=0.05時，3種策略塊的擦除數

4.4 3種合并回收的開銷

圖8～圖10給出了在THs= 0 .05時，全合并回收，部分合并回收與交換合并回收在3種負載下的開銷。BAST在Postmark負載下的全合并次數占80%左右，FAST的全合并回收次數占50%左右，而PWRST全合并次數只占了10%左右。FAST充分利用了存儲空間，避免了不必要的擦除開銷。因此，FAST的全合并開銷比BAST低。PWRST將“寫相關”的頁面寫入同一數據塊，減少了日志塊關聯的數據塊數量，增加了部分合并回收與交換合并回收的比例。因此，PWRST垃圾回收的開銷比BAST和FAST都小。

圖8 在Postmark負載下合并開銷的比例

圖9 在IOzone負載下合并開銷的比例

圖10 在TPC-C負載下合并開銷的比例

4.5 不同FTL策略的I/O平均響應時間

圖11 當 T Hs = 0 .15時，BAST、FAST和PWRST的平均響應時間

圖12 當 T Hs = 0 .10時，BAST、FAST和PWRST的平均響應時間

圖13 當 T Hs = 0 .05時，BAST、FAST和PWRST的平均響應時間

圖11～圖13給出了3種FTL策略在Postmark、IOzone和TPC-C 3種負載下的平均響應時間。當THs= 0 .15時，PWRST(0.7)在Postmark下的平均響應時間比BAST減少了18%，比FAST減少了14%。PWRST(0.7)在TPC-C下的平均響應時間比BAST策略減少了10%，比FAST減少了8%。當THs=0.05時，PWRST(0.7)在 Postmark下的平均響應時間比BAST減少35%，比FAST減少26%。在TPC-C負載下，PWRST(0.7)的平均響應時間比BAST減少了12%,比FAST減少了10%。因此，本文提出的PWRST策略在響應時間等方面優越于BAST和FAST。

5 結束語

經典的閃存轉換層策略（如BAST、FAST）都有其自身的缺點，BAST會造成存儲空間的浪費和不必要的擦除開銷。FAST策略中的日志塊可能關聯多個數據塊，垃圾回收的開銷非常大。本文提出了一種基于頁面寫相關的FTL策略PWRST。PWRST將“寫相關”的頁面存儲到同一數據塊，減少了全合并回收的次數。實驗表明，PWRST減少了塊的擦除次數，降低了垃圾回收的開銷和I/O的平均響應時間。進一步驗證了PWRST的可行性和優越性。

[1] CHUNG T S, PARK S W, LEE D H,et al.Systems software for flash memory： a survey[A].Proceedings of the 2006 IFIP International Conference on Embedded and Ubiquitous Computing[C].Korea, 2006.394-404.

[2] DING X N, JIANG S, CHEN F,et al.DULO： an effective buffer cache management scheme to exploit both temporal and spatial localities[J].ACM Trans Storage, 2007, 3(2)：1242522.

[3] LI Z M, CHEN Z F, SUDARSHAN M S,et al.C-miner： mining block correlations in storage systems[A].Proc of FAST’02[C].San Francisco, USA, 2004.173-186.

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

[5] LEVENTHAL A.Flash storage memory communications[J].Communications of the ACM, 2008, 51(7)：47-51.

[6] SANTARINI M.NAND versus NOR[J].EDN, 2005, 50(21)：41-48.

[7] KIM J S, KIM J M, NOH S H,et al.A space-efficient flash translation layer for compactflash systems[J].IEEE transactions on Consumer Electronics, 2002, 48(2)：366-375.

[8] LEE S W, PARK D J, CHUNG T S,et al.A log buffer based flash translation layer using fully associative sector translation[J].IEEE Transactions on Embedded Computing Systems, 2007, 6(3)：18-45.

[9] KANG J U, JO H, KIM J S,et al.A superblock based flash translation layer for NAND flash memory[A].Proc of ICES’06[C].Seoul, Korea,2006.161-170.

[10] CHAO H, SHIN D , EOM Y I.Kast： k-associative sector translation for NAND flash memory in real-time systems[A].Design, Automation Test in Europe Conference Exhibition[C].Nice, France, 2009.507-512.

[11] CHEN F, LUO T, ZHANG X D.CAFTL： A content-aware flash translation layer enhancing the lifespan of flash memory based solid state drivers[A].Proceedings of FAST’2011[C].San Jose, CA, USA, 2011.77-90.

[12] WU G Y, HE X B.ΔFTL： improving SSD lifetime via exploiting content locality[A].7th ACM European Conference on Computer Systems, Euro-Sys’12[C].Bern, Switzerland, 2012.253-265.

[13] KWON O, KOH K, LEE J,et al.FEGC： an efficient garbage collection scheme for flash memory based storage systems[J].Journal of Systems and Software, 2011, 84(9)：1507-1523.

[14] ANAM Z, SUMAYYA S, SABA Z,et al.A Flash aging prevention technique (FAP) for flash based solid state disks[A].International Conference on Computer Science & Education- ICCSE[C].Singapore,2011.531-536.

[15] KATCHER J.Postmark： A New File System Benchmark[R].Technical Report TR 3022, Network Appliance, 1997.

[16] NORCOTT W, CAPPS D.IOzone file system benchmark[EB/OL].http：//www.iozone.org.

[17] Transaction processing performance council TPC-C benchmark[EB/OL].http：//www.tpc.org/tpcc/spec/tpcc_current.pdf, 2004.

[18] KIM Y, TAURAS B, GUPTA A,et al.Flashsim： a simulator for NAND flash-based solid-state drives[A].1st International Conference on Advances in System Simulation, SIMUL 2009[C].Porto, Portugal,2009.125-131.