智能瓷砖网格：针对非均匀地理数据优化FlightAware地图

‍Philip Clifton是一名高级软件工程师和团队负责人，负责指导FlightAware网络技术的整体实现。

对于FlightAware的许多用户来说，网站上最明显和最直观的体验之一是地图，这些地图以各种形式描绘了航班数据-个别航班、往返机场的交通情况和航空公司机队。然而，也许最明显的应用程序是FlightAware实时地图-这是一款试图描绘世界各地所有正在飞行的飞机的产品。实现此地图功能面临重大挑战-任何给定时间都可能有超过10,000架飞机在途中，需要获取、处理、传输到客户端浏览器并呈现大量数据。这些步骤中的每一个都需要迅速而有效地工作-毕竟，如果用户必须等待10秒以上才能真正加载描述，即使是最引人注目的地图描述也会失去一些影响！

在我们进入这些挑战的核心之前，我们将简要讨论一些映射概念。多亏了Google Maps等工具，基于Web的地图产品如今无处不在，而且随着它们的流行，地图的工作方式也出现了大量的标准化。与此讨论特别相关的是地图如何使用磁贴来提供可靠的用户体验。

当我们谈论“平铺”时，我们真正谈论的是将地图的数据或图像分解成一小块一口大小的小块。让我们以FlightAware的经典蓝色基础层为例。虽然我们当然有能力将所有内容呈现为单个大图像，但实际上我们将其分解为单独的小图像。通过这样做，当用户查看地球的一小部分时，我们可以只加载地图视口中可见内容所需的瓦片。这反过来又节省了不必要的工作和数据传输-即加载用户无法查看的图像。

对于我们在FlightAware地图上使用分片的大多数情况，我们使用三维坐标系，它根据分片的地理位置(X/Y坐标，对应于经度和纬度)及其缩放级别(Z“坐标”)来识别分片。第三个缩放维度很重要，因为它允许我们根据当前的缩放级别定制瓷砖上所描绘的内容。当用户近距离放大某个区域时，我们希望显示大量细节-次要道路、机场跑道等-但如果同一用户缩小以查看整个美国，那么在该级别描绘每一条次要道路和跑道都会严重扰乱地图！

然而，这个三维系统有一个相关的结果：可能的XYZ组合的数量以惊人的速度增长。每增加一个整数的缩放级别，我们就会使地图的比例加倍。也就是说，如果一英里的距离在屏幕上占用了10个像素，那么在下一个变焦级别上，它将占用20个像素。这样做的结果是，给定任意视口大小，增加一个缩放意味着我们将该视口中描绘的地理区域减少四倍。

同时，每个平铺图像总是一个恒定的像素大小，因此扩展起来，单个平铺也只覆盖下一个较低缩放级别的地理区域的1/4。因此，每次我们将缩放级别增加一个整数，我们就需要四倍多的平铺来表示整个世界。在一个典型的缩放级别范围内(比如1-20)外推这一点，可能会有数十亿个可能的平铺。

既然我们已经讨论了平铺策略，让我们继续讨论我们可以在这些平铺中提供哪些类型的数据。与图像文件非常相似，平铺有两种一般形式：光栅和矢量。可以根据原始地理数据转换成(希望)最终用户在视觉上满意的东西的点来考虑这两者之间的界限。

栅格瓷砖在服务器端渲染为常见的图像格式：JPG、PNG等。瓷砖像任何其他图像一样向下传送到浏览器，在浏览器中，浏览器内的地图软件将其与其他瓷砖放在适当的位置。

但是，矢量平铺以GeoJSON等格式作为简单的原始数据传递给浏览器。然后，制图软件负责创建该数据的可视化，将数据所描述的要素放置在地图上的适当位置，并使用样式规则来控制要素的外观。

查看FlightAware实时地图时，可以看到这两种类型的切片的示例。经典的蓝色基层瓷砖是光栅图像，而飞机则被描述为矢量特征。本质上，客户端接收一个非常长的点列表(每架飞机的位置)以及用于决定如何描述飞机的其他元数据。飞机类型(例如，波音737)确定使用什么图标，飞机的当前航向确定其指向的位置，其他飞行数据(如高度和地速)用于在地图上显示飞机图标旁边的信息块。

将其付诸实践：实时地图的矢量数据(“旧”方式)。

当实时地图第一次被概念化时，获取数据的方法很简单：客户端地图配置了一个矢量层(即用矢量要素填充的图层)，该图层利用了前面概述的XYZ平铺方案。数据的检索由Ajax端点处理，该端点接受XYZ坐标作为参数。此端点中的逻辑负责将这些坐标转换为纬度/经度边界框，该框表示平铺块的地理边界，而该边界框又用于检索该框内的所有当前飞机位置。

这种方法的一个主要优点是实现起来很简单。我们使用的客户端地图库OpenLayers为发出此类请求提供了非常健壮的内置类；因此，客户端代码很简单(本质上降低到配置级别)，服务器端代码也同样简单。简而言之，这种方法很容易付诸实践-而且奏效了。

然而，这种方法也有一些明显的缺点。正如我们已经概述的，XYZ平铺坐标系的本质是，每个缩放级别都有一组完全唯一的平铺，这种缩放级别的专一性对于在不同缩放级别提供不同级别的数据细节非常有用。在这种情况下，我们根本没有利用这种特定的潜力-每个平铺请求只相当于“归还这个矩形区域中的所有飞机”。

结果，我们确实在做多余的工作。想象一下，如果用户允许所有飞机以例如3级的缩放级别加载，然后放大地图。因为这意味着新的地图视口比以前的地理区域更小，而且我们已经在该更大的地理区域加载了所有已知的飞机，所以客户端已经有了缩放后显示所需的所有数据-但是平铺实现要求地图上的所有飞机都从白板上重新加载！

尽管如此，它还是奏效了，多年来一直为FlightAware提供了一个很好的展示产品-直到头寸数据的增加开始将缺点变成实际问题。

作为性能难题的最后一块，让我们简要讨论FlightAware如何存储和检索航班的位置和轨迹。虽然我们使用PostgreSQL作为我们的主要关系数据库引擎，但是我们接收的大量位置数据使我们无法将这些数据存储在Postgres中。取而代之的是，我们对途中的航班使用单独的存储系统，从而允许更好的更新和检索性能。这个系统的第一次迭代是Birdseye，这是一个建立在Speedtables之上的内存位置数据库。Birdseye为我们服务了很多年，直到2018年，它被Popye取代，后者使用SQLite作为基础，而不是Speedtable。

这两者都有类似的性能问题，尽管这种担忧在Birdseye中更为普遍。具体地说，对于边界框搜索用例，检索一组位置所需的时间与在结果集中找到的匹配位置的数量大致成正比。例如，一个包含1,000个飞机位置的包围盒的取回时间大约是一个包含100个位置的包围盒的10倍。

人们可能会忍不住认为这个问题只适用于大小差异很大的盒子(也就是瓷砖)，但事实并非如此。毕竟，在途中的飞机并不是通过任何想象力均匀地分布在全球各地的。为了说明这一点，让我们看看覆盖了适用的XYZ平铺网格的样本实时地图：

现在，想象一下在地图客户端中加载北大西洋和南大西洋瓷砖(分别为2，1，-2和2，1，-3)。南大西洋的瓷砖加载时间不到一秒，而北美的瓷砖可能需要几秒钟的时间。在最终用户看来，结果看起来介于不太好和彻底崩溃之间。对于我们的飞行数据的旗舰可视化来说，这肯定是一个糟糕的外观。

减少这种差异影响的传统方法是通过战略缓存，但在这里，我们对切片网格的选择再次出现问题：正如我们所讨论的，可能有数十亿个不同的切片，这意味着在任何特定时间缓存任何特定切片的可能性都很小。可能的分片差异太大，缓存无法发挥作用。

我们现在已经看到了几年前实时地图的状态：客户端加载缓慢、零散，对数据端点的冗余调用给我们的服务带来了不必要的额外负载，并且缓存大多是无效的。显然，这是一种需要新的解决方案的情况，我们决定的方向是放弃XYZ，转而采用定制的瓷砖网格系统。

保持每个瓷砖中的飞机数量相对均匀，从而允许所有瓷砖具有相对均匀的加载时间。

限制可能的分片数量，以允许更多改进的缓存共享，同时还保持每个分片的飞机数量足够低，以使缓存未命中负载保持可接受的较短时间。

我们决定探索的解决方案是基于对飞行位置数据的分析生成一个平铺网格。这个想法是在某个时间点收集所有已知的飞行位置，然后将整个数据集划分为平铺，这样每个平铺包含几乎相同且可管理的飞机数量。做这个分析对现场来说太昂贵了，这意味着它必须是一项离线工作。另一个要考虑的因素是，飞机的地理分布在一天中的不同时间会有很大的不同；当世界的一半是完全清醒的，另一半是睡眠的。因此，一个为美国中午时间优化的瓷砖网格在12小时后将会非常糟糕，那时飞机的密度将有利于地球的另一边。因此，此平铺网格需要全天定期重新生成。

在考虑了几个关于如何执行必要分析的想法之后，我们确定了一个相当基本的迭代方法，本质上是一个试错过程。其基本思想是取一大块包含一系列点的矩形区域，然后将其分割，直到达到所需的点密度。点的不均匀分布意味着这些较小的矩形必然在大小上变化很大。

这个想法的第一次迭代把“分裂”这个词从字面上理解为“分裂”。迭代过程如下：

给定一个任意矩形，尝试在其中点处拆分。决定是垂直还是水平拆分矩形只是基于哪个维度更宽：高度还是宽度。

在此初始拆分之后，计算拆分点每一侧的点数。

按照与计数不平衡成比例的数量，向较大点填充的方向移动拆分点。

在实践中，“相等”的定义有点模糊，因为实际上可能无法做到完美-例如，原始矩形可能包含奇数个点。

递归重复此拆分过程，直到达到每个平铺所需的点数。

虽然执行矩形拆分的基本方法如上所述，但此过程有一个主要缺点-具体地说，因为所有拆分操作都涉及将一个矩形拆分为两个，所以我们仅限于最终的平铺计数是2的幂：一个矩形变成两个，再变成四个，然后是八个、十六个、三十二个，依此类推。

回想起我们的目标之一是仔细优化瓷砖总数和每块瓷砖的飞机数量，这个结果是有问题的。使用这种方法，我们只能非常粗略地控制最终结果。假设我们有一个包含4,000个点的集合，并且我们希望每个平铺以400个点为目标-使用此方法，递归如下所示：

16块瓷砖=每块瓷砖250架飞机；现在我们已经大大超过了我们的密度目标。

显然，如果我们想要这个分析实现我们的目标，我们需要对其进行一些改进。

要做到这一点，最明显的方法是找到一种更灵活的方式来执行瓦片拆分。在此之前，我们知道的唯一一种分割方法是均匀分割：取一组点，将其分割成两个相等的较小的种群。

做出这一改变的关键是一种简单而有力的思维重组：我们以前的方法不是认为“将这个群体一分为二”，我们可以将操作重新表述为“将这个群体分成两个群体，两个新群体之间的比例是1：1。”通过这样做，并通过调整分裂逻辑来匹配，我们打开了能够将人口分裂成任意比例的大门。反过来，这又允许将一个矩形拆分成相等数量的小矩形；例如，要将单个矩形拆分成三个小矩形，我们可以拆分原始矩形并以1：2的比例为目标；然后我们将以1：1的比例再次拆分较大的矩形，从而得到三个具有“相等”人口的矩形。

尽管如此，我们的工作算法只完成了一半，因为我们必须弄清楚如何使用这种新的任意比率能力。以前，递归拆分的结束状态很容易定义：每次拆分一组矩形时，我们都会检查瓷砖密度，看看它是否足够低；如果不够低，则再次拆分所有矩形(将瓷砖数量加倍)，然后再次检查。一旦瓷砖密度降到我们的门槛以下，我们就可以停止分裂。

这种逐步递归不适用于任意拆分。回到我们将一个矩形拆分成三个较小的矩形的示例，在拆分之前，我们必须知道应该得到多少个矩形。这就引出了进行任意拆分所必需的第二个基本重构：不是使用瓷砖密度作为开始度量并递归拆分，直到达到该目标，而是必须在开始之前决定我们需要多少瓷砖，并递归拆分，直到我们达到这个数字。当然，计算出瓷砖数量很简单：只需将飞机总数除以所需的瓷砖密度，四舍五入到下一个整数。

与所有递归代码一样，执行这种拆分的递归代码既令人难以置信，又非常简单。

确定所需的平铺计数后，我们调用一个函数(SPLIT_RECT_TO_COUNT)，该函数的唯一目的是将一个矩形分割成任意数量的小矩形(例如：“将整个世界分割成33个矩形”)；从那里开始，逻辑如下所示：

通过将请求的计数除以2，然后使用结果数字的下限和上限来确定拆分比率，从而确定第一次拆分操作的比率。(例如33/2=16.5=>；16/17比率)。

调用第二个函数(Split_Rect)，其唯一任务是使用请求的比率将人口分割为两个矩形。此函数返回两个矩形及其点填充的列表，顺序与请求的比率相同。(例如，16/17 SPLIT首先返回较小的矩形，然后返回较大的矩形)。

现在我们知道，第一个矩形需要拆分为16个较小的矩形，第二个矩形需要拆分为17个。有了这个信息，我们现在可以递归地为这两个矩形中的每一个调用Split_rect_to_count。

从顶层开始，此递归生成两个矩形列表，一个16长，另一个17长，我们将它们连接在一起以生成最终的矩形列表。

从视觉上看，这个递归(使用较小的目标计数5)看起来有点像这样(尽管在实践中它当然不是完全循序渐进的：

这就是整个过程：用这种精致的方法，我们可以尽可能接近我们想要的瓷砖密度。

既然我们已经讨论了很多理论，让我们来看看我们在实践中从这种平铺网格生成方法中实际得到了什么。

首先，让我们看一个实际生产平铺网格的示例。这个特殊的网格的目标是每块瓷砖有400架飞机的密度：

这里首先要注意的是，我们现在正好有26块瓷砖覆盖整个世界。回想一下，XYZ网格选择会产生数十亿个离散的瓷砖--我们已经将这个数字减少了9个数量级。这对缓存性能来说非常重要！

第二件更抽象(至少对我来说也很美)的事情是，我们可以用瓷砖的地理大小作为飞机密度的指示器。毕竟，每一块瓷砖都将包含相同数量的飞机，因此较小瓷砖中的飞机必然会包装得更密集。我们看到，这幅图得出了合理的结论--美国大陆、欧洲和亚洲的密度都很高，而南半球的密度却低得离谱。

这就引出了第二个示例：夸张的平铺网格。对于这个网格，目标密度是每块瓷砖100架飞机，这当然意味着我们有四倍于此的瓷砖数量。这也意味着我们可以更精细地了解全球的飞机密度分布：

我们还可以使用这些夸张的瓷砖网格来查看空中飞机在一天中的分布是如何变化的。要创建此动画，需要在24小时内每小时生成一次平铺栅格，并在地图上对生成的栅格集以及白天/夜晚边界的表示进行动画处理。这使我们能够清楚地看到飞机是如何跟随太阳在世界各地活动的。夜晚，一个地区变得安静，然后随着早晨让位于白天，又变得活跃起来。

最后，我们可以看到另一个发人深省的例证。前面的所有瓷砖网格示例都是在2019年秋季作为会议演示文稿的一部分生成的。以下是2020年5月以来较新的实际生产瓷砖网格：

以前的网格需要26块瓷砖才能达到400机密度目标，而我们现在只需13块瓷砖就可以实现同样的目标-这是新冠肺炎全球大流行导致航空旅行急剧减少的结果。

地图显然会继续存在，因为它们允许直观而引人入胜地显示FlightAware的数据。这意味着我们有责任不断改进这些体验。这类数据的平铺策略很可能不是未来的选择--例如，实时地图是我们提供的唯一使用平铺的地图产品。所有其他地图都使用松散的发布/订阅模型，客户端地图通过该模型请求与其相关的目标数据-例如，所有往返Kiah的航班，或单个航班。未来的改进可能包括为实时地图或其他功能更丰富的产品采用类似的发布/订阅模式，这些产品甚至可能支持。

.