內(nèi)存數(shù)據(jù)索引：以處理器為核心的性能優(yōu)化技術(shù)

董紹嬋, 周敏奇, 張 蓉, 周傲英

(華東師范大學(xué) 軟件學(xué)院;數(shù)據(jù)科學(xué)與工程研究院，上海 200062)

?

內(nèi)存數(shù)據(jù)索引：以處理器為核心的性能優(yōu)化技術(shù)

董紹嬋, 周敏奇, 張 蓉, 周傲英

(華東師范大學(xué) 軟件學(xué)院;數(shù)據(jù)科學(xué)與工程研究院，上海 200062)

隨著單機內(nèi)存容量的持續(xù)上升，內(nèi)存數(shù)據(jù)庫技術(shù)逐漸取代傳統(tǒng)磁盤數(shù)據(jù)庫為數(shù)據(jù)管理提供更快速的支持.本文分析了設(shè)計內(nèi)存索引結(jié)構(gòu)所需要考慮的基本要素；對目前的內(nèi)存索引結(jié)構(gòu)進行了分類總結(jié)，并分析各結(jié)構(gòu)的優(yōu)缺點；針對當(dāng)前應(yīng)用發(fā)展趨勢，指出內(nèi)存索引未來發(fā)展的機遇與挑戰(zhàn)；最后介紹了我們正在研發(fā)的分布式集群感知內(nèi)存數(shù)據(jù)庫(CLAIMS)中的內(nèi)存索引結(jié)構(gòu).

內(nèi)存索引; cache利用率; 分布式內(nèi)存數(shù)據(jù)庫; 索引壓縮

0 引 言

在20世紀(jì)70—80年代，由于硬盤技術(shù)的不成熟，導(dǎo)致計算機磁盤空間增長緩慢，數(shù)據(jù)訪問性能低下.當(dāng)時數(shù)據(jù)庫系統(tǒng)所處理的數(shù)據(jù)規(guī)模并不大，所以有人曾設(shè)想過在數(shù)據(jù)庫處理過程中，將磁盤上的數(shù)據(jù)全部常駐在內(nèi)存[1]，以提高數(shù)據(jù)訪問和處理的速度.1980年，IBM提出“薄膜”磁頭技術(shù)，這為進一步減小硬盤體積、增大容量提高讀寫速度提供了可能；1980年代末期發(fā)明了磁阻磁頭，使得盤片的存儲密度較以往提高了數(shù)十倍；隨后推出了首個容量超過1 GB的硬盤“IBM 3380直連存儲設(shè)備(DASD)”(每個容量為2.5 GB)[2].從此，磁盤容量的增長速率遠遠超過了內(nèi)存容量的增長，“內(nèi)存數(shù)據(jù)庫”的想法看似已無可能.對內(nèi)存數(shù)據(jù)庫系統(tǒng)的研究也止步不前；研究人員或者轉(zhuǎn)向?qū)崟r系統(tǒng)領(lǐng)域，或者致力于對磁盤數(shù)據(jù)庫性能的改進.

在傳統(tǒng)的磁盤數(shù)據(jù)庫中，數(shù)據(jù)從磁盤加載到內(nèi)存的過程成為提高整個數(shù)據(jù)庫系統(tǒng)性能的瓶頸所在.為了減少數(shù)據(jù)訪問時的I/O開銷，各種基于磁盤的數(shù)據(jù)索引結(jié)構(gòu)應(yīng)運而生；其中，由于對數(shù)據(jù)的增刪改有非常好的性能支持，本身結(jié)構(gòu)可以進行范圍查詢等優(yōu)勢，B+樹[3]索引得到了廣泛的應(yīng)用.

近十幾年來，隨著RAM價格的不斷下降，計算機內(nèi)存的容量飛速上升.在當(dāng)今的主流服務(wù)器中，TB級的內(nèi)存容量已隨處可見.這使得完全可以將所有數(shù)據(jù)常駐內(nèi)存，以實現(xiàn)快速的數(shù)據(jù)訪問和更新，基于內(nèi)存的數(shù)據(jù)庫系統(tǒng)再次得到人們的重視.

在內(nèi)存數(shù)據(jù)庫系統(tǒng)中，所有的數(shù)據(jù)操作任務(wù)都可直接在內(nèi)存中得到響應(yīng)；因此，困擾傳統(tǒng)數(shù)據(jù)庫的I/O瓶頸不復(fù)存在.類似于內(nèi)存-磁盤間的性能差異，CPU與內(nèi)存對數(shù)據(jù)的不同處理能力導(dǎo)致內(nèi)存數(shù)據(jù)庫的瓶頸轉(zhuǎn)變?yōu)镃PU-memory代價.由于處理器廠商與內(nèi)存廠商相互分離的產(chǎn)業(yè)格局，導(dǎo)致內(nèi)存技術(shù)與處理器技術(shù)發(fā)展的不同步.圖1給出了20世紀(jì)最后20年間CPU和DRAM性能增長的趨勢；從圖中可明顯看出，在這段時間內(nèi)，處理器的性能每年大約有60%的提升，而內(nèi)存性能的提升速度則每年只有10%左右.這種不均衡的發(fā)展使得當(dāng)前內(nèi)存的存取速度嚴(yán)重滯后于處理器的計算速度，內(nèi)存訪問瓶頸導(dǎo)致高性能處理器難以發(fā)揮應(yīng)有的效率，并且直接制約了內(nèi)存數(shù)據(jù)庫系統(tǒng)操作性能的提升.事實上，早在1994年就有研究人員分析和預(yù)測了這一問題，并將這種嚴(yán)重阻礙處理器性能發(fā)揮的內(nèi)存瓶頸命名為"內(nèi)存墻"(Memory Wall)[4].在很長一段時間內(nèi)，對內(nèi)存索引的研究都圍繞著如何減弱“內(nèi)存墻”問題對數(shù)據(jù)獲取的延遲進行.一系列“緩存敏感性”[5]索引的提出(例如CSB-Tree[6]、CST-Tree[7]等)使得該問題得到了緩解.

圖1 CPU與DRAM性能增長對比[6]

在現(xiàn)今的CPU-Cache-Memory處理架構(gòu)下，已有實驗結(jié)果表明[8]：數(shù)據(jù)庫執(zhí)行時間的一半用于等待內(nèi)存，而且90%的等待時間是由二級數(shù)據(jù)cache失效和一級指令cache失效造成的——這就意味著數(shù)據(jù)放置即數(shù)據(jù)模型對二級數(shù)據(jù)cache、一級指令cache有重要的影響.因此,如何有效地利用cache的特征設(shè)計高效算法，成為內(nèi)存數(shù)據(jù)庫系統(tǒng)中亟待解決的一個重要問題.類比于傳統(tǒng)數(shù)據(jù)庫系統(tǒng)中對I/O瓶頸的索引處理方式，在內(nèi)存數(shù)據(jù)庫中，同樣需要建立針對內(nèi)存數(shù)據(jù)的索引結(jié)構(gòu)，以避免對其進行全部掃描或大量隨機讀取，從而加快數(shù)據(jù)訪問與處理的速度，盡可能減弱“內(nèi)存墻”問題對數(shù)據(jù)庫處理性能的影響.

除此之外，新的硬件架構(gòu)也對內(nèi)存索引的結(jié)構(gòu)設(shè)計提出了各種要求.由于多核技術(shù)的發(fā)展及內(nèi)存容量的增大，單臺計算機中的內(nèi)存被分配給了不同的處理器，從而催生了非一致性內(nèi)存訪問(Non-Uniform Memory Access，NUMA)[9]系統(tǒng)的出現(xiàn).由于處理器訪問直接掛載內(nèi)存與遠端內(nèi)存的時間消耗存在差異，針對內(nèi)存中數(shù)據(jù)的索引結(jié)構(gòu)可增添新的標(biāo)識信息以使得數(shù)據(jù)盡量被其所在內(nèi)存直接掛載的處理器所處理，從而加快數(shù)據(jù)的訪問處理時間.另外，隨著處理器與內(nèi)存間緩存層數(shù)的增加，各處理器對一級、二級緩存的私有化導(dǎo)致數(shù)據(jù)訪問過程中的相干性沖突增加，在多線程處理環(huán)境下，當(dāng)多個處理器同時對某一特定的索引結(jié)構(gòu)進行遍歷搜索時，如何有效的避免對特定結(jié)點訪問所造成的相干性沖突也是提升內(nèi)存數(shù)據(jù)訪問效率的一個有效手段.

除了在單機環(huán)境下要解決的“內(nèi)存墻”問題之外，大數(shù)據(jù)時代的到來，它所具有的“3V”(即海量(Valume)、高速(Velocity)、多樣(Variety)[10])特性，對數(shù)據(jù)庫的分析和處理能力提出了新的挑戰(zhàn).傳統(tǒng)的單機內(nèi)存數(shù)據(jù)庫系統(tǒng)并不能夠很好地滿足要求，于是分布式數(shù)據(jù)管理系統(tǒng)受到重視并被廣泛研究.基于Key-Value Store的分布式內(nèi)存數(shù)據(jù)管理系統(tǒng)(例如Spark[11]、RAMCloud[12]等)已經(jīng)取得較好的應(yīng)用.分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)的研究也如火如荼.SAP的HANA[13]已經(jīng)有相對穩(wěn)定高效的分布式版本；MinSQL[14]作為一個實驗室產(chǎn)物，是用JAVA搭建的，一個較為完善的分布式內(nèi)存數(shù)據(jù)庫系統(tǒng).在分布式環(huán)境下，源數(shù)據(jù)的存儲策略直接影響數(shù)據(jù)在集群中的分布；而之前的基于單機內(nèi)存的索引結(jié)構(gòu)，也必然要針對分布式的數(shù)據(jù)存儲作出新的調(diào)整.整個數(shù)據(jù)在集群中數(shù)據(jù)結(jié)點間的分布式存儲策略與在每個數(shù)據(jù)結(jié)點內(nèi)部的部分?jǐn)?shù)據(jù)的局部索引的結(jié)合，將導(dǎo)致分布式環(huán)境下索引的多層架構(gòu).目前，針對內(nèi)存數(shù)據(jù)的分布式索引結(jié)構(gòu)的研究并不是很成熟，仍有很多的工作值得去做.

圖2列出了內(nèi)存索引技術(shù)近30年來的開展.從20世紀(jì)80年代開始，內(nèi)存索引結(jié)構(gòu)被首次提出并開始針對其獨立于傳統(tǒng)的磁盤索引結(jié)構(gòu)的特征進行研究改進.隨著計算機硬件的不斷變化，內(nèi)存索引結(jié)構(gòu)也產(chǎn)生了相對應(yīng)的改變.從傳統(tǒng)的基于B樹類型的索引到Trie結(jié)構(gòu)的引進，從對磁盤hash結(jié)構(gòu)的直接應(yīng)用到針對cache及TLB的特性進行的敏感性改進，直到后來針對不同的索引結(jié)構(gòu)特性進行復(fù)合利用，逐步提升內(nèi)存索引對數(shù)據(jù)掃描的性能影響.

在過去的30多年中，已有很多學(xué)者致力于研究如何對內(nèi)存數(shù)據(jù)建立高效的索引結(jié)構(gòu)，但是這部分的研究工作主要針對集中式環(huán)境，對分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)并沒有作相關(guān)的索引工作探討.本文嘗試全面回顧內(nèi)存數(shù)據(jù)庫索引工作在近30年來的研究進展與已有成果，并展望其未來可能的發(fā)展方向.此外，華東師范大學(xué)數(shù)據(jù)科學(xué)與工程院在分布式內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)存儲及索引建立方面也做了一些探索，本文也會給出簡要的介紹.

圖2 內(nèi)存數(shù)據(jù)庫系統(tǒng)索引發(fā)展概覽

本文的后續(xù)內(nèi)容組織如下：第1節(jié)介紹內(nèi)存索引結(jié)構(gòu)需要考慮的基本要素；第2節(jié)和第3節(jié)分別介紹單機和分布式環(huán)境下內(nèi)存數(shù)據(jù)庫索引結(jié)構(gòu)的研究進展；第4節(jié)總結(jié)當(dāng)今數(shù)據(jù)及應(yīng)用的發(fā)展趨勢并展望未來內(nèi)存大數(shù)據(jù)索引的發(fā)展方向，同時簡介華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院在CLAIMS系統(tǒng)中的分布式內(nèi)存索引研究；最后，第5節(jié)總結(jié)全文.

1 內(nèi)存索引結(jié)構(gòu)要考慮的基本要素

已有的研究成果表明，在傳統(tǒng)的磁盤行數(shù)據(jù)庫系統(tǒng)中，最大的性能瓶頸在于對大量磁盤數(shù)據(jù)的訪問和獲取.因此，產(chǎn)生了各種磁盤數(shù)據(jù)索引方式，用以避免對原始數(shù)據(jù)的全盤掃描，精準(zhǔn)定位數(shù)據(jù)；然而，隨著內(nèi)存容量的上升及列存儲方式的出現(xiàn)，基于內(nèi)存的數(shù)據(jù)庫系統(tǒng)可以將查詢所需的原始數(shù)據(jù)全部緩存在內(nèi)存中以便在查詢到來時可以快速地獲取到對應(yīng)于查詢的數(shù)據(jù).

由圖3給出的計算機中各級存儲介質(zhì)數(shù)據(jù)訪問效率的對比可看出，當(dāng)傳統(tǒng)的磁盤瓶頸消失之后，內(nèi)存訪問延遲將會變成制約內(nèi)存數(shù)據(jù)庫系統(tǒng)查詢處理性能提升的新瓶頸，如何加速數(shù)據(jù)從內(nèi)存獲取到CPU處理的過程已經(jīng)成為內(nèi)存數(shù)據(jù)庫性能提升的一個重要研究方向.總結(jié)上述情況并結(jié)合近年來出現(xiàn)的新的硬件架構(gòu)形式及分布式環(huán)境的發(fā)展，以下給出在設(shè)計內(nèi)存數(shù)據(jù)索引時需要重點考慮的基本要素.

圖3 各級存儲介質(zhì)的訪問延遲說明

1.1 提升cache利用率

類似于傳統(tǒng)磁盤數(shù)據(jù)庫中內(nèi)存buffer與磁盤的關(guān)系，在內(nèi)存數(shù)據(jù)庫中數(shù)據(jù)cache可看作是內(nèi)存中原始數(shù)據(jù)的更高一層存儲buffer.cache與內(nèi)存之間數(shù)據(jù)的交換以cache line為單位；每次不論實際所需的數(shù)據(jù)占用多少空間，一旦在cache中不能找到所需數(shù)據(jù)，訪問內(nèi)存獲取的數(shù)據(jù)規(guī)模必定填充滿一個完整的cache line.因此，盡量提高cache中的空間利用率，使得每次加載到cache中的索引數(shù)據(jù)能夠全部有效地用于查詢處理中對結(jié)果集的prune或直接指示，是設(shè)計內(nèi)存索引結(jié)構(gòu)的一個主要考慮因素.

以傳統(tǒng)的B樹[15]類索引為例，雖然該類索引在磁盤數(shù)據(jù)庫中得到了非常廣泛的應(yīng)用并且也被證明可以取得很好的性能提升，但是顯然這類結(jié)構(gòu)并不能直接用于對內(nèi)存數(shù)據(jù)進行索引.Ross提出了“緩存敏感(cache conscious)”的概念，形式化地說明了對cache line利用率的優(yōu)化問題，并在文獻[5]中以傳統(tǒng)B樹結(jié)構(gòu)為基礎(chǔ)，在OLAP(在線分析系統(tǒng)，On-Line Analysis Processing)環(huán)境下提升cache利用率，通過對其進行緩存敏感性改進使得其變體結(jié)構(gòu)最終能被應(yīng)用到內(nèi)存數(shù)據(jù)索引結(jié)構(gòu)中.

1.2 減少cache失效及TLB失效

通過已有的實驗已經(jīng)知道，數(shù)據(jù)庫執(zhí)行時間的一半是CPU在等待內(nèi)存，而90%的等待時間是由二級數(shù)據(jù)cache失效和一級指令cache失效造成的.因此，減少二級數(shù)據(jù)cache失效的發(fā)生概率顯得尤為重要.對于樹型索引，如果整個結(jié)構(gòu)沒有被加載到cache，那么每次層間偏移都對應(yīng)一次數(shù)據(jù)cache失效.因此如何提高其結(jié)點的扇出分支數(shù)目，降低樹高，減少索引搜索過程中cache失效發(fā)生的概率是內(nèi)存索引要考慮的另一個重要因素.

對hash類索引而言，數(shù)據(jù)的定位只需一次hash值的計算，理想情況下搜索代價為O(1).但是由于TLB空間局限性，對于大規(guī)模分散hash而言，絕大多數(shù)數(shù)據(jù)桶的物理地址都不在TLB中，這使得在數(shù)據(jù)定位過程中TLB失效頻發(fā)，嚴(yán)重影響索引效率.針對這種情況，如何組織hash的層次以減少在尋址過程中出現(xiàn)的TLB失效問題是設(shè)計內(nèi)存hash類索引要考慮的一個重要方面.其中，將Radix[16]技術(shù)引入索引結(jié)構(gòu)而提出的分層hash算法得到廣泛的認(rèn)可.

1.3 索引結(jié)構(gòu)壓縮

對于傳統(tǒng)的行存儲磁盤數(shù)據(jù)庫而言，表的所有屬性以記錄為單位按行存儲，在沒有索引的情況下對任一列的查詢都將引發(fā)整個數(shù)據(jù)表的全部掃描，這極大地增加了系統(tǒng)的I/O開銷，不利于查詢性能的提升.傳統(tǒng)磁盤索引通過避免對數(shù)據(jù)的全部掃描來提高查詢性能，其壓縮比率以一列的索引空間對比整個完整表數(shù)據(jù)；因此，即使沒有任何壓縮技術(shù)，索引的壓縮率也非常高.

當(dāng)前，針對常駐內(nèi)存的大量列數(shù)據(jù)建立索引結(jié)構(gòu)，其壓縮性能就成為一個非常重要的考量因素：首先，新的列存儲數(shù)據(jù)組織形式使得原始表中的數(shù)據(jù)按屬性進行組織存儲，這樣一來在針對某列操作時可以有針對性的只掃描該列的原始數(shù)據(jù)，大大縮小了對原始數(shù)據(jù)掃描的范圍(相比行數(shù)據(jù)庫而言).因此，索引結(jié)構(gòu)的壓縮比率也由對比之前行存儲的整個數(shù)據(jù)表變成僅與所要建立索引結(jié)構(gòu)的列進行對比.這種情況下，由于索引中添加了許多指示數(shù)據(jù)位置的信息，原來未經(jīng)壓縮的稠密索引所占用的空間必然大于原始該列數(shù)據(jù)所占用空間；因此，對于索引結(jié)構(gòu)的精簡和壓縮在列存儲的環(huán)境下就必不可少.其次，由于源數(shù)據(jù)已全部在內(nèi)存中放置，其全部掃描相比磁盤而言本身已經(jīng)非常迅速，要使索引結(jié)構(gòu)發(fā)生效力，必定通過查詢索引結(jié)構(gòu)直接定位數(shù)據(jù)要快于有cache預(yù)取加速下的數(shù)據(jù)順序掃描.而如上一小節(jié)所說，不論是樹型結(jié)構(gòu)還是基于hash的索引結(jié)構(gòu)，其在訪問過程中都會不可避免的產(chǎn)生cache失效和TLB失效，類比于傳統(tǒng)磁盤數(shù)據(jù)庫的內(nèi)存維護，最好的處理策略是能夠讓針對磁盤的索引結(jié)構(gòu)直接維護在cache中，這樣對索引結(jié)構(gòu)的訪問不會產(chǎn)生任何cache失效問題，整個數(shù)據(jù)的訪問過程只會產(chǎn)生直接獲取數(shù)據(jù)一次cache失效.為了使整個索引結(jié)構(gòu)能夠在cache中維護，該結(jié)構(gòu)所占用的空間量必須足夠小，針對大規(guī)模數(shù)據(jù)集，索引的壓縮就顯得尤為重要.

1.4 新的硬件特性帶來的索引結(jié)構(gòu)改進

在傳統(tǒng)磁盤數(shù)據(jù)庫中，系統(tǒng)的性能瓶頸主要在磁盤I/O上，而單位時間內(nèi)系統(tǒng)能從磁盤上讀取的數(shù)據(jù)量與配置磁頭數(shù)目，磁盤轉(zhuǎn)速等物理因素直接相關(guān)，這導(dǎo)致只能通過改變物理架構(gòu)來提升I/O吞吐量.而在內(nèi)存中，隨著當(dāng)今計算機硬件的發(fā)展，多核、多線程的處理模式完全能夠支持處理性能的成倍提升.圖4給出了計算機存儲架構(gòu)示意圖，結(jié)合新的結(jié)構(gòu)特性及技術(shù)發(fā)展，為了充分利用硬件性能，內(nèi)存中的索引結(jié)構(gòu)應(yīng)充分考慮到以下幾個因素.

圖4 各級存儲層架構(gòu)示意圖

(1) 隨著cache層數(shù)的增加以及多核技術(shù)的使用，在多線程環(huán)境下，核與核間L3 cache對內(nèi)存中數(shù)據(jù)訪問產(chǎn)生的相干性沖突，以及核內(nèi)不同處理器間更高層cache對L3 cache中數(shù)據(jù)訪問的相干性沖突，都會導(dǎo)致訪問過程中處理器的等待，使得最終的總體性能下降；

(2) 由于內(nèi)存容量的上升以及多核技術(shù)的應(yīng)用，“非一致性內(nèi)存訪問”[9]結(jié)構(gòu)使得CPU訪問不同內(nèi)存中的數(shù)據(jù)所需要的時間不盡相同；如何設(shè)計索引算法，使得在數(shù)據(jù)搜索過程中CPU所遍歷的數(shù)據(jù)恰好在其直接掛載的內(nèi)存中，這也是提升性能的一個有效途徑；

(3) 同時單指令多數(shù)據(jù)流(Single Instruction Multiple Data，SIMD)[17]技術(shù)的合理利用也能夠使索引的搜索性能得到進一步的提升；傳統(tǒng)的單個key值比較指令可直接擴展到對整個數(shù)據(jù)結(jié)點的處理，從而節(jié)約key值在索引結(jié)點中比較過程的時間消耗，進一步加快索引訪問的速度.

1.5 分布式內(nèi)存集群特性

從圖2中對近30年來的索引結(jié)構(gòu)的初步總結(jié)可看出，內(nèi)存索引結(jié)構(gòu)的研究一直都孤立于內(nèi)存數(shù)據(jù)庫系統(tǒng)之外單獨存在；并且?guī)缀跛械乃饕Y(jié)構(gòu)所注重的只是在單機內(nèi)存中的性能優(yōu)化策略，對于現(xiàn)今應(yīng)用越來越廣泛的分布式集群系統(tǒng)并沒有太多的研究.

隨著數(shù)據(jù)庫所處理的數(shù)據(jù)規(guī)模的急劇增大，實時處理需求的不斷提升，對集中式環(huán)境下服務(wù)器結(jié)點的要求也日益提高.相較于配置極高的單臺服務(wù)器，基于分布式架構(gòu)的集群更易被接受.內(nèi)存數(shù)據(jù)處理系統(tǒng)發(fā)展的下一階段必然會向分布式環(huán)境拓展，目前已經(jīng)有許多較為成熟的分布式內(nèi)存系統(tǒng)：基于Key-Value存儲的Spark、RamCloud；基于Hadoop的存儲結(jié)構(gòu)拓展而來的Impala；以及分布式的內(nèi)存數(shù)據(jù)庫系統(tǒng)memSQL、HANA等等.相較于分布式內(nèi)存系統(tǒng)的蓬勃發(fā)展，在其上的索引技術(shù)并沒有隨之興起.而由于網(wǎng)絡(luò)間內(nèi)存訪問的額外開銷，分布式內(nèi)存索引技術(shù)的研究也對傳統(tǒng)的單機內(nèi)存索引結(jié)構(gòu)提出了新的要求：建立分布式索引必須結(jié)合考慮數(shù)據(jù)在分布式系統(tǒng)中的存儲策略；索引結(jié)構(gòu)與原始數(shù)據(jù)的一致性存儲與否對數(shù)據(jù)訪問時間的影響不可忽略.而在分布式環(huán)境下應(yīng)用廣泛的基于HASH的數(shù)據(jù)分布策略與傳統(tǒng)的比較性索引結(jié)構(gòu)的結(jié)合效率并不理想.因此，如何在分布式環(huán)境下建立高效的內(nèi)存索引結(jié)構(gòu)需要考慮的因素更加復(fù)雜.

2 現(xiàn)有的內(nèi)存索引結(jié)構(gòu)

回顧內(nèi)存索引結(jié)構(gòu)的發(fā)展，其每一次改進都與CPU-Cache-Memory架構(gòu)的發(fā)展變化密切相關(guān).由于源數(shù)據(jù)的內(nèi)存存放，使得處理器及memory的架構(gòu)對索引結(jié)構(gòu)的影響逐漸增大.從傳統(tǒng)的單核單處理器單線程架構(gòu)到SIMD指令集的出現(xiàn)，到多線程多處理器多核時代的到來，每次CPU-Cache-Memory架構(gòu)的改進都引起針對內(nèi)存索引結(jié)構(gòu)的改革.

2.1 基于樹型結(jié)構(gòu)的內(nèi)存索引

鑒于B-tree一族的索引結(jié)構(gòu)在傳統(tǒng)磁盤數(shù)據(jù)庫索引中取得良好的效果，目前大部分內(nèi)存索引結(jié)構(gòu)也是以B-Tree類的Key值比較樹為原型，再針對CPU-Cache-Memory架構(gòu)下的新特性進行性能優(yōu)化.

(1) “內(nèi)存索引”的首次提出——T-Tree

在20世紀(jì)90年代，B-Tree作為一種被廣泛接受的磁盤索引結(jié)構(gòu)被直接用于內(nèi)存索引；但是，由于當(dāng)時cache的容量較小，B-Tree的結(jié)點結(jié)構(gòu)中指針數(shù)據(jù)過多，導(dǎo)致整個結(jié)構(gòu)太過龐大；并且索引結(jié)構(gòu)對cache的利用率明顯不高，不能很好地滿足Cache-Memory架構(gòu)對索引的新要求.

針對B-Tree的不足，結(jié)合AVL樹[18]和B樹[15]的各自特性進行改進得到的T-Tree[19]被認(rèn)為是最早出現(xiàn)的針對內(nèi)存數(shù)據(jù)建立的索引結(jié)構(gòu).該結(jié)構(gòu)由威斯康星大學(xué)的Lehman和Carey共同提出，并在后來被應(yīng)用于MonetDB[20]中索引更新區(qū)的數(shù)據(jù)，取得了較好的查詢性能提升.但是，由于其平衡的調(diào)整仍然借鑒AVL樹的結(jié)點旋轉(zhuǎn)規(guī)則，導(dǎo)致其失衡后的再平衡過程非常繁瑣；并且插入的上溢出及刪除的下溢出算法過于復(fù)雜，也導(dǎo)致T-Tree更新操作的平均消耗過大.

(2) “cache敏感性”概念提出及索引結(jié)構(gòu)的改進

盡管T-Tree的改進探索并不是很成功，但T-Tree的提出使得人們認(rèn)識到，由于Cache-Memory架構(gòu)與Memory-Disk架構(gòu)之間的性能及容量等各方面的差異，所以內(nèi)存索引結(jié)構(gòu)并不能完全照搬磁盤索引結(jié)構(gòu).

當(dāng)數(shù)據(jù)從磁盤全部轉(zhuǎn)移到內(nèi)存中后，cache的結(jié)構(gòu)特性對內(nèi)存數(shù)據(jù)索引的建立影響重大，其涉及的最重要的一個問題是cache的敏感性.CPU及cache對數(shù)據(jù)處理和訪問速度的差異成為內(nèi)存數(shù)據(jù)庫的主要性能瓶頸.已有實驗結(jié)果表明，在內(nèi)存數(shù)據(jù)庫系統(tǒng)中，半數(shù)的CPU等待時間消耗在二級cache的數(shù)據(jù)失效和一級cache的指令失效處理上[8].所以，如何合理地利用cache特征設(shè)計cache敏感算法已經(jīng)成為內(nèi)存數(shù)據(jù)庫系統(tǒng)中要解決的一個重要問題.

針對內(nèi)存數(shù)據(jù)索引和cache的架構(gòu)特性，人們提出了“緩存敏感(Cache-Sensitive)技術(shù)”[5].研究表明，對傳統(tǒng)的磁盤索引進行緩存敏感改造得到的內(nèi)存索引結(jié)構(gòu)能夠較為顯著地提升內(nèi)存數(shù)據(jù)的查詢性能.“緩存敏感性”主要解決的問題是針對cache的容量較小、以cache Line為數(shù)據(jù)交換的最小單位以及cache 失效所帶來的巨大的時間消耗等特性；通過盡量提高cache Line的利用率來降低在索引搜索過程中Cache Miss發(fā)生的概率，從而提高查詢的性能.

針對Cache敏感性問題，Ross等人對傳統(tǒng)面向磁盤的B+-Tree類索引結(jié)構(gòu)作了一系列的改進，提出了新的緩存敏感的內(nèi)存索引結(jié)構(gòu)： 基于OLAP應(yīng)用的CSS-Tree[5]及添加OLTP(在線事務(wù)系統(tǒng)，On-Line Transaction Processing)的更新操作的CSB+-Tree[6].其中CSS-Tree與B+-Tree的索引結(jié)構(gòu)類似，利用索引結(jié)點的連續(xù)順序存放特性，容易得出任意索引結(jié)點的任意子結(jié)點所存放的位置，從而完全省略B+Tree中用于指示子結(jié)點位置的指針空間，最大化索引結(jié)點的扇出分支數(shù)目，達到提高cache利用率的最終目的.并對索引結(jié)點大小與cache line的對應(yīng)關(guān)系的改變導(dǎo)致的索引結(jié)構(gòu)遍歷過程中產(chǎn)生的cache失效次數(shù)給出了詳細(xì)的理論論證，從而確立了索引結(jié)點大小與cache line容量相等的最優(yōu)索引結(jié)點配置.

在當(dāng)時的硬件環(huán)境下，針對OLAP應(yīng)用，CSS-Tree已經(jīng)達到了接近最優(yōu)的查詢性能優(yōu)化；然而，為此付出的更新代價極大：由于該索引結(jié)構(gòu)中沒有任何指針數(shù)據(jù)的存在，所有的結(jié)點按順序連續(xù)存放，使得該索引結(jié)構(gòu)的更新變得非常困難；在OLAP應(yīng)用的定期批量更新操作中，索引結(jié)構(gòu)只能通過重新構(gòu)建的方式進行維護，并不具備實時插入更新的能力.為了解決OLTP系統(tǒng)中的實時增刪改操作，必須對CSS-Tree的結(jié)構(gòu)進行合理化的改進——適當(dāng)?shù)厝菰S位置標(biāo)示指針的存在.針對該應(yīng)用需求，結(jié)合傳統(tǒng)B+Tree在處理增刪改操作時的規(guī)范，CSB+-Tree在每個索引結(jié)點組(Node Group)中增加了一個位置指針，使得整個索引結(jié)構(gòu)只需以結(jié)點組為單位連續(xù)存放即可；增加了索引結(jié)構(gòu)的位置靈活性，并借鑒B+Tree的增刪調(diào)節(jié)算法加以改進，實現(xiàn)了實時的動態(tài)索引項增刪操作.改進后的CSB+Tree在提升OLTP應(yīng)用中的數(shù)據(jù)查找性能上展示了較大的優(yōu)勢.在文獻[6]中,除了提出針對基于內(nèi)存的OLTP應(yīng)用有較好性能提升的CSB+Tree索引結(jié)構(gòu)外，對其索引結(jié)點組的規(guī)模也進行了形式化的討論：通過Segmented CSB+Tree的結(jié)點塊劃分來調(diào)節(jié)整個索引結(jié)點組的空間占用大小及數(shù)量規(guī)模，從而調(diào)節(jié)索引項增刪造成結(jié)點或結(jié)點組分裂時的維護開銷.

在當(dāng)時的CPU-Cache-Memory架構(gòu)形式下，充分考慮cache敏感性問題所提出的CS-類索引無疑極大提升了內(nèi)存數(shù)據(jù)查找效率，最大化地發(fā)揮了內(nèi)存索引在數(shù)據(jù)檢索中的作用.到2007年，韓國的一組研究人員對T-Tree做了緩存敏感性改進，提出基于T-Tree的CST-Tree[7]，以改善數(shù)據(jù)所消耗的索引樹層數(shù)較大且沒有進行cache line對齊等問題；與此同時，合理避免了傳統(tǒng)T-Tree在查找過程中可能發(fā)生結(jié)點誤載入cache的情況；從而使經(jīng)過改進的CST-Tree在數(shù)據(jù)查詢的時間性能上大幅度優(yōu)于之前的CSB+Tree.

(3) 針對內(nèi)存索引的優(yōu)化技術(shù)

① SIMD指令技術(shù)

當(dāng)代計算機的CPU提供“單指令流多數(shù)據(jù)流”(SIMD)的指令集支持，以實現(xiàn)一條指令同時作用于多個操作數(shù)，從而加快數(shù)據(jù)處理的速度.文獻 [21]給出了將傳統(tǒng)數(shù)據(jù)庫操作進行SIMD推廣的實現(xiàn)，并說明SIMD指令集對索引結(jié)構(gòu)的支持給不同索引的構(gòu)建或遍歷帶來性能提升.

有了SIMD指令集在數(shù)據(jù)庫索引結(jié)構(gòu)中的應(yīng)用基礎(chǔ)，2009年Schlegel等人提出了K-Ary Search算法[22].該算法在傳統(tǒng)的二分查找的基礎(chǔ)上，對其進行SIMD拓展，使其每個比較指令針對k個操作數(shù)進行，將要查找的原始有序數(shù)據(jù)分為k+1個區(qū)間;對比于原來的折半查找，單條指令過濾掉的數(shù)據(jù)成倍增加，從而加快有序數(shù)據(jù)的查找效率.隨后，由Kim等人提出的FAST(Fast Architecture Sensitive Tree)[23]索引結(jié)構(gòu)正式將SIMD技術(shù)應(yīng)用于內(nèi)存索引中：該結(jié)構(gòu)以K-Ary Search為基礎(chǔ)，充分考慮cache層的架構(gòu)特性，平衡索引頁塊、cache line塊及SIMD指令塊三者之間的關(guān)系，通過page blocking-cache line blocking-SIMD blocking三層架構(gòu)的索引樹存儲方式，使得在兼顧、cache敏感性問題的同時將SIMD指令運用于內(nèi)存索引結(jié)構(gòu).

② 查詢緩存技術(shù)[24]

在建立內(nèi)存索引結(jié)構(gòu)的基本考慮因素中除了，盡量提升cache利用率和考慮cache敏感性之外，減少cache失效所帶來的額外時間損耗也是提升性能的有效方法之一.在對海量數(shù)據(jù)建立內(nèi)存索引時，并不能保證整個索引結(jié)構(gòu)在任意時刻都在cache中緩存；因此在對基于樹型結(jié)構(gòu)的索引進行搜索時，也需要盡量避免cache失效所帶來的性能損失.Kenneth A. Ross團隊以B-Tree和CSB+Tree為基礎(chǔ)，提出的針對批量查詢的緩存技術(shù)，在很大程度上減少了系統(tǒng)冷啟動或索引結(jié)構(gòu)被替換出cache時對其搜索產(chǎn)生的cache失效次數(shù).該算法基于已有的內(nèi)存索引結(jié)構(gòu)，在結(jié)點(或結(jié)點組)上新加用于緩存搜索鍵值的數(shù)組空間.當(dāng)大量的查詢來臨時，逐層進行索引結(jié)構(gòu)的查找將搜索鍵值存放于該層目標(biāo)索引結(jié)點(所在結(jié)點組)對應(yīng)的緩存數(shù)組中，只有當(dāng)用于緩存鍵值的數(shù)組存滿溢出時才會觸發(fā)索引結(jié)構(gòu)向下一層進一步查找；同樣的，只有葉子結(jié)點(組)對應(yīng)的緩存數(shù)組溢出時才會返回查詢結(jié)果.

當(dāng)批量查找操作到來時，假定數(shù)據(jù)索引結(jié)構(gòu)不在cache中緩存，該算法將原來單獨的索引結(jié)構(gòu)中針對每個鍵值查找的cache失效次數(shù)進行了有效合并，使得一組鍵值的查找只會產(chǎn)生一次cache失效，大大減少了cache失效帶來的時間消耗，從而提升數(shù)據(jù)搜索的效率.需要注意的是，該算法的原始結(jié)構(gòu)并不能保證批量查詢的返回結(jié)果順序與查詢到來順序一致，需要額外的保序算法；另外，該方案增大了索引結(jié)構(gòu)所占用的空間大小(用于增加鍵值緩存數(shù)組)，因此對鍵值緩存數(shù)組的選取需進行較為完善的空間代價分析.

2.2 基于字典(trie)結(jié)構(gòu)的內(nèi)存索引

文獻[25]首次形式化的給出了trie(也稱數(shù)字搜索樹digital search tree[16])結(jié)構(gòu)的概念——一種類似于字典的數(shù)據(jù)索引方式，直接通過對要查找的原始數(shù)據(jù)的每一位進行索引來組織整個索引結(jié)構(gòu)，常被用于對字符串?dāng)?shù)據(jù)建立索引.在2011年SIGMOD Programming Contest中，德累斯頓工業(yè)大學(xué)的Kissinger等人組成的團隊所提出的針對內(nèi)存數(shù)據(jù)的廣義前綴搜索樹(Generalized Prefix Search Tree GPS-Tree)[26,27]索引結(jié)構(gòu)，取得了很好的成績.該結(jié)構(gòu)以傳統(tǒng)trie-tree為基礎(chǔ)，用原始數(shù)據(jù)(限定為數(shù)值類型)對應(yīng)的二進制表示形式建立索引結(jié)構(gòu)，并提出bypass structure和dynamic，prefix-based expansion算法壓縮索引樹高度從而取得了較好的查詢性能.

文獻[16]提出的GPS-Tree索引結(jié)構(gòu)，在樹高壓縮上已經(jīng)臻于完美；然而當(dāng)索引數(shù)據(jù)長度較大并且值域空間分布較小時，其固定的結(jié)點結(jié)構(gòu)使得結(jié)點中索引值浪費的情況非常普遍；并且其特定的針對二進制數(shù)據(jù)進行索引的限制條件也極大縮小了該結(jié)構(gòu)能夠處理的數(shù)據(jù)類型種類.為了解決這些問題，Leis等人提出了adaptive radix tree(AR-Tree)[28].在AR-tree中針對GPS-tree的問題作了一系列的改進：(1)索引結(jié)點的大小并不固定，而是根據(jù)其子結(jié)點的數(shù)目動態(tài)變化，從而盡可能地減少結(jié)點載入cache時導(dǎo)致的利用率下降問題；(2)形式化地定義了對傳統(tǒng)trie-tree高度進行壓縮的兩種算法(path compression和lazy expansion)并將其應(yīng)用于AR-tree中；(3)給出了常用的數(shù)據(jù)類型及其復(fù)合形式與二進制串的對應(yīng)轉(zhuǎn)換關(guān)系，拓展了AR-tree可用于索引的數(shù)據(jù)類型范圍.經(jīng)過如上的算法改進，AR-tree在內(nèi)存索引的查找性能相較于GPS-tree取得了進一步的提升.

2.3 Hash及復(fù)合型結(jié)構(gòu)的內(nèi)存索引

(1) 基于hash結(jié)構(gòu)的內(nèi)存索引

傳統(tǒng)的Hash索引結(jié)構(gòu)也被廣泛的用于磁盤數(shù)據(jù)庫中，其索引結(jié)構(gòu)不需要額外的存儲空間，并且能夠在O(1)的時間復(fù)雜度下準(zhǔn)確定位到所查找的數(shù)據(jù).將磁盤數(shù)據(jù)庫中的數(shù)據(jù)查找時間代價優(yōu)化至最小.從chained bucket hash[26]的提出到后來extendible hash[29]、linear hash[30]、modified linear hash[19]的改進，只是對映射沖突的處理、桶分裂的策略進行了性能優(yōu)化，并沒有針對內(nèi)存索引的結(jié)構(gòu)特性進行任何算法改進，直至2007年，由Ross提出的基于現(xiàn)代處理器的Hash預(yù)取算法[31]才將SIMD指令集融入到hash算法中，從內(nèi)存索引的角度提升傳統(tǒng)hash算法的索引構(gòu)造過程中數(shù)據(jù)組織的效率.

回顧hash算法的發(fā)展史可看出，針對hash算法的內(nèi)存改進與傳統(tǒng)磁盤hash相比沒有明顯的區(qū)別，單獨的基于hash的內(nèi)存索引結(jié)構(gòu)在內(nèi)存數(shù)據(jù)庫系統(tǒng)中并不常見，大多被用作分布式環(huán)境下原始數(shù)據(jù)分布的一種平衡性策略.

(2) 復(fù)合型結(jié)構(gòu)的內(nèi)存索引

由于其對于字符串類型數(shù)據(jù)的完美索引方式，使得Trie索引結(jié)構(gòu)及其變型總能達到相對較優(yōu)的性能；但Trie的先天性結(jié)構(gòu)問題導(dǎo)致在內(nèi)存索引中對cache的利用率比較低下.因此，以Trie結(jié)構(gòu)為基礎(chǔ)，添加各種輔助結(jié)構(gòu)優(yōu)化其針對內(nèi)存數(shù)據(jù)的索引能力成為復(fù)合型內(nèi)存索引結(jié)構(gòu)的主要組成方式.

Trie與hash結(jié)構(gòu)的結(jié)合：眾所周知，trie結(jié)構(gòu)對字符串類型的數(shù)據(jù)有較好的索引效率，而hash可以根據(jù)數(shù)據(jù)的不同特征將原始數(shù)據(jù)劃分為不同的模塊.正如之前所說，由于Trie的基本結(jié)構(gòu)中結(jié)點大小固定，當(dāng)索引數(shù)據(jù)長度較大并且取值空間分布較小時，結(jié)點中索引項浪費情況明顯；而結(jié)合hash先對數(shù)據(jù)進行分組，使得同一組中的數(shù)據(jù)范圍相對縮小，可以有效的提升trie結(jié)構(gòu)中索引結(jié)點的有效利用率.文獻[32,33]中分別對trie和hash結(jié)構(gòu)進行了結(jié)合，相較于原始的結(jié)構(gòu)有效的提升了索引的查找效率.

Trie與比較樹類型索引結(jié)構(gòu)的結(jié)合：由于trie結(jié)構(gòu)本身的不保序性導(dǎo)致其無法應(yīng)對范圍查詢，而在現(xiàn)實應(yīng)用中絕大多數(shù)情況下會面臨范圍查詢的需求.因此借鑒比較樹類型索引的特性對trie進行改進，使其能夠支持范圍查詢也得到廣泛的研究：文獻[34,35]中給出了trie與B/T-Tree結(jié)合的算法；文獻[36]中給出了trie與CSB+Tree結(jié)合產(chǎn)生的索引結(jié)構(gòu)，在滿足范圍字符串查詢的基礎(chǔ)上綜合考量了緩存敏感性問題，對內(nèi)存索引更具針對性.

3 分布式內(nèi)存數(shù)據(jù)庫中索引的應(yīng)用

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)處理系統(tǒng)所要處理的數(shù)據(jù)規(guī)模日益增大.傳統(tǒng)的單機式系統(tǒng)已逐漸無法滿足應(yīng)用對處理性能的所提出的要求，內(nèi)存數(shù)據(jù)處理系統(tǒng)也逐漸向分布式方向發(fā)展.隨之而來的針對內(nèi)存數(shù)據(jù)建立的索引結(jié)構(gòu)必然要針對分布式數(shù)據(jù)存儲進行有效的調(diào)整，使其在分布式環(huán)境下仍然能夠高效進行數(shù)據(jù)查找過程中的過濾，快速精準(zhǔn)的定位數(shù)據(jù)位置.

目前，對分布式內(nèi)存數(shù)據(jù)庫的研究還剛剛開始，尚未有非常完善的分布式內(nèi)存數(shù)據(jù)庫系統(tǒng).memSQL[37]作為一個分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)，完全遵從傳統(tǒng)的ACID事務(wù)準(zhǔn)則；利用無鎖的數(shù)據(jù)結(jié)構(gòu)和即時編譯器(Just-In-Time Compiler，JIT Compiler)處理高負(fù)荷的工作流，使得數(shù)據(jù)處理性能得到很大的提升；然而，其對數(shù)據(jù)的獲取并沒有添加任何基于索引算法的加速，仍舊采取簡單的順序掃描策略.除此之外，以SAP公司開發(fā)的商業(yè)內(nèi)存數(shù)據(jù)庫系統(tǒng)HANA[13]為例，雖然有分布式版本，但是相較于其單機版本的性能優(yōu)化仍有一定的差距；并且SAP開發(fā)人員并沒有提供對HANA的主數(shù)據(jù)建立內(nèi)存索引的功能，只是在其用于處理增刪改等OLTP操作的deta內(nèi)存區(qū)默認(rèn)建立了CSB+Tree的索引結(jié)構(gòu)以便快速定位已被修改的數(shù)據(jù).而對整個的未被修改的原始數(shù)據(jù)的搜索，其認(rèn)為在內(nèi)存環(huán)境下的列存儲數(shù)據(jù)，順序掃描的速率已經(jīng)足夠迅速，可以滿足日常應(yīng)用對數(shù)據(jù)查詢的性能要求.

由于分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)的研究并不成熟，相應(yīng)的分布式內(nèi)存數(shù)據(jù)索引結(jié)構(gòu)的探索也并沒有系統(tǒng)的展開.如何結(jié)合當(dāng)前硬件的CPU-Cache-Memory架構(gòu)對已有的單機內(nèi)存索引結(jié)構(gòu)進行分布式拓展，使其能夠無縫的融入已有的分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)從而大幅度提升數(shù)據(jù)查找過程的性能，成為內(nèi)存索引研究領(lǐng)域的難點問題之一.

4 未來展望

當(dāng)今是網(wǎng)絡(luò)極具膨脹發(fā)展的時代，數(shù)據(jù)產(chǎn)生量日益增多，大規(guī)模數(shù)據(jù)的有效管理問題臻待解決，大數(shù)據(jù)的管理技術(shù)也已經(jīng)成為當(dāng)前和未來一段時間內(nèi)計算機領(lǐng)域的重要研究課題之一[41].

4.1 數(shù)據(jù)及應(yīng)用的發(fā)展趨勢

隨著云時代的來臨,大數(shù)據(jù)也吸引了越來越多的關(guān)注.2008年Nature上出現(xiàn)“大數(shù)據(jù)”?？痆42]，而時至今日大數(shù)據(jù)時代早已開啟.盡管傳統(tǒng)的基于磁盤的數(shù)據(jù)庫系統(tǒng)在處理傳統(tǒng)的應(yīng)用時表現(xiàn)出了優(yōu)異的性能，但在不同的時代所要處理的數(shù)據(jù)規(guī)模也大不相同.例如在Web 1.0時代，整個互聯(lián)網(wǎng)的數(shù)據(jù)總規(guī)模較小，數(shù)據(jù)管理較為簡單；而隨著Web 2.0、Web 3.0時代的到來，所有的互聯(lián)網(wǎng)用戶均可在互聯(lián)網(wǎng)上產(chǎn)生數(shù)據(jù)記錄.以社交媒體為例，F(xiàn)aceBook的日數(shù)據(jù)產(chǎn)生量已經(jīng)達到TB級.日益龐大的網(wǎng)絡(luò)數(shù)據(jù)規(guī)模對數(shù)據(jù)的有效管理提出了新的挑戰(zhàn)，目前大數(shù)據(jù)處理中最大的困難并非是如何存儲規(guī)模龐大的數(shù)據(jù)，而是如何從這些海量數(shù)據(jù)中高效檢索出所需要的數(shù)據(jù)，并對其進行處理.

隨著數(shù)據(jù)規(guī)模的日益增大，數(shù)據(jù)處理系統(tǒng)也逐步面臨更新改革.在最初的數(shù)據(jù)庫誕生之際，基于單機的簡單的磁盤數(shù)據(jù)庫管理系統(tǒng)能夠充分滿足當(dāng)時數(shù)據(jù)處理的需求；隨著時間的推移逐步出現(xiàn)了分布式數(shù)據(jù)庫系統(tǒng).當(dāng)今各個不同企業(yè)或組織的應(yīng)用不同，系統(tǒng)設(shè)計的目標(biāo)、所面向的負(fù)載也不盡相同，傳統(tǒng)的面向磁盤的數(shù)據(jù)庫系統(tǒng)所支持的數(shù)據(jù)分析處理功能受到前所未有的挑戰(zhàn)，類似于Hadoop[43]，HBase[44]，Cassandra[45]等完全顛覆數(shù)據(jù)庫的ACID事務(wù)準(zhǔn)則[46]而基于key-value的分布式存儲處理系統(tǒng)也得到廣泛的應(yīng)用，并在海量數(shù)據(jù)的并行處理中取得了非常好的性能提升.另一方面，隨著硬件技術(shù)的革新，內(nèi)存價格迅速下降導(dǎo)致單機特別是高性能服務(wù)器的內(nèi)存容量日趨增大，基于內(nèi)存的數(shù)據(jù)處理系統(tǒng)也應(yīng)運而生，Spark、Shark[47]等對Hadoop的內(nèi)存拓展系統(tǒng)也得到廣泛的應(yīng)用.同時，如何將傳統(tǒng)的磁盤數(shù)據(jù)庫進行內(nèi)存拓展也引起越來越多人的興趣.與傳統(tǒng)的磁盤數(shù)據(jù)庫相比，內(nèi)存數(shù)據(jù)庫并不是單純的增加了緩沖區(qū)的大小.當(dāng)傳統(tǒng)的磁盤I/O瓶頸消失后，CPU與內(nèi)存間的數(shù)據(jù)獲取時間差異也成為新的內(nèi)存數(shù)據(jù)庫中的系統(tǒng)瓶頸.于是，對內(nèi)存中數(shù)據(jù)快速有效的獲取問題成為分布式內(nèi)存數(shù)據(jù)庫領(lǐng)域中新的研究熱點.隨著內(nèi)存數(shù)據(jù)庫的發(fā)展和分布式數(shù)據(jù)管理技術(shù)的提高，針對分布式的內(nèi)存數(shù)據(jù)庫系統(tǒng)的研究也成為新的領(lǐng)域熱點問題.如何針對不同的數(shù)據(jù)類型、分布規(guī)律、查詢處理頻率等信息建立相對應(yīng)的高效的分布式內(nèi)存索引結(jié)構(gòu)引起許多業(yè)內(nèi)人士的討論研究.

嶄新的應(yīng)用需求是推動數(shù)據(jù)庫技術(shù)發(fā)展的源動力.企業(yè)中實際的應(yīng)用需求決定了數(shù)據(jù)庫系統(tǒng)發(fā)展及性能提升的研究方向.現(xiàn)今時代，數(shù)據(jù)量爆炸，對數(shù)據(jù)的實時性分析要求越來越高，例如證券交易所中對股票行情的實時展示，金融機構(gòu)所提供的人們信用卡的近期消費情況統(tǒng)計分析等，這些應(yīng)用導(dǎo)致企業(yè)對能夠處理大數(shù)據(jù)量的實時分析系統(tǒng)的需求日益緊迫.毫無疑問，新生的分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)在分布式數(shù)據(jù)處理效率上取得了極大的提升，并且依舊兼容傳統(tǒng)的SQL查詢方式，對上層的應(yīng)用接口并未進行任何改變使得其更容易被企業(yè)所接收.同時，在傳統(tǒng)數(shù)據(jù)庫中極大提升搜索速率的磁盤索引結(jié)構(gòu)也被借鑒到內(nèi)存數(shù)據(jù)庫中，針對內(nèi)存數(shù)據(jù)的有效索引既要考慮分布式集群內(nèi)存數(shù)據(jù)的分布情況，又要結(jié)合CPU-Cache-Memory的新型架構(gòu)，使得內(nèi)存數(shù)據(jù)索引的結(jié)構(gòu)與傳統(tǒng)的磁盤索引不盡相同，針對不同類型的應(yīng)用需求都可以考慮建立相對應(yīng)的查詢加速索引結(jié)構(gòu).

4.2 未來內(nèi)存索引研究的機遇與挑戰(zhàn)

索引的有效cache：Cache-Memory間的訪問延遲相較于Memory-Disk間更加微小(圖3)，如何利用有效的索引結(jié)構(gòu)在這更小的訪問延遲中加速數(shù)據(jù)的訪問效率，這是內(nèi)存索引所要考慮的重要問題之一.由于在數(shù)據(jù)訪問過程中cache失效所帶來的時間消耗很大，利用有效策略使得在訪問內(nèi)存索引結(jié)構(gòu)的過程中盡量避免cache失效成為提升整個數(shù)據(jù)訪問性能的關(guān)鍵技術(shù).隨著數(shù)據(jù)規(guī)模的增大，如何設(shè)計高效的索引壓縮算法，以盡可能減少索引所占用的空間，從而使得整個或者絕大部分的索引結(jié)構(gòu)能夠常駐在L3 cache中，在索引的訪問過程中消除cache失效所產(chǎn)生的性能損耗，這些是未來設(shè)計內(nèi)存索引結(jié)構(gòu)所要面對的重要問題.

硬件變化：由于cache結(jié)構(gòu)的特殊性所帶來的cache敏感性，使得當(dāng)今索引在設(shè)計的時候都要充分考慮所針對集群的具體架構(gòu)；并且為了使得索引的搜索效率達到最大化，類似于SIMD指令技術(shù)及NUMA架構(gòu)的訪問性能等都做了針對性的優(yōu)化，這使得索引結(jié)構(gòu)在不同配置集群間的可移植性受到限制，從而影響整個內(nèi)存數(shù)據(jù)庫系統(tǒng)的集群可移植性.

分布式索引拓展：從本文第2、3節(jié)可看出，雖然內(nèi)存索引的研究已經(jīng)歷經(jīng)了三十多年，但其研究領(lǐng)域依局限于單機的環(huán)境，對現(xiàn)今流行的分布式環(huán)境并沒有給出較好的拓展策略.而隨著大數(shù)據(jù)時代的到來，海量的數(shù)據(jù)規(guī)模對單機的處理器性能提出了非常高的要求，使得絕大多數(shù)企業(yè)都選擇了分布式的處理環(huán)境從而減輕對單機的性能限制.類似于Hadoop、Shark、Spark等基于Key-Value存儲方式的分布式數(shù)據(jù)處理系統(tǒng)得到廣泛的應(yīng)用.而內(nèi)存數(shù)據(jù)庫系統(tǒng)從原來的單機版本(傳統(tǒng)的MonetDB[20])向分布式版本拓展也變得尤為迫切.針對單機的內(nèi)存索引結(jié)構(gòu)勢必要進行分布式的改進，以便在分布式集群環(huán)境下繼續(xù)有效的提升數(shù)據(jù)查找過程中的效率.

海量數(shù)據(jù)的地址表示：在傳統(tǒng)的磁盤數(shù)據(jù)庫中，除非外力進行干預(yù)(如人工進行數(shù)據(jù)遷徙)否則原始數(shù)據(jù)表格在磁盤上的位置保持不變；因此，磁盤索引的葉子結(jié)點可以直接用數(shù)據(jù)所在磁盤的邏輯地址來指示數(shù)據(jù)位置.而在內(nèi)存數(shù)據(jù)庫系統(tǒng)中，不論內(nèi)存容量如何增大，系統(tǒng)運行過程中總是無法保證有足夠大的內(nèi)存空間可以使得所有的表數(shù)據(jù)都完全被載入.因此，內(nèi)存數(shù)據(jù)庫系統(tǒng)中也會存在數(shù)據(jù)在內(nèi)存與磁盤間的交換(swap).一旦內(nèi)存中原始數(shù)據(jù)被swap到磁盤，當(dāng)其重新被載入內(nèi)存時，操作系統(tǒng)所分配給它的內(nèi)存地址幾乎不可能與之前的地址完全一致；因此，在內(nèi)存索引結(jié)構(gòu)中，葉子結(jié)點索引數(shù)據(jù)時并不能直接使用其在內(nèi)存中的邏輯地址.通常情況下，對小規(guī)模的數(shù)據(jù)而言該問題的解決辦法為用數(shù)據(jù)相對于某些特定標(biāo)志位置的偏移來指示數(shù)據(jù)在內(nèi)存中的位置，這樣只要原始數(shù)據(jù)的排序保持不變，無論其是否因內(nèi)存不足被交換到磁盤過，只要重新被載入內(nèi)存，都可以根據(jù)其相對目標(biāo)位置的偏移準(zhǔn)確的進行定位.隨著數(shù)據(jù)規(guī)模的增大，使得存儲相對目標(biāo)偏移所需的空間隨之越來越大，索引結(jié)構(gòu)葉子結(jié)點的規(guī)模也急劇上升，非常不利于整個索引結(jié)構(gòu)在L3 cache中的常駐存儲，因此，當(dāng)數(shù)據(jù)規(guī)模龐大時，如何有效地表示數(shù)據(jù)所處的位置從而高效地定位數(shù)據(jù)也是未來內(nèi)存索引要考慮的一個重要因素.

4.3 分布式內(nèi)存索引探索@CLAIMS[48]

當(dāng)今時代數(shù)據(jù)規(guī)模急劇增長，對數(shù)據(jù)的實時處理需求日益提高，即使當(dāng)今單臺服務(wù)器結(jié)點的性能可以達到非常高的標(biāo)準(zhǔn)，不論是處理器數(shù)目還是內(nèi)存容量都相當(dāng)可觀，集中式的內(nèi)存數(shù)據(jù)庫系統(tǒng)仍然極大的限制了其數(shù)據(jù)處理的能力及規(guī)模.內(nèi)存數(shù)據(jù)庫的分布式拓展顯得尤為重要.而目前并沒有相對成熟的分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)及比較成熟的內(nèi)存索引結(jié)構(gòu).華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院在此類系統(tǒng)的研發(fā)上已經(jīng)開展了近兩年的工作，致力于設(shè)計與實現(xiàn)一個集群感知的基于內(nèi)存的分布式數(shù)據(jù)庫系統(tǒng)(Cluster-Aware In-Memory System， CLAIMS).該系統(tǒng)中也已經(jīng)設(shè)計了針對內(nèi)存數(shù)據(jù)的分布式索引結(jié)構(gòu)，該索引基于傳統(tǒng)的B-tree[15]，充分考慮cache的敏感性問題；并在此基礎(chǔ)上結(jié)合列存儲及分布式數(shù)據(jù)組織的特點，對該結(jié)構(gòu)作進一步的優(yōu)化：

(1) 考慮“cache敏感性”問題，對傳統(tǒng)的B-tree索引進行內(nèi)存改進：消除子結(jié)點指針、數(shù)據(jù)指針分塊存儲、結(jié)點cache line對齊，得到CSB-tree結(jié)構(gòu).

(2) 結(jié)合分布式hash和NUMA技術(shù)對數(shù)據(jù)進行以chunk為單位的分布式內(nèi)存bounding，并對每個chunk建立CSB-tree構(gòu)成分布式環(huán)境下的Clustered CSB-trees.

(3) 利用SIMD指令集對Clustered CSB-Trees查詢算法進行加速，以期達到更高的訪問效率.

(4) 根據(jù)索引數(shù)據(jù)的值域進行結(jié)點壓縮，進一步增大索引結(jié)點扇出，降低樹高減少層間偏移產(chǎn)生cache miss的次數(shù).

經(jīng)過一系列的優(yōu)化，我們所提出的clustered enhanced CSB-trees能夠高效地應(yīng)用于分布式內(nèi)存數(shù)據(jù)索引，并在CLAIMS中得到實驗驗證.

5 小 結(jié)

隨著內(nèi)存容量的大幅度增加及價格的急劇下降，使得單機的內(nèi)存配置快速提升.內(nèi)存數(shù)據(jù)庫相較于傳統(tǒng)數(shù)據(jù)庫的瓶頸的改變，導(dǎo)致之前在傳統(tǒng)磁盤數(shù)據(jù)庫中的所有性能優(yōu)化策略都要在內(nèi)存數(shù)據(jù)庫系統(tǒng)中重新考慮.本文對近30年來內(nèi)存索引結(jié)構(gòu)的技術(shù)發(fā)展，作了詳細(xì)的回顧，在此過程中也發(fā)現(xiàn)由于內(nèi)存索引的特殊性，所以其結(jié)構(gòu)的發(fā)展與計算機CPU-Cache-Memory架構(gòu)的發(fā)展有著密切的聯(lián)系.并且給出大數(shù)據(jù)時代到來對內(nèi)存結(jié)構(gòu)分布式拓展的挑戰(zhàn)，在分布式環(huán)境下，無論是內(nèi)存數(shù)據(jù)庫系統(tǒng)還是索引結(jié)構(gòu)都還有長足的發(fā)展空間.本文最后還簡單介紹了華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院在分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)及分布式內(nèi)存索引方面正在進行的探索性工作.

[1] AMMANN A C, HANRAHAN M B, KRISHNAMURTHY R. Design of a memory resident DBMS[C]//Proc IEEE COMPCOM Conf, 1985.

[2] 微硬盤磁頭彈性臂的研究[R/OL].http://www.docin.com/p-270914249.html

[3] JANNINK J. Implementing deletion in B+-trees[J]. SIGMOD Record, 1995, 24(1).

[4] WOLF W A, MCKEE S A. Hitting the memory wall: Implications of the obvious[C]//ACM SIGARCH, 1995.

[5] RAO J, ROSS K A. Cache conscious indexing for decision-support in main memory[C]//Proceedings of the 25th VLDB Conference, 1999.

[6] RAO J, ROSS K A. Making B+-trees cache conscious in main memory[C]//SIGMOD, 2000.

[7] LEE I, SHIM J, LEE S, et al. CST-Trees: Cache Sensitive T-Trees[C]//DASFAA 2007, LNCS 4443, 2007: 398-409.

[8] AILAMAKI A, et al. DBMSs on a modern processor: Where does time go. In Proceedings of the 25th VLDB Conference, 1999.

[9] WIKIPEDIA. Non-uniform memory access [EB/OL].[2014-08-31]. http://en.wikipedia.org/wiki/Non-uniform_memory_access.

[10] LANEY D. 3D data management: controlling data volume, velocity and variety[R]. Technical Report, Meta Group, 2001.

[11] Amplab spark-lightning-fast cluster computing: https://amplab.cs.berkeley.edu/projects/spark-lightning-fast-cluster-computing.

[12] RAMCloud[EB/OL]. https://ramcloud.stanford.edu/wiki/display/ramcloud/RAMCloud.

[13] Homepage for SAP HANA Database: http://www.saphana.com/welcome.

[14] SWART G. MinSQL: a simple componentized database for the classroom[C]//PPPJ, 2003:129-132.

[15] BAYER R, MCCREIGHT E M. Organization and maintenance of large ordered indices[J]. Acta Inf, 1972(1):173-189.

[16] KNUTH D E. The art of computer programming Volume I: fundamental algorithms[M], 3rd ed. Addison-Wesley, 1997.

[17] Single Instruction Multiple Data: http://en.wikipedia.org/wiki/SIMD

[18] AHO A, HOPCROFT J, ULLMAN J D. The design and analysis of computer algorithms, Addison-Wesley Publishing Company, 1974.

[19] LEHMAN T J, et al. A study of index structures for main memory database management systems[C]//Proceedings of the 12th VLDB Conference, 1986.

[20] Homepage for MonetDB[EB/OL]. http://www.monetdb.org/Home

[21] ZHOU J, ROSS K A. Implementing database operations using SIMD instructions[C]//SIGMOD, 2002.

[22] SCHLEGEL B, GEMULLA R, LEHNER W. k-Ary search on modern processors[C]//DaMoN, 2009.

[23] KIM C, CHUGANI J, SATISH N, et al. FAST: fast architecture sensitive tree search on modern CPUs and GPUs[C]//SIGMOD, 2010:339-350.

[24] ZHOU J, ROSS K A. Buffering accesses to memory-resident index structures[J].VLDB, 2003.

[25] FREDKIN E. Trie Memory[J]. Communications of the ACM, 1960, 3(9):490-499.

[26] BOEHM M, SCHLEGEL B, VOLK P B, et al. Efficient in-memory indexing with generalized prefix trees[J]. BTW, 2011:52-55.

[27] KISSINGER T, SCHLEGEL B, BOEHM M, et al. A high-throughput in-memory index, durable on flash-based SSD[J]. SIGMOD, 2012,41(3):40-50.

[28] LEIS V, KEMPER A, NEUMANN T. The adaptive radix tree: aRTful indexing for main-memory databases[J]. ICDE, 2013.

[29] FAGIN R, NIEVERGELT J, PIPPENGER N, et al. Extendible hashing—A fast access method for dynamic files[J]. ACM Trans Database Syst, 1979, 4(3):315-344.

[30] LARSON P. Linear hashing with separators-a dynamic hashing scheme achieving one-access retrieval[J]. ACM Trans Database Syst, 1988,13(3):366-388.

[31] ROSS K A. Efficient hash probes on modern processors. In ICDE, 2007.

[32] COFFMAN E G, EVE J. File structures using hashing functions[J]. Commun ACM, 1970, 13(7):427-433.

[33] ASKITIS N, SINHA R. HAT-Trie: a cache-conscious trie-based data structure for strings. In ACSC, 2007.

[34] BOHANNON P, MCILROY P, RASTOGI R. Main-memory index structures with fixed-size partial keys. In SIGMOD, 2001.

[35] LUAN H, DU X, WANG S. Prefetching J+-tree: a Cache-optimized main memory database index structure[J]. J Comput Sci Technol, 2009,24(4):687-707.

[36] BINNIG C, HILDENBRAND S, FARBER F. Dictionary-based order preserving string compression for main memory column stores[C]//SIGMOD, 2009.

[37] Homepage for memsql: http://www.memsql.com.

[38] AGUILERA M K, GOLAB W, SHAH M A. A practical scalable distributed b-tree[C]//VLDB, 2008.

[39] WU S, JIANG D, OOI B C, et al. Efficient b-tree based indexing for cloud data processing[C]//Proc VLDB Endow, 2010,3(1): 1207-1218.

[40] MOUZA C, LITWIN W. Sd-rtree: A scalable distributed rtree[C]//ICDE, 2007: 296-305.

[41] 宮學(xué)慶，金澈清，王曉玲，等. 數(shù)據(jù)密集型科學(xué)與工程：需求和挑戰(zhàn)[J]. 計算機學(xué)報，2012, 35(8): 1563-1578.

[42] Big Data Section in Nature: http://www.nature.com/news/specials/bigdata/index.html.

[43] WHITE T.Hadoop權(quán)威指南[M].周敏奇，王曉玲，金澈清，錢衛(wèi)寧譯.2版. 北京：清華出版社，2011.

[44] Apache HBASE[EB/OL]. http://hbase.apache.org.

[45] Apache Cassandra[EB/OL]. http://cassandra.apache.org.

[46] HAERDER T, REUTER A. Principles of transaction-oriented database recovery[C]//ACM Computing Srveys, 1983, 15(4): 287-317.

[47] XIN R S, ROSEN T, ZAHARIA M, et al. Shark: SQL and rich analytics at scale[C]//SIGMOD, 2013: 13-24.

[48] CLAIMS Homepage at Github[EB/OL]. https://github.com/scdong/Claims/wiki.

(責(zé)任編輯 王善平)

In-memory index: Performance enhancement techniques leveraging on processors

DONG Shao-chan, ZHOU Min-qi, ZHANG Rong, ZHOU Ao-ying

(InstituteforDataScienceandEngineering,SoftwareEngineeringInstitute,EastChinaNormalUniversity,Shanghai200062,China)

As main memory capacities grows larger and larger, the memory era has arrived and in-memory databases have taken the place of traditional disk-based databases to provide efficient data management. In this paper, we analyzed the fundamental elements in in-memory index designing: summarized and evaluated the existing index structures, pointing out the future opportunities and challenges based on the development trend of current applications. Finally, we introduced our on-going distributed in-memory index studies on the Cluster Aware In-Memory System (CLAIMS).

in-memory indexing; cache utility; distributed in-memory database; index compressing

1000-5641(2014)05-0192-15

2014-06

國家自然科學(xué)基金(61332006)

董紹嬋，女，碩士研究生，研究方向為內(nèi)存數(shù)據(jù)庫系統(tǒng).Email:scdong510@163.com

周敏奇，男，副教授，碩士生導(dǎo)師，研究方向為內(nèi)存數(shù)據(jù)庫系統(tǒng).Email:mqzhou@sei.ecnu.edu.cn.

TP392

A

10.3969/j.issn.1000-5641.2014.05.017