崔 瑩，劉 兵

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

隨著大數(shù)據(jù)技術(shù)應(yīng)用的推廣，計(jì)算機(jī)系統(tǒng)對內(nèi)存的容量要求越來越高，需要足夠的頁面緩存來保證程序能夠快速執(zhí)行。馮諾依曼結(jié)構(gòu)計(jì)算機(jī)的處理器從大容量存儲中獲取數(shù)據(jù)一般都會花費(fèi)許多時(shí)間,這已經(jīng)成為提升當(dāng)代計(jì)算機(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è)計(jì)適用于PCM的數(shù)據(jù)索引結(jié)構(gòu)這個(gè)課題。不同于一些傳統(tǒng)研究項(xiàng)目，在這個(gè)新興領(lǐng)域目前我國專家學(xué)者暫處于較領(lǐng)先的水平。

一、背景知識

（一）PCM存儲器簡介

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

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

PCM也有很明顯的缺點(diǎn)。首先這種存儲器較易磨損，讀寫次數(shù)有限一旦達(dá)到一定的次數(shù)，就無法對存儲在其中的數(shù)據(jù)進(jìn)行讀寫操作；其次PCM內(nèi)存寫速度緩慢讀寫速度不平衡，讀性能與DRAM相似（約1-5倍），但在寫運(yùn)算中，DRAM速度約是它的5-50倍。因此，如果用PCM全部取代DRAM，引入實(shí)際內(nèi)存系統(tǒng)時(shí)，可能會產(chǎn)生意想不到的性能下降和壽命縮短的現(xiàn)象，因此目前主要是將兩種技術(shù)組成混合架構(gòu)投入實(shí)際應(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)在查找單個(gè)值索引上有優(yōu)勢。比如：MYSQL的innodb引擎采用了B+樹索引結(jié)構(gòu)，而Memcache和redis采用了hash索引結(jié)構(gòu)。為了同時(shí)支持范圍查詢和單點(diǎn)查詢，也有學(xué)者提出了混合索引的設(shè)計(jì)。

以往的數(shù)據(jù)結(jié)構(gòu)都是為DRAM內(nèi)存設(shè)計(jì)的，提供對稱的讀寫速度，而PCM最明顯的一個(gè)特征就是讀寫速率的不平衡。這些索引結(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è)計(jì)方法和思路。

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

（一）B+樹索引

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

綜上兩段所述，文獻(xiàn)的研究要點(diǎ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)點(diǎn)，使用了基于共享的兩層結(jié)構(gòu)。其中，直接訪問的是第1層的哈希元素，第2層的哈希單元用于處理哈希沖突。Level hashing的一大特點(diǎn)是支持自動(dòng)哈希擴(kuò)容。在調(diào)整大小時(shí)候，臨時(shí)變成一個(gè)三級結(jié)構(gòu)，如圖2所示，將底層的哈希條目重新分布到上面兩層，減少了移動(dòng)和替換結(jié)點(diǎn)的寫操作。

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

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

文獻(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)，未來的研究方向主要集中在以下幾個(gè)方面。

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

目前，針對PCM環(huán)境的索引數(shù)據(jù)結(jié)構(gòu)主要是B+樹和hash表兩大類。這兩種類別適用于范圍查詢和單點(diǎn)查詢。為了同時(shí)支持以上兩種操作，混合索引的設(shè)計(jì)也是一個(gè)有應(yīng)用價(jià)值的研究領(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ā)控制，成了一個(gè)新的研究方向。只有對優(yōu)化目前的單核數(shù)據(jù)結(jié)構(gòu)的研究也達(dá)到一定水平后再深入研究多個(gè)線程中的如何優(yōu)化調(diào)度，才能真正提高PCM數(shù)據(jù)應(yīng)用的性能。目前，這種高階研究成果還很稀缺。