屠要峰 陳正華 韓銀俊 陳 兵 關(guān)東海

1(南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院 南京 211106)2(中興通訊股份有限公司 南京 210012)(tu.yaofeng@zte.com.cn)

近年來，隨著移動通信和物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，數(shù)據(jù)的規(guī)模呈爆發(fā)式增長，傳統(tǒng)的存儲系統(tǒng)已經(jīng)無法滿足不斷增長的海量數(shù)據(jù)存儲的需要.為解決數(shù)據(jù)存儲規(guī)模、數(shù)據(jù)備份、數(shù)據(jù)安全、服務(wù)質(zhì)量、軟件定義等問題，分布式存儲系統(tǒng)應(yīng)運而生.分布式存儲是通過軟件的方法把若干節(jié)點的存儲資源，如磁盤、內(nèi)存等組織起來，對外提供虛擬的統(tǒng)一的塊、文件或?qū)ο蠼涌诘陌葱璐鎯Ψ?wù).

本地文件系統(tǒng)如XFS(extents file system)，EXT4(fourth extended file system)，btrfs(B-tree file system)等，具有成熟、穩(wěn)定的優(yōu)勢，成為分布式存儲系統(tǒng)訪問本地存儲資源的主要方法.應(yīng)用廣泛的分布式存儲系統(tǒng)Ceph的后端存儲FileStore也是基于XFS進(jìn)行存儲訪問.這樣做的優(yōu)勢是利用了文件和對象天然的映射關(guān)系，利用操作系統(tǒng)頁緩存機制緩存數(shù)據(jù)，利用索引節(jié)點(inode)緩存機制緩存元數(shù)據(jù)，同時從操作系統(tǒng)層面保證了磁盤的隔離性.但是這種架構(gòu)也有明顯的缺陷[1]，主要是事務(wù)一致性難以保證，元數(shù)據(jù)管理低效，以及缺乏對新型硬件的支持.鑒于此，Ceph在Jewel版本引入了BlueStore作為后端存儲.BlueStore將對象數(shù)據(jù)的存放方式改為直接對裸設(shè)備進(jìn)行指定地址和長度的讀寫操作，不再依賴本地文件系統(tǒng)提供的POSIX(portable oper-ating system interface of Unix)接口.同時，BlueStore引入了RocksDB數(shù)據(jù)庫保存元數(shù)據(jù)和屬性信息，包括對象的集合、對象、存儲池的omap信息和磁盤空間分配記錄等，BlueStore有效避免了數(shù)據(jù)的雙寫，提升了元數(shù)據(jù)的操作效率，同時借助RocksDB解決了事務(wù)一致性問題.

BlueStore雖然改善了元數(shù)據(jù)效率和事務(wù)一致性，但在實際使用中存在一些明顯的問題[1]，主要包括：

1) RocksDB使用預(yù)寫式日志(write ahead logging, WAL)技術(shù)保證一致性，存在寫放大.RocksDB本身的LSM-Tree(log-structured merge tree)[2]機制也會帶來寫放大.LSM-Tree的數(shù)據(jù)壓緊(compaction)機制還會帶來業(yè)務(wù)的性能抖動.

2) BlueStore的元數(shù)據(jù)信息、屬性信息和小數(shù)據(jù)被存儲到RocksDB中，并在其中多次復(fù)制和序列化，帶來較大的CPU開銷.

3) 為了保證事務(wù)一致性，對小數(shù)據(jù)的更新需要先從磁盤讀取更新后保存到RocksDB中，同時RocksDB有自己的WAL日志，導(dǎo)致Journal of Journal的寫放大問題.

上述3個問題和對應(yīng)的系統(tǒng)開銷，在固態(tài)硬盤(solid state disk, SSD)和機械盤場景下，相對系統(tǒng)整體性能提升帶來的收益來說是值得的，但在持久性內(nèi)存場景下則成為了不必要的負(fù)擔(dān).

PMEM(persistent memory)[3]也稱為非易失內(nèi)存(non-volatile memory, NVM)或存儲級內(nèi)存(storage class memory, SCM)，在本文統(tǒng)稱為PMEM.PMEM因其非易失、字節(jié)尋址和原地更新等特性，成為工業(yè)界和學(xué)術(shù)界研究的熱點.

BlueStore沒有很好利用PMEM內(nèi)存式高速處理和外存式持久化的雙重能力.PMEM具有非易失、字節(jié)尋址特性[4]，可以通過簡化日志的方式保證事務(wù)一致性，減少日志結(jié)構(gòu)引起的數(shù)據(jù)整理和寫放大，以及由此帶來的額外系統(tǒng)開銷和性能瓶頸.與傳統(tǒng)基于塊的存儲設(shè)備相比，PMEM提供了更高的吞吐和更低的延遲.但是，PMEM比SSD容量小且單位存儲成本更高，而且目前商用的PMEM讀寫具有不對稱性，例如通過Intel MLC[5]測得的Intel Optane DC Persistent Memory讀帶寬最高約為6 GBps，而寫帶寬則約為2 GBps.因此，PMEM更適合用來存儲元數(shù)據(jù)和小數(shù)據(jù)，而SSD更適合存儲大塊的數(shù)據(jù)對象.充分發(fā)揮PMEM和SSD存儲介質(zhì)的優(yōu)勢特性，設(shè)計高性能的后端存儲，將為解決傳統(tǒng)存儲的不足帶來了新的機遇.

本文提出了一種基于PMEM和SSD的分布式后端存儲MixStore，通過針對PMEM和SSD特性的組合優(yōu)化設(shè)計，構(gòu)建性能更優(yōu)的本地存儲系統(tǒng)，解決了Ceph現(xiàn)有后端存儲BlueStore的寫放大以及compaction等問題.

1 相關(guān)工作

Ceph現(xiàn)有的BlueStore被設(shè)計為一個面向SSD和HDD(hard disk drive)的存儲引擎，致力于提供快速的元數(shù)據(jù)操作、避免對象(Object)寫入時的一致性開銷，同時解決日志雙寫問題.BlueStore通過將元數(shù)據(jù)保存到RocksDB來實現(xiàn)快速的元數(shù)據(jù)操作.通過Space Allocator進(jìn)行磁盤空間管理，將Object直接寫入塊設(shè)備，去除對文件系統(tǒng)的依賴.同時，BlueStore實現(xiàn)了寫時復(fù)制機制(copy-on-write, CoW)方式的Object更新，從而避免在日志中包含完整的Object數(shù)據(jù)，解決雙寫問題.但是基于RocksDB管理元數(shù)據(jù)存在寫放大問題，RocksDB的compaction操作也會導(dǎo)致性能抖動，影響系統(tǒng)吞吐率.另一方面，在數(shù)據(jù)規(guī)模較大以及EC(erasure code)等應(yīng)用場景中，基于RocksDB的元數(shù)據(jù)管理仍然難以滿足性能要求.即使更換持久性內(nèi)存等更高性能的硬件，所獲得的提升也有限.

以LevelDB[6]和RocksDB[7]為代表的LSM-Tree存儲引擎憑借其優(yōu)異的寫性能成為眾多分布式組件的存儲基石.在大型生產(chǎn)環(huán)境中，例如BigTable[8]，Cassandra[9]，HBase[10]等廣泛部署了各種基于LSM-Tree的本地存儲.LSM-Tree把小的隨機寫通過合并操作變成連續(xù)的順序?qū)懀虼藢DD硬盤的寫入性能有很好的優(yōu)化.相比HDD來說，SSD的順序?qū)懭牒碗S機寫入性能差別較小，所以LSM-Tree對SSD的寫入性能提升有限.為此，WiscKey[11]提出一種基于SSD優(yōu)化的鍵值(key-value, KV)存儲，核心思想是把key和value分離，只有key被保存在LSM-Tree中，而value單獨存儲在日志中.這樣就顯著減小了LSM-Tree的大小，使得查找期間數(shù)據(jù)讀取量減少，并減輕了索引樹合并時不必要的數(shù)據(jù)移動而引起的寫放大.WiscKey保留了LSM-Tree的優(yōu)勢，減少了寫放大，但數(shù)據(jù)訪問時需要進(jìn)行多次MAP映射，且依然存在LSM-Tree固有的compaction過程.SLM-DB[12]基于PMEM和磁盤對LSM-Tree進(jìn)行改進(jìn)，將磁盤上的數(shù)據(jù)從多級樹減少到1級，在PMEM上構(gòu)建B樹加速對磁盤數(shù)據(jù)的訪問，具有低寫入放大和近乎最優(yōu)的讀取放大特性.但在磁盤上數(shù)據(jù)依然需要做compaction操作，同時因為數(shù)據(jù)存放在磁盤，小數(shù)據(jù)的訪問性能較差.NoveLSM[13]是一款基于PMEM的LSM-Tree存儲結(jié)構(gòu)的KV系統(tǒng)，旨在利用PMEM為應(yīng)用提供高吞吐、低延遲的KV存儲，在WAL日志滿的時候，或在compaction受阻時，引入PMEM進(jìn)行加速，是一種改良的LSM-Tree，但沒有完全解決寫放大和compaction的問題.

針對PMEM，NOVA[14]把DRAM和PMEM相結(jié)合，索引存放在DRAM中，日志放在PMEM中，每個inode都有自己的日志，日志通過鏈表進(jìn)行組織，這樣的設(shè)計充分發(fā)揮了PMEM的字節(jié)尋址特性，但因為單位存儲成本較高不適合作為大容量后端存儲.Ziggurat[15]提供了一個分層文件系統(tǒng)，將PMEM和慢速磁盤結(jié)合在一起，通過在線預(yù)測應(yīng)用的訪問模型，把同步的、小的數(shù)據(jù)寫入PMEM，把異步的、大的數(shù)據(jù)寫入磁盤，這種分層放置的策略對有多樣性的訪問模型有效，但對于單一數(shù)據(jù)類型的應(yīng)用將不能充分發(fā)揮PMEM和磁盤的各自的特性.NV-Booster[16]提出了一種基于PMEM的文件系統(tǒng)來加速存儲節(jié)點的對象訪問，通過PMEM中的高效命名空間管理，實現(xiàn)了快速的對象搜索以及對象ID和磁盤位置之間的映射，其優(yōu)化是針對Ceph的FileStore，未解決BlueStore所面臨的問題.此外，以上這些工作都提供基于內(nèi)核態(tài)的本地文件系統(tǒng)，由于系統(tǒng)調(diào)用、內(nèi)存拷貝和中斷而導(dǎo)致較大的性能開銷，并不適合作為分布式存儲的后端.Octopus[17]提出了一種基于PMEM和RDMA(remote direct memory access)的分布式持久存儲文件系統(tǒng)，利用了RDMA可以直接讀寫PMEM的特性，將文件數(shù)據(jù)設(shè)置為全局可見，直接執(zhí)行遠(yuǎn)程讀寫，提高性能；而文件元數(shù)據(jù)則設(shè)置為私有，對應(yīng)的操作由服務(wù)端來執(zhí)行，從而保證安全性和系統(tǒng)數(shù)據(jù)一致性.但該系統(tǒng)缺少對大容量SSD的集成，不適合作為分布式存儲的后端.

KVell[18]是基于NVMe SSD設(shè)計的高效KV存儲，核心設(shè)計思想是簡化CPU的使用，數(shù)據(jù)在SSD上不排序，每個分區(qū)的索引在內(nèi)存中是有序的.這種設(shè)計在每次啟動時需要進(jìn)行索引的重構(gòu)，無法滿足快速重啟動的工程需求.KVell使用頁緩存和LRU(least recently used)算法負(fù)責(zé)磁盤上的空閑空間申請和釋放，省去了磁盤上空閑空間回收和整理的過程.但是當(dāng)磁盤容量快被用完，特別是被覆蓋寫時，大概率觸發(fā)SSD的擦除→拷貝→修改→寫入過程，實際IO性能會大幅下降.Pmemkv[19]是針對持久性內(nèi)存優(yōu)化的本地鍵值數(shù)據(jù)存儲，其底層包含了cmap、csmap、tree3、stree等多種存儲引擎，其中csmap引擎基于SkipList實現(xiàn)，put、get、count等操作的性能隨線程數(shù)擴展，但其remove操作使用了全局鎖，限制了并發(fā)性.

在并發(fā)訪問控制和事務(wù)一致性方面，Harris等人[20]利用指針標(biāo)記的方法解決了DRAM上CAS(compare-and-swap)算法在并發(fā)執(zhí)行節(jié)點插入和刪除操作時，刪除前置節(jié)點會導(dǎo)致插入節(jié)點丟失的問題.David等人[21]基于此研究提出一種無鎖數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)了適用于PMEM的CAS算法，當(dāng)使用CAS指令更新前置節(jié)點的next指針時，同步為該指針添加未持久化標(biāo)記，并在完成持久化后去除此標(biāo)記.其他并發(fā)的更新操作在檢測到未持久化標(biāo)記時，則首先執(zhí)行持久化，以保證更新的線性執(zhí)行.但上述方法中，保存在PMEM中的指針包含了未持久化標(biāo)記，后續(xù)的標(biāo)記移除操作則可能因故障而未被持久化，導(dǎo)致故障恢復(fù)后新的插入操作重復(fù)執(zhí)行指針持久化，產(chǎn)生不必要的性能開銷.PMwCAS[22]通過無鎖持久高效的多字段CAS技術(shù)，解決了多字段更新的原子性問題，大大降低了構(gòu)建無鎖索引的復(fù)雜性，但未提供節(jié)點刪除時資源回收的解決方案.TLPTM[23]通過分配感知和基于壓縮算法的日志優(yōu)化策略設(shè)計了一種基于微日志的持久性事務(wù)內(nèi)存系統(tǒng)，雖然減少了日志的寫入量，但本質(zhì)上還是一種基于日志的事務(wù)系統(tǒng)，沒有解決前述的數(shù)據(jù)雙寫問題.

肖仁智等人[24]從持久索引層面、文件系統(tǒng)層面和持久性事務(wù)等方面對面向PMEM的數(shù)據(jù)一致性相關(guān)工作進(jìn)行了綜述和總結(jié)，并指出在開發(fā)新的一致性的持久內(nèi)存索引方面，未來更多的工作將集中在LSM-Tree和SkipList上.

綜上，現(xiàn)有后端存儲BlueStore固有的寫放大和compaction問題在PMEM上更加突出，業(yè)界針對SSD和PMEM下的LSM-Tree提出了許多改進(jìn)，但仍然避免不了compaction帶來的性能抖動.在構(gòu)建基于持久性內(nèi)存的存儲系統(tǒng)方面業(yè)界提供了一些解決方案，但大多是內(nèi)核態(tài)的實現(xiàn)，存在較多的上下文切換和數(shù)據(jù)拷貝的開銷，并且基于本地文件系統(tǒng)的后端存儲在事務(wù)一致性保證和高效元數(shù)據(jù)訪問方面并不友好，同時PMEM本身由于容量和成本原因并不適合單獨構(gòu)建大規(guī)模分布式存儲系統(tǒng)，因此基于PMEM和SSD的特性聯(lián)合設(shè)計后端存儲存在切實的需求.

2 MixStore架構(gòu)設(shè)計

針對PMEM和SSD的硬件場景，本文設(shè)計了MixStore替換原有的BlueStore，作為Ceph的后端本地存儲.其最大的挑戰(zhàn)是事務(wù)一致性處理和充分發(fā)揮新型硬件的性能，事務(wù)一致性要求一次IO更新操作要么全部成功，要么什么也沒做，確保系統(tǒng)異常崩潰時數(shù)據(jù)的正確性.通?；诒镜匚募到y(tǒng)實現(xiàn)后端存儲時，需要先寫WAL日志，再更新數(shù)據(jù)，但這樣存在嚴(yán)重的寫放大而影響到系統(tǒng)的性能.與此同時，由于本地文件系統(tǒng)在管理文件時使用了多層級inode來管理文件數(shù)據(jù)和元數(shù)據(jù)的存放，但后端存儲也有自己的元數(shù)據(jù)，會導(dǎo)致后端存儲元數(shù)據(jù)到本地文件系統(tǒng)多級元數(shù)據(jù)和數(shù)據(jù)的映射的開銷，所以直接基于裸盤設(shè)計后端存儲更具有性能優(yōu)勢.

MixStore利用PMEM的字節(jié)尋址和持久性特性，把元數(shù)據(jù)和小塊數(shù)據(jù)存放在PMEM中，基于SSD裸盤，把對齊的大塊數(shù)據(jù)對象存儲在SSD上.PMDK(persistent memory development kit)[25]是Intel提供的適用于持久性內(nèi)存的開源庫，專門針對PMEM進(jìn)行了優(yōu)化.基于PMDK事務(wù)機制可以確保在節(jié)點故障后，所有內(nèi)存操作都回滾到最后提交的狀態(tài)，PMDK實現(xiàn)了線程內(nèi)的原子性，但沒有提供隔離性.MixStore提出了一種基于PMEM的Concurrent SkipList索引管理機制，基于PMDK事務(wù)、區(qū)段標(biāo)志位以及待刪除列表的方式保證節(jié)點修改的事務(wù)一致性、原子性和并發(fā)性.同時提出了一種高效的數(shù)據(jù)對象更新管理方法.針對PMEM和SSD各自的特性，優(yōu)化數(shù)據(jù)對象的訪問性能.

MixStore的系統(tǒng)架構(gòu)如圖1所示.作為用戶態(tài)后端存儲，MixStore對外提供ObjectStore接口，內(nèi)部分為元數(shù)據(jù)管理和數(shù)據(jù)對象的管理.MixStore的核心創(chuàng)新是在PMEM上實現(xiàn)了基于Concurrent SkipList的索引替換原有RocksDB所實現(xiàn)的元數(shù)據(jù)管理功能，去除了對RocksDB的依賴；通過直接管理Object元數(shù)據(jù)，避免了WAL和LSM-Tree機制帶來的寫放大和compaction時的性能抖動；同時避免了序列化和反序列化帶來的CPU開銷；小塊的數(shù)據(jù)存放于PMEM中，并優(yōu)化了小IO的事務(wù)一致性處理方法，避免了BlueStore的Journal of Journal的問題，對于大塊的數(shù)據(jù)對象，首尾非最小可分配大小(minimal allocate size, MAS)對齊的部分存放在PMEM中，中間MAS對齊部分使用CoW機制存儲到SSD中.得益于PMEM的字節(jié)尋址特性，對于非對齊寫和小IO有更好的優(yōu)化.

Fig. 1 System architecture of MixStore圖1 MixStore系統(tǒng)架構(gòu)圖

在索引結(jié)構(gòu)的選擇上，現(xiàn)有的LSM-Tree在WAL日志更新，多層級查找及序列化方面開銷巨大[13]，且無法利用PMEM的字節(jié)尋址和低延遲特性，顯然不適用于PMEM.有序鏈表因為O(N)的較高時間復(fù)雜度消耗亦不適合用作索引結(jié)構(gòu).對于樹形結(jié)構(gòu)，數(shù)據(jù)量的變化通常需要對樹結(jié)構(gòu)重新平衡，重新平衡操作可能會影響樹結(jié)構(gòu)的較大范圍，這將需要在較多樹節(jié)點上使用互斥鎖.相比樹結(jié)構(gòu)，SkipList具有更好的局部性，更適合并發(fā)訪問修改[26-27].對SkipList的操作只會影響到節(jié)點本身以及前后插入的節(jié)點，在更改SkipList結(jié)構(gòu)時不需要鎖住和同步整個SkipList數(shù)據(jù)，具有更好的并發(fā)性.MixStore選擇SkipList作為索引結(jié)構(gòu)，同時基于PMEM實現(xiàn)了事務(wù)一致性和并發(fā)性.

在寫放大方面，PebblesDB[28]顯示，插入5億個鍵值對時，平均鍵值大小100 B，共寫入45 GB數(shù)據(jù)，RocksDB實際寫入了1 868 GB數(shù)據(jù)，寫放大率達(dá)42倍.對于SkipList來說，只需要額外一個指針，加上中間層次節(jié)點，平均一個鍵值對額外增加16 B，寫放大為0.16倍，遠(yuǎn)遠(yuǎn)少于RocksDB的寫放大.對于每個100 B鍵值加上SkipList管理開銷16 B，可以管理NVMe SSD上的4 KB的數(shù)據(jù)塊，實際元數(shù)據(jù)最多消耗僅為數(shù)據(jù)量的2.8%.

在時間效率方面，SkipList通過維護(hù)一個多層次的鏈表，且與下面一層鏈表元素的數(shù)量相比，每一層鏈表中的元素的數(shù)量更少.算法首先在最稀疏的層次進(jìn)行搜索，直至需要查找的元素在該層2個相鄰的元素中間.這時，算法將跳轉(zhuǎn)到下一個層次，重復(fù)剛才的搜索，直到找到需要查找的元素為止[29].SkipList與平衡二叉樹一樣可提供時間復(fù)雜度為O(logN)查找、插入和刪除操作[30]，而無需像B樹、紅黑樹或AVL樹所要求的那樣，進(jìn)行復(fù)雜的樹平衡或頁面拆分，并且實現(xiàn)起來更加簡單和簡潔.

在數(shù)據(jù)布局方面，根據(jù)DRAM，PMEM，SSD各自特性和優(yōu)勢，合理搭配使用以充分挖掘系統(tǒng)的性能.SSD容量最大，用于存儲具體的數(shù)據(jù)內(nèi)容，PMEM隨機讀寫性能好，且具有持久性，用于存儲元數(shù)據(jù)信息、磁盤空間分配信息、屬性信息等，同時還存儲非MAS對齊的臨時的數(shù)據(jù)內(nèi)容.而對于DRAM，性能相比PMEM更好，用作熱點數(shù)據(jù)和元數(shù)據(jù)的緩存.對于MAS對齊的數(shù)據(jù)首先寫入DRAM，然后持久化到SSD中，但在DRAM中仍然保留，直至后續(xù)被LRU淘汰.

在事務(wù)一致性方面，PMDK libpmemobj庫實現(xiàn)了事務(wù)機制，提供更新原子性，以及崩潰一致性保證.通過Concurrent SkipList設(shè)計，基于PMDK實現(xiàn)了強一致的元數(shù)據(jù)管理，而不必額外使用日志機制，從而避免了Journal of Journal問題.但是PMDK未提供足夠的隔離性，當(dāng)多個線程并發(fā)執(zhí)行事務(wù)操作時，對共享資源的訪問仍然需要額外的隔離機制.MixStore通過區(qū)段標(biāo)志位方式進(jìn)行并發(fā)控制訪問，解決了多線程隔離性問題.對于PMEM中非MAS對齊的小數(shù)據(jù)更新使用ntstore或clwb指令通過CoW方式直接寫入.因為大塊數(shù)據(jù)使用ntstore指令具有更好的性能表現(xiàn)[31]，所以MixStore對于大于等于256 B的數(shù)據(jù)采用ntstore的方式進(jìn)行存儲，而對于小于256 B的數(shù)據(jù)采用clwb的方式進(jìn)行存儲.

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

本節(jié)詳細(xì)描述MixStore在元數(shù)據(jù)管理和數(shù)據(jù)對象管理方面的關(guān)鍵技術(shù).

3.1 基于Concurrent SkipList的元數(shù)據(jù)管理

MixStore的元數(shù)據(jù)通過基于PMEM的SkipList進(jìn)行管理，內(nèi)存結(jié)構(gòu)的SkipList可以基于CAS指令實現(xiàn)數(shù)據(jù)的并發(fā)更新機制，但在PMEM上應(yīng)用CAS算法面臨新的挑戰(zhàn).

現(xiàn)有的Cache Coherency模型是針對DRAM的，當(dāng)CAS操作完成時，數(shù)據(jù)在CPU Cache間保持一致，但對于PMEM，仍然需要額外的clflush操作，才能完成持久化.因此，操作原子性被破壞，如果在斷電時僅完成了指針的更新，而沒有持久化到PMEM，則在多線程并發(fā)更新訪問時，會導(dǎo)致數(shù)據(jù)結(jié)構(gòu)的損壞，產(chǎn)生內(nèi)存泄漏和一致性問題.

3.1.1 元數(shù)據(jù)插入機制

與David等人[21]提出的無鎖數(shù)據(jù)結(jié)構(gòu)不同，MixStore使用一種易失區(qū)段標(biāo)記來解決并發(fā)操作一致性問題，即將SkipList分為多個區(qū)段，并在DRAM中保存每個區(qū)段的更新標(biāo)記.更新操作在完成前置節(jié)點查找后，通過CAS指令將對應(yīng)區(qū)段設(shè)置為更新中，以與同區(qū)段的其他更新操作互斥.更新標(biāo)記保存在DRAM而不是PMEM中，以提升訪問效率，并簡化故障恢復(fù)處理.區(qū)段級而不是節(jié)點級的更新標(biāo)記則可以縮減內(nèi)存使用量，并有助于解決插入和刪除并發(fā)時的節(jié)點丟失問題.為了解決跨區(qū)段更新的問題，在SkipList中引入dummy節(jié)點作為區(qū)段邊界，以保證前置節(jié)點和待插入節(jié)點總是在一個區(qū)段中.此時，僅同區(qū)段的更新操作需要互斥，不同區(qū)段的更新操作可以并發(fā)執(zhí)行，而查找操作不需要互斥，完全是并發(fā)執(zhí)行的.

以一個2區(qū)段的SkipList為例，新元素的插入操作如圖2所示，首先根據(jù)待插入元素d所屬區(qū)段設(shè)置對應(yīng)的更新標(biāo)記，并開啟PMDK事務(wù)，然后將待插入元素d的next指針指向x(x為區(qū)段中第1個元素時，則指向該區(qū)段的起始dummy節(jié)點)，通過CAS操作將元素c的指針指向元素d.此時，CPU cache中的插入操作完成，元素d對查找操作可見.接下來，提交PMDK事務(wù)將更新操作持久化到PMEM中，并復(fù)位SkipList的區(qū)段更新標(biāo)記.此時，CPU cache和PM中的數(shù)據(jù)視圖達(dá)成一致，整個插入操作完成.對于待插入元素的高度超過1的情況，由于上層list在故障恢復(fù)時可以通過底層的數(shù)據(jù)進(jìn)行重建，因此可以僅通過CAS操作進(jìn)行更新，無需主動執(zhí)行持久化操作.

Fig. 2 Metadata insertion mechanism圖2 元數(shù)據(jù)插入機制

為了進(jìn)一步減少同區(qū)段的并發(fā)沖突，插入時的查找操作可以使用二次確認(rèn)(double check)的方式，即首先遍歷SkipList確定新元素的插入位置，然后設(shè)置區(qū)段更新標(biāo)記，并再次檢查前置節(jié)點的next指針，確定是否需要重新執(zhí)行查找操作.完整的節(jié)點插入流程描述如算法1.

在節(jié)點插入時需要同時更新本節(jié)點的next指針和前一節(jié)點的next指針，把這2個指針更新放在同一PMDK事務(wù)中執(zhí)行，確保系統(tǒng)的崩潰一致性，避免斷電導(dǎo)致的各類異常，例如數(shù)據(jù)部分持久化導(dǎo)致的內(nèi)存區(qū)域泄漏、SkipList鏈表斷裂等情況.

算法1.插入節(jié)點Insert(node).

①pre←SearchPrevious(node.key);

②MarkRange(node.key);

③ ifpre.next.key

④pre←SearchPrevious(node.key);

⑤ end if

⑦node.next←pre.next;

⑧pre.next←node;

⑩UnmarkRange(node.key).

3.1.2 元數(shù)據(jù)刪除及查詢機制

元素刪除操作與插入操作類似，需要通過區(qū)段更新標(biāo)記進(jìn)行互斥.與插入操作不同的是，元素從SkipList移除后，由于可能有其他線程正在執(zhí)行查找操作，其內(nèi)存區(qū)域不能立即釋放.同時，在等待釋放期間，為了避免異常斷電導(dǎo)致持久內(nèi)存泄漏，待刪除的元素需要進(jìn)行妥善的跟蹤管理.

MixStore使用待刪除列表解決上述問題.如圖3所示，首先為每個線程維護(hù)一個SkipList訪問事件時戳，線程每次完成SkipList的訪問后，時戳加1.同時，每個線程有一個保持在持久內(nèi)存中的待刪除元素列表，該列表實際由2個數(shù)組和對應(yīng)的2個時戳向量組成，在當(dāng)前數(shù)組滿時互相交換，并在符合特定條件時清空備用數(shù)組.時戳向量中記錄了特定時刻所有線程的時戳值，線程時戳和時戳向量均無需持久化，在啟動時初始化為0即可.元素從SkipList中刪除時，會被暫存到待刪除列表，同時更新此刻的時戳向量.

Fig. 3 Metadata deletion mechanism圖3 元數(shù)據(jù)刪除機制

以刪除元素c為例，首先設(shè)置區(qū)段更新標(biāo)記，并開啟PMDK事務(wù)，然后使用CAS操作將元素b的next指針指向元素x.此時，元素c對后續(xù)的查找操作不可見，但仍然可能有查找過程正在訪問元素c.然后，元素c被加入待刪除列表，提交PMDK事務(wù)完成持久化，同時復(fù)位區(qū)段更新標(biāo)記.接下來，更新時戳向量，記錄當(dāng)前時刻所有線程的時戳值.顯然，刪除操作發(fā)生在此時戳向量之前，當(dāng)后續(xù)某一時刻的時戳向量嚴(yán)格大于該值時，即每個線程的時戳都大于舊值時，元素c的內(nèi)存可以被釋放.具體而言，在更新當(dāng)前時戳向量后，將當(dāng)前時戳向量與備用數(shù)組的時戳向量進(jìn)行比較，并確定是否清空備用數(shù)組.完整的節(jié)點刪除流程描述如算法2所示.

算法2.刪除節(jié)點Remove(key).

①pre←SearchPrevious(key);

②MarkRange(key);

③ ifpre.next.key≠keythen

④pre←SearchPrevious(key);

⑤ end if

⑥curr←pre.next;

⑧pre.next←curr.next;

⑨AddToSwaplist(curr);

在進(jìn)程重啟后的故障恢復(fù)階段，由于待刪除列表中的元素仍然可能會被其他線程的恢復(fù)過程訪問，故保留待刪除列表中的元素，并將2個時戳向量重置為0.此時，待刪除列表中的元素被延遲到后續(xù)刪除操作中進(jìn)行清理.

與插入和刪除不同，查詢操作不需要關(guān)注區(qū)段標(biāo)記.節(jié)點插入時，鏈表指針的更新通過原子操作完成，從鏈表中刪除的節(jié)點則首先保存在額外的待刪除列表中，直到查詢操作完成后相關(guān)內(nèi)存才被釋放.因此，查詢操作是完全并發(fā)的，不存在等待時間，故而具備較高的性能和延遲一致性表現(xiàn).

3.2 數(shù)據(jù)對象管理

MixStore充分利用PMEM的字節(jié)尋址特性，來優(yōu)化Object的寫入性能.一方面，Object的元數(shù)據(jù)使用存儲在PMEM中的SkipList進(jìn)行管理，另一方面，對于非對齊IO和隨機小IO，也利用PMEM，通過不同的寫入策略進(jìn)行優(yōu)化.

雖然SSD有較好的隨機讀寫性能，但相比于順序讀寫仍有所降低.為此，設(shè)定SSD的最小分配大小MAS，對于普通的SATA SSD來說，MAS=16 KB.對于NVMe SSD來說，因為有更好的隨機讀寫性能，我們設(shè)定MAS=4 KB.通過數(shù)據(jù)寫入策略的設(shè)定，有效減少了SSD的隨機讀寫，進(jìn)一步優(yōu)化系統(tǒng)的性能.

Object更新時，小于MAS的數(shù)據(jù)被直接寫入PMEM，后續(xù)小IO寫入也直接在PMEM中進(jìn)行追加更新和合并，從而有效減少了SSD的磨損和閃存轉(zhuǎn)換層(flash translation layer, FTL)頻繁垃圾回收(garbage collection, GC)導(dǎo)致的性能抖動.對于此類數(shù)據(jù)，如圖4左側(cè)部分所示，BlueStore采用DeferredWrite策略，即首先從SSD讀取舊數(shù)據(jù)與新數(shù)據(jù)進(jìn)行合并，獲得block對齊的待更新數(shù)據(jù)塊，然后將待更新數(shù)據(jù)塊和元數(shù)據(jù)作為WAL寫入RocksDB.最后，異步執(zhí)行數(shù)據(jù)的In-Place更新，并在完成數(shù)據(jù)寫入后刪除WAL.這種方式導(dǎo)致在構(gòu)建WAL時即需要執(zhí)行SSD數(shù)據(jù)讀取，且增加了PMEM的寫入數(shù)據(jù)量.與BlueStore不同，MixStore對異步寫入的數(shù)據(jù)不使用In-Place更新策略，如圖4右側(cè)部分所示，MixStore將非對齊小IO直接寫入PMEM，然后異步執(zhí)行SSD讀取操作并進(jìn)行CoW異地更新.MixStore面向更高性能的PMEM和SSD設(shè)計，由于數(shù)據(jù)的不連續(xù)分布對SSD設(shè)備的讀性能影響要遠(yuǎn)小于HDD，因此選擇CoW異地更新而不是In-Place更新，從而避免了構(gòu)建WAL，降低了PMEM寫入數(shù)據(jù)量；此外，PMEM的高性能也可以更好的支撐不連續(xù)的讀取操作，使得MixStore可以使用更惰性的數(shù)據(jù)回寫策略，從而提升非對齊小IO的合并概率，減少最終的SSD寫入次數(shù)和數(shù)據(jù)的碎片化.

Fig. 4 Comparison of unaligned IO processing圖4 小IO數(shù)據(jù)更新流程對比

對于大于MAS的更新操作，則首先進(jìn)行MAS對齊，將其切分為3個部分，即首尾非MAS對齊的部分和中間MAS對齊的部分.對于首尾非對齊部分使用與小IO相似的方式處理，對齊部分則使用CoW策略，在寫入SSD后更新元數(shù)據(jù)信息.具體而言，整個更新操作分為2個階段，即首先將中間MAS對齊部分異地寫入SSD，首尾非對齊部分寫入PMEM，然后將所有的元數(shù)據(jù)修改在一個PMDK事務(wù)中完成.

Object讀取時，通過訪問SkipList獲取數(shù)據(jù)存放位置信息，首選從SSD中讀取本次IO涉及的數(shù)據(jù)區(qū)域，然后從PMEM中讀取非對齊的小IO增量，并進(jìn)行必要的合并即可.得益于PMEM的隨機訪問性能，對數(shù)據(jù)的碎片化有更高的容忍度，讀性能仍然可以保持較高的水平.

MixStore根據(jù)PMEM的可用容量和數(shù)據(jù)的碎片化情況決定是否執(zhí)行合并操作，PMEM讀取4 KB數(shù)據(jù)的延遲通常不超過5 μs，而NVMe SSD的4 KB讀延遲通常在100 μs左右.MixStore在讀操作中檢查數(shù)據(jù)的碎片化情況，當(dāng)碎片數(shù)量超過閾值以后，觸發(fā)合并操作，合并后的數(shù)據(jù)使用CoW的形式進(jìn)行更新，以避免In-Place更新可能的一致性問題.碎片閾值是動態(tài)的，在PMEM容量充足時，碎片閾值較高，并隨著可用容量的減少而逐步降低.

4 實驗及分析

4.1 實驗環(huán)境

本實驗采用的硬件配置信息如表1所示，實驗在一個由40 GbE以太網(wǎng)交換機連接的4節(jié)點集群上完成，測試使用的持久內(nèi)存為Intel最新推出的Optane DC持久性內(nèi)存，單條容量為256 GB，NVMe SSD為Intel的P4610，單盤容量為1.6 TB.PMEM可以配置為App-Direct或Memory這2種工作模式，由于本實驗都是把PMEM作為持久存儲來使用，所以采用App-Direct模式.本實驗對比BlueStore和MixStore測試時所采用的硬件環(huán)境相同.

Table 1 Experiment Configuration表1 實驗環(huán)境配置

所有主機均安裝Fedora release 29，內(nèi)核版本升級到4.18.16-300，以提供對PMEM的支持.測試基于Ceph Luminous 12.2.12或其修改版本完成，使用FIO 3.10進(jìn)行負(fù)載模擬.

Ceph集群部署在其中3臺安裝了PMEM和NVMe的主機上，PMEM配置為fsdax模式.另一臺主機作為客戶端運行FIO程序，該主機上實際未安裝PMEM和NVMe設(shè)備.

4.2 性能對比

測試BlueStore時，PMEM作為塊設(shè)備使用，用于存儲WAL和DB數(shù)據(jù)，SSD用于保存對象數(shù)據(jù).測試MixStore時，PMEM格式化為ext4-dax，然后通過MMAP轉(zhuǎn)換為持久內(nèi)存使用，PMEM用于存儲索引和小塊數(shù)據(jù)，大塊對象數(shù)據(jù)保存在SSD上.

本次測試使用FIO工具的rbd ioengine訪問Ceph RBD接口，后端為2副本存儲池.為了更接近真實負(fù)載，F(xiàn)IO的隊列深度被設(shè)置為32，而不是更大的值.每次測試使用20個FIO客戶端分別對20個大小為50 GB的RBD Image進(jìn)行讀寫，測試過程持續(xù)5 min.

4.2.1 寫性能

本次測試覆蓋了小IO隨機寫入和大IO順序?qū)懭?類場景.對于隨機寫入，為了進(jìn)一步確認(rèn)BlueStore和MixStore針對不同數(shù)據(jù)大小的寫入策略差異，分別測試了2 KB，4 KB，16 KB的數(shù)據(jù)寫入.對于順序?qū)懭?，分別測試了64 KB，128 KB，256 KB的數(shù)據(jù)寫入.

每組數(shù)據(jù)測試完成后，重啟全部OSD(object storage daemon)節(jié)點，以排除緩存等因素的干擾.

小IO隨機寫入的性能如圖5所示，可以看到，對于所有隨機寫入場景MixStore均有優(yōu)于BlueStore的表現(xiàn)，其中4 KB寫入高出約59%，這顯然得益于MixStore的高效原數(shù)據(jù)管理和事務(wù)日志的消除.對于2 KB隨機寫，BlueStore和MixStore均使用PMEM進(jìn)行數(shù)據(jù)暫存，不同的是，BlueStore需要執(zhí)行read-merge-write操作，因此最終寫入PMEM的為包含4 KB數(shù)據(jù)塊的事務(wù)日志，而MixStore則直接將2 KB的數(shù)據(jù)以及相關(guān)元數(shù)據(jù)寫入PMEM.測試過程中，通過iostat或pcm-memory.x可以觀察到MixStore消除了NVMe讀操作，PMEM寫帶寬約為BlueStore的一半.但由于NVMe磁盤實際負(fù)載較小，最終MixStore測試結(jié)果僅表現(xiàn)出與4 KB類似的優(yōu)勢，領(lǐng)先BlueStore約56%.對于16 KB的隨機IO，MixStore領(lǐng)先約34%，一方面，MixStore更高效的元數(shù)據(jù)操作釋放了NVMe的性能，另一方面，對于16 KB的數(shù)據(jù)，NVMe寫操作在整個請求處理開銷中的占比上升，導(dǎo)致最終的性能優(yōu)勢不如4 KB數(shù)據(jù)明顯.MixStore的平均延遲和尾延遲也呈現(xiàn)出和IOPS相同的優(yōu)勢，平均延遲約為BlueStore的63%～75%，尾延遲約為BlueStore的72%～84%.

Fig. 5 Comparison of random write圖5 隨機寫測試對比

如圖6所示，對于大IO順序?qū)懭?，MixStore和BlueStore基本表現(xiàn)出相同的性能，平均延遲也基本相同.這是因為對于64 KB以上的寫請求，2個系統(tǒng)的處理策略基本相同.較大的數(shù)據(jù)尺寸也導(dǎo)致請求處理的主要開銷來自于SSD寫入操作，軟件棧的差異被進(jìn)一步削弱.即便如此，由于具備更好的元數(shù)據(jù)操作并發(fā)性，MixStore仍然表現(xiàn)出了更好的尾延遲，約為BlueStore的54%～91%.

Fig. 6 Comparison of sequential write圖6 順序?qū)憸y試對比

4.2.2 讀性能

對于讀操作，本次測試選擇了與寫操作相同的數(shù)據(jù)特征，即針對2 KB，4 KB，16 KB的隨機讀取，以及64 KB，128 KB，256 K的順序讀取場景進(jìn)行測試.同樣，每組測試完成后重啟所有OSD，以消除緩存的干擾.

對于小IO隨機讀，如圖7所示，MixStore和BlueStore有基本相同的IOPS和平均延遲，這是因為在排除緩存干擾后，讀操作的開銷主要來自于磁盤數(shù)據(jù)讀取.而較大的寫入總量也導(dǎo)致讀操作更多的是從SSD而不是PMEM讀取數(shù)據(jù)，因此不同數(shù)據(jù)大小的測試之間并未體現(xiàn)出差異.但得益于MixStore元數(shù)據(jù)訪問的高并發(fā)性，在16 KB讀取測試中，MixStore的尾延遲表現(xiàn)出了23%的降低.

Fig. 7 Comparison of random read圖7 隨機讀測試對比

對于大IO順序讀，如圖8所示，受限于本次測試的網(wǎng)絡(luò)環(huán)境，BlueStore和MixStore未能體現(xiàn)出差別，僅64 KB順序讀MixStore體現(xiàn)出約21%的尾延遲降低.128 KB及256 KB的性能制約則更多來自于網(wǎng)絡(luò)傳輸.

Fig. 8 Comparison of sequential read圖8 順序讀測試對比

5 結(jié) 論

現(xiàn)有的分布式存儲的后端存儲存在著明顯的寫放大和compaction消耗.持久內(nèi)存具備字節(jié)尋址，接近DRAM性能，掉電不丟數(shù)據(jù)等特性.但持久內(nèi)存容量較小，更適合存放數(shù)據(jù)的元數(shù)據(jù)或小的數(shù)據(jù)的緩存，相反SSD容量較大，順序讀寫性能更優(yōu)，更適合存放大塊的數(shù)據(jù).MixStore充分利用持久內(nèi)存和磁盤各自的特性，把兩者結(jié)合起來，通過構(gòu)建Concurrent SkipList進(jìn)行精細(xì)的索引元數(shù)據(jù)組織，以及通過惰性的CoW的數(shù)據(jù)存放機制，提供了高性能的后端存儲，有效減少了寫放大和避免了compaction帶來的消耗.實驗顯示，相比BlueStore，MixStore的寫吞吐提升59%，寫時延降低了37%，有效地提升了系統(tǒng)的性能，并且具有更好的讀寫尾時延表現(xiàn).展望未來，隨著新型器件的發(fā)展和持久內(nèi)存產(chǎn)業(yè)化水平的提升，計算、存儲和網(wǎng)絡(luò)能力都將顯著提升，可能會出現(xiàn)基于持久內(nèi)存等新型器件構(gòu)筑的全新存儲環(huán)境.我們需要重新審視現(xiàn)有的設(shè)計和優(yōu)化機制，并設(shè)計新的算法來適配新的硬件環(huán)境.