WAPFTL:支持預測機制的負載自適應閃存轉換層算法

謝徐超，宋振龍，李 瓊，魏登萍，方 健，肖立權

(國防科學技術大學計算機學院，湖南 長沙 410073)

1 引言

基于NAND Flash的固態盤SSD(Solid State Drive)具有低延遲、低功耗、高可靠性等優點，可以有效地提升存儲系統的性能，在企業級和消費級存儲領域得到廣泛應用。在高性能計算領域，固態盤已成為用來提高系統IO性能的主要手段之一，例如位居2013年6月TOP 500榜首的“天河二號”計算機系統就采用了PCIe接口的SSD作為數據加速層，大幅提高了全系統的IO性能。而NAND Flash的寫前擦除、擦除次數有限等固有特性使得基于NAND Flash的寫性能相對其讀性能要差，整體性能還有待提高。

作為固態盤控制器的核心，閃存轉換層FTL(Flash Translation Layer)可以將底層NAND Flash陣列封裝成一個和硬盤一樣的塊設備，隱藏擦除操作，保證現有文件系統對SSD的兼容性。FTL的主要功能包括地址映射、垃圾回收、磨損均衡等。地址映射將來自文件系統的讀寫請求的邏輯地址轉換成固態盤內的物理地址，保證了異地更新策略的實現，是FTL中最重要的一項功能。當垃圾回收被觸發時，對被擦除的數據塊中有效頁回收，然后將該數據塊進行擦除。由于需要涉及對其中有效頁的遷移和對塊的擦除操作，對數據塊進行垃圾回收是一個非常耗時的操作。

FTL中地址映射方式主要有頁映射、塊映射和混合映射等[1～4]。其中頁映射機制以頁為基本映射粒度，是最靈活、性能最優的地址映射方式。但是，隨著固態盤容量的增加，地址映射過程中對頁映射表的緩存需要更大的SRAM存儲空間，造成成本增加?；陧撚成錂C制的DFTL[5]算法將經常用到的部分映射關系存放到SRAM中，而整個映射表保存在Flash中，但是SRAM中部分緩存的地址映射信息很大程度上依賴于負載的時間局部性。另外，因地址映射信息在SRAM中未命中而引起的額外的讀寫操作，及其可能觸發的垃圾回收操作等所產生的延遲對整個存儲系統性能的影響是巨大的。因此，如何選擇性地緩存地址映射信息，提高命中率，對于提升SSD的性能至關重要。

為了有效利用緩存空間對地址映射信息進行緩存，減少FTL對SRAM存儲空間的依賴，我們提出了一種新的地址映射算法。該算法在有效協同利用訪問請求的時間局部性和空間局部性的同時，能根據負載的數據請求特點動態預測請求的特點，并動態調整地址映射信息的緩存管理策略，提高命中率，有效改善系統的寫性能。

2 WAPFTL算法設計

2.1 WAPFTL整體設計

WAPFTL的整體結構如圖1所示，NAND Flash在邏輯上被劃分為數據塊(Data Blocks)和轉換塊(Translation Block)。數據塊占據了絕大部分Flash空間，主要用來存儲數據，轉換塊只占據小部分Flash空間，用來存儲數據塊中的所有邏輯頁地址到物理頁地址之間的地址映射關系。

Figure 1 Architecture of WAPFTL圖1 WAPFTL結構

如圖1所示，WAPFTL在固態盤SRAM中建立順序緩存映射表SCMT(Sequential Cached Mapping Table)、緩存分裂表CST(Cached Split Table)、緩存映射表CMT(Cached Mapping Table)和全局轉換目錄GTD(Global Translation Directory)，并預先設置一個閾值threshold。其中SCMT、CST和CMT協同記錄SRAM中處于活躍狀態的頁映射關系，全局轉換目錄GTD用來記錄所有邏輯頁對應地址映射信息在Flash中存放的物理頁號。threshold的大小決定一個請求的地址映射信息在SRAM中緩存的方式，通過對threshold的動態調整，可以使整個算法針對當前負載請求的特點進行自適應調整，有效提高SRAM中映射信息的命中率。

SCMT和CST有三個表項：起始邏輯頁號LPN、起始物理頁號PPN和長度SIZE，其中長度SIZE指明了該映射關系中以該邏輯頁號為起始頁的一組起始邏輯頁號和起始物理頁號都連續的頁的數量。SCMT和CST中SIZE的大小表示該映射關系的映射范圍，但是其最大值不會超過一個塊中所擁有頁的總數量；在WAPFTL中，針對當前固態盤及其所用NAND Flash的規格，為保證足夠的尋址空間，我們將LPN和PPN分別設置為4 B，將SIZE設置為2 B，因此，在SCMT和CST中一個地址映射信息所占用的空間為10個字節大小，而CMT中只用8個字節。

SCMT和CMT是用于記錄SRAM中頁映射信息最主要的數據結構。在高性能計算及企業級服務器中，有順序寫請求，也有較小的隨機請求，CMT主要是用于緩存那些物理地址不連續的隨機請求的地址映射信息。對于邏輯頁號連續的讀請求，在當前NAND Flash中，其數據所在的物理頁的頁號并不一定是連續的。因此，讀請求從轉換塊中的某個轉換頁中一次只能讀出一個邏輯頁號對應的映射信息，當讀失效時，SCMT中的SIZE并不能發揮其效果。因此，在這些情況下，設置SIZE造成了SRAM中存儲空間的浪費。CMT中沒有設置SIZE域，其實質是SIZE=1的SCMT，但是可以在隨機請求和讀請求密集的負載條件下更有效地利用SRAM空間。緩存分裂表CST主要用于記錄緩存映射表中某些頁映射關系由于部分更新分裂而形成的子頁映射關系。CST在保證不破壞根據時間局部性原理而組織的SCMT的內部邏輯結構的前提下，更有效地利用IO請求的空間局部性原理。

2.2 地址轉換

WAPFTL接收來自文件系統的IO請求，IO請求所攜帶的信息包括該IO請求的請求類型(讀/寫)、起始邏輯頁號LPN、請求的長度SIZE頁。

WAPFTL首先檢查當前IO請求的起始邏輯頁在SCMT或CST中的命中情況，即判斷該請求的起始邏輯頁號是否在SCMT或CST中某個地址映射關系所表示的區間內，可以得到命中和未命中兩種結果。對命中的結果，通過判斷該命中的地址映射信息表示的范圍是否包含此IO請求的所有邏輯頁，可得到完全命中或者部分命中兩種結果。假設當前IO請求為寫請求，請求邏輯地址為LPN，請求長度為SIZE頁，SCMT中被命中的映射關系為(SCMTLPN,SCMTPPN,SCMTSIZE)，根據請求的SIZE以及SCMT和CST中命中的映射串信息，判斷該請求的命中類型及相應操作的過程為：

(1)完全命中：該地址映射串包含了所有此IO請求需要的地址映射信息。生成兩個長度不小于0的額外的子映射關系(SCMTLPN,SCMTPPN,LPN-SCMTSIZE)和(LPN+SIZE,SCMTPPN+LPN+SIZE-SCMTLPN,SCMTLPN+SCMTSIZE-LPN-SIZE)。對新生成的兩個子映射信息，分別比較它們的長度與當前threshold的大小，若大于threshold，則將其放入CST中緩存，若小于threshold，則將該映射信息中包含的多個映射關系分別緩存到CMT中。

(2)部分命中：該地址映射串中只包含了此IO請求需要的部分地址映射信息。將當前IO請求根據緩存映射表映射關系表項中滿足命中的范圍分裂為兩個子請求REQ1= (LPN,SIZE1)和REQ2= (LPN+SIZE1,SIZE-SIZE1)，其中，SIZE1 =SCMTLPN+SCMTSIZE-LPN。REQ1為在該映射關系中能夠滿足的子請求，REQ2為不能夠滿足的子請求，SIZE1為映射關系中滿足命中部分的長度。同時，該過程中還會生成新的子映射關系(SCMTLPN,SCMTPPN,SCMTSIZE-SIZE1)。對于新生成的子映射關系，其處理方式與命中情況相同。

若該IO請求的起始邏輯頁號未在SCMT和CST中命中，則繼續到CMT中查找。與SCMT和CST中的命中情況不同，在CMT中命中的映射關系，一次只能得到該IO請求需要的所有映射信息中的一條，而在SCMT和CST中則可以一次得到多條。若該IO請求的起始邏輯頁號在CMT中也沒有命中，則表示該請求所需要的地址映射信息并沒有緩存在SRAM中，需要通過GTD訪問存有該信息的轉換塊，從其相應的頁中取出所需要的映射關系，并根據當前緩存管理策略放入SRAM相應的表中緩存。在WAPFTL中，每個表都采用Segment LRU[3]進行組織。

2.3 地址映射信息的緩存策略

對于寫請求，當SSD中有新的數據寫入Flash時，FTL會在當前所有的空閑塊中選擇一塊磨損次數最少的數據塊作為當前數據塊(Current Block)，用來存儲最近被寫入的數據。對于SIZE大于1的寫請求，其寫入該當前塊中頁的數量為SIZE，并且寫入Flash后的物理地址也是連續的。因此，對于順序寫請求，我們可以利用這一特性在一個地址映射信息中記錄多條頁地址映射關系，如圖2所示。

Figure 2 Cache strategy of address mappings in WAPFTL圖2 WAPFTL地址映射信息緩存策略

由于SSD所采取的異地更新策略，在當前寫請求完成對數據的存儲以后，原有的地址映射關系發生改變，FTL需要作廢原有映射信息并記錄最新的地址映射關系。WAPFTL比較當前寫請求的SIZE與當前threshold，如果SIZE大于threshold，則表示在當前負載情況下，WAPFTL的決策是及該地址映射信息緩存到SCMT中，WAPFTL在SCMT中緩存一個映射串，記錄此次請求將該IO請求的所有映射關系。如果SIZE小于threshold，則表示在當前負載情況下，WAPFTL的決策是將每條地址映射關系單獨緩存到CMT中。

對于讀請求，由于SSD在完成讀請求的過程中并不會發生對數據的更新操作，原有的地址映射關系也不會發生改變，因此，如果讀請求的邏輯頁號可以在SRAM任何一個表中命中，則無需處理。當所需地址映射關系在SRAM中未命中時，WAPFTL將所需映射關系從轉換塊中相應的轉換頁讀入SRAM，并緩存到CMT中。顯然，只有當threshold的值為1時，因讀失效而從Flash的轉換塊中讀入SRAM的映射關系才可能緩存到SCMT中。

2.4 預測及自適應

WAPFTL統計并分析在一段時間間隔內負載的請求類型與請求的大小，對以后的IO請求可能具有的特點進行預測，以調整當前SRAM對地址映射信息的緩存管理策略。WAPFTL通過改變當前threshold的值，動態調整SRAM中地址映射信息的緩存方式，以便在當前負載下可以盡可能地緩存更多的頁映射關系，擴大SRAM地址映射范圍，提高命中率，減少SRAM與Flash之間因為地址映射而造成的額外讀寫開銷。在WAPFTL中，threshold值的變化規律如圖3所示。

Figure 3 State transitions of workloads and the process of threshold in WAPFTL圖3 WAPFTL中負載特性狀態轉換及threshold值變化規律

WAPFTL用“隨機寫”、“順序寫”和“讀”三個狀態表示當前負載請求的特點。對于所取時間間隔內，如果所有的請求中寫請求比例超過40%，并且寫請求所請求的頁數大于當前threshold值的比例超過25%，則表明相對于SRAM中所緩存的映射關系來說，當前負載的順序寫請求較多，WAPFTL認為該負載當前的特點為“順序寫”，并執行threshold++。這是因為對于大量的寫請求，如果threshold值較低，必然造成所有由于寫操作而新形成的映射關系都直接存放到SCMT中，當SCMT內無空閑表項時，會造成SCMT中大量的具有較大SIZE值的映射信息寫回Flash，而該映射關系所表示的映射范圍直接影響WAPFTL中SRAM的命中率。WAPFTL通過執行threshold++，讓SIZE值較小的映射關系緩存到CMT中，SCMT中SIZE較大的映射關系保證了SCMT中映射信息表示的邏輯范圍。若當前負載請求的狀態為“隨機寫”且threshold值仍大于1，WAPFTL則執行threshold--，以保證SRAM中SCMT空間的有效利用。

如果該時間間隔內所有的請求中讀請求的數量占據了多數，WAPFTL則標記當前負載狀態為“讀”。如果threshold值仍大于1，WAPFTL執行threshold--。由于邏輯頁號連續的頁，其當前在Flash中所存放的頁的物理頁號不一定是連續的，對于讀請求所需的地址映射信息未在SRAM中命中時，只能一條一條地從Flash中取出。但是，當讀請求較密集時，就會造成CMT映射關系與Flash轉換塊之間頻繁的數據交換。為了避免SCMT不能發揮作用，當WAPFTL檢測到當前負載狀態為“讀”時，就執行threshold--，直至threshold值為1。

3 性能分析與評價

3.1 實驗環境

為了驗證WAPFTL的性能，我們擴展了SSD仿真環境Flashsim[7]，并在Flashsim中實現了頁映射算法、FAST[8]、DFTL和WAPFTL算法。SSD的詳細配置如表1所示。其中SRAM空間設置為64 KB，并假設整個SRAM空間足以緩存頁映射算法和FAST的所有映射表。

Table 1 Specification of SSD configuration表1 SSD配置說明

實驗應用的trace文件中，SPC1和SPC2來自于SPC[9]，MSRC1和MSRC2是由MSRCambridge所采集[10]。這些用來驅動Flashsim的trace的特點如表2所示。

Table 2 Workload characteristics表2 負載特點 %

3.2 系統響應時間和命中率

通過運行不同的trace，測試WAPFTL對SSD寫性能的提高，在實驗中我們以頁映射算法為性能評測的基準(Baseline)。平均響應時間可以較好地衡量整個FTL的性能，其綜合反映了FTL中地址映射、垃圾回收和磨損均衡算法所需的開銷。如圖4所示，WAPFTL平均響應時間低于DFTL，對系統性能有非常明顯的提高。特別對于順序寫請求比例較大的MSRC1和MSRC2，已接近于理想狀態下的響應時間。

Figure 4 Average system response time 圖4 系統平均響應時間

為了評價WAPFTL中地址映射信息緩存方法的效率，我們對SRAM中地址映射關系的命中率和SRAM與Flash之間讀寫次數進行分析。如圖5所示，WAPFTL中對映射關系的緩存可以有效提高SRAM中各類負載地址映射信息的命中率。

Figure 5 Cache hit ratio圖5 命中率

在以頁映射算法為基準時，對于DFTL和WAPFTL，額外的讀寫操作是由于SRAM中地址映射信息未命中而引起的。對于FAST，則是由于大量的完全合并而引起的垃圾回收操作而引起，如圖6所示為四種算法在SPC1負載下的垃圾回收次數，FAST算法的垃圾回收操作嚴重影響了其性能。

Figure 6 Number of block erasures in SPC1圖6 SPC1中塊擦除次數

如圖7所示，在負載一定的情況下，不同地址映射算法會產生不同的讀寫次數。

Figure 7 Number of read/write operations圖7 讀寫次數

WAPFTL利用負載的當前特性進行預測并自適應調整緩存策略，保證盡可能多的地址映射信息緩存在SRAM中，有效減少了因為地址映射在SRAM中未命中而引起的SRAM與Flash之間額外的讀寫請求次數，從而減少對Flash的總的讀寫次數，提高SSD整體性能。

4 結束語

本文面向大容量SSD在高性能計算及企業級服務器中應用的特點，提出了一種閃存轉換層中基于頁映射機制的自適應地址映射算法WAPFTL。WAPFTL高效協同利用負載的時間局部性和空間局部性，在地址轉換處理過程中通過預測當前負載請求特性，實現了對SRAM中映射信息緩存策略的動態調整。仿真與測試結果表明，WAPFTL算法能夠提高SRAM中地址映射信息的命中率，減少因地址映射而引起的額外讀寫操作；同時，WAPFTL有效地減少了垃圾回收次數，提高了SSD整體性能。

[1] Chung T S, Park D J, Park S, et al. A survey of flash translation layer[J]. Journal of Systems Architecture, 2009, 55(5):332-343.

[2] Lim S P, Lee S W, Moon B. Faster FTL for enterprise-class flash memory SSDs[C]∥Proc of 2010 IEEE International Workshop on Storage Network Architecture and Parallel I/Os (SNAPI), 2010:3-12.

[3] Wei Q, Gong B, Pathak S, et al. WAFTL:A workload adaptive flash translation layer with data partition[C]∥Proc of 2011 IEEE 27th Symposium on Mass Storage Systems and Technologies (MSST), 2011:1-12.

[4] Wang C, Wong W F. ADAPT:Efficient workload-sensitive flash management based on adaptation, prediction and aggre-

gation[C]∥Mass Storage Systems and Technologies (MSST),2012 IEEE 28th Symposium on. IEEE,2012:1-12.

[5] Gupta A, Kim Y, Urgaonkar B. DFTL:A flash translation layer employing demand-based selective caching of page-level address mappings[C]∥Proc of the 14th International Conference on Architectural Support for Programming Languages and Operating System,2009:229-240.

[6] Karedla R, Love J S, Wherry B G. Caching strategies to improve disk system performance[J]. Computer, 1994, 27(3):38-46.

[7] Kim Y, Tauras B, Gupta A, et al. Flashsim:A simulator for NAND flash-based solid-state drives[C]∥Proc of the First IEEE International Conference on Advances in System Simulation, 2009:125-131.

[8] Lee S W, Park D J, Chung T S, et al. FAST:A log-buffer based FTL scheme with fully associative sector translation[J]. ACM Transations on Embedded Computing Systems, 2007,6(3):1-18.

[9] Storage performance council (SPC) storage traces[EB/OL].[2007-06-01]. http://traces.cs.umass.edu/index.php/Storage/Storage.

[10] Narayanan D, Donnelly A, Rowstron A. Write off-loading:Practical power management for enterprise storage[J]. ACM Transactions on Storage (TOS), 2008, 4(3):10.