閆 瑋 張興軍 紀(jì)澤宇 董小社 姬辰肇

(西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 西安 710049)(yanweiwei.002@stu.xjtu.edu.cn)

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

為了大幅提高數(shù)據(jù)訪問速度，存儲(chǔ)系統(tǒng)通常需要根據(jù)訪問需求及硬件特性設(shè)計(jì)高效的索引結(jié)構(gòu)如樹、散列、字典樹等.B+樹以其擴(kuò)展性好、性能穩(wěn)定、緩存局部性較強(qiáng)等特點(diǎn)成為其中最受歡迎的索引結(jié)構(gòu)之一，目前作為內(nèi)存數(shù)據(jù)結(jié)構(gòu)也得到了廣泛應(yīng)用.然而PM的出現(xiàn)并作為存儲(chǔ)級(jí)內(nèi)存設(shè)備為其設(shè)計(jì)帶來了新的挑戰(zhàn)：

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

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

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

本文設(shè)計(jì)主要基于以下4個(gè)觀察：

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

2) B+樹節(jié)點(diǎn)占用率通常為70%左右[11].

3) 在有序節(jié)點(diǎn)內(nèi)，插入或刪除一組數(shù)據(jù)會(huì)造成平均50%的數(shù)據(jù)移動(dòng)，這將帶來大量的有序持久化操作.

4) 同節(jié)點(diǎn)內(nèi)，插入操作能夠大概率與之前發(fā)生的刪除操作結(jié)合，進(jìn)而減少數(shù)據(jù)的移動(dòng)距離.

本文針對(duì)有序節(jié)點(diǎn)進(jìn)行優(yōu)化，主要貢獻(xiàn)包括3個(gè)方面:

Fig. 1 Updating the node with three strategies圖1 節(jié)點(diǎn)的3種更新方法

1) 設(shè)計(jì)了一種基于節(jié)點(diǎn)內(nèi)數(shù)據(jù)真實(shí)分布的數(shù)據(jù)單向移動(dòng)算法.通過原地刪除的方式，減少刪除帶來的持久化開銷.利用刪除操作在節(jié)點(diǎn)內(nèi)留下的空位，減少后續(xù)插入操作造成的數(shù)據(jù)移動(dòng)，進(jìn)而減少數(shù)據(jù)持久化操作數(shù)量.

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

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

1 研究背景

1.1 節(jié)點(diǎn)更新方式

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

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

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

3) 寫時(shí)復(fù)制.如圖1(c)所示，當(dāng)我們要對(duì)節(jié)點(diǎn)進(jìn)行更新時(shí)，首先分配一個(gè)新的節(jié)點(diǎn)，將原始節(jié)點(diǎn)數(shù)據(jù)拷貝到新節(jié)點(diǎn)中，然后將相應(yīng)更新操作在新節(jié)點(diǎn)內(nèi)進(jìn)行，更新完成后，通過修改父節(jié)點(diǎn)內(nèi)指針使新節(jié)點(diǎn)替換原始節(jié)點(diǎn).寫時(shí)復(fù)制不需要額外日志保證更新的原子性，但會(huì)引起顯著的寫放大，在樹結(jié)構(gòu)中尤為明顯，如產(chǎn)生一個(gè)“自底而上”的拷貝.

文獻(xiàn)[12]中通過對(duì)比分析在PM環(huán)境下的3種更新策略，提出原地更新方式更適用于基于PM的B+樹節(jié)點(diǎn)更新.在原地更新條件下，由于節(jié)點(diǎn)內(nèi)數(shù)據(jù)排布方式不同，增刪查改等操作細(xì)節(jié)也需要相應(yīng)的變化.

1.2 節(jié)點(diǎn)數(shù)據(jù)排布方式及其更新方式

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

1.3 失敗原子性及其保證

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

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

1) 若需要更新的數(shù)據(jù)量小于等于8 B，則可直接對(duì)數(shù)據(jù)進(jìn)行更新操作.

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

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

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

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

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

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

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

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

1.4 相關(guān)研究

為了減少基于PM的B+樹持久化開銷，目前相關(guān)研究根據(jù)存儲(chǔ)架構(gòu)不同可分為：基于DRAM+PM的B+樹與基于單一PM架構(gòu)的B+樹.基于DRAM+PM架構(gòu)的部分主要相關(guān)研究如下：

1) NV-Tree[19].內(nèi)部節(jié)點(diǎn)數(shù)據(jù)有序且存儲(chǔ)在DRAM內(nèi)，該設(shè)計(jì)能夠大幅提高數(shù)據(jù)查找速度；葉子節(jié)點(diǎn)無序且存儲(chǔ)在PM內(nèi)，在該設(shè)計(jì)下每次數(shù)據(jù)插入僅需要一次持久化操作，能夠大幅減少寫入開銷.然而，系統(tǒng)崩潰后，內(nèi)部節(jié)點(diǎn)的重構(gòu)需要消耗大量時(shí)間.

2) FP-Tree[20].與NV-Tree不同的是，F(xiàn)P-Tree為葉子節(jié)點(diǎn)添加了一組元數(shù)據(jù)(指紋)用以管理無序的數(shù)據(jù)，每一個(gè)key對(duì)應(yīng)一個(gè)1 B的散列值.查找操作通過優(yōu)先訪問元數(shù)據(jù)，提高了Cache命中率.同時(shí)，F(xiàn)P-Tree還采用硬件事務(wù)內(nèi)存來保證內(nèi)部節(jié)點(diǎn)的并發(fā)性.

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

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

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

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

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

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

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

2 基于PM的單向移動(dòng)算法

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

本節(jié)將對(duì)本文設(shè)計(jì)的基于PM的單向移動(dòng)算法進(jìn)行詳細(xì)描述.主要從節(jié)點(diǎn)內(nèi)結(jié)構(gòu)、查找操作、插入操作、刪除操作、數(shù)據(jù)可見性與系統(tǒng)崩潰后恢復(fù)6個(gè)方面進(jìn)行.

2.1 節(jié)點(diǎn)內(nèi)結(jié)構(gòu)

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

2.2 查找操作

每次查找一個(gè)節(jié)點(diǎn)之前，首先驗(yàn)證位圖的可用性，若位圖時(shí)間戳過期，則根據(jù)原始數(shù)據(jù)進(jìn)行重構(gòu)，通過遍歷數(shù)據(jù)完成重構(gòu)后同時(shí)返回查找結(jié)果；若位圖可用，則根據(jù)位圖對(duì)數(shù)據(jù)進(jìn)行二分查找.查找過程中，若位圖相應(yīng)標(biāo)記為0，則選擇附近的數(shù)據(jù)進(jìn)行比較.重復(fù)上述操作直至找到數(shù)據(jù)位置.為防止節(jié)點(diǎn)分裂過程中發(fā)生故障，查找操作還需要檢測兄弟節(jié)點(diǎn)內(nèi)數(shù)據(jù).具體細(xì)節(jié)分析見3.2節(jié).

2.3 插入操作

插入操作所引起的數(shù)據(jù)移動(dòng)過程如圖3所示：

Fig. 3 Data changing after inserting 13 in the node圖3 插入13后節(jié)點(diǎn)內(nèi)數(shù)據(jù)的變化

節(jié)點(diǎn)初始為執(zhí)行過多次原地刪除之后的狀態(tài)：節(jié)點(diǎn)內(nèi)存在許多已經(jīng)被刪除的數(shù)據(jù)，此類數(shù)據(jù)直接由位圖中的0直觀表示，在原始數(shù)據(jù)中該key值兩側(cè)value相同，在位圖有效期間不需修正.具體插入過程如算法1所示：

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

① if 位圖不合法 then

②reconstruct_node();*重構(gòu)位圖*

③ 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;

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

2.4 刪除操作

刪除操作的原理是使待刪除的數(shù)據(jù)對(duì)讀操作不可見.在本文設(shè)計(jì)中，刪除操作采用重復(fù)value值的方式使刪除的數(shù)據(jù)不可見，由于value值長度為8 B，因此采用一次原子操作即可完成.重復(fù)value值的選擇通常為前一組數(shù)據(jù)的value值，若被刪除的是第1組數(shù)據(jù)，則value設(shè)置為兄弟節(jié)點(diǎn)指針(葉節(jié)點(diǎn))或最左側(cè)子節(jié)點(diǎn)指針(內(nèi)部節(jié)點(diǎn)).此過程可視為我們?nèi)藶榈刂圃炝艘淮伪恢袛嗟木哂惺≡有员ＷC的數(shù)據(jù)移動(dòng)操作.我們可以在邏輯上認(rèn)為節(jié)點(diǎn)內(nèi)存在很多空位，這些空位通過位圖直觀展示.待刪除數(shù)據(jù)value值更新后，再將位圖相應(yīng)位置設(shè)置為0，即完成了一次刪除操作.刪除操作對(duì)原始數(shù)據(jù)的影響與插入操作數(shù)據(jù)移動(dòng)過程中發(fā)生系統(tǒng)崩潰后造成的影響相同，均可以通過讀操作進(jìn)行修正(僅修正讀操作的結(jié)果，不需要對(duì)原始數(shù)據(jù)修改).刪除操作完成后若位圖值為0，即節(jié)點(diǎn)內(nèi)無有效數(shù)據(jù)，則將該節(jié)點(diǎn)從父節(jié)點(diǎn)內(nèi)刪除，由于本文混合負(fù)載中刪除比例較低，因此不會(huì)造成顯著的空間浪費(fèi).

2.5 數(shù)據(jù)的可見性

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

在插入操作導(dǎo)致的數(shù)據(jù)移動(dòng)過程中，重復(fù)value值以及之間的不可見key也會(huì)作相應(yīng)移動(dòng)，因此發(fā)生系統(tǒng)崩潰時(shí)產(chǎn)生的不一致仍可通過讀操作驗(yàn)證是否有重復(fù)value來修正.

2.6 系統(tǒng)崩潰后的恢復(fù)

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

3 基于PM的單向移動(dòng)B+樹

本節(jié)詳細(xì)描述了應(yīng)用單向移動(dòng)算法后B+樹的重均衡(rebalancing)策略.主要包括選擇性重均衡策略操作、節(jié)點(diǎn)分裂與內(nèi)部整合等操作.

3.1 選擇性重均衡操作

由于我們?cè)O(shè)計(jì)的算法中不使用數(shù)據(jù)修復(fù)操作，因此節(jié)點(diǎn)內(nèi)會(huì)產(chǎn)生刪除與系統(tǒng)崩潰產(chǎn)生的空位.盡管該空位能夠通過位圖有效識(shí)別，但會(huì)造成節(jié)點(diǎn)內(nèi)疏松的結(jié)構(gòu)，影響節(jié)點(diǎn)空間利用率.當(dāng)節(jié)點(diǎn)無法插入新數(shù)據(jù)時(shí)，若節(jié)點(diǎn)內(nèi)空間利用率較低，分裂操作相較于節(jié)點(diǎn)內(nèi)部整合操作開銷較大.因此我們需要通過位圖分析節(jié)點(diǎn)內(nèi)空間利用率與數(shù)據(jù)分布，選擇重均衡策略.

在本文的設(shè)計(jì)中，所有重均衡策略均由插入操作觸發(fā)，若數(shù)據(jù)無法被插入到節(jié)點(diǎn)內(nèi)，則需要根據(jù)節(jié)點(diǎn)內(nèi)空間利用率及數(shù)據(jù)分布情況選擇相應(yīng)的重均衡操作.目前本文采取的重均衡策略包括分裂與節(jié)點(diǎn)內(nèi)部整合.為便于表述，我們?cè)O(shè)定2個(gè)關(guān)于重均衡策略選擇的參數(shù)P1與P2.P1用于表示當(dāng)前數(shù)據(jù)能否插入到當(dāng)前節(jié)點(diǎn)內(nèi)；P2為當(dāng)前節(jié)點(diǎn)的空間利用率，用于判斷應(yīng)選擇何種重均衡策略.具體過程如下：

找到數(shù)據(jù)插入位置后，根據(jù)位圖所示數(shù)據(jù)分布判斷節(jié)點(diǎn)內(nèi)是否能夠通過移動(dòng)數(shù)據(jù)為待插入的數(shù)據(jù)提供空間.若能夠提供空間，則P1=true；若無法提供空間則P1=false.

若P1=true，繼續(xù)完成插入操作.若P1=false，根據(jù)位圖獲得當(dāng)前P2值.若P2值小于閾值T，即節(jié)點(diǎn)內(nèi)空間利用率小于T，則進(jìn)行內(nèi)部整合操作，使節(jié)點(diǎn)內(nèi)數(shù)據(jù)緊致，若P2≥T，則進(jìn)行分裂操作.實(shí)驗(yàn)證明節(jié)點(diǎn)內(nèi)空缺比例為20%，設(shè)T=0.7時(shí)，能夠在保證性能的同時(shí)減少樹0.1%左右的空間消耗.

3.2 節(jié)點(diǎn)分裂

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

算法2.單向移動(dòng)樹分裂算法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

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

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

3.3 節(jié)點(diǎn)內(nèi)部整合

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

4 實(shí)驗(yàn)與結(jié)果

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

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

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

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

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

4.2 單一負(fù)載測試

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

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

性能評(píng)估結(jié)果如圖4所示，3種版本的ODS相較于其他2種樹，刪除性能均大幅提高，所用時(shí)間為FAST&FAIR的32.2%～34.4%，wB+樹的3.6%～4.5%.這是因?yàn)槲覀儾扇〉脑貏h除操作能夠大幅減少刪除操作引起的數(shù)據(jù)移動(dòng)，進(jìn)而減少持久化操作，提高性能.稀疏版本ODS插入操作性能在3種延遲環(huán)境下，所用時(shí)間分別為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能夠有效減少插入操作引起的數(shù)據(jù)移動(dòng)距離，進(jìn)而減少持久化操作數(shù)量，從而提高了插入性能.查找操作在延遲較高的情況下性能低于FAST&FAIR與wB+樹.這是由于稀疏化結(jié)構(gòu)導(dǎo)致查找的數(shù)據(jù)量增多，盡管我們使用了位圖加速數(shù)據(jù)查找速度，但只是單純減少了處理器層面的計(jì)算操作，需要處理器實(shí)際處理的cache line增多了，此時(shí)內(nèi)存性能成為瓶頸，因此性能對(duì)內(nèi)存延遲比較敏感.

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

4.3 合成負(fù)載測試

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

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

性能結(jié)果如圖5所示：圖5(a)顯示了60%插入、20%刪除、20%查找條件下5種索引結(jié)構(gòu)的性能.相較于FAST&FAIR，不同延遲下，3個(gè)版本ODS性能分別提高了14.1%，14.6%，11.7%.相較于wB+樹，不同延遲下3個(gè)版本ODS性能分別提高了82.9%，74.8%，75.4%.圖5(b)顯示了20%插入，20%刪除，60%查找條件下5種索引結(jié)構(gòu)的性能.相較于FAST&FAIR，不同延遲下，3個(gè)版本ODS性能分別提高了18.1%，18.8%，22.1%.相較于wB+樹，不同延遲下3個(gè)版本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 不同合成負(fù)載條件下各索引結(jié)構(gòu)在不同PM延遲下的性能

5 總 結(jié)

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