提升固態存儲設備讀取性能的方法

李明江，段星輝，陳 仁

(1.黔南民族師范學院 計算機與信息學院 人工智能與大數據應用技術研究所，貴州 都勻 558000；2.黔南民族師范學院 計算機與信息學院，貴州 都勻 558000；3.中科院上海技術物理研究所 中國科學院紅外探測與成像技術重點實驗室，上海 200083)

0 引 言

近年來，由于基于閃存的固態存儲設備具有速度快、延時低、功耗低、抗震、體積小[1]等優點，固態存儲設備在存儲領域中得到廣泛的使用。但閃存具有其自身的一些問題，比如寫前擦除、壽命有限、讀取次數有限、讀寫速度不一致等[2]。基于閃存的固態存儲設備通過閃存轉換層(flash translation layer，FTL)來管理閃存。FTL的主要作用是管理邏輯地址(LBA)到物理地址(PPA)的映射。基于不同粒度的映射，FTL有塊映射、頁映射以及混合映射等地址映射方式[3]，其中頁映射具有最好的讀寫性能，因此為主流固態存儲設備所使用。然而，基于頁映射的映射表很龐大，需要大容量的緩存來存放。然而在一些固態存儲設備中，出于成本和功耗考慮，沒有配備大容量的緩存存儲映射表，映射表只能部分存儲在有限的控制器SRAM上，其絕大部分則存儲在閃存上。有限的SRAM限制了無DRAM設備的讀取性能，尤其是隨機讀取性能，因為設備首先需要訪問閃存獲取映射關系，然后再根據該映射關系從閃存中讀取用戶數據。在有限的SRAM空間，如果能盡可能多緩存映射關系，則能減少對閃存的訪問，從而提升設備的讀取性能。這是包括本文在內的很多論文解決該問題的一個思路。本文提出的另一個想法是利用有限的SRAM資源，緩存盡可能多熱數據的映射關系，因為熱數據的訪問速度對用戶體驗有直接的影響，而冷數據的訪問速度則對用戶體驗沒有那么大的影響。

1 無大緩存存儲設備的主要FTL算法

對性能要求高的固態硬盤(如企業級固態硬盤)，一般都配有大容量的DRAM來存放映射表。對讀寫I/O來說，由于整個映射表都存儲在DRAM中，固件可以快速獲取讀寫所需的映射關系，讀取或者更新映射關系都很迅速(只需訪問DRAM)，因此讀寫性能很好。

如何在無DRAM的固態硬盤中實現基于頁映射的FTL，國內外有很多研究，最為經典的FTL算法是DFTL[4]，其它很多FTL算法都是在此基礎上衍生和改進的。

DFTL基本思想是把整個映射表按映射頁管理，所有映射頁都存儲在閃存上，映射頁按需加載到緩存(cached mapping table，CMT)中，而全局翻譯目錄(global translation directory，GTD)用以存儲這些映射頁在閃存中的物理地址，它常駐SRAM。對讀寫I/O來說，它首先在CMT中查找該邏輯頁的映射關系，如果命中緩存，則直接根據該映射關系讀取閃存獲得用戶數據；如果沒有命中緩存，則查找GTD，找到所需映射頁的物理地址，然后從閃存中讀取映射頁到緩存中，最后固件根據該映射關系獲得用戶數據。

DFTL的順序讀取性能很好，因為一個映射頁加載到緩存中后，對接下來的很多筆讀，都能發生緩存命中，無需訪問閃存便能獲得該邏輯地址對應的物理地址；但對隨機讀取來說，因為CMT大小有限，對每筆讀取來說，發生映射頁緩存命中概率很低，因此很多時候它都需要訪問兩次閃存才能最終獲得用戶數據，隨機讀取性能差。

為提高映射頁緩存的命中率，在DFTL的基礎上，文獻[5]提出LAST++，其思想是根據主機的讀寫負荷，對順序寫入的數據，采用塊映射，而對隨機寫入的數據，采用頁映射。這種方式能減小整個映射表大小，對同樣大小的映射頁緩存，緩存命中率會有一定的提升。但這種混合映射方式實現起來很復雜，因為要同時兼顧塊映射管理和頁映射管理。

文獻[6,7]提出的FTL算法，其基本思路相似，即在DFTL的基礎上，對順序寫入的，采用更粗的映射粒度，對隨機寫入的數據，采用更細的映射粒度。更粗的映射粒度能減小映射表的大小，提升映射頁的緩存命中率。但這些算法有個弊端，就是順序寫的數據中如果加入少量的隨機寫(這在實際使用場景中是經常發生的，比如順序寫的文件中加入文件元數據的寫入[6])，粗的映射粒度就不能使用，因此無法提升頁緩存命中率。其實，LAST++存在同樣的問題。

另外，這些FTL算法對熱冷數據無差別對待。其實，在有限的SRAM空間緩存冷數據的映射關系是沒有意義的，因為這些數據很少被用戶訪問，它們訪問速度的快慢對用戶體驗沒有大的差別。

2 本文工作

讀取速度的快慢，尤其是熱數據的讀取延時和性能，和用戶體驗息息相關。低延時和高速的讀取訪問能大大提升用戶體驗，反之亦然。為改善無DRAM大緩存的存儲設備的讀取延時和性能，本文調研了業界和學術界最新的設計方法(如第1節所述)，在他們工作的基礎上，本文創造性提出以下方法：

(1)用戶在實際使用固態存儲設備時，存在很多順序寫入以及大數據量的寫入[8]，這些數據寫入產生的映射具有邏輯地址和物理地址連續的特點。連續的映射關系很適合壓縮，本文通過壓縮連續映射關系以讓有限的緩存空間存儲更多的映射關系；

(2)用戶在實際使用存儲設備時，順序寫和隨機寫可能交錯寫入[9]，為保證順序寫入的數據在閃存物理空間連續(不被隨機寫打斷)，本文提出讓順序寫入的數據和隨機寫入的數據存儲在不同的閃存物理塊上。分離存儲保證更多的連續物理地址映射，從而有助于提升映射表的壓縮率；

(3)用戶在使用存儲設備時，雖然存儲設備上存儲了很多數據，但經常訪問的數據往往有限。因此，本文提出只緩存熱數據的映射表，從而在有限的映射緩存空間能存儲更多的有助于提升用戶體驗的映射關系；

(4)普通用戶在使用存儲設備時，設備很多時候都是空閑的，因此本文提出利用設備空閑時間預取和壓縮熱數據的映射表，達到提升熱數據訪問速度的目的。

在設計和實現以上算法的基礎上，本文還設計實驗比較了不同FTL算法之間的讀取性能差異，并對實驗結果做了理論分析。

3 算法設計

3.1 映射表壓縮

為減小映射表的大小，本文的思路是壓縮映射表，讓有限的映射表緩存能存儲盡可能多的映射關系，來達到提升映射表緩存命中率的目的。

注意到無論是在基準測試(benchmark tests)中，還是在實際用戶使用存儲設備過程中，都會有很多的順序寫入或者大數據量的寫入(比如視頻、圖像、大文件等)，這些數據的寫入，會產生很多的連續的物理地址。比如write(0,1024)(起始LBA為100，寫入1024個邏輯頁)寫入，產生表1所示的映射。

表1 傳統映射表示例

對這些邏輯地址和物理地址都連續映射，采用游程編碼的方式，把它們用另外一種形式表示，見表2。

表2 映射描述符表示例

把其中的條目稱為映射描述符，包括“起始LBA，起始PPA，連續長度”3個域。同樣的映射關系，用表1傳統的頁映射管理形式，它們需要4096字節來緩存，而采用游程編碼壓縮后，表2只需10字節就能表示同樣的映射關系，所需SRAM空間大大減小。

在DFTL的映射頁緩存(CMT)基礎上，所提算法加入映射描述符緩存(mapping descriptor cache，MDC)用以緩存游程編碼后的映射描述符。為減小查詢開銷和內存使用空間，MDC通常只有幾KB。在第4節實驗結果部分提供了不同MDC大小下的軟件查詢開銷。

當加入MDC緩存后，設備處理主機讀取命令步驟如下：

(1)FTL查找傳統的映射頁緩存(CMT)，看該LBA對應的映射頁是否在CMT，如果命中緩存，返回該LBA對應的物理地址，跳到(4)；否則，走到(2)；

(2)FTL查找新加的映射描述符緩存(MDC)，看該LBA是否落在其中某個映射描述符內，如果在，則返回該LBA對應的物理地址，跳到(4)；否則，走到(3)；

(3)查找全局翻譯目錄(GTD,即映射頁物理地址表)，找到LBA對應的映射頁的物理地址，然后讀取所需的映射頁到映射頁緩存，同時，FTL遍歷該映射頁以壓縮其中的連續映射關系，如滿足條件則新的映射描述符會被加入到MDC中。

(4)根據該LBA對應的物理地址讀取閃存獲得該用戶數據，返回給主機。

偽代碼如下：

輸入：LBA，邏輯地址

輸出：PPA，物理地址

if(LBA hit CMT)

{//LBA所對應的映射頁在映射頁緩存CMT中

return PPA from CMT;

}

else

{

if(LBA hits MDC)

{//LBA落在映射描述符緩存MDC中

PPA =(LBA-Start_LBA)+ Start_PPA

return PPA；

}

else

{//CMT和MDC都沒有命中

PPT_Index = LBA/PPT_SIZE;//獲得該LBA對應的映射頁編號；

PPT_PPA = GTD[PPT_Index]；//查找GTD獲得所需加載映射頁的物理地址；

根據物理地址PPT_PPA加載映射頁到映射頁緩存CMT;

遍歷映射頁看是否能加入到MDC;

return PPA;

}

}

3.2 順序寫入和隨機寫入數據分開存儲

對連續的寫入，或者大數據的寫入，會產生連續的地址映射，有利于映射數據的壓縮。但在實際用戶使用存儲設備的過程中，在連續數據寫入過程中會有隨機的寫入，如文件系統層在寫入大文件數據的時候，中間會寫入管理文件相關的元數據。隨機寫入會導致連續的地址映射中斷，不利于映射關系的壓縮。

舉例來說，兩個連續的寫write(0,64)和write(64,32)，寫入到的閃存空間起始物理地址為0，則一個映射描述符(0,0,96)可以描述兩個命令產生的映射關系。如果在兩個命令中加入了一個不連續的命令write(200,1)，則需要兩個映射描述符來描述之前兩個命令產生的映射關系，見表3。

表3 連續物理地址被中斷的例子

如果對加入到MDC的映射描述符有限制的話，比如連續長度需大于32，則表中第3條映射關系不會被緩存，導致更多的映射關系沒有被緩存，從而導致緩存命中率降低。

為避免隨機的寫入中斷順序寫的映射關系，本文提出把順序寫入的數據和隨機寫入的數據分開寫在不同的物理塊或者超級塊。以上面3個寫入命令為例，由于write(0,64)和write(64,32)是連續的寫入命令，因此它們會寫在起始物理位置為0的閃存空間(如圖1中的超級塊A)；而write(200,1)是隨機寫入，因此它的數據會被寫到另外的閃存空間，比如起始物理位置為10000的閃存空間(如圖1中的超級塊B)。

圖1 順序數據和隨機數據分開存儲示例

順序寫入的數據和隨機寫入的數據分開存儲讓連續的命令write(0,64)和write(64,32)具有連續的物理地址，它們的映射關系這樣就可以被一個映射描述符(0,0,96)描述，提升了映射表的壓縮率，有限的緩存空間MDC可以緩存更多的映射關系，映射緩存的命中率得到提升。

3.3 區分冷熱數據

盡管用戶的存儲設備上存儲了很多數據，但很多時候，用戶只會頻繁訪問其中的一部分數據，這部分數據被稱作熱數據，相反，那些不經常訪問的數據則稱為冷數據。要提升用戶體驗，重在提升熱數據的訪問速度。

FTL對整個用戶存儲空間進行劃分，比如每1 GB為一區間，128 GB的存儲設備則被劃分成128個用戶區間，見表4。對每個用戶區間，FTL維護它的讀取次數：如某個LBA被主機讀取，其所在的用戶區間的讀次數則加1。

表4 用戶區間讀計數表例子

比如，在表4的基礎上，read(0,10)命令處理完后，其所在的用戶區間讀次數應該加10，即用戶區間(0，1 GB)的讀次數變成143。

FTL可以把讀次數最多的若干個用戶區間定義為熱數據，其它用戶區間則定義為冷數據。由于映射關系的緩存空間有限，FTL沒有必要緩存冷數據的映射關系，而是在有限的空間緩存更多的熱數據對應的映射關系，有助于提升熱數據的緩存命中率，從而提升用戶體驗。

3.4 更新映射描述符緩存(MDC)

有兩個時機映射頁會被壓縮成映射描述符加入到映射描述符緩存MDC：一是當讀取某個LBA發生映射頁緩存不命中的時候，FTL會去閃存上加載該映射頁到緩存CMT，在這個時候，FTL會去遍歷該映射頁，如果有很多的連續物理地址存在該映射頁，則它們會被壓縮成映射描述符而被加入到MDC；另外一個時機是存儲設備空閑的時候，FTL會把所有熱數據對應的映射頁讀取上來，然后遍歷這些映射頁，壓縮那些連續的映射關系，壓縮成的映射描述符可能被加入到映射描述符緩存中。

映射緩存中緩存的映射關系越多，則映射緩存命中率越高，系統讀取性能越好。為在有限的緩存空間緩存盡可能多的映射關系，該算法制定如下更新描述符緩存的規則：

FTL只會把熱數據對應的映射關系更新到映射描述符緩存；

對加入到映射描述符緩存中的映射描述符做限制，即只有物理地址連續個數超過某個閾值(如32個)的描述符才能加入到緩存中；

當MDC緩存滿了的時候，當需要添加新的映射描述符，如果待加入的描述符其連續的物理地址長度大于緩存中最短的那個描述符，則取代該描述符加入緩存中，否則放棄添加新的映射描述符到緩存。

這些規則的定義，能保證有限的MDC空間緩存盡可能多的映射關系，尤其是熱數據的映射關系。

4 實驗結果

本文使用FlashSim[10]仿真軟件來評估該算法性能。FlashSim是一款開源的SSD模擬器，它是一款事件驅動的、模塊化的基于C++的模擬器，內置了多種FTL策略，能夠提供響應時間、能耗的模擬及許多額外的統計信息。在FlashSim內置的DFTL算法的基礎上，實現映射壓縮、順序和隨機數據分開存儲、區分冷熱數據和后臺加載熱數據映射表并進行壓縮。

實驗使用FlashSim模擬128 GB存儲設備，該存儲設備有4個32 GB的Flash組成，每個通道上掛一個Die。具體參數見表5。

表5 存儲設備配置

映射頁緩存CMT大小為256 KB，可以緩存64個4 KB大小的映射頁；映射描述符緩存MDC大小為2 KB，由于每一個描述符大小為10字節，因此可以緩存大概200個映射描述符。在處理每筆讀取命令的過程中，需要查找映射描述符，在本實驗平臺上實測軟件查詢2 KB的MDC需要額外多出1 μs，因此MDC不能配置太大，否則查詢成本太高。如20 KB的MDC查詢時間為10 μs，意味著讀取的延時增加10 μs，系統讀取性能大大減小。圖2給出了不同MDC大小配置下的MDC查詢時間。

圖2 MDC查詢時間和其緩存大小的關系

實驗設計1：目的是測試壓縮映射表對數據讀取性能的提升。

測試方法：

(1)順序填滿整個盤；

(2)不同LBA范圍內測試數據的讀取性能。

結果(如圖3所示)分析：由于DFTL只用256 KB CMT緩存映射表，因此映射表緩存命中率隨著LBA測試范圍擴大，命中率逐漸下降，具體見表6。

圖3 本文算法和傳統FTL隨機讀取性能對比

表6 DFTL映射緩存命中率和讀取性能

由于本文算法采用了映射表壓縮，并使用MDC來緩存壓縮后的映射描述符。2 KB的MDC能緩存200個映射描述符，每個映射描述符可以描述256 MB(超級塊的大小，一個超級塊需要一個描述符)，因此50 GB LBA范圍內的映射關系可以被存儲在MDC中。因此，如果LBA讀取范圍在50 GB之內，則發生100%的映射緩存命中，讀取數據的時候無需從閃存上讀取映射關系。從實驗數據可以看出，50 GB LBA測試范圍內，4 KB平均讀取性能約為70 K IOPS，平均延時為68 μs，但從50 G LBA范圍開始，隨著LBA測試范圍加大，其性能逐漸變差，命令延時也加大，因為緩存命中率慢慢變低，需要更大概率從閃存上讀取映射關系。

由于MDC緩存的映射描述符有限，不能覆蓋整個用戶空間的數據，這也是本文提出只緩存熱數據映射關系的原因。在本實驗中，如果用戶熱數據在50 GB(128 GB中有50 GB數據被經常訪問)之內，則在讀取這些熱數據的時候，能發生100%的MDC緩存命中，從而加快熱數據訪問的性能和延時，從而改善用戶體驗。

注意到LAST++在順序填充滿盤的情況下，它能做到全盤范圍內保持一個高的隨機讀取性能，那是因為完全順序寫入時，LAST++采用的是塊映射，映射表相對頁映射來說大大減小，因此其所有映射關系可以緩存在SRAM。

實驗設計2：目的是測試順序寫入的數據中夾雜著少量的隨機寫，然后測試讀取性能。

測試方法：

(1)順序填滿整個盤，但在填盤的過程中，每寫1 MB的用戶數據，插入一個隨機寫的數據，用以模擬平時文件的寫入(文件系統在寫入用戶數據的同時也會寫入文件元數據)；

(2)不同LBA范圍內測試數據的讀取性能，比較順序寫入的數據和隨機寫入的數據分開存儲和統一存儲兩者對隨機讀取性能影響，以及和傳統DFTL，LAST++性能的對比。

結果分析：從實驗結果(如圖4所示)可以看出，如果順序寫入的大數據和隨機寫入的小數據混合存儲，其4 KB讀取性能和DFTL(沒有映射表數據的壓縮)差不多。這是因為，每寫入1 MB的數據，則需要一個映射描述符。由于MDC只能緩存200個左右的映射描述符，也就是說只能緩存200 MB左右的用戶數據的映射關系(見表7)，和CMT緩存映射關系差不多，因此在性能和延時上，混合存儲和DFTL性能差不多，都遠遠不及分開存儲的性能。

圖4 混合存儲和分開存儲性能對比

表7 混合存儲和分開存儲覆蓋的LBA范圍

結果還發現，在實驗1順序填盤情況下表現優異的LAST++，在碰到這種隨機和順序混合填盤的情況下，其性能退化成DFTL性能。LAST++的基本思想是對順序寫入采用塊映射，對隨機寫入采用頁映射。在此測試中，隨機寫入打斷了順序寫入，導致順序寫入量不足一個閃存塊，無法實現塊映射，演變成純粹的頁映射，因此無法減小映射關系，最后導致其讀取性能跟DFTL性能一樣。

5 結束語

針對不帶大緩存的固態存儲設備讀取性能和延時差的問題，本文采用游程編碼的方式壓縮和緩存熱數據的映射表、順序寫入的數據和隨機寫入的數據分開存儲、大數據寫入和小數據寫入分開存儲等方法，提升讀取命令的映射緩存命中率，來提升用戶訪問熱數據的讀取性能，從而改善用戶在使用移動存儲(比如手機、平板上使用的存儲設備)或不帶DRAM固態硬盤時的使用體驗。對企業級的固態存儲設備，雖然一般都配有大容量的DRAM作為緩存，但隨著存儲設備容量越來越大，還是存在緩存不能容納整個設備映射表的問題，因此，本文提出的算法也適用于這些企業級應用的固態存儲設備。