加速 Redis 7 中的地理命令

英特尔和 Redis 在性能方面取得了显著提升！在此，我们将 分享我们用于评估和最大化 Redis GEO 命令性能的优化技术，例如减少不必要的计算和简化算法。

所有的努力都得到了回报。总的来说，我们将 Redis 的性能提高了至多四倍！ 

Redis 的 GEO 命令（正式名称为 地理空间索引）是处理地理数据的强大工具。Redis 可以存储对象的地理坐标，例如商店位置或移动中的送货卡车。然后，Redis 可以对这些数据执行基于数学和坐标的操作，例如确定两点之间的距离（我订购午餐的送货车离我有多远？）或查找另一个点给定半径内的所有注册点（离我当前位置最近的宠物店在哪里？）。

最终，这些经度和纬度只是您应用程序访问和更新的数据。与作为关键业务逻辑一部分的任何数据库一样，您希望获得最佳性能——特别是在访问数据的系统正在进行物理移动（例如送货卡车）并因此需要实时响应时。为了实现这一点，优化您用于与 GEO 数据交互的查询和算法非常重要。

为了最大限度地提高 Redis GEO 命令的执行性能，我们深入研究了性能分析和工作负载特征分析技术。目标是找出瓶颈、优化资源利用并提升整体性能。

在这篇文章中，我们将分享这些优化技术，例如减少不必要的计算和简化算法，以及我们分析的结果。结论是：我们可以在 GEOSEARCH 查询上实现四倍的吞吐量，并且这一改进已作为 Redis 7 的一部分发布。

性能分析与地理应用场景

性能分析和工作负载特征分析是理解应用程序性能特性的重要技术。这些技术涉及收集和分析有关应用程序行为及其资源使用情况的数据，以识别瓶颈、优化资源利用并提高整体性能。

无论我们尝试加速哪种应用程序，我们都使用确定性、简洁和系统的方法来监控和分析性能。要亲自实践，您可以采用多种 性能方法 中的任何一种，根据您想要解决的问题类型和进行的分析，有些方法比其他方法更适用。

广义上讲，当您想要提高程序的效率时，这份通用清单适用于大多数情况

1. 确定性能目标：开始之前，您需要清楚地了解想要达成的目标。目标可能包括改善响应时间、减少资源利用或提高吞吐量。在本例中，我们希望同时改善每个独立操作的响应时间，并因此提高可实现的吞吐量。

2. 识别工作负载：接下来，确定您将分析的工作负载。这可能涉及识别应用程序将执行的特定任务或操作，以及预期的负载和使用模式。对于 GEO 命令的应用场景，我们使用了基于 OpenStreetMap (PlanetOSM) 数据的包含 6000 万个数据点的数据集，并使用了一组地理距离查询进行基准测试。

3. 收集数据：识别工作负载后，为每个使用案例收集有关应用程序性能及其资源利用率的数据。您可以使用分析器、调试器或性能分析工具。收集有关程序内存使用、CPU 利用率和其他指标的数据。通过按时间间隔采样堆栈跟踪来分析 CPU 使用情况是一种快速简便的方法，可以识别性能关键的代码段（也称为热点）。我们的发现正是基于使用 Linux perf 工具来实现这一目标。我们关于识别性能退化和潜在 CPU 性能改进的文档包含工具的完整列表和更深入的方法。

4. 分析数据：收集数据后，可以使用各种技术来分析数据并识别可能影响应用程序性能的区域。其中一些技术包括分析随时间变化的性能、比较不同的工作负载以及寻找数据中的模式。我们发现在拥有正在分析的应用程序的代码上下文时，通过使用 perf report 分析记录的剖析信息，可以轻松改进 CPU 相关的用例。您对应用程序代码的经验越多，就越容易对其进行优化。

5. 优化应用程序：根据您的分析，您可以识别可能导致性能问题的应用程序区域。然后采取措施优化代码，例如更改为更高效的算法、减少内存使用量或进行其他代码调整。在接下来展示的场景中，我们将重点关注算法效率和减少重复计算量。

6. 重复流程：性能分析和工作负载特征分析是持续进行的流程，因此定期审查和分析应用程序的性能非常重要。这使您能够识别和解决在更新或使用场景中可能出现的新瓶颈或问题。

Redis 地理空间索引距离计算的背景信息

如果您不了解软件在做什么，就无法让它运行得更快。在这种情况下，这意味着简要介绍处理地理空间数据的过程。

大多数查询 Redis 地理空间索引 的命令都会计算两个坐标之间的距离，因此有必要研究其算法实现方式。半正矢距离（Haversine distance）是一个有用的度量，因为它考虑了地球的曲率，结果比欧几里得距离计算更准确。 

要在球体（例如地球）上计算半正矢距离，您需要两个点的纬度和经度以及球体的半径。半正矢公式计算两点之间的直线距离，即沿着球体表面的最短路径。

这些计算高度依赖三角函数来计算半正矢距离，并且调用三角函数在 CPU 周期方面是昂贵的。在对简单 GEOSEARCH 命令的瓶颈分析中，大约 55% 的 CPU 周期消耗在这些函数内部，如图 1 所示。这意味着优化这些代码块是值得的，正如 Amdahl 会说的那样：“通过优化系统的一个部分获得的整体性能提升受限于该优化部分实际使用的时间比例。”

所以，让我们着眼于最大可能的优化。

第一轮优化：减少不必要的计算

如上面的剖析数据所示，  54.78% 的 CPU 周期是由 geohashGetDistanceIfInRectangle 生成的。在该函数内部，我们调用了 geohashGetDistance 三次。前两次调用该例程是为了产生中间结果（例如检查一个点是否超出经度或纬度范围）。如果条件不满足，这可以避免耗费 CPU 的距离计算。检查数据是否在范围内是合理的，但我们不需要重复这样做。

我们第一次尝试优化，分两步减少中间结果的不必要计算（详细描述在 PR #11535 中）

• 减少中间 geohashGetDistance 计算中的昂贵计算。
• 如果纬度距离条件不满足，则避免昂贵的经度距离计算。

这一优化带来了显著差异。对于该 GEOSEARCH 查询，在使用单个无 pipeline 的基准测试客户端时，我们将平均延迟（包括往返时间）从 93.598 毫秒降低到 73.046 毫秒，延迟降低了约 22%。

第二轮：不必要的计算

对 GEOSEARCH 查询的相同性能分析还表明，在某些情况下，Redis 会对 sdsdup 和 sdsfree 执行冗余调用。这些命令分别用于分配和释放字符串内存。这种情况发生在大数据集上，其中许多元素超出了搜索范围。

我们在 PR 11522 中提出的性能改进很简单：我们没有预先分配字符串内存，而是改变了 geoAppendIfWithinShape 的作用，让调用者只在需要时创建字符串。这导致延迟降低了约 14%，可实现的 ops/sec 提高了 25%。

第三轮：简化算法

为了优化地理索引查询，我们重点关注数据模式信息。目的是简化计算半正矢距离所需的计算次数。这纯粹是一项数学练习。

当经度差为 0 时

• 给定经度差为零时，半正矢公式中的 asin(sqrt(a)) 变为 asin(sin(abs(u)))。
• 当 x ∈[−𝜋/2,𝜋/2] 时，将 arcsin(sin(x)) 等于 x。
• 给定纬度在 [−𝜋/2,𝜋/2] 之间时，我们可以将 arcsin(sin(x)) 简化为 abs(x)。

PR #11579 详细描述了这项简化的优化及其获得的性能提升。结论是：它使得 Redis GEOSEARCH 命令的可实现每秒操作次数增加了 55%。

第四轮：表示问题

所有严重依赖将双精度浮点数转换为字符串表示（例如将双精度浮点数 (1.5) 转换为字符串 (“1.5”)）的用例，都可以通过将对 snprintf(buf,len,”%.4f“,value) 的调用替换为等效的定点双精度数到字符串的优化版本来受益。 

如图 3 所示的 GEODIST 命令就是一个很好的例子。大约四分之一的 CPU 时间用于类型转换。

PR 11552 详细描述了我们建议的优化，它使得 GEODIST 命令的可实现每秒操作次数增加了 35%。

将所有优化整合到 Redis 7.0 中

Redis 作为数据库受欢迎的一个主要原因是其性能。我们通常以亚毫秒级的响应时间来衡量查询——而且我们希望继续改进它！

我们在本博客文章中描述的优化措施的累积效果是：我们将 Redis 地理空间命令的性能提高了至多四倍。您已经可以从这些改进中受益，因为它们是 Redis 7.0.7 的一部分。这将使您更快地到达目的地。

命令	测试用例	可实现的每秒操作次数 Redis 7.0.5	可实现的每秒操作次数 Redis 7.0.7	改进系数
GEODIST key …	geo-60M-elements-geodist-pipeline-10	775524	993632	1.3 X
GEOSEARCH … FROMLONLAT … BYRADIUS	geo-60M-elements-geosearch-fromlonlat	11.8	13.8	1.2 X
GEOSEARCH … FROMLONLAT … BYBOX	geo-60M-elements-geosearch-fromlonlat-bybox	13.2	49.6	3.8 X

命令	测试用例	总体的 p50 延迟（含 RTT）（毫秒） Redis 7.0.5	总体的 p50 延迟（含 RTT）（毫秒） Redis 7.0.7	改进系数
GEODIST key …	geo-60M-elements-geodist-pipeline-10	2.575	2.007	1.3 X
GEOSEARCH … FROMLONLAT … BYRADIUS	geo-60M-elements-geosearch-fromlonlat	679.935	598.097	1.1 X
GEOSEARCH … FROMLONLAT … BYBOX	geo-60M-elements-geosearch-fromlonlat-bybox	605.739	161.791	3.7 X

请注意，这并非孤立的性能提升——恰恰相反。这组改进是我们称之为“Redis 基准测试规范”的性能工作影响的一个真实案例。我们正在不断努力，以提高整个 Redis API 的可见性和性能。

更进一步

想了解更多关于地理空间计算的知识吗？这个五分钟的视频为您概述了情况。

了解本系列其他性能博客文章的更多信息，其中大部分是与英特尔合著的

• 更快，再更快！系统地改进 Redis 性能，描述了我们如何将 stream 的摄取性能提高约 20%。
• 性能测试、剖析和分析，描述了我们的“零接触”性能和剖析自动化。
• 房间里的大猩猩：探索 RedisTimeSeries 性能优化，研究了 RedisTimeSeries 压缩/解压缩算法的潜在性能优化。 
• 优化 Redis 的默认编译器标志，关于改变 Redis OSS 中的编译器行为。

*Intel、英特尔标识以及其他英特尔商标是英特尔公司或其子公司的商标。