CCF产学研动态: 京东城市时空数据引擎JUST

时空实验室 2022-04-01

546

摘要

定位技术的普及产生了海量的时空数据，这些时空数据能够用于各种智能城市应用。时空数据具有数据体量大、结构复杂、查询分析独特等特点，对大规模时空数据的管理极具挑战。本文介绍的京东城市时空数据引擎JUST，能够便捷、高效地管理海量的时空数据。

关键字：时空数据管理，时空数据挖掘，分布式计算，城市计算

李瑞远 liruiyuan@whu.edu.cn

CCF数据库专委会执行委员，陕西省计算机学会优博，北京京东智能城市研究院研究员，京东城市时空数据引擎JUST的负责人。主要研究方向为：时空数据管理与挖掘、分布式计算、城市计算。(编者注: 目前作者已在重庆大学任教)

时空数据管理的背景与挑战

随着定位技术的发展，海量的时空数据在源源不断地产生。例如，在京东，每天都有好几万的一线快递员产生上TB的GPS记录；此外，京东商城每天都会产生几千万的订单，每个订单都会关联一个收货地址。许多城市应用都强烈依赖于对时空数据的查询（如时空范围查询或者k邻近查询）和挖掘（如空间聚类或者轨迹地图匹配）。例如，如果一个用户发起了一个派件请求，京东物流将会找到离该用户最近的k个快递员，然后通知一个最合适的快递员上门取件；在我们修复小区路网的工作中[1]，我们首先利用时空范围查询取出目标区域的快递员轨迹，然后通过深度学习模型和轨迹地图匹配等步骤获得最终的结果（如图1(a)所示）；我们还可以利用订单数据来分析一个区域的经济水平或区域功能，这对选址和规划非常有用（如图1(b)所示）。

图1 时空数据的应用场景

为了更好地支持各种复杂的城市应用，需要有一个时空数据管理系统，同时提供高效的时空数据查询和挖掘服务。然而，对时空数据的管理和挖掘极具挑战。首先是数据量大的问题。在大数据时代，时空数据的数据量可能会非常大，从这些海量数据中快速提取出需要的数据本身就比较困难，而很多时空数据挖掘操作是非常耗时的，特别是当数据量特别大的时候，所需的处理时间常常令人难以忍受（例如此前我们对某城市出租车一个月内的轨迹数据进行地图匹配，所花的时间超过了一个星期）。其次，时空数据是连续不断地产生的，这就要求我们的系统能够高效支持数据的插入和更新，同时无需较多的索引维护成本。第三，高维度问题。时空数据至少有三维的信息，即经度、纬度和时间。高维信息意味着高复杂度的查询和挖掘。因此，需要设计有效的时空索引和特殊的框架来高效支持时空查询和挖掘。最后，统一框架的需求。对时空数据的使用方式可以分为两类：时空数据的查询和挖掘。一方面，时空数据查询通常拥有较小的吞吐量和计算开销，但是要求较快的查询响应速度以及较高的并发度。另一方面，时空数据挖掘的吞吐量和计算开销通常很大，但是并发度要求不高。一个同时高效支持时空数据查询和挖掘的统一框架，能够减少开发人员的学习成本，提升城市应用的构建效率。

现有时空数据管理系统的不足

传统关系型数据库的空间扩展，例如Oracle Spatial、MySQL Spatial以及PostGIS，能够高效支持时空数据查询，但是当数据量特别大的时候，它们通常难以奏效。过去十几年，涌现了很多大数据存储和处理的框架，例如Apache Hadoop和ApacheSpark。基于Hadoop的分布式时空数据管理系统[2-5]仍然面临着效率问题，因为Hadoop将它们的中间结果存储到磁盘中，即使对于单个作业，也会触发多次磁盘读写。Spark将数据以RDD（Resilient Distributed Dataset）的形式缓存在内存中，因此相较于Hadoop，它的效率更高。大多数基于Spark的时空数据管理系统[6-11]在内存中构建了很大的空间索引，例如R-tree、KD-tree或者grid索引，因此能够高效支持时空数据管理。然而，这些系统需要先把数据加载到内存，然后构建索引，因此需要内存充足的高性能集群，故它们的扩展性是受限的。第二，当时空查询到来时，它们可能需要扫描很大的时空索引，通常比较耗时。第三，大多数基于Hadoop或者Spark的系统对数据更新不友好，因为它们构建的时空索引包含了不同记录之间的关系，如果有新的数据到来时，它们通常需要调整甚至重建索引，以保持一个良好的查询性能。第四，Hadoop和Spark主要面向于数据处理，因此基于它们构建的时空数据管理系统难以有效地支持高并发查询。

分布式NoSQL（Not Only SQL）数据库，例如HBase能够高效支持百万级别的数据插入和更新。然而，由于缺乏二级索引，这些NoSQL数据库原生不支持时空数据的管理。基于NoSQL，涌现了很多时空数据管理系统[12-16]。例如，开源索引工具GeoMesa[12]能够将多维数据转化成一维数据，因此，它能够基于分布式NoSQL数据库管理大规模的时空数据。然而，这些系统主要面向的是数据存储，它们大多数未提供时空数据处理的方法或者SQL语言，因此，要使用这些系统的门槛较高，因为我们需要深究它们的开发手册，实现我们自己的时空数据分析算法。

JUST的特点

京东智能城市时空数据组实现了第一个完整的时空数据管理系统JUST（JD Urban Spatio-Temporal data engine）[17]，能够便捷、高效地管理海量的时空数据。目前，JUST处在快速迭代中，新的功能和特性在不断地加入。本文基于2021年6月份发版的JUSTV2.1.2，该版本拥有很多显著的特点：

（1）统一的。为了支持快速和高并发的时空数据查询，JUST实现了一个单机版执行引擎；为了支持高效可扩展的时空数据挖掘，JUST无缝集成了一个分布式执行引擎。JUST提供了一套统一的执行接口，并能够智能地为用户选择合适的执行引擎。

（2）高可扩展的。JUST采用HBase作为底层的存储引擎，GeoMesa作为索引工具，Spark作为分布式的执行引擎。因此，JUST能够利用有限的集群资源管理海量的时空数据。

（3）高效的。我们发现原生的GeoMesa提供的索引不大适合时空范围查询，因此，我们设计了两个新的索引，即Z2T和XZ2T[17]，能够极大地提升查询效率。针对一种最通用的时空数据类型——轨迹，我们设计了一种新的存储机制[18][19]，减少了存储开销的同时，加快了查询效率；

（4）便于数据更新。时空信息编码到了HBase的键中，不同记录的键之间没有关系，因此JUST支持新数据的写入和历史数据的更新，而无需牺牲已有的索引性能。

（5）易于使用的。我们设计并实现了一个完整的SQL引擎，预置了很多时空优化规则以及开箱即用的时空分析函数，所有的操作都可以通过一句标准的SQL语句来实现。

JUST整体框架

图2展示了JUSTV2.1.2的整体框架，其中橘色框表示JUST新提出的模块。由图可知，JUST共分成6层：

图2 JUST的整体框架

（1）数据源。当前，JUST能够从以下三类数据源中直接加载时空数据：1）单台机器或者HDFS中的CSV、GPX、KML、GeoJson格式的磁盘文件；2）Apache Hive、Apache HBase以及关系型数据库（如MySQL）的表数据；3）Apache Kafka中的实时数据流。

（2）存储索引层。在这一层中，JUST对加载后的数据构建空间或者时空索引，并对数据进行有效的组织存储。针对GeoMesa本身的Z3和XZ3索引，在支持时空范围查询时比较慢的问题，我们提出了两种新的索引策略Z2T和XZ2T来加速时空范围查询[17]。其中Z2T面向的是点数据的时空索引，XZ2T面向的是线或面数据的时空索引。此外，针对不同的应用场景，我们提出了四种表：1）数据表。数据表存储了真实的用户数据。除了支持通用的数据类型（例如字符型、数值型等）外，我们还支持基本空间数据类型（例如：点、线、面或者它们的混合类型）。我们还设计了多种特殊的时空数据类型，包括轨迹、路段等。特别地，针对轨迹数据，我们提出了一种新的水平存储[18][19]方式，将一条轨迹中的GPS点存储在一起，并采用gzip的方式进行压缩，减小了存储开销，加快了查询效率。2）视图表。为了支持时空数据查询和挖掘，我们首先从磁盘中加载了必要的数据到了内存中。这些数据可能会被进一步分析和处理。为了避免每次分析操作都从磁盘中加载数据，JUST可以将中间结果缓存在内存中，我们称之为视图表。视图表极大地加快了JUST的数据分析效率，实现了“一次加载，多次使用”的目标。3）元数据表。元数据表存储了数据表和视图表的元数据信息，对后面的数据分析和查询优化非常有用。因为元数据不会很大。如ApacheHive一样，JUST的元数据表存储在了MySQL中。4）统计表。统计表记录了每张数据表的时空分布信息，包括落在一个空间范围内、在一段时间范围内产生的记录的最大值、最小值、数据条数、平均值等，当有数据插入或者删除时，会同时更新统计表中的数据。统计表也存在了MySQL中，对查询优化非常有用。元数据表和统计表对于普通用户来说是透明的，因此普通用户无法直接修改它们。

（3）操作层。这一层共有5种类型的操作：1）数据定义操作，能够创建或者删除JUST中的数据表或者视图表；2）数据控制操作，能够管理用户以及他们的权限；3）数据操纵操作，能够删除、添加或者修改JUST中的数据；4）数据查询操作：能够从数据表或者视图表中提取数据；5）数据分析操作，封装了许多时空数据挖掘和处理算法，例如轨迹地图匹配、时空聚类等。

（4）SQL层。这一层构建了两个执行引擎，这两个执行引擎遵循了一套由执行适配器定义的统一的查询接口，因此上层SQL语法是一致的。单机版执行引擎基于Apache Calcite实现的，面向的是时空数据查询处理；分布式版执行引擎与Spark SQL无缝地集成在了一起，面向的是大规模时空数据的挖掘分析。JUST首先将SQL语句解析成抽象语法树，然后验证一些必要的信息，例如表的名字、列的类型或者用户的权限等。逻辑优化器能够根据表的元数据信息和统计信息智能地选择一个开销最小的执行引擎。最后，JUST能够将逻辑计划转化成底层具体的操作。

（5）服务层。为了支持各种各样的城市应用，JUST提供了遵循JDBC标准的多编程语言驱动器，包括Java驱动器和Python驱动器。利用这些驱动器，开发人员能够向JUST的访问服务器提交SQL语句。

（6）应用层。用户能够通过JUST提供的网页门户或者命令行工具来实现对时空数据的管理。此外，开发人员还可以基于JUST提供的驱动器构建他们自己的城市应用。

JUST数据流

图3展示的是JUST的数据流向，共包含3种类型的数据流：通用数据流（黑色实线箭头），单机版数据流（红色虚线箭头）和分布式数据流（蓝色点状箭头）。首先，JUST将时空数据从外部数据源中加载至GeoMesa中（这里我们将GeoMesa及其底层的存储统称为GeoMesa）。然后，GeoMesa将会根据用户的配置，为这些时空数据构建索引。前两步只需要执行一次。之后，数据流将会分成两部分。第一，针对时空数据查询请求，JUST在Calcite中执行时空数据查询操作，然后将查询结果发送至访问服务器中。第二，针对时空数据挖掘请求，JUST利用Spark从GeoMesa中加载必要的数据，然后执行时空挖掘和分析操作。如果最终的结果行数小于一个可配置的参数（例如10000行）时，分析结果将会通过一个内存缓存返回至访问服务器中；否则，为了避免内存溢出，分析结果将会通过多次传输返回至访问服务器中。具体而言，JUST会将最终结果进行切分，存储在HDFS多个文件中。访问服务器将顺序读取这些HDFS文件。

前述的数据分流对用户来说是透明的，用户只需要通过JUST驱动器从访问服务器中读取数据，就像使用普通的数据库游标一样。

图3 JUST的数据流

JUST网页门户界面

图4展示了JUST门户的用户界面，读者可以通过公开链接进行访问体验。用户登录后，将会看到三个面板：表面板、JustSQL面板、结果面板。表面板展示了已有库表，也允许用户对库表进行管理，包括新增库表、删除库表、共享和取消共享、上传数据等。JustSQL面板允许用户输入一条或者多条SQL语句，当点击运行时，SQL语句将会发送到服务端，转化为底层的时空查询或者分析操作。在JustSQL面板，用户也可以指定执行引擎，或者让JUST智能地选择合适的执行引擎。当时空查询和分析操作完成后，执行结果将会展示在结果面板中，结果面板可以以表格、柱状图、折线图或者地图的形式对结果进行展示。图4展示的是执行两个点表的时空kNN连接操作，结果展示方式为表格。

图4 JUST门户的用户界面(https://portal-just.urban-computing.cn/)

JUST的应用案例

JUST作为一个PaaS（Platform as a Service）对外提供服务。基于JUST，已经落地了许多智能城市项目，包括雄安块数据平台、南通市域治理现代化平台、江苏园博园等。本文以南通市域治理现代化平台中的危化品监管应用举例，说明JUST是如何帮助快速构建智能城市应用的。图5展示了危化品监管系统的界面。

图5 基于JUST的危化品监管系统

在2020年6月13日，浙江温岭发生了一场严重的危化品爆炸事故，造成了20多人的死亡，170多人的受伤。因此，对危化品的监管事关人民的生命财产安全，受到了政府部门的极大关注。JUST目前在危化品监管上主要做了两件事情：1）危化品车辆是否按照了报备的路线行驶？因为如果危化品车辆闯入了居民区，会造成严重的安全威胁；2）是否存在非法的化工厂？比如，有些居民可能会将自己的住房腾出来，用来存储、生产化工用品，我们称之为“黑化工”，另外，一些不符合要求的化工厂，被政府勒令关停后，还可能偷偷进行生产。对危化品的监管是非常困难的，以南通为例，危化品监管涉及到6个环节、7个要素，需要9个不同的政府部门协同、12个软件系统的联动，而南通共有2000多家危化品企业、3000多辆危化品车辆、1000多艘船舶，一线的危化品监管人员只有20多人，如果只是通过人工进行排查，是非常困难的。JUST部署到了南通后，很好地解决了上述两个问题。JUST实时接入了危化品车辆的轨迹数据。针对第一个问题，JUST利用预置的轨迹地图匹配算法，一旦发现某辆危化品车辆偏离了原来报备的路线，就会实时拉响警报；同时，利用预置的实时可达区域分析算法[20]，快速分析出这辆危化品车辆在当前交通状况下未来15分钟内能够到达的区域范围，结合路网信息，推荐交警部门设置路障的位置，对该车辆进行拦截，防止其驶入居民区，对社会安全造成威胁。针对第二个问题，我们对危化品车辆的GPS点轨迹信息进行分析，找到它们经常停留的地点，再结合POI分布信息，如果发现某些停留的地点周围没有危化品工厂，或者是已经关停的危化品工厂，那么这些停留的地方很有可能存在非法化工厂。我们把这些位置推荐给监管部门，他们再在实地进行核实。

图6 JUST监测危化品车辆的行驶路线

JUST的学术合作及科研成果

目前，京东智能城市时空数据组与多所国内外顶级高校进行合作，包括新加坡国立大学、美国伍斯特理工学院、香港科技大学、上海交通大学、电子科技大学、西安电子科技大学、西南交通大学等著名高校与JUST团队长期共同培养研究生。JUST的两篇系统论文[17][18]被CCFA类数据库顶级会议ICDE 2021成功接收，一篇系统论文[19]被CCFA类期刊TKDE成功收录。基于JUST系统，共发表了30余篇国内外顶级会议或者期刊论文，申请了30余项发明专利。

总结与展望

本文介绍的京东城市时空数据引擎JUST，具有接口统一、扩展性强、效率高、易用性好等特点，同时有效支持时空数据查询和分析操作，这些操作都可以通过一句简单的SQL语句完成。总而言之，JUST能够便捷、高效地管理海量的时空数据。未来工作中，JUST将会继续推进产学研的合作，在不断打磨产品的同时，落地更多的智能城市应用，为社会创造更多的价值。

参考文献

[1]S. Ruan, C. Long, J. Bao, C. Li, Z. Yu, R. Li, Y. Liang, T. He, and Y. Zheng, “Learning to generate maps from trajectories,” in AAAI, 2020.

[2]L. Alarabi, M. F. Mokbel, and M. Musleh, “St-hadoop: A mapreduce framework for spatio-temporal data,” GeoInformatica, vol. 22, no. 4, pp. 785–813, 2018.

[3]A. Eldawy and M. F. Mokbel, “Spatialhadoop: A mapreduce framework for spatial data,” in ICDE. IEEE, 2015, pp. 1352–1363.

[4]A. Eldawy, L. Alarabi, and M. F. Mokbel, “Spatial partitioning techniques in spatialhadoop,” VLDB, vol. 8, no. 12, pp. 1602–1605, 2015.

[5]A. Aji, F. Wang, H. Vo, R. Lee, Q. Liu, X. Zhang, and J. Saltz, “Hadoop gis: a high performance spatial data warehousing system over mapreduce,” VLDB, vol. 6, no. 11, pp. 1009–1020, 2013.

[6]J. Yu, J. Wu, and M. Sarwat, “A demonstration of geospark: A cluster computing framework for processing big spatial data,” in ICDE. IEEE, 2016, pp. 1410–1413.

[7]J. Yu and J. Wu, “Geospark: A cluster computing framework for processing large-scale spatial data,” in SIGSPATIAL. ACM, 2015, p. 70.

[8]M. Tang, Y. Yu, Q. M. Malluhi, M. Ouzzani, and W. G. Aref, “Locationspark: A distributed in-memory data management system for big spatial data,” VLDB, vol. 9, no. 13, pp. 1565–1568, 2016.

[9]F. Baig, H. Vo, T. Kurc, J. Saltz, and F. Wang, “Sparkgis: Resource aware efficient in-memory spatial query processing,” in SIGSPATIAL. ACM, 2017, p. 28.

[10]S. Hagedorn, P. Gotze, and K.-U. Sattler, “The stark framework for spatio-temporal data analytics on spark,” BTW, 2017.

[11]D. Xie, F. Li, B. Yao, G. Li, L. Zhou, and M. Guo, “Simba: Efficient in-memory spatial analytics,” in SIGMOD. ACM, 2016, pp. 1071–1085.

[12]“Geomesa,” https://www.geomesa.org/, 2021.

[13]S. Nishimura, S. Das, D. Agrawal, and A. El Abbadi, “Md-hbase: A scalable multi-dimensional data infrastructure for location aware services,” in MDM, vol. 1. IEEE, 2011, pp. 7–16.

[14]J. K. Nidzwetzki and R. H. Guting, “Bboxdb-a scalable data store ¨ for multi-dimensional big data,” in CIKM. ACM, 2018, pp. 1867–1870.

[15]N. Du, J. Zhan, M. Zhao, D. Xiao, and Y. Xie, “Spatio-temporal data index model of moving objects on fixed networks using hbase,” in CICT. IEEE, 2015, pp. 247–251.

[16]X. Tang, B. Han, and H. Chen, “A hybrid index for multi-dimensional query in hbase,” in CCIS. IEEE, 2016, pp. 332–336.

[17]Li R, He H, Wang R, et al. Just: Jd urban spatio-temporal data engine[C]//2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020: 1558-1569.

[18]Li R, He H, Wang R, et al. Trajmesa: A distributed nosql storage engine for big trajectory data[C]//2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020: 2002-2005.

[19]Li R, He H, Wang R, et al. TrajMesa: A Distributed NoSQL-Based Trajectory Data Management System[J]. IEEE Transactions on Knowledge and Data Engineering, 2021.

[20]Li R, Bao J, He H, et al. Discovering Real-Time Reachable Area Using Trajectory Connections[C]//International Conference on Database Systems for Advanced Applications. Springer, Cham, 2020: 36-53.

大数据用户分析索引

文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。