基于內(nèi)存的HBase二級(jí)索引設(shè)計(jì)

崔 晨，鄭林江，韓鳳萍，何牧君

(1.重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶400044; 2.重慶城市綜合交通樞紐開發(fā)投資有限公司，重慶401121)(*通信作者電子郵箱15123034669@163.com)

0 引言

物聯(lián)網(wǎng)和大數(shù)據(jù)的廣泛應(yīng)用，產(chǎn)生了海量的多類型實(shí)時(shí)數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)存儲(chǔ)與管理方法已難以適應(yīng)當(dāng)前大規(guī)模數(shù)據(jù)管理對(duì)效率的需求，因此非關(guān)系型數(shù)據(jù)庫(kù)(Not Only SQL，NoSQL)［1］得以迅速發(fā)展。HBase作為NoSQL數(shù)據(jù)庫(kù)的代表，已被廣泛應(yīng)用于各行各業(yè)的數(shù)據(jù)存儲(chǔ)與管理中。索引是數(shù)據(jù)庫(kù)中提高數(shù)據(jù)管理與查詢效率的關(guān)鍵技術(shù)，HBase在行鍵(Rowkey)上建立了類B+樹索引，可以高效地支持基于行鍵的快速數(shù)據(jù)查詢［2］，但對(duì)非行鍵的列沒有建立索引，故進(jìn)行非行鍵的列的查詢時(shí)，需要對(duì)全表進(jìn)行掃描，這樣的查詢效率十分低下，極大限制了HBase在復(fù)雜條件下的查詢性能。為解決這一問題，現(xiàn)有研究提出建立非行鍵的列與行鍵的索引，從而構(gòu)建起二級(jí)索引方案，方案在對(duì)非行鍵的列進(jìn)行查詢時(shí)，先通過二級(jí)索引獲取與其對(duì)應(yīng)的行鍵，再通過行鍵到HBase中進(jìn)行查找。

目前，國(guó)內(nèi)部分企業(yè)和個(gè)人基于第三方開源軟件進(jìn)行索引設(shè)計(jì)，使用搜索服務(wù)器Solr［3］來構(gòu)建HBase二級(jí)索引。Solr是一個(gè)基于Lucene［4］的企業(yè)級(jí)全文搜索服務(wù)器，用戶可以通過超文本傳輸協(xié)議(HyperText Transfer Protocol，HTTP)請(qǐng)求向Solr提交HBase中的數(shù)據(jù)，建立非行鍵的列與行鍵的映射，生成索引;也可以通過HTTP Get操作提出查找請(qǐng)求返回索引中的行鍵。華為基于協(xié)處理器(Coprocessors)進(jìn)行了HBase二級(jí)索引的實(shí)現(xiàn)，它利用HBase的原生代碼即可獲得索引，但這也帶來插入數(shù)據(jù)速度變慢、升級(jí)維護(hù)困難以及索引無法動(dòng)態(tài)修改等問題。葛微等［2］提出了名為HiBase的二級(jí)索引，它是一種基于分層式索引的設(shè)計(jì)方案，其將熱點(diǎn)索引進(jìn)行緩存，并建立高效的緩存替換策略來提高二級(jí)索引的查詢速度。Zou等［5］提出了互補(bǔ)聚簇式索引(Complemental Clustering Index，CCIndex)，該方案把數(shù)據(jù)的詳細(xì)信息也存放在索引表中，不需要通過獲取的行鍵再到原表中去查找數(shù)據(jù)。

在索引實(shí)現(xiàn)方面，基于內(nèi)存的索引相較于傳統(tǒng)位于磁盤的索引在設(shè)計(jì)和架構(gòu)上都大不相同，基于內(nèi)存的索引在查詢效率上得到了極大提升。廣泛采用的內(nèi)存索引有T樹［6］、基于緩存敏感的CSS/CSB+樹和改進(jìn)的Hash索引等。T樹，是針對(duì)B+樹在內(nèi)存中空間浪費(fèi)的問題而提出的一種樹型索引。T樹所有節(jié)點(diǎn)都直接指引數(shù)據(jù)項(xiàng)，節(jié)省了中間節(jié)點(diǎn)所占空間。而針對(duì)Hash索引空間利用問題，提出了最小完美Hash索引［7］，其哈希函數(shù)不會(huì)產(chǎn)生沖突且函數(shù)的值域和參數(shù)域的大小完全相等，但這一哈希函數(shù)構(gòu)造難度非常大。后來，研究發(fā)現(xiàn)CPU高速緩存對(duì)數(shù)據(jù)查詢性能有著非常顯著的影響［8］，所以研究者在B+樹的基礎(chǔ)上對(duì)緩存作了優(yōu)化，提出了CSB+樹［9］。在Hash索引的基礎(chǔ)上，提出了可擴(kuò)展Hash、桶鏈Hash等緩存敏感的索引結(jié)構(gòu)。到了2007年，Ross［10］提出了基于現(xiàn)代處理器的Hash預(yù)取算法，將單指令多數(shù)據(jù)流(Single Instruction Multiple Data，SIMD)指令集融入到 Hash算法中，在內(nèi)存環(huán)境中大大提高了索引的性能。文獻(xiàn)［11］基于有界障礙(Bounded Disorder，BD)方法提出了一種BD樹索引，其將樹形結(jié)構(gòu)與Hash表結(jié)構(gòu)結(jié)合，上層是樹結(jié)構(gòu)，下層葉子節(jié)點(diǎn)是哈希表，每個(gè)哈希表中桶的大小等于CPU緩存塊的大小。這樣的索引結(jié)構(gòu)既對(duì)緩存作了優(yōu)化，又實(shí)現(xiàn)了針對(duì)Hash表的范圍查找。文獻(xiàn)［12］中根據(jù)BD樹索引的思想，實(shí)現(xiàn)了B+樹索引與Hash索引的結(jié)合并進(jìn)行了實(shí)驗(yàn)，結(jié)果展現(xiàn)BD樹索引具有較好的性能。

本文提出一種基于內(nèi)存的HBase二級(jí)索引的設(shè)計(jì)方案。為HBase中非行鍵的列建立索引并存儲(chǔ)在Spark集群中。Spark是一款基于內(nèi)存的并行計(jì)算框架［13］，其將數(shù)據(jù)加載到內(nèi)存中，然后在內(nèi)存中完成計(jì)算，且Spark集群能構(gòu)造一個(gè)大的內(nèi)存環(huán)境。由于是將索引建立在內(nèi)存中，所以在索引的選擇上希望得到節(jié)約存儲(chǔ)空間、查詢效率較高的索引。本文根據(jù)要建索引的列的基數(shù)大小以及是否涉及范圍查詢構(gòu)建了三種基于內(nèi)存的索引，分別是位圖索引、分段Hash索引以及BD森林索引，并利用Spark并行化的特點(diǎn)來提高索引的查詢效率。

1 基于內(nèi)存的HBase二級(jí)索引總體設(shè)計(jì)

1.1 二級(jí)索引結(jié)構(gòu)

HBase對(duì)行鍵建立了索引，對(duì)非行鍵的列未建立索引，這嚴(yán)重影響了條件查詢的效率。為此，針對(duì)HBase在進(jìn)行非行鍵的列的查詢和組合條件查詢時(shí)效率較低的問題，本文對(duì)需要查詢的列建立與行鍵對(duì)應(yīng)的二級(jí)索引，建立的二級(jí)索引結(jié)構(gòu)如圖1所示。圖1中對(duì)HBase的簇(Column Family，CF)的NAME列和ADDR.列在Spark上建立了非行鍵的列的索引，索引可以通過 NAME列或 ADDR.列中的屬性值映射到HBase中對(duì)應(yīng)的行鍵。有時(shí)會(huì)對(duì)NAME列與ADDR.列進(jìn)行組合條件查詢，故針對(duì)這兩列建立了組合條件的索引，可以通過索引映射到滿足這一組合條件的行鍵。

圖1 HBase二級(jí)索引結(jié)構(gòu)Fig.1 Secondary index structure in HBase

查詢非行鍵的列或組合條件時(shí)，可以先通過位于Spark內(nèi)存環(huán)境中的索引獲取對(duì)應(yīng)的行鍵，再利用行鍵在HBase中查詢符合條件的記錄。這樣的二級(jí)索引能極大提高條件查詢的效率。

1.2 二級(jí)索引查詢框架

面對(duì)非行鍵的列或組合條件的查詢，可以先建立上述結(jié)構(gòu)的二級(jí)索引。該索引以彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset，RDD)的形式存儲(chǔ)在Spark的內(nèi)存環(huán)境中，RDD是Spark內(nèi)存計(jì)算中一種彈性分布式數(shù)據(jù)集，且在Spark上有許多內(nèi)置操作，可以將其并行化地轉(zhuǎn)換。為了防止斷電內(nèi)存數(shù)據(jù)的丟失，對(duì)主要的RDD進(jìn)行磁盤持久化，也可從磁盤中讀取歷史數(shù)據(jù)的RDD。查詢時(shí)在Spark中對(duì)索引的RDD進(jìn)行操作，獲取對(duì)應(yīng)的行鍵，再用行鍵在HBase中查找對(duì)應(yīng)的記錄并返回給查詢的客戶端。圖2展示了二級(jí)索引的查詢框架。

圖2 二級(jí)索引查詢框架Fig.2 Secondary index query framework

這樣的查詢框架可以充分發(fā)揮HBase中行鍵的作用，同時(shí)利用了Spark內(nèi)存計(jì)算和并行化的優(yōu)勢(shì)。為了提高框架的查詢效率，本文要構(gòu)建合適的內(nèi)存索引用于該查詢框架中，這將在第2章節(jié)具體討論。

1.3 表和二級(jí)索引的構(gòu)造

使用上述的二級(jí)索引，首先要在HBase中構(gòu)造存儲(chǔ)數(shù)據(jù)的表，其中行鍵設(shè)計(jì)是構(gòu)造表的關(guān)鍵。由于HBase是無模式的，事先不需要定義列限定符和數(shù)據(jù)類型，只需利用數(shù)據(jù)中的相關(guān)字段構(gòu)建每條數(shù)據(jù)的行鍵。在構(gòu)建行鍵時(shí)，要選擇反映數(shù)據(jù)重要特征的字段組合成行鍵，并且這樣的行鍵要具有唯一性。例如在后面的實(shí)驗(yàn)中針對(duì)基于射頻識(shí)別(Radio Frequency IDentification，RFID)的機(jī)動(dòng)車電子車牌數(shù)據(jù)，本文選擇采集點(diǎn)IP和通行時(shí)間這兩個(gè)重要的字段來建立行鍵，同時(shí)在其基礎(chǔ)上加入隨機(jī)數(shù)，使行鍵更加唯一和分散，避免熱點(diǎn)問題。如果行鍵過長(zhǎng)，為了在讀寫以及存儲(chǔ)時(shí)具有好的性能，可以對(duì)行鍵進(jìn)行壓縮處理。

在二級(jí)索引的構(gòu)造過程中，建立一個(gè)輔助的記錄表。對(duì)HBase表中新插入的數(shù)據(jù)存儲(chǔ)到輔助的記錄表中，每當(dāng)記錄表中的數(shù)據(jù)個(gè)數(shù)達(dá)到一定的閾值時(shí)，就對(duì)記錄表中的數(shù)據(jù)建立對(duì)應(yīng)的索引并以RDD的形式存儲(chǔ)(具體的索引構(gòu)建過程見第二章)，故所建的索引都是分段的索引，這樣有利于Spark的并行操作。與此同時(shí)清空輔助的記錄表，用于記錄下一批新插入的數(shù)據(jù)，從而對(duì)這部分新的數(shù)據(jù)建立二級(jí)索引。由于HBase中更新操作實(shí)際上是插入新的數(shù)據(jù)，而本文在行鍵的構(gòu)造中加入隨機(jī)數(shù)使其唯一化，不存在行鍵相同根據(jù)時(shí)間戳來更新數(shù)據(jù)的情況，故本文中二級(jí)索引不進(jìn)行更新。當(dāng)在HBase的表中刪除數(shù)據(jù)時(shí)，則要將RDD形式的索引全部刪除，重新分批讀取HBase中的數(shù)據(jù)，每讀取一定數(shù)量的數(shù)據(jù)就建立分段的索引，以保證索引內(nèi)容的正確性。

2 內(nèi)存索引構(gòu)建

列的基數(shù)是指該列擁有的不重復(fù)數(shù)值的個(gè)數(shù)。例如:員工信息表中性別這列的基數(shù)是2，只有“男”和“女”兩個(gè)值。列的基數(shù)的大小直接影響索引的選擇與構(gòu)造。同時(shí)，是否涉及范圍查詢也決定了索引方法的選擇。為此，根據(jù)各列基數(shù)大小以及是否涉及范圍查詢，本文構(gòu)建了不同的內(nèi)存索引。針對(duì)基數(shù)較小列，構(gòu)建位圖索引;針對(duì)基數(shù)較大但不涉及范圍查詢的列，構(gòu)建分段Hash索引;針對(duì)基數(shù)較大且涉及范圍查詢的列，構(gòu)建BD森林索引。整個(gè)索引構(gòu)建的步驟流程如圖3所示。

2.1 對(duì)基數(shù)較小列的索引

一般認(rèn)為列基數(shù)小于100且小于HBase中的總列數(shù)的0.1%時(shí)，該列即為基數(shù)較小列。針對(duì)基數(shù)較小列，由于字段重復(fù)值較多，建立樹形索引不能帶來快速的查詢響應(yīng)，還會(huì)帶來索引空間冗余，達(dá)不到“空間換取時(shí)間”的目的。因此，針對(duì)基數(shù)較小列，采用位圖索引進(jìn)行二級(jí)索引的構(gòu)建。

位圖索引是用二進(jìn)制位0、1組成的位向量表示數(shù)據(jù)的索引信息，并通過將檢索條件映射為二進(jìn)制位的邏輯運(yùn)算來實(shí)現(xiàn)高效的查詢。設(shè)有一組數(shù)據(jù)，數(shù)據(jù)的總記錄數(shù)為N，數(shù)據(jù)中有一列為基數(shù)較小列。對(duì)基數(shù)較小列建立索引，針對(duì)基數(shù)較小列的每一屬性值a建立一個(gè)位向量X，X的長(zhǎng)度為N，判斷X的第j位Xj表示第j條記錄在該列中的值是否為屬性值a，若是a，則Xj=1;若不是a，則Xj=0。員工信息表中性別這一列建立的位圖索引示例如圖4所示。

圖3 索引構(gòu)建步驟流程Fig.3 Flowchart of index building step

圖4 員工信息表的性別位圖索引Fig.4 Bitmap index of employee information about sex

位圖索引采用0、1來存儲(chǔ)信息，在內(nèi)存中所占空間很小。內(nèi)存中一個(gè)字節(jié)的空間可以存儲(chǔ)8條某個(gè)屬性值的取值情況，例如800萬條員工信息對(duì)性別為“男”的情況建立索引，則只需消耗不到1 MB內(nèi)存空間。位圖索引的另一優(yōu)勢(shì)就是可以將組合查詢轉(zhuǎn)為高性能的位運(yùn)算。例如已經(jīng)得到N條記錄其A列中屬性值a的位向量X和B列中屬性值b的位向量W。若要查詢的組合條件為A列中值為a且B列中值為b的記錄時(shí)，只需將X與W進(jìn)行按位與的運(yùn)算得到位向量Z，若Zj=1，則第j條記錄符合本文的查詢條件。

在本文中，用字節(jié)數(shù)組來存儲(chǔ)位圖索引并將其建立在Spark構(gòu)成的內(nèi)存空間中。為了方便構(gòu)造和提高構(gòu)造速度，取每N條記錄為一組構(gòu)建分段的位圖索引。每段位圖索引在Spark內(nèi)存中用parallelize方法轉(zhuǎn)為RDD形式，RDD在Spark的環(huán)境中可以被緩存且支持并行操作。為了防止斷電內(nèi)存數(shù)據(jù)丟失，將這些RDD進(jìn)行RDD.saveAsObjectFile執(zhí)行操作，從而把數(shù)據(jù)持久化到硬盤中。在查詢時(shí)，由于需要利用數(shù)組下標(biāo)和數(shù)組中字節(jié)數(shù)值轉(zhuǎn)為對(duì)應(yīng)記錄的取值情況，故將這些分段的位圖索引按記錄順序進(jìn)行整合，用Spark中RDD.collect執(zhí)行操作轉(zhuǎn)為一個(gè)整體的位于本地的有序數(shù)組。對(duì)位圖索引進(jìn)行查詢就是對(duì)這一內(nèi)存中的數(shù)組進(jìn)行遍歷，內(nèi)存中連續(xù)空間遍歷的速度我們是可以接受的，故針對(duì)基數(shù)較少的列建立位圖索引是有效的。位圖索引在Spark中的操作如圖5所示。

圖5 位圖索引在Spark中操作過程Fig.5 Operation process of bitmap index in Spark

2.2 對(duì)基數(shù)較大但不涉及范圍查詢的列的索引

當(dāng)HBase中某列的基數(shù)較大時(shí)，就可以使用Hash索引或樹形索引。當(dāng)該列不涉及范圍查詢時(shí)，即根據(jù)一個(gè)確定的值進(jìn)行等值查詢，選擇能在O(1)的時(shí)間復(fù)雜度下準(zhǔn)確查找的Hash索引。

本文中對(duì)基數(shù)較大但不涉及范圍查詢的列構(gòu)建鏈接桶哈希，其結(jié)構(gòu)如圖6所示。在構(gòu)建Hash索引時(shí)，仍將數(shù)據(jù)分段，建立分段Hash索引，這樣不僅能方便后面的并行化查找，同時(shí)可以根據(jù)分段的大小事先確定桶的數(shù)目，以防桶的數(shù)目過小帶來查詢效率下降以及桶的數(shù)目過大帶來空間浪費(fèi)的問題。為了減少哈希表所占用的內(nèi)存空間，提高負(fù)載因子，通常的負(fù)載因子為0.75，這里選用0.8，即要對(duì) N條數(shù)據(jù)建立Hash索引，則先產(chǎn)生桶的數(shù)目為1.25*N的哈希表。雖然提高負(fù)載因子會(huì)增加桶中鏈的長(zhǎng)度從而增加查詢數(shù)據(jù)的時(shí)間開銷，但這是時(shí)間成本和空間成本上的一種折中，是可以接受的。

圖6 鏈接桶哈希結(jié)構(gòu)Fig.6 Hash structure of link bucket

在查詢時(shí)，對(duì)分段Hash索引進(jìn)行并行的查找［14］，這些索引轉(zhuǎn)為RDD的形式存儲(chǔ)在內(nèi)存中，在硬盤上也有備份。利用Spark中RDD.map轉(zhuǎn)化操作算子對(duì)每個(gè)分段Hash索引進(jìn)行時(shí)間復(fù)雜度為O(1)的快速查找。這樣的查詢速度非常理想，不會(huì)因數(shù)據(jù)量的增大產(chǎn)生巨大變化，這也是本文愿意提高負(fù)載因子的原因。索引在Spark中的操作如圖7所示。

圖7 分段哈希索引在Spark中操作過程Fig.7 Operation process of segmented hash index in Spark

2.3 對(duì)基數(shù)較大且涉及范圍查詢的列的索引

2.3.1 BD 樹索引的結(jié)構(gòu)

Hash索引不能進(jìn)行范圍查詢，故面對(duì)HBase中某列基數(shù)較大且涉及范圍查詢時(shí)，本文采用BD樹索引的思想，構(gòu)建由多棵BD樹索引組成的BD森林索引。其中BD樹索引由B+樹與哈希表結(jié)合得到，即索引的樹結(jié)構(gòu)是B+樹，B+樹的葉子節(jié)點(diǎn)由n個(gè)哈希桶組成，且每個(gè)哈希桶的大小等于CPU緩存塊的大小，故哈希桶中存放數(shù)據(jù)是固定的。同時(shí)為了能進(jìn)行范圍查找，各葉子節(jié)點(diǎn)按順序連接起來，可以通過指針進(jìn)行查詢。圖8是BD樹索引的結(jié)構(gòu)。

圖8 BD樹索引結(jié)構(gòu)Fig.8 Index structure of BD tree

在構(gòu)造BD樹索引時(shí)，使用遞歸的方法將關(guān)鍵字不斷插入。先查找關(guān)鍵字所在的哈希表，然后定位到其所在的桶中，若桶未滿則插入關(guān)鍵字;若桶已滿則需分裂該節(jié)點(diǎn)，將原哈希表中所有關(guān)鍵字分配到兩個(gè)新的哈希表中，分界可選原哈希表關(guān)鍵字的最大值和最小值的均值，同時(shí)對(duì)上層B+樹進(jìn)行修改，產(chǎn)生指向新的哈希表節(jié)點(diǎn)的指針。詳細(xì)過程可以參考文獻(xiàn)［11－12］。

在BD樹索引的查詢中，面對(duì)精確查詢，根據(jù)關(guān)鍵字在B+樹中找到對(duì)應(yīng)的葉子節(jié)點(diǎn)，即哈希表，接著則是在哈希表中進(jìn)行查詢。BD樹索引關(guān)鍵在于可以進(jìn)行范圍查詢，當(dāng)查詢的關(guān)鍵字范圍為［ks，ke］時(shí)，找到關(guān)鍵字ks所在的哈希表記為U，找到關(guān)鍵字ke所在的哈希表記為V，則U、V之間的哈希表的所有值(哈希表按順序用指針串聯(lián)在一起)、U中關(guān)鍵字大于ks對(duì)應(yīng)的值和V中關(guān)鍵字小于ke對(duì)應(yīng)的值是范圍查詢的結(jié)果。

2.3.2 BD 森樹索引的結(jié)構(gòu)

本文對(duì)基數(shù)較大且涉及范圍查詢的列構(gòu)建BD森林索引，即多棵BD樹索引，其結(jié)構(gòu)如圖9所示。

仍然將數(shù)據(jù)分段，對(duì)每一段建立BD樹索引，并轉(zhuǎn)為RDD的形式存儲(chǔ)在內(nèi)存中，利用Spark中操作對(duì)每個(gè)BD樹索引進(jìn)行查詢，操作過程同圖7的分段Hash索引。但這樣在面對(duì)范圍查詢時(shí)，要對(duì)每棵BD樹進(jìn)行查詢，最后將查詢結(jié)果進(jìn)行匯總，算法1描述了BD森林索引范圍查詢算法的過程。

算法1 BD森林索引范圍查詢算法。

輸入 查詢范圍［ks，ke］的關(guān)鍵字 ks，ke。

輸出 行鍵集合RQ。

RQ← //結(jié)果集合設(shè)為空

for each tree T in Tsdo //遍歷每棵BD樹索引

Hs← T.GetHash(ks) //通過樹形索引查找ks所在的哈希表

He← T.GetHash(ke)

H←Hs

while next［H］≠ Hsdo

H ← next［H］

RQ∪allValue［H］ //將哈希表中所有值并入結(jié)果集合中

end while

for each map M in Hsdo //遍歷哈希表

if key［M］ ＞ ksthen

//當(dāng)遍歷映射的鍵大于范圍開始的關(guān)鍵字時(shí)

RQ∪value［M］ //將映射的值并入結(jié)果集合中

end if

end for

for each map M in Hedo

if key［M］ ＜ kethen//當(dāng)遍歷映射的鍵小于范圍結(jié)束的關(guān)鍵字時(shí)

RQ ∪ value［M］

end if

end for

end for

構(gòu)建BD森林索引是因?yàn)橐淮涡詫⑺袛?shù)據(jù)構(gòu)造成BD樹索引，在轉(zhuǎn)化RDD時(shí)會(huì)因?yàn)闃涞倪f歸構(gòu)造次數(shù)［15］太多帶來StackOverflowError問題，無法轉(zhuǎn)為RDD存儲(chǔ)在Spark內(nèi)存環(huán)境中。構(gòu)建BD森林索引，降低每棵樹的高度，減少樹的遞歸構(gòu)造深度，將其成功轉(zhuǎn)為RDD。范圍查詢時(shí)雖然要對(duì)森林中的每棵樹進(jìn)行操作，但可以利用Spark中 RDD.map轉(zhuǎn)化操作算子進(jìn)行并行操作，故效果是可以接受的。

3 實(shí)驗(yàn)與結(jié)果分析

圖9 BD森林索引結(jié)構(gòu)Fig.9 Index structure of BD forest

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

本文的實(shí)驗(yàn)環(huán)境是在三臺(tái)虛擬機(jī)下搭建的HBase集群與Spark集群，為了進(jìn)行對(duì)比實(shí)驗(yàn)還搭建了Solr集群。每臺(tái)虛擬機(jī)的環(huán)境是1核CPU，2 GB內(nèi)存，60 GB硬盤，操作系統(tǒng)是CentOS7。

本文的實(shí)驗(yàn)數(shù)據(jù)是基于RFID電子車牌的交通數(shù)據(jù)，其來源于重慶市智能交通系統(tǒng)，其數(shù)據(jù)模型如表1所示。數(shù)據(jù)模型中各字段的含義分別是:記錄在表中的id號(hào)、采集點(diǎn)名稱、行駛方向、采集點(diǎn)的IP標(biāo)識(shí)、車輛的電子車牌號(hào)、車輛通過時(shí)間、車輛類型、號(hào)牌的種類以及車輛使用性質(zhì)。數(shù)據(jù)存入HBase中，用01到99之間的隨機(jī)數(shù)加上采集點(diǎn)IP標(biāo)識(shí)加上通行時(shí)間的月日時(shí)分秒構(gòu)成每條原始記錄的行鍵(Rowkey)，例如表1中的第一條記錄的行鍵為“19101112010229012445”(產(chǎn)生的隨機(jī)數(shù)是19)。這樣的行鍵具有唯一性和分散性。

在后面的實(shí)驗(yàn)中，主要對(duì)三種索引的檢索效率進(jìn)行了實(shí)驗(yàn)對(duì)比，期望基于這樣的二級(jí)索引能在數(shù)據(jù)查詢上帶來效率的提高。另外對(duì)索引的大小也十分關(guān)注，期望索引所占空間合理，以便能在內(nèi)存中存儲(chǔ)，故在實(shí)驗(yàn)中對(duì)索引所占的空間大小也進(jìn)行了實(shí)驗(yàn)測(cè)試。

表1 原始數(shù)據(jù)模型Tab.1 Original data model

3.2 結(jié)果分析

3.2.1 二級(jí)索引實(shí)驗(yàn)

在HBase中進(jìn)行查詢時(shí)通常需要利用行鍵，在不知道行鍵的情況下或通過過濾器掃描進(jìn)行查找，但這樣的查詢速度非常慢。在本實(shí)驗(yàn)中分別從1000萬、2000萬、3000萬和5000萬數(shù)量級(jí)的數(shù)據(jù)中查找行鍵為“34101079500229080703”，內(nèi)容為“金開大道，兩路方向，10.10.79.50，1410080，2016-02-29 08:07:03，K33，02，D”的記錄，分別使用行鍵查詢和過濾器掃描兩種方法進(jìn)行查找，實(shí)驗(yàn)結(jié)果如圖10所示。由圖10可以看出，通過行鍵進(jìn)行數(shù)據(jù)查詢的時(shí)間是毫秒級(jí)的，而利用過濾器進(jìn)行掃描查詢的時(shí)間是秒級(jí)的，所以建立二級(jí)索引，在查詢前事先獲取行鍵是十分有必要的。后面將分別討論前面的三種索引獲取行鍵的性能，根據(jù)列的基數(shù)大小以及是否涉及范圍查詢選擇位圖索引、分段Hash索引和BD森林索引進(jìn)行實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與基于Solr建立的二級(jí)索引獲取行鍵的性能進(jìn)行對(duì)比。

3.2.2 位圖索引實(shí)驗(yàn)

在實(shí)驗(yàn)數(shù)據(jù)中，車輛使用性質(zhì)這一列有“非運(yùn)營(yíng)”“租賃”“警用”“工程搶險(xiǎn)”等值，其基數(shù)為16;車輛類型這一列有“大型普通客車”“大型臥鋪客車”“轎車”“中型罐式貨車”等值，其基數(shù)為52。故車輛使用性質(zhì)和車輛類型這兩列都屬于基數(shù)較小的列，在這兩列上進(jìn)行組合條件查詢時(shí)，可以使用位圖索引。例如，要查詢車輛類型為“H37”，車輛使用性質(zhì)為“K”的記錄，即查找類型為輕型自卸貨車的工程搶險(xiǎn)車輛的過車記錄。對(duì)這兩列建立位圖索引，將屬性值為“H37”的位向量與屬性值為“K”的位向量進(jìn)行按位與操作，得到這一組合條件查詢的位圖索引。對(duì)索引的位向量進(jìn)行遍歷得到所需的行鍵。在1000萬、2000萬、3 000萬和5000萬數(shù)量級(jí)的數(shù)據(jù)中利用位圖索引查找類型為輕型自卸貨車的工程搶險(xiǎn)車輛的過車記錄行鍵的時(shí)間和基于Solr獲取行鍵的時(shí)間如圖11所示。由圖11可以發(fā)現(xiàn)，位圖索引查找時(shí)間是毫秒級(jí)的且優(yōu)于基于Solr的二級(jí)索引。得到這些行鍵后，就可以在HBase中快速查到相應(yīng)的記錄。

另外，位圖索引所占的存儲(chǔ)空間要遠(yuǎn)小于Solr中的索引，如圖12所示，故位圖索引適用于在內(nèi)存中使用。

圖10 使用行鍵查詢和過濾器掃描查詢效率比較Fig.10 Query efficiency comparison of rowkey query and filter scan

圖11 位圖索引和基于Solar索引查詢行鍵時(shí)間比較Fig.11 Time comparison of querying rowkey by bitmap index and Solar-based index

圖12 位圖索引和基于Solar索引存儲(chǔ)空間大小比較Fig.12 Storage space size comparison of bitmap index and Solar-based index

3.2.3 分段Hash索引實(shí)驗(yàn)

當(dāng)要根據(jù)車輛的電子車牌號(hào)來查詢表中的記錄時(shí)，可以在該列建立分段Hash索引來獲取相應(yīng)的行鍵。在1 000萬、2000萬、3000萬和5 000萬數(shù)量級(jí)的數(shù)據(jù)中利用分段Hash索引獲取電子車牌號(hào)為“1410080”的過車記錄行鍵的時(shí)間和基于Solr獲取行鍵的時(shí)間如圖13所示，可以發(fā)現(xiàn)分段Hash索引的效果是較好的。由于使用了分段Hash索引進(jìn)行了并行化的查找，故查找時(shí)間并沒有因?yàn)閿?shù)據(jù)量的增加而發(fā)生陡增，基本維持在100 ms左右獲取行鍵，大大提高了查詢效率。

圖13 分段Hash索引和基于Solar索引查詢行鍵時(shí)間比較Fig.13 Time comparison of querying rowkey by segment Hash index and Solar-based index

3.2.4 BD 森林索引實(shí)驗(yàn)

有時(shí)要對(duì)某輛車查詢其在一段時(shí)間內(nèi)的記錄，這時(shí)涉及到時(shí)間的范圍查詢，故選擇將電子車牌號(hào)與通行時(shí)間這兩列結(jié)合在一起建立BD森林索引。在1000萬、2000萬、3000萬和5000萬數(shù)量級(jí)的數(shù)據(jù)中利用BD森林索引獲取電子車牌號(hào)為“1410080”在“2016-02-29 08:00:00”至“2016-02-29 12:00:00”期間的過車記錄行鍵的時(shí)間和基于Solr獲取行鍵的時(shí)間如圖14所示。由圖14可以看出，當(dāng)數(shù)據(jù)量增大時(shí)，可以適當(dāng)提高哈希表中桶的個(gè)數(shù)來維持樹的高度，但桶的個(gè)數(shù)過大也會(huì)影響范圍查詢中首尾兩哈希表的查找性能。BD森林索引由于數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性，故查詢時(shí)間稍長(zhǎng)但獲取行鍵后進(jìn)行查詢的綜合時(shí)間仍比通過HBase過濾器掃描的時(shí)間要短不少，獲取行鍵的時(shí)間也少于基于Solr獲取行鍵的時(shí)間。

圖14 BD森林索引和基于Solar索引查詢行鍵時(shí)間比較Fig.14 Time comparison of querying rowkey by BD forest index and Solar-based index

3.2.5 二級(jí)索引所占空間實(shí)驗(yàn)

整個(gè)二級(jí)索引以RDD的形式存儲(chǔ)在Spark構(gòu)建的內(nèi)存環(huán)境中，故期望索引能夠在內(nèi)存中存儲(chǔ)。在1 000萬、2000萬、3000萬和5000萬數(shù)量級(jí)的數(shù)據(jù)中建立整體的二級(jí)索引(包含關(guān)于車輛使用性質(zhì)、車輛類型的位圖索引、關(guān)于電子車牌號(hào)的分段Hash索引以及關(guān)于電子車牌號(hào)和通行時(shí)間的BD森林索引)的空間大小如圖15所示。在當(dāng)前的數(shù)據(jù)規(guī)模下索引可以在集群的2560 MB執(zhí)行內(nèi)存中存儲(chǔ)。

圖15 二級(jí)索引空間大小Fig.15 Space size of secondary index

4 結(jié)語

本文針對(duì)HBase無法在非行鍵的列上建立索引導(dǎo)致條件查詢效率低下的問題建立了基于內(nèi)存的二級(jí)索引。根據(jù)每列基數(shù)大小以及是否涉及范圍查詢構(gòu)建不同類型的索引并進(jìn)行改進(jìn)，使其在Spark搭建的內(nèi)存環(huán)境中進(jìn)行高效的檢索。實(shí)驗(yàn)結(jié)果表明這樣的二級(jí)索引大大提高了查詢效率，值得構(gòu)建。對(duì)此下一步準(zhǔn)備對(duì)索引的結(jié)構(gòu)進(jìn)行再次的改進(jìn)，希望減小Hash索引的空間大小以及提高樹形索引的并行度，并考慮分布式索引的改進(jìn)，從而繼續(xù)提高二級(jí)索引的整體性能并將其運(yùn)用在實(shí)時(shí)數(shù)據(jù)處理中。