陳順舉，鄒 喆，劉 銳，陶 濤，汪 超，鄭林江

（1.重慶市公安局渝北區(qū)分局交通巡邏警察支隊(duì)，重慶 401120；2.重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

隨著物聯(lián)網(wǎng)和傳感器技術(shù)的快速發(fā)展，產(chǎn)生了海量的多源異構(gòu)數(shù)據(jù)，針對(duì)這些大數(shù)據(jù)的儲(chǔ)存和管理逐漸成為了研究的熱點(diǎn)。傳統(tǒng)關(guān)系型數(shù)據(jù)庫由于存儲(chǔ)能力和擴(kuò)展性等方面的不足，無法滿足海量數(shù)據(jù)實(shí)時(shí)的查詢處理需求［1］。近年來，非關(guān)系型數(shù)據(jù)庫的應(yīng)用和發(fā)展為海量數(shù)據(jù)的存儲(chǔ)管理帶來了新的研究思路［2］。HBase［3］作為其中的代表，是一種被廣泛應(yīng)用、高效的分布式數(shù)據(jù)庫。它在行鍵上建立了類B+樹的索引，可以支持基于行鍵的快速查詢。但對(duì)于非行鍵列的查詢，由于缺少索引能力，需要對(duì)全表進(jìn)行掃描。全表掃描在海量數(shù)據(jù)下的查詢時(shí)延是難以接受的，極大地影響了HBase非行鍵列的查詢性能。

為了提升HBase對(duì)非行鍵列的查詢性能，研究提出二級(jí)索引方案，建立非行鍵列和行鍵之間的索引。在查詢非行鍵列時(shí)，先從二級(jí)索引中查詢對(duì)應(yīng)的行鍵集合，再通過得到的行鍵集在HBase中查找最終結(jié)果。近年來，各類二級(jí)索引技術(shù)相繼提出，為HBase快速查詢提供了解決方案。但由于應(yīng)用場(chǎng)景和HBase特性的限制，這些方案仍然存在數(shù)據(jù)不一致、維護(hù)代價(jià)高等問題，并且在設(shè)計(jì)中未充分考慮通信開銷和索引結(jié)構(gòu)的分類和優(yōu)化。

基于上述問題，設(shè)計(jì)一種基于協(xié)處理器的HBase分類二級(jí)索引方案。該方案提出一種基于協(xié)處理器的索引管理和并行查詢機(jī)制，通過Observer在內(nèi)存中建立并維護(hù)索引，使得索引和數(shù)據(jù)始終存儲(chǔ)在同一個(gè)RegionServer中，能有效降低通信時(shí)間開銷，保證數(shù)據(jù)和索引的一致性；同時(shí)，通過Endpoint設(shè)計(jì)Region級(jí)別的并行查詢算法，進(jìn)一步提升了HBase的查詢性能。針對(duì)索引結(jié)構(gòu)單一，未充分利用內(nèi)存性能的問題，本文提出一種分類內(nèi)存索引模型。根據(jù)非行鍵列的基數(shù)大小和有無范圍查詢需求，設(shè)計(jì)并優(yōu)化3種索引結(jié)構(gòu)。在構(gòu)建二級(jí)索引時(shí)，選擇恰當(dāng)?shù)慕Y(jié)構(gòu)，可以有效平衡查詢性能和索引性能。

1 相關(guān)研究

研究領(lǐng)域常采用二級(jí)索引方案來提升HBase的查詢性能。通過對(duì)待索引列建立與行鍵對(duì)應(yīng)的二級(jí)索引，將非行鍵列的查詢轉(zhuǎn)換成查詢二級(jí)索引對(duì)應(yīng)的行鍵和通過所得行鍵在HBase中查詢結(jié)果2個(gè)步驟［4］。圖1中對(duì)列族 CF下的 id列和time列分別建立屬性值到對(duì)應(yīng)行鍵的映射關(guān)系。為滿足組合條件下的查詢需要，可以選擇性的維護(hù)組合條件查詢的索引結(jié)構(gòu)。根據(jù)索引存儲(chǔ)方式的不同，二級(jí)索引方案又可分為基于客戶端、基于HBase內(nèi)部機(jī)制和基于內(nèi)存的方案。

圖1 HBase二級(jí)索引結(jié)構(gòu)

1）基于客戶端的方案：ITHBase［5］是由開源社區(qū)開發(fā)的一款帶索引的事務(wù)型HBase擴(kuò)展，其通過客戶端邏輯構(gòu)建并維護(hù)索引表，一個(gè)查詢請(qǐng)求需要2次遠(yuǎn)程的過程調(diào)用。近年來，基于Solr構(gòu)建HBase二級(jí)索引的方案［6］受到業(yè)界廣泛應(yīng)用。Solr［7］是一款高效的基于Lucene的企業(yè)級(jí)全文搜索引擎，通過將HBase中的數(shù)據(jù)以HTTP請(qǐng)求的方式發(fā)送到Solr服務(wù)器，即可建立非行鍵列到行鍵的二級(jí)索引結(jié)構(gòu)。在查詢索引時(shí)，得益于Solr高效的檢索性能，只需通過Get請(qǐng)求即可得到對(duì)應(yīng)的索引結(jié)果。此類方案將索引存儲(chǔ)于HBase集群之外的客戶端或第三方平臺(tái)中，需要額外建立和維護(hù)索引，會(huì)出現(xiàn)索引維護(hù)困難，數(shù)據(jù)不一致等問題。

2）基于HBase內(nèi)部機(jī)制的方案：隨著HBase功能的加強(qiáng)，HBase 0.92版本以后引入了協(xié)處理器的概念。它可以將用戶自定義的代碼放在服務(wù)器上運(yùn)行，允許用戶執(zhí)行Region級(jí)的操作［8］。協(xié)處理器又分為 Observer和 Endpoint兩類，其中Observer與觸發(fā)器類似，當(dāng)特定事件發(fā)生時(shí)會(huì)觸發(fā)回調(diào)函數(shù)的執(zhí)行；Endpoint則更像存儲(chǔ)過程，支持將用戶自定義的操作添加到服務(wù)器端。用戶可以組合Observer和Endpoint實(shí)現(xiàn)特定的功能，極大豐富了HBase的可用性。Hindex［9］是華為基于協(xié)處理器對(duì)HBase二級(jí)索引的實(shí)現(xiàn)，其核心思想是保證索引表和主表在同一個(gè)RegionServer上，能有效降低節(jié)點(diǎn)間的數(shù)據(jù)傳輸開銷。Zou等［10］提出了互補(bǔ)聚簇式索引CCIndex，其通過在索引表中額外存儲(chǔ)詳細(xì)的數(shù)據(jù)信息，能節(jié)省結(jié)果查詢帶來的時(shí)間開銷，從而提升數(shù)據(jù)查詢性能?，F(xiàn)有的這些基于HBase內(nèi)部機(jī)制的方案，通常只利用Observer協(xié)處理器建立和維護(hù)索引。在查詢時(shí)需要修改scan函數(shù)并添加過濾器，未能有效利用Endpoint的并行處理能力，減少通信時(shí)間消耗，且需要額外建立索引表，會(huì)導(dǎo)致插入性能下降，索引空間開銷過大等問題。

3）基于內(nèi)存的方案：隨著內(nèi)存性能的提升和價(jià)格的下降，內(nèi)存在實(shí)時(shí)數(shù)據(jù)處理中發(fā)揮了越來越重要的作用。目前，用內(nèi)存計(jì)算提升大數(shù)據(jù)處理性能已成為公認(rèn)的發(fā)展方向［11］。廣泛應(yīng)用的內(nèi)存索引有：T樹、CSS／CSB+樹、哈希、BD樹以及它們的改進(jìn)結(jié)構(gòu)。其中，T樹［12］是針對(duì)主存訪問優(yōu)化的索引技術(shù)，能有效節(jié)省空間占用，但由于較高的TBL失配率會(huì)影響其查詢效率；基于緩存敏感的CSS樹／CSB+樹［13］減少了高速緩存對(duì)索引的影響，提高了查詢效率，但會(huì)導(dǎo)致更新性能差等問題；哈希索引則具有極好的隨機(jī)查詢性能，但存在空間利用問題，改進(jìn)的可擴(kuò)展哈希、鏈接桶哈希［14］等結(jié)構(gòu)可以提升其整體性能；BD樹［15］將樹形結(jié)構(gòu)與哈希表結(jié)合，既對(duì)緩存作了優(yōu)化，又實(shí)現(xiàn)了范圍查詢?；谶@些內(nèi)存索引結(jié)構(gòu)，越來越多的研究選擇將部分或全部二級(jí)索引存放在內(nèi)存中，極大地提升了索引的管理和查詢性能。葛微等［16］提出了一種名為HiBase的基于分層式索引的設(shè)計(jì)方案，在持久化索引表的基礎(chǔ)上，對(duì)熱點(diǎn)數(shù)據(jù)在Redis內(nèi)存數(shù)據(jù)庫中進(jìn)行緩存，并利用熱度累積策略替換緩存，有效提高了查詢效率。Ye等［17］針對(duì)傳感器數(shù)據(jù)提出了基于協(xié)處理器的索引方案，在內(nèi)存中建立并維護(hù)HT樹索引，顯著提升了索引數(shù)據(jù)的檢索速度。此類方案利用了內(nèi)存查詢處理的速度優(yōu)勢(shì)，但仍存在索引結(jié)構(gòu)單一，未充分考慮待索引列的數(shù)據(jù)特征和查詢需求等問題。

2 基于協(xié)處理器的分類二級(jí)索引

2.1 整體框架

基于協(xié)處理器的HBase分類二級(jí)索引方案的整體框架如圖2所示，主要由數(shù)據(jù)表模塊、索引模塊和查詢模塊3個(gè)部分組成。其中，數(shù)據(jù)表模塊通過設(shè)計(jì)滿足存儲(chǔ)需求的行鍵和列族，更好地持久化原始數(shù)據(jù)。索引模塊則通過基于Observer的索引管理機(jī)制，在數(shù)據(jù)插入和更新的同時(shí)，構(gòu)建并維護(hù)每個(gè)Region中的二級(jí)索引。查詢模塊通過基于Endpoint的并行查詢算法實(shí)現(xiàn)對(duì)非行鍵列的快速查詢。此外，為防止內(nèi)存索引斷電丟失，索引結(jié)果會(huì)定期序列化并存儲(chǔ)至HDFS。

圖2 整體框架

1）數(shù)據(jù)表模塊：數(shù)據(jù)表模塊用于持久化需要存儲(chǔ)的數(shù)據(jù)，在構(gòu)建時(shí)主要考慮行鍵和列族的設(shè)計(jì)。設(shè)計(jì)行鍵時(shí)，需要選擇能反映數(shù)據(jù)重要特征的字段組合成行鍵，使其滿足唯一、長(zhǎng)度較短、熱點(diǎn)分散等特性。設(shè)計(jì)列族時(shí)，為避免過多列族帶來額外的IO操作，導(dǎo)致系統(tǒng)性能下降的問題，通常僅需設(shè)計(jì)一個(gè)列族，用于存儲(chǔ)一行原始數(shù)據(jù)的所有值。設(shè)計(jì)表時(shí)，為實(shí)現(xiàn)對(duì)讀寫請(qǐng)求的負(fù)載均衡，可以對(duì)數(shù)據(jù)表進(jìn)行預(yù)分區(qū)。

2）索引模塊：索引模塊用于管理Region級(jí)別的索引，在內(nèi)存中為每個(gè)Region分別構(gòu)建分類二級(jí)索引。采用基于Observer的索引管理機(jī)制，在數(shù)據(jù)插入時(shí)，按數(shù)據(jù)特征和查詢需求，選擇位圖索引、哈希索引和BD樹索引中的一種結(jié)構(gòu)構(gòu)建二級(jí)索引。在Region發(fā)生分裂或遷移時(shí)，對(duì)應(yīng)的索引也需要分裂或遷移，從而保證索引和數(shù)據(jù)始終在同一RegionServer中。

3）查詢模塊：查詢模塊用于接收客戶端的查詢需求。采用基于Endpoint的并行查詢算法，在該表所有在線的Region中并行查詢二級(jí)索引獲取行鍵集合后，在對(duì)應(yīng)Region中直接批量獲取結(jié)果，并返回至客戶端。客戶端接收所有結(jié)果后，進(jìn)行匯總。

2.2 基于協(xié)處理器的索引管理和并行查詢機(jī)制

為了實(shí)現(xiàn)高效的索引管理和數(shù)據(jù)查詢，本文提出一種基于協(xié)處理器的索引管理和并行查詢機(jī)制，包括基于Observer的索引管理機(jī)制和基于Endpoint的并行查詢算法。

2.2.1 基于Observer的索引管理機(jī)制

索引管理機(jī)制流程如圖3所示，包括索引構(gòu)建和索引維護(hù)兩部分。構(gòu)建索引時(shí)，根據(jù)數(shù)據(jù)輸入方式的不同，可分為面向流式數(shù)據(jù)和面向歷史數(shù)據(jù)2類。

圖3 索引管理流程框圖

對(duì)于流式數(shù)據(jù)的索引構(gòu)建方法，本文重寫Observer提供的回調(diào)函數(shù)prePut，每插入1條數(shù)據(jù)前會(huì)被觸發(fā)調(diào)用。prePut函數(shù)根據(jù)索引信息對(duì)用戶發(fā)起的Put操作進(jìn)行分析，當(dāng)Put操作的數(shù)據(jù)包含索引列時(shí)，根據(jù)分類內(nèi)存索引模型對(duì)其構(gòu)建索引。由于索引存儲(chǔ)于內(nèi)存中，為了防止掉電丟失，需要對(duì)索引文件進(jìn)行序列化，定期轉(zhuǎn)存在HDFS中。歷史數(shù)據(jù)一般相對(duì)較大，且已存于HBase數(shù)據(jù)庫中，為了加快這些歷史數(shù)據(jù)的索引構(gòu)建速度，本文重寫Observer提供的回調(diào)函數(shù)postOpen，當(dāng)Region加載完成后被觸發(fā)調(diào)用，若HDFS中有存儲(chǔ)完整的索引文件，可以直接對(duì)文件進(jìn)行反序列化操作構(gòu)建索引。否則，需要遍歷Region中的所有數(shù)據(jù)，重新構(gòu)建索引。

在索引構(gòu)建完畢后，為了保證索引與數(shù)據(jù)存儲(chǔ)在同一RegionServer中，需要對(duì)索引進(jìn)行維護(hù)。主要體現(xiàn)在2個(gè)方面，即Region的split和migrated，這里同樣利用Observer相關(guān)的回調(diào)函數(shù)進(jìn)行維護(hù)。當(dāng)Region發(fā)生split操作時(shí)，1個(gè)Region會(huì)分裂為2個(gè)新的Region。通過重寫觸發(fā)調(diào)用的postCompletedSplit函數(shù)，刪除原Region的索引文件，并對(duì)分裂后產(chǎn)生的Region重新讀取數(shù)據(jù)，分別構(gòu)建索引。當(dāng) Region發(fā)生migrated操作時(shí)，1個(gè)Region會(huì)被分配到其他RegionServer中。通過重寫觸發(fā)調(diào)用postBalance函數(shù)，根據(jù)從Region計(jì)劃參數(shù)中獲取到待分配Region，源RegionServer和目的RegionServer等信息，把索引文件遷移到對(duì)應(yīng)的目的RegionServer中。為了提高框架的查詢效率，發(fā)揮協(xié)處理器處理Region級(jí)別操作的優(yōu)勢(shì)，需要根據(jù)數(shù)據(jù)特點(diǎn)和查詢需求構(gòu)建適合的索引結(jié)構(gòu)，這將在2.3中具體討論。

2.2.2 基于Endpoint的并行查詢算法

由于查詢條件是否包含行鍵對(duì)查詢時(shí)間影響很大，本文在客戶端中對(duì)行鍵的查詢和非行鍵列的查詢分別進(jìn)行處理。對(duì)于含有行鍵的查詢，直接使用HBase自帶的Get和Scan函數(shù)處理即可。對(duì)于含有非行鍵列的查詢，為了充分利用HBase分布式特性，提升查詢效率，本文實(shí)現(xiàn)了基于Endpoint的并行化查詢算法。相較于MapReduce框架，Endpoint更加輕量級(jí)，查詢效率更高，花費(fèi)的構(gòu)建時(shí)間和資源也更少，非常適用于本文的查詢環(huán)境。Endpoint的實(shí)現(xiàn)包括了基于Protobuf的RPC定義，協(xié)議接口實(shí)現(xiàn)和調(diào)用函數(shù)實(shí)現(xiàn)等步驟［18］。

算法1 基于Endpoint的并行查詢算法輸入：需要查詢的非行鍵列cq，查詢條件qcs。輸出：所有符合要求的查詢結(jié)果集合。1 if secondary index not contain cq，then 2 return table.scan.filter（cq，qcs）／／通過過濾器對(duì)全表進(jìn)行掃描，并返回結(jié)果3 else 4 for each Region do in parallel ／／Region并行查詢5 rs← secondary index.getRowkeys（cq，qcs）；／／查詢索引得到滿足要求的行鍵集合rs 6 qrs← Region.get（rs）；／／查詢對(duì)應(yīng) Region 7 end parallel 8 return client.collect（qrs）；／／客戶端匯總所有結(jié)果集9 end if

對(duì)非行鍵列的查詢?nèi)缢惴?所示。當(dāng)系統(tǒng)未對(duì)查詢列建立二級(jí)索引時(shí)，需要利用查詢條件設(shè)置過濾器并掃描全表以獲得查詢結(jié)果集合。當(dāng)查詢列包含相應(yīng)二級(jí)索引時(shí)，行4～7描述了所有Region并行執(zhí)行Endpoint中設(shè)計(jì)的函數(shù)。在每個(gè)Endpoint查詢過程中，先查詢對(duì)應(yīng)的二級(jí)索引以獲得滿足要求的行鍵集合rs，再根據(jù)rs訪問Region中的數(shù)據(jù)，得到結(jié)果集qrs返回至客戶端。在這里由于查詢?cè)诿總€(gè)Region中并行執(zhí)行，可以獲得高效的查詢效率。加之索引和數(shù)據(jù)維護(hù)在同一個(gè)RegionServer中，在得到行鍵后可以直接在對(duì)應(yīng)Region中查找到數(shù)據(jù)，能有效減少傳輸開銷，進(jìn)一步提高查詢效率。最后，客戶端只需要匯總從Region接收到的結(jié)果即可。

2.3 分類內(nèi)存索引模型

列的基數(shù)大小和有無范圍查詢需求直接影響了索引結(jié)構(gòu)的選擇，構(gòu)建符合數(shù)據(jù)特征和查詢需求的索引可以節(jié)省索引開銷，穩(wěn)定查詢時(shí)間，從而平衡索引性能和查詢性能。為此，本文根據(jù)待索引列的基數(shù)大小和有無范圍查詢需求，構(gòu)建了3種不同的二級(jí)索引結(jié)構(gòu)。分類內(nèi)存索引模型如圖4所示。針對(duì)基數(shù)較小的列，在每個(gè)Region中分別構(gòu)建位圖索引。針對(duì)基數(shù)較大但無范圍查詢需求的列，構(gòu)建哈希索引。針對(duì)基數(shù)較大且有范圍查詢需求的列，則構(gòu)建BD樹索引。索引存儲(chǔ)在Region的內(nèi)存中，詳細(xì)的維護(hù)和查詢過程見2.2節(jié)。

圖4 分類內(nèi)存索引模型

2.3.1 基數(shù)較小列的位圖索引

列基數(shù)是指該列具有的不相同屬性值的個(gè)數(shù)，通常將基數(shù)小于總行數(shù)0.1%的列認(rèn)定為基數(shù)較小列［19］。例如，在作為實(shí)驗(yàn)數(shù)據(jù)集的出租GPS數(shù)據(jù)中，運(yùn)營(yíng)狀態(tài)這一列有空車、載客2種值，列基數(shù)為2，屬于基數(shù)較小列。對(duì)此列建立索引時(shí)，由于屬性的重復(fù)值非常多，樹形結(jié)構(gòu)索引非但不能提升數(shù)據(jù)的查詢性能，還會(huì)帶來額外的空間開銷。故本文選擇位圖索引結(jié)構(gòu)為基數(shù)較小列構(gòu)建二級(jí)索引。

位圖索引是一種使用位向量表示數(shù)據(jù)信息的索引結(jié)構(gòu)，其由比特位0和1組成。檢索時(shí)，通過將查詢條件轉(zhuǎn)換為布爾邏輯運(yùn)算，能有效提升索引的查詢性能［20］。設(shè)有一個(gè)含有n行記錄的數(shù)據(jù)表，其上有一個(gè)基數(shù)大小為m的基數(shù)較小列。針對(duì)該列構(gòu)建位圖索引時(shí)，需要?jiǎng)?chuàng)建m個(gè)長(zhǎng)度為n的位向量。其中，每個(gè)屬性值b對(duì)應(yīng)1個(gè)位向量Y，Yi用于記錄數(shù)據(jù)表中第i行記錄在該列的取值情況。若該列屬性值等于b，則Yi＝1；否則，Yi＝0。對(duì)出租汽車GPS數(shù)據(jù)表中運(yùn)營(yíng)狀態(tài)這一列建立位圖索引，如圖5所示。由于運(yùn)營(yíng)狀態(tài)的列基數(shù)為2，故需要構(gòu)建2個(gè)長(zhǎng)度為N的列向量。

圖5 出租車GPS數(shù)據(jù)表運(yùn)營(yíng)狀態(tài)位圖索引

位圖索引采用比特位存儲(chǔ)數(shù)據(jù)信息，由此帶來的索引空間開銷很小。8條某個(gè)屬性值的取值情況對(duì)應(yīng)8個(gè)比特位，只需占用1個(gè)字節(jié)的空間。例如，在800萬條實(shí)驗(yàn)數(shù)據(jù)中對(duì)運(yùn)營(yíng)狀態(tài)為載客的情況構(gòu)建位圖索引，僅有不到1 MB的索引空間開銷。此外，位圖索引還可以將多個(gè)基數(shù)較小列的組合查詢轉(zhuǎn)換為高效的布爾邏輯運(yùn)算。例如實(shí)驗(yàn)數(shù)據(jù)中，要查詢運(yùn)營(yíng)狀態(tài)為“載客”，行駛方向?yàn)椤?0”的行車記錄，只需要將運(yùn)營(yíng)狀態(tài)列中屬性值為“載客”的位向量與行駛方向列中屬性值為“30”的位向量進(jìn)行按位與運(yùn)算，得到該組合查詢對(duì)應(yīng)的位向量Z。再對(duì)Z進(jìn)行遍歷，查詢Zi＝1對(duì)應(yīng)的第i條記錄即為所需的行鍵值。

2.3.2 基數(shù)較大但無范圍查詢需求列的哈希索引

待索引列的基數(shù)較大時(shí)，可以使用哈希索引或樹形結(jié)構(gòu)索引。但當(dāng)該列無范圍查詢需求，即可根據(jù)確定的屬性值進(jìn)行等值查詢時(shí)，一般選擇哈希索引可以獲得更好的索引性能。

本文選擇鏈接桶哈希對(duì)基數(shù)較大但無范圍查詢需求的列構(gòu)建二級(jí)索引。鏈接桶哈希索引由一組鏈表構(gòu)成，每一個(gè)鏈表稱為一個(gè)桶，桶中元素具有相同的哈希碼并通過單鏈表進(jìn)行組織。插入數(shù)據(jù)時(shí)，先通過關(guān)鍵字生成哈希碼，從而確定所屬桶位置；然后在該桶對(duì)應(yīng)的鏈表頭部插入數(shù)據(jù)即可。這種采用鏈?zhǔn)浇Y(jié)構(gòu)處理哈希沖突的方法，能較好地適用于海量數(shù)據(jù)頻繁插入的情況。查詢索引時(shí)，同樣通過哈希碼先確定桶的位置，然后遍歷對(duì)應(yīng)的鏈表，直到查詢到指定記錄的行鍵。桶的數(shù)量對(duì)鏈接桶哈希索引的性能影響較大。若桶的數(shù)量過多，會(huì)導(dǎo)致索引空間開銷增大，帶來內(nèi)存空間的浪費(fèi)；若桶的數(shù)量過少，則會(huì)導(dǎo)致同一桶中鏈接的數(shù)據(jù)增多，進(jìn)而造成查詢性能的降低和退化。由于本文對(duì)每個(gè)Region分別構(gòu)建哈希索引，可以根據(jù)Region大小事先確定桶的數(shù)量，從而解決上述空間浪費(fèi)和性能下降的問題。此外，為了進(jìn)一步降低哈希索引帶來的空間開銷，本文適當(dāng)提高了負(fù)載因子。負(fù)載因子的提高意味著索引結(jié)構(gòu)更加緊湊，需要構(gòu)建的桶數(shù)量隨之減少。雖然在一定程度上會(huì)增加索引查詢的時(shí)間，但這是對(duì)索引性能和查詢性能的綜合考量，在可接受范圍內(nèi)。實(shí)驗(yàn)數(shù)據(jù)中，車輛eid就屬于基數(shù)較大但無范圍查詢需求的列。對(duì)該列進(jìn)行索引查詢時(shí)，通過在內(nèi)存中對(duì)不同Region的哈希索引進(jìn)行并行檢索，能獲得非常理想的查詢性能，且不會(huì)隨著數(shù)據(jù)量的增大而發(fā)生陡變。

2.3.3 基數(shù)較大且有范圍查詢需求列的BD樹索引

哈希索引無法支持屬性值的范圍查詢，故本文選擇BD樹對(duì)基數(shù)較大且有范圍查詢需求的列構(gòu)建二級(jí)索引。BD樹由上下2層構(gòu)成：其中，上層的非葉子節(jié)點(diǎn)為樹形結(jié)構(gòu)，通常采用B+樹進(jìn)行實(shí)現(xiàn)；下層的葉子節(jié)點(diǎn)為哈希表，由n個(gè)哈希桶組成。其結(jié)合了B+樹索引和哈希索引的優(yōu)點(diǎn)，能實(shí)現(xiàn)快速的索引查詢。此外，各個(gè)葉子節(jié)點(diǎn)通過指針按順序鏈接，可以滿足范圍查詢的需求。

在構(gòu)建BD樹時(shí)，先通過關(guān)鍵字找到對(duì)應(yīng)的葉子節(jié)點(diǎn)。然后通過計(jì)算哈希碼確定哈希桶的位置，并將對(duì)應(yīng)的行鍵值插入到該桶中。若桶中數(shù)據(jù)未滿，則插入操作完成；否則，需要對(duì)BD樹進(jìn)行分裂操作。即將原葉子節(jié)點(diǎn)中所有記錄按關(guān)鍵字大小分配到2個(gè)新的葉子節(jié)點(diǎn)中，通常將原葉子節(jié)點(diǎn)中關(guān)鍵字的最大值和最小值的均值作為分界點(diǎn)。葉子節(jié)點(diǎn)分裂后可能會(huì)引發(fā)BD樹索引的調(diào)整，故在插入1個(gè)新的葉子節(jié)點(diǎn)時(shí)需要判斷對(duì)應(yīng)BD樹結(jié)構(gòu)是否正常。若正常，則分裂完成；否則，需要對(duì)非葉子節(jié)點(diǎn)進(jìn)行相應(yīng)的分裂操作，即對(duì)上層B+樹的結(jié)構(gòu)進(jìn)行修改，從而指向新的葉子節(jié)點(diǎn)。詳細(xì)過程可以參考文獻(xiàn)［21］。

在檢索BD樹時(shí)，針對(duì)單值查詢，先通過關(guān)鍵字在B+樹中定位到葉子節(jié)點(diǎn)對(duì)應(yīng)的哈希表，然后通過計(jì)算哈希碼對(duì)哈希表進(jìn)行查詢，可以很快得到索引結(jié)果。針對(duì)范圍查詢，假設(shè)某個(gè)查詢的關(guān)鍵字范圍為［qs，qe］，首先找到關(guān)鍵字 qs所在的哈希表記為U，再找到關(guān)鍵字qe所在的哈希表記為V，則U和V間的哈希表的所有值，以及U中關(guān)鍵字大于qs對(duì)應(yīng)的值和V中關(guān)鍵字小于qe對(duì)應(yīng)的值均為該范圍查詢的結(jié)果。

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

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

本文從查詢性能和索引性能等多個(gè)方面驗(yàn)證所提方案的有效性。默認(rèn)實(shí)驗(yàn)環(huán)境共有5個(gè)節(jié)點(diǎn)，搭建的HBase集群包含1個(gè)Master節(jié)點(diǎn)和4個(gè)RegionServer節(jié)點(diǎn)。為了進(jìn)行對(duì)比實(shí)驗(yàn)，本文還搭建了Solr集群和Redis集群，并實(shí)現(xiàn)了基于Solr和HiBase的二級(jí)索引方案。實(shí)驗(yàn)環(huán)境的節(jié)點(diǎn)配置信息見表1。

表1 實(shí)驗(yàn)環(huán)境節(jié)點(diǎn)配置信息表

實(shí)驗(yàn)采用的數(shù)據(jù)集是出租車行車GPS數(shù)據(jù)，其來源于重慶市智能交通系統(tǒng)。表2展示了原始數(shù)據(jù)部分樣本，其中各字段的含義分別是：每行數(shù)據(jù)在表中的id號(hào)、車輛eid（已脫敏處理）、GPS時(shí)間、經(jīng)度、緯度、速度、行駛方向和運(yùn)營(yíng)狀態(tài)（1為載客、0為空車）。

表2 原始數(shù)據(jù)

二級(jí)索引方案中，非行鍵列的查詢由查詢二級(jí)索引對(duì)應(yīng)的行鍵和通過所得行鍵在HBase中查詢結(jié)果2個(gè)步驟組成。從而有公式：Ttotal＝Tindex+Tresult，即整體查詢時(shí)間 Ttotal等于索引查詢時(shí)間Tindex和結(jié)果查詢時(shí)間Tresult之和。為了更充分詳盡地驗(yàn)證所提方案的查詢性能，本文對(duì)索引查詢和結(jié)果查詢2個(gè)部分分別進(jìn)行實(shí)驗(yàn)，并對(duì)比了本文方案和基于Solr以及HiBase方案的整體查詢性能。此外，在實(shí)時(shí)的查詢速度之上，我們期望方案有較好擴(kuò)展性和數(shù)據(jù)插入性能，以及合理的內(nèi)存占用大小，故對(duì)方案的擴(kuò)展性以及索引的構(gòu)造時(shí)間和內(nèi)存占用情況也進(jìn)行了實(shí)驗(yàn)和分析。

3.2 索引查詢對(duì)比實(shí)驗(yàn)

本文所提方案根據(jù)數(shù)據(jù)特征和查詢需求在位圖索引、哈希索引和BD樹索引中選擇適合的結(jié)構(gòu)構(gòu)建二級(jí)索引。為驗(yàn)證這3種不同類型索引的查詢性能，在十萬、百萬、千萬數(shù)量級(jí)的數(shù)據(jù)下進(jìn)行對(duì)比實(shí)驗(yàn)。圖6的橫坐標(biāo)是索引查詢結(jié)果的數(shù)據(jù)量，縱坐標(biāo)分別是3種索引的查詢時(shí)間Tindex。每組實(shí)驗(yàn)測(cè)試100次并取平均值作為最終結(jié)果。對(duì)比實(shí)驗(yàn)中，HiBase方案的索引查詢時(shí)間取熱查詢下的最優(yōu)值，即每次索引查詢均在內(nèi)存中命中。由于基于Solr的方案時(shí)間消耗較大，等比例坐標(biāo)無法很好地展示，這里使用指數(shù)坐標(biāo)。

圖6 索引查詢時(shí)間對(duì)比

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

實(shí)驗(yàn)數(shù)據(jù)中，行駛方向這一列的基數(shù)為360，小于總行數(shù)的0.1%，屬于基數(shù)較小的列。在對(duì)該列的值構(gòu)建索引時(shí)，采用位圖索引。在查詢行駛方向?yàn)椤?60”的行車記錄實(shí)驗(yàn)中，索引查詢時(shí)間Tindex如圖6（a）所示?？梢钥闯?，位圖索引查詢時(shí)間優(yōu)于基于Solr的方案，但略高于HiBase的熱查詢時(shí)間（最優(yōu)值）。這是因?yàn)槲粓D索引存儲(chǔ)在內(nèi)存中能獲得高效的查詢性能，但其需要對(duì)位向量進(jìn)行遍歷，相較于HiBase的熱查詢需要更多的時(shí)間。隨著數(shù)據(jù)量增大，本文方案中索引分布式的優(yōu)勢(shì)體現(xiàn)，查詢性能逐漸接近HiBase熱查詢的水平。

3.2.2 哈希索引實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)中，車輛id屬于基數(shù)較大但無范圍查詢需求的列，可以在該列上建立哈希索引來獲取相應(yīng)行鍵。在查找車輛id為“7115”的行車記錄實(shí)驗(yàn)中，索引查詢時(shí)間Tindex如圖6（b）所示?？梢钥闯?，哈希索引的查詢性能優(yōu)于基于Solr和HiBase的方案。這是由于使用了基于Region的哈希索引和并行化的查詢方式，查詢時(shí)間隨著數(shù)據(jù)的增長(zhǎng)能保持較好的穩(wěn)定性。

3.2.3 BD樹索引實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)中，速度這一列屬于基數(shù)較大且有范圍查詢需求的列，可以在該列上建立BD樹索引來獲取相應(yīng)行鍵。在查找行駛速度在80～81 km／h的行車記錄實(shí)驗(yàn)中，索引查詢時(shí)間Tindex如圖6（c）所示?？梢钥闯?，BD樹索引查詢時(shí)間是毫秒級(jí)的。由于其索引結(jié)構(gòu)的復(fù)雜性，故查詢時(shí)間稍長(zhǎng)但仍優(yōu)于基于Solr和HiBase的方案。

3.3 結(jié)果查詢對(duì)比實(shí)驗(yàn)

在通過二級(jí)索引獲得查詢對(duì)應(yīng)的行鍵后，需要根據(jù)行鍵集合在HBase中查詢結(jié)果。為驗(yàn)證方案中基于協(xié)處理器的索引管理和并行查詢機(jī)制的有效性，對(duì)本文所提方案和基于Solr以及HiBase方案的結(jié)果查詢時(shí)間進(jìn)行對(duì)比實(shí)驗(yàn)。圖7中的橫坐標(biāo)是查詢獲得的結(jié)果集大小，縱坐標(biāo)是結(jié)果查詢時(shí)間Tresult。每組實(shí)驗(yàn)測(cè)試100次并取平均值，同樣使用指數(shù)指標(biāo)?？梢钥闯?，本文方案的結(jié)果查詢性能大大優(yōu)于對(duì)比方案。這是因?yàn)榛赟olr和HiBase方案都需要在第三方平臺(tái)查詢到行鍵集合后，再建立與HBase的連接進(jìn)行批量的結(jié)果查詢，故兩者的結(jié)果查詢時(shí)間相當(dāng)。而在本文中，得益于基于Observer的索引管理機(jī)制，在得到行鍵集合后可以直接查詢對(duì)應(yīng)Region獲得結(jié)果，極大程度地降低了通信開銷。加之基于Endpoint的并行查詢算法在每個(gè)Region中進(jìn)行并行化查詢，本文方案的結(jié)果查詢性能相較于對(duì)比方案隨著結(jié)果量的增加而不斷提升。

圖7 結(jié)果查詢時(shí)間對(duì)比

3.4 整體查詢性能對(duì)比實(shí)驗(yàn)

在對(duì)索引查詢和結(jié)果查詢分別進(jìn)行實(shí)驗(yàn)分析后，對(duì)本文方案、原生HBase、基于Solr以及HiBase方案的整體查詢性能進(jìn)行了對(duì)比實(shí)驗(yàn)。針對(duì)分類索引，對(duì)3種不同條件的查詢分別進(jìn)行100次并取平均值。圖8中的橫坐標(biāo)是HBase的數(shù)據(jù)量，縱坐標(biāo)是整體查詢時(shí)間Ttotal，使用指數(shù)指標(biāo)?？梢钥闯觯疚姆桨傅恼w查詢性能明顯優(yōu)于對(duì)比方案。在數(shù)據(jù)量較少（10萬量級(jí)）的查詢中，方案的查詢性能相較于基于Solr的方案提升了97%，相較于HiBase提升了45%。在數(shù)據(jù)量較大（1 000萬量級(jí)）的查詢中，方案相較于基于Solr的方案查詢性能提升達(dá)3.6倍，相較于HiBase性能提升約1.1倍。不僅如此，本文方案隨著數(shù)據(jù)量的增長(zhǎng)表現(xiàn)出穩(wěn)定的查詢性能，適用于海量數(shù)據(jù)下的實(shí)時(shí)查詢。

圖8 整體查詢時(shí)間對(duì)比

3.5 集群擴(kuò)展實(shí)驗(yàn)

為了驗(yàn)證本文方案的集群擴(kuò)展性能，在千萬數(shù)量級(jí)的數(shù)據(jù)下對(duì)節(jié)點(diǎn)數(shù)量為3、5、7、9個(gè)的集群進(jìn)行了可擴(kuò)展性測(cè)試。圖9中的橫坐標(biāo)是集群的節(jié)點(diǎn)數(shù)量，縱坐標(biāo)是3種查詢平均的整體查詢時(shí)間，每組實(shí)驗(yàn)測(cè)試100次并取平均值?？梢钥闯?，隨著節(jié)點(diǎn)數(shù)量的增長(zhǎng)，整體查詢時(shí)間逐漸降低。這是因?yàn)樗饕樵兒徒Y(jié)果查詢均是在RegionServer中并行執(zhí)行，隨著節(jié)點(diǎn)數(shù)量的增多，RegionServer增加，故整體查詢時(shí)間逐漸降低。

圖9 集群擴(kuò)展查詢時(shí)間

3.6 索引構(gòu)建時(shí)間和空間開銷實(shí)驗(yàn)

二級(jí)索引方案是在數(shù)據(jù)導(dǎo)入階段創(chuàng)建索引的。分別在十萬、百萬、千萬的數(shù)據(jù)集上對(duì)3種不同條件下的查詢建立索引，并測(cè)試本文方案的數(shù)據(jù)導(dǎo)入時(shí)間來衡量索引構(gòu)建時(shí)間開銷。同時(shí)還測(cè)試了原生HBase、基于Solr和HiBase方案的數(shù)據(jù)導(dǎo)入時(shí)間，每組實(shí)驗(yàn)重復(fù)10次取平均值。索引構(gòu)建時(shí)間的實(shí)驗(yàn)結(jié)果如圖10所示。從中可以發(fā)現(xiàn)，原生HBase的導(dǎo)入性能最好，這是由于原生HBase在數(shù)據(jù)導(dǎo)入時(shí)無需構(gòu)建和維護(hù)索引，而其他方案需要基于協(xié)處理器觸發(fā)索引插入操作。隨著數(shù)據(jù)量的增長(zhǎng)，本文方案的索引構(gòu)建性能仍然優(yōu)于對(duì)比方案。這是因?yàn)樗饕迦氩僮魅堪l(fā)生在內(nèi)存中，消耗時(shí)間較少。HiBase方案則需要并行地構(gòu)建索引記錄并插入到索引表中，較為耗時(shí)?；赟olr的方案在對(duì)插入數(shù)據(jù)構(gòu)建索引記錄之后，需要將其發(fā)送至Solr集群并插入到索引表中，故耗時(shí)最長(zhǎng)。實(shí)驗(yàn)結(jié)果表明，本文方案為建立索引所帶來的時(shí)間開銷是可以接受的。

圖10 索引構(gòu)建時(shí)間對(duì)比

空間開銷上，由于基于Solr和HiBase的方案占用的內(nèi)存不是絕對(duì)固定的，依賴于用戶的設(shè)置，故在此不作對(duì)比實(shí)驗(yàn)。對(duì)于本文方案，在千萬數(shù)量級(jí)的數(shù)據(jù)上建立整體的二級(jí)索引（包含關(guān)于行駛方向的位圖索引，關(guān)于車輛id的哈希索引以及關(guān)于速度的BD樹索引），其占用空間的大小約為500 MB，對(duì)于采用廉價(jià)分布式存儲(chǔ)、具有良好存儲(chǔ)空間可擴(kuò)展性的Hadoop和HBase系統(tǒng)來說，本文方案占用內(nèi)存空間以換取更快的查詢性能是可取的。

4 結(jié)論

本文研究并實(shí)現(xiàn)了一種基于協(xié)處理器的HBase分類二級(jí)索引方案。其充分利用協(xié)處理器機(jī)制，在內(nèi)存中管理索引，并將查詢過程并行化，較大程度上提升了查詢效率。同時(shí)，根據(jù)數(shù)據(jù)特征和查詢需求構(gòu)建不同結(jié)構(gòu)的二級(jí)索引，進(jìn)一步平衡了查詢性能和索引性能。實(shí)驗(yàn)結(jié)果表明，本文方案的查詢管理性能優(yōu)于基于Solr和HiBase方案。下一步，針對(duì)海量數(shù)據(jù)下索引空間開銷較大的問題，會(huì)進(jìn)一步研究緩存機(jī)制和替換策略，從而提供更為經(jīng)濟(jì)穩(wěn)定的查詢可選方案。