面向非易失性內存的持久索引數據結構研究綜述

王永鋒，陳志廣

中山大學計算機學院，廣東 廣州 510006

1 引言

非易失性內存是一種新興的存儲介質，其具備字節(jié)可尋址、內存級別讀寫時延的特性，這給當前大量的存儲系統(tǒng)帶來了根本性的變革。非易失性內存正在迅速發(fā)展，現有的大部分非易失性內存（如相變內存[1]、STT-RAM[2]等）仍處于研究階段，但由美光科技有限公司和英特爾聯(lián)合研制的傲騰持久內存（基于3D XPoint[3]）已經發(fā)布，并且投入市場。由此，在存儲系統(tǒng)中盡可 能發(fā)揮非易失性內存性能優(yōu)勢的需求越發(fā)迫切。其中，面向非易失內存研發(fā)新型持久索引數據結構是解決該問題的關鍵。

在存儲系統(tǒng)的設計與實現中，持久索引數據結構是核心之一。文件系統(tǒng)中文件路徑到索引節(jié)點的尋址、大文件中偏移量到指定數據塊的尋址、鍵值存儲系統(tǒng)中根據鍵尋找值的數據結構、數據庫中的聚集索引等，都需要持久存儲的索引數據結構，且這些持久索引數據結構的實現對系統(tǒng)本身的性能至關重要。但這些持久索引數據結構目前大多面向傳統(tǒng)存儲設備進行優(yōu)化，而不能高效利用非易失性內存的硬件特性。將這些持久索引數據結構在非易失性內存上重新設計實現，并面向非易失性內存的硬件特性進行優(yōu)化，能夠大大降低存儲系統(tǒng)的時延、提升吞吐量。

近年來，已經有一些工作對非易失性內存上的存儲系統(tǒng)進行了深入的探討和研究。陳游旻等人[4]在大數據環(huán)境下分析了基于新型存儲硬件進行存儲系統(tǒng)構建的挑戰(zhàn)和趨勢；Liu H K等人[5]對非易失性內存下的內存架構設計、持久內存管理、性能優(yōu)化和功耗管理、編程框架以及非易失性內存之上的應用進行了全面的綜述；Lersch L等人[6]將基于模擬非易失性內存設計的有序索引數據結構進行分析，并在英特爾傲騰持久內存上進行了測試；Hu D K等人[7]則針對面向非易失性內存構建的哈希表進行了測試和分析。另外，鄧鎮(zhèn)龍等人[8]將非易失內存與MPIIO相結合，大大提升了應用在高性能集群上的讀寫性能；楊青霖等人[9]提出的高效數據緩存方法顯著提升了存儲系統(tǒng)的讀寫性能。這些工作對在非易失性內存上設計存儲系統(tǒng)具有重要的指導意義。本文從持久索引數據結構的設計出發(fā)，對不同的設計之間的差異進行細粒度的對比。

提高持久索引數據結構的性能是實現低時延、高吞吐的現代存儲系統(tǒng)亟須解決的問題。針對大量在非易失性內存上優(yōu)化持久索引數據結構的工作，筆者對其進行分類、匯總、對比，厘清索引數據結構的發(fā)展主線，總結其中的關鍵挑戰(zhàn)，并對其發(fā)展趨勢進行展望。

2 持久索引數據結構

索引數據結構是一種能夠存儲鍵值對映射的數據結構。常用的數組僅能實現高效的查詢，無法實現高效的插入操作，而設計良好的索引數據結構對于查詢和插入操作，都能達到對數時間復雜度，甚至是常數時間復雜度，這樣的性能優(yōu)勢使其在內存系統(tǒng)和外存系統(tǒng)中均得到廣泛應用。索引數據結構面向的場景種類繁多，針對不同的場景，索引數據結構有多種不同的實現，本文關注需要持久存儲在存儲設備上的索引數據結構，這樣的索引數據結構被稱為持久索引數據結構（以下簡稱索引數據結構）。

2.1 索引數據結構的分類

在不同的場景中，對索引數據結構中存儲的數據有不同的假定。構建在關系型數據庫中的索引數據結構往往需要處理大量的范圍查詢，即查詢在某個區(qū)間內的所有鍵值對。為了高效支持范圍查詢，索引數據結構需要維護數據的有序性，并針對范圍查詢進行優(yōu)化。而在一些鍵值存儲系統(tǒng)中，可能僅輸入指定的鍵，要求系統(tǒng)返回對應的值，不需要范圍查詢，此時底層的索引數據結構就不需要額外的開銷來維護數據的有序性，相鄰的鍵值對可以存放在存儲設備上的任意位置。因此，根據其內部數據結構對數據有序性的維護情況，可以將索引數據結構分為有序索引數據結構和無序索引數據結構。

有序索引數據結構需要嚴格維護數據結構中的有序性。對于每一次寫入操作，有序索引數據結構都需要根據插入的數據對整體的結構進行修改以保證有序性，因此范圍查詢的性能最好。哈希表完全不維護數據結構中的有序性，因此一般而言額外開銷最小，但無法對范圍查詢進行優(yōu)化。另外，在有序索引數據結構中，維護有序性會帶來大量開銷，因此一些面向寫優(yōu)化的有序索引數據結構會放松一部分對有序性的約束，從而提升寫性能。

除了傳統(tǒng)索引，新興的學習索引（learning index）將索引任務變?yōu)橐粋€回歸問題，能夠根據輸入數據自適應地調整數據的存放模式。

2.2 面向非易失性內存的索引數據結構關鍵問題

為了能夠讓索引數據結構在傳統(tǒng)的存儲設備（如機械硬盤、固態(tài)硬盤）中進行持久存儲，并且高效地利用硬件特性，很多研究人員進行了大量的研究工作。隨著新型存儲設備（如非易失性內存）漸漸成熟，研究人員分析了非易失性內存和傳統(tǒng)存儲設備的差異，并且就索引數據結構的設計提出了不少新穎的方法。具體地說，在非易失性內存上實現持久索引數據結構，需要解決以下3個問題。

● 如何減少在操作持久索引數據結構時的軟件開銷？

● 如何針對特定的持久化語義實現崩潰一致性保證？

● 在非易失性內存上如何利用多核架構高效并發(fā)處理讀寫請求？

索引數據結構的軟件開銷逐漸成為限制性能的關鍵因素。傳統(tǒng)存儲設備的持久化時延往往是微秒級甚至毫秒級，而內存的時延最多不過一百多納秒，因此在傳統(tǒng)存儲設備上的持久索引數據結構并不需要過多地關注與內存讀寫相關的軟件開銷，而是更多地關注如何通過寫聚合等方式盡可能減小持久化的開銷。但在非易失性內存的背景之下，持久化開銷與內存的讀寫相近，如傲騰內存的寫時延為62 ns，而讀時延為169～305 ns[10]，過去的一些略微提高軟件開銷、降低持久化開銷的優(yōu)化手段無法被直接應用在非易失性內存中，軟件開銷對性能的影響大大增加[11]。同時，緩存未命中、流水線停頓等體系架構層面的性能損失也會對構建在非易失性內存之上的索引數據結構有較大的影響。如為了進一步降低開銷，MOD[12]將持久化所需要的內存屏障進一步降低，以提升性能。另外，為了降低開銷，還需要盡可能解決讀寫放大的問題，有工作指出[10]，由于傲騰內存的內部讀寫粒度為256 byte，小于256 byte的讀寫均可能帶來寫放大，這會對索引數據結構的性能有所影響。

同時，需要重新思考崩潰一致性的實現。傳統(tǒng)存儲設備基于塊設備的抽象、操作和讀寫都以塊為單位（更具體地說，機械硬盤的讀寫粒度為扇區(qū)，大小一般是512 byte，固態(tài)硬盤的讀寫粒度為閃存頁，大小一般是4 KB），只要相應的塊或頁被寫入存儲設備，即完成了持久化。但在非易失性內存中，一般的store指令原子操作粒度僅為8 byte，且該指令會由于CPU的亂序執(zhí)行而難以按照開發(fā)者預想的順序寫入存儲。另外，數據會首先寫入CPU的L1/L2/L3緩存中，而CPU的緩存并不能保證持久化。因此，為了保證讓數據在非易失性內存上持久化存儲，需要在store指令后相應地加入內存屏障和刷寫緩存行指令（如clflush或clwb），將緩存行從CPU緩存刷到非易失性內存里。由此，非易失性內存上需要新的方法來保證崩潰一致性。

另外，面對海量的讀寫請求，需要設計適合多核架構的索引數據結構。由于極低的時延以及字節(jié)可尋址的特性，與傳統(tǒng)存儲設備相比，構建在非易失性內存之上的索引數據結構的吞吐量有多個數量級的優(yōu)勢，在多核架構上非易失性內存的優(yōu)勢將更加顯著。盡管如此，由于前面提到的兩個問題，能夠在動態(tài)隨機存取存儲器（dynamic random access memory，DRAM）上使用的并行索引數據結構并不能直接用于非易失性內存上。另外，由于非易失性內存額外引入的刷寫緩存行操作，以及傲騰內存在線程數過多時帶寬反而會下降[10]，需要對索引數據結構上的并發(fā)讀寫做進一步的優(yōu)化，才能夠充分適應非易失性內存的特性。

針對上述3個問題，目前已有很多研究給出了針對非易失性內存的索引數據結構設計。本文主要分析其中兩種常見的索引數據結構（B/B+樹（B/B+-Tree）和哈希表），并總結了它們在非易失性內存上的發(fā)展。

3 有序索引數據結構在非易失性內存上的實現

有序索引數據結構能夠高效地處理范圍查詢任務，其中的一種實現——B/B+-Tree能夠顯著地減少磁盤I/O的次數，已經被廣泛應用到InnoDB等存儲引擎中。針對B/B+-Tree在非易失性內存上的實現，筆者總結了下面的工作，并分析了其優(yōu)劣。其中2011—2018年的工作都是在模擬的非易失內存模擬器上完成的，之后的工作才開始在真實的傲騰內存上實現。

2011年Venkataraman S等人[13]首次提出了針對非易失性內存設計的CDDS B-Tree。他們使用mfence（內存屏障）和clflush（刷寫緩存行）的組合指令來保證數據按順序寫入非易失性內存中，在B-Tree的基礎上，使用多版本機制實現更新操作，另外通過寫時復制實現節(jié)點的分裂和合并，從而減少了額外的寫入，無須通過寫日志保證崩潰一致性。但是使用多版本和寫時復制的代價是需要后臺線程來進行垃圾回收，這會帶來額外的性能開銷。

2015年Yang J等人[14]對非易失性內存上的B+-Tree進行了改進，提出了能夠進一步降低維護一致性開銷的NV-Tree。通過深入分析，他們發(fā)現在葉子節(jié)點維護順序存放的鍵值需要刷寫多個緩存行，另外還需要維護B+-Tree的內部節(jié)點的崩潰一致性，這些引入了大量開銷。為了進一步優(yōu)化，該文章提出可以讓葉子節(jié)點存放的鍵值對亂序，具體的實現是使用日志結構寫入。另外，由于內部節(jié)點可以重建，不需要額外維護內部節(jié)點的崩潰一致性。但由于葉子節(jié)點沒有維護順序，這種方法對讀操作的性能造成了一定的影響。

2015年Chen S M等人[15]基于參考文獻[14]進一步優(yōu)化了B+-Tree在非易失性內存上的實現，提出了wB+-Tree。如果葉子節(jié)點沒有維護鍵值對的順序，就會影響讀操作的性能，因此該文章在葉子節(jié)點中使用位圖記錄槽的分配情況，并進一步增加槽數組（slot array）用于記錄鍵值的順序，優(yōu)化讀操作。另外針對崩潰一致性的實現，wB+-Tree在插入操作和更新操作中，都先在節(jié)點中尋找空的或無用的槽寫入并保證持久化，然后通過一次8 byte的原子寫入和持久化修改元數據，從而完成操作。這樣的實現使用非易失性內存上的8 byte原子寫入指令保證崩潰一致性，但節(jié)點分裂操作依然使用了傳統(tǒng)的重做日志方法，帶來了額外的寫入。

2016年Oukid I等人[16]結合參考文獻[14]提到的分析，在非易失性內存上進一步優(yōu)化了B+-Tree，提出了FPTree?；趦炔抗?jié)點可以通過葉子節(jié)點重建的原理，FPTree將所有內部節(jié)點都放在DRAM里，只將葉子節(jié)點持久化存放在非易失性內存中，減小維護崩潰一致性的開銷。同時FPTree在葉子節(jié)點中存放了每個鍵各1 byte的指紋，用于快速判斷指定鍵是否在該葉子節(jié)點中，從而降低葉子節(jié)點無序存放鍵值對讀操作的影響。為了進一步降低軟件開銷，優(yōu)化并發(fā)，FPTree將分配內存的開銷分攤到多個節(jié)點上，并結合硬件事務內存降低了并發(fā)訪問的開銷。

2018年Arulraj J等人[17]基于PMwCAS在非易失性內存上實現了能夠無鎖并發(fā)的BzTree。比較并交換（compare and swap，CAS）指令是實現無鎖并發(fā)算法的關鍵指令，其能夠對單個字節(jié)進行原子的比較和交換操作，而PMwCAS[18]將該操作擴展到多個字節(jié)且保證非易失性內存上的持久化。通過PMwCAS提供的原子性，開發(fā)者可以避免非易失性內存帶來的編程細節(jié)，使用通用的方法在非易失性內存上實現支持崩潰一致性且無鎖并發(fā)的BzTree。

2018年Hwang D等人[19]在非易失性內存上基于FAST（failure-atomic shift）&FAIR（failure atomic in-place rebalancing）算法實現了可容忍瞬時不一致的B+-Tree。由于一些不一致的情況可以通過修改讀操作來容忍，避免讀取錯誤的內容，作者首先通過FAST算法保證在節(jié)點內部維護有序性時，移動鍵值對產生的不一致是可容忍的，然后FAIR算法能夠以類似的保證進一步處理節(jié)點分裂或合并的情況。這個方法無須任何日志就能夠保證B+-Tree在任何操作中都處于不一致但可容忍的狀態(tài)，同時由于內部節(jié)點也存在于非易失性內存中，基于該方法實現的B+-Tree崩潰后能夠馬上恢復，而無須重建索引。

2020年Chen Y M等人[20]發(fā)現非易失性內存上的B+-Tree有較嚴重的長尾時延，經過深入分析后，他們認為在非易失性內存中對葉子節(jié)點的結構進行改變的操作（排序和節(jié)點平衡）以及并發(fā)線程之間相互等待訪問非易失性內存是造成長尾時延的根本原因?；谶@樣的分析，他們提出uTree。uTree的內部節(jié)點組織與一般B+-Tree相同，存放在內存上，而葉子節(jié)點分成內存中的數組層與存放在非易失性內存上的鏈表層。該設計能讓造成長尾時延的操作在內存上完成，而在非易失性內存上可以并行操作鏈表的個別元素。這樣的設計緩解了長尾時延，但也增加了索引數據結構的內存占用。

2020年Liu J H等人[21]在3D XPoint上優(yōu)化了B+-Tree，提出了LB+Trees。他們充分利用了3D XPoint上內部介質讀寫粒度為256 byte和持久化粒度為64 byte之間的差異，發(fā)現影響性能的是CacheLine的寫入，在CacheLine寫入數量相同的情況下，CacheLIne內部臟字寫入是沒有影響的，進而提出可以通過節(jié)點內部鍵值對的移動來減少內部介質讀寫。同時為了保證崩潰一致性，他們在wB+-Tree的實現上進一步擴展，基于類似的思路，利用8 byte的原子寫保證了包括節(jié)點分裂和聚合在內的所有操作的崩潰一致性，無須寫日志，并且還能夠通過分布式頭元數據的方式擴大葉子節(jié)點的大?。?56 byte的倍數）而不犧牲崩潰一致性。

B/B+-Tree在非易失內存上的實現及優(yōu)缺點見表1。除了B/B+-Tree之外，在非易失性內存上進行優(yōu)化的有序索引數據結構還包括基數樹（radix tree）以及其變體，如WORT[22]、P-ART[23]、HART[24]、DPTree[25]、ROART[26]等。這些工作從不同方面對上述3個關鍵問題給出了不同的解決方案。從這些工作可以發(fā)現，為了高效地利用非易失性內存的性能，減小軟件開銷、通過避免日志寫入實現崩潰一致性、通過避免鎖的使用來實現高效的并發(fā)、結合處理器體系架構和非易失性內存的硬件特性來進行優(yōu)化，已經成為主流的方法。

表1 B+-Tree在非易失性內存上的實現與優(yōu)缺點

4 哈希表在非易失性內存上的實現

隨著NoSQL存儲系統(tǒng)逐漸發(fā)展，無須維護數據有序性從而具備更小開銷和更簡潔實現的哈希表目前在各種存儲系統(tǒng)中得到越來越廣泛的應用，如MongoDB、HBase、Memcached等。在哈希表的設計中，需要解決的兩個核心問題分別是哈希表擴容和哈希沖突。哈希表擴容指的是當哈希表的容量不足以容納用戶需要寫入的所有數據時，哈希表需要進行容量擴大，并根據需要將舊的數據重哈希到新的哈希表上。哈希沖突指的是哈希表中的單個桶（bucket）沒有空閑位置放置鍵值對的情況。

現有的針對哈希表的研究可分為兩類：動態(tài)哈希和靜態(tài)哈希。在靜態(tài)哈希中，當哈希表容量需要進行擴大時，一般需要創(chuàng)建一個更大的哈希表，并將舊哈希表中的數據重新插入新的哈希表中，其擴容的開銷與哈希表本身包含的數據量成正比。關于這種哈希表在非易失性內存上的實現，目前的研究成果如下。

Zuo P F等人[27]提出的Path-Hashing針對非易失性內存環(huán)境下的哈希表，指出以往的哈希表設計會帶來大量的額外寫，這會極大地影響哈希表在非易失性內存上的性能。因此他們提出了一個基于路徑的哈希表。該哈希表通過位置共享技術解決哈希沖突問題，優(yōu)化了對CPU緩存的使用且不會帶來額外的寫。為了進一步提高負載因子和讀寫性能，Path-Hashing還能夠使用兩個哈希函數構建兩條搜索路徑，并進行路徑壓縮，在緩解哈希沖突的同時，減小路徑的深度。

Zuo P F等人[28]進一步優(yōu)化了哈希表的寫入操作，提出了Level-Hashing。他們不僅提出了一種寫優(yōu)化的層次哈希結構，通過雙哈希函數和沖突后一次鍵值對的移動來提升哈希表的負載因子，同時還實現了一種原地擴容機制，這讓Level-Hashing只需要對1/3的內容進行重哈希，將處于底層的內容重新寫到頂層的哈希表中，即可完成擴容。另外Level-Hashing還能夠以無須日志的方式保證插入、修改、刪除、擴容操作的一致性，只有更新操作可能需要寫日志。

Chen Z Y等人[29]提出的CLevel-Hashing對哈希表的并發(fā)性能進行了大量改進。一方面，CLevel-Hashing能夠在后臺異步擴容和重哈希，而不會阻塞操作，從而避免了等待擴容導致的長尾時延；另一方面，過去哈希表一般使用鎖來實現并發(fā)，他們針對讀取、插入、更新、刪除操作均基于CAS原語實現了無鎖并發(fā)算法，從而避免鎖競爭，提升哈希表的擴展性。

相對于靜態(tài)哈希，動態(tài)哈希能夠根據用戶插入的鍵值對的數量靈活地擴大或縮小哈希表的容量，每次擴容時只需要常數時間復雜度的開銷。

Nam M等人[30]在非易失性內存中引入了可擴展哈希CCEH（CacheLineconscious extendible hashing）。基于原始的可擴展哈希設計，他們根據非易失性內存的特性進行了一些改進，包括將桶的大小設置為緩存行的整數倍，以及增加一層段（segment）來減少空間占用。同時他們還提出了一種崩潰恢復算法，使其能夠保證在修改CCEH和進行段分裂時無須任何日志即可保證崩潰一致性。

Lu B T等人[31]進一步提出了一種擴展性更好的哈希表Dash。他們認為不僅要優(yōu)化非易失性內存上的寫入，還要盡量減少非易失性內存上的讀取操作。因此他們對Dash做了兩方面的優(yōu)化。從哈希表本身的設計上，他們提出基于指紋對鍵的存在與否進行快速的判斷以優(yōu)化讀取速度，同時在哈希沖突的解決上，他們使用哈希桶間自平衡的方法來提高哈希表的負載因子。同時Dash還能夠讓插入和更新操作均不需要用日志來保證崩潰一致性，僅在段分裂時需要使用重做日志。另外，Dash還使用了優(yōu)化的并發(fā)控制訪問，讀取不需要鎖的參與，寫時使用原子變量實現互斥訪問。

Zou X M等人[32]提出了HMEH（hybrid memory extendible hashing）。他們在CCEH的基礎上，考慮到可擴展哈希的目錄層可通過非易失性內存上額外構建的一顆基數樹來重建，因此將目錄層放到DRAM中，以減少非易失性內存上的讀寫。另外他們還提出了一種利用8 byte原子寫實現的鍵值交錯策略，使HMEH無須任何日志也無須顯式地刷寫緩存行就能夠保證一般操作的崩潰一致性。對于段分裂操作，基于之前設置的基數樹，HMEH實現了一種無須任何日志和寫時復制的分裂方法。

哈希表在非易失性內存上的實現與優(yōu)缺點見表2，可以發(fā)現，其發(fā)展趨勢與有序索引數據結構是一致的，在充分利用硬件特性進行優(yōu)化的同時，無須日志的崩潰一致性保證和無鎖算法成為在非易失性內存上高效實現索引數據結構的關鍵所在。

表2 哈希表在非易失性內存上的實現與優(yōu)缺點

5 結束語

本文分別對B+樹和哈希表在非易失性內存上的設計和實現進行了深入的分析。根據兩者的發(fā)展發(fā)現，在非易失性內存上實現持久索引數據結構所需要解決的3個問題目前已有一致的趨勢。為了減小索引數據結構的軟件開銷，現有研究會放松對數據有序性的維護，減少內存屏障與緩存行的刷寫，感知內部存儲介質的讀寫粒度以及盡可能減少額外寫，而對于崩潰一致性與適應多核架構，則分別趨近于無須日志和無須加鎖的方法。

最后，對在非易失性內存下高效實現索引數據結構的過程中存在的一些挑戰(zhàn)進行總結。

一是如何在保留崩潰一致性的同時利用DRAM進一步優(yōu)化索引數據結構的性能。目前的非易失性內存盡管性能接近DRAM，但是其時延仍然比DRAM高好幾倍，且?guī)捀邮芟?。由于非易失性內存和DRAM之間的性能差距仍然不可忽略，現有的研究工作已經在嘗試使用DRAM來優(yōu)化索引數據結構的性能，但也有研究表明，在一些場景中，DRAM和非易失性內存混用可能會由于額外的數據遷移造成性能損失，因此如何高效地利用DRAM來優(yōu)化索引數據結構仍然是一個需要深入研究的問題。

二是如何更進一步地利用非易失性內存的硬件特性對索引數據結構進行優(yōu)化。非易失性內存與DRAM類似，但又有其獨特的性質，之前的研究大多在使用DRAM模擬的非易失性內存上完成，近兩年的研究工作大多基于英特爾傲騰持久內存，指出過去的研究中存在的問題，并對傲騰內存的硬件特性進行了一些適配。但一方面英特爾并沒有公布傲騰持久內存的內部原理和架構，研究人員只能通過猜測其硬件特性進行優(yōu)化，另一方面還有更多的新型非易失性內存存儲介質未面市，這些存儲介質可能具備不一樣的特性，在這樣的背景下，持久索引數據結構需要具有更靈活的設計才能適應存儲介質的發(fā)展。

三是如何實現高效的非易失性內存空間分配器。在索引數據結構的設計和實現中，非易失性內存空間的動態(tài)分配是一個不可或缺的操作，其作為軟件開銷的一部分，對索引數據結構的性能有較大影響。同時一個高效的非易失性內存分配器要求避免永久性的內存泄露，并支持高效的并發(fā)操作。然而現有的研究中大多僅關注數據結構本身，忽略了這部分重要的軟件開銷，另外在DRAM中的內存分配器也需要更進一步的改進才能充分利用非易失性內存的特性。