使用更智能的缓存将地图集群服务速度提高 50 倍

具有位置标记的地图组件在当今的移动应用程序中很常见。 例如，Airbnb 应用程序突出显示了从网络服务获取的此类标记，以表示地图上的可用属性。

为了确保获取的数据量不会随着标记数量的增加而变得难以管理，服务器将这些标记组合在一起，然后再将它们发送到客户端。 地图簇是一个专门的标记，其位置等于它所包含的标记的平均位置。 它标有它所代表的标记数量。

尽管如此，服务集群可能会造成性能瓶颈，因为 Web 服务必须从数据库中检索给定地理区域内的每个标记。 幸运的是，这个问题可以通过缓存策略来解决。 为了更好地理解如何设计和维护缓存，让我们看一下我为 Playsports 应用程序构建的示例地图 API 端点。

扩展问题和简单的解决方案

在 Playsports 地图中，每个标记代表一个运动设施。 在给定缩放级别和边界框的情况下，地图的 API 端点需要返回标记和标记簇的列表。

如果标记的数量足够少，我们可以从数据库中加载边界框中的所有标记，根据需要进行聚类，并将生成的标记和聚类返回给客户端。

一开始，Playsports 中任何可到达边界框中的最大标记数约为 400，因此端点速度约为 0.5 秒。 对于这个用例，实施简单的解决方案就足够了。

然而，随着标记数量的增加，该机制的低效率变得明显。 在我们添加了约 10,000 个新的体育设施标记后，在某些缩放级别下，端点速度减慢至约 4.3 秒。 此速率远低于通常被认为是移动应用程序中用户操作的最大可接受延迟的一秒持续时间。

为了更好地理解朴素解决方案的低效率，让我们在标记查询的上下文中对其进行分析：

1. 从数据库中检索边界框中的所有标记。 对于大多数应用程序，此步骤需要包括获取纬度/经度定位之外的标记详细信息。 例如，Airbnb 的标记包括价格、用户是否已经查看过该房产以及是否将其标记为收藏。
2. 在检索到的标记上，运行包含缩放级别的地图聚类算法。
3. 将集群和（详细）标记返回给客户端。

随着标记数量的增加，第 1 步和第 2 步的性能会下降：

• 当边界框足够大，并且超过 10,000 个标记需要通过 JOIN 进行详细查找时，数据库查询会显着减慢（1 到 2 秒）。
• 将 10,000 个项目提供给地图聚类算法需要另外约 250 毫秒。

假设窗口大小恒定，当边界框相对较大时，缩放级别通常较低（即，缩小得很远）。 在低缩放级别下，结果往往有利于集群以避免视觉拥挤。 因此，优化的最大潜力在于解决方案的第一步，其中加载了数千个单独的标记。 结果中不需要大多数这些标记。 我们只需要它们中的每一个都计入一个集群。

构建优化的解决方案

天真的解决方案需要更长的时间才能完成最坏情况的查询：标记密集区域中的最大边界框。 相比之下，优化后的解决方案仅需 73 毫秒，加速了约 58 倍。 从高层次来看，它看起来像这样：

1. 缓存策略。 从特定于缩放级别的缓存中检索边界框中的标记和集群。
2. 附加标记详细信息（可选）。 使用从数据库中获取的有效负载增强标记。
3. 返回结果。 将标记和集群返回给客户端。

主要的复杂性在于缓存的架构（即第一步）。

第 1 步：缓存策略

这个主要步骤包括六个部分：

技术

Redis 是一种快速的内存数据库，通常用作缓存。 其内置的地理空间索引使用 Geohash 算法来高效存储和检索经纬度点，这正是我们标记所需要的。

每个缩放级别的缓存

地图聚类的程度（是否返回单个标记或聚类）由传递给端点的缩放级别决定。

• 对于高缩放级别（即，放大关闭），结果将有利于单个标记，但标记密集区域除外。
• 对于低缩放级别（即，缩小远），结果将有利于集群，但标记稀疏区域除外。

谷歌地图支持从零到最大 20 的缩放级别，具体取决于区域。 （其他地图服务支持的范围类似。例如，Mapbox 使用从零到最大 23 的缩放级别。）由于这些缩放级别也是整数值，我们可以简单地为每个缩放级别创建单独的缓存。

为了支持谷歌地图中的所有缩放级别——除了零级，它被缩小得太远——我们将创建 20 个不同的缓存。 每个缓存将存储整个地图的所有标记和集群，按照它所代表的缩放级别进行集群。

缓存数据类型

每个缓存都将存储集群和单独的标记。 对于任何一种类型的条目，我们都需要填充几个字段：

但是，Redis 允许用户仅将位置和单个字符串存储为地理空间集中的值。 为了绕过这个限制，我们将上述字段序列化为 JSON 字符串。 然后我们使用这个字符串作为 Redis 中的值。 Redis 中键和值的最大大小为 512 MB，对于这个用例来说已经绰绰有余了。

填充缓存

为了填充缓存，我们从数据库中检索所有标记。 对于每个缩放级别，我们执行地图聚类算法。 我们使用 Redis 的GEOADD将生成的标记和簇插入到相应缩放级别的缓存中，并传递纬度和经度，加上前面描述的 JSON 字符串。

在这个阶段在整个地图上运行地图聚类算法（而不是在用户的边界框上，按需）理论上可能会在聚类位置上产生一些边缘差异，但整体用户体验将保持不变。

查询缓存

对于传入的请求，我们将给定的边界框传递给 Redis GEOSEARCH命令，该命令查询给定缩放级别的缓存以检索该区域中的标记和集群候选者。

设计缓存刷新计划

20 级缓存刷新很昂贵，因此最好在项目要求允许的情况下尽可能不频繁地刷新。 例如，在 Playsports 中添加或删除体育设施只会将缓存标记为陈旧； 如果需要，每小时 cron 作业会刷新缓存。 有关此内容的更多信息，请参阅缓存陈旧部分。

第 2 步：附加标记详细信息（可选）

此时，大多数应用都需要根据各个标记 ID 获取详细信息。 我们可以将此详细信息作为缓存中字符串化 JSON 值的一部分，但在许多应用程序中，标记详细信息是用户特定的。 由于所有用户都有一个共享缓存，因此不可能在其中存储这些附加字段。

我们优化的解决方案从缓存结果中获取各个标记的 ID，并从数据库中获取它们的详细信息。 现在我们只查找聚类后留下的单个标记。 当地图缩小时（因为我们将有大部分集群）或放大时（因为区域会很小），这些不会太多。

相反，朴素的解决方案在聚类之前查找边界框中的所有标记（及其详细信息）。 因此，这一步（可选，但对于许多应用程序而言至关重要）现在运行得更快了。

第 3 步：返回结果

随着集群的构建和单个标记的增强，我们现在可以将这些交付给客户。 除了一些无关紧要的边缘情况之外，生成的数据几乎与天真的解决方案相同——但我们能够更快地交付它。

进一步的考虑

现在让我们看看另外两个因素：

资源需求

假设一个应用的地图总共包含 N 个标记。 由于最多有 20 个缩放级别，我们最多需要存储 20N 个缓存项。 然而，在实践中，由于集群的原因，缓存项的实际数量通常要低得多，尤其是在较低的缩放级别中。 事实上，分布在所有 Playsports 缓存中的缓存项的总数仅为 ~2N。

此外，如果我们假设缓存值（字符串化的 JSON）的长度约为 250 个字符（一个合理的假设，至少对于 Playsports）并且字符串大小是每个字符 1 个字节，那么JSON 值大约为 2 * N * 250 字节。

在这个图中，我们为GEOADD使用的排序集添加了 Redis 的内部数据结构。 Redis 为 100 万个小型键值对使用 85 MB 内存，因此我们可以假设 Redis 内部占每个缓存项不到 100 字节。 这意味着我们可以使用 1 GB-RAM Redis 实例来支持多达 140 万个标记。 即使在标记均匀分布在整个地图上的不太可能的情况下，导致缓存项的数量接近 20N，N 仍可能上升到 ~140,000。 由于一个 Redis 实例可以处理超过 40 亿个键（准确地说是 2 ^{32 个}），因此这不是限制因素。

缓存陈旧

根据使用情况，仅定期刷新缓存可能是不够的。 在这种情况下，我们可以使用限速任务队列。 它将减少缓存陈旧，同时仍然限制缓存刷新次数，从而限制系统负载。

每次数据库更新后，我们都会排队缓存刷新作业。 这个队列会将任务数限制为每小时 M。 这种折衷方案允许比每小时更快的更新，同时保持系统上相对较低的负载（取决于 M）。

缓存策略胜过地图聚类算法

Playsports 的优化解决方案——比简单的解决方案快 50 多倍——运行良好。 它应该会继续运行良好，直到我们达到 140 万个标记或超过现有数据的 100 倍。

对于大多数基于地图的 Web 服务请求，需要某种形式的预先计算以实现可伸缩性。 要使用的技术类型以及具体设计将取决于业务需求。 缓存陈旧需求、标记扩充和标记数量是设计解决方案时要考虑的重要特征。

进一步阅读 Toptal 工程博客：

• 面向 Web 开发人员的最佳在线制图工具调查：路线图路线图
• GPS 编程和开发历险记：地理空间教程