基于HBASE的时空大数据关联查询优化

徐爱萍 王 波 张 煦

1(武汉大学计算机学院 湖北 武汉 430072)2(湖北省环境监测中心站 湖北 武汉 430079)

基于HBASE的时空大数据关联查询优化

徐爱萍1王 波1张 煦2*

1(武汉大学计算机学院 湖北 武汉 430072)2(湖北省环境监测中心站 湖北 武汉 430079)

随着数字采集和存储技术的快速发展，视频监测系统得到快速普及，以此带来了海量的监测视频数据。与文本数据不同的是，监测数据具有时空特征，如何在规模庞大且动态增长的数据量下进行高效的查询成为许多时空数据应用所关心的问题。针对云存储体系结构中监测视频大数据高效的时空联合查询需求，充分利用时空特征值和属性特征值在应用中的关联关系，以及HBase数据库在海量查询方面的优良性能，提出了基于HBase Bloomfilter的时空大数据多重过滤机制，创新性地利用视频文件特征值之间的依赖与关联关系来安排rowkey索引键。在此基础上设计出两种时空关联查询算法。最后通过实验证明了算法在时空大数据查询方面的可行性、灵活性和高效性，对其他大数据关联查询应用有较好的指导意义。

云存储 大数据 关联查询 时空特征

0 引 言

海量的时空大数据存储与检索的研究尚处于初步阶段，主要局限于空间文本的处理研究方面。其数据存储主要利用传统的空间数据存储系统根据空间数据模型进行数据存储，研究点是采用曲线降维和存储压缩机制将多维空间数据进行降维压缩成文本信息进行存储，以方便HBase进行处理。常用的降维有PCA、Hilbet曲线等降维方法[1]。PCA基于主元分析的特征提取算法，对于样本差别很大的空间样本存在明显的缺陷，匹配精度不够；在数据查询方面，RDBMS采用对一个或者若干个属性建立索引以及优化分页算法来达到性能上的提升。经典的分页算法有ADO Recordset算法、基于TOP的快速查询算法以及Limits算法[2]，这些算法在数据集上进行分组分页式加速，对关系数据库的快速查询起到很好的效果。文献[3]提出了一种基于属性相关性的SPARQL 查询优化方法，文献[4-5]通过优化索引表以及通过持续更新维护元数据对海量数据存储进行查询优化。这些方法通常要耗费大量的资源来维护查询所需要的性能开销，且面对海量的时空大数据查询性能很低[6]。

云计算技术的出现为解决该问题提供了新的思路，特别是开源社区的活跃，Hadoop生态下的HBase、Hive以及MapReduce计算框架等技术的出现为PB级别的数据存储提供支持[7]。本研究以监测视频数据为信息载体，提出了一种基于各组特征值之间依赖关系而进行rowkey排序拼接的构成规则。首先挖掘监测视频中具有时空特征依赖性的关联特征值，并在HBase中建立高效、易扩展的存储访问索引，在此基础上进一步提出了两种基于HBase的时空关联查询算法，最后通过实验验证了本研究的可行性、高效性和可扩展性。

1 基于HBase的监测视频的时空大数据存储设计

1.1 HBase存储模型

HBase是一个面向列的、版本化的、可伸缩的、以键值对形式来存储数据的分布式存储系统。与传统的关系型数据模型不同的是，HBase采用类似于Google的Bigtable存储模型[8]，并支持“大表”的动态扩展，这种Bigtable存储模型可以按如下定义进行形式化描述：

(1)

F→ {Sj，Cj，j=1，2，…，J}

(2)

(3)

其中符号→表示映射关系，超列集合S和列集合C可属于同一层次，F可以同时映射至S、C。HBase将这种存储模型实现为字典式大表，K为大表行健Row Key、F实现为列簇ColumnFamily、S和C组成列成员Famlily:Qualifier。行健、列成员以及时间戳来唯一标识一个cell，时间戳用来区分每个Cell可能出现的多个版本，每个cell中存放着一个无类型的字节码。又由于其底层是一个稀疏的、分布式的、持久化存储的多维度排序Map结构，通常用来处理分布在数千台普通服务器上的PB级的大数据，又由于其优良的并行处理能力和高度可扩展性，本文选择HBase作为时空大数据索引表存储结构。

1.2 基于HBase时空大数据rowkey设计

1.2.1 监测视频时空大数据的关联依赖规则

其中数据记录Recordi与其特征值存在如下关系：

时空特征不依赖业务特征而独立存在，当时空特征T、G确定时：

(1) 任意的camera下必定有连续的case与之对应；

(2) 任意的case下必定有连续的record与之对应；

(3) 当camera、case、record均一定时，则Recordi唯一确定。

我们称视频监测时空大数据的业务特征case、camera、record之间存在相关依赖性，而时空特征Time、Geo与之形成时空关联模式。例如，在某个时间某个街区，监测系统的探头必定监测到某些事件的发生，这个事件必定分布于不同的记录，如果我们确定了探头号、事件号、记录号，也就唯一了一个监测视频记录，反之则不成立。

表1给出了监测视频时空大数据集Records中的信息描述，监控视频的大数据对象相关依赖性特征值由一组关键字成：{Time，Geo ，camera，case，record，filepath}，这组关键字即是满足上述依赖规则的特征值序列，filepath指向上述序列所确定的文件记录在存储服务器中的路径。

表1 监测视频时空大数据Records的表结构

1.2.2 监测视频时空大数据rowkey设计

rowkey=T+Properties+Z-order值

(4)

这样设计rowkey的好处在于：一方面，由于属性特征具有相关依赖性，这样安排rowkey很方便基于rowkey地去批量查询某一时空特征下的连续记录；另一方面，在HBase中，基于rowkey的查询方式比过滤器的查询方式简单，并且指定起始位置的行扫描的IO操作效率比过滤器删选要高效。同时Z-oder降维算法的高效压缩机制使得其索引表能够在保证其查询性能的前提下大大降低数据所需的实际存储空间。

1.3 基于HBase时空大数据列簇设计

在监测视频Record的元信息基础上进行整合，时间、空间特征整合为时空关联特征。为时空关联特征和属性特征建立HBase列簇。为了进一步筛选特征值缺省下满足查询条件的rowkey，方便从时空关联特征和属性特征两个维度数据处理，结合 HBase的过滤器机制，将属性特征和时空关联特征存储到HBase表中并分别建立过滤列簇，用以解决在某特征值缺省情况下限定rowkey筛选的范围。利用这种多重过滤机制加快时空数据的处理、增强查询的灵活性。

1.3.1 时空关联特征列簇设计

时空关联数据模型将数据划分为：矢量数据、时间数据、属性数据以及拓扑数据，结合监测视频数据应用场景涉及到的空间坐标数据、时间数据、业务数据(属性数据)。我们利用HBase存储模型将三类数据依次设计成时间数据列簇、空间矢量列簇。矢量空间点在GeoTool采用二维坐标存储，在HBase中需将矢量空间点横纵坐标解析成字符串类型进行存储；时间数据采用14位时间占位符Time: yyyy-MM-dd hh:mm:进行存储。空间数据和时间数据共同构成时空关联列簇TGeo，TGeo列簇设计如表2所示。各列簇中的属性名称作为HBase的列限定符动态增加，使列簇模式可复用和扩展。

表2 TGeo列簇设计

属性数据是建立在时空数据之上的一组监测视频Record属性特征集，存储在Properties列簇中，存储格式采用普通字符串，列属性名称为事件号、探头号、记录号，各占4位。例如，假设t1时刻在(x1,y1)处的监测站点记录下一段监测视频Record1，则视频处理程序会通过监测视频本体库为Record1进行属性标记，这些标记属性有case1(事件号)、camera1(探头号)、record1(记录号)，并且在记录进行插入时，将文件所在的路径filepath写入到HBase表中。Properties列簇设计如表3所示。

表3 Properties列簇设计

1.3.2 多重过滤键列簇设计

多重过滤机制的过滤列簇用来解决时空关键字查询的，缩小候选键查找范围， HBase单一的行健查询规则无法过滤掉不满足条件的结果集，例如，在片区A(我们这里假设片区A中包含的监测坐标点群为(1,1),(1,2),(1,3))中查找t时刻，(1,1)～(2,2)范围内的所有记录,如果采用HBase提供的基于行健的查询接口scan，查询过程分为两步。首先，根据rowkey构成规则在rowkey中挑选出含纵坐标的行键，得到的(1,1),(1,2),(1,3)中,(1,3)纵坐标不在(1,1)～(2,2)范围内，这个点不应出现在结果中，因此必须设计过滤键在HBase服务器段进行再次过滤。过滤列簇采用HBase的布隆过滤器[10](bloom filter)对查询进行优化，列簇设计如表4所示。过滤列簇的Qualifiler(列限定符)包含：时空点横纵坐标x+y构成的空间过滤键(记作G)，和时间t构成的时空过滤键(记作T)；事件号、探头号、记录号构成的属性过滤键(记作P)；Value存储他们的值。

表4 MutiFilter过滤列簇设计

2 基于HBase的时空大数据联合查询优化策略

在建立上述基于HBase的监测视频时空大数据的存储基础上，利用Rowkey值对海量的大数据进行时空关联的查询。查询要求可分为单记录查询和多记录查，由于HBase提供的行键查询接口即可解决单记录。这里我们主要对连续多记录查询接口进行算法设计，最终问题聚焦在：时空关联的关键字查询(标记为Q(Q.T,Q.G,Q.B)，其中Q.T表示时间范围关键字，Q.G表示空间范围关键字，Q.B表示属性关键字)，找出时空范围(Q.T,Q.S)上所有包含业务关键字Q.B的记录。

为了解决这类查询要求，本文提出了基于多重过滤键的Z曲线时空关联查询算法 ZRMF( Z-order Range with Multi Filter based Algorithm) ，对于给定的一个时空关联查询请求Q(Q.T，Q.G，Q.B)，ZRMF算法主要分为三个步骤:

步骤一 计算出查询空间范围对应的 Z-order 值范围 ZRange;

步骤二 根据Zrange以及计算出rowkey Range;

步骤三 调用 HBase的scan 接口扫描索引表 indexTable多重过滤列簇MutiFilter在 HBase 服务器端过滤掉所有不在Q.T范围内的数据。

具体见算法1。

算法1 ZRMF时空关联查询算法

输入: 时空关联关键字查询Q(Q.T,Q.G,Q.B)，其中，Q.T由给出的时间范围确定，Q.G由左下角顶点坐标 left Low和右上角顶点坐标right High确定，Q.B是业务特征进行字符串拼接组成的集合

输出: 结果集列表RecordList

1. min Z←calculate Min Zorder(left Low )

2. max Z←calculate Max Zorder(right High)

3. Zrange←calculate Zorder Range(min Z,max Z)

4. for Ziin Zrange do

5. for Biin Q.B do

6. rowkeyRange←(Zi+Bi)右移14位

7. Scan scan←rowkeyRange,MutiFilter(T),

Properties:filepath

8. RecodSeti←indexTable.getScanner( scan)

教学过程最优化是把教学过程作为一个系统进行研究，将构成该系统的有机组成部分，即：教学过程中的人(教师和学生)、条件(教学物质条件、卫生条件、道德心理条件)、教学过程结构(教学目的和任务、教学内容、教学方法、教学组织形式、教学结果)及教学实施的基本环节当作整体进行研究[7]。

9. RecordList.add( RecordSeti)

10. end for

11. end for

ZRMF算法对于空间连续性好的情况(Q.G为连续可变范围)有非常好的效果，这是因为，一方面相关依赖值固定的情况下采用行健(rowkey)扫描的方式进行数据查询，复杂度为O(l)，(其中l为region分组大小)；另一方面，对于相关依赖特征值为取值范围的情况，尽可能地利用正则表达式对查询请求进行正则化，得到的正则查询行间依然是以扫描rowkey的方式进行检索，IO效率更高。但是当Q.G空间连续性不好，Zrang中无用的候选行健会更多，特别是当查询空间范围Q.G增大时，无效的Z-order对HBase通信量的占用越大，ZRMF算法效率降低。因此 我们在ZRMF算法基础上提出了基于空间块划分的时空关联查询算法。该算法利用kd树整个查询空间范围划分为更小的空间块，并在该划分块上建立索引范围kdi，查询的时候则将Zrange与kdi求交集，过滤掉无效的Z-order值，以此处理完每个划分块之后形成一个更精准的Zrange,后面的算法过程同ZRMF一样。

具体见算法2。

算法2 kd-ZRMF时空关联查询算法

输入: 时空关联关键字查询Q(Q.T,Q.G,Q.B)，其中 Q.T由给出的时间范围确定 ，Q.G由左下角顶点坐标left Low和右上角顶点坐标right High确定，Q.B是业务特征进行字符串拼接组成的集合

输出: 结果集列表RecordList

2. max Z←calculateMaxZorder(right High)

3. Zrange←calculateZorder Range( minZ,max Z)

4. for kdiin kd-tree do

newZrangei←Zrange ∩kdi

newZrange.add (newZrangei)

5. end for

6. for Zi in newZRange do

7. for Biin Q.B do

8. rowkeyRange←(Zi + Bi)右移14位

9. Scan scan←rowkeyRange,MutiFilter(T),

Properties:filepath

10. RecodSeti←index Table.getScanner( scan)

11. RecordList.add( RecordSeti)

12. end for

13. end for

3 实验分析与评估

3.1 实验环境

本实验采用真实云存储系统，系统架构由两部分组成，第一部分是搭建了12台服务器作为Hadoop集群及其上的HBase集群，其中1个节点作为HMaster，其他11个节点作为RegionServer和ZooKeeper服务器。另一部分是安装了thrift和自主研发的Geao-GIS系统。

3.2 数据导入

本文数据来源于Geao-GIS系统下武汉市视频监测站点空间数据库，它采用shapefile格式的空间数据模型将视频监测点站标记成Symbol点值，横纵坐标采用整型数据存储。我们挑选其中Z值在0～500的symbol点，并将Symbol点的矢量空间数据以及各个Symbol的视频数据元信息加载到HBase中，为方便实验，分时段对数据进行加载，在加载过程中按照rowkey生成规则采用for循环方式对事件号，探头号，记录号进行连续生成。分别生成五张不同数据级别的HBase表，导入的数据量如表5所示。

表5 数据导入情况

3.3 算法实验与分析

在上述数据导入的基础上，我们主要研究大规模数据量下基于HBase的时空大数据联合查询优化算法ZRMF的性能情况。本文将全表扫描的查询标记为QBFT(Query Based On Full Table)；将在Q.T和Q.G上构造索引的查询标记为QBIT(Query Based On Index Table)。分别不同的数据量时对算法进行性能测试，并从属性特征集、时空特征范围两个方面对算法的影响进行了实验分析。

1) 数据量对算法的影响测试

实验在50万条、100万条、200万条、400万条、800万条进行类比，查询条件Q.T：20150307100000，Q.G(1,4)，Q.P(010100～010199)，Q.T缺省，得到的查询响应时间如图1所示。

图1 不同的数据量下的查询响应时间

从图1中我们分析得知，四类算法在数据量不大的时候都能表现较好的查询效率，而伴随着数据量的增长，全表扫描的查询性能对数据量非常敏感，性能降低得严重；适当的索引使得QBIT充分利用HBase级联索引表不断收窄检索空间，由于本实验查询的属性特征值具有连续性，QBIT、ZRFM、kd_ZRMF均采用连续的rowkeyRange读取空间连续的整块数据作为cache，提高了查找效率。所不同的是 QBIT只需一次读取，而ZRMF、kd_ZRMF读取的次数直接取决于属性特征集的大小，时间开销稍大，但是数据量对性能的影响不大。

2) 属性特征集合对算法的影响测试

本实验为避免属性特征连续的影响，采用离散属性特征序列进行算法测试，查询条件Q.T：20150307100000，Q.G：(1.1)～(4.4)，Q.P：{100110，011001，101001，001100，001001})，查找实验结果如图2所示。

从图2中可以看出，对于离散型属性特征值的查找，QBIT基于连续rowkey查询的优势减弱，ZRFM则由于采用基于布隆过滤器的多重过滤机制，RowKey+ColFamily+Qualify的Scan去掉了不存在此Qualify的storefile，而且指明Qualify也能减少流量，因此即便属性特征集增大，其性能仍然比较稳定。同时我们发现kd_ZRMF随着属性特征值集的增加查询响应时间增加较快，且高于ZRMF。这是由于kd_ZRMF基于块划分的机制在保证候选间正确的情况下，其每个属性特征值所包含的候选rowkey较多，增加了HBase的通信开销。

图2 不同的属性集下算法的查询响应时间

3) 时空范围对算法的影响测试

由于QBIT是建立在时空属性上的索引查找，在时空值不确定情况下，无法采用前缀方式进行查询，其查询过程转换为全表扫描，因此本部分实验仅选取ZRMF、kd_ZRMF进行算法实验。查询条件Q.T：20150307100000～20150307110000，Q.P(010100～010199)，空间范围Q.G在各个ZRange段时算法的查询响应时间。实验结果如表6所示。

表6 ZRMF、kd_ZRMF在不同空间范围的查询响应时间

从表6中可以看出，ZRMF 和 kd-ZRMF 的查询响应时间随着查询范围的增大而有所增加，但仍处于可接受范围内。当查询空间范围小于等于 200 时，ZRMF 具有较好的查询性能； 而当查询空间范围超过 200 时，kd-ZRMF 表现出了比 ZRMF 更好的查询性能，并且这种优势随着查询空间范围的增大表现得愈加明显。

从以上三组实验可以看出，通过合理设计表行键、过滤列簇以及查询算法，将HBase 应用于时空大数据数据管理可以提高时空大数据的存储效率。并且通过算法类比，相对于索引查询方式，ZRMF和kd_ZRMF算法在灵活解决时空数据联合联合查询请求的同时，算法性能更为稳定，且能够很好地平衡存储效率和查询性能；而对于非时空特征的查询，ZRMF和kd_ZRMF算法性能仍然不错，但是受离散型属性特征值的数目影响较大。

4 结 语

本文以时空大数据在视频监测的应用作为研究背景，利用具有时空大数据特征的大数据的监测视频作为数据源，巧妙地挖掘出其特征关联关系并设计rowkey来构建候选查询键。同时为提高查询的准确性，利用HBase bloomfiter构造多重过滤键，并根据多种可能的查询需求提出了两种基于HBase的时空大数据查询算法。最后通过实验证明了ZRMF、kd_ZRNF算法在时空联合查询方面算法性能非常好，并且能满足各类查询请求。然而算法在处理属性特征的查询请求时性能尚有提升的空间，今后的工作中我们会对用户的查询请求进行分类，对不同的查询分类动态地调整行健的位置，灵活运用索引表进行辅助查询，用以提高时空关联查询的效率。

[1] 丁琛.基于HBase的空间数据分布式存储和并行查询算法研究[D].南京师范大学,2014.

[2] 樊新华. 关系数据库的查询优化技术[J]. 计算机与数字工程, 2009, 37(12):188-192.

[3] 林子雨, 赖永炫, 林琛,等. 云数据库研究[J]. 软件学报, 2012, 34(5):1148-1166.

[4] 汪璐,程耀东,陈刚等.海量存储系统元数据服务器的设计及性能优化[J].计算机工程,2012,38(2):1-3.

[5] Sun Z, Shen J, Yong J. DeDu: Building a Deduplication Storage System over Cloud Computing[C]// Proc. of the 2011 15th International Conference on Computer Supported Cooperative Work in Design: IEEE 2011,348-355．

[6] Vashishtha H, Stroulia E. Enhancing query support in HBase Via An Extended Coprocessors Framework[C]// European Conference on Towards A Service-Based Internet. Springer-Verlag, 2011:75-87.

[7] Qin X P, Wang H J, Du X Y, et al. Big Data Analysis—Competition and Symbiosis of RDBMS and MapReduce[J]. Journal of Software, 2012, 23(1):32-45.

[8] Xu J W, Liang J L.Research on a Distributed Storage Application with HBase[J].Advanced Materials Research,2013,631:1265-1269.

[9] 张榆, 马友忠, 孟小峰. 一种基于HBase的高效空间关键字查询策略[J]. 小型微型计算机系统, 2012, 33(10):2141-2146.

[10] Dimiduk N, Khurana A. HBase 实战[M]. 北京：人民邮电出版社,2013.

OPTIMIZATION OF SPATIAL AND TEMPORAL BIG DATA ASSOCIATION QUERY BASED ON HBASE

Xu Aiping1Wang Bo1Zhang Xu2*

1(SchoolofComputer,WuhanUniversity,Wuhan430072,Hubei,China)2(EnvironmentalMonitoringCenteofHubeiProvince,Wuhan430079,Hubei,China)

With the rapid development of digital acquisition and storage technology, video surveillance system has been rapidly popularized, which brings a lot of monitoring video data. Different from the text data, the monitoring data has the characteristics of time and space, and how to carry out efficient query under the large-scale and dynamic growth of data becomes a concern of many spatial and temporal data applications. To meet the requirement of space-time joint query for efficient monitoring of large video data in cloud storage architecture, in this paper, we make full use of the relationship between the temporal and spatial eigenvalues and the attribute eigenvalues in the application and the excellent performance of the HBase database in the massive query, propose HBase Bloomfilter’s multi-filtering mechanism of large data in space and time, and make use of the dependency and association between the eigenvalues of video files to arrange rowkey index keys in an innovative manner. On this basis, two kinds of spatiotemporal correlation query algorithms are designed. Finally, the feasibility, flexibility and efficiency of the algorithm are proved by experiments. It is useful for other large data association queries.

Cloud storage Big data Associated query Spatial and temporal characteristics

2016-04-16。国家水体污染控制与治理科技重大专项(2013ZX07503-001);湖北省重大科技创新计划项目(2013AAA020)。徐爱萍，教授，主研领域：云存储，空间分析，自然语言理解。王波，硕士生。张煦，工程师。

TP311

A

10.3969/j.issn.1000-386x.2017.06.008