UStore：面向新型硬件的統(tǒng)一存儲系統(tǒng)

屠要峰 韓銀俊 金 浩 陳正華 陳 兵

1（南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106）2（中興通訊股份有限公司 南京 210012）

近年來，隨著云計(jì)算、移動互聯(lián)和物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，數(shù)據(jù)規(guī)模呈爆發(fā)式增長，傳統(tǒng)的存儲系統(tǒng)已經(jīng)無法滿足不斷增長的海量數(shù)據(jù)存儲需要，大容量高性能分布式存儲已經(jīng)成為數(shù)據(jù)中心的必備.長期以來，大多數(shù)分布式存儲直接使用本地文件系統(tǒng)如XFS（extents file system），EXT4（fourth extended file system）等訪問本地存儲資源.比如GlusterFS，HDFS直接使用本地文件系統(tǒng)作為其后端存儲，早期分布式文件系統(tǒng)Ceph 的FileStore 也是基于本地文件系統(tǒng)XFS 進(jìn)行本地存儲的訪問.本地文件系統(tǒng)成熟穩(wěn)定，充分利用了文件和對象天然的映射關(guān)系，利用操作系統(tǒng)頁緩存機(jī)制緩存數(shù)據(jù)，利用inode 節(jié)點(diǎn)緩存機(jī)制緩存元數(shù)據(jù)，同時從操作系統(tǒng)層面保證了磁盤的隔離性.但這種架構(gòu)也有明顯的局限性[1]，主要是事務(wù)一致性難以保證，元數(shù)據(jù)管理低效，以及缺乏對新型硬件的支持.由于這些弊端，Ceph 在Jewel 版本引入了BlueStore 作為后端存儲.BlueStore 將對象數(shù)據(jù)的存放方式改為直接對裸設(shè)備進(jìn)行指定地址和長度的讀寫操作，不再依賴本地文件系統(tǒng)提供的POSIX接口.同時，BlueStore 引入了RocksDB 數(shù)據(jù)庫保存元數(shù)據(jù)和屬性信息，包括對象的集合、對象、存儲池的omap 信息和磁盤空間分配記錄等.BlueStore 有效避免了數(shù)據(jù)和日志的雙寫，提升了元數(shù)據(jù)的操作效率，使得本地I/O 性能得到了較大的提升.但BlueStore 在小I/O 的處理上依然需要寫日志到RocksDB 中，同時RocksDB 的使用引入了序列化和反序列化以及compaction 帶來的開銷.

持久內(nèi)存（persistent memory，PMEM）、硬件加速的KVS（key-value store）等新型存儲形態(tài)的出現(xiàn)為本地存儲帶來了新的機(jī)遇.PMEM 具有低時延、非易失、字節(jié)尋址等特性，但是目前商用的PMEM 也存在著讀寫不對稱等不足，PMEM 比固態(tài)硬盤（solid state drive，SSD）容量小且單位存儲成本更高，在大容量高性能存儲場景下，存儲的數(shù)據(jù)規(guī)模和擴(kuò)展性受限，因此PMEM 適合用來存儲元數(shù)據(jù)和小數(shù)據(jù).KVS 規(guī)范為存儲設(shè)備定義了標(biāo)準(zhǔn)APIs，基于FPGA 硬件的KVS 在實(shí)現(xiàn)CPU-offload 的同時，利用超級電容保證崩潰一致性，可以有效減少類似RocksDB 在處理事務(wù)過程中帶來的寫放大和compaction 的開銷，具有較好的性能表現(xiàn)，同樣適合于元數(shù)據(jù)的存儲.基于Flash 的SSD由于存在著磨損不均衡、垃圾回收（garbage collection，GC）開銷及長尾延時等問題，不適合海量小文件頻繁讀寫的元數(shù)據(jù)管理，而更適合存儲大塊的數(shù)據(jù)對象.研究者針對新型硬件的存儲系統(tǒng)做了大量的研究和優(yōu)化.然而，現(xiàn)有基于新型硬件的存儲系統(tǒng)大多是對某種硬件單一場景的優(yōu)化，其優(yōu)化機(jī)制和應(yīng)用場景存在較大差異，普遍存在兼容性和擴(kuò)展性差的問題，無法靈活適配多種硬件配置的不同組合，例如基于SSD 優(yōu)化的存儲系統(tǒng)無法很好地適配PMEM 的讀寫特性.

針對上述問題，本文提出并實(shí)現(xiàn)了一種適配多種新型硬件的統(tǒng)一存儲UStore，通過不同存儲介質(zhì)特性的組合優(yōu)化設(shè)計(jì)，靈活構(gòu)建性價比更優(yōu)的本地存儲系統(tǒng).本文的主要貢獻(xiàn)有3 個方面：

1）實(shí)現(xiàn)了一個兼容PMEM、KVS 加速卡、NVMe SSD 等多種存儲介質(zhì)的統(tǒng)一存儲系統(tǒng)UStore，并可根據(jù)業(yè)務(wù)場景靈活選擇存儲介質(zhì)；針對PMEM+NVMeSSD，KVS+NVMeSSD，NVMe SSD 這3 種常用場景，結(jié)合PMEM 和NVMe SSD 硬件特性進(jìn)行組合設(shè)計(jì)優(yōu)化，滿足多層次的業(yè)務(wù)需求.

2）提出一種高效的數(shù)據(jù)布局和管理方法，利用易失的空閑空間管理和寫時重定向（redirect on write，ROW）技術(shù)，實(shí)現(xiàn)了無日志的數(shù)據(jù)更新方法，減少寫放大和管理開銷，提升了數(shù)據(jù)的訪問性能.

3）提出一種與物理存儲介質(zhì)形態(tài)解耦的元數(shù)據(jù)管理機(jī)制，能夠高效地適配不同存儲硬件介質(zhì)和接口；設(shè)計(jì)了一種面向數(shù)據(jù)原子寫優(yōu)化的元數(shù)據(jù)結(jié)構(gòu)，利用PMEM，NVMe SSD 等新型硬件的寫入原子性實(shí)現(xiàn)高效的元數(shù)據(jù)原子更新.

1 相關(guān)工作

現(xiàn)有研究在本地存儲優(yōu)化設(shè)計(jì)、基于PMEM 的存儲優(yōu)化、基于SSD 的存儲優(yōu)化等方面做了很多有益嘗試，以充分發(fā)揮新型存儲器件的特性和性能優(yōu)勢，提升存儲系統(tǒng)性能.

1）基于PMEM 的存儲優(yōu)化.傳統(tǒng)的存儲棧冗長的I/O 路徑和諸如頁緩存等機(jī)制嚴(yán)重影響PMEM 的特性和性能.PMFS[2]是英特爾公司提出的持久內(nèi)存文件系統(tǒng)，采用8B 原地更新和細(xì)粒度日志機(jī)制保證元數(shù)據(jù)更新的原子性，采用undo 日志和寫時復(fù)制混合的方式保證數(shù)據(jù)的一致性.NOVA[3]是一個基于混合易失/非易失主內(nèi)存的日志結(jié)構(gòu)文件系統(tǒng)，充分利用PMEM 的優(yōu)勢提供更強(qiáng)的一致性和原子性保證，支持元數(shù)據(jù)、數(shù)據(jù)和mmap 三種操作的原子性保證.NOVA 保存日志和文件數(shù)據(jù)到PMEM 中，并且通過在DRAM 中構(gòu)建radix 樹保存索引以便加速查找操作.NoveLSM[4]是基于PMEM 的LSM-Tree（log-structure merge tree）的鍵值存儲系統(tǒng)，旨在利用PMEM，為應(yīng)用提供低延遲和高吞吐鍵值存儲，但是沒有引入SSD進(jìn)行組合優(yōu)化.KucoFS[5]重新審視了基于非易失性存儲器的文件系統(tǒng)體系結(jié)構(gòu)，提出一個內(nèi)核和用戶級協(xié)作文件系統(tǒng)，它充分利用了用戶級直接訪問和內(nèi)核空間數(shù)據(jù)保護(hù)各自的優(yōu)點(diǎn).KucoFS 將文件系統(tǒng)解耦為內(nèi)核線程（稱為master）和用戶空間庫（稱為Ulib），客戶端能夠通過Ulib 直接在用戶級別讀取/寫入文件數(shù)據(jù)，而master 專用于更新元數(shù)據(jù)并保證文件數(shù)據(jù)的完整性，通過以只讀模式將PMEM 空間導(dǎo)出到用戶級別來防止錯誤的程序破壞文件系統(tǒng).KucoFS通過索引卸載技術(shù)重新平衡內(nèi)核和用戶空間之間的路徑名解析開銷，通過協(xié)調(diào)內(nèi)核和用戶空間之間的數(shù)據(jù)分配，并使用范圍鎖定寫入和無鎖定讀取來支持高并發(fā)，提升了數(shù)據(jù)訪問效率和多核擴(kuò)展性.

2）基于SSD 的存儲優(yōu)化.業(yè)界主要研究和解決基于Flash 的SSD 所存在的GC 長尾延時、垃圾回收開銷、容量利用率低以及主機(jī)軟件復(fù)雜等問題.Stream SSD[6]通過SSD 主控來對寫入的請求進(jìn)行標(biāo)記，請求進(jìn)入到流式SSD 內(nèi)部的時候根據(jù)預(yù)定義好的流式SSD 標(biāo)記來將帶有不同標(biāo)記的輸入命令分配存儲到不同的擦除塊之內(nèi)，可以減少因?yàn)閮?nèi)存轉(zhuǎn)換層（flash translation layer，F(xiàn)TL）調(diào)度GC 導(dǎo)致的性能和SSD 壽命的損失.但是流式SSD 對主控要求比較高，需要消耗更多的內(nèi)存（保存未區(qū)分的狀態(tài)）以及性能更好的主控芯片.Open-channel SSD[7]允許SSD 主機(jī)和SSD 共同管理一個連續(xù)的LBA（logical block address）塊集合，并且對外暴露的操作指令是擦除塊對齊的.這種按照擦除塊對齊的訪問模型能夠消除 SSD 內(nèi)部GC 的代價，并且降低對OP（over provisioning）空間的消耗.但是，Open-channel SSD 需要主機(jī)軟件來做LBA管理、擦除塊的回收以及壞塊的管理，還需要兼容不同的SSD 內(nèi)部實(shí)現(xiàn)機(jī)制，開發(fā)維護(hù)成本過于高昂.NVMe 分區(qū)命名空間命令集規(guī)范（zoned namespaces command set specification，ZNS）代表主機(jī)軟件和基于閃存的SSD 之間的新功能劃分，它有望成為解決SSD 現(xiàn)有問題的主流方案.文獻(xiàn)[8]采用ZNS 接口，通過將管理擦除塊內(nèi)數(shù)據(jù)組織的功能從FTL 層轉(zhuǎn)移到主機(jī)軟件，消除了設(shè)備內(nèi)LBA 到頁的映射、GC 和OP 空間.ZNS 使得基于閃存的SSD 具有更高的性能和更低的每字節(jié)成本.ZNS 的架構(gòu)契合LSM-Tree 的追加順序?qū)懱匦?，SSD 的GC 過程也能和LSM-Tree的compaction 操作相結(jié)合，因此軟件層面上的需求和發(fā)展趨勢也促進(jìn)了ZNS SSD 的發(fā)展.

在軟件層面上，LSM-Tree 把離散的隨機(jī)I/O 通過compaction 操作轉(zhuǎn)變成連續(xù)的順序I/O，相對于傳統(tǒng)的B+樹，對于機(jī)械硬盤（hard disk drive，HDD）的寫入性能有很好的優(yōu)化，對于SSD 則能夠減少GC.WiscKey[9]提出一種基于SSD 優(yōu)化的鍵值存儲，核心思想是把鍵Key和值Value分離，只有Key被保存在LSM-Tree中，而Value單獨(dú)存儲在日志中.這樣就顯著減小了LSM-Tree 的大小，使得查找期間數(shù)據(jù)讀取量變少，并減輕了由于索引樹合并時不必要的數(shù)據(jù)移動而引起的寫放大.WiscKey 保留了LSM-Tree 的優(yōu)勢，減少了寫放大，但數(shù)據(jù)訪問時需要進(jìn)行多次MAP 映射，且依然存在LSM-Tree 固有的compaction 過程.KVell[10]是基于NVMe SSD 設(shè)計(jì)的高效鍵值存儲，核心設(shè)計(jì)思想是簡化CPU 的使用，數(shù)據(jù)在SSD 上不排序，每個分區(qū)的索引在內(nèi)存中是有序的.這種設(shè)計(jì)在每次啟動時需要進(jìn)行索引的重構(gòu)，無法滿足快速重啟動的需求.KVell 使用頁緩存和最近最少使用（least recently used，LRU）算法負(fù)責(zé)磁盤上的空閑空間申請和釋放，省去了磁盤上空閑空間回收和整理的過程.但是當(dāng)磁盤容量快被用完時，大概率觸發(fā)SSD 的擦除→拷貝→修改→寫入過程，實(shí)際I/O 性能會大幅下降.

3）基于PMEM/SSD 混合存儲的優(yōu)化.Strata[11]是針對持久性內(nèi)存、SSD 和HDD 設(shè)計(jì)的混合存儲系統(tǒng).Strata 將PMEM 空間劃分為日志區(qū)和共享數(shù)據(jù)區(qū)2個部分，日志區(qū)對每個進(jìn)程是私有的，共享數(shù)據(jù)區(qū)對所有進(jìn)程可見，SSD 和HDD 均為共享數(shù)據(jù)區(qū).在進(jìn)行文件系統(tǒng)更新操作時，將更新在用戶態(tài)直接以日志的形式寫入到PMEM 的私有日志區(qū)，以繞過內(nèi)核中的頁緩存.后臺線程異步地將私有日志區(qū)中的數(shù)據(jù)寫入到共享數(shù)據(jù)區(qū)中，即digest 操作，過程中先對日志進(jìn)行合并后再寫入，從而減少寫入量.在DRAM中維護(hù)LRU 列表，供內(nèi)核進(jìn)行數(shù)據(jù)遷移，將最近訪問的數(shù)據(jù)保存在快速設(shè)備中，遷移的粒度分別使用SSD 擦除塊的大小或者HDD 寫入塊大小，優(yōu)化SSD和HDD 的寫入.SLM-DB[12]基 于PMEM 和SSD 對LSM-Tree 進(jìn)行改進(jìn)，通過把多層SSTable 結(jié)構(gòu)減少為一層，避免了多層SSTable 帶來的寫放大問題，同時在PMEM 上用B+樹給所有的SSTable 建立了全局索引，加速對磁盤數(shù)據(jù)的訪問，具有低寫入放大和近乎最優(yōu)的讀取放大特性.但是，當(dāng)數(shù)據(jù)量變多時維護(hù)PMEM 上B+樹的代價會很大.

Table 1 Experimental Environment Configuration表1 實(shí)驗(yàn)環(huán)境配置

肖仁智等人[13]從持久索引、文件系統(tǒng)和持久性事務(wù)等方面對基于PMEM 的相關(guān)工作進(jìn)行了綜述和總結(jié)，并指出在開發(fā)新的一致性持久內(nèi)存索引方面，未來更多的工作將集中在LSM-Tree[14]和SkipList[15]上.在基于異構(gòu)硬件加速的優(yōu)化方面，PolarDB 的后端存儲引擎X-Engine[16]基于LSM-Tree 改進(jìn)，將寫操作實(shí)現(xiàn)為多核并行流水化模式，使用FPGA 加速compaction 過程，將L0 層文件保存到PMEM 介質(zhì)，一定程度上避免抖動.PolarDB 所做的優(yōu)化對電商業(yè)務(wù)場景的數(shù)據(jù)訪問有顯著改進(jìn)，對普通的存儲場景的數(shù)據(jù)讀寫效果未知.

上述3 種改進(jìn)和優(yōu)化[11-13]，都是針對SSD 或者PMEM 的硬件特性在軟件層面進(jìn)行優(yōu)化，以提升系統(tǒng)性能和器件壽命.各種優(yōu)化方案相互差異大，存在彼此不兼容、擴(kuò)展性差、缺乏對硬件環(huán)境的靈活適應(yīng)等問題，未見從兼容性和擴(kuò)展性角度出發(fā)，構(gòu)建PMEM+SSD 混合存儲系統(tǒng)，靈活適配多種硬件配置的工作和研究.本文提出并實(shí)現(xiàn)了一種適配多種新型硬件的統(tǒng)一存儲UStore，通過不同存儲介質(zhì)特性的組合優(yōu)化設(shè)計(jì)，靈活構(gòu)建性價比更優(yōu)的本地存儲系統(tǒng).

2 UStore 架構(gòu)設(shè)計(jì)

傳統(tǒng)的存儲系統(tǒng)通常是面向內(nèi)存+外存2 層存儲架構(gòu)設(shè)計(jì).內(nèi)存是高性能、易失的，容量較??；外存（例如HDD，SSD）則是低速、非易失的，容量較大.新型存儲硬件的出現(xiàn)打破了內(nèi)存、外存之間的界限，對上層軟件系統(tǒng)的設(shè)計(jì)產(chǎn)生重大影響.針對高性能的NVMe SSD，PMEM，KVS 存儲等硬件，雖然都是非易失存儲器，但相互之間在容量、成本、性能以及硬件特性方面差異較大.為了充分利用不同存儲設(shè)備各自的性能、容量和成本優(yōu)勢，有必要將性能、容量、易失性作為獨(dú)立的維度進(jìn)行考慮，設(shè)計(jì)全新的系統(tǒng)架構(gòu)，靈活適配多種硬件特性和業(yè)務(wù)場景.

原子寫是存儲系統(tǒng)需要解決的關(guān)鍵問題之一.原子寫是指寫入的數(shù)據(jù)是原子的，要不全部寫入成功，要不寫入失敗，保留原先數(shù)據(jù)，而不能是一個中間的不確定狀態(tài).XFS 等文件系統(tǒng)通過日志機(jī)制保證了自身元數(shù)據(jù)的崩潰一致性，但不提供針對文件內(nèi)容的原子寫保證.NVMe 規(guī)范定義了原子寫相關(guān)特性AWUN（atomic write unit normal）和AWUPF（atomic write unit power fail），但當(dāng)前主流的NVMe SSD 僅實(shí)現(xiàn)了4KB 數(shù)據(jù)的寫入原子性，如果要更新4KB 以上的數(shù)據(jù)則仍然需要在軟件層面通過額外的手段進(jìn)行保證.比如MySQL 通過DWB（double write buffer）機(jī)制保證數(shù)據(jù)庫8KB 頁面的原子寫入，PostgreSQL 通過FPW（full page writes）機(jī)制保證了16KB 數(shù)據(jù)頁面的原子寫入，RocksDB[17]通過預(yù)寫式日志（write ahead log，WAL）機(jī)制確保了數(shù)據(jù)寫入的原子性.這些系統(tǒng)有一個共性，就是通過重復(fù)的數(shù)據(jù)寫入機(jī)制來實(shí)現(xiàn)原子更新，但是數(shù)據(jù)的多次寫入帶來了額外的系統(tǒng)開銷，對SSD 來說同時也增加了閃存介質(zhì)的磨損，減少了硬件壽命.

UStore 將介質(zhì)的容量、性能、易失性分開考慮，從系統(tǒng)架構(gòu)層面進(jìn)行重新組合，通過數(shù)據(jù)和元數(shù)據(jù)分離、元數(shù)據(jù)設(shè)計(jì)和存儲介質(zhì)解耦，實(shí)現(xiàn)了性能與容量的平衡，數(shù)據(jù)和元數(shù)據(jù)的存儲可以分別使用特定硬件或硬件組合完成，充分發(fā)揮各自的優(yōu)勢，具有很好的通用性.同時，利用硬件的寫入原子性實(shí)現(xiàn)元數(shù)據(jù)的原子更新，并進(jìn)一步結(jié)合ROW 機(jī)制完成數(shù)據(jù)的原子更新，使得上層軟件不再需要關(guān)注該問題.

UStore 的系統(tǒng)架構(gòu)如圖1 所示.UStore 對上層提供塊接口，內(nèi)部則主要包括元數(shù)據(jù)管理、數(shù)據(jù)管理和空閑空間管理3 個模塊，其中元數(shù)據(jù)管理模塊負(fù)責(zé)管理系統(tǒng)的元數(shù)據(jù)，數(shù)據(jù)管理模塊負(fù)責(zé)SSD 盤的管理和數(shù)據(jù)的讀寫，空閑空間管理模塊則記錄了數(shù)據(jù)存儲空間的空閑情況，用于空間的分配和回收.

Fig.1 UStore system architecture圖1 UStore 系統(tǒng)架構(gòu)

數(shù)據(jù)管理模塊提供可變?nèi)萘看鎯臻g分區(qū)（Blob）的抽象.Blob 與傳統(tǒng)的LVM（logical volume manager）邏輯卷類似，提供一段連續(xù)的邏輯存儲空間，并支持動態(tài)擴(kuò)容.Blob 分區(qū)可用于支持?jǐn)?shù)據(jù)和性能的隔離，有利于實(shí)現(xiàn)更高效、更穩(wěn)定的數(shù)據(jù)訪問.用戶數(shù)據(jù)被切分為較小粒度的數(shù)據(jù)塊（Chunk）進(jìn)行管理和存儲，用戶的塊接口讀寫請求被轉(zhuǎn)換為基于ChunkID 的Chunk 內(nèi)數(shù)據(jù)讀寫.數(shù)據(jù)管理模塊中的數(shù)據(jù)是非易失的，且提供特定粒度數(shù)據(jù)的原子更新特性，以幫助UStore 對外提供任意粒度的原子寫接口.數(shù)據(jù)管理模塊底層可以選用NVMe SSD，ZNS SSD 等大容量設(shè)備作為其物理存儲設(shè)備.

空閑空間管理模塊負(fù)責(zé)空閑空間管理.一段存儲空間在任意時刻只可能是“空閑”或“占用”2 種狀態(tài)之一，占用空間信息由元數(shù)據(jù)管理模塊持久化，空閑空間信息則可不必持久化.因此，空閑空間管理被設(shè)計(jì)為易失性的，以避免持久化開銷，同時降低數(shù)據(jù)更新的復(fù)雜度，提高空閑空間管理的性能.空閑空間被描述為若干個[offset，length]的結(jié)構(gòu)并在內(nèi)存中進(jìn)行索引，在空間分配、回收或Blob 容量調(diào)整時更新.在系統(tǒng)啟動階段，通過加載和遍歷元數(shù)據(jù)管理中的已占用空間信息，在內(nèi)存中反向構(gòu)建出每個Blob 的空閑空間信息.配合Blob 的動態(tài)調(diào)整，空閑空間管理模塊的索引數(shù)據(jù)總量可以維持在較小的規(guī)模，可以全部駐留在內(nèi)存中，并由此獲得較高的性能.

元數(shù)據(jù)管理模塊負(fù)責(zé)維護(hù)Chunk 和Blob 中數(shù)據(jù)的映射關(guān)系，即元數(shù)據(jù)，該信息描述為Chunk 在Blob內(nèi)的偏移地址，以縮減元數(shù)據(jù)總量.該信息是非易失的，支持原子更新，并且需要提供高效讀寫能力.元數(shù)據(jù)管理模塊設(shè)計(jì)了與物理存儲介質(zhì)形態(tài)解耦的元數(shù)據(jù)管理方案，可根據(jù)業(yè)務(wù)場景選擇不同的存儲介質(zhì)保存元數(shù)據(jù)，滿足同一存儲系統(tǒng)靈活適配不同存儲硬件形態(tài)的組合.對于容量和性能要求較高、存儲成本不敏感的業(yè)務(wù)場景選擇PMEM+NVMe SSD 方式，將元數(shù)據(jù)保存到性能較好的PMEM.對于需要控制成本、無法添加PMEM 等硬件的傳統(tǒng)業(yè)務(wù)，則可以選擇全NVMe SSD 方式構(gòu)建存儲系統(tǒng)，將數(shù)據(jù)、元數(shù)據(jù)都保存到NVMe SSD.對于CPU 資源敏感的場景選擇硬件KVS+NVMe SSD 方式，可以將元數(shù)據(jù)讀寫卸載到硬件KVS 系統(tǒng).

UStore 充分利用新型存儲硬件的寫入原子性，實(shí)現(xiàn)了Chunk 粒度的原子寫，根據(jù)寫操作是否超出了硬件提供的原子寫能力，系統(tǒng)通過2 種不同的方式進(jìn)行處理.當(dāng)寫操作滿足硬件原子寫對齊和粒度要求時，例如NVMe SSD 的4KB 更新，使用直接I/O的方式進(jìn)行覆蓋寫，不需要對索引進(jìn)行更新，硬件的原子寫直接保證了數(shù)據(jù)的原子寫.當(dāng)寫操作粒度超出硬件能力時，例如大于4KB 的數(shù)據(jù)寫入，則通過ROW 方式寫入，UStore 首先分配新的空閑空間進(jìn)行數(shù)據(jù)的寫入，在寫入成功以后再更新元數(shù)據(jù)信息，此時原子寫問題被轉(zhuǎn)換為元數(shù)據(jù)的一致性問題.進(jìn)一步地，UStore 通過優(yōu)化的元數(shù)據(jù)設(shè)計(jì)將一致性問題簡化為單次、小粒度的元數(shù)據(jù)更新問題，然后通過硬件原子寫完成元數(shù)據(jù)更新.具體來說，空閑空間管理是易失性的，空閑空間的分配不涉及持久化操作；數(shù)據(jù)寫入完成后，僅由元數(shù)據(jù)管理模塊執(zhí)行一次元數(shù)據(jù)原子更新，并在成功后進(jìn)行舊數(shù)據(jù)所占用空間的回收過程；同樣，空間回收過程不涉及持久化操作.由于元數(shù)據(jù)更新的原子性和空閑空間管理的易失性，此過程在任意階段崩潰都不會造成用戶數(shù)據(jù)的錯誤和Blob 空閑空間的泄漏.

此外，系統(tǒng)中的數(shù)據(jù)及其維護(hù)操作被按照Blob進(jìn)行了水平分割，每個Blob 由特定的工作線程處理，這樣可減少資源爭用和鎖沖突，使得數(shù)據(jù)隔離等特性容易實(shí)現(xiàn)，NUMA（non-uniform memory access）親和性等技術(shù)也可以方便地應(yīng)用到系統(tǒng)中，以便從多方面提升系統(tǒng)性能.

UStore 通過數(shù)據(jù)和元數(shù)據(jù)的分離、與存儲硬件形態(tài)解耦的元數(shù)據(jù)管理、基于存儲硬件特性的原子寫等優(yōu)化設(shè)計(jì)，充分利用不同存儲器件的容量、成本、性能以及硬件特性優(yōu)勢，實(shí)現(xiàn)了針對多種存儲硬件和場景優(yōu)化的統(tǒng)一存儲，在提升性能的同時，具有較好的通用性和靈活性.

3 關(guān)鍵技術(shù)

3.1 高效的數(shù)據(jù)管理機(jī)制

數(shù)據(jù)管理包括物理空間的分配與回收、數(shù)據(jù)的讀寫等功能.出于優(yōu)化硬件兼容性和管理效率的考慮，空間分配和回收被劃分為Blob 和Block 兩個級別，Blob 的管理由數(shù)據(jù)管理模塊負(fù)責(zé)，Block 的管理則由空閑空間管理模塊負(fù)責(zé)，并借助元數(shù)據(jù)管理模塊進(jìn)行持久化.

3.1.1 高性能的空間分區(qū)

數(shù)據(jù)管理模塊主要負(fù)責(zé)Blob 管理和讀寫，Blob空間隨著用戶數(shù)據(jù)的寫入動態(tài)擴(kuò)容.Block 是Blob 的基本讀寫單元，但不是空間分配單元，這樣做的目的是減少地址轉(zhuǎn)換條目的數(shù)量.

如圖2（a）所示，為了實(shí)現(xiàn)動態(tài)擴(kuò)容，Blob 實(shí)際由NVMe 盤上的多個物理區(qū)段組成，每個物理區(qū)段的容量是Block 的整數(shù)倍，并遠(yuǎn)大于Block 大小.數(shù)據(jù)管理模塊僅需要維護(hù)極少量Blob 到物理區(qū)段的地址轉(zhuǎn)換條目信息，對Blob 內(nèi)特定偏移地址的訪問可以很容易地通過計(jì)算轉(zhuǎn)換為NVMe SSD 的物理地址.Blob的另一個作用是性能的聚合或隔離，例如，對于ZNS SSD，可以將Blob 映射到不同zone，以避免高負(fù)載用戶擠占其他用戶的資源，或者將Blob 交錯排布到不同硬件上，以提供更高的讀寫性能.

Fig.2 Data management mechanism圖2 數(shù)據(jù)管理機(jī)制

數(shù)據(jù)管理模塊的設(shè)計(jì)要求Blob 邊界滿足硬件原子寫的對齊要求，以便利用存儲硬件的原子寫特性實(shí)現(xiàn)高效的Chunk 粒度原子寫接口.對于NVMe SSD，由于硬件支持Block 級別的原子寫，Blob 劃分總是滿足對齊要求，無需額外的處理.當(dāng)后續(xù)適配其他新型存儲硬件時，可以根據(jù)新硬件的特性擴(kuò)展Blob 的實(shí)現(xiàn)，并對UStore 的其他模塊屏蔽這種變化.

實(shí)現(xiàn)Blob 的高性能讀寫，還需要降低或避免系統(tǒng)調(diào)用、內(nèi)存拷貝等操作的開銷.UStore 選擇基于SPDK[18]庫實(shí)現(xiàn)數(shù)據(jù)管理模塊.SPDK 是Intel 提供的存儲平面開發(fā)套件，其BlobStore 接口實(shí)現(xiàn)了UStore所需的Blob 語義，并能夠支持NVMe，ZNS 等多種存儲設(shè)備，SPDK 通過用戶態(tài)NVMe 驅(qū)動訪問NVMe SSD，以繞過操作系統(tǒng)內(nèi)核，獲得更高的I/O 性能.Blob 的創(chuàng)建、刪除、擴(kuò)容都是原子的，異常崩潰不會導(dǎo)致一致性問題.同時，SPDK 提供了直接內(nèi)存訪問（direct memory access，DMA）內(nèi)存管理機(jī)制，UStore 利用這種機(jī)制管理Blob 讀寫時的內(nèi)存申請和釋放，以減少數(shù)據(jù)的來回拷貝.

3.1.2 輕量級空閑空間索引

數(shù)據(jù)空間分配、空閑空間回收的實(shí)現(xiàn)方式不僅關(guān)系到整個存儲系統(tǒng)的性能，而且直接影響存儲空間利用率.Blob 內(nèi)的空間按Block 進(jìn)行管理，對用戶提供的塊接口也是Block 對齊的，不會出現(xiàn)不規(guī)則的空間碎片，因此物理空間的分配回收算法能夠做到簡潔而高效.

如圖2（b）所示，空閑空間管理模塊使用鏈表和B+樹來存儲空閑塊信息，空閑塊[offset，length]信息保存在鏈表中，并按空閑塊長度length升序排列，方便按長度查找空閑塊.B+樹的Key為空閑塊的offset值，底層葉子節(jié)點(diǎn)則直接指向鏈表中的節(jié)點(diǎn)，用于實(shí)現(xiàn)相鄰空閑塊的歸并.除此之外，為鏈表增加多個Pointer指針，分別指向不同長度的空閑空間的起始節(jié)點(diǎn)，以避免空間分配時遍歷整個鏈表.同一個Blob 的I/O 請求由相同的工作線程處理，因此避免了多線程并發(fā)訪問和更新上述結(jié)構(gòu)時的鎖開銷.

空間分配操作從鏈表中找到符合要求的最小空閑塊，首先將空閑塊從鏈表、B+樹中刪除，從空閑塊尾部分配指定大小空間，然后更新空閑塊的length信息，最后將更新后的空閑塊重新插入到B+樹及鏈表，當(dāng)空閑塊剩余長度為0 時，則不需要重新插入.

空間釋放操作根據(jù)待釋放空間的offset在B+樹查找插入位置，并嘗試與相鄰節(jié)點(diǎn)的空閑塊合并.若與前驅(qū)節(jié)點(diǎn)合并成功，則更新前驅(qū)節(jié)點(diǎn)的length為二者之和；若與后繼節(jié)點(diǎn)合并成功，則刪除后繼節(jié)點(diǎn)，并使用待釋放空間的offset作為Key插入新節(jié)點(diǎn)，其length為二者之和；若與前、后節(jié)點(diǎn)都合并成功，則更新前驅(qū)節(jié)點(diǎn)length為三者之和，并刪除后繼節(jié)點(diǎn)；若無法合并，則直接插入新節(jié)點(diǎn).

初始化時，空閑空間管理模塊將整個Blob 初始化為一個連續(xù)的空閑塊，然后通過遍歷元數(shù)據(jù)找到所有已占用的空間信息，按照空間分配過程將所有已占用的空間從空閑空間管理中刪除，最終恢復(fù)出Blob 的空閑空間信息，元數(shù)據(jù)管理的高性能使得這一過程能夠很快地完成.

得益于Block 對齊和最佳匹配長度的數(shù)據(jù)分配策略，經(jīng)過長時間頻繁的空間分配和回收，系統(tǒng)空閑空間仍然比較規(guī)整，不會出現(xiàn)大量碎片空間，避免了傳統(tǒng)空間管理中復(fù)雜的碎片整理流程，也使空閑空間管理的索引數(shù)據(jù)總量得到控制.相對于傳統(tǒng)的空閑空間管理，UStore 空閑空間管理更簡潔而高效.

3.2 與存儲介質(zhì)形態(tài)解耦的元數(shù)據(jù)管理

元數(shù)據(jù)管理模塊負(fù)責(zé)維護(hù)元數(shù)據(jù)信息，元數(shù)據(jù)索引的本質(zhì)是邏輯地址與數(shù)據(jù)存儲位置的對應(yīng)關(guān)系，讀寫操作根據(jù)邏輯地址查詢索引，找到數(shù)據(jù)保存的Blob 及offset信息.UStore 設(shè)計(jì)了一種與物理存儲介質(zhì)形態(tài)解耦的元數(shù)據(jù)管理方案，能夠適配不同存儲硬件介質(zhì)和接口，元數(shù)據(jù)采用2 級索引結(jié)構(gòu)，第1 級索引是Chunk 索引，記錄Chunk 的物理地址信息，第2 級索引是Chunk 內(nèi)子數(shù)據(jù)塊的地址信息，用于實(shí)現(xiàn)數(shù)據(jù)原子寫能力.同時，2 級索引的引入使得多個子數(shù)據(jù)塊可以并發(fā)寫入，提高系統(tǒng)的并發(fā)更新能力.

當(dāng)Chunk 首次寫入數(shù)據(jù)時，按照Chunk 大小分配一段連續(xù)的初始空間，此時邏輯空間的Block 塊與物理空間Block 塊一一對應(yīng).如圖3（a）所示，元數(shù)據(jù)中只需要保存邏輯ChunkID、物理空間偏移地址offset.

Fig.3 Metadata management圖3 元數(shù)據(jù)管理

當(dāng)使用ROW 模式完成數(shù)據(jù)更新時，需要將數(shù)據(jù)寫入新分配的物理空間，因此每次寫入超過Block 長度的數(shù)據(jù)會產(chǎn)生一段隨機(jī)物理地址，如圖3（b）所示，一個Chunk 的數(shù)據(jù)由一段初始空間和多段增量空間存儲.為了管理這些不連續(xù)的物理空間，UStore 采用2 級索引記錄子數(shù)據(jù)塊邏輯地址與物理地址的映射關(guān)系.

索引條目采用鍵值接口的數(shù)據(jù)容器存儲，Key為ChunkID，Value為索引條目.KV 數(shù)據(jù)容器的類型根據(jù)實(shí)際采用的存儲介質(zhì)不同而有所差異.一個Chunk索引條目具體包括ChunkID，offset，head，tail，以及用于保存二級索引的entry數(shù)組.其中ChunkID長度為8B，offset（長度為4B）為Blob 內(nèi)地址偏移，tail（長度為2B）指向entry數(shù)組的下一個空閑位置，head（長度為2B）指向entry數(shù)組的最早寫入位置，entry數(shù)組每個成員保存一段子數(shù)據(jù)塊的索引信息，包括：數(shù)據(jù)在Chunk 內(nèi)的偏移地址entry_off（長度為2B）、數(shù)據(jù)在Blob 中的偏移地址data_off（長度為4B）、以Block 為單位的數(shù)據(jù)長度len（長度為2B）.數(shù)組長度決定了單個Chunk 更新的最大并發(fā)度以及讀操作時的最大讀盤次數(shù)，為了適配不同業(yè)務(wù)場景需求，2 級索引條目數(shù)組長度支持靈活配置，可以根據(jù)實(shí)際情況指定.

經(jīng)過測試驗(yàn)證，深度為16 的4KB 原子寫能夠接近主流NVMe SSD 的吞吐率上限，因此，UStore 設(shè)定默認(rèn)值為16.此時，一個完整的Chunk 索引條目長度為8+4+2+2+（4+2+2）×16=144B.為了優(yōu)化索引的讀寫性能，將head，tail都定義為2B，同時將索引結(jié)構(gòu)聲明為cacheline 對齊的.此時，單個entry也滿足8B 對齊要求，硬件僅需提供8B 的原子寫保證即可用于元數(shù)據(jù)的原子更新，而無需日志機(jī)制.

第2 級索引基于數(shù)組entry實(shí)現(xiàn)循環(huán)隊(duì)列算法，head，tail分別指向循環(huán)隊(duì)列的頭位置和尾位置，隊(duì)列采用尾部插入、頭部刪除的規(guī)則，插入時前移tail指針，刪除前移head指針，指針到達(dá)邊界后從0 重新開始.

基于這樣的2 級索引，數(shù)據(jù)讀取操作在查詢到Chunk 索引條目后，需要遍歷循環(huán)隊(duì)列head和tail之間的所有條目，確定對應(yīng)的數(shù)據(jù)塊是否存在更新.如果不存在，則直接從1 級索引對應(yīng)偏移位置讀??；否則，根據(jù)實(shí)際情況不同，可能需要讀取多個更新并進(jìn)行合并，得到所需的用戶數(shù)據(jù).考慮到上層系統(tǒng)通常以相同的粒度更新和讀取數(shù)據(jù)，涉及合并的情況并不會太多.

為了避免2 級索引耗盡導(dǎo)致寫操作產(chǎn)生性能抖動，UStore 啟動后臺歸并線程，在循環(huán)隊(duì)列屆滿時進(jìn)行子數(shù)據(jù)塊的合并.歸并線程首先將所有子數(shù)據(jù)塊合并到原始Chunk 中，然后更新第2 級索引的head指針.子數(shù)據(jù)塊遷移完成前，索引、子數(shù)據(jù)塊都不變，因此不影響數(shù)據(jù)的讀流程，遷移過程中系統(tǒng)崩潰也不會產(chǎn)生一致性問題.對于寫操作，工作線程、歸并線程分別更新第2 級索引的head，tail指針，可以并行執(zhí)行，而無需使用鎖或其他互斥機(jī)制.

綜上，UStore 的元數(shù)據(jù)結(jié)構(gòu)是面向數(shù)據(jù)原子寫而優(yōu)化的，任意情況下對索引條目的更新僅需8B 原子性保證，降低了對底層硬件的要求.對于元數(shù)據(jù)條目本身的創(chuàng)建和刪除操作，其原子性則通過KV 容器來保證.當(dāng)元數(shù)據(jù)存儲到不同硬件時，可以靈活地根據(jù)其特性設(shè)計(jì)高性能的KV 容器方案，最大限度地保證2 級索引的訪問性能.通過與物理存儲介質(zhì)形態(tài)解耦的元數(shù)據(jù)管理機(jī)制，UStore 實(shí)現(xiàn)了對多層次存儲需求的兼容，可以根據(jù)業(yè)務(wù)場景靈活地選擇存儲介質(zhì)的組合.

3.2.1 基于NVMe SSD 的索引

NVMe SSD 支持4KB 的Block 原子寫能力，可以用于實(shí)現(xiàn)2 級索引的原子更新.當(dāng)僅使用NVMe SSD存儲元數(shù)據(jù)時，每次讀寫數(shù)據(jù)都需要至少2 次訪問SSD盤，如果元數(shù)據(jù)訪問涉及不止1 次I/O，則性能損耗更為明顯.為了提高讀寫效率，使用DRAM 作為緩存，即組合使用DRAM+NVMe SSD 完成元數(shù)據(jù)存儲.此時，讀操作可以從內(nèi)存中讀取元數(shù)據(jù).數(shù)據(jù)更新時先寫數(shù)據(jù)，再更新內(nèi)存中的元數(shù)據(jù)，最后將元數(shù)據(jù)所在的Block 寫入SSD 盤，依靠Block 原子寫保證整個寫流程的原子性.[19]

如圖4 所示，元數(shù)據(jù)、數(shù)據(jù)分別由索引Blob，數(shù)據(jù)Blob 存儲.系統(tǒng)啟動后，初始化階段將所有索引Blob 內(nèi)容加載到連續(xù)的內(nèi)存空間，這樣可以通過內(nèi)存數(shù)組方式直接訪問元數(shù)據(jù)的一級索引.根據(jù)前文定義，單個Chunk 的索引條目長度為144 B，那么1 個Block可以容納4 096/144=28 個索引，以Intel P4610 SSD 盤（1.6 TB）為例，當(dāng)Chunk 大小為默認(rèn)值1MB 時，1 個SSD 盤的索引空間大約為（1.6 TB/1 MB）/28×4 096=236 MB，DRAM 中索引緩沖空間則最多為236 MB.運(yùn)行過程通過查找內(nèi)存線性表完成Chunk 索引查詢，第1 級索引查詢的時間復(fù)雜度O（1），其算法為ptr=（ChunkID/28）×4 KB+ChunkIDmod 28.第2 級索引需要從尾部遍歷子數(shù)據(jù)塊，因此，查詢效率與子數(shù)據(jù)塊的數(shù)量相關(guān).

Fig.4 NVMe SSD-based index圖4 基于NVMe SSD 的索引

單個Chunk 的索引條目保存在1 個Block 塊，因此，1 個Chunk 的索引更新可以通過1 次原子寫完成持久化，依靠SSD 的原子寫能力實(shí)現(xiàn)用戶數(shù)據(jù)的原子更新.一次完整的索引更新步驟為：

1）分配新的SSD 盤物理空間并寫入數(shù)據(jù)，構(gòu)造新的索引條目；2）將索引條目寫入內(nèi)存中靜態(tài)數(shù)組的對應(yīng)位置；3）將索引所在Block 整體寫入SSD 盤對應(yīng)的索引Blob 中.

元數(shù)據(jù)的原子性和一致性機(jī)制確保了系統(tǒng)崩潰一致性.系統(tǒng)發(fā)生宕機(jī)等異常時，內(nèi)存緩存數(shù)據(jù)全部丟失，系統(tǒng)重新加載SSD 盤索引分區(qū)中的元數(shù)據(jù)，并根據(jù)元數(shù)據(jù)重新計(jì)算磁盤空閑空間信息，由于元數(shù)據(jù)信息的原子寫入特性，不會出現(xiàn)數(shù)據(jù)不一致和空間泄漏的情況，同時保證元數(shù)據(jù)和數(shù)據(jù)保持一致.

基于NVMe SSD 的元數(shù)據(jù)存儲，充分利用了NVMe SSD 硬件Block 原子寫特性，實(shí)現(xiàn)了元數(shù)據(jù)的原子更新，有效提升了寫性能，保證數(shù)據(jù)、元數(shù)據(jù)一致性；利用DRAM 緩存索引條目，顯著提高系統(tǒng)讀性能.

3.2.2 基于PMEM 的索引

PMEM 是介于內(nèi)存、外存之間的新型存儲介質(zhì)，一方面PMEM 具有非易失、字節(jié)尋址、低讀寫延遲等特性，另一方面，PMEM 具有比DRAM 更大的存儲空間和比NVMe SSD 更小的存儲容量.因此，PMEM更適合存儲元數(shù)據(jù)，這樣可以充分發(fā)揮其延遲低、字節(jié)尋址的特性，同時節(jié)省內(nèi)存資源開銷.另外，借助PMDK[20]框架，不僅能夠?qū)崿F(xiàn)任意大小元數(shù)據(jù)原子寫，而且支持多個元數(shù)據(jù)原子更新的事務(wù).目前業(yè)界常用的PMEM 索引管理方式有B+樹、SkipList 跳表，如DAOS[21]項(xiàng)目中使用B+樹存儲數(shù)據(jù)，MixStore[22]實(shí)現(xiàn)了一種PMEM 的無鎖跳表，支持多線程并發(fā)，大大提高了PMEM 內(nèi)存的訪問效率.與NVMe SSD 采用靜態(tài)表的方式不同，UStore 利用持久內(nèi)存的硬件特性，設(shè)計(jì)了基于PMEM 的索引，整個數(shù)據(jù)空間劃分為相互隔離的Blob 分區(qū)，每個Blob 的元數(shù)據(jù)保存到半持久化的SkipList 中，跳表葉子節(jié)點(diǎn)存儲在PMEM 中，索引節(jié)點(diǎn)則存儲在DRAM 中.一方面，PMEM 索引基于PMEM 的字節(jié)尋址能力實(shí)現(xiàn)了指針尋址，通過索引節(jié)點(diǎn)的地址信息可以直接訪問持久存儲中的葉子節(jié)點(diǎn)，每個葉子節(jié)點(diǎn)保存了下一個葉子節(jié)點(diǎn)地址信息，進(jìn)而實(shí)現(xiàn)基于持久內(nèi)存的鏈表結(jié)構(gòu).另一方面，利用PMEM 持久化特性解決索引節(jié)點(diǎn)掉電丟失問題，借助PMDK 接口中的布局（layout）結(jié)構(gòu)體保存葉子節(jié)點(diǎn)鏈表頭節(jié)點(diǎn)的地址信息，系統(tǒng)初始化時定位到頭節(jié)點(diǎn)并遍歷葉子節(jié)點(diǎn)鏈表，可以在DRAM 內(nèi)存中構(gòu)造整個跳表索引結(jié)構(gòu).UStore 采用半持久化的跳表索引，既能發(fā)揮DRAM 讀寫性能高的優(yōu)勢和提高元數(shù)據(jù)查找性能，又能發(fā)揮PMEM 的持久化、字節(jié)尋址特性，實(shí)現(xiàn)元數(shù)據(jù)的崩潰一致性.

如圖5 所示，第1 級索引實(shí)現(xiàn)為半持久化的SkipList 跳表，第2 級索引為葉子節(jié)點(diǎn)中entry數(shù)組.與NVMe SSD 方式不同，不需要將索引內(nèi)容映射到內(nèi)存空間，而是直接訪問持久內(nèi)存中的索引，因此，第1 級索引查詢的時間復(fù)雜度為O（logn）.

Fig.5 PMEM-based index圖5 基于PMEM 的索引

第1 級索引的更新表現(xiàn)為跳表的插入、刪除操作，涉及PMEM 中空間分配、回收、地址更新等，UStore 使用PMDK 開發(fā)庫提供的持久內(nèi)存事務(wù)實(shí)現(xiàn)索引的原子更新，事務(wù)接口需要記錄事務(wù)日志，開銷較大，但第1 級索引更新只發(fā)生在首次寫Chunk、刪除邏輯分區(qū)流程中，對存儲系統(tǒng)讀寫性能影響有限.第2 級索引中entry長度為8B，而且設(shè)計(jì)為cacheline對齊，因此，第2 級索引直接由PMEM 硬件特性實(shí)現(xiàn)原子更新，entry數(shù)據(jù)更新后調(diào)用clflush 操作確保持久化完成，無需額外的原子性保證機(jī)制.

基于PMEM 的元數(shù)據(jù)存儲，充分利用PMEM 的字節(jié)尋址、持久化特性以及8B 寫入原子性，實(shí)現(xiàn)了接近內(nèi)存的元數(shù)據(jù)訪問性能.

3.2.3 基于硬件KVS 的索引

為了提高本地存儲引擎的性能，業(yè)界嘗試對存儲軟件棧進(jìn)行卸載，以釋放CPU 資源，硬件KVS 就是一種重要的卸載方式.一方面，KVS 內(nèi)部集成掉電保護(hù)的高速存儲芯片，能夠像PMEM 一樣持久化保存索引元數(shù)據(jù)；另一方面KVS 硬件設(shè)備對外提供標(biāo)準(zhǔn)的鍵值接口，軟件棧通過get，put 接口方便地完成任意大小鍵值讀寫，并保證插入數(shù)據(jù)的原子性、一致性，極大地簡化讀寫流程的設(shè)計(jì).但是，KVS 采用PCIe 總線與主機(jī)CPU 通信，會帶來較大延遲開銷.

為了降低KVS 硬件訪問頻率，UStore 在DRAM空間中實(shí)現(xiàn)一個cache 層來緩存熱數(shù)據(jù)索引，采用LRU算法對cache 中索引進(jìn)行替換更新，索引查詢時先從cache 中查找元數(shù)據(jù)，未命中則從KVS 硬件中讀取元數(shù)據(jù)，并將讀取的元數(shù)據(jù)信息插入到cache 中，當(dāng)緩存中元數(shù)據(jù)數(shù)量超過閾值時則根據(jù)上次訪問時間淘汰最近最少訪問的元數(shù)據(jù).cache 實(shí)現(xiàn)為DRAM 內(nèi)存中的一個無鎖SkipList 跳表，支持多個線程并發(fā)訪問，只緩沖最近訪問的熱數(shù)據(jù)，跳表能夠保持較低的深度，確保cache 能夠?qū)崿F(xiàn)非常高的查詢效率.與NVMe SSD 索引緩沖類似，更新索引都需要調(diào)用put 接口將新的鍵值寫入KVS 硬件，寫入成功后同步更新cache，由硬件保證元數(shù)據(jù)更新的原子性，進(jìn)而確保元數(shù)據(jù)、數(shù)據(jù)的一致性.

基于硬件KVS 的元數(shù)據(jù)存儲，充分利用硬件KVS 的加速能力和原子讀寫特性，通過鍵值接口將元數(shù)據(jù)管理卸載到FPGA 硬件，主機(jī)軟件不需要維護(hù)元數(shù)據(jù)信息，降低了軟件棧的復(fù)雜度，有效減少了CPU 資源的開銷.

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)采用的環(huán)境配置信息如表1 所示，PMEM配置為App-Direct 模式，作為持久化的內(nèi)存來使用.主機(jī)操作系統(tǒng)均安裝Fedora34，內(nèi)核版本升級到5.16.11-100，以提供對PMEM 的支持，服務(wù)端分別安裝UStore，Ceph octopus 15.2.16 提供底層存儲服務(wù)，安裝PostgreSQL 數(shù)據(jù)庫軟件.客戶端選擇壓力測試工具FIO 完成I/O 性能測試，選擇benchmarkSQL 完成數(shù)據(jù)庫TPC-C 性能測試.進(jìn)行BlueStore 和UStore對比測試時所采用的硬件環(huán)境和相關(guān)軟件相同.

測試BlueStore 時，使用NVMe SSD 設(shè)備存儲數(shù)據(jù)，PMEM 配置為fsdax 模式，用于存儲BlueStore 的WAL 和DB 文件；測試UStore 時，使用NVMe SSD 存儲數(shù)據(jù)，并分別使用PMEM，NVMe SSD，KVS 設(shè)備存儲元數(shù)據(jù)，對應(yīng)UStore-PM，UStore-NVMe，UStore-KVS 這3 種測試場景.客戶端使用FIO 3.10 進(jìn)行負(fù)載模擬，吞吐率測試配置深度為32，延遲測試配置深度為1，分別測試4KB，8KB，16KB，64KB 這4 種數(shù)據(jù)塊大小的讀寫場景.FIO 工具使用自研bdevUstore ioengin 插件訪問UStore 邏輯卷，使用FIO 自帶的ioengine 插件訪問BlueStore 存儲，完成單節(jié)點(diǎn)塊存儲設(shè)備的性能測試.

4.2 寫性能測試

寫操作性能測試包括單深度的寫延遲、32 深度的吞吐率，主要測試幾種不同I/O 大小數(shù)據(jù)在UStore，BlueStore 這2 種存儲系統(tǒng)的寫流程.UStore 采用數(shù)據(jù)索引分離的設(shè)計(jì)方案，首次寫入數(shù)據(jù)時需要為Chunk 塊分配初始空間，并創(chuàng)建Chunk 索引，首次寫開銷大于覆蓋寫，為了驗(yàn)證設(shè)計(jì)方案，本實(shí)驗(yàn)還對首次順序?qū)懙难舆t做測試分析.

首先測試UStore-PM，UStore-NVMe，UStore-KVS，BlueStore 這 4 種系統(tǒng)在4 KB，8 KB，16 KB，64 KB 四種I/O 數(shù)據(jù)大小場景下的寫延遲，圖6～8 是首次順序?qū)?、順序覆蓋寫、隨機(jī)覆蓋寫3 種場景下的延遲測試結(jié)果.在這3 種測試場景中，BlueStore 的寫延遲都遠(yuǎn)大于UStore，以順序覆蓋寫場景為例，BlueStore 的4KB 寫延遲是UStore 的13 倍，8 KB 寫延遲是UStore的4 倍，16 KB 寫延遲是UStore 的3 倍.UStore 在這3種場景下的寫延遲表現(xiàn)出相同的變化規(guī)律，隨著I/O數(shù)據(jù)塊的增大，寫延遲顯著增加，說明UStore 軟件棧開銷在整個寫流程中占比較小，存儲設(shè)備的寫開銷對整個寫延遲影響較大.I/O 數(shù)據(jù)小于64 KB 時，BlueStore 的寫延遲隨寫入數(shù)據(jù)大小的變化不大，說明此時BlueStore 軟件棧開銷遠(yuǎn)遠(yuǎn)大于硬件讀寫開銷，存儲硬件寫延遲的變化對整個寫延遲影響較小.4 種存儲系統(tǒng)的64 KB 寫延遲都出現(xiàn)較大幅度增長，說明此時硬件延遲成為寫延遲開銷的主要部分.可見，隨著I/O 數(shù)據(jù)塊變大，存儲硬件的寫延遲在整個寫延遲中占比變大，UStore 軟件棧的優(yōu)勢逐漸變小，存儲系統(tǒng)的寫延遲都趨向于硬件設(shè)備延遲.

Fig.6 First sequential write latency圖6 首次順序?qū)懷舆t

Fig.7 Sequential override write latency圖7 順序覆蓋寫延遲

Fig.8 Random override write latency圖8 隨機(jī)覆蓋寫延遲

通過圖6～8 縱向比較可以發(fā)現(xiàn)，相同數(shù)據(jù)大小場景下UStore 隨機(jī)覆蓋寫、順序覆蓋寫的延遲差距很小，首次寫的延遲大于覆蓋寫延遲，例如UStore-PM的4 KB 首次寫延遲比覆蓋寫多1.8 μs，16 KB 首次寫比覆蓋寫多4.2 μs.這是因?yàn)槭状螌憰r需要創(chuàng)建索引、更新索引、持久化索引，覆蓋寫只需要更新索引、持久化索引，創(chuàng)建索引的操作主要在內(nèi)存中完成，因此多了幾個微秒的開銷.BlueStore 寫延遲整體較大，首次寫、順序覆蓋寫采用同樣的實(shí)現(xiàn)機(jī)制，首次寫、順序覆蓋寫延遲基本持平.

通過縱向比較還發(fā)現(xiàn)，UStore 的16 KB 寫延遲較8 KB 寫延遲增長較小，8 KB 寫延遲較4 KB 寫延遲增長顯著.如圖8 所示，UStore-PM 的16KB 隨機(jī)寫延遲是8KB 隨機(jī)寫延遲的1.27 倍，8 KB 隨機(jī)寫延遲是4 KB 隨機(jī)寫延遲的3.4 倍.這是因?yàn)? KB 數(shù)據(jù)采用直寫方式更新Chunk 的初始空間，8 KB，16 KB，64 KB 采用ROW 方式寫入數(shù)據(jù)，執(zhí)行路徑增加較多步驟，包括：分配新空間、遍歷2 級索引、更新索引條目、釋放舊空間等，因而UStore 的8 KB 寫延遲較4 KB寫延遲出現(xiàn)跳躍式增長，16 KB 寫延遲較8 KB 寫延遲則表現(xiàn)出緩慢增長趨勢，64 KB 寫延遲再次出現(xiàn)大幅增加則是由硬件延遲變大導(dǎo)致.

寫滿盤后分別測試順序?qū)?、隨機(jī)寫的性能變化，測試結(jié)果如圖9 和圖10 所示.UStore 順序?qū)憽㈦S機(jī)寫的性能都高于BlueStore，其中4 KB 場景下的性能優(yōu)勢最大，UStore-PM 的4 KB 順序?qū)懲掏侣适荁lueStore的3.2 倍，4 KB 隨機(jī)寫吞吐率是BlueStore 的9.2 倍.測試結(jié)果符合UStore 的設(shè)計(jì)預(yù)期，4 KB 支持原子寫，數(shù)據(jù)直接寫入SSD 空間，因此4 KB 寫性能是UStore的最佳性能，與BlueStore 相比優(yōu)勢明顯.隨著數(shù)據(jù)塊的增大，UStore 領(lǐng)先的優(yōu)勢逐漸減小，UStore-PM 的8 KB順序?qū)懙耐掏侣适荁lueStore 的2.8 倍，16 KB 順序?qū)懶缘耐掏侣适荁lueStore 的1.7 倍.隨機(jī)寫性能表現(xiàn)出同樣的規(guī)律，UStore-PM 的8KB 隨機(jī)寫吞吐率是BlueStore 的7.3 倍，16 KB 隨機(jī)寫吞吐率是BlueStore的2.7 倍.這是由于UStore 采用的ROW 方式實(shí)現(xiàn)超過4 KB 大小的數(shù)據(jù)原子寫，數(shù)據(jù)從ROW 空間遷移到Chunk 初始空間占用了大量的磁盤帶寬，導(dǎo)致UStore 的有效吞吐下降，相比BlueStore 的性能優(yōu)勢顯著下降.當(dāng)數(shù)據(jù)大小增加到64 KB 時，存儲硬件所占開銷比重更大，UStore 的性能優(yōu)勢進(jìn)一步縮小，如圖9 所示，UStore-PM 的64 KB 順序?qū)懲掏侣适荁lueStore 的1.55 倍.

Fig.9 Sequential write performance圖9 順序?qū)懶阅?/p>

UStore 的3 種實(shí)現(xiàn)方式中，在順序?qū)憟鼍跋?，UStore-PM 性能最高，UStore-NVMe 性能最低.根據(jù)硬件特性，PMEM 介質(zhì)訪問延遲最低，支持多線程并發(fā)寫，寫操作吞吐率最高；基于FPGA 的KVS 系統(tǒng)支持多深度異步寫入，訪問延遲介于PMEM 和NVMe SSD 之間，吞吐率基本介于二者之間；UStore-NVMe的元數(shù)據(jù)、數(shù)據(jù)都需要寫SSD 盤，而且空間相鄰數(shù)據(jù)的索引可能出現(xiàn)重復(fù)持久化，寫操作的吞吐率最低.在隨機(jī)寫場景下，UStore-PM 性能最高，但隨著數(shù)據(jù)大小的變化，UStore-KVS 與UStore-NVMe 的性能對比互有高低。這是由UStore-KVS 的元數(shù)據(jù)緩存機(jī)制導(dǎo)致的，在隨機(jī)寫時UStore-KVS 緩存命中率較低，而且變化比較大.

4.3 讀性能測試

本次實(shí)驗(yàn)在盤寫滿前提下，分別對4 KB，8 KB，16 KB，64 KB 大小的數(shù)據(jù)在順序讀和隨機(jī)讀2 種場景下做性能對比測試.由圖11、圖12 可見，所有測試場景中UStore 的讀操作性能都明顯高于BlueStore.以UStore-PM 為例，4 KB 順序讀吞吐率是BlueStore的4.4 倍，4 KB 隨機(jī)讀吞吐率是BlueStore 的4.2 倍，UStore-KVS 和UStore-NVMe 的性能優(yōu)勢更加明顯.這是因?yàn)閁Store 讀流程先查找索引，再經(jīng)過用戶態(tài)驅(qū)動讀取NVMe SSD 中的數(shù)據(jù)，繞過了內(nèi)核軟件棧，避免了操作系統(tǒng)中斷開銷.與寫性能測試不同，相同場景下，UStore-KVS 和UStore-NVMe 的讀性能要高于UStore-PM，因?yàn)樗鼈兊乃饕烤彌_在DRAM 中，讀流程直接從DRAM 中讀取索引元數(shù)據(jù)，性能高于從PMEM 中讀取元數(shù)據(jù).

Fig.12 Random read performanc圖12 隨機(jī)讀性能

隨著數(shù)據(jù)塊的增大，存儲設(shè)備的讀開銷逐漸增大，UStore 讀吞吐率隨之下降，與BlueStore 相比，讀性能優(yōu)勢顯著縮小.以UStore-NVMe 隨機(jī)讀場景為例，8 KB 的吞吐率比4 KB 下降39%，16 KB 的吞吐率比8 KB 下降43%.數(shù)據(jù)大小為64 KB 時，UStore 順序讀、隨機(jī)讀的吞吐率下降到50KIOPS 以下，與BlueStore 的吞吐率差距縮寫到10～30KIOPS.

UStore 的3 種實(shí)現(xiàn)方式中，UStore-PM 的順序讀、隨機(jī)讀性能都低于另外2 種實(shí)現(xiàn)方式，UStore-PM 的元數(shù)據(jù)存儲在PMEM 的葉子節(jié)點(diǎn)中，讀操作需要從PMEM 讀取索 引，UStore-KVS 和UStore-NVMe 的 熱數(shù)據(jù)索引緩沖在DRAM 中，讀操作從內(nèi)存中讀取索引，但是DRAM 空間有限，只能存放部分熱數(shù)據(jù)的索引，緩存未命中時需要從SSD 盤讀取索引信息，最差情況讀性能會下降50%.因此，大規(guī)模存儲場景下，UStore-PM 的整體讀性能仍然高于UStore-KVS 和UStore-NVMe.

4.4 數(shù)據(jù)庫負(fù)載測試

為了對比UStore 和BlueStore 在業(yè)務(wù)負(fù)載場景下的性能表現(xiàn)，本實(shí)驗(yàn)采用TPC-C 基準(zhǔn)測試，將UStore-PM 和BlueStore 這2 種塊設(shè)備格式化為EXT4 類型，掛載為PostgreSQL 數(shù)據(jù)庫的數(shù)據(jù)盤，設(shè)置倉庫數(shù)量為100，向PostgreSQL 導(dǎo)入10GB 業(yè)務(wù)數(shù)據(jù)，使用benchmarkSQL-5.0 測試工具，通過修改并發(fā)線程數(shù)模擬數(shù)據(jù)庫的負(fù)載壓力，測試不同負(fù)載場景下事務(wù)流量和數(shù)據(jù)盤延遲.

測試結(jié)果如圖13 所示，基于UStore-PM 數(shù)據(jù)盤的數(shù)據(jù)庫性能表現(xiàn)優(yōu)異.UStore-PM 的事務(wù)流量是BlueStore 事務(wù)流量的2.8 倍，UStore-PM 的90%尾延遲不足BlueStore 90%尾延遲的50%.隨著并發(fā)線程數(shù)量的增加，這2 種數(shù)據(jù)盤的事務(wù)性能都呈線性增長，UStore-PM 增長的斜率越大，并發(fā)度越高，性能優(yōu)勢越明顯.主要原因是UStore 存儲系統(tǒng)基于無鎖并發(fā)的框架[23]實(shí)現(xiàn)，從根本上避免系統(tǒng)中斷、互斥鎖的開銷，UStore 軟件棧的并發(fā)能力遠(yuǎn)遠(yuǎn)優(yōu)于基于內(nèi)核實(shí)現(xiàn)的BlueStore，可以更好地發(fā)揮PostgreSQL 數(shù)據(jù)庫事務(wù)并行處理能力.

Fig.13 TPC-C performance comparison圖13 TPC-C 性能對比

本實(shí)驗(yàn)中，數(shù)據(jù)庫服務(wù)通過NVMe over RDMA訪問UStore-PM 設(shè)備，BlueStore 的rbd 客戶端只能使用以太網(wǎng)訪問遠(yuǎn)端存儲設(shè)備.為了避免網(wǎng)絡(luò)傳輸?shù)牟町?，?shù)據(jù)庫服務(wù)使用rbd 內(nèi)核驅(qū)動直接訪問本地BlueStore 存儲，因此，數(shù)據(jù)庫服務(wù)訪問UStore-PM 設(shè)備增加了網(wǎng)絡(luò)傳輸?shù)臅r間開銷.本實(shí)驗(yàn)使用了新型高性能RDMA 網(wǎng)卡，收發(fā)延遲在10 μs 以內(nèi)，根據(jù)4.2 節(jié)實(shí)驗(yàn)結(jié)果，UStore-PM 的4 KB 寫延遲比BlueStore小50～80 μs，雖然增加了網(wǎng)絡(luò)傳輸?shù)难舆t開銷，訪問UStore-PM 數(shù)據(jù)盤的延遲仍然小于訪問BlueStore 數(shù)據(jù)盤，因此，數(shù)據(jù)庫事務(wù)訪問數(shù)據(jù)盤次數(shù)越多，UStore事務(wù)延遲的優(yōu)勢越明顯.圖13 中訪問BlueStore 數(shù)據(jù)盤延遲比UStore-PM 數(shù)據(jù)盤多4～5 ms，這部分延遲差距包括多次訪問數(shù)據(jù)盤增加的延遲和BlueStore 驅(qū)動層增加的延遲.隨著并發(fā)量增加，事務(wù)訪問2 種數(shù)據(jù)盤的延遲都出現(xiàn)增大，由于每個數(shù)據(jù)庫事務(wù)訪問數(shù)據(jù)盤的次數(shù)不變，總的延遲差變化不大.

綜上，實(shí)驗(yàn)結(jié)果表明UStore 的吞吐率、單深度延遲都優(yōu)于BlueStore，在4KB 塊大小的場景下存在量級的優(yōu)勢.在3 種場景中，UStore-PM 的寫性能優(yōu)勢突出，但讀性能低于UStore-KVS，UStore-NVMe 的內(nèi)存緩沖模式，因此UStore-PM 更適合數(shù)據(jù)規(guī)模大、寫多讀少的業(yè)務(wù)場景；UStore-NVMe 方式在元數(shù)據(jù)緩沖全部命中的前提下，能夠取得非常好的性能，適合讀寫數(shù)據(jù)比較集中的業(yè)務(wù)場景；UStore-KVS 總體性能接近UStore-PM，CPU 資源占用最小，更適合計(jì)算密集的業(yè)務(wù)場景.在數(shù)據(jù)庫負(fù)載測試中，相比于BlueStore，UStore-PM 在TPC-C 場景表現(xiàn)出較大優(yōu)勢.因此，UStore 能夠靈活適配多種存儲硬件配置和應(yīng)用場景，在提升性能的同時，具有較好的通用性.

5 結(jié)論

持久內(nèi)存、高性能KVS 加速卡、NVMe SSD 等新型存儲硬件的出現(xiàn)，對存儲軟件棧提出了新的要求.本文實(shí)現(xiàn)了一種兼容PMEM、KVS 加速卡、NVMe SSD 等多種存儲介質(zhì)的統(tǒng)一存儲系統(tǒng)UStore，滿足多層次的業(yè)務(wù)需求；提出了一種高效的數(shù)據(jù)布局和管理方法，優(yōu)化數(shù)據(jù)的存儲和訪問性能，利用硬件原子性實(shí)現(xiàn)了數(shù)據(jù)一致性，提升性能的同時增強(qiáng)了系統(tǒng)的穩(wěn)定性；提出一種與物理存儲介質(zhì)形態(tài)解耦的元數(shù)據(jù)設(shè)計(jì)方案，能夠高效地適配不同存儲硬件介質(zhì)和接口，并可根據(jù)硬件特性實(shí)現(xiàn)高效的數(shù)據(jù)塊索引.實(shí)驗(yàn)表明，UStore 顯著提升了讀寫性能，相比BlueStore，UStore-PM 的4 KB 隨機(jī)寫性能提升了8.2 倍，4 KB隨機(jī)讀性能提升了3.2 倍，UStore-KVS 和UStore-NVMe在不同測試場景中均表現(xiàn)出顯著的性能改善.

展望未來，隨著新型器件發(fā)展和持久內(nèi)存產(chǎn)業(yè)化水平的提升，計(jì)算、存儲和網(wǎng)絡(luò)能力都將顯著提升，可能會出現(xiàn)基于持久內(nèi)存等新型器件構(gòu)筑的全新存儲環(huán)境.我們需要重新審視現(xiàn)有的設(shè)計(jì)和優(yōu)化機(jī)制，并設(shè)計(jì)新的算法來適配新的硬件環(huán)境.

作者貢獻(xiàn)聲明：屠要峰提出了文章思路和方案設(shè)計(jì)，撰寫論文；韓銀俊、金浩參與方案實(shí)施和論文修改；陳正華協(xié)助設(shè)計(jì)實(shí)驗(yàn)方案；陳兵指導(dǎo)方案設(shè)計(jì)和論文寫作.