大规模可扩展的地理图形分析：InfiniteGraph和Uber的六边形层次空间索引

2023-02-28

数据对象数据库

译者 |李睿审校 |孙淑娟许多企业发现了图形数据库在解决连接数据的复杂问题方面提供的巨大价值。在关系数据库关注数据模型中的数据时，它们很难从同一数据模型中的数据项之间的关系中获取价值。而图形数据库旨在从数据模型中的数据和关系中获取价值。当需要捕获和分析的图形数据包含地理元素时会发

译者 | 李睿

审校 | 孙淑娟

许多企业发现了图形数据库在解决连接数据的复杂问题方面提供的巨大价值。在关系数据库关注数据模型中的数据时，它们很难从同一数据模型中的数据项之间的关系中获取价值。而图形数据库旨在从数据模型中的数据和关系中获取价值。

当需要捕获和分析的图形数据包含地理元素时会发生什么？当企业的大部分分析都关注数据模型的“位置”方面时会发生什么情况？

Uber公司工程团队开发了名称为H3的分层六边形索引，作为将世界划分为六边形的模型，并且他们创建了一组用于与这些六边形交互的API。他们没有提供H3 API的数据库或存储模型，但InfiniteGraph可以发挥重要作用。

本文描述了开发人员实现图形数据模型来表示Uber H3索引的方法。这个模型扩展了H3模型，允许开发人员将域数据模型组件与存储在数据库中的H3六边形相关联。

将所有这些结合在一起，为开发人员提供了一组强大的功能，可以根据域模型和底层H3地理模型来存储和查询域数据。通过使用InfiniteGraph作为图形数据库平台，可以在高性能系统和分析中以近乎实时的速度和规模对这些数据执行复杂的查询。InfiniteGraph支持垂直和水平可扩展性，以及通过分布实现的可扩展性。因此，可以轻松地向上和向下扩展应用程序。

统一的地理环境：一个故事

为了更深入地了解其现有运营的业务并帮助他们规划未来，一家全国性零售商从其所有的商店的各种来源收集数据。所有收集的数据都提供了对其业务有直接影响的事物的可见性。

零售商收集以下数据：

购买：

o购买了什么商品

o购买时间

o购买地点

顾客：

o客户住址

o客户的电子邮件、电话号码和购买历史记录

供应链：

o哪些供应商供应哪些商品

o交货延迟

o批发价格波动

运营商店数据：

o劳动力成本

o水电费

o库存损失

天气：

o每日温度

o即将来临的风暴

每个数据项都存储在创建统一地理环境的数字地图上。购买信息与进行购买的商店的地图位置相关联。客户数据与每个客户的住址、邻居和社区相关联。供应链数据与供应商的位置和他们使用的交付路线相关联。运营商店数据与商店的位置相关联。最后，将天气数据应用于与商店、客户和供应链相关的所有区域的地图。

使用图形数据库时，所有这些数据汇集在一起，提供了一个强大的新工具，使零售商能够对客户购买模式和人口统计、复杂的供应链互动以及恶劣天气对销售和供应链绩效的影响进行预测分析。

什么是图形数据库？

从根本上说，图形数据库是将数据表示为节点和边的数据库。节点通常表示域中的数据项（如人物、地点或事物），边表示节点之间的关系。例如，可以将一个人和一个地址表示为节点，然后可以在他们之间创建一条边来表示“LivesAt”关系。

图形数据模型为表示数据提供了极大的灵活性，可以通过在LivesAt边缘包含一个日期范围来扩展Person-LivesAt地址模型，这样就可以表示一个人居住过的所有地方。

什么是InfiniteGraph？

InfiniteGraph是一个面向对象的图形数据库平台。InfiniteGraph使用联合架构来实现大规模的可扩展性。单个InfiniteGraph联合数据库可以分布在65,000台服务器上，理论上可以容纳1.84×1019个对象。

开发人员创建使用InfiniteGraph API库与联合数据库交互的应用程序。InfiniteGraph部署了两个轻量级服务器：一个锁服务器，用于协调所有正在运行的应用程序的锁；一个页面服务器，响应来自客户端应用程序中运行的InfiniteGraph API的页面请求。所有图形处理都发生在客户端应用程序和API中。API用作链接到客户端应用程序的数据库服务器，使其速度非常快。

在许多其他图形数据库产品使用属性模型方法的情况下，InfiniteGraph使用基于模式的方法。InfiniteGraph基于模式的方法要求开发人员在存储任何数据之前，为要存储的数据类型创建模式定义。这提供了许多优点，其中包括支持InfiniteGraph的布局管理功能（PMC）。PMC是一个基于规则的系统，允许开发人员定义规则，规定数据在数据库中的放置方式。PMC规则可以告诉InfiniteGraph，可能是不同类型的两个对象（例如Person和Address）应该放在同一个磁盘页面上，因为它们经常一起使用。

当用户对人员（Person）执行查询时，他们接下来可能会请求相关的地址（Address）对象。如果这两个对象在同一个磁盘页面上，当磁盘页面被读取以响应对人员（对象）的查询时，同一磁盘页面上的相关地址对象将被读入客户端应用程序中的InfiniteGraph页面缓存中。当用户随后请求地址对象时，将不需要进行第二次读取页面，因为带有地址对象的页面已在内存中。

所有这些功能共同创建了一个可大规模扩展的高性能对象图分析平台，客户可以在该平台上构建尖端应用程序。

什么是H3？

H3是Uber的六边形分层空间索引系统。

Uber公司指出，“……我们开发了网格系统，以有效地优化乘车的定价和调度，以可视化和探索空间数据。H3使我们能够分析地理信息以设置动态价格，并在全市范围内做出其他决策。我们使用H3作为整个市场的分析和优化网格系统。H3就是为这一目的而设计的，并引导我们做出一些选择，例如使用六边形层次索引。”

H3六边形地址

H3为每个六边形分配一个唯一的地址。H3地址是形式为“852A1077FFFFF”的十六进制值，它们表示特定的六边形。

该地址允许H3确定：

六边形的分辨率
六边形中心的经纬度
六边形每个角的经纬度
它的父地址（假设它不是分辨率为0的六边形）
它的7个H3的子地址（假设它不是分辨率为15的六边形）

H3地址主要是开发人员与H3索引系统交互的方式。

H3分辨率

H3还引入了分辨率概念，以支持不同尺寸的六边形层次。下表给出了每种解决方案的详细信息。在15个解决方案中，每个六边形都有7个子六边形。每个子六边形约占其父六边形覆盖面积的1/7。在除0以外的所有分辨率下，每个六边形都有一个父六边形。每个父六边形覆盖的面积约为子六边形的7倍。图1显示了分辨率为9的单个六边形，它的七个六边形分辨率为10，这些六边形的子六边形分辨率为11。

图1：H3六边形分辨率

构建H3图数据库

H3 API支持广泛的转换，使H3成为管理地理数据模型的优雅工具。但是，H3不提供存储模型。H3不附带底层数据库。它本质上是一组工具，用于获取有关映射到地球上的六边形的信息。

因为H3提供了有趣的功能，例如根据其纬度/经度计算六边形的地址或给六边形的邻居的地址，所以创建一个H3六边形对象的图形数据库似乎是合理的，其中每个六边形都是一个节点，它与邻居、其父节点（分辨率减1）及其子节点（分辨率加1）边连接。这正是开发人员所要做的。

H3数据的InfiniteGraph模式

六边形类的初始模式非常简单。因此需要地址、分辨率、对父六边形的引用，对子六边形引用的一个列表，以及一个对相邻六边形参考的列表。

这给出以下信息：

这是一个很好的开始，但是为了有用，需要添加更多的信息。首先，为了支持更广泛的地理查询，需要添加字段，为六边形的纬度和经度提供最小值和最大值。最后，想将一些数据与六边形对象相关联，因此需要一个对某种数据对象的引用，现在称之为HexagonData。

这给出以下定义：

这为构建H3图数据库提供了强大的基础。

HexagonData 类

拥有边连接六边形的图形数据库非常棒。它使能够跨连接的六边形执行图形导航查询。但是，除非可以使用与六边形相关联的某种域数据来限定导航查询，否则它并不是很有用。

一种方法是将域数据属性放在Hexagon类定义中。更好的方法是将Hexagon对象与域数据分开。这就是HexagonData类发挥作用的地方。

如下图所示，HexagonData类只有一个属性“itemMap”。itemMap属性是一个NameToReferenceMap，它允许将字符串键映射到将存储实际数据值的DataItem对象的引用。在这种情况下，键本质上是数据字段名称，关联的字段值包含在引用的DataItem对象中。

HexagonData对象用作六边形地图对象和可能与其关联的任何数据之间的间接层次。可以安全地假设六边形对象在其初始创建后不会经常更改。假设可能有大量数据被摄取并与每个六边形相关联，或者更具体地说，与每个HexagonData对象相关联，也可能是安全的。

将六边形对象与HexagonData和DataItem对象分开的另一个优点是对象放置。可以将六边形对象放在联合架构的一个部分，然后将HexagonData和DataItem对象放在联合架构的完全不同的部分。在数百个甚至数千个线程从数据库读取和写入数据库的环境中，一个理想的放置策略将最大限度地减少锁的争用。

DataItem类

DataItem类是实际将值与六边形关联的旅程的最后一站。

这是DataItem类的简化版本：

DataItem类有一个时间戳，用于指示值何时出现，然后有一个strValue String属性用于存储文本数据，还有一个realValue用于存储十进制值。在当前设计中，DataItem对象中没有任何信息可以指示值所代表的内容。该信息源自HexagonData对象中itemMap指向DataItem对象的键。

一图胜千言…

给定一个特定的六边形对象，与其关联的DataItems的“路径”如下所示。

在这个图中，有一些由变量“hex”表示的六边形。它有一个属性“data”，它是对HexagonData对象的引用。该HexagonData对象有一个属性：“itemMap”。itemMap有一个键值对，其键为“Population.density”，该键与对DataItem对象的引用相关联，其中存储了Hexagon的Population.density值hex。同一个HexagonData对象还有一个键“Climate.avgTemp”，它与存储Climate.avgTemp值的DataItem相关联。

图2：DataItems的路径

查询

InfiniteGraph支持几种不同类型的查询，这些查询分为两大类：FROM查询和匹配（MATCH）查询。

（1）FROM查询

FROM查询允许根据特定的类类型和可能的谓词从对象返回数据。例如，以下查询返回所有Hexagon对象的每个属性：

如果只想要所有Hexagon对象的地址属性，可以修改return子句只返回地址：

可以添加一个谓词来缩小结果集。

最后，可以使用点符号返回连接到每个符合WHERE子句的六边形对象的DataItem对象。

（2）匹配查询

匹配查询是可以真正利用图片的强大功能的地方。

一个简单的匹配查询允许找到到1度邻居的所有路径：

图3：1度邻居

如果不想要路径，而是想要out degree=1邻居中的地址，可以通过将返回的内容从“p”修改为“h2.addresses” 来实现。

在这里，为目标六边形和返回的h2.address分配了一个变量h2。这将提供degree=1相邻六边形对象的从0到6个地址的列表。

如果想获得degree=2相邻六边形的地址，只需在查询中间添加另一个边缘节点子句：

图4：2度邻居

（3）查询之间的路径

可以使用匹配查询来查找两个六边形对象之间的路径。在六边形网格系统中，会有很多路径，所以只对两个六边形之间的最短路径感兴趣。需要注意的是，设置希望查询搜索距离的上限也很重要，否则查询可能最终需要很长时间才能运行，因为需要处理大量数据才能找到端点。这是通过设置一个变量但有界的边缘限定符来完成的，例如“-[:neighbors*1..20]->”。“*1..20”表示在进行搜索时从1跳到不超过20跳。

给定两个六边形地址，可以通过将最短运算符合并到匹配查询中来找到它们之间的最短路径，如下所示：