王永鋒,陳志廣
中山大學(xué)計(jì)算機(jī)學(xué)院,廣東 廣州 510006
非易失性內(nèi)存是一種新興的存儲(chǔ)介質(zhì),其具備字節(jié)可尋址、內(nèi)存級(jí)別讀寫時(shí)延的特性,這給當(dāng)前大量的存儲(chǔ)系統(tǒng)帶來(lái)了根本性的變革。非易失性內(nèi)存正在迅速發(fā)展,現(xiàn)有的大部分非易失性內(nèi)存(如相變內(nèi)存[1]、STT-RAM[2]等)仍處于研究階段,但由美光科技有限公司和英特爾聯(lián)合研制的傲騰持久內(nèi)存(基于3D XPoint[3])已經(jīng)發(fā)布,并且投入市場(chǎng)。由此,在存儲(chǔ)系統(tǒng)中盡可 能發(fā)揮非易失性內(nèi)存性能優(yōu)勢(shì)的需求越發(fā)迫切。其中,面向非易失內(nèi)存研發(fā)新型持久索引數(shù)據(jù)結(jié)構(gòu)是解決該問(wèn)題的關(guān)鍵。
在存儲(chǔ)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)中,持久索引數(shù)據(jù)結(jié)構(gòu)是核心之一。文件系統(tǒng)中文件路徑到索引節(jié)點(diǎn)的尋址、大文件中偏移量到指定數(shù)據(jù)塊的尋址、鍵值存儲(chǔ)系統(tǒng)中根據(jù)鍵尋找值的數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)中的聚集索引等,都需要持久存儲(chǔ)的索引數(shù)據(jù)結(jié)構(gòu),且這些持久索引數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)對(duì)系統(tǒng)本身的性能至關(guān)重要。但這些持久索引數(shù)據(jù)結(jié)構(gòu)目前大多面向傳統(tǒng)存儲(chǔ)設(shè)備進(jìn)行優(yōu)化,而不能高效利用非易失性內(nèi)存的硬件特性。將這些持久索引數(shù)據(jù)結(jié)構(gòu)在非易失性內(nèi)存上重新設(shè)計(jì)實(shí)現(xiàn),并面向非易失性內(nèi)存的硬件特性進(jìn)行優(yōu)化,能夠大大降低存儲(chǔ)系統(tǒng)的時(shí)延、提升吞吐量。
近年來(lái),已經(jīng)有一些工作對(duì)非易失性內(nèi)存上的存儲(chǔ)系統(tǒng)進(jìn)行了深入的探討和研究。陳游旻等人[4]在大數(shù)據(jù)環(huán)境下分析了基于新型存儲(chǔ)硬件進(jìn)行存儲(chǔ)系統(tǒng)構(gòu)建的挑戰(zhàn)和趨勢(shì);Liu H K等人[5]對(duì)非易失性內(nèi)存下的內(nèi)存架構(gòu)設(shè)計(jì)、持久內(nèi)存管理、性能優(yōu)化和功耗管理、編程框架以及非易失性內(nèi)存之上的應(yīng)用進(jìn)行了全面的綜述;Lersch L等人[6]將基于模擬非易失性內(nèi)存設(shè)計(jì)的有序索引數(shù)據(jù)結(jié)構(gòu)進(jìn)行分析,并在英特爾傲騰持久內(nèi)存上進(jìn)行了測(cè)試;Hu D K等人[7]則針對(duì)面向非易失性內(nèi)存構(gòu)建的哈希表進(jìn)行了測(cè)試和分析。另外,鄧鎮(zhèn)龍等人[8]將非易失內(nèi)存與MPIIO相結(jié)合,大大提升了應(yīng)用在高性能集群上的讀寫性能;楊青霖等人[9]提出的高效數(shù)據(jù)緩存方法顯著提升了存儲(chǔ)系統(tǒng)的讀寫性能。這些工作對(duì)在非易失性內(nèi)存上設(shè)計(jì)存儲(chǔ)系統(tǒng)具有重要的指導(dǎo)意義。本文從持久索引數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)出發(fā),對(duì)不同的設(shè)計(jì)之間的差異進(jìn)行細(xì)粒度的對(duì)比。
提高持久索引數(shù)據(jù)結(jié)構(gòu)的性能是實(shí)現(xiàn)低時(shí)延、高吞吐的現(xiàn)代存儲(chǔ)系統(tǒng)亟須解決的問(wèn)題。針對(duì)大量在非易失性內(nèi)存上優(yōu)化持久索引數(shù)據(jù)結(jié)構(gòu)的工作,筆者對(duì)其進(jìn)行分類、匯總、對(duì)比,厘清索引數(shù)據(jù)結(jié)構(gòu)的發(fā)展主線,總結(jié)其中的關(guān)鍵挑戰(zhàn),并對(duì)其發(fā)展趨勢(shì)進(jìn)行展望。
索引數(shù)據(jù)結(jié)構(gòu)是一種能夠存儲(chǔ)鍵值對(duì)映射的數(shù)據(jù)結(jié)構(gòu)。常用的數(shù)組僅能實(shí)現(xiàn)高效的查詢,無(wú)法實(shí)現(xiàn)高效的插入操作,而設(shè)計(jì)良好的索引數(shù)據(jù)結(jié)構(gòu)對(duì)于查詢和插入操作,都能達(dá)到對(duì)數(shù)時(shí)間復(fù)雜度,甚至是常數(shù)時(shí)間復(fù)雜度,這樣的性能優(yōu)勢(shì)使其在內(nèi)存系統(tǒng)和外存系統(tǒng)中均得到廣泛應(yīng)用。索引數(shù)據(jù)結(jié)構(gòu)面向的場(chǎng)景種類繁多,針對(duì)不同的場(chǎng)景,索引數(shù)據(jù)結(jié)構(gòu)有多種不同的實(shí)現(xiàn),本文關(guān)注需要持久存儲(chǔ)在存儲(chǔ)設(shè)備上的索引數(shù)據(jù)結(jié)構(gòu),這樣的索引數(shù)據(jù)結(jié)構(gòu)被稱為持久索引數(shù)據(jù)結(jié)構(gòu)(以下簡(jiǎn)稱索引數(shù)據(jù)結(jié)構(gòu))。
在不同的場(chǎng)景中,對(duì)索引數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的數(shù)據(jù)有不同的假定。構(gòu)建在關(guān)系型數(shù)據(jù)庫(kù)中的索引數(shù)據(jù)結(jié)構(gòu)往往需要處理大量的范圍查詢,即查詢?cè)谀硞€(gè)區(qū)間內(nèi)的所有鍵值對(duì)。為了高效支持范圍查詢,索引數(shù)據(jù)結(jié)構(gòu)需要維護(hù)數(shù)據(jù)的有序性,并針對(duì)范圍查詢進(jìn)行優(yōu)化。而在一些鍵值存儲(chǔ)系統(tǒng)中,可能僅輸入指定的鍵,要求系統(tǒng)返回對(duì)應(yīng)的值,不需要范圍查詢,此時(shí)底層的索引數(shù)據(jù)結(jié)構(gòu)就不需要額外的開銷來(lái)維護(hù)數(shù)據(jù)的有序性,相鄰的鍵值對(duì)可以存放在存儲(chǔ)設(shè)備上的任意位置。因此,根據(jù)其內(nèi)部數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)有序性的維護(hù)情況,可以將索引數(shù)據(jù)結(jié)構(gòu)分為有序索引數(shù)據(jù)結(jié)構(gòu)和無(wú)序索引數(shù)據(jù)結(jié)構(gòu)。
有序索引數(shù)據(jù)結(jié)構(gòu)需要嚴(yán)格維護(hù)數(shù)據(jù)結(jié)構(gòu)中的有序性。對(duì)于每一次寫入操作,有序索引數(shù)據(jù)結(jié)構(gòu)都需要根據(jù)插入的數(shù)據(jù)對(duì)整體的結(jié)構(gòu)進(jìn)行修改以保證有序性,因此范圍查詢的性能最好。哈希表完全不維護(hù)數(shù)據(jù)結(jié)構(gòu)中的有序性,因此一般而言額外開銷最小,但無(wú)法對(duì)范圍查詢進(jìn)行優(yōu)化。另外,在有序索引數(shù)據(jù)結(jié)構(gòu)中,維護(hù)有序性會(huì)帶來(lái)大量開銷,因此一些面向?qū)憙?yōu)化的有序索引數(shù)據(jù)結(jié)構(gòu)會(huì)放松一部分對(duì)有序性的約束,從而提升寫性能。
除了傳統(tǒng)索引,新興的學(xué)習(xí)索引(learning index)將索引任務(wù)變?yōu)橐粋€(gè)回歸問(wèn)題,能夠根據(jù)輸入數(shù)據(jù)自適應(yīng)地調(diào)整數(shù)據(jù)的存放模式。
為了能夠讓索引數(shù)據(jù)結(jié)構(gòu)在傳統(tǒng)的存儲(chǔ)設(shè)備(如機(jī)械硬盤、固態(tài)硬盤)中進(jìn)行持久存儲(chǔ),并且高效地利用硬件特性,很多研究人員進(jìn)行了大量的研究工作。隨著新型存儲(chǔ)設(shè)備(如非易失性內(nèi)存)漸漸成熟,研究人員分析了非易失性內(nèi)存和傳統(tǒng)存儲(chǔ)設(shè)備的差異,并且就索引數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)提出了不少新穎的方法。具體地說(shuō),在非易失性內(nèi)存上實(shí)現(xiàn)持久索引數(shù)據(jù)結(jié)構(gòu),需要解決以下3個(gè)問(wèn)題。
● 如何減少在操作持久索引數(shù)據(jù)結(jié)構(gòu)時(shí)的軟件開銷?
● 如何針對(duì)特定的持久化語(yǔ)義實(shí)現(xiàn)崩潰一致性保證?
● 在非易失性內(nèi)存上如何利用多核架構(gòu)高效并發(fā)處理讀寫請(qǐng)求?
索引數(shù)據(jù)結(jié)構(gòu)的軟件開銷逐漸成為限制性能的關(guān)鍵因素。傳統(tǒng)存儲(chǔ)設(shè)備的持久化時(shí)延往往是微秒級(jí)甚至毫秒級(jí),而內(nèi)存的時(shí)延最多不過(guò)一百多納秒,因此在傳統(tǒng)存儲(chǔ)設(shè)備上的持久索引數(shù)據(jù)結(jié)構(gòu)并不需要過(guò)多地關(guān)注與內(nèi)存讀寫相關(guān)的軟件開銷,而是更多地關(guān)注如何通過(guò)寫聚合等方式盡可能減小持久化的開銷。但在非易失性內(nèi)存的背景之下,持久化開銷與內(nèi)存的讀寫相近,如傲騰內(nèi)存的寫時(shí)延為62 ns,而讀時(shí)延為169~305 ns[10],過(guò)去的一些略微提高軟件開銷、降低持久化開銷的優(yōu)化手段無(wú)法被直接應(yīng)用在非易失性內(nèi)存中,軟件開銷對(duì)性能的影響大大增加[11]。同時(shí),緩存未命中、流水線停頓等體系架構(gòu)層面的性能損失也會(huì)對(duì)構(gòu)建在非易失性內(nèi)存之上的索引數(shù)據(jù)結(jié)構(gòu)有較大的影響。如為了進(jìn)一步降低開銷,MOD[12]將持久化所需要的內(nèi)存屏障進(jìn)一步降低,以提升性能。另外,為了降低開銷,還需要盡可能解決讀寫放大的問(wèn)題,有工作指出[10],由于傲騰內(nèi)存的內(nèi)部讀寫粒度為256 byte,小于256 byte的讀寫均可能帶來(lái)寫放大,這會(huì)對(duì)索引數(shù)據(jù)結(jié)構(gòu)的性能有所影響。
同時(shí),需要重新思考崩潰一致性的實(shí)現(xiàn)。傳統(tǒng)存儲(chǔ)設(shè)備基于塊設(shè)備的抽象、操作和讀寫都以塊為單位(更具體地說(shuō),機(jī)械硬盤的讀寫粒度為扇區(qū),大小一般是512 byte,固態(tài)硬盤的讀寫粒度為閃存頁(yè),大小一般是4 KB),只要相應(yīng)的塊或頁(yè)被寫入存儲(chǔ)設(shè)備,即完成了持久化。但在非易失性內(nèi)存中,一般的store指令原子操作粒度僅為8 byte,且該指令會(huì)由于CPU的亂序執(zhí)行而難以按照開發(fā)者預(yù)想的順序?qū)懭氪鎯?chǔ)。另外,數(shù)據(jù)會(huì)首先寫入CPU的L1/L2/L3緩存中,而CPU的緩存并不能保證持久化。因此,為了保證讓數(shù)據(jù)在非易失性內(nèi)存上持久化存儲(chǔ),需要在store指令后相應(yīng)地加入內(nèi)存屏障和刷寫緩存行指令(如clflush或clwb),將緩存行從CPU緩存刷到非易失性內(nèi)存里。由此,非易失性內(nèi)存上需要新的方法來(lái)保證崩潰一致性。
另外,面對(duì)海量的讀寫請(qǐng)求,需要設(shè)計(jì)適合多核架構(gòu)的索引數(shù)據(jù)結(jié)構(gòu)。由于極低的時(shí)延以及字節(jié)可尋址的特性,與傳統(tǒng)存儲(chǔ)設(shè)備相比,構(gòu)建在非易失性內(nèi)存之上的索引數(shù)據(jù)結(jié)構(gòu)的吞吐量有多個(gè)數(shù)量級(jí)的優(yōu)勢(shì),在多核架構(gòu)上非易失性內(nèi)存的優(yōu)勢(shì)將更加顯著。盡管如此,由于前面提到的兩個(gè)問(wèn)題,能夠在動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(dynamic random access memory,DRAM)上使用的并行索引數(shù)據(jù)結(jié)構(gòu)并不能直接用于非易失性內(nèi)存上。另外,由于非易失性內(nèi)存額外引入的刷寫緩存行操作,以及傲騰內(nèi)存在線程數(shù)過(guò)多時(shí)帶寬反而會(huì)下降[10],需要對(duì)索引數(shù)據(jù)結(jié)構(gòu)上的并發(fā)讀寫做進(jìn)一步的優(yōu)化,才能夠充分適應(yīng)非易失性內(nèi)存的特性。
針對(duì)上述3個(gè)問(wèn)題,目前已有很多研究給出了針對(duì)非易失性內(nèi)存的索引數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。本文主要分析其中兩種常見的索引數(shù)據(jù)結(jié)構(gòu)(B/B+樹(B/B+-Tree)和哈希表),并總結(jié)了它們?cè)诜且资詢?nèi)存上的發(fā)展。
有序索引數(shù)據(jù)結(jié)構(gòu)能夠高效地處理范圍查詢?nèi)蝿?wù),其中的一種實(shí)現(xiàn)——B/B+-Tree能夠顯著地減少磁盤I/O的次數(shù),已經(jīng)被廣泛應(yīng)用到InnoDB等存儲(chǔ)引擎中。針對(duì)B/B+-Tree在非易失性內(nèi)存上的實(shí)現(xiàn),筆者總結(jié)了下面的工作,并分析了其優(yōu)劣。其中2011—2018年的工作都是在模擬的非易失內(nèi)存模擬器上完成的,之后的工作才開始在真實(shí)的傲騰內(nèi)存上實(shí)現(xiàn)。
2011年Venkataraman S等人[13]首次提出了針對(duì)非易失性內(nèi)存設(shè)計(jì)的CDDS B-Tree。他們使用mfence(內(nèi)存屏障)和clflush(刷寫緩存行)的組合指令來(lái)保證數(shù)據(jù)按順序?qū)懭敕且资詢?nèi)存中,在B-Tree的基礎(chǔ)上,使用多版本機(jī)制實(shí)現(xiàn)更新操作,另外通過(guò)寫時(shí)復(fù)制實(shí)現(xiàn)節(jié)點(diǎn)的分裂和合并,從而減少了額外的寫入,無(wú)須通過(guò)寫日志保證崩潰一致性。但是使用多版本和寫時(shí)復(fù)制的代價(jià)是需要后臺(tái)線程來(lái)進(jìn)行垃圾回收,這會(huì)帶來(lái)額外的性能開銷。
2015年Yang J等人[14]對(duì)非易失性內(nèi)存上的B+-Tree進(jìn)行了改進(jìn),提出了能夠進(jìn)一步降低維護(hù)一致性開銷的NV-Tree。通過(guò)深入分析,他們發(fā)現(xiàn)在葉子節(jié)點(diǎn)維護(hù)順序存放的鍵值需要刷寫多個(gè)緩存行,另外還需要維護(hù)B+-Tree的內(nèi)部節(jié)點(diǎn)的崩潰一致性,這些引入了大量開銷。為了進(jìn)一步優(yōu)化,該文章提出可以讓葉子節(jié)點(diǎn)存放的鍵值對(duì)亂序,具體的實(shí)現(xiàn)是使用日志結(jié)構(gòu)寫入。另外,由于內(nèi)部節(jié)點(diǎn)可以重建,不需要額外維護(hù)內(nèi)部節(jié)點(diǎn)的崩潰一致性。但由于葉子節(jié)點(diǎn)沒(méi)有維護(hù)順序,這種方法對(duì)讀操作的性能造成了一定的影響。
2015年Chen S M等人[15]基于參考文獻(xiàn)[14]進(jìn)一步優(yōu)化了B+-Tree在非易失性內(nèi)存上的實(shí)現(xiàn),提出了wB+-Tree。如果葉子節(jié)點(diǎn)沒(méi)有維護(hù)鍵值對(duì)的順序,就會(huì)影響讀操作的性能,因此該文章在葉子節(jié)點(diǎn)中使用位圖記錄槽的分配情況,并進(jìn)一步增加槽數(shù)組(slot array)用于記錄鍵值的順序,優(yōu)化讀操作。另外針對(duì)崩潰一致性的實(shí)現(xiàn),wB+-Tree在插入操作和更新操作中,都先在節(jié)點(diǎn)中尋找空的或無(wú)用的槽寫入并保證持久化,然后通過(guò)一次8 byte的原子寫入和持久化修改元數(shù)據(jù),從而完成操作。這樣的實(shí)現(xiàn)使用非易失性內(nèi)存上的8 byte原子寫入指令保證崩潰一致性,但節(jié)點(diǎn)分裂操作依然使用了傳統(tǒng)的重做日志方法,帶來(lái)了額外的寫入。
2016年Oukid I等人[16]結(jié)合參考文獻(xiàn)[14]提到的分析,在非易失性內(nèi)存上進(jìn)一步優(yōu)化了B+-Tree,提出了FPTree?;趦?nèi)部節(jié)點(diǎn)可以通過(guò)葉子節(jié)點(diǎn)重建的原理,F(xiàn)PTree將所有內(nèi)部節(jié)點(diǎn)都放在DRAM里,只將葉子節(jié)點(diǎn)持久化存放在非易失性內(nèi)存中,減小維護(hù)崩潰一致性的開銷。同時(shí)FPTree在葉子節(jié)點(diǎn)中存放了每個(gè)鍵各1 byte的指紋,用于快速判斷指定鍵是否在該葉子節(jié)點(diǎn)中,從而降低葉子節(jié)點(diǎn)無(wú)序存放鍵值對(duì)讀操作的影響。為了進(jìn)一步降低軟件開銷,優(yōu)化并發(fā),F(xiàn)PTree將分配內(nèi)存的開銷分?jǐn)偟蕉鄠€(gè)節(jié)點(diǎn)上,并結(jié)合硬件事務(wù)內(nèi)存降低了并發(fā)訪問(wèn)的開銷。
2018年Arulraj J等人[17]基于PMwCAS在非易失性內(nèi)存上實(shí)現(xiàn)了能夠無(wú)鎖并發(fā)的BzTree。比較并交換(compare and swap,CAS)指令是實(shí)現(xiàn)無(wú)鎖并發(fā)算法的關(guān)鍵指令,其能夠?qū)蝹€(gè)字節(jié)進(jìn)行原子的比較和交換操作,而PMwCAS[18]將該操作擴(kuò)展到多個(gè)字節(jié)且保證非易失性內(nèi)存上的持久化。通過(guò)PMwCAS提供的原子性,開發(fā)者可以避免非易失性內(nèi)存帶來(lái)的編程細(xì)節(jié),使用通用的方法在非易失性內(nèi)存上實(shí)現(xiàn)支持崩潰一致性且無(wú)鎖并發(fā)的BzTree。
2018年Hwang D等人[19]在非易失性內(nèi)存上基于FAST(failure-atomic shift)&FAIR(failure atomic in-place rebalancing)算法實(shí)現(xiàn)了可容忍瞬時(shí)不一致的B+-Tree。由于一些不一致的情況可以通過(guò)修改讀操作來(lái)容忍,避免讀取錯(cuò)誤的內(nèi)容,作者首先通過(guò)FAST算法保證在節(jié)點(diǎn)內(nèi)部維護(hù)有序性時(shí),移動(dòng)鍵值對(duì)產(chǎn)生的不一致是可容忍的,然后FAIR算法能夠以類似的保證進(jìn)一步處理節(jié)點(diǎn)分裂或合并的情況。這個(gè)方法無(wú)須任何日志就能夠保證B+-Tree在任何操作中都處于不一致但可容忍的狀態(tài),同時(shí)由于內(nèi)部節(jié)點(diǎn)也存在于非易失性內(nèi)存中,基于該方法實(shí)現(xiàn)的B+-Tree崩潰后能夠馬上恢復(fù),而無(wú)須重建索引。
2020年Chen Y M等人[20]發(fā)現(xiàn)非易失性內(nèi)存上的B+-Tree有較嚴(yán)重的長(zhǎng)尾時(shí)延,經(jīng)過(guò)深入分析后,他們認(rèn)為在非易失性內(nèi)存中對(duì)葉子節(jié)點(diǎn)的結(jié)構(gòu)進(jìn)行改變的操作(排序和節(jié)點(diǎn)平衡)以及并發(fā)線程之間相互等待訪問(wèn)非易失性內(nèi)存是造成長(zhǎng)尾時(shí)延的根本原因?;谶@樣的分析,他們提出uTree。uTree的內(nèi)部節(jié)點(diǎn)組織與一般B+-Tree相同,存放在內(nèi)存上,而葉子節(jié)點(diǎn)分成內(nèi)存中的數(shù)組層與存放在非易失性內(nèi)存上的鏈表層。該設(shè)計(jì)能讓造成長(zhǎng)尾時(shí)延的操作在內(nèi)存上完成,而在非易失性內(nèi)存上可以并行操作鏈表的個(gè)別元素。這樣的設(shè)計(jì)緩解了長(zhǎng)尾時(shí)延,但也增加了索引數(shù)據(jù)結(jié)構(gòu)的內(nèi)存占用。
2020年Liu J H等人[21]在3D XPoint上優(yōu)化了B+-Tree,提出了LB+Trees。他們充分利用了3D XPoint上內(nèi)部介質(zhì)讀寫粒度為256 byte和持久化粒度為64 byte之間的差異,發(fā)現(xiàn)影響性能的是CacheLine的寫入,在CacheLine寫入數(shù)量相同的情況下,CacheLIne內(nèi)部臟字寫入是沒(méi)有影響的,進(jìn)而提出可以通過(guò)節(jié)點(diǎn)內(nèi)部鍵值對(duì)的移動(dòng)來(lái)減少內(nèi)部介質(zhì)讀寫。同時(shí)為了保證崩潰一致性,他們?cè)趙B+-Tree的實(shí)現(xiàn)上進(jìn)一步擴(kuò)展,基于類似的思路,利用8 byte的原子寫保證了包括節(jié)點(diǎn)分裂和聚合在內(nèi)的所有操作的崩潰一致性,無(wú)須寫日志,并且還能夠通過(guò)分布式頭元數(shù)據(jù)的方式擴(kuò)大葉子節(jié)點(diǎn)的大小(256 byte的倍數(shù))而不犧牲崩潰一致性。
B/B+-Tree在非易失內(nèi)存上的實(shí)現(xiàn)及優(yōu)缺點(diǎn)見表1。除了B/B+-Tree之外,在非易失性內(nèi)存上進(jìn)行優(yōu)化的有序索引數(shù)據(jù)結(jié)構(gòu)還包括基數(shù)樹(radix tree)以及其變體,如WORT[22]、P-ART[23]、HART[24]、DPTree[25]、ROART[26]等。這些工作從不同方面對(duì)上述3個(gè)關(guān)鍵問(wèn)題給出了不同的解決方案。從這些工作可以發(fā)現(xiàn),為了高效地利用非易失性內(nèi)存的性能,減小軟件開銷、通過(guò)避免日志寫入實(shí)現(xiàn)崩潰一致性、通過(guò)避免鎖的使用來(lái)實(shí)現(xiàn)高效的并發(fā)、結(jié)合處理器體系架構(gòu)和非易失性內(nèi)存的硬件特性來(lái)進(jìn)行優(yōu)化,已經(jīng)成為主流的方法。
表1 B+-Tree在非易失性內(nèi)存上的實(shí)現(xiàn)與優(yōu)缺點(diǎn)
隨著NoSQL存儲(chǔ)系統(tǒng)逐漸發(fā)展,無(wú)須維護(hù)數(shù)據(jù)有序性從而具備更小開銷和更簡(jiǎn)潔實(shí)現(xiàn)的哈希表目前在各種存儲(chǔ)系統(tǒng)中得到越來(lái)越廣泛的應(yīng)用,如MongoDB、HBase、Memcached等。在哈希表的設(shè)計(jì)中,需要解決的兩個(gè)核心問(wèn)題分別是哈希表擴(kuò)容和哈希沖突。哈希表擴(kuò)容指的是當(dāng)哈希表的容量不足以容納用戶需要寫入的所有數(shù)據(jù)時(shí),哈希表需要進(jìn)行容量擴(kuò)大,并根據(jù)需要將舊的數(shù)據(jù)重哈希到新的哈希表上。哈希沖突指的是哈希表中的單個(gè)桶(bucket)沒(méi)有空閑位置放置鍵值對(duì)的情況。
現(xiàn)有的針對(duì)哈希表的研究可分為兩類:動(dòng)態(tài)哈希和靜態(tài)哈希。在靜態(tài)哈希中,當(dāng)哈希表容量需要進(jìn)行擴(kuò)大時(shí),一般需要?jiǎng)?chuàng)建一個(gè)更大的哈希表,并將舊哈希表中的數(shù)據(jù)重新插入新的哈希表中,其擴(kuò)容的開銷與哈希表本身包含的數(shù)據(jù)量成正比。關(guān)于這種哈希表在非易失性內(nèi)存上的實(shí)現(xiàn),目前的研究成果如下。
Zuo P F等人[27]提出的Path-Hashing針對(duì)非易失性內(nèi)存環(huán)境下的哈希表,指出以往的哈希表設(shè)計(jì)會(huì)帶來(lái)大量的額外寫,這會(huì)極大地影響哈希表在非易失性內(nèi)存上的性能。因此他們提出了一個(gè)基于路徑的哈希表。該哈希表通過(guò)位置共享技術(shù)解決哈希沖突問(wèn)題,優(yōu)化了對(duì)CPU緩存的使用且不會(huì)帶來(lái)額外的寫。為了進(jìn)一步提高負(fù)載因子和讀寫性能,Path-Hashing還能夠使用兩個(gè)哈希函數(shù)構(gòu)建兩條搜索路徑,并進(jìn)行路徑壓縮,在緩解哈希沖突的同時(shí),減小路徑的深度。
Zuo P F等人[28]進(jìn)一步優(yōu)化了哈希表的寫入操作,提出了Level-Hashing。他們不僅提出了一種寫優(yōu)化的層次哈希結(jié)構(gòu),通過(guò)雙哈希函數(shù)和沖突后一次鍵值對(duì)的移動(dòng)來(lái)提升哈希表的負(fù)載因子,同時(shí)還實(shí)現(xiàn)了一種原地?cái)U(kuò)容機(jī)制,這讓Level-Hashing只需要對(duì)1/3的內(nèi)容進(jìn)行重哈希,將處于底層的內(nèi)容重新寫到頂層的哈希表中,即可完成擴(kuò)容。另外Level-Hashing還能夠以無(wú)須日志的方式保證插入、修改、刪除、擴(kuò)容操作的一致性,只有更新操作可能需要寫日志。
Chen Z Y等人[29]提出的CLevel-Hashing對(duì)哈希表的并發(fā)性能進(jìn)行了大量改進(jìn)。一方面,CLevel-Hashing能夠在后臺(tái)異步擴(kuò)容和重哈希,而不會(huì)阻塞操作,從而避免了等待擴(kuò)容導(dǎo)致的長(zhǎng)尾時(shí)延;另一方面,過(guò)去哈希表一般使用鎖來(lái)實(shí)現(xiàn)并發(fā),他們針對(duì)讀取、插入、更新、刪除操作均基于CAS原語(yǔ)實(shí)現(xiàn)了無(wú)鎖并發(fā)算法,從而避免鎖競(jìng)爭(zhēng),提升哈希表的擴(kuò)展性。
相對(duì)于靜態(tài)哈希,動(dòng)態(tài)哈希能夠根據(jù)用戶插入的鍵值對(duì)的數(shù)量靈活地?cái)U(kuò)大或縮小哈希表的容量,每次擴(kuò)容時(shí)只需要常數(shù)時(shí)間復(fù)雜度的開銷。
Nam M等人[30]在非易失性內(nèi)存中引入了可擴(kuò)展哈希CCEH(CacheLineconscious extendible hashing)?;谠嫉目蓴U(kuò)展哈希設(shè)計(jì),他們根據(jù)非易失性內(nèi)存的特性進(jìn)行了一些改進(jìn),包括將桶的大小設(shè)置為緩存行的整數(shù)倍,以及增加一層段(segment)來(lái)減少空間占用。同時(shí)他們還提出了一種崩潰恢復(fù)算法,使其能夠保證在修改CCEH和進(jìn)行段分裂時(shí)無(wú)須任何日志即可保證崩潰一致性。
Lu B T等人[31]進(jìn)一步提出了一種擴(kuò)展性更好的哈希表Dash。他們認(rèn)為不僅要優(yōu)化非易失性內(nèi)存上的寫入,還要盡量減少非易失性內(nèi)存上的讀取操作。因此他們對(duì)Dash做了兩方面的優(yōu)化。從哈希表本身的設(shè)計(jì)上,他們提出基于指紋對(duì)鍵的存在與否進(jìn)行快速的判斷以優(yōu)化讀取速度,同時(shí)在哈希沖突的解決上,他們使用哈希桶間自平衡的方法來(lái)提高哈希表的負(fù)載因子。同時(shí)Dash還能夠讓插入和更新操作均不需要用日志來(lái)保證崩潰一致性,僅在段分裂時(shí)需要使用重做日志。另外,Dash還使用了優(yōu)化的并發(fā)控制訪問(wèn),讀取不需要鎖的參與,寫時(shí)使用原子變量實(shí)現(xiàn)互斥訪問(wèn)。
Zou X M等人[32]提出了HMEH(hybrid memory extendible hashing)。他們?cè)贑CEH的基礎(chǔ)上,考慮到可擴(kuò)展哈希的目錄層可通過(guò)非易失性內(nèi)存上額外構(gòu)建的一顆基數(shù)樹來(lái)重建,因此將目錄層放到DRAM中,以減少非易失性內(nèi)存上的讀寫。另外他們還提出了一種利用8 byte原子寫實(shí)現(xiàn)的鍵值交錯(cuò)策略,使HMEH無(wú)須任何日志也無(wú)須顯式地刷寫緩存行就能夠保證一般操作的崩潰一致性。對(duì)于段分裂操作,基于之前設(shè)置的基數(shù)樹,HMEH實(shí)現(xiàn)了一種無(wú)須任何日志和寫時(shí)復(fù)制的分裂方法。
哈希表在非易失性內(nèi)存上的實(shí)現(xiàn)與優(yōu)缺點(diǎn)見表2,可以發(fā)現(xiàn),其發(fā)展趨勢(shì)與有序索引數(shù)據(jù)結(jié)構(gòu)是一致的,在充分利用硬件特性進(jìn)行優(yōu)化的同時(shí),無(wú)須日志的崩潰一致性保證和無(wú)鎖算法成為在非易失性內(nèi)存上高效實(shí)現(xiàn)索引數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵所在。
表2 哈希表在非易失性內(nèi)存上的實(shí)現(xiàn)與優(yōu)缺點(diǎn)
本文分別對(duì)B+樹和哈希表在非易失性內(nèi)存上的設(shè)計(jì)和實(shí)現(xiàn)進(jìn)行了深入的分析。根據(jù)兩者的發(fā)展發(fā)現(xiàn),在非易失性內(nèi)存上實(shí)現(xiàn)持久索引數(shù)據(jù)結(jié)構(gòu)所需要解決的3個(gè)問(wèn)題目前已有一致的趨勢(shì)。為了減小索引數(shù)據(jù)結(jié)構(gòu)的軟件開銷,現(xiàn)有研究會(huì)放松對(duì)數(shù)據(jù)有序性的維護(hù),減少內(nèi)存屏障與緩存行的刷寫,感知內(nèi)部存儲(chǔ)介質(zhì)的讀寫粒度以及盡可能減少額外寫,而對(duì)于崩潰一致性與適應(yīng)多核架構(gòu),則分別趨近于無(wú)須日志和無(wú)須加鎖的方法。
最后,對(duì)在非易失性內(nèi)存下高效實(shí)現(xiàn)索引數(shù)據(jù)結(jié)構(gòu)的過(guò)程中存在的一些挑戰(zhàn)進(jìn)行總結(jié)。
一是如何在保留崩潰一致性的同時(shí)利用DRAM進(jìn)一步優(yōu)化索引數(shù)據(jù)結(jié)構(gòu)的性能。目前的非易失性內(nèi)存盡管性能接近DRAM,但是其時(shí)延仍然比DRAM高好幾倍,且?guī)捀邮芟?。由于非易失性?nèi)存和DRAM之間的性能差距仍然不可忽略,現(xiàn)有的研究工作已經(jīng)在嘗試使用DRAM來(lái)優(yōu)化索引數(shù)據(jù)結(jié)構(gòu)的性能,但也有研究表明,在一些場(chǎng)景中,DRAM和非易失性內(nèi)存混用可能會(huì)由于額外的數(shù)據(jù)遷移造成性能損失,因此如何高效地利用DRAM來(lái)優(yōu)化索引數(shù)據(jù)結(jié)構(gòu)仍然是一個(gè)需要深入研究的問(wèn)題。
二是如何更進(jìn)一步地利用非易失性內(nèi)存的硬件特性對(duì)索引數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。非易失性內(nèi)存與DRAM類似,但又有其獨(dú)特的性質(zhì),之前的研究大多在使用DRAM模擬的非易失性內(nèi)存上完成,近兩年的研究工作大多基于英特爾傲騰持久內(nèi)存,指出過(guò)去的研究中存在的問(wèn)題,并對(duì)傲騰內(nèi)存的硬件特性進(jìn)行了一些適配。但一方面英特爾并沒(méi)有公布傲騰持久內(nèi)存的內(nèi)部原理和架構(gòu),研究人員只能通過(guò)猜測(cè)其硬件特性進(jìn)行優(yōu)化,另一方面還有更多的新型非易失性內(nèi)存存儲(chǔ)介質(zhì)未面市,這些存儲(chǔ)介質(zhì)可能具備不一樣的特性,在這樣的背景下,持久索引數(shù)據(jù)結(jié)構(gòu)需要具有更靈活的設(shè)計(jì)才能適應(yīng)存儲(chǔ)介質(zhì)的發(fā)展。
三是如何實(shí)現(xiàn)高效的非易失性內(nèi)存空間分配器。在索引數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)中,非易失性內(nèi)存空間的動(dòng)態(tài)分配是一個(gè)不可或缺的操作,其作為軟件開銷的一部分,對(duì)索引數(shù)據(jù)結(jié)構(gòu)的性能有較大影響。同時(shí)一個(gè)高效的非易失性內(nèi)存分配器要求避免永久性的內(nèi)存泄露,并支持高效的并發(fā)操作。然而現(xiàn)有的研究中大多僅關(guān)注數(shù)據(jù)結(jié)構(gòu)本身,忽略了這部分重要的軟件開銷,另外在DRAM中的內(nèi)存分配器也需要更進(jìn)一步的改進(jìn)才能充分利用非易失性內(nèi)存的特性。