基于協(xié)處理器的HBase分類二級索引設計

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

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

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

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

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

1 相關研究

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

圖1 HBase二級索引結(jié)構

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

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

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

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

2.1 整體框架

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

圖2 整體框架

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

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

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

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

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

2.2.1 基于Observer的索引管理機制

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

圖3 索引管理流程框圖

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

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

2.2.2 基于Endpoint的并行查詢算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

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

表1 實驗環(huán)境節(jié)點配置信息表

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

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

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

3.2 索引查詢對比實驗

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

圖6 索引查詢時間對比

3.2.1 位圖索引實驗

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

3.2.2 哈希索引實驗

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

3.2.3 BD樹索引實驗

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

3.3 結(jié)果查詢對比實驗

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

圖7 結(jié)果查詢時間對比

3.4 整體查詢性能對比實驗

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

圖8 整體查詢時間對比

3.5 集群擴展實驗

為了驗證本文方案的集群擴展性能，在千萬數(shù)量級的數(shù)據(jù)下對節(jié)點數(shù)量為3、5、7、9個的集群進行了可擴展性測試。圖9中的橫坐標是集群的節(jié)點數(shù)量，縱坐標是3種查詢平均的整體查詢時間，每組實驗測試100次并取平均值?？梢钥闯?，隨著節(jié)點數(shù)量的增長，整體查詢時間逐漸降低。這是因為索引查詢和結(jié)果查詢均是在RegionServer中并行執(zhí)行，隨著節(jié)點數(shù)量的增多，RegionServer增加，故整體查詢時間逐漸降低。

圖9 集群擴展查詢時間

3.6 索引構建時間和空間開銷實驗

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

圖10 索引構建時間對比

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

4 結(jié)論

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