主機和設(shè)備協(xié)作方式提升固態(tài)硬盤隨機讀取性能

李明江 陳 仁

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

0 引 言

近年來，由于基于閃存(主要是NAND Flash)的固態(tài)存儲設(shè)備具有速度快、延時低、功耗低、抗震、體積小[1]等優(yōu)點，無論是在消費領(lǐng)域，企業(yè)數(shù)據(jù)中心，或是在移動領(lǐng)域(如eMMC、UFS等)都得到了廣泛的使用。在存儲設(shè)備內(nèi)部，需要維護一張邏輯地址到閃存物理地址的映射表，該表大小約為存儲容量的千分之一。過去，固態(tài)存儲設(shè)備都配備相應(yīng)大小的DRAM來存放該映射表，設(shè)備在處理主機讀取命令時，通過訪問DRAM快速獲取該數(shù)據(jù)塊在閃存的物理位置，從而能夠快速獲取用戶數(shù)據(jù)。但在一些固態(tài)存儲設(shè)備(如消費級固態(tài)硬盤、移動存儲設(shè)備)中，出于成本和功耗考慮，沒有配備DRAM存儲映射表，有限的SRAM限制了無DRAM設(shè)備的隨機讀取性能，因為設(shè)備首先需要訪問閃存以獲取映射關(guān)系，然后再根據(jù)該映射關(guān)系從閃存中讀取用戶數(shù)據(jù)。本文注意到現(xiàn)在的主機端DRAM資源充足，因此提出把設(shè)備端的映射表存放到主機端，采用主機和設(shè)備協(xié)作的方式，實現(xiàn)一種快速隨機讀取算法，來提升主機隨機讀取設(shè)備的性能。

1 FTL

SSD的存儲介質(zhì)一般是閃存，閃存有其自身的一些特點，如寫前擦除、擦除/寫入次數(shù)有限、讀取次數(shù)有限等。寫前擦除特性不允許數(shù)據(jù)覆蓋更新，當一個邏輯頁面被重寫時，設(shè)備會分配一個新的可用閃存頁，將新的數(shù)據(jù)寫入其中，并通過FTL(Flash Translation Layer)軟件層來維護邏輯頁到閃存頁的映射關(guān)系。管理邏輯地址到物理地址(Logical address To Physical address, L2P)的映射是FTL最基本的功能。除此之外，F(xiàn)TL還針對閃存特性，實現(xiàn)了其他算法，如垃圾回收(Garbage Collection)、磨損均衡(Wear Leveling)等算法。

圖1 FTL在固態(tài)存儲設(shè)備中的位置和作用

在存儲設(shè)備內(nèi)部，F(xiàn)TL起著承上啟下的作用，其處理來自主機的讀寫請求，然后把這些讀寫請求轉(zhuǎn)換成對閃存的訪問請求。另外FTL實現(xiàn)了一些和閃存特性相關(guān)的算法，諸如垃圾回收、磨損均衡、讀干擾處理、數(shù)據(jù)保持處理等算法，來克服閃存的一些特性或者說是缺點。FTL算法的好壞直接影響著固態(tài)存儲設(shè)備的性能、可靠性等關(guān)鍵指標。

FTL最原始和最基本的作用是管理邏輯地址(Logical Block Address，LBA)到物理地址(Physical Page Address，PPA)的映射，映射方案有塊映射(Block Mapping)、頁映射(Page Mapping)和混合映射(Hybrid Mapping)。塊映射的優(yōu)點是映射表小，占用存儲設(shè)備存儲資源(RAM)少，但其最大缺點是隨機寫入性能差；頁映射的優(yōu)點是性能好，缺點是映射表龐大，需占用很多RAM(一般為存儲容量的千分之一，即1 TB的存儲設(shè)備需要1 GB的內(nèi)存來存放映射表)。混合映射則是介于兩者之間的一種映射算法，典型的混合映射算法有BAST[2]、FAST[3]、LAST[4]、SuperBlock FTL[5]等。由于頁映射性能好的優(yōu)點，現(xiàn)在業(yè)界主流固態(tài)硬盤的映射算法采用頁映射方案。

2 DFTL

基于頁映射的FTL具有好的讀寫性能，但是其映射表龐大，對性能要求高的固態(tài)硬盤，一般都配有大容量的DRAM來存放映射表。對讀寫I/O來說，由于整個映射表都存儲在DRAM中，固件可以快速地獲取讀寫所需的映射關(guān)系，讀取或者更新映射關(guān)系都很迅速(只需訪問DRAM)，因此其讀寫性能很好。

然而在一些對成本或功耗很敏感的固態(tài)硬盤中，存儲設(shè)備沒有DRAM，只配有少量的SRAM。如何在無DRAM的固態(tài)硬盤中實現(xiàn)頁映射的FTL，國內(nèi)外有很多研究。

Gupta等[6]注意到主機訪問設(shè)備的時間局部性(temporal locality)，提出了DFTL。其基本思想是把整個映射表按頁管理，全局翻譯目錄(Global Translation Directory, GTD)用以存儲這些映射頁在閃存中的物理地址，而映射頁按需加載到緩存中(Cached Mapping Table, CMT)。對讀寫I/O來說，它首先在CMT中查找映射關(guān)系，如果命中緩存，則直接根據(jù)該映射關(guān)系讀取閃存獲得用戶數(shù)據(jù)；如果沒有命中緩存，則查找GTD，找到所需映射頁的物理地址，然后從閃存中讀取映射頁到緩存中，最后固件根據(jù)該映射關(guān)系獲得用戶數(shù)據(jù)。

DFTL的順序讀取性能很好，因為一個映射頁加載到緩存中后，對接下來的很多筆讀取，都能發(fā)生緩存命中，無須訪問閃存便能獲得該邏輯地址對應(yīng)的物理地址。但對隨機讀取來說，因為頁緩存大小有限，對每筆讀取來說，發(fā)生映射頁緩存的概率很小，因此很多時候它都需要訪問兩次閃存才能最終獲得用戶數(shù)據(jù)。舉例來說，一個128 GB的固態(tài)硬盤，整個映射表大小為128 MB，由于SRAM大小受限，映射頁緩存大小可能只有512 KB，因此發(fā)生頁映射緩存命中的概率不到1%，意味著99%的讀命令需要訪問兩次閃存才能獲得數(shù)據(jù)。

為在有限的頁緩存條件下提高緩存的命中率，在DFTL的基礎(chǔ)上，Wei等[7]提出WAFTL,其思想是根據(jù)主機的讀寫負荷，對順序?qū)懭氲臄?shù)據(jù)，采用塊映射，而對隨機寫入的數(shù)據(jù)，采用頁映射。這種方式能減小整個映射表大小，對同樣大小的映射頁緩存，緩存命中率會有一定的提升。

DFTL利用了主機訪問設(shè)備的時間局部性，Xu等[8]同時注意到主機訪問設(shè)備的空間局部性，提出了CAST FTL，其基本思想是壓縮順序?qū)懭氲臄?shù)據(jù)的映射表，達到減小映射表大小的目的，從而提升頁映射緩存命中率。

WAFTL和CAST對順序?qū)懭氲臄?shù)據(jù)，能提升讀取速度，但是如果數(shù)據(jù)本來就是隨機寫入的，則隨機性能并不能得到提升。

無論是DFTL還是CAST和WAFTL，其讀取性能，尤其是隨機讀取性能，都不如帶DRAM 的固態(tài)硬盤，因為帶DRAM的固態(tài)硬盤只需訪問一次閃存便能獲得用戶數(shù)據(jù)，而不帶DRAM的固態(tài)硬盤在大多數(shù)時候都是需要訪問兩次閃存的(第一次訪問閃存獲得映射關(guān)系，第二次讀取閃存獲得用戶數(shù)據(jù))。

3 新的固態(tài)存儲架構(gòu)

自帶DRAM的存儲設(shè)備的性能好，但是成本和功耗高；不帶DRAM的存儲設(shè)備的成本和功耗低，但是性能不足。無論DFTL、WAFTL或CAST FTL，都沒有從根本上解決無DRAM固態(tài)硬盤隨機讀取性能差的問題。

本文注意到當前主流的主機設(shè)備DRAM豐富，無論是臺式機，還是移動設(shè)備，內(nèi)存資源充足，因此提出了一種新的映射表存儲架構(gòu)，如圖2所示。利用主機端的內(nèi)存資源，把映射關(guān)系存放到主機端，通過主機和設(shè)備協(xié)作的方式來提升不帶DRAM的存儲設(shè)備的隨機讀取性能，解決了存儲設(shè)備性能和成本、功耗之間的矛盾。

圖2 映射表存儲在主機端的存儲架構(gòu)

在這個架構(gòu)的基礎(chǔ)上，本文設(shè)計實現(xiàn)了一種改善隨機存儲性能的算法，稱為快速隨機讀取算法(Fast Random Read Algorithm，F(xiàn)RRA)。該算法只需更改主機端驅(qū)動和設(shè)備端固件算法，無須修改硬件，只需犧牲主機端部分內(nèi)存來換取快速的隨機讀取性能。

4 快速隨機讀取算法(FRRA)設(shè)計

4.1 相關(guān)定義

映射條目(Mapping Entry，ME)：每個LBA在閃存中的物理地址，一般為4字節(jié)大小。

映射頁(Mapping Page，MP)：若干個連續(xù)LBA在閃存中的物理地址集合，如連續(xù)1 024個LBA的映射關(guān)系集合，則映射頁大小為4 KB。它是設(shè)備管理映射數(shù)據(jù)的基本單位。本文假設(shè)映射頁大小為4 KB。

全局映射表(Global Mapping Table，GMT)：整個存儲設(shè)備邏輯空間的映射集合。如一個存儲設(shè)備容量為128 GB，一共128 GB/4 KB=32 M個LBA，每個LBA的物理地址為4字節(jié)，則全局映射表大小為32 M×4 B=128 MB。

主機端映射緩存空間(Host Mapping Cache,H_MC)：主機端分配的內(nèi)存空間，專門用以緩存映射頁。其大小取決于存儲設(shè)備大小和主機端可用的內(nèi)存空間。它可以存儲整個全局映射表，也可以緩存部分映射表。

主機端緩存映射頁(Host Caching Mapping Page,H_CMP)：緩存在主機端的映射頁。

主機端緩存映射位圖(Host Caching Mapping Bitmap,H_CMB)：主機端的一個位圖，每個LBA對應(yīng)一個比特，0表示該LBA的映射關(guān)系不在主機端映射緩存空間，或者在映射緩存空間的物理地址不是最新的；1表示該LBA的映射關(guān)系在主機端映射緩存空間并是最新的。比如存儲設(shè)備容量為128 GB，一共128 GB/4 KB=32 M個LBA，每個LBA占用1個比特，主機端總共需要32 MB/8=4 MB空間存儲該位圖。

主機端緩存映射頁有效數(shù)據(jù)表(Host Caching Mapping Page Valid Count，H_PVC)：主機端對每個緩存映射頁，都記錄了該映射頁的有效映射條目的個數(shù)。當某個映射頁加載到主機端映射緩存空間時，有效映射條目為1 024個，如果其中某個LBA之后被寫過，則有效條目減1。當某個緩存映射頁的有效條目數(shù)減少到一定閾值的時候，主機應(yīng)該從設(shè)備重新加載該緩存映射頁。

設(shè)備端緩存映射位圖(Device Caching Mapping Bitmap,D_CMB)：設(shè)備端的一個位圖，每個映射頁對應(yīng)一個比特，0表示該映射頁中至少有一個LBA對應(yīng)的物理地址是過時的，或者是無效的；1表示該映射頁中所有的LBA對應(yīng)的物理地址都是最新的。

2個定制的主機命令如下：

1)讀映射表命令(Read Mapping Table Command，RMTC)。主機通過RMTC加載映射表到主機映射緩存。RMTC中有兩個參數(shù)：起始LBA和結(jié)束LBA，LBA為1 024的整數(shù)倍。

2)快速隨機讀命令(Fast Random Read Command,FRRC)。主機通過FRRC命令讀取映射關(guān)系在主機映射緩存中的4 KB數(shù)據(jù)。FRRC命令中不僅帶有LBA的信息，同時還帶有該LBA對應(yīng)的物理地址信息。

4.2 初始化

設(shè)備上電時，主機通過RMTC命令加載全部或者部分映射頁到主機緩存空間。圖3為以128 GB存儲設(shè)備為例，主機加載全部128 MB映射關(guān)系到主機緩存空間。

圖3 用RMTC命令加載128 MB映射表的例子

主機端：當128 MB映射數(shù)據(jù)加載到映射緩存空間后，初始化H_CMB為全1，即所有LBA的映射關(guān)系都是有效的，同時還需初始化所有H_PVC為1 024。

設(shè)備端：設(shè)備端接收到RMTC命令后，把所需的映射關(guān)系從閃存中讀出，然后返回給主機，并初始化D_CMB為全1，即所有的映射頁都是有效的。

4.3 主機讀取操作

當主機需要讀取一個LBA(4 KB)數(shù)據(jù)時，主機查詢H_CMB，如果對應(yīng)的比特為1，則向設(shè)備發(fā)送FRRC，即快速隨機讀命令；否則只發(fā)送普通的4 KB讀命令，如圖4所示。

圖4 主機根據(jù)H_CMB發(fā)送不同的讀取命令

設(shè)備接收到的如果是普通的4 KB讀命令，則先做地址翻譯，即查詢該LBA對應(yīng)的物理地址，根據(jù)該物理地址從閃存中讀取數(shù)據(jù)，然后返回給主機。由于設(shè)備內(nèi)部緩存空間有限，所以該LBA對應(yīng)的映射頁很大概率不在緩存中，所以對每次讀，大概率需要先從閃存中加載映射頁，然后再根據(jù)映射頁得到的物理地址，從閃存中獲得主機所需的用戶數(shù)據(jù)，即一次普通的4 KB隨機讀，需要訪問兩次閃存。

如果設(shè)備接收到的是FRRC，即快速隨機讀命令，其不僅帶有LBA信息，還帶有該LBA對應(yīng)的物理地址，相當于主機已經(jīng)幫設(shè)備做好LBA的翻譯工作，則設(shè)備可以根據(jù)該物理地址直接從閃存中讀取數(shù)據(jù)，大大改善了隨機讀的速度。

但由于設(shè)備內(nèi)部存在垃圾回收算法，用戶數(shù)據(jù)會從一個物理閃存塊搬到另外一個物理閃存塊，因此設(shè)備接收到FRRC之前，還需要檢驗該物理地址是否有效。設(shè)備通過查詢D_CMB，如果該LBA所在的映射頁對應(yīng)的比特為0，表明該映射頁中至少有一個LBA被內(nèi)部垃圾回收搬走，由于不確定是否為該LBA，因此設(shè)備簡單地認為FRRC中的物理地址是無效的，所以設(shè)備需要自己重新做LBA地址翻譯，行為和處理普通讀命令一樣；如果查詢該LBA所在的映射頁對應(yīng)的比特為1，則表明FRRC的物理地址是有效的，設(shè)備可以直接拿它來獲取用戶數(shù)據(jù)。圖5為設(shè)備端處理命令的流程圖。

圖5 設(shè)備端處理讀命令

4.4 主機寫入操作

主機寫入數(shù)據(jù)時，設(shè)備會把這些數(shù)據(jù)寫到空閑的閃存空間。如果這些數(shù)據(jù)的映射關(guān)系緩存在主機內(nèi)存，由于設(shè)備把這些數(shù)據(jù)寫到新的地方，主機緩存的映射關(guān)系變成無效的(或者過時的)，主機清除H_CMB相應(yīng)的比特。主機在讀取的時候，不再使用該映射關(guān)系來發(fā)送FRRC。同時，如果某個LBA被主機寫入，該LBA對應(yīng)的映射頁有效數(shù)據(jù)H_PVC應(yīng)該減1。當某個映射頁的H_PVC減到一定閾值，即該緩存映射頁絕大多數(shù)映射關(guān)系都是無效時，主機在空閑的時候，應(yīng)該再次從設(shè)備加載最新的映射關(guān)系。主機端處理寫操作如圖6所示。

圖6 主機端處理寫操作

4.5 垃圾回收寫入操作

基于閃存的存儲設(shè)備，內(nèi)部需要垃圾回收來釋放閃存空間。垃圾回收會把用戶有效數(shù)據(jù)從一個物理塊重寫到另外一個物理塊，用戶數(shù)據(jù)映射關(guān)系會在主機沒有感知下發(fā)生變化，即緩存在主機端的映射頁除了因為主機寫之外，垃圾回收也會導(dǎo)致主機端緩存的映射關(guān)系無效。

垃圾回收重寫應(yīng)該更新設(shè)備端的D_CMB，具體來說，某個LBA被垃圾回收重寫，如果其對應(yīng)的映射頁緩存在主機端，則把該映射頁對應(yīng)的D_CMB比特清零，該過程如圖7所示。設(shè)備在接收到FRRC命令時，根據(jù)LBA對應(yīng)的映射頁查詢D_CMB。如果對應(yīng)的比特為0，則FRRC中的物理地址不可信，需要重寫做LBA地址翻譯；如果對應(yīng)的比特為1，則FRRC中的物理地址是有效的，設(shè)備無需LBA地址翻譯。

圖7 垃圾回收操作需清除D_CMB相應(yīng)比特

4.6 重新加載映射頁到主機緩存

隨著主機端數(shù)據(jù)的寫入，緩存的映射頁很多映射關(guān)系會無效，主機在寫入時會登記哪些映射頁需要重寫加載以提升FRRC命令占的比例。當主機空閑時，主機可以發(fā)送RMTC命令給設(shè)備，讓設(shè)備重新上傳最新的映射頁。

另外，垃圾回收也會導(dǎo)致緩沖頁無效，它也會在做垃圾回收的時候登記哪些映射頁需要重新加載。主機在空閑的時候，可以查詢設(shè)備狀態(tài)，獲取這些登記信息，然后發(fā)送相應(yīng)的RMTC命令重新加載映射頁到主機緩存。加載新的映射頁到主機緩存，需要更新相應(yīng)的H_CMB、D_CMB和H_PVC。

5 實驗結(jié)果

本文使用FlashSIM[9]仿真軟件來測試FRRA算法性能。FlashSIM是一款開源的SSD模擬器，也是一款事件驅(qū)動的、模塊化的基于C++的模擬器，內(nèi)置了多種FTL策略，能夠提供響應(yīng)時間、能耗的模擬和許多額外的統(tǒng)計信息。本文在模擬器上實現(xiàn)了FRRA算法，同時通過修改主機端驅(qū)動程序來支持FRRA。

設(shè)備端：本文使用FlashSIM模擬128 GB存儲設(shè)備，該存儲設(shè)備由4個32 GB的Flash組成，每個通道上掛一個Die。表1為存儲設(shè)備的配置信息。

表1 存儲設(shè)備配置

本文使用DFTL算法，在此基礎(chǔ)上增加了對RMTC和FRRC兩個定制命令的處理，以及相應(yīng)的FRRA算法實現(xiàn)。

主機端：分配128 MB內(nèi)存，可以容納全部的128 GB容量對應(yīng)的映射頁數(shù)據(jù)。增加了兩個RMTC和FRRC命令，分別用以加載映射頁到緩存和發(fā)送快速隨機讀取命令。

測試步驟：1)順序?qū)憹M盤，測試帶DRAM SSD的4 KB隨機讀取性能，以及不帶DRAM SSD不同算法下的4 KB隨機讀取性能；2)隨機寫滿盤，測試帶DRAM SSD的4 KB隨機讀取性能，以及不帶DRAM SSD不同算法下的4 KB隨機讀取性能。

實驗結(jié)果對比：

1)順序填滿盤后的4 KB隨機讀取性能對比如圖8所示。

圖8 順序填盤后4 KB隨機讀取性能對比

2)隨機填滿盤后的4 KB隨機讀取性能對比如圖9所示。

圖9 隨機填盤后4 KB隨機讀取性能對比

順序填盤后，由于CAST和WAFTL能針對順序?qū)懽鰞?yōu)化(減小映射表大小)，因此它比DFTL的4 KB隨機讀取性能好，但是如果是隨機數(shù)據(jù)填盤，WAFTL和CAST并沒有體現(xiàn)出性能優(yōu)勢。可以看出，利用主機端DRAM存儲映射表的FRR算法，與帶DRAM的SSD具有差不多的性能，其性能幾乎為DFTL性能的兩倍，因為它們訪問一次閃存便能獲得用戶數(shù)據(jù)。

6 結(jié) 語

無論是DFTL、CAST FTL和WAFTL等基于頁映射的FTL算法，都不能從根本上解決不帶DRAM的固態(tài)硬盤隨機讀取性能差的問題。FRRA通過利用主機端充足的DRAM資源來存儲設(shè)備的映射表，使用主機和存儲設(shè)備協(xié)同合作的方式，主機讀取命令中不僅攜帶了邏輯塊地址，還包括該數(shù)據(jù)塊在閃存中的物理地址，因此設(shè)備端省去了邏輯地址到物理地址的翻譯工作。故FRRA能顯著改善不帶DRAM的存儲設(shè)備的隨機讀取性能，并且其實現(xiàn)簡單，只需軟件層面的修改，無須改動硬件和修改接口協(xié)議。同時，它也不受當前協(xié)議限制，可以在當前幾乎所有的接口協(xié)議上實現(xiàn)，比如PCIe、SATA、UFS和eMMC等。