一种面向智能交通场景的HBase时空索引设计

摘要：针对HBase无法直接实现海量时空数据查询的问题，结合智能交通的常用场景，提出一种基于原生HBase接口的、结构简单的时空索引设计。首先引入基于时间与空间信息的加盐算法作为索引前缀，以避免产生HBase数据读写热点。然后利用Google S2算法将经纬度信息降维为一维编码，与时间、数据类型标识等字段组合形成时空索引。最后通过实验验证了所提出的HBase时空索引设计在TB级存储场景下多维查询的性能和数据分布。

关键词：智能交通;时空索引;HBase;加盐算法;GoogleS2

中图分类号：TP311.133.1

文献标识码：A

文章编号：1009-3044（2020）04-0163-03

收稿日期：2019-12-05

基金项目：重庆市公安局科技攻关计划项目（项目编号：G2018-15）

作者简介：刘一流（1991—），男，河南许昌人，助理工程师，硕士，主要研究方向为时空大数据挖掘。

Spatio-temporal Index for Intelligent Transportation System Based on HBase

LIU Yi-liu

（Chongqing Municipal Public Security Bureau，Chongqing 401 120，China）

Abstract：Focusing on the issue that HBase couldn ' t execute multiple analysis directly when processing massive traffic data，a spatio-temporal index Based on HBase was proposed to support intelligent transportation applications.Firstly，a salting algorithm with temporal parameter and spatial parameter was introduced to generate rowkey prefix in order to avoid the data workload hot spot.Secondly，the di-mensionality reduction method Based on Google S2 was used to convert two-dimensional spatial position data into one-dimensional code，then the code was combined with elements like temporal dimension，data type and so on to generate the whole spatio-temporal in-dex.Finally，the experimental results show that the proposed HBase spatio-temporal index can effectively improve the traffic data que-ry performance when the data storage size is over TB.

Key words：intelligent transportation;spatio-temporal index;HBase;salting algorithm;Google S2

1 背景

隨着5G等新一代信息技术的崛起，智慧城市在中国经历了井喷式的发展。据政府公开信息统计，仅在2013年至2018，年六年时间内，由各地方政府委托的智慧城市项目的中标数量从12个激增至162个，年复合增长率超过45%。智慧交通作为智慧城市的重要组成部分，可通过对城市交通时空数据进行分析，为公安、公路、交管等部门的决策提供依据，以支撑交通诱导、应急指挥、线路优化等应用。

依托监控、物联网等技术，城市交通所产生的时空数据量级呈爆炸式发展，传统关系型数据库在存储与处理这些数据时显得力不从心。以HBase为代表的分布式NoSQL数据库在海量数据存储场景下具有优异的表现，并能集成MapReduce、Spark等计算框架作为工具对存储的数据进行大规模分析。但HBase 自身也存在种种限制，如只有在基于Rowkey查询时才能获得高性能、只能通过内置Filter执行过滤操作、原生不支持SQL语句等。

目前已有部分将HBase应用于时空数据的研究。时空数据的快速检索查询一般都是通过建立高效的时空索引来实现，常用的时空索引包括R-Trees、Quad-Trees和K-DimensionTreesl[1-4]等结构。但上述时空索引方案在落地过程中，存在结构复杂、数据存储不平衡、对存储组件入侵性大等缺点。本文主要讨论一种基于原生HBase接口的，针对智慧交通特有场景，设计结构简单高效、对组件无侵入的索引方案，以支撑TB级智慧交通时空数据的检索。

2 研究现状

原生的HBase接口仅提供了Get、Scan、Filter等基础查询操作，不支持数据多维查询。随着HBase的大规模应用，其在多维查询方面的限制也日益明显。国内外关于HBase如何支持多维时空索引的研究从未停止过。下面针对主要研究结果做简要介绍：

2.1 二级索引

国内外主要的Paas层厂商在其Hadoop平台中将HBase二级索引作为一种企业增强特性，以弥补HBase在多维查询方面的短板。其思路是通过借助协处理器[5]、Solr[6]、ElastieSearch[7]等组件为所需查询的维度生成二级索引。

以华为的HIdex方案为例，每当插入一条数据时，会通过RegionServer上的协处理器对该数据中需要索引的列生成二级索引。用户在查询索引列数据时，通过调用华为重写的SingleColumnValueFilter等过滤器，会自动查询二级索引，极大的缩短查询时间。

二级索引作为一种通用的多维索引解决方案，其缺点也非常明显，基于协处理器的二级索引在列簇设置TL的场景下会出现索引与原始数据不一致的情况，多列数据做联合索引的场景下查询条件依然受限。基于ElasticSearch和Solr的实现的二级索引方案受搜索引擎组件自身性能的限制。并不适合直接拿来做时空数据检索。

2.2 时空索引

GeoMesal[8]是一款由LocationTech开源的地理大数据处理工具套件，借助HBase、Cassandra、Accumulo等分布式存储，通过基于三阶Z-order填充曲线方法的Z3/XZ3索引，对经度、纬度时间三个维度进行编码，向用户提供大规模时空数据查询能力。该方案对HBase组件的侵入较大，时空数据的写人和读取请求都需通过独立的GeoServer处理，不利于与Mapreduce、Spark等分布式计算引擎进行整合。

文献[9]和文献[10]分别提出了两种基于Geohash编码与时间组合的时空索引结构，这类索引实现简单，对组件无入侵。文献[9]中的索引方案以时间中的年月部分和Geohash前缀组合作为Rowkey，通过列簇和列名区分不同日期的数据。该方案在数据日增量过亿的场景下，单个Rowkey下存储的数据过多，无法获得理想的查询性能。文献[10]中探讨了四种时间与Geohash组合生成Rowkey的方式，并分析了每种组合所适用的场景。但四种方案都使用时间或Geohash字段作为Rowkey前缀，在实践中都会造成HBase读写热点等问题，无法发挥HBase分布式存储的优势。同时，上述两种方案所依赖的Geohash算法在空间填充曲线上存在突变，并且Geohash在選择不同长度的前缀查询时，覆盖范围跳变很大，在实践中很难选择合适的前缀长度。只能用较大范围的前缀覆盖需要查询的区域，对数据再做过滤，直接影响到查询效率。

3 基于HBase的时空数据索引方案

本文在研究各种Geohash编码与时间组合生成时空索引方案的基础上，借鉴其将经纬度编码降维后与时间组合的思路，针对HBase存在读写热点、Geohash覆盖范围跳变等问题做出改进。在HBase原生接口的基础上，设计一种无入侵、结构简单的时空索引。

3.1 索引结构设计

通过对智能交通场景下应用需求进行调研，在时空碰撞、车辆伴随、道路拥堵分析等应用中，一般查询的时间条件跨度为小时级别，常用空间查询条件的覆盖范围多数不超过60000平方米，要求当查询条件均符合上述范围时能实时响应查询请求。同时支持超出上述条件范围的查询请求，以支撑热力图、人流迁徙等应用。

针对上述应用需求，将经纬度通过Google S21[11]算法降维编码生成CellID，并将时间与CllID等信息组合作为HBase Rowkey构建时空索引，具体结构如图1所示，索引由五部分组成。

第一部分是盐值，盐值由时间和CelID值计算得到。首先截取数据中时间的年月日小时（yyMMddhh）部分，CellID以能够覆盖常用查询范围为基准，截取固定长度的前缀。然后将截取后的时间与CellID前缀合并做散列运算，散列运算的返回结果范围控制在0到255之间，放在Rowkey的第一个字节。在HBase建表时，根据存储数据的总量对表格做预分区，预分区数量最高支持256个。时空数据基于其盐值均匀地分布在不同分区中，以解决HBase写热点的问题。

第二部分是时间，时间被截成年月日时（yyMMddhh）和分秒（mmss）两部分，其中yyMMddhh部分用于将数据按小时维度切割，以在查询时间条件为小时级时获得最佳的性能。由于mmss部分拼接在CellID后，所以该部分不能作为Scan操作时的过滤条件，只能在Scan的结果返回后对结果集再做过滤。

第三部分是elID，CllID是基于GoogleS2算法将经纬度映射为投影上的坐标后，通过希尔伯特填充曲线对坐标编码后生成的一个长整形数字。S2算法可以通过两个CellID限定的区间范围表示地图上的一个区域。与Geohash相似的是S2可根据CllID前缀的长度控制其覆盖的范围，但是elllID不同长度的前缀覆盖范围跳变比Geohash更为平缓，同时可以通过调用S2库的getCovering方法计算任意多边形内包含的所有S2块。比Geohash使用更为简洁。

第四部分是数据类型标识，在智慧交通场景下，往往既希望能将不同部门采集的数据整合使用，又希望在需要时单独查询其中的某一种。通过在索引结构中增加数据类型标志字段，缺省情况下可默认查询所有类型的数据，当需要查询某个固定类型的数据时，通过添加FuzzyRowFilter可过滤指定数据类型标识的数据。

第五部分是数据MD5，将例如车牌等信息的MD5值作为时空索引的后缀，既可以避免时间、空间、数据类型标识完全相同的数据在写入时相互覆盖，也可以在时空碰撞等场景通过MD5实现去重。

通过上述五部分组合生成的Rowkey即为时空索引，索引对应的数据主体内容通过ProtoBuf序列化为二进制数组，作为Rowkey对应的内容存人列簇中。

3.2 检索流程设计

该索引设计在时间跨度小于一小时、查询空间条件未超过盐值中CellID截取范围的情况下能够获得最佳检索性能。在上述理想条件下，根据查询时间条件的年月日小时（yyMMddhh）部分和空间条件所对应的CellID值可直接计算出HBaseScan操作的Rowkey范围，再对返回数据中时间的分秒（mmss）部分做过滤，即可获得符合条件的所有结果。但在实际应用中，查询时间条件可能会横跨数天，查询空间条件也可能需要一组Cel-IID才能覆盖。此时上述时空索引设计无法直接获得查询结果，需要对查询条件进行分解。检索流程如图2所示。

对于需要分解的查询请求，首先按小时对查询的时间条件进行分割。然后调用Google S2算法库中的getCovering方法，获取查询区域包含的所有S2块。将分割后的时间和S2块组合为一组请求，并行向HBase发起查询。最后将所有返回结果过滤后执行并集操作，即可获得符合时空检索条件的数据。由于不同请求计算出的盐值不一样，分解后的查询操作会被分发到不同的分区上并行执行，以充分发挥HBase作为分布式存储的优势。

4 实验结果及分析

4.1 实验环境与数据

本文实验的硬件环境为40台至强E5-2620CPU、256CB内存、48TB硬盘配置的服务器。软件环境为Hadoop 2.5.0、HBase 0.98.6、JDK 8、Centos 6操作系统。

实验数据来自某智能交通项目。该项目平均每日时空数据条目增量为百亿级，总计存量数据超过千亿条，除去备份等因素，原始时空数据经Snappy算法压缩后占用存储约60TB。原始数据样例如表1所示。

4.3 实验结果及分析

本文实验的主要目的是测试在不同区域范围、不同时间范围下时空索引的性能表现。同时统计该时空索引下HBase各分区数据分布情况，验证是否存在热点。

4.3.1 固定空间条件的查询测试

模拟针对某商圈车流分析场景，查询空间条件固定为6万平方米的矩形，分别记录查询不同时间条件下返回的数据条数和耗时，形成统计图如图3所示。

可见随着查询时间范围的增加，返回数据条数呈类似线性增长。受HBase拉取数据量增加的影响，查询耗时有所增加。但得益于查询被分割成多个查询请求多线程执行，在查询时间条件超过60分钟的情况下，查询耗时并没有随着时间条件呈线性增加，稳定在3.5秒左右。

4.3.2 固定时间条件的查询测试

随机设定查询时间范围为一小时。分别记录查询不同空间条件下返回的数据条数和耗时，形成统计图如图4所示。

随着空间条件的范围不断扩大，返回数据条数和耗时都有了明显增加。在查询空间条件小于20000平方米的情况下，因查询请求未满足分解条件，只会通过单线程拉取数据，此时从HBase拉取数据的平均速度在每秒25000条左右。当查询空间条件大于20000平方米时，查询会按照空间条件被分解为多个请求并行处理，拉取数据的平均速度增加至每秒85000条。随着查询的空间条件进-步增加，分解后的请求并行数会随之增加，进而提升每秒从HBase拉取数据的速度，减少查询耗时。

4.3.3 存量数据的分区分布统计

根据HBase在HDFS存储路径下各个分区所对应的文件大小。形成统计图如下图5所示。在建表时预置了256个分区，最大分区249GB，最小分区为226GB。得益于加盐算法的调优，从分布看，绝大多数分区的大小控制在230GB到245GB之间。没有出现数据热点的情况。

5 结束语

本文针对基于HBase存储的海量时空数据多维查询场景，结合智能交通应用的查询特点，在现有研究的基础上提出了一种基于HBase原生接口的、结构简单的时空索引结构。利用加盐算法解决现有索引结构的HBase数据热点问题，利用GoogleS2算法替换Geohash算法以解决查询层级间覆盖范围跳变的问题。经实验验证，该时空索引结构设计在TB级存储场景下获得了较好的查询检索性能，能够满足智能交通场景下时空碰撞、热力图、车辆伴随、道路拥堵分析等应用的需求。但是需要：注意的是，该时空索引中的加盐算法针对应用场景在时间条件与空间条件上做了妥协。在实践中需根据常用时空条件的范围对加盐算法的参数进行调优，以获得最佳查询性能。

参考文献：

[1]Kothuri R K V，Ravada S，Abugov D.Quadtree and R-tree in-

dexes in oracle spatial[C]/Proceedings of the 2002 ACM SIG-MOD international conference on Management of data一SIG-MOD '02，June 3-6，2002.Madison，Wisconsin.New York，USA：ACM Press，2002.

[2]Gong J，Ke S，Zhu Q，et al.An efficient trajectory data index

integrating R-tree，hash and B*-tree[J].Acta Geodaetica et Cartographica Sinica，2015，44（5）：570-577.

[3]叶小平，郭欢，汤庸，等.基于相点分析的移动数据索引技术[J].计算机学报，2011，34（）：256-274.

[4]尹章才，李霖，王琤.基于HR-树扩展的时空索引机制研究[J].武汉大学学报：信息科学版，2007，32（12）：1131-1134.

[5]丁飞，陈长松，张涛，等.基于协处理器的HBase区域级第二索引研究与实现[J].计算机应用，2014（z1）：181-185.

[6]王文贤，陈兴蜀，王海舟，等.一种基于Solr的HBase海量数据二级索引方案[].信息网络安全，2017（8）：39-44.

[7]邹敏昊.基于Lucene的HBase全文检索功能的设计与实现[D].南京：南京大学，2013.

[8]James N Hughes，Andrew Annex，Christopher N.Eichelberger，Anthony Fox，Andrew Hulbert，Michael Ronquest.GeoMesa：a distributed architecture for spatio-temporal fusion[P].Defense + Security Symposium，2015.

[9]Fox A，Eichelberger C，Hughes J，et al.Spatio-temporal index-

ing in non-relational distributed databases[C]//2013 IEEE International Conference on Big Data，October 6-9，2013.Sili-con Valley，CA，USA.EEE，2013：.

[10]房俊，李冬，郭会云，等.面向海量交通数据的HBase时空索引[J].计算机应用，2017，37（2）：311-315.

[11].Google.S2 Geometry[EB/OL].（2019-12-03）.http：//s2geome-try.io.

[通聯编辑：谢媛媛]