基于協處理器的HBase內存索引機制的研究

朱松杰，婁淵勝，葉 楓，，李 凌，陳 勇

1.河海大學 計算機與信息學院，南京211100

2.南京龍淵微電子科技有限公司 博后工作站，南京211106

1 引言

隨著大數據時代的到來，傳統的關系型數據庫難以處理無規范模式的數據集，并且隨著數據集規模的增大，不能提供高效的存儲和查詢服務，也不能滿足系統的新需求。互聯網先驅不得不重新設計數據庫，大數據系統和NoSQL（Not-Only-SQL即非關系型數據庫）越來越多地被開發出來，例如Facebook的Cassandra、Amazon的Dynamo 以及支持高效數據查詢的內存數據存儲系統Redis等[1]。這些數據庫的數據存儲都采用了key-value數據模型，HBase 便是key-value 數據庫中使用最為廣泛的[2]。

在Google 的BigTable 論文的發表后，Cafarella 在Hadoop 上面實現了BigTable 的一個開源版本，被稱為HBase[3]。HBase由多個軟件子系統組成，主要包括客戶端、HMaster、HRegionServer、Zookeeper 等，這些子系統共同組成一個分布式應用系統，它具有開源、分布式、可擴展及面向列存儲的特點，能夠為大數據提供隨機、實時的讀寫訪問功能。如何從海量數據中快速獲得所需數據是使用HBase 等NoSQL 數據庫的一個重要原因，HBase在其主鍵上建立了B+樹索引，在使用主鍵進行查詢時效率很高[4]。但是，在進行非主鍵的條件查詢時，由于缺少主鍵的支撐，HBase 必須進行全表掃描，導致查詢效率低下，無法滿足上述要求。對此，本文在借鑒關系型數據庫解決方案的基礎上，提出了一種基于二級索引的查詢機制，并將索引數據存儲在內存數據庫中，通過內存進行二級索引檢索，進一步提高了對大數據的實時查詢響應。

2 相關工作

HBase 是一個構建在HDFS 之上，用于海量數據存儲分布式列存儲系統[5]。HBase 表的每行都是按照RowKey 的字典序排序存儲，每行數據是按照RowKey區間進行分割存儲成多個Region。HBase 只針對行健的索引，在原生產品中訪問HBase表中的行只能通過行健訪問，行健區間訪問和全表掃描三種。

當前，國內許多使用HBase的企業或者個人都會對其建立索引來提高性能，比較常見的有基于Coprocessor方案，如華為的HIndex方案和Apache Phoenix方案[6]。其支持自定義數據處理邏輯，采用數據“雙寫”（dual-write）策略，在有數據寫入時同時同步到二級索引表。相比于華為的HIndex，Apache Phoenix 的版本迭代情況較好，支持和兼容多個HBase版本，二級索引只是其中一塊功能[6]。同時，二級索引的創建和管理直接有SQL語法的支持，使用簡單。王文賢等人[7]實現了一種基于Solr 的HBase海量數據二級索引方案，該方案主要對華為Hindex進行改進，其基于數據存儲和索引分離的思想，將Solr 檢索與HBase 的大數據存儲結合起來，具有一定的通用性。丁飛等人[4]實現了基于協處理器的HBase區域級服務端區域級第二索引擴展功能，索引存儲格式選HBase自身的數據組織方式，即HFile文件格式。利用HFile高效的IO性能保證索引查詢的效率。周偉等人[8]對HBase分布式二級索引通用方案進行研究，引入分布式索引機制，在SolrCloud中完成對索引的管理，借助協處理器提供的索引功能為HBase記錄創建、存儲索引，其中HBase負責存儲數據，Solr負責索引數據和檢索。

許多研究者已經使用Coprocessor 來構建HBase 二級索引，具體有兩種解決方案：一種是直接存儲到數據庫或文件中實現索引持久化，但這種方法的索引檢索效率較低，另一種是通過構建內存索引，并存儲到特定環境中實現持久化。從開發設計的角度看，把很多對二級索引管理的細節都封裝在的Coprocessor具體實現類里面，這些細節對外面讀寫的人是無感知的，簡化了數據訪問者的使用。雖然具有一定的入侵性，會對Region-Server性能產生一定影響。

對于非Coprocessor方案，不基于Coprocessor開發，而是自行在外部構建和維護索引關系。常見的是采用底層基于Apache Lucene 的Elasticsearch[9]，來構建強大的索引能力、搜索能力，例如支持模糊查詢、全文檢索、組合查詢、排序等。LilyHBase Indexer（也簡稱HBase Indexer）是國外的NGDATA公司開源的基于solr的索引構建工具，特色是其基于HBase 的備份機制，開發了一個叫SEP工具，通過監控HBase的WAL日志（Put/Delete操作），來觸發對solr 集群索引的異步更新，基本對HBase無侵入性[10]。葛微等人[3]提出了名為HiBase的二級索引，它是一種基于分層式索引的設計方案，其將熱點索引進行緩存，并建立高效的緩存替換策略來提高二級索引的查詢速度。Zou 等提出了互補聚簇式索引（Complemental Clustering Index，CCIndex），該方案把數據的詳細信息也存放在索引表中，不需要通過獲取的行鍵再到原表中去查找數據。使用非Coprocessor方案時，如存儲開銷比較大，尤其是當索引列比較多的時候，空間開銷會更大。索引更新代價比較高，會影響系統的吞吐量，索引創建以后，不能夠動態增加或修改。

綜上，本文使用基于觀察者模式的Coprocessor 方法實現二級索引功能，并通過分布式存儲保證二級索引的高可用和高容錯性。提出了基于Coprocessor的索引構建方案，并且針對協處理器索引檢索速度問題，構建了內存索引，意圖是提高索引檢索速度。

3 所提出的索引機制

所提機制的總體結構如圖1所示。其中，索引管理模塊是框架核心，在用戶對數據表進行更新操作時，協處理器Coprocessor 會對這些請求進行攔截，并對索引表進行相應操作，包括插入、刪除和更新索引的元數據（記錄用戶表對應的索引表名稱、索引列等信息）。執行查詢操作時，系統會在緩存中尋找對應索引位置，提高了索引檢索速度，當緩存中的索引更新時，索引管理模塊也會對索引進行更新。索引持久化管理模塊主要對緩存索引進行持久化操作，提供索引表和值表的持久化存儲，HBase為持久化存儲數據提供可擴展性和容錯性。

圖1 系統總體結構圖

3.1 Coprocessor基本概念

由于HBase無法定制服務端邏輯，使得用戶無法在服務端實現自己需求的二級索引方案，HBase在0.92版本中引入了協處理器Coprocessor 機制，它受啟發于Google 的Bigtable 的協處理器，為實現建立二次索引、復雜過濾器（謂詞下推）以及訪問控制等提供了一種很好的解決方案[11]。協處理器是一種服務端組件，類似于輕量級的MapReduce，它的主要思想是通過將集群內的數據移動取代為計算移動來減少計算代價，提高效率。其可理解為服務端的攔截器，可根據需求確定攔截點，再重寫這些攔截點對應的方法。協處理器允許在Region服務器上運行自己的代碼，更準確地說是允許用戶執行Region級的操作，并且可以使用與RDBMS中觸發器（trigger）類似的功能。

Coprocessor可以分為兩大類：Observer Coprocessors（觀察者）和EndPoint Coprocessor（終端）。Observer Coprocessor在一個特定的事件發生前或發生后觸發，其工作過程如圖2所示。

圖2 協處理器工作過程

Observer Coprocessor使用場景如下。

（1）安全性：在執行Get 或Put 操作前，通過preGet或prePut方法檢查是否允許該操作。

（2）引用完整性約束：HBase 并不直接支持關系型數據庫中的引用完整性約束概念，即通常所說的外鍵。但是，可以使用Coprocessor增強這種約束。

（3）二級索引：可以使用Coprocessor 來維持一個二級索引。

Endpoint協處理器類似傳統數據庫中的存儲過程，客戶端可以調用這些Endpoint協處理器執行一段Server端代碼，并將Server 端代碼的結果返回給客戶端進一步處理[12]。利用Coprocessor，用戶可以將代碼部署到HBase Server 端，HBase 將利用底層cluster 的多個節點并發執行。Endpoint 不僅能與客戶端通信，而且能與Observer 進行通信。Observer 可以在回調方法里通知Endpoint，執行一定的事件響應邏輯。兩種處理器的共同協作可以定制功能強大的HBase應用，既可以實現對集群中每個Region數據變更的監控，又可以通過Endpoint將處理結果返回給客戶端。

3.2 Coprocessor二級索引實現

協處理器機制支持用戶根據業務要求，重寫Endpoint和Observer代碼，本文使用Observer協處理器來進行索引的構建。Observer 協處理器類似于關系型數據庫中的觸發器，當對數據庫進行增刪改查操作時，Observer會對這些請求進行攔截，并根據這些請求，實時更新索引表。二級索引的整體架構圖如圖3所示。

圖3 二級索引架構圖

建立的索引結構如圖3 所示，采用了倒排的方法，將數據表的值與主鍵進行交換，原本的值充當主鍵，原本的主鍵放在值的位置，一個最基本的索引表即構建完畢。在未建立索引前，HBase的數據模型可形式化表示為：

其中行健為R，列族為C ，列限定符為CQ，時間戳為T ，值為V 。則二級索引的形式化表示為：Vi→{Ci→{CQi→{Ti|R}}},i=0,1,2,…,n。

框架保證了索引文件和主表在同一個Regionserver上，這樣可以保證在需要使用索引文件時只需與Region-Server建立一次連接就可以完成，提高了速度。在此架構中，用戶首先在配置文件（hbase-site.xml）中設定索引的細節，主服務器從配置文件中獲取需要建立的索引信息，然后在對應的RegionServer中的IndexingCoprocessor中建立索引同時管理二級索引數據。每個節點上都部署了協處理器Coprocessor，部署之后RegionServer端中的每個區域Region 上都會自動創建一個區域協處理RegionCoprocessorHost實例，它的主要功能是用來維護系統級或表級的區域觀察者協處理RegionObserver。每當RegionObserver啟動時會將RegionCoprocessorHost初始化，初始化的過程中，RegionCoprocessorHost 會加載當前服務端所有的RegionObserver。索引管理由擴展的RegionObserver 實例（IndexRegionObserver）完成。IndexRegionObserver主要的擴展接口如表1所示。

表1 IndexRegionObserver主要擴展接口

下面以Put攔截器舉例說明索引表的更新過程：

如圖4所示，在數據表進行Put操作時，數據表會監測插入數據的Rowkey，并由此定位到RegionServer 上的Region，該事件在Put 操作之前被CoprocessorHost攔截，并自動調用此Region 上進行監聽的Observer 的prePut 方法。用戶可以根據自己的需求對這個方法重寫，更新索引。在索引更新完成后，即Put方法執行完成后，Put之后的事件會再次被CoprocessorHost攔截，并調用監聽器Observer 的postPut 方法，同樣，該方法支持用戶的重寫，以實現在Put 操作完成后的索引邏輯。由此可以看出，在Put操作未完成時，監聽器將監聽到這一事件，從而不會調用postPut 方法，索引邏輯將無法完成，保證了索引與原數據表的一致性與事件性，不會出現索引與原數據表無法匹配的情況。

圖4 索引表更新過程

索引的使用：在構建完索引表后，當進行索引查詢時，客戶端需要進行Scan操作，此操作將會被協處理器攔截，將檢索條件截取，并從索引表中找出符合條件的索引項，返回原數據表的Rowkey，數據表根據Rowkey查詢即可。

3.3 內存索引構建

Coprocessor 構建的索引只是在邏輯上實現了索引結構，為了提高檢索Coprocessor 索引速度，需要對Coprocessor 構建的索引進行特定結構設計，內存索引設計即可完成上述目標。內存的索引相較于傳統位于磁盤的索引在設計和架構上都大不相同，基于內存的索引在查詢效率上得到了極大提升。廣泛采用的內存索引有T 樹、基于緩存敏感的CSS/CSB+樹和改進的Hash 索引等[13]。使用了HT 樹構建內存索引，其結構如圖5所示。

圖5 HT樹的結構

如圖5所示，每個葉子節點有4個哈希表，每個哈希表中有3個哈希桶，在使用HT構建內存索引時，需要通過查找算法查找到關鍵字可以插入的哈希表，然后通過計算，找到關鍵字可插入的哈希桶，判斷哈希桶是否已滿，若已滿則分裂該節點，將該關鍵字插入，若未滿則直接插入哈希桶。

內存索引工作流程與一般索引的使用過程有所不同，具體流程如下：

（1）內存索引初始化

當向數據表的構建過程中，需要同步進行內存索引的建立，對外提供檢索服務。在第一次請求索引檢索時，系統會檢查內存索引是否為空，如果為空，則進行索引的初始化操作，建立內存索引。

（2）Put操作過程

Put 操作在HBase 中相當于插入操作，當HBase 執行這個操作時，當前操作發生的Region上的Observer會攔截這個事件，向內存索引中插入一條對應的索引項。

（3）Delete操作過程

和Put 操作相似，當客戶端執行Delete 操作時，HBase將從表中刪除一條記錄，當前操作發生的Region上的Observer會攔截這個事件，在內存索引中刪除一條對應的索引項。

（4）查詢操作過程

該機制中，為了提高查詢效率，盡量將數據處理過程本地化。在協處理器攔截到查詢請求后，將會構建檢索條件，根據條件在內存索引中進行多線程檢索。得到滿足檢索條件的Rowkey 后，返回數據表中查詢原始數據，將結果返回客戶端。在內存中檢索的過程如下：

在進行內存索引查詢時，首先在哈希表中進行查找，定位關鍵字所在桶，繼續在桶中查找，若找到，則指針指向所需記錄。當關鍵字處于內部節點，且它的鍵為K1,K2,…,Kn。如果key ＜K1，則為第一個子節點；如果K1≤key ＜K2，則為第二個子節點。依此類推，在該子節點上遞歸運用查找過程。對于范圍查詢，在實際情況下使用頻率較高，下面給出算法進行說明。

算法1 內存索引查找算法

輸入 查詢范圍[ks,ke]的關鍵字ks,ke。輸出 行鍵集合RQ。

RQ ←[?]// 結果集合設為空

Hs←T .Get Hash（ks）//通過樹形索引查找ks所在的哈希表

He←T .Get Hash（ke）

H ←Hs

while next[H]≠Hsdo

H ←next[H]

RQ ∪all Value[H] //將哈希表中所有值并入結果集合中

end while

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

if key [M]＞ksthen //當遍歷映射的鍵大于范圍開始的關鍵字時

RQ ∪value[M] //將映射的值并入結果集合中

end if

end for

for each map M in Hedo if key [M]＜kethen //當遍歷映射的鍵小于范圍結束的關鍵字時

RQ ∪value[M]

end if

end for

end for

（5）Region分片過程

Region分片主要為了解決在數據表數據增加時，數據行超出預設分片大小的情況。當數據表發生分片過程即Split操作時，對應的內存索引對象也會隨之發生變化[14]。分片時，Region 將會從一個變為兩個，數據表的也會一分為二，分別存于兩個Region 中，此時Observer會監測到Split事件，通知Endpoint重新構建索引表。如圖6所示。

圖6 分片時表變化

數據表從第三項分裂成兩張表，協處理器在原索引表第一行構建索引游標，以此標記向后檢索并在Region的數據表中尋找是否有此條記錄，若存在則保留數據記錄，否則刪除，索引表由此更新完成。內存索引構建在索引表主鍵之上，由于索引主鍵結構的改變，原索引結構需要初始化操作，即步驟一操作。新分片的內存索引對象存儲在新的Region協處理器中。

3.4 內存索引持久化

由于內存索引的維護都由協處理器完成，因此，內存持久化的操作主要為了保證內外存數據的一致性，保證主機斷電時不用重新構建索引，不涉及對索引創建操作。提出了內存索引持久化方法，將建立的內存索引從內存中映射到外存中，用于持久化內存索引的外存區域索引文件由存儲索引信息的索引頭和索引結構組成，索引文件與內存空間采用內存映射技術mmap 保持一致性[15]，映射時會使用地址轉換表，將索引文件中的地址轉換為內存中地址，并一一對應。在對內存索引結構進行修改時，外存索引文件也會自動更新。具體的內存持久化流程如圖7所示。

圖7 內存持久化流程

在上述流程圖中，一個重要的步驟即如何將索引文件映射入內存，索引文件映射入內存后返回的是虛擬地址，索引結構數據沒有進入內存中。為了保證索引結構完全處于內存中，要使用相應的方法將索引結構逐步導入內存，采用了層次遍歷的方法，將索引樹完全遍歷，所有索引結構便處于內存中。

4 實驗與結果分析

4.1 實驗環境與數據

為評估本文提出的基于協處理器的內存索引方案，驗證在構建二級索引時對數據庫寫入性能的影響和在構建了二級索引時對查詢性能有怎樣的提升。同時，實驗同樣基于協處理器但使用內存構建索引（本文方案）與使用solr構建索引在查詢性能上的表現，測試了數據擴展性與集群擴展性。本文在主機上搭建了Hadoop集群、Zookeeper集群和HBase集群，為了與同樣基于協處理器的solr 方案和HiBase 方案進行比較，還搭建了solr集群。實驗環境如表2所示。

表2 實驗環境

實驗所用數據為某河流近3 年各站點水位觀測記錄，屬性包括ID、站點（STCD）、水位（RZ）、地區（RFROM）和時間（TM），共3 000萬條數據。

4.2 插入性能對比

實驗在分布式環境下進行，通過3臺客戶端同時向HBase 表中插入數據，并在3 臺客戶端上統計每500 萬數據的Put 時間，為了保證實驗的準確性，進行30 次重復測試，并將結果累加求得均值。實驗分別測試了無索引、基于solr 的索引、HiBase 和本文提出的基于協處理器與內存的索引方案在相同條件下的Put 時間，結果如圖8所示。

圖8 插入實驗結果

從實驗結果可以看出，Put 效率執行最高的是無索引方案，這是因為在進行Put操作時，無索引方案無需分配資源進行索引的構建，而其他需構建二級索引的方案在將數據放入數據表的同時，會觸發協處理器對Put 操作進行攔截，并調用用戶自定義的方法開始構建二級索引。同時也可得出，在前對500 萬條數據進行Put 操作時，各方案的性能差距較小，但在到達1 000 萬數量級時，無索引的方案明顯優于其他有索引方案。這是因為隨著數據量的增加，索引數據也越來越多，在進行索引插入時也會相較500 萬條記錄時更加困難。HiBase 和本方案都是基于內存索引，在構建內存索引時，需要在協處理器中構建適合內存存儲的索引結構，會消耗額外的計算資源。而基于solr的方案只需要在solr中構建二級索引，不需要在程序中進行額外計算。因此，HiBase和本方案相較基于solr的方案稍有劣勢，但在一個可接受的范圍之內。

4.3 查詢性能對比

實驗在一臺客戶端上進行，數據源仍然是3 000 萬條數據，本次實驗設置了4 個測試用例。詳情如下：查詢河流站點水位值（STCD）在一定范圍內的記錄條數，對水位值范圍更改后即可得到不同的數據量。在水位值屬性上以建立HT 樹內存索引，對水位值進行范圍查詢，圖9 所示橫坐標數據是4 次測試用例所查詢到的所有結果數據量。進行30 次測試，求得各數據庫查詢時間的平均值，結果如圖9所示。

圖9 查詢實驗結果

如圖9所示，無索引的方案與其他有索引的方案性能相比有很大差距，原因是，在原生的數據庫中搜尋一個特定值時，只能通過Scan的方式進行全表的掃描，效率極低，在數據量大時，這種查詢方式可達幾十個小時，無法進行實際使用。同時，可以發現，無論查詢出的結果為多少，無索引的查詢速度都在110 min 左右。排除誤差影響，這是因為，無論結果如何，無索引的方案都要全表掃描，在每次掃描的數據量相同時，查詢時間變化不大。而本方案相比于同樣構建了二級索引的基于solr的方案，性能有較明顯的提升，數據量大時，查詢速度為其3.5 倍左右，與未構建索引的查詢效率相比速度是其50 倍左右，與同樣基于內存索引的HiBase 方案提升了10%左右。本方案不僅在性能上優勢巨大，隨著查詢結果的增大時，查詢所需的時間變化也較小，因為通過內存進行計算，計算速度快，并且都在索引上建立了索引樹結構，在關鍵字搜索時根據樹結構搜索可以快速定位，數據量增大時，對速度影響也較小。

4.4 擴展性實驗

測試了基于協處理器的內存索引在不同規模數據下均勻與非均勻分布數據集查詢性能。均勻分布數據集使用3 000 萬條水文數據，單值查詢河流站點水位值（STCD）為62.20和范圍查詢水位值在60到65之間的記錄條數，結果如圖10所示。

圖10 均勻數據集查詢性能

可以看到，當數據的規模從0 持續變化到3 000 萬級別時，查詢的時間保持了線性增長，這也驗證了基于內存方案在數據的可擴展性方面有著良好的表現，查詢響應時間和結果集大小成正比。因為在查詢響應時間中，主要開銷是對查詢結果集的訪問，在數據集中，數據是符合均勻分布的，隨著數據行總數的增長，查詢結果集也隨之增加，因此，查詢響應時間會與數據行總數大小成正比。

同時，本文選用了UCI數據集Abalone數據集，該數據集符合非均勻分布，數據集可分為6類，并滿足22.69%、27.53%、25.33%、19.46%、2.31%和2.68%的數據分布規律，同時長度數據也滿足非均勻分布性。為了滿足大數據測試要求，將數據量以同等倍數增加，保證數據分布的不變性，查詢數據集中Length 為130 和Length 大于110小于130的數據，兩種查詢結果如圖11所示。

圖11 非均勻數據集查詢性能

由圖11 可以看出，當數據量從0 增加到600 萬時，由于數據的非均勻分布性，并未出現像均勻分布數據集中的線性增長趨勢。這是由于單值查詢和范圍查詢查詢的目標數值普遍分布于數據表的前半段，在查詢開始時查詢所得結果集較多，因此，查詢時間增加較快。查詢數據量增多時，滿足查詢條件的記錄條數減少，查詢增加時間也隨之變少，這也驗證了內存索引方案良好的可擴展性。

同時，在3 000萬條數據的基礎上，通過增加節點的數量進行集群擴展性實驗，由于節點的變化對單值查詢的性能影響可以忽略。因此，實驗只對范圍查詢進行，實驗結果如圖12所示。

圖12 節點數量變化對查詢時間影響

可以看出，隨著節點數量的增加，查詢響應時間逐漸減少。在進行范圍查詢時，會向所有節點發送查詢請求，因此，當節點數量增加時，相應的查詢時間就會變短。

5 結束語

為了提高HBase的查詢性能，本文提出了基于協處理器Coprocessor的方案，實現了內存索引的構建，并將構建的內存索引持久化存儲在外存中，通過實驗達到了預期目標。其核心的思想為：通過協處理器構建內存索引，具體的內存索引結構為HT樹索引，它可以極大提高索引的檢索速度。同時，使數據表與索引文件協同分布，托管于同一臺Region Server，保證了數據表和索引文件同時分布于集群中的同一臺服務器上，在需要用到索引文件時，直接將索引文件映射入內存，節約了時間。

但本文還有一些不足，為了查詢的簡易性，對每一個列值都創建了索引，這導致了構建的索引文件較為龐大，降低了索引效率。同時，在內存中構建索引對象需要付出巨大的內存開銷，當數量過大或索引內容過多時，集群中各服務器的內存會急劇消耗，有可能出現系統癱瘓。

綜上所述，本文提出的索引方案實現了HBase檢索速度的提高，性能和穩定性也得到了充分的保證，但面對大數據環境下各種各樣的挑戰，仍需要更多的努力去完善HBase的大數據處理方案。