結(jié)合HBase的散列概要森林索引方案

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

1(浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310027) 2(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

1 引 言

時序數(shù)據(jù)為以時間序列索引的連續(xù)數(shù)據(jù),隨著計(jì)算機(jī)應(yīng)用的普及,時序數(shù)據(jù)在各個領(lǐng)域也得到了廣泛的應(yīng)用.

例如隨著金融領(lǐng)域與互聯(lián)網(wǎng)的結(jié)合越來越緊密,金融領(lǐng)域大量的量化回撤操作對時序數(shù)據(jù)的聚合操作性能需求越來越大.

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

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

在這樣的應(yīng)用場景下,必須支持在海量的時序數(shù)據(jù)中快速取得聚合操作結(jié)果.

2 相關(guān)研究

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

HBase中由Hmaster管理分散在每個節(jié)點(diǎn)機(jī)上的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維護(hù)多個存儲在該節(jié)點(diǎn)的Region,每個Region負(fù)責(zé)從Start Rowkey～End Rowkey范圍內(nèi)的一部分?jǐn)?shù)據(jù).

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

一些NoSQL數(shù)據(jù)庫將樹型索引結(jié)構(gòu)融合[9-11],提高了查詢效率,減少了磁盤訪問次數(shù).

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

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

概要森林在時序數(shù)據(jù)中k個時間上連續(xù)的數(shù)據(jù)項(xiàng)的統(tǒng)計(jì)信息及其時間窗口構(gòu)成1個概要信息.由數(shù)據(jù)項(xiàng)產(chǎn)生的概要信息加上特定的標(biāo)記信息構(gòu)成線段樹的葉子節(jié)點(diǎn).由兩個葉子節(jié)點(diǎn)或兩個中間節(jié)點(diǎn)信息匯總加上特定的標(biāo)記信息構(gòu)成中間節(jié)點(diǎn).概要森林每個節(jié)點(diǎn)保存由建樹開始依次遞增的序號,通過計(jì)算序號定位要查詢的樹節(jié)點(diǎn).概要森林為節(jié)點(diǎn)產(chǎn)生的概要樹形成的森林.

當(dāng)HBase的某個Region中存儲的數(shù)據(jù)量大于一定臨界值,將觸發(fā)此Region的分裂,一個現(xiàn)有Region將會根據(jù)指定分裂策略被分裂成負(fù)責(zé)兩段rowkey的新Region.

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

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

3 基于HBase散列概要森林構(gòu)建實(shí)現(xiàn)

3.1 數(shù)據(jù)模型和查詢需求

定義1.一個數(shù)據(jù)項(xiàng)D(data point)是一個三元組(s,t,v).其中s是數(shù)據(jù)的索引ID,t是時間戳,s和t構(gòu)成了全局唯一標(biāo)識,v是數(shù)據(jù)數(shù)值.形同s的連續(xù)時間數(shù)據(jù)構(gòu)成了時序數(shù)據(jù).

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

3.2 基于HBase的散列概要森林

本節(jié)借鑒概要森林以及HBase散列機(jī)制,描述基于HBase的散列概要森林的相關(guān)概念.

3.2.1 散列概要森林結(jié)構(gòu)

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

圖1 散列概要森林樹型結(jié)構(gòu)Fig.1 Structure of synopsis forest tree

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

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

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

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

3.2.2 HBase散列

每一棵時間單元樹對應(yīng)一個散列值,依照HBase的region分裂策略4KeyPrefixRegionSplitPolicy,當(dāng)該region中數(shù)據(jù)量大小達(dá)到一定值進(jìn)行分裂,分裂后擁有相同rowkey前綴的數(shù)據(jù)行在同一個region.每個散列字段對應(yīng)一棵時間單元樹.

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

Hash=md5(treeInfo+treelowbound)

tree info為數(shù)據(jù)信息 tree low bound為時間單元樹的起始時間點(diǎn).

3.2.3 HBase表設(shè)計(jì)

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

表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為該樹的散列值+該節(jié)點(diǎn)所在樹的層數(shù)+該節(jié)點(diǎn)包含時間范圍的中間時間點(diǎn).

Rowkey=TreeHash+NodeLevel+NodeMidTime

表列字段LBound、RBound表示該節(jié)點(diǎn)包含時間段的起始時間點(diǎn)和終止時間點(diǎn);LNode、RNode表示該節(jié)點(diǎn)左孩子和右孩子節(jié)點(diǎn)包含時間點(diǎn)的中點(diǎn);Data表示該節(jié)點(diǎn)存放的概要數(shù)據(jù)值.

3.2.4 時間聚合粒度

一棵時間單元樹表示一個單元時間粒度范圍的聚合結(jié)果,每棵樹的葉子節(jié)點(diǎn)表示最細(xì)粒度范圍的聚合概要信息.粒度可根據(jù)實(shí)際需求調(diào)整.

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

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

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

例如一棵時間單元樹時間范圍定為一天,樹高定為9層,葉子節(jié)點(diǎn)表示6分鐘的概要信息.所以一棵樹共管轄1536分鐘的聚合數(shù)據(jù).實(shí)現(xiàn)一棵時間單元樹覆蓋一天的時間范圍.

隨著增大樹的層數(shù)以及增加葉子節(jié)點(diǎn)管轄的時間范圍,一棵時間單元樹負(fù)責(zé)的時間范圍增加.

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

3.3.1 建樹過程

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

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

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

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

3.3.2 數(shù)據(jù)插入

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

經(jīng)過的每個中間節(jié)點(diǎn),更新該中間節(jié)點(diǎn)的概要信息結(jié)果.插入過程如圖3所示.

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

3.3.3 數(shù)據(jù)查詢

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

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

圖3 散列概要森林?jǐn)?shù)據(jù)插入過程
Fig.3 Process of inserting into a tree

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

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

圖4 散列概要森林?jǐn)?shù)據(jù)查詢過程
Fig.4 Process of find a object

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

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

4 實(shí)驗(yàn)設(shè)計(jì)與分析

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

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

實(shí)驗(yàn)1.對原始數(shù)據(jù)進(jìn)行直接插入建立聚合結(jié)果索引.原始HBase方案直接對原始數(shù)據(jù)進(jìn)行寫入,Opentsdb開源時序數(shù)據(jù)庫方案對數(shù)據(jù)進(jìn)行了緩存以及字段二級索引等優(yōu)化.實(shí)驗(yàn)?zāi)康?比對三種方案在寫入時的速度,考察基于HBase的散列概要森林方案的寫入與通用框架opentsdb之間的比較.

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

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

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

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

實(shí)驗(yàn)2.對比散列概要森林、Opentsdb以及原始HBase方案范圍聚合查詢性能.實(shí)驗(yàn)?zāi)康?考察在不同時間范圍跨度中,對比三種方案查詢耗時,考察基于HBase的散列概要森林方案與通用框架opentsdb在長時間范圍聚合查詢操作得耗時上的性能優(yōu)劣對比.

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

RegionStartRowKeyEndRowKeyregion1IwCeyMA9Jnq+b6DrIron33520160314Jnq+b6DrMIodzKr4Iron33520160315MIodzKr4SYV4i6vo

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

圖7 范圍查詢耗時比對,單位ms 橫坐標(biāo)表示數(shù)據(jù)量條數(shù)Fig.7 Comparision of range query performance

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

實(shí)驗(yàn)3.

實(shí)驗(yàn)?zāi)康?對比散列概要森林以及非散列方案查詢耗時.非散列方案rowkey缺少散列字段,并且查詢搜索線段樹每次遞歸時對HBase進(jìn)行隨機(jī)查詢.同一棵線段樹可能分散在不同的region中.

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

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

5 總 結(jié)

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

[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.

附中文參考文獻(xiàn)：

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

[2] 宋麗華,郭 銳,任 強(qiáng),等.東營云計(jì)算系統(tǒng)架構(gòu)關(guān)鍵技術(shù)的研究[J].計(jì)算機(jī)應(yīng)用與軟件,2011,28(10):211-212,249.

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