基于PCM構(gòu)建的索引數(shù)據(jù)結(jié)構(gòu)設(shè)計研究

崔 瑩，劉 兵

（銅陵職業(yè)技術(shù)學(xué)院，安徽 銅陵 244000）

隨著大數(shù)據(jù)技術(shù)應(yīng)用的推廣，計算機(jī)系統(tǒng)對內(nèi)存的容量要求越來越高，需要足夠的頁面緩存來保證程序能夠快速執(zhí)行。馮諾依曼結(jié)構(gòu)計算機(jī)的處理器從大容量存儲中獲取數(shù)據(jù)一般都會花費許多時間,這已經(jīng)成為提升當(dāng)代計算機(jī)性能所能遇到的最大瓶頸。單純通過優(yōu)化算法來改善效果十分有限,需要通過構(gòu)建新的存儲系統(tǒng)才能改善。

隨著材料和存儲技術(shù)的發(fā)展，以相變存儲器(PCM，Phase change Memory)為代表的新型非易失性存儲（NVM，non-volatile memory）技術(shù)近年來取得了重大進(jìn)展，研究者們建議用新型NVM技術(shù)來代替?zhèn)鹘y(tǒng)存儲技術(shù),因而需要研究與其適配的高效率存儲系統(tǒng)。PCM技術(shù)的迅速發(fā)展讓學(xué)術(shù)界開始關(guān)注如何設(shè)計適用于PCM的數(shù)據(jù)索引結(jié)構(gòu)這個課題。不同于一些傳統(tǒng)研究項目，在這個新興領(lǐng)域目前我國專家學(xué)者暫處于較領(lǐng)先的水平。

一、背景知識

（一）PCM存儲器簡介

PCM的基本存儲原理是在元器件上施加不同的電流信號，使得相變材料（硫化物）發(fā)生物理相態(tài)的變化，從而產(chǎn)生導(dǎo)電性的差異來存儲數(shù)據(jù)。即使在斷電情況下PCM也能保存數(shù)據(jù)，同時數(shù)據(jù)擦寫速度還很快，是目前技術(shù)最成熟的新一代存儲器。

PCM技術(shù)的主要優(yōu)點在于存儲密度高和具有非易失性，前一個優(yōu)點可使得內(nèi)存容量比現(xiàn)在有所擴(kuò)大，后一個讓存儲器即使掉電數(shù)據(jù)仍可以長期保存，最長的期限可達(dá)10年。另外PCM還有字節(jié)可尋址、低能耗等特點。

PCM也有很明顯的缺點。首先這種存儲器較易磨損，讀寫次數(shù)有限一旦達(dá)到一定的次數(shù)，就無法對存儲在其中的數(shù)據(jù)進(jìn)行讀寫操作；其次PCM內(nèi)存寫速度緩慢讀寫速度不平衡，讀性能與DRAM相似（約1-5倍），但在寫運算中，DRAM速度約是它的5-50倍。因此，如果用PCM全部取代DRAM，引入實際內(nèi)存系統(tǒng)時，可能會產(chǎn)生意想不到的性能下降和壽命縮短的現(xiàn)象，因此目前主要是將兩種技術(shù)組成混合架構(gòu)投入實際應(yīng)用。

（二）PCM帶來的數(shù)據(jù)結(jié)構(gòu)問題

索引是重要的數(shù)據(jù)結(jié)構(gòu)，對系統(tǒng)性能有著重要的影響，在大數(shù)據(jù)應(yīng)用背景下，數(shù)據(jù)庫的性能主要體現(xiàn)在高效率的索引查找上。常見的索引結(jié)構(gòu)有以下幾種：B+樹、hash表等。B+樹形索引結(jié)構(gòu)在區(qū)間索引上占據(jù)優(yōu)勢，而hash結(jié)構(gòu)在查找單個值索引上有優(yōu)勢。比如：MYSQL的innodb引擎采用了B+樹索引結(jié)構(gòu)，而Memcache和redis采用了hash索引結(jié)構(gòu)。為了同時支持范圍查詢和單點查詢，也有學(xué)者提出了混合索引的設(shè)計。

以往的數(shù)據(jù)結(jié)構(gòu)都是為DRAM內(nèi)存設(shè)計的，提供對稱的讀寫速度，而PCM最明顯的一個特征就是讀寫速率的不平衡。這些索引結(jié)構(gòu)中插入，刪除和拆分等操作以及保持?jǐn)?shù)據(jù)的一致性的方法，均會引入較多的寫操作，對于PCM來說會帶來性能下降問題。

在現(xiàn)有的PCM性能提高研究中，已經(jīng)出現(xiàn)了對各類不同技術(shù)層次的探索。比如，有的研究者從硬件角度考慮，在底層通過磨損均衡機(jī)制來減少寫操作；在應(yīng)用層次，有研究者提出各種的內(nèi)存調(diào)度算法，將讀操作和寫操作進(jìn)行區(qū)分等等。本文將主要分析在應(yīng)用層次，總結(jié)現(xiàn)有的PCM數(shù)據(jù)結(jié)構(gòu)設(shè)計方法和思路。

二、PCM數(shù)據(jù)結(jié)構(gòu)設(shè)計

（一）B+樹索引

B+樹是B樹的變體，是一種多路索引樹。B+樹的特點就是每層結(jié)點數(shù)目非常多，層數(shù)很少，目的就是為了減少交互次數(shù)，當(dāng)查詢數(shù)據(jù)的時候，由于內(nèi)部結(jié)點和葉子結(jié)點的鍵是有序排列的，通過二分查詢可以高效率的讀取數(shù)據(jù)。一旦需要新插入一個結(jié)點的時候，首先要找到相關(guān)葉子結(jié)點，如果已滿，就需要進(jìn)行分裂操作。同樣刪除結(jié)點的時候也會帶來結(jié)點的拆分和合并操作。

在DRAM內(nèi)存系統(tǒng)中，B+樹得到了廣泛的應(yīng)用。由于B+樹結(jié)點記錄是有序的，可以直接使用二分查找，因此查詢的性能較好。但是，插入、刪除包含了過多的寫操作，不適合PCM環(huán)境，效率低下。因此需要對B+樹結(jié)構(gòu)進(jìn)行調(diào)整，以適應(yīng)新的內(nèi)存體系。

1.對葉子結(jié)點內(nèi)部排序

一些研究通過葉子結(jié)點亂序存儲來是減少排序帶來的寫操作，提高了插入和刪除結(jié)點性能，但是增加了查詢的讀操作。Chen等人提出無序方式有3種：全部結(jié)點無序，僅葉子結(jié)點無序和部分葉子結(jié)點無序（帶有位圖信息）。1）內(nèi)部結(jié)點無序排列會讓查找效率減低，而結(jié)點分裂需要對結(jié)點重新排序計算，增加了CPU計算開銷。2）部分節(jié)點無序，文獻(xiàn)[3]提出了基于PCM內(nèi)存的B+樹方案，做了部分優(yōu)化：采用了對葉子結(jié)點部分無序，并對葉子結(jié)點設(shè)置了合并因子，來判斷葉子結(jié)點的合并。3）僅葉子節(jié)點無序，文獻(xiàn)提出了NV-tree，適用于PCM/DRAM混合內(nèi)存。因為只有葉子結(jié)點信息需要持久化，所以將B+樹的所有葉子結(jié)點保存在PCM內(nèi)存，而將中間結(jié)點保存在DRAM內(nèi)存中的連續(xù)地址。為了降低葉子節(jié)點的排序開銷，葉子節(jié)點也是無序排列。

2.溢出結(jié)構(gòu)

由于葉子結(jié)點的插入和刪除操作，往往對B+樹的多個結(jié)點產(chǎn)生影響。例如，當(dāng)需要拆分葉子結(jié)點的時候，需要改寫3個結(jié)點，分別是原始的分裂結(jié)點、拆分到的結(jié)點、父結(jié)點。為了提高效率，很多研究采用溢出結(jié)點結(jié)構(gòu)。這種結(jié)構(gòu)通過將一部分葉子節(jié)點的合并和拆分操作，保留在溢出結(jié)點（稍后再對父結(jié)點進(jìn)行批量處理），如圖1所示，這樣不影響父結(jié)點的結(jié)構(gòu)，減少了寫操作的次數(shù)。文獻(xiàn)[3]葉子結(jié)點包含多個溢出結(jié)點，這樣只有當(dāng)葉子節(jié)點的溢出深度達(dá)到樹的溢出因子時，其后的結(jié)點分裂操作才會導(dǎo)致樹的重組，分裂時所有溢出節(jié)點的葉子節(jié)點獨立出來和一組鍵被一次性插入到父節(jié)點中，這樣提高了寫操作的效率。如果溢出鏈過長，也會對數(shù)據(jù)查詢（讀操作）帶來性能下降的影響。

3.數(shù)據(jù)一致性

wB+-Tree為每個數(shù)據(jù)項增加了一個位圖（bitmap），為每個結(jié)點增加了一個位圖數(shù)組，通過原子更新來保證數(shù)據(jù)的一致性。FP-Tree在NV-Tree基礎(chǔ)上，對數(shù)據(jù)項也是采用了設(shè)置位圖的方式保持插入、刪除數(shù)據(jù)的一致性。同時，為了提高查詢性能，它還對葉子結(jié)點的每個數(shù)據(jù)項目都保存了一個哈希值，用哈希索引加快查詢過程。

圖1 帶溢出結(jié)點的B+樹

由于CPU和PCM之間的緩存以緩存行（cache line）為單位進(jìn)行讀寫,而故障原子寫單元為8B而非64B的緩存行大小，因此需要設(shè)計更細(xì)的訪問粒度來達(dá)到性能提升和減少一致性開銷。除了PCM中的B+樹外，也有學(xué)者研究了其他類型的樹狀結(jié)構(gòu)，如基數(shù)樹（radixtree）。

(二）Hash 索引改進(jìn)

傳統(tǒng)哈希索引并不適用于PCM，主要原因可以歸納為以下3個：

1.哈希索引一旦在遇到哈希沖突的時候，通常采用4種方法來處理：鏈?zhǔn)焦！⒕€性探測、二選哈希和布谷哈希。無論哪一種，都會帶來較多的寫操作。

2.PCM的非易失性沒有充分使用

由于在DRAM存儲上,為了防止斷電故障，保持?jǐn)?shù)據(jù)的一致性，需要使用日志來保證系統(tǒng)的可恢復(fù)。數(shù)據(jù)在更新前先在日志中保存，然后再寫入到磁盤，性能開銷很大。

3.哈希擴(kuò)容問題

哈希表的容量是有限的，當(dāng)不能容納新的元素的時候就必須要擴(kuò)容。擴(kuò)容的經(jīng)典操作是新開辟一塊空間，然后將原來的哈希元素移動到新的哈希表中，會帶來很多的寫操作。

自布谷哈希以來，很多研究人員使用兩個hash函數(shù)，構(gòu)造出備選位置，來降低哈希沖突。文獻(xiàn)首先提出了索引結(jié)構(gòu)在PCM環(huán)境中面臨的問題，提出了PFHT算法，是布谷哈希的改進(jìn)。每次插入操作只允許一次替換。另外，將多個哈希元素放到一個地方，提升了效率。使用Stash輔助存儲所有插入失敗的哈希元素。

文獻(xiàn)提出了的path hashing方法，主要是通過分層處理。path hashing在邏輯上構(gòu)建了一個二叉樹結(jié)構(gòu)，葉子結(jié)點用來存儲原始的映射地址，而中間結(jié)點用來保存發(fā)生沖突的備選位置。使用兩個獨立的哈希函數(shù)，找到兩條備選路徑，只要上面有空位置，就可以插入新的結(jié)點。同樣，刪除請求只需要探測葉結(jié)點及其備用位置，而不會導(dǎo)致額外的寫入。此算法很大程度上減少了在PCM寫入的次數(shù)，但查詢性能還有改進(jìn)的空間。

綜上兩段所述，文獻(xiàn)的研究要點在于減少寫操作，對查找和插入刪除的結(jié)構(gòu)上做了優(yōu)化，但是對于問題2和3的解決方案都還有改進(jìn)的空間，特別是問題3哈希擴(kuò)容問題方面的表現(xiàn)不是很理想。

文獻(xiàn)提出了一種基于NVM的level hashing，這種方法結(jié)合了PFHT和path hashing的優(yōu)點，使用了基于共享的兩層結(jié)構(gòu)。其中，直接訪問的是第1層的哈希元素，第2層的哈希單元用于處理哈希沖突。Level hashing的一大特點是支持自動哈希擴(kuò)容。在調(diào)整大小時候，臨時變成一個三級結(jié)構(gòu)，如圖2所示，將底層的哈希條目重新分布到上面兩層，減少了移動和替換結(jié)點的寫操作。

圖2 Level Hasing擴(kuò)容過程

Level hashing使用無日志技術(shù)來保證數(shù)據(jù)一致性。主要實現(xiàn)方法是數(shù)據(jù)的原子修改（主要是8字節(jié)的操作），增加和slots（插槽）對應(yīng)的token（令牌），同時制定無日志刪除、查找、擴(kuò)容、更新的規(guī)則，修改數(shù)據(jù)時同步原子寫入修改令牌。

文獻(xiàn)[1]提出Group Hashing，即所謂的組哈希策略，主要思路是將散列表分成組，通過組內(nèi)共享以及組內(nèi)再次哈希的方式，來提升索引的性能，達(dá)到較好的效果，說明哈希索引結(jié)構(gòu)的優(yōu)化還有空間。

（三）PCM數(shù)據(jù)結(jié)構(gòu)研究展望

目前并沒有成熟的PCM索引數(shù)據(jù)結(jié)構(gòu)的應(yīng)用，上述所有的索引數(shù)據(jù)結(jié)構(gòu)的研究都還處于起步初級階段。隨著PCM內(nèi)存技術(shù)的日益成熟，普及的腳步加快，索引數(shù)據(jù)結(jié)構(gòu)受重視的程度也會逐漸加強(qiáng)，未來的研究方向主要集中在以下幾個方面。

1.混合索引結(jié)構(gòu)

目前，針對PCM環(huán)境的索引數(shù)據(jù)結(jié)構(gòu)主要是B+樹和hash表兩大類。這兩種類別適用于范圍查詢和單點查詢。為了同時支持以上兩種操作，混合索引的設(shè)計也是一個有應(yīng)用價值的研究領(lǐng)域。

已經(jīng)有學(xué)者提出HiKV混合索引結(jié)構(gòu)，在PCM中應(yīng)用Hash索引，在DRAM中采用B+索引，但是缺少在相應(yīng)體系結(jié)構(gòu)中的索引結(jié)構(gòu)的優(yōu)化。未來，也有可能將紅黑樹、跳表（skiplist）等其他結(jié)構(gòu)引入，構(gòu)造混合索引以適應(yīng)不同的應(yīng)用場景。

目前，通過對索引在PCM和DRAM中的差異研究導(dǎo)出如何優(yōu)化混合索引，以及在混合內(nèi)存體系中如何配置，還沒有成熟的方案，有待進(jìn)一步的研究。

2.并發(fā)索引結(jié)構(gòu)

目前的索引結(jié)構(gòu)研究大多是基于單線程進(jìn)行，沒有涉及到并發(fā)的數(shù)據(jù)結(jié)構(gòu)。在多核多進(jìn)程環(huán)境下的索引的并發(fā)控制，成了一個新的研究方向。只有對優(yōu)化目前的單核數(shù)據(jù)結(jié)構(gòu)的研究也達(dá)到一定水平后再深入研究多個線程中的如何優(yōu)化調(diào)度，才能真正提高PCM數(shù)據(jù)應(yīng)用的性能。目前，這種高階研究成果還很稀缺。