从 0 到 1 看懂 Uber：百万并发下如何高效匹配“附近司机”？

码农有道2025年11月21日约 9 分钟

2016 年3月，查尔斯和他的家人正在土耳其伊斯坦布尔旅游。然而，他们的出行却遇到了困难，因为最近的出租车站距离酒店足有3公里远。这让他们感到非常沮丧。

在与酒店接待员交流后，他们得知了一款名为Uber的拼车应用。抱着试一试的心态，查尔斯立即下载安装了Uber，几秒钟后，他惊讶地发现，找到附近的司机竟然如此简单。

然而，对于开发人员来说，准确且高效地找到附近的司机并不是一件容易的事。我们看看Uber是这样解决这个难题的。

位置索引

要解决“附近司机”这个问题，首先要面对一个核心难题——位置索引。

仅仅依靠经纬度坐标来查找附近的司机，几乎是不可能高效完成的，原因在于：

数据量庞大：经纬度是一个连续的数值范围，如果只根据经纬度进行查询，系统需要遍历海量的司机位置数据并逐一计算距离，来找到符合条件的司机，这样效率非常低。
缺乏结构化信息：经纬度本身并没有提供一种结构化的方式来定义“附近”这个概念。系统需要计算每个司机的位置与乘客的位置之间的距离，计算量大，非常耗时。

因此，Uber 通过一种名为位置索引的技术，更高效地解决了“如何快速找到附近司机”的问题。

位置索引的核心思想，是将地理位置（如经纬度）转化为一种便于搜索和管理的数据结构，从而避免直接对海量坐标进行距离计算。

为此 Uber 的开发人员开发了一个名为 H3 的开源库。H3 是一个高效的地理空间索引系统，它使用六边形网格将地球表面划分为许多小的单元格。每个六边形单元都有一个唯一的 64 位整数编号，这个编号就是 H3 索引。

这种设计带来了性能上的极大提升：当系统需要查找乘客附近的司机时，不再需要对所有司机的经纬度进行复杂的距离计算，只需找到与乘客位置相邻或重叠的六边形区域编号，即可快速定位到用户附近的司机。这样提高了查询的速度和准确性。

具体来说，当乘客发出叫车请求时，Uber 首先会确定乘客所在位置属于哪个六边形单元。然后，系统会进一步选取该单元周围的一圈甚至多圈六边形区域，以确保覆盖到所有可能接单的司机。

接下来，Uber 会在这些候选单元格中查找司机，并根据司机的预计到达时间（ETA, Estimated Time of Arrival）对结果进行排序。ETA 表示司机从当前位置到乘客位置的预计行驶时间，最后，系统会将最合适的几个司机返回给乘客端，展示司机的头像、车辆信息和预计到达时间等数据，这样，乘客可以选择最适合自己的司机。

下面将更为详细的介绍H3 的工作原理。

H3 的工作原理

1. 分层索引

Uber 需要一种既精确又高效的地理索引方式。索引单元越小，位置精度就越高；但单元过多又会导致存储和计算成本上升。反之，如果单元太大，虽然计算更快，却会掩盖数据中的细节。

为了解决这一矛盾，Uber 采用了一种分层网格结构，在这种结构中，每个较大的六边形单元都可以被细分为更小的六边形单元，从而在需要时提供更高的空间分辨率。

分层网格的好处在于，它允许数据压缩：细节较少的区域用较少的单元表示，而在城市这种细节丰富的区域则由更多的单元表示。

此外，使用分层网格还能更方便地调整数据分辨率，因为可以通过截断子单元的标识符来找到其上层单元。

在 H3 的实现中，Uber 首先创建了一个包含122个基础单元的全球网格。其中，有12个基础单元是五边形，因为地球是球体，不能仅通过六边形完美地铺满。为了保持一致性，H3 将这些五边形视为“特殊的六边形”，不再细分。

此外，六边形在细分时无法做到完美等分，H3 采用了一个近似方案：每个六边形会被细分为 7 个子六边形，并通过旋转和对齐来尽量减少误差。

目前，H3 支持 16 个不同级别的分辨率，最高精度可细化到约 1 平方米的区域。

在实际应用中，Uber 还将 H3 的单元标识符作为数据分区键使用。这种方式既能确保高效的数据处理，又能优化存储和查询的成本。

2. 六边形网格与距离计算

在建立分层索引后，Uber 还需要解决另一个关键问题——如何精确地计算不同位置之间的距离。

因为在实际场景中，找到“附近的司机”本质上就是一个距离计算问题。

理论上，地球表面可以用多种形状的网格来划分，例如三角形、正方形或六边形。但 H3 最终选择了六边形网格，原因在于它在距离计算上具有天然优势：

每个六边形单元的中心到相邻单元中心的距离相等，这使得邻居之间的距离计算更加简便；
在三角形单元中，有 3 个邻居比其他邻居更远；
在正方形单元中，也存在 2 个“对角邻居”距离更远的问题；

因此，六边形是地理空间索引中一种理想的几何形状，而使用三角形或正方形单元进行距离计算时，需要额外的修正系数。

3. 分层算法

在确定了网格结构之后，3 还提供了一套强大的算法，用于在网格中快速定位和搜索。通过输入经纬度和分辨率等级，H3 可以立即返回对应位置的唯一单元标识符。

当系统需要查找某个单元周围的其他单元（例如，乘客周围的司机）时，H3 提供了一个非常高效的函数——kRing()，这个函数能够在给定的半径范围内，快速找到目标单元的所有邻居单元。

位置存储

在构建位置索引系统后，Uber 还需要解决另一个现实问题：如何确保位置数据本身的准确性。

司机的手机应用会每隔几秒向服务器上报一次当前的 GPS 位置。然而在实际环境中，GPS 信号往往会受到建筑物遮挡、天气、网络延迟等因素的影响，从而出现漂移或噪声变得不准确。

为了保证位置数据的可靠性，Uber 采用了地图匹配技术。

地图匹配技术

地图匹配技术的主要目的是将这些不准确的 GPS 数据点“匹配”到最接近的实际道路上，以便提供更可靠的导航信息，其主要工作流程如下：

获取原始 GPS 数据：车辆或移动设备在行驶过程中，每隔一段时间会记录一次经纬度信息，从而形成一系列经纬度数据点。
预处理和过滤：对这些原始数据进行噪声消除与平滑处理。例如，剔除突发跳跃的异常点（可能由信号干扰造成），同时对连续的位置点进行平滑处理，减少由于信号噪声引起的位置波动。
匹配算法执行：使用特定的地图匹配算法将 GPS 数据点映射到道路上。常见的算法包括线性插值、卡尔曼滤波等。

数据存储

在完成位置索引和地图匹配之后，Uber 还需要将这些位置信息高效、可靠地保存下来，以便后续进行查询、分析。

Uber 选择使用 Apache Cassandra 作为核心的数据存储系统。

Cassandra 是一个高可用、分布式的 NoSQL 数据库，专门针对写入操作进行了优化。值得注意的是，Uber 并不是直接存储经纬度，而是存储的单元格的标识符。

为了管理这些位置数据，Uber 设计一张位置信息表location_info，表结构大致上是这样的：

例如，假设一个user_id为001的司机其经纬度坐标为 (40.7128°N, 74.0060°W)。这个坐标会被转换为一个 H3 单元格的标识符，例如是 891fbf5b547f7e0。那么在表中会存储为：

001   1   891fbf5b547f7e0  1723346519

这张表会存储所有人（包括司机和乘客）的位置信息。

现在假设一个乘客所在的 H3 单元格的标识符为 '891fbf5b547f7e0'，如果要搜索其附近的司机，那么一个最简单也是最自然的想法就是，将和乘客处于同一个单元格的司机找出来就可以了，对应于以下sql语句：

#查询和乘客同一单元格的所有司机：SELECT user_idFROM location_infoWHERE h3_cell_id = '891fbf5b547f7e0'AND user_type = 'driver';

但是，这里至少有2个点值得思考：

1. 如果想要找到更广泛区域内的司机？

我们前面只是查询了和乘客位于一个单元格的司机，但是有时刚好和乘客落在一个单元格的司机很少，那么我们需要扩大查找范围，乘客所在单元格周围的单元格也需要查找。

为了解决这个问题，H3 提供了一个非常实用的函数 kRing()，其作用是返回指定单元格周围的 k 层邻近单元格，其中参数 k 表示扩展的层数，例如将 k 设为 2，则会获取乘客所在单元格以及周围两层的所有相邻单元格。

# 伪代码示例# k=2 表示查找乘客所在单元格及其周围 2 层单元格surrounding_cells = h3.kRing('891fbf5b547f7e0', k=2)#假设返回了891fbf5b547f7e1, 891fbf5b547f7e2

然后我们就可以继续用上面的查询语句查询这些单元格内的司机：

SELECT user_idFROM location_infoWHERE h3_cell_id in ('891fbf5b547f7e0', '891fbf5b547f7e1', '891fbf5b547f7e2')AND user_type = 'driver';

2. 如果要求推荐给乘客的是距离他最近的20个司机？

为了实现这个目的。我们需要知道每个司机的经纬度坐标，我们可以直接在location_info增加2个字段表示经度和维度。

这样查询出来的数据就包含经度和维度了，就能计算距离，然后进行排序输出了。

引入缓存

缓存用户最新位置信息

为了减少读取操作的延迟，Uber 在 Cassandra 上添加了一个 Redis 缓存层，用于存储每位用户的最新位置。

Uber 在 Redis 中主要维护了两类缓存数据：

1. 用户的最新位置信息

Key： 用户 ID（user_id）Value： 用户（包括司机和乘客）的最新位置信息，通常以 JSON 格式存储例如：key： 12345value：{"latitude": 40.7128,"longitude": -74.0060,"user_type": 1,"timestamp": "2024-08-11T14:32:00Z"}

这表示用户 12345 的最新坐标是 (40.7128, -74.0060)。

2. H3 单元格内的司机 ID

除了缓存每个用户的最新位置，Uber 还在 Redis 中维护了另一类关键信息——单元格内的司机 ID。

Key： H3 单元格标识符Value：当前位于该单元格内的司机 ID 集合例如：key：h3:891fbf5b547f7e0value：[ "12345", "67890", "54321" ]

表示单元格 891fbf5b547f7e0 中目前有三个司机。

引入缓存后，“查找附近司机”的过程得到了极大优化，现在的查询流程如下：

确定相关单元格：首先使用 H3 库将乘客的经纬度位置转换为对应的 H3 单元格标识符。如果需要扩大查找范围，可调用kRing 函数获取该单元格周围若干层的相邻单元格，以覆盖更大的地理区域。
从缓存中获取候选司机：对于每个相关的 H3 单元格标识符，可以查看Redis 缓存中有没有对应的司机 ID 集合，如果没有，就要去查询数据库了，这是前面没引入缓存时的流程，这里我们假设能在缓存中找到。
获取司机的最新位置：取得候选司机 ID 后，系统再根据这些 ID 从 Redis 中获取各自的最新位置信息。有了这些坐标数据，系统就可以计算司机与乘客的距离，并按距离或预计到达时间（ETA）进行排序，最终选出最合适的司机。

缓存支持地图匹配

在实际运行中，司机的 GPS 信号会不断上报，Uber 需要实时对这些数据进行地图匹配处理，以修正偏差、确保定位准确。

为此，Redis 会暂存足够数量的原始位置数据点，供地图匹配算法进行计算。当这些数据经过处理后，结果会被持久化到 Cassandra 的独立数据模式中，以便后续分析和追踪。

总结

通过以上架构设计，Uber 构建了一套高效、可扩展且精准的实时位置服务系统。

其中，H3 负责地理空间索引与邻近查找，Cassandra 提供海量数据的持久化支持，而通过引入缓存提升系统性能，并为地图匹配等实时任务提供数据支撑。这样的架构使得 Uber 能够准确地定位附近的司机，确保了乘客有良好的用户体验，并且能够扩展到每秒处理 100 万个请求的能力。