地理位置服务设计 (Uber/滴滴)

发表于 分类于

Uber 每天在全球处理数千万次行程，核心技术挑战包括：司机/乘客实时位置上报、附近车辆搜索、高效的匹配算法和精准的 ETA 预估。所有这些问题的解决都离不开对地理空间数据的有效组织和查询。

一、核心需求

需求 说明
司机位置上报 司机端每 4 秒上报一次 GPS 坐标
附近车辆搜索 乘客叫车时找到附近可用车辆（500m-2km）
高效匹配 根据距离、司机评分、接单意愿等匹配最优司机
ETA 预估 预估司机到达时间（结合实时路况）
行程追踪 实时显示司机位置、预计到达时间

二、技术选型

2.1 空间索引方案

查询”距离我 2km 内的所有可用车辆”是经典的空间范围查询。以下是常用方案对比：

方案 原理 优点 缺点
GeoHash 经纬度编码为字符串，前缀匹配可做范围查询 简单、Redis 原生支持 边界问题需要查周围 8 个格子
四叉树 (QuadTree) 递归将地图分为四个象限 自适应密度 实现复杂、更新代价高
Google S2 希尔伯特曲线映射到球面 精度高、覆盖全球 学习成本高
H3 (Uber) 六边形网格 邻域查询更均匀 生态不如 GeoHash

2.2 Redis Geohash

Redis 原生 GEO 命令基于 GeoHash + ZSet 实现：

1
2
3
4
5
6
7
8
# 更新司机位置
GEOADD drivers 121.4737 31.2304 driver:1001

# 查询上海外滩 2km 范围内的司机
GEORADIUS drivers 121.49 31.24 2 km WITHDIST COUNT 20 ASC

# 计算两个位置之间的距离
GEODIST drivers driver:1001 driver:2002 km

底层实现：Redis 将 GeoHash 值（52 位整数）作为 ZSet 的 score 存储。范围查询等价于在 ZSet 上对 GeoHash 前缀做范围扫描。

三、GeoHash 原理

3.1 编码过程

GeoHash 将二维经纬度编码为一维字符串。核心原理是二分逼近：

1
2
3
4
5
6
以纬度 31.23 为例：
  区间 [-90, 90] → 31.23 在右半区 → 编码 1
  区间 [0, 90] → 31.23 在左半区 → 编码 0
  区间 [0, 45] → 31.23 在右半区 → 编码 1
  区间 [22.5, 45] → 31.23 在左半区 → 编码 0
  ...

经度和纬度交替编码，最终得到一串二进制位，每 5 位映射为一个 base32 字符，形成 GeoHash 字符串。

1
上海坐标 (121.47, 31.23) → GeoHash: wtw3s

3.2 精度与长度

GeoHash 长度 区域大小 适用场景
5 位 4.9km × 4.9km 城市级
6 位 1.2km × 0.6km 区级
7 位 153m × 153m 街道级
8 位 38m × 19m 精确位置

3.3 边界问题与解决方案

GeoHash 的缺陷：两个地理位置可能很近，但 GeoHash 前缀不同——因为它们在网格边界两侧。

例如，上海人民广场附近的两个点，一个在网格 A 的右边缘，一个在网格 B 的左边缘，虽然距离 50 米，但 GeoHash 可能完全不同。

解决方案：查询时同时检查目标网格 + 周围 8 个相邻网格：

1
2
3
4
查询网格 "wtw3s" 及周围 8 个邻居：
  wtw3k  wtw3m  wtw3t
  wtw3h  wtw3s  wtw3u
  wtw35  wtw3e  wtw3g

Redis GEORADIUS 内部已经自动处理了这个边界问题。

四、位置上报与更新

4.1 架构

1
2
3
4
5
6
7
8
9
10
司机端 (每4秒上报GPS)
    │
[WebSocket Gateway]
    │
[位置更新服务]
    │
    ├─ 更新 Redis GEO (实时查询用)
    ├─ 写入 Kafka (持久化数据流)
    │      └─ [消费者] → HBase/Cassandra (历史位置存储)
    └─ 通知匹配服务 (有新司机可用)

4.2 写入优化

策略 说明
批量写入 聚合多辆车的更新，一次 Redis pipeline 写入
有条件更新 位置变动 < 10 米时不更新，避免无意义写入
异步化 位置更新是异步的，接受短暂延迟

五、司机匹配

5.1 匹配流程

1
2
3
4
5
6
7
8
9
乘客叫车
    │
[GeoRadius] 查询 2km 内可用司机 → [司机列表]
    │
[过滤] 排除低分司机、已有订单的司机、距离太远的司机
    │
[排序] 按综合得分排序
    │
[派单] 向 Top-3 司机推送订单（30s 内无人接单则扩大范围）

5.2 匹配评分算法

1
2
3
Score = w1 × f(distance) + w2 × f(rating) + w3 × f(acceptance_rate) + ...

其中 f(distance) = 1 / (1 + distance/1000)  # 近距离加权更高

5.3 防止无效匹配

  • 推送订单前检查司机是否在线（心跳机制）
  • 30 秒超时 → 自动取消推送给其他司机
  • 司机端防作弊：检测模拟位置、异常轨迹

六、ETA 预估

ETA（预计到达时间）的精度直接影响用户体验，需要综合以下因素：

  • 路径距离：OpenStreetMap / 高德地图提供的路径规划
  • 实时路况：GPS 数据分析实时车速
  • 历史数据：同一时段、同一路段的平均耗时
  • 特殊因素：天气、事故、道路封闭

简单做法：路径距离 ÷ 预估速度。精度取决于路况数据的实时性。

地图和路径规划通常依赖第三方服务（高德/百度/Google Maps），业务层只需要调用 API 获取路径距离和预估值即可。

七、数据架构

数据 存储 说明
实时位置 Redis GEO TTL 1 分钟，超时自动清除
司机状态 Redis Hash 在线/离线/接单中，心跳保活
历史轨迹 HBase/Cassandra 按 driver_id + timestamp 排序存储
订单数据 MySQL/PostgreSQL 强一致性的订单状态
路况数据 内存网格 将地图切为 1km×1km 网格，实时计算每网格平均车速

八、小结

地理位置服务的核心技术：GeoHash 空间索引实现快速”附近搜索”，ZSet + 范围查询在 Redis 中高效实现，流式位置更新通过 Kafka 管道处理海量 GPS 数据。Uber 进一步自研了 H3 六边形网格系统来优化匹配公平性，这体现了在特定领域深耕带来的技术创新。