結合HBase的散列概要森林索引方案

馮詩淳,曹 斌,晁德文,林 博,尹建偉

1(浙江大學 計算機科學與技術學院,杭州 310027) 2(浙江工業大學 計算機科學與技術學院,杭州 310023)

1 引 言

時序數據為以時間序列索引的連續數據,隨著計算機應用的普及,時序數據在各個領域也得到了廣泛的應用.

例如隨著金融領域與互聯網的結合越來越緊密,金融領域大量的量化回撤操作對時序數據的聚合操作性能需求越來越大.

例如,對期貨中一個季度時間范圍內的某種商品合約的市價、盤口價格或成交量等進行統計,進行求和或計算最大值等聚合操作.這樣的應用場景在金融量化中出現頻繁,并且由于數據量巨大,如何快速準確地計算t1～t2時間內的金融時序數據的聚合操作結果變得十分重要.以對Au金屬期貨交易數據中一定時間范圍內市價的求和操作為例:

Select SUM(Last Price)From‘Au’WHERE time>t1 AND time

在這樣的應用場景下,必須支持在海量的時序數據中快速取得聚合操作結果.

2 相關研究

HBase*hbase(http://hbase.apache.org/)是以Google的BigTable為原型的一種列式存儲的分布式開源NoSQL數據庫,具有高可靠性、高性能、可伸縮、實時讀寫的特點[1,2].HBase采用列式存儲,每行數據按全局有序Rowkey鍵進行索引,負載均衡性和擴展性很高.HBase集群存儲海量數據有很大優勢,因此HBase適合于時序數據存儲.

HBase中由Hmaster管理分散在每個節點機上的Region2http://zh.hortonworks.com/blog/apache-HBase-region-splitting-and-merging/ https://ikaisays.com/2011/01/25/app-engine-datastore-tip-monotonically-increasing-values-are-bad3opentsdb(http://opentsdb.net/)

Server,每個RegionServer維護多個存儲在該節點的Region,每個Region負責從Start Rowkey～End Rowkey范圍內的一部分數據.

傳統關系型數據庫主要采用物化視圖或概要表的方式達到加速聚合查詢的目的[3-5].物化視圖是對涉及表連接的查詢命令進行預處理,并將結果保存在視圖表中,查詢時直接取出預處理好的結果.概要表則是在寫入數據的同時,計算并保存相應的概要信息,從而發生查詢時,直接從概要表中查詢并返回結果.此類方法提高了查詢效率,但是缺點是增加了數據庫的膨脹率.在NoSQL數據庫中,一些數據庫采用了MapReduce的方式[6]來處理這些聚合操作,或者管道的方式[7].MapReduce和聚合管道的方式都是實時計算的代表.雖然沒有增加數據庫的膨脹率,但查詢過程中產生了大量的磁盤[8]和計算開銷,低效耗時,無法滿足即席查詢的需求.

一些NoSQL數據庫將樹型索引結構融合[9-11],提高了查詢效率,減少了磁盤訪問次數.

概要森林[12]是一種支持NoSQL數據庫聚合操作的索引機制.其基本思想是將概要表和線段樹"Segment Tree"結合起來,在概要表上建立由多棵線段樹構成的線段森林模型,從而避免概要表的全表掃描操作.同時,通過自底向上的方式動態構建線段森林,回避了傳統線段

樹不支持增長的缺點.此外,查詢算法通過計算直接定位索引數據,避免了對線段森林的遞歸遍歷操作,減少了磁盤IO次數.

概要森林在時序數據中k個時間上連續的數據項的統計信息及其時間窗口構成1個概要信息.由數據項產生的概要信息加上特定的標記信息構成線段樹的葉子節點.由兩個葉子節點或兩個中間節點信息匯總加上特定的標記信息構成中間節點.概要森林每個節點保存由建樹開始依次遞增的序號,通過計算序號定位要查詢的樹節點.概要森林為節點產生的概要樹形成的森林.

當HBase的某個Region中存儲的數據量大于一定臨界值,將觸發此Region的分裂,一個現有Region將會根據指定分裂策略被分裂成負責兩段rowkey的新Region.

但當在HBase上處理由時間上連續事件得到的數據時,rowkey中含有事件發生時間.帶來的一個問題2便是HBase對于數據行的不均衡分布,它們被存儲在一個唯一的rowkey區間中(Region).對于單調遞增的時間類型數據,很容易被散列到同一個Region中,這樣它們會被存儲在同一個服務器上,從而所有的訪問和更新操作都會集中到這一臺服務器上,從而在集群中形成一個熱點,從而不能將集群的整體性能發揮出來.

基于上述問題,本文提出一種基于HBase的線段樹散列存儲方案,結合概要森林實現一種基于HBase的散列概要森林索引方案.采用控制線段樹高的方式將時序數據的概要信息存入多棵線段樹,每棵線段樹負責一部分時間范圍,同時設計同一棵線段樹中rowkey具有相同散列碼,HBase中采用特定的分裂策略,實現以每棵樹為單位的散列負載均衡.解決了連續數據分布不均形成的熱點問題.此外通過rowkey設計可利用HBase范圍查詢機制快速查詢同一棵樹中數據,查到同一棵樹中數據緩存在內存中,優化了同一棵樹中多次查詢速度.本文通過與基于數據的直接查詢以及開源時序數據庫Opentsdb3基于數據的查詢的對比,表明基于HBase散列概要森林有效解決熱點問題,并加快了查詢速度.

3 基于HBase散列概要森林構建實現

3.1 數據模型和查詢需求

定義1.一個數據項D(data point)是一個三元組(s,t,v).其中s是數據的索引ID,t是時間戳,s和t構成了全局唯一標識,v是數據數值.形同s的連續時間數據構成了時序數據.

本文要解決的時序數據聚合查詢就是在查詢時間窗口(t1,t2)間的求和、最值、方差等統計信息,本文以求和為例.

3.2 基于HBase的散列概要森林

本節借鑒概要森林以及HBase散列機制,描述基于HBase的散列概要森林的相關概念.

3.2.1 散列概要森林結構

基于HBase的散列概要森林結合概要森林以及HBase散列機制,通過控制每棵線段樹的高度,從而固定線段樹的時間范圍.通過設計節點數據rowkey,rowkey包含每棵樹生成的散列碼,實現存儲負載均衡,以及使同一棵樹的節點的rowkey屬于一個相鄰的范圍,加快HBase范圍查詢效率.

圖1 散列概要森林樹型結構Fig.1 Structure of synopsis forest tree

定義2.線段樹節點存儲該節點范圍的概要信息,通過控制每棵樹的樹高,使一棵線段樹成為包含一個固定時間粒度的時間單元樹(UnitTree).每棵樹的根節點表示這棵樹攜帶的時間范圍t數據的聚合結果,第二層節點攜帶t/2時間范圍的聚合結果,類推每層節點攜帶上一層節點一半的時間范圍的索引數據.通過控制樹高等從而實現包含的固定時間粒度的時間單元樹可以方便用同一個散列字段聚合每棵樹的節點,實現熱點的負載均衡.

定義3.多棵時間單元樹組成散列概要森林,整個概要森4https://HBase.apache.org/devapidocs/org/apache/hadoop/HBase/regionserver/KeyPrefixRegionSplitPolicy.html

林所索引的數據的時間范圍為組成他的時間單元樹所表示的時間范圍之和.

圖1為散列概要森林樹型結構圖,圖中含有兩棵三層時間單元樹,每棵樹包括了時間t的求和聚合結果,每棵樹的根節點表示整個樹所表示的時間范圍t,第二層節點表示t/2時間范圍的求和索引結果,葉子層節點表示t/4時間范圍的數據結果.

3.2.2 HBase散列

每一棵時間單元樹對應一個散列值,依照HBase的region分裂策略4KeyPrefixRegionSplitPolicy,當該region中數據量大小達到一定值進行分裂,分裂后擁有相同rowkey前綴的數據行在同一個region.每個散列字段對應一棵時間單元樹.

定義4.通過對每棵樹的信息進行md5轉碼等處理生成此時間單元樹的對應散列字段(Hash)

Hash=md5(treeInfo+treelowbound)

tree info為數據信息 tree low bound為時間單元樹的起始時間點.

3.2.3 HBase表設計

基于HBase的散列概要森林由tree-hash和tree-node兩個HBase表組成.tree-hash表用于查找時間單元樹的散列字段,tree-node表存儲所有的時間單元樹的葉子節點.

表1 Tree-hash表字段
Table 1 Tree-hash field

RowKeyColumnHashCodeTreeInfo+TreeStartDayTimeTreeHashCodeIron33520160314MIodzKr4Iron33520160315IwCeyMA9

表1為tree-hash表字段,RowKey為單元樹的信息與該單元樹包含時間范圍的起始時間組成,列中保存該單元樹的散列碼.

表2 Tree-node表字段
Table 2 Tree-node field

RowKeyColumnLBoundRBoundLNodeRNodeDatahash08016412100hash1408261hash11291681299

表2為tree-node表字段,RowKey為該樹的散列值+該節點所在樹的層數+該節點包含時間范圍的中間時間點.

Rowkey=TreeHash+NodeLevel+NodeMidTime

表列字段LBound、RBound表示該節點包含時間段的起始時間點和終止時間點;LNode、RNode表示該節點左孩子和右孩子節點包含時間點的中點;Data表示該節點存放的概要數據值.

3.2.4 時間聚合粒度

一棵時間單元樹表示一個單元時間粒度范圍的聚合結果,每棵樹的葉子節點表示最細粒度范圍的聚合概要信息.粒度可根據實際需求調整.

時間單元樹覆蓋時間(TreeBound)計算公式:

TreeBound= (2^(TreeMaxLevel-1))*LeafBound

TreeMaxLevel為樹最大樹高,LeafBound為葉子節表示的時間范圍.

例如一棵時間單元樹時間范圍定為一天,樹高定為9層,葉子節點表示6分鐘的概要信息.所以一棵樹共管轄1536分鐘的聚合數據.實現一棵時間單元樹覆蓋一天的時間范圍.

隨著增大樹的層數以及增加葉子節點管轄的時間范圍,一棵時間單元樹負責的時間范圍增加.

3.3 散列概要森林建樹寫入查詢過程

3.3.1 建樹過程

基于固定時間單元樹的高度和所包含時間范圍,與概要森林的自底向上建樹方式不同,散列概要森林在插入屬于新時間單元內數據時預先建樹,遞歸建樹操作步驟如圖2所示.

輸入：樹信息，樹起始時間范圍輸出：樹散列值1．calculatetreebound2．calculatetreehash；insertintotree?hash；3．從根節點開始遞歸，創建節點createNode＿recursive(rootNode)；4．if(leftBound

圖2 散列概要森林建樹過程
Fig.2 Process of building a tree

圖2為散列概要森林的建樹過程,以每棵單元樹為例,首先先預先確定此單元樹的范圍;然后計算此單元樹的tree hash,并寫入tree hash表中;建樹過程以根節點開始進行遞歸,每次建立一個新的節點,然后遞歸建立此節點的左右孩子節點,當創建的節點超出預先計算的范圍時停止遞歸.

3.3.2 數據插入

時序數據寫入過程,首先通過時間范圍鎖定要插入的時間單元樹,并查詢出tree hash.然后自頂向下沿著線段樹查詢過程找到葉子節點.

經過的每個中間節點,更新該中間節點的概要信息結果.插入過程如圖3所示.

圖3為散列概要森林的數據插入過程,該過程為當一個時序數據數據項寫入散列概要森林時,首先通過數據項的時間在tree-hash表中找到此數據項所在的單元樹的tree hash值,然后在tree-node表中進行遞歸插入;首先根據tree hash值找到所處單元樹的根節點開始遞歸,通過數據項的時間點信息與當前查詢節點的時間比對,當數據項時間小于該節點時間時,繼續遞歸向節點左孩子進行插入,若大于,則向右孩子遞歸插入;直到插入到單元樹的葉子節點為止.

3.3.3 數據查詢

與概要森林不同,散列概要森林由于同一個時間單元樹中的數據的rowkey擁有同樣的散列字段,所以HBase范圍查詢可以快速找出整棵時間單元樹并存入內存中,大大節省對樹進行遞歸后的磁盤IO操作.

查詢(t1,t2)范圍內的聚合結果,分2種情況:1:t1、t2屬于同一個時間單元樹范圍,查詢操作為Query(t1,t2);2:t1、t2不屬于同一個時間單元樹范圍,查詢操作分解為Query(t1,EndUnitTime(t1))、Query(midUnitTime) 、Query((StartUnitTime(t2),t2))

圖3 散列概要森林數據插入過程
Fig.3 Process of inserting into a tree

StartUnitTime(t)與EndUnitTime(t)分別為時間t所處的時間單元的起始與結束時間點.Query(midUnitTime)為對t1與t2所處的時間單元的中間時間單元的根節點的查詢.

輸入：查詢任務范圍輸出：查詢結果1．查找到單元樹根節點2．findResult＿recursive(t1，t2)；//從根節點開始遞歸查詢，查詢任務從(t1，t2)開始3．leftBound=calculateLeftBound(node)；rightBound=calculateRightBound(node)；//解析出該節點的范圍(leftBound，rightBound)以及中間時間點midTime4．ift1==leftBound&&t2==rightBound updateResult()；break；//記錄該節點結果并退出遞歸5．ift1<=midTime&&t2<=midTime，在該節點的左子節點中進行從第2步開始的遞歸操作ift1>=midTime&&t2>=midTime，在該節點的右子節點中進行遞歸6．ifleftBound

圖4 散列概要森林數據查詢過程
Fig.4 Process of find a object

Query(t1,t2)操作為在同一棵時間單元樹中查詢范圍(t1,t2)的聚合操作結果,具體步驟如圖4所示.

圖5所示為范圍查詢流程圖,范圍查詢被分成了3部分,day1、day2～dayN-1、dayN.day1中,虛線為查詢流程,在根節點被分裂成兩部分查詢分別進行,當查詢到葉子節點時,由于粒度比葉子節點更細,所以需要通過該節點的原始數據得到聚合數據.day2～dayN-1由于被查詢范圍完全覆蓋,所以只需要遍歷根節點取出整個時間段的聚合結果.

4 實驗設計與分析

本文使用相同配置HBase集群,配置CPU2.2 GHz,內存8G.本文模擬數據為真實期貨數據,連續時間序列的同一種類期貨市價.數據時間跨度為10天,共200000條數據.形成約10000個概要包,每個概要包數據大小約為普通數據的5倍,即數據庫膨脹率20%,參考比對其他高效索引方案[9-11],以及HBase的索引優化方案[13]等,選用采用類似優化索引思想的通用開源框架opentsdb作為實驗對比對象.

圖5 范圍查詢流程示意圖Fig.5 Process graph of find a object

實驗1.對原始數據進行直接插入建立聚合結果索引.原始HBase方案直接對原始數據進行寫入,Opentsdb開源時序數據庫方案對數據進行了緩存以及字段二級索引等優化.實驗目的:比對三種方案在寫入時的速度,考察基于HBase的散列概要森林方案的寫入與通用框架opentsdb之間的比較.

三種方案分別對數據進行寫入操作,并記錄寫入吞吐量(thoughput).

圖6 寫入數據thoughput對比(條/s)Fig.6 Comparison of write thoughput

從圖6可以看出散列概要森林方案由于有索引以及建樹過程比HBase直接存入原始數據慢,但比opentsdb插入速度快.

從表3可以看出散列概要森林在觸發HBase的region分裂后按散列值分裂為多個region.擁有相同散列值的同一棵樹會分在同一個region中.散列值隨機生成,新建的樹均勻負載地散列在不同的region中,避免了熱點問題.

實驗2.對比散列概要森林、Opentsdb以及原始HBase方案范圍聚合查詢性能.實驗目的:考察在不同時間范圍跨度中,對比三種方案查詢耗時,考察基于HBase的散列概要森林方案與通用框架opentsdb在長時間范圍聚合查詢操作得耗時上的性能優劣對比.

表3 Region分裂后情況
Table 3 Region after spliting

RegionStartRowKeyEndRowKeyregion1IwCeyMA9Jnq+b6DrIron33520160314Jnq+b6DrMIodzKr4Iron33520160315MIodzKr4SYV4i6vo

由圖7可知大跨度時間范圍的聚合查詢操作中,散列概要森林方案表現較好.同時可以看出原始HBase方案在查詢200000條數據的聚合結果時,耗時數十秒,無法滿足快速即席查詢需求.Opentsdb由于緩存以及索引機制速度大大提升.

圖7 范圍查詢耗時比對,單位ms 橫坐標表示數據量條數Fig.7 Comparision of range query performance

散列概要森林方案比Opentsdb查詢速度更快,且隨著查詢范圍增大,查詢耗時增幅較其他方案更緩慢.說明利用HBase的rowkey設計,使用范圍查詢將整棵樹查出放入內存對查詢性能有優化作用,節約了磁盤開銷.

實驗3.

實驗目的:對比散列概要森林以及非散列方案查詢耗時.非散列方案rowkey缺少散列字段,并且查詢搜索線段樹每次遞歸時對HBase進行隨機查詢.同一棵線段樹可能分散在不同的region中.

圖8 散列方案與非散列方案查詢時間對比Fig.8 Comparision of hash schema

從圖8可以看出,散列方案的查詢耗時優于非散列方案,且隨著查詢范圍的增大優勢越明顯.

5 總 結

本文提出的基于HBase的散列概要森林索引方案,能夠支持簡單聚合操作的快速即席查詢,同時解決HBase數據熱點問題.同時在查詢效率上利用HBase的范圍查詢對查詢性能進行優化,節約了磁盤開銷.通過對比實驗可以看出,這種索引機制的效率優于現有的在HBase上的數據庫的索引機制.下一步將繼續研究聚合數據存儲的粒度問題,尋找更優的粒度適配方案,同時研究其他樹型索引在NoSQL數據庫中的應用.

[1] Guo Yan-xia,Yan Jun.Massive data storage mode of study[J].Computer & Digital Engineering,2008,36(11):162-165.

[2] Song Li-hua,Guo Rui,Ren Qiang,et al.Research on key technologies of architecture of cloud computing system in Dongying[J].Computer Applications and Software,2011,28(10):211-212,249.

[3] Goldstein J,Larson P A.Optimizing queries using materialized views:apractical,scalable solution[J].Special Interest Group on Management of Data,2001,30(2):331-342.

[4] Lehner W,Cochrane B,Pirahesh H,et al.Applying mass query optimization to speed up automatic summary table refresh[C].In Proceedings of the International Conference on Data Engineering,Heidelberg,Germany:IEEE Computer Society,2001:1-22.

[5] Chen Y,Chen M,Liu X,et al.MapReduce based aggregate-join query algorithms[J].Journal of Computer Research & Development,2013,50(z1):306-311.

[6] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Operating Systems Design&Implementation,2004,51(1):147-152.

[7] Abramova V,Bernardino J.NoSQL databases:MongoDB vs cassandra[C].Proceedings of the International Conference on Computer Science and Software Engineering,Porto,Portual:ACM,2013:14-22.

[8] Ibrahim S,Jin H,Lu L,et al.Adaptive disk I/O scheduling for MapReduce in virtualized environment[C].IEEE 42nd International Conference on Parallel Processing,Taipei,Taiwan,China:IEEE Computer Society,2011:335-344.

[9] Sfakianakis G,Patlakas I,Ntarmos N,et al.Interval indexing and querying on key-value cloud stores[C].Data Engineering (ICDE),2013 IEEE 29th International Conference on.IEEE,2013:805-816.

[10] Kaplanis A,Kendea M,Sioutas S,et al.HB+ tree:use hadoop and HBase even your data isn't that big[C].Proceedings of the 30th Annual ACM Symposium on Applied Computing,ACM,2015:973-980.

[11] Kang I S,Kim B K,Lee D H.A Read-optimized index structure for distributed log-structured key-value store[C].IEEE 39th Annual Computer Software and Applications Conference (COMPSAC),2015,3:650-651.

[12] Huang Xiang-dong,Zheng Liang-fan,Qiu Ming-ming,et al.Time-series data aggregation index[J].J Tsinghua(Sci & Technol),2016,56(3):3-10.

[13] Shen B,Chao H C,Xu W.Multi-column query method research and optimization on HBase[C].International Conference on Knowledge Management in Organizations,Springer International Publishing,2015:414-421.

附中文參考文獻：

[1] 郭艷霞,顏 軍.海量數據存儲模式的研究[J].計算機與數字工程,2008,36(11):162-165.

[2] 宋麗華,郭 銳,任 強,等.東營云計算系統架構關鍵技術的研究[J].計算機應用與軟件,2011,28(10):211-212,249.

[12] 黃向東,鄭亮帆,邱明明,等.支持時序數據聚合函數的索引 Time-series data aggregation index[J].清華大學學報 (自然科學版),2016,56(3):3-10.