基于持久性內存的單向移動B+樹

閆 瑋 張興軍 紀澤宇 董小社 姬辰肇

(西安交通大學計算機科學與技術學院 西安 710049)(yanweiwei.002@stu.xjtu.edu.cn)

由新型非易失存儲介質如PCM[1],ReRAM[2],MRAM[3]等構成的持久性內存(persistent memory, PM)具有按字節訪問、非易失、存儲密度高等特性，為計算機主存與外存融合提供了一個強大的契機.相較于傳統內存，PM由于內部結構與制作工藝不同，具有更強的擴展性，同時由于其持久化特性，PM還能夠大幅降低系統的靜態能耗.相較于傳統塊設備，PM能夠提供更快的訪問速度，同時支持按字節訪問.

為了大幅提高數據訪問速度，存儲系統通常需要根據訪問需求及硬件特性設計高效的索引結構如樹、散列、字典樹等.B+樹以其擴展性好、性能穩定、緩存局部性較強等特點成為其中最受歡迎的索引結構之一，目前作為內存數據結構也得到了廣泛應用.然而PM的出現并作為存儲級內存設備為其設計帶來了新的挑戰：

1) 失敗原子性問題.目前常見Cache由易失存儲介質構成，在系統故障后數據會完全丟失.因此在寫回式(write-back)Cache與PM交互時，cache line內數據會根據Cache替換算法被寫回到主存上，若發生故障，Cache內未及時寫回到PM中的數據將會丟失.這可能會破壞PM中數據的完整性.另外為了滿足內存級并行[4-5]，Cache中寫回PM的cache line的順序可能被打亂，進一步增加了數據恢復的難度.為了保證失敗原子性，目前常見操作是使用clflush指令將cache line顯式寫回到主存之上，同時通過mfence指令規定cache line的寫回順序.然而上述操作會顯著降低內存的并發性能，進而降低整個系統的性能.

2) 持久化開銷問題.保證失敗原子性會帶來顯著的持久化開銷(mfence+clflush)，這個開銷在B+樹中會被進一步放大，如若B+樹節點內數據有序，那么插入一個數據的排序操作會引起平均一半數據的移動，這些移動有明確的移動次序，意味著多次有序持久化操作；若B+樹內節點無序，需先持久化數據，再持久化相應元數據；B+樹節點的合并與分裂時，涉及到大量數據移動(拷貝)與部分指針的修改，數據移動(拷貝)必須在指針修改之前完成；若采用寫時復制策略，亦涉及到大量數據移動(拷貝)與部分指針的修改.同時目前商用較為成功的持久性內存如Intel Optane DC persistent memory亦面臨著使用壽命有限的問題[6-8]，過多的持久化操作亦會影響其設備的使用壽命.

雖然現存PM設備相較傳統DRAM，延遲與吞吐量存在一定差距[9-10]，但隨著新型非易失存儲介質技術的不斷發展，其性能差距必然會被不斷縮小(ReRAM具有近似SRAM的性能).同時在官方公布信息與文獻[10]針對Intel Optane DC persistent memory的測評中均無法得知其失敗原子性的保證粒度及機制，因此本文假定PM的失敗原子性保證仍為8 B.本文聚焦基于單一PM架構的B+樹設計，旨在保證數據結構失敗原子性的基礎上，進一步減少持久化開銷，進而提高其性能并優化其使用壽命.

本文設計主要基于以下4個觀察：

1) 使用無序數據布局能夠大幅提高寫入性能，但由于數據無序，查找速度會受到很大影響，同時也會影響插入操作中節點內元素定位的過程.通過添加元數據加快查找速度會帶來額外的持久化開銷.節點內數據排序能夠大幅提高數據訪問性能，但排序開銷較大.

2) B+樹節點占用率通常為70%左右[11].

3) 在有序節點內，插入或刪除一組數據會造成平均50%的數據移動，這將帶來大量的有序持久化操作.

4) 同節點內，插入操作能夠大概率與之前發生的刪除操作結合，進而減少數據的移動距離.

本文針對有序節點進行優化，主要貢獻包括3個方面:

Fig. 1 Updating the node with three strategies圖1 節點的3種更新方法

1) 設計了一種基于節點內數據真實分布的數據單向移動算法.通過原地刪除的方式，減少刪除帶來的持久化開銷.利用刪除操作在節點內留下的空位，減少后續插入操作造成的數據移動，進而減少數據持久化操作數量.

2) 基于該單向移動算法，設計了一個基于PM的單向移動樹(one-direction shifting tree, ODS-Tree).ODS樹通過基于數據分布的分裂算法緩解了節點空間利用率較低的問題，同時利用選擇性重均衡算法進一步節省了ODS樹占用的空間.

3) 通過單一負載與混合負載驗證本文所提出的ODS樹空間利用的合理性及訪問性能.

1 研究背景

1.1 節點更新方式

目前常見B+樹節點更新的方式如圖1所示，包括原地更新(in-place updates)、日志式更新(log-structured updates)和寫時復制(copy-on-writes, COW).具體介紹如下：

1) 原地更新.原地更新是指增刪查改等操作直接作用于原始節點.如圖1(a)所示，插入操作直接發生在節點內，該過程需要日志來保證更新的原子性，同時更新操作需要的空間較少.

2) 日志式更新.如圖1(b)所示，增刪查改等操作均記錄在日志內，以追加的方式存儲在節點之后，或存儲在特定區域.該更新策略能夠支持高效的順序讀寫，因此非常適合基于傳統機械硬盤的存儲.日志式更新由于其產生的日志式結構，不需要額外日志保證原子性，但讀操作需要訪問原節點以及其所有日志并通過一定的計算才能獲得正確結果.

3) 寫時復制.如圖1(c)所示，當我們要對節點進行更新時，首先分配一個新的節點，將原始節點數據拷貝到新節點中，然后將相應更新操作在新節點內進行，更新完成后，通過修改父節點內指針使新節點替換原始節點.寫時復制不需要額外日志保證更新的原子性，但會引起顯著的寫放大，在樹結構中尤為明顯，如產生一個“自底而上”的拷貝.

文獻[12]中通過對比分析在PM環境下的3種更新策略，提出原地更新方式更適用于基于PM的B+樹節點更新.在原地更新條件下，由于節點內數據排布方式不同，增刪查改等操作細節也需要相應的變化.

1.2 節點數據排布方式及其更新方式

樹節點內常見數據排布方式包括有序排布與無序排布.有序排布是指所有數據按照數據key的大小升序或降序排布，這有利于查找速度的提升，但插入操作會造成大量的數據移動(平均一半節點內數據)，刪除操作與插入操作類似，只是數據移動方向相反.無序排布是一種寫優化排布，在此排布下插入操作直接將數據存儲到數據組尾部(或數據組內部可用位置)，刪除操作將數據組內相應數據刪除或在數據組尾部存儲一個帶刪除標記的該數據.無序排布的寫性能較高，但每次訪問某一數據都需要遍歷所有數據，造成大量的查找開銷，寫性能優勢亦會相應下降，可以通過元數據設計優化降低查找開銷.

1.3 失敗原子性及其保證

原子性通?？煞譃椴l原子性與失敗原子性.并發原子性是指我們對數據的操作在多個事務看來具有原子性，這意味著任何事務無法看到操作過程中數據的中間狀態.目前保證并發原子性的常見機制除利用顯式內存屏障外還可通過硬件事務內存保證[13-14].

失敗原子性是指在數據持久化的過程中，需要保證斷電或系統故障后數據的完整性與正確性.其中一個破壞失敗原子性的主要表現為數據從易失介質寫入到非易失介質的過程中，若傳輸數據量大于非易失介質的原子寫入粒度，此過程中發生斷電或故障，未寫入數據將會丟失，同時非易失介質內數據可能會出現無法識別的局部更新現象.在基于PM的存儲系統中，Cache與PM的交互粒度為一條cache line(通常為64 B)，原子性更新粒度為8 B.因此故障既可能發生在單條cache line內字(word)更新之間(在64位處理器中，word長度通常為8 B)，也可以能發生在多條cache line更新之間，同時由于粒度差距，日志會造成顯著的寫放大.結合圖2分析，失敗原子性的保證條件為：

1) 若需要更新的數據量小于等于8 B，則可直接對數據進行更新操作.

2) 若需要更新的數據大小大于8 B小于等于64 B且位于一條cache line內，則需考慮在當前cache burst order(word寫回順序)情況下[15]，持久化一條cache line過程中發生故障是否會破壞數據的完整性.若單條cache line內所有word不存在依賴性，則需使用日志保證所有word在一個原子區間內完成持久化操作(不考慮額外硬件保證).若word之間存在依賴性(原地更新場景下插入操作后數據移動)，為減少日志開銷，可通過選擇特定的burst order通過一次持久化指令保證word有序持久化到PM上.

3) 若需要更新的數據大于8 B且跨多條cache line，則在每條cache line內需滿足條件2).同時由于多條cache line寫回PM過程中可能會出現亂序問題，因此還需要保證多條cache line的寫回順序.若cache line之間不存在依賴性，則多條cache line的更新需保證在一個原子區間內完成，通常采用日志方式完成(不考慮額外硬件保證)；若多條cache line之間存在依賴性(原地更新場景下插入操作后數據移動)，為保證多條cache line之間的有序持久化，需要采用顯式持久化指令+內存屏障的形式，保證多條cache line順序持久化到PM上.

Fig. 2 Updated data after insertion under different conditions圖2 不同條件下插入操作更新的數據量

在B+樹中，更新操作通常僅修改value值，而value值的長度通常為8 B，插入操作需完成一次key，value對的插入，尺寸大于8 B.在節點內數據有序排布的情況下，更新操作能夠直接對數據進行原子更新操作；插入操作會造成大量的數據移動(平均移動節點內一半的數據)，這涉及到大量數據的修改，操作粒度通常遠大于原子更新粒度，同時數據在移動過程中存在依賴性，因此需根據更新數據量大小選擇2)或3)來保證失敗原子性，即保證被更新數據的有序持久化.刪除操作與插入操作類似，僅移動方向相反.由于節點內數據有序排布，查找操作可以通過順序查找或二分查找進行，查找性能較高.

在節點內數據無序排布的情況下，更新操作可直接對原始數據進行.插入操作會將key，value對追加到尾部(或數據組內部可用位置)，結合2)分析，該操作需要日志保護.但我們可以通過增加一個額外的位圖表示數據的可見性，數據寫入后，通過原子性更新位圖來保證整個追加操作的原子性，另外也可通過該位圖來快速完成刪除操作(標記位圖相應位置為0即可，無需在數據組尾部追加標記).基于上述條件優化之后，插入操作的持久化保證可簡化為先持久化key，value對，再持久化元數據(位圖).查找操作需要遍歷所有有效數據，若數據存儲設備與Cache直接交互，位圖雖然能減少查找開銷，但訪存開銷依舊較高.

如果更新數據量小于8 B，更新操作可以直接原子性完成，更新數據量大于8 B則需要根據情況選擇持久化策略：在有序節點內，若更新操作僅涉及修改一條cache line，則需保證cache line內每一個word的持久化順序，若更新涉及到多條cache line，則需要保證數據移動過程中相應修改的cache line按一定順序持久化；在無序節點內，需要先持久化數據，再持久化元數據.因此可得到結論：無論節點內數據如何排布，更新大于8 B的失敗原子性均需要通過有序的持久化操作來保證.

目前基于X86架構下，保證數據持久化的常用指令包括clflush,clflushopt,clwb[16].clflush能夠顯式地將一條包含指定地址的cache line寫回到內存中同時使Cache中相應的cache line無效；clflushopt是一種并行版本的clflush；clwb在clflushopt功能的基礎上，能夠保證cache line在Cache中有效，進而能夠在一定程度上保證Cache的命中率.為了保證數據持久化操作之間的有序性，我們可以通過mfence指令來規定持久化的順序，目前相關研究均假定clflush與store,clflush指令存在亂序現象，但最新Intel編程手冊中指出clflush不會與上述指令亂序.由于mfence添加與否對本研究影響極小，為便于對照，故本研究采用clflush+mfence的方式保證數據有序持久化操作.為了進一步提高數據持久化效率，文獻[17]提出了epoch barrier，通過硬件保證多個epoch之間的持久化順序，同時epoch內flush操作可以并行執行.文獻[18]在epoch barrier的基礎上，通過使strand內epoch可并發執行，進一步放松了持久化操作的順序性.由于實驗硬件條件限制，同時結合前人研究，本文采用clflush與mfence指令保證失敗原子性.

除單個節點內情況外，B+樹的重均衡操作也會帶來大量的持久化操作，因此亦需要保證其失敗原子性.B+樹的分裂操作原子性保證與寫時復制相似，但是由于B+樹為了支持高效范圍查找，葉子節點間通過兄弟指針連接，這將導致一個新節點插入到樹中需要修改2個指針(父節點內指針與兄弟節點內指針).B+樹節點合并操作亦涉及到上述2個指針.這將增大基于PM的B+樹的設計難度.

1.4 相關研究

為了減少基于PM的B+樹持久化開銷，目前相關研究根據存儲架構不同可分為：基于DRAM+PM的B+樹與基于單一PM架構的B+樹.基于DRAM+PM架構的部分主要相關研究如下：

1) NV-Tree[19].內部節點數據有序且存儲在DRAM內，該設計能夠大幅提高數據查找速度；葉子節點無序且存儲在PM內，在該設計下每次數據插入僅需要一次持久化操作，能夠大幅減少寫入開銷.然而，系統崩潰后，內部節點的重構需要消耗大量時間.

2) FP-Tree[20].與NV-Tree不同的是，FP-Tree為葉子節點添加了一組元數據(指紋)用以管理無序的數據，每一個key對應一個1 B的散列值.查找操作通過優先訪問元數據，提高了Cache命中率.同時，FP-Tree還采用硬件事務內存來保證內部節點的并發性.

3) DP-Tree[21].設計了一種基于DRAM+PM的，同時具有雙階段的索引架構.該設計基于真實硬件Intel Optane DC persistent memory訪問粒度為256 B的特性，首先通過DRAM中的buffer tree對數據更新操作進行緩沖，同時將更新寫入到位于PM的日志中.然后，當buffer tree達到一定尺寸后，合并到base tree中.值得注意的是base tree的內部節點也存在于DRAM中，且只允許合并之后進行修改.除此之外，DP-Tree還提出了一種粗粒度的鎖，以保證索引結構的并發性.

4) FlatStore[22].結合新硬件特性，利用DRAM中的B+樹或散列對更新請求進行緩沖，提出了一種橫向steal的打包策略，將更新請求批量寫入到PM內，有效解決了Cache與Intel Optane DC persistent memory訪問粒度不同的問題，同時將每一個包填充至cache line對齊的尺寸，以解決Optane DC flush同一條cache line會產生額外延遲的問題.該優化策略可兼容絕大多數B+樹和散列，能夠顯著提高KV-store吞吐量.

基于PM+DRAM的B+樹能夠利用DRAM低延遲與高吞吐量的特性高效完成數據的查找操作，進而一定程度上提高插入操作的性能.但DRAM易失特性會顯著影響故障后數據恢復的效率.基于PM的B+樹能夠提供快速的故障后數據恢復，部分主要研究如下：

1) wB+樹[23].wB+樹在無序節點的基礎上引入了排序(permutation)設計.該設計通過增加一個slot array對每個數據的索引進行排序，提高了查找速度，但會額外增加一次持久化操作.在節點容量較小時，slot array尺寸為8 B，可以進行原子更新，但當節點容量增大后，需要額外增加一個8 B的位圖(bitmap)，持久化操作又會額外增加.

2) FAST&FAIR[24].FAST&FAIR保證節點內數據有序，插入或刪除數據均會引起平均節點內一半數據的移動，移動過程中通過先移動value再移動key的形式(刪除與插入類似，但value的移動策略稍有不同)保證重復value之間的key不可見，讀操作通過驗證是否出現重復value來識別該key是否有效.同時為了保證分裂操作的失敗原子性，FAST&FAIR為每次讀操作添加一個檢測兄弟節點的操作，這樣能夠檢測出分裂過程中是否發生過故障，同時找到正確的數據，避免了數據不一致的情況.FAST&FAIR保證了持久化操作與所修改(包含數據移動對原始數據的修改)的cache line數量相同，獲得了較低的持久化操作數量.

FAST&FAIR雖然相較于前人研究能夠顯著減少數據的持久化操作數量，但其持久化操作所改變的數據量更大(平均移動節點內一半數據意味著PM上一半數據需要被更新)，這將影響PM的使用壽命.這一情況在包含刪除操作的混合負載中更為嚴重，會產生不必要的數據來回移動，不僅增加了介質的磨損量，同時也顯著增加了操作延遲.本研究提出的單項移動B+樹能夠通過利用重復value完成刪除操作且不移動相關數據，既降低了刪除操作延遲，又能減少后續插入操作引起的數據移動距離，減少持久化操作次數，進而減少插入操作延遲.數據移動距離的減少也意味著數據更新量的減少，對介質的磨損也有一定的緩和作用.

盡管基于PM的B+樹能夠在故障后快速恢復，但其性能受制于PM相對較高的讀寫延遲與較低的吞吐量.隨著非易失介質相關技術的發展，PM性能將不斷提高，因此基于PM的索引結構設計將獲得更加廣闊的前景.本文通過分析前人研究成果，在基于PM原地更新策略的基礎上，針對節點內有序的數據排布，提出了一種新的更新策略.該策略通過避免刪除操作帶來的左移操作以減少數據移動，同時利用刪除操作留下的空位減少下一次插入操作所需的數據移動距離，進而減少數據的持久化開銷.

2 基于PM的單向移動算法

基于PM的單向移動算法旨在解決插入與刪除混合操作時造成的數據來回移動過程中持久化操作開銷過大的問題.該算法主要由3個操作協同完成：通過設置重復value值完成的刪除操作、基于節點內數據分布且通過重復value值保證失敗原子性的插入操作以及能夠根據重復value值修正結果的讀操作.該算法能夠在降低刪除開銷的情況下減少后續插入操作的數據移動距離，進而減少數據持久化開銷.通過易失位圖實現高效的數據移動策略并提高數據訪問效率.

本節將對本文設計的基于PM的單向移動算法進行詳細描述.主要從節點內結構、查找操作、插入操作、刪除操作、數據可見性與系統崩潰后恢復6個方面進行.

2.1 節點內結構

本文設計的ODS樹節點內數據均有序排布，同時每個節點頭部均有一個位圖來表示節點內的空間利用情況.在本文的設計中，數據并不會在系統故障后被損壞，元數據可以在系統故障后被重構，因此為了盡量減少元數據持久化開銷，該位圖設計為易失狀態.該狀態意味著每次系統重啟后，其數據均不可用，需要根據原始數據進行重構.位圖前部為基于系統全局時鐘的時間戳，每次系統重啟后，該時間戳進行+1操作，以此來保證位圖的有效性.重構操作在系統重啟后第1次訪問節點進行，因此不會給系統性能帶來明顯影響.位圖可用于輔助統計節點內元素個數、二分查找以及計算數據移動的距離.

2.2 查找操作

每次查找一個節點之前，首先驗證位圖的可用性，若位圖時間戳過期，則根據原始數據進行重構，通過遍歷數據完成重構后同時返回查找結果；若位圖可用，則根據位圖對數據進行二分查找.查找過程中，若位圖相應標記為0，則選擇附近的數據進行比較.重復上述操作直至找到數據位置.為防止節點分裂過程中發生故障，查找操作還需要檢測兄弟節點內數據.具體細節分析見3.2節.

2.3 插入操作

插入操作所引起的數據移動過程如圖3所示：

Fig. 3 Data changing after inserting 13 in the node圖3 插入13后節點內數據的變化

節點初始為執行過多次原地刪除之后的狀態：節點內存在許多已經被刪除的數據，此類數據直接由位圖中的0直觀表示，在原始數據中該key值兩側value相同，在位圖有效期間不需修正.具體插入過程如算法1所示：

算法1.單向移動樹插入算法ODS_insert(key,value).

① if 位圖不合法 then

②reconstruct_node();*重構位圖*

③ else

④tail=get_tail(node.bitmap);

⑤ for (i=tail-1;i≥0;i--) do

⑥ if (get_bit(node.bitmap,i)==1)

then

⑦ ifkey>node.records[i].keythen

⑧position=i+1;

⑨ break;

⑩ end if

then

records[j].value;

records[j].key;

records[position-1].value;

由于位圖不做持久化處理，每個節點的位圖可能存在故障后不一致的情況，因此在數據插入前應首先檢測節點的位圖是否可用，該過程通過比對位圖內時間戳與系統時間戳是否相同，若相同，則位圖可用，若不同，則位圖不可用.若判斷結果為位圖不可用，則需要根據原始數據對位圖進行重構.若位圖可用，我們首先根據位圖獲得數據組尾部位置，然后結合位圖從右向左遍歷數組，通過位圖內1對應的數據比對查找數據插入位置，同時記錄位圖內0的位置作為數組內離插入位置最近的空位位置(⑤～).～操作用來檢測保證分裂過程中是否出現故障(具體見3.2節).獲得數據插入位置后，根據獲得的空位位置，我們采用文獻[25]中的數據移動策略，將插入位置與空位之間的數據進行移動，先移動value再移動key以保證移動過程的失敗原子性.在此過程中若發生斷電，相同的value可以被讀操作識別為當前key不可用狀態，因此可保證系統崩潰后的失敗原子性.由于移動過程中，load與store指令存在依賴性，因此我們不需要添加內存屏障；若數據移動到另外一條cache line內，則進行一次持久化操作.移動完成后將數據插入，再進行一次數據持久化操作，更新位圖，數據插入操作完成.

2.4 刪除操作

刪除操作的原理是使待刪除的數據對讀操作不可見.在本文設計中，刪除操作采用重復value值的方式使刪除的數據不可見，由于value值長度為8 B，因此采用一次原子操作即可完成.重復value值的選擇通常為前一組數據的value值，若被刪除的是第1組數據，則value設置為兄弟節點指針(葉節點)或最左側子節點指針(內部節點).此過程可視為我們人為地制造了一次被中斷的具有失敗原子性保證的數據移動操作.我們可以在邏輯上認為節點內存在很多空位，這些空位通過位圖直觀展示.待刪除數據value值更新后，再將位圖相應位置設置為0，即完成了一次刪除操作.刪除操作對原始數據的影響與插入操作數據移動過程中發生系統崩潰后造成的影響相同，均可以通過讀操作進行修正(僅修正讀操作的結果，不需要對原始數據修改).刪除操作完成后若位圖值為0，即節點內無有效數據，則將該節點從父節點內刪除，由于本文混合負載中刪除比例較低，因此不會造成顯著的空間浪費.

2.5 數據的可見性

讀操作存在于查找操作以及插入過程中插入位置的搜索.數據的可見性需要讀操作來完成：當讀操作找到相應位置后，額外讀取下一個記錄的value值，若2個value值相同，則當前位置的key為無效數據，讀操作將繼續進行直至查找到需要數據或返回未查找到.

在插入操作導致的數據移動過程中，重復value值以及之間的不可見key也會作相應移動，因此發生系統崩潰時產生的不一致仍可通過讀操作驗證是否有重復value來修正.

2.6 系統崩潰后的恢復

我們設計的ODS樹不需要對不一致的數據進行修復，只需要在讀操作過程中對不可用的位圖進行重構，因此支持瞬間恢復，其原理主要為：系統崩潰后，所有節點的位圖由于版本不匹配，均為不可用狀態，此時讀操作(包括插入操作的定位操作與查找操作)進入節點后首先判斷位圖是否可用，若不可用，則直接對節點內全部原始數據進行順序讀操作，若當前key對應的value值與前一個key的value值相同，則位圖相應位為0，若不同則為1，遍歷操作在到達第1個null時(節點內數據組的尾部)停止，此時位圖修復完成，同時讀操作亦相應完成.臨近重復value之間的key不可見，通過位圖相應位置為0表現為已刪除(空閑)狀態.

3 基于PM的單向移動B+樹

本節詳細描述了應用單向移動算法后B+樹的重均衡(rebalancing)策略.主要包括選擇性重均衡策略操作、節點分裂與內部整合等操作.

3.1 選擇性重均衡操作

由于我們設計的算法中不使用數據修復操作，因此節點內會產生刪除與系統崩潰產生的空位.盡管該空位能夠通過位圖有效識別，但會造成節點內疏松的結構，影響節點空間利用率.當節點無法插入新數據時，若節點內空間利用率較低，分裂操作相較于節點內部整合操作開銷較大.因此我們需要通過位圖分析節點內空間利用率與數據分布，選擇重均衡策略.

在本文的設計中，所有重均衡策略均由插入操作觸發，若數據無法被插入到節點內，則需要根據節點內空間利用率及數據分布情況選擇相應的重均衡操作.目前本文采取的重均衡策略包括分裂與節點內部整合.為便于表述，我們設定2個關于重均衡策略選擇的參數P1與P2.P1用于表示當前數據能否插入到當前節點內；P2為當前節點的空間利用率，用于判斷應選擇何種重均衡策略.具體過程如下：

找到數據插入位置后，根據位圖所示數據分布判斷節點內是否能夠通過移動數據為待插入的數據提供空間.若能夠提供空間，則P1=true；若無法提供空間則P1=false.

若P1=true，繼續完成插入操作.若P1=false，根據位圖獲得當前P2值.若P2值小于閾值T，即節點內空間利用率小于T，則進行內部整合操作，使節點內數據緊致，若P2≥T，則進行分裂操作.實驗證明節點內空缺比例為20%，設T=0.7時，能夠在保證性能的同時減少樹0.1%左右的空間消耗.

3.2 節點分裂

本文設計的節點分裂算法通過位圖獲得節點內數據的分布，并根據數據分布將部分稀疏數據緊密地寫入到兄弟節點內.該算法每次分裂均包含為一次對部分稀疏數據的緊密化操作，因此能夠緩解節點內數據稀疏結構對空間利用率的影響.具體算法描述如下：

算法2.單向移動樹分裂算法ODS_split(node).

①shifting_position=get_shifting_data_

num(node.bitmap);

②tail=get_tail(node.bitmap);

③new_sibling=malloc(sizeof(node));

④new_sibling.sibling=node.sibling;

⑤new_sibling.bitmap=0;

⑥ for (i=shifting_position;i≤tail;i++) do

⑦ ifget_bit(node.bitmap,i)==1 then

⑧new_sibling.ODS_insert(node.records

[i].key,node.records[i].value);

⑨ end if

⑩ end for

null;

position].key,&sibling);

do

當節點需要分裂時，處理流程為:1)確定需要移動的數據(①②).2)分配一個新的節點并進行初始化(③～⑤).3)根據原節點內位圖，將需要移動的數據插入到新節點中，插入過程中新節點內能夠緊密地保存原節點內一半數據，新節點內位圖也會被相應修改(⑥～⑩).4)修改原節點的兄弟指針指向新分配的節點().5)將原節點內分裂位置的value設置為null并持久化().6)將新節點添加到父節點中().7)修改原節點位圖(～).

在分裂過程中，若故障發生在1)與4)之間，對數據的操作均不可見.若故障發生在4)與5)之間，由于4)5)在操作過程中，均可保證失敗原子性，因此僅需分析4)完成后到5)開始之前的時間段內的故障情況.在此情況下，新節點對父節點不可見，同時存儲的數據與原節點后半部分相同.故障后，原節點內仍為需要分裂狀態，因此讀操作執行時需添加一個判斷操作：當key大于節點內最大key時，需要額外訪問兄弟節點，通過兄弟節點內最小key與原節點內最大key作對比，若兄弟節點內最小key小于原節點內最大key，則意味著此過程中發生了故障，需要繼續完成分裂操作.若兄弟節點內最小key大于原節點內最大key且小于待查找的key，則此故障發生在5)6)之間，重復上述讀操作至返回結果.6)操作為原子性操作，7)操作不需要持久化，因此不需要考慮失敗原子性問題.

3.3 節點內部整合

當節點需要進行內部整合時，僅需根據節點位圖，計算出每個數據的位移，將所有數據左移至緊密相鄰，然后更新位圖即可.通過利用位圖分析，可以直接對原始數據進行最短路徑的移動.上述移動過程采取和右移相同的重復value移動策略，在故障發生時，雖然位圖不可用，讀操作可以修正移動過程中產生的不一致，即將其視為一次已經完成的刪除操作.

4 實驗與結果

由于本文研究針對基于單一PM架構的B+樹，同時WORT源碼中并未實現刪除操作，因此出于嚴謹性考慮，本文對比實驗采用wB+樹與FAST& FAIR.其中wB+樹采用bitmap+slot array的結構.盡管本實驗室目前沒有配置Intel Optane DC per-sistent memory，但本文設計的單向移動B+樹旨在減少基于PM的索引結構持久化開銷(持久化操作數量及其時間開銷)，故可使用quartz[25]進行模擬實驗.

4.1 實驗環境

我們實驗使用的服務器環境配置如表1所示.由于quartz目前不能模擬PM寫延遲，因此我們參考前人研究通過在clflush指令后添加延遲來模擬PM寫延遲[4].同時由于quartz無法同時模擬PM讀延遲與帶寬，因此我們假定PM與DRAM帶寬相同.在quartz配置文件中，我們設置模擬器為NVM only模式，其他參數采用默認配置.通過對不同索引結構在不同大小節點上性能的測試，我們采取的最優節點大小分別為：FAST&FAIR與ODS節點大小為256 B，wB+樹節點大小為512 B.

Table 1 Experiment Configuration表1 實驗環境配置

我們使用YCSB[26]分別生成了單一操作的工作負載及混合操作的工作負載用于測試索引結構的單一負載性能及混合負載的性能.由于我們采用重復value值作為失敗原子性的保障條件，且value長度為8 B，支持原子操作，因此在定長key，value對場景下，key的長度超過8 B并不會產生失敗原子性問題.為簡化實驗，我們故將key，value長度均設置為8 B.

4.2 單一負載測試

我們分別測試了ODS,FAST&FAIR,wB+樹在不同讀寫延遲下的單一負載性能.首先分別使用了5萬個數據進行預熱，然后分別對其進行數量為5萬的插入、查找與刪除測試.其中由于ODS使用原地刪除，因此節點內數據的結構較為疏松.在保證數據量相同的情況下，我們分別設定ODS的空缺比例為10%(ODS0.1)與20%(ODS0.2).完成插入操作后，ODS與FAST&FAIR均占用12 182個節點，ODS0.1占用12 343個節點，ODS0.2占用12 507個節點.相比FAST&FAIR，ODS的3個版本占用空間分別提高了0%，1.3%，2.7%.由此可見插入操作能夠較有效地填補刪除操作留下的空缺.在不考慮預熱階段持久化次數的情況下，各索引結構的操作產生的持久化操作如表2所示，在10%刪除預熱情況下，ODS0.1與FAST&FAIR相比，插入操作能夠減少4.9%、刪除操作能夠減少60.6%的flush操作數量；在20%刪除預熱情況下，ODS0.2與FAST& FAIR相比，插入操作能夠減少9.6%、刪除操作能夠減少60.5%的flush操作數量.

Table 2 Flush Number of Insertion and Deletion in Different Data Structures

性能評估結果如圖4所示，3種版本的ODS相較于其他2種樹，刪除性能均大幅提高，所用時間為FAST&FAIR的32.2%～34.4%，wB+樹的3.6%～4.5%.這是因為我們采取的原地刪除操作能夠大幅減少刪除操作引起的數據移動，進而減少持久化操作，提高性能.稀疏版本ODS插入操作性能在3種延遲環境下，所用時間分別為FAST&FAIR的90%～93.5%,95.7%～97%,93.1%～96.5%；wB+樹的45.9%～47.3%,42.7%～42.3%,41.7%～43%.稀疏化的ODS能夠有效減少插入操作引起的數據移動距離，進而減少持久化操作數量，從而提高了插入性能.查找操作在延遲較高的情況下性能低于FAST&FAIR與wB+樹.這是由于稀疏化結構導致查找的數據量增多，盡管我們使用了位圖加速數據查找速度，但只是單純減少了處理器層面的計算操作，需要處理器實際處理的cache line增多了，此時內存性能成為瓶頸，因此性能對內存延遲比較敏感.

Fig. 4 Performance of different operations under specified latency圖4 不同延遲下各操作的性能

4.3 合成負載測試

在合成負載測試中，我們測試的索引結構與單一負載測試相同.預熱數據量為0.5M，操作數量為0.5M.負載插入、刪除與查找比例分別為3∶1∶1(W1)與1∶1∶3(W2).

在不同數據結構下，我們采用不同合成負載對索引結構進行測試，其中flush操作統計如表3所示：在插入、刪除與查找比例為3∶1∶1情況下，相較于FAST& FAIR，ODS能夠最多減少23%的flush次數；相較于wB+樹能夠減少85.5%的flush次數.在插入、刪除與查找比例為1∶1∶3情況下，相較于FAST&FAIR，ODS能夠最多減少34.8%的flush次數；相較于wB+樹,ODS能夠最多減少92.7%的flush次數.wB+樹在節點分裂與合并時需要記錄日志，會產生大量的持久化操作，ODS不需要記錄日志同時刪除操作能夠減少大量持久化操作，因此相比之下能夠大幅減少持久化操作數量.FAST& FAIR在插入數據時會造成節點內大量數據的移動，ODS利用刪除留下的空位能夠有效減少數據的實際移動距離，能進一步減少持久化操作數量，同時刪除操作也能減少大量持久化操作數量.

性能結果如圖5所示：圖5(a)顯示了60%插入、20%刪除、20%查找條件下5種索引結構的性能.相較于FAST&FAIR，不同延遲下，3個版本ODS性能分別提高了14.1%，14.6%，11.7%.相較于wB+樹，不同延遲下3個版本ODS性能分別提高了82.9%，74.8%，75.4%.圖5(b)顯示了20%插入，20%刪除，60%查找條件下5種索引結構的性能.相較于FAST&FAIR，不同延遲下，3個版本ODS性能分別提高了18.1%，18.8%，22.1%.相較于wB+樹，不同延遲下3個版本ODS性能分別提高了74.2%，80.3%，81.7%.

Table 3 Flush Number of Different Data StructuresUnder Different Workloads

Fig. 5 Performance of index structures under different latency for different synthetic workloads圖5 不同合成負載條件下各索引結構在不同PM延遲下的性能

5 總 結

持久性內存的出現為主存輔存一體的存儲結構提供了強大的契機，索引結構設計將趨向于內存索引結構.然而傳統內存索引結構由于內存的易失性，通常不需要考慮失敗原子性問題.因此基于持久性內存的索引結構為保證其失敗原子性，需要更加細致的設計.本文提出了一種基于有序節點內數據分布的數據移動策略，通過原地刪除產生的節點空位，減少數據的移動距離，同時減少持久化操作的數量.結合上述移動策略，本文實現了一個單向移動B+樹，通過基于節點內數據分布的分裂及整合操作，顯著減輕了節點稀疏化造成的負面影響.目前本設計僅考慮單線程情況，下一步工作為設計一個多線程版本的單向移動B+樹.