WAPFTL:支持預(yù)測機制的負載自適應(yīng)閃存轉(zhuǎn)換層算法

謝徐超，宋振龍，李 瓊，魏登萍，方 健，肖立權(quán)

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

1 引言

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

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

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

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

2 WAPFTL算法設(shè)計

2.1 WAPFTL整體設(shè)計

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

Figure 1 Architecture of WAPFTL圖1 WAPFTL結(jié)構(gòu)

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

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

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

2.2 地址轉(zhuǎn)換

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

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

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

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

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

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

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

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

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

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

2.4 預(yù)測及自適應(yīng)

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

Figure 3 State transitions of workloads and the process of threshold in WAPFTL圖3 WAPFTL中負載特性狀態(tài)轉(zhuǎn)換及threshold值變化規(guī)律

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

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

3 性能分析與評價

3.1 實驗環(huán)境

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

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

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

Table 2 Workload characteristics表2 負載特點 %

3.2 系統(tǒng)響應(yīng)時間和命中率

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

Figure 4 Average system response time 圖4 系統(tǒng)平均響應(yīng)時間

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

Figure 5 Cache hit ratio圖5 命中率

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

Figure 6 Number of block erasures in SPC1圖6 SPC1中塊擦除次數(shù)

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

Figure 7 Number of read/write operations圖7 讀寫次數(shù)

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

4 結(jié)束語

本文面向大容量SSD在高性能計算及企業(yè)級服務(wù)器中應(yīng)用的特點，提出了一種閃存轉(zhuǎn)換層中基于頁映射機制的自適應(yīng)地址映射算法WAPFTL。WAPFTL高效協(xié)同利用負載的時間局部性和空間局部性，在地址轉(zhuǎn)換處理過程中通過預(yù)測當(dāng)前負載請求特性，實現(xiàn)了對SRAM中映射信息緩存策略的動態(tài)調(diào)整。仿真與測試結(jié)果表明，WAPFTL算法能夠提高SRAM中地址映射信息的命中率，減少因地址映射而引起的額外讀寫操作；同時，WAPFTL有效地減少了垃圾回收次數(shù)，提高了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.