设计附近的人 / Yelp(邻近服务)

邻近服务回答一个看似难的问题:"我附近有什么地方?"给定用户的纬度/经度和半径,返回附近商家、按距离和相关性排序——快、有规模、对数亿个兴趣点。这是 Yelp、Google Maps 的"附近",以及打车背后匹配层的核心。整个问题归结到一件普通数据库无法高效做的事:地理空间索引——把二维坐标变成你能按区域索引和查询的东西。

  ┌──────┬──────┬──────┐   查用户的格子(★)和它的
  │ 9q8yt│ 9q8yw│ 9q8yx│   8 个邻居,因为刚好跨边界的
  ├──────┼──────┼──────┤   地方"近"但落在
  │ 9q8ys│ 9q8y★│ 9q8yr│   不同格子里。
  ├──────┼──────┼──────┤
  │ 9q8ye│ 9q8yg│ 9q8yu│   附近点共享一个 geohash 前缀:
  └──────┴──────┴──────┘   "9q8y…" → 便宜的前缀范围扫描

第 1 步 — 澄清需求

功能:给定一个位置和半径(或带默认半径的"给我看附近的餐厅"),返回附近地点;支持添加/更新一个商家;可选按分类过滤。非功能:低延迟、极读多、高可用、扩展到 ~数亿地点和高搜索 QPS。一个关键简化观察:数据大体静态——商家不移动且很少添加/编辑——所以我们能预计算并激进缓存,且更新的最终一致没问题。(对比打车,那里"地点"是每几秒更新的移动司机——那需要一个实时内存索引。)

第 2 步 — 容量估算

比如 200M 地点和 100M 每日搜索(~1–2K 搜索/秒平均,峰值高得多,如密集城市的午餐时间)。每条地点记录小(id、名、lat/lng、分类、评分)——几百字节——所以数据集是数十 GB,易缓存。负载压倒性是对很少变化数据的读,这把整个设计导向索引 + 缓存而非写吞吐。

第 3 步 — API 设计

GET /search?lat=37.78&lng=-122.41&radius=2km&category=cafe
      → [{id, name, distance, rating}, ...]   # 已排序
POST /places   {name, lat, lng, category, ...}   # 添加/更新一个商家

第 4 步 — 为什么普通索引失败

本能是存 lat 和 lng 列并查 WHERE lat BETWEEN ... AND lng BETWEEN ...。问题:B-tree 索引是一维的。lat 上的索引找到正确纬度带但包括整个星球那个纬度的每个地点;你随后在内存里按经度过滤(或反过来)。对一个全球数据集那是每查询的巨大扫描。我们需要一个保留 2D 局部性的索引——地图上接近的点在索引里也应接近。两种标准结构做这个。

第 5 步 — Geohash

Geohash 递归把世界分成网格并交错纬度和经度的位,把结果编码为一个短 base-32 字符串。两个属性使它强大:更长的 geohash = 更小、更精确的格子(每个额外字符 ~细化方框),且附近位置共享一个公共前缀(如同一街区的两个咖啡馆可能都以 9q8yyk 开头)。所以你存一个 geohash 列、正常索引它,"找 X 附近地点"变成"找 geohash 以 X 前缀开头的地点"——普通索引上一个便宜的前缀/范围扫描。你选前缀长度匹配搜索半径(更紧半径用更长前缀)。

第 6 步 — Quadtree

Quadtree 采取自适应方法:从整个地图作一个节点开始;若一个格子含超过阈值的点,把它分成四个相等象限;递归。结果是密集区(市中心)有许多小格子而稀疏区(乡村)有几个大的——格子粒度自动跟随数据密度,所以每个叶持有有界数量的点。一次搜索下降到含查询点的叶并收集附近的叶。Quadtree 通常保在内存并周期性重建;它给出无论密度如何都很均匀的结果集大小。

Geohash 是更简单、更常见的面试答案(它骑在任何现有数据库索引上);quadtree 在密度剧烈变化、你想要均匀结果大小时出彩。Redis 的地理空间命令和 PostGIS 底下用相关技术。

第 7 步 — 数据模型与存储

places (
   place_id PK, name, category, rating,
   lat, lng,
   geohash        # 已索引;如 "9q8yyk8ytpxr"
)
INDEX on geohash   # 前缀范围扫描 = 附近查找

你能存几个 geohash 精度(或就用可变前缀长度查询)以匹配不同半径。places 表是真相来源;geohash 列是骑在标准 B-tree 上的空间索引。

第 8 步 — 读路径与边界问题

一次搜索分两阶段。阶段 1(索引):以匹配半径的精度计算查询点的 geohash,然后取 geohash 共享那个前缀的候选地点。阶段 2(精炼):计算查询到每个候选的精确大圆距离、丢掉半径外的、排序。陷阱是边界问题:50 米外的一个地点可能刚好坐在格子边界另一侧、因而有不同 geohash 前缀,会被漏掉。修法是也查查询格子周围的 8 个相邻格子、合并候选、然后精炼。(Quadtree 有类似问题,同样检查相邻叶。)

第 9 步 — 缓存与读扩展

因为数据几乎不变且读主导,缓存是主要扩展杠杆。给热门格子——密集、频繁搜索的区域如市中心——的结果(或候选集)在 Redis 缓存配宽松 TTL,因为一家新餐厅出现非时间关键。用副本罩住读流量,让大体静态的数据集大体住在内存。繁忙区域的大多数搜索应从缓存服务而不碰主存储。

第 10 步 — 分片与扩展写

读随副本和缓存扩展;为存储和写分布,按区域分片(如按 geohash 前缀,使一个分片拥有一个连续区域)。这让搜索的候选格子大多时候在一个分片上。警惕热点:覆盖曼哈顿的 geohash 前缀分片处理的地点和查询远多于覆盖公海的,所以按负载而非仅按面积平衡分片(密集处更细拆分)。写(新/编辑商家)罕见且能异步更新索引。

第 11 步 — 排序

"附近"不只关于距离。最终排序通常混合距离、评分/热度、分类相关性,有时还有赞助位。因为空间过滤后的候选集小(半径内的地点),这个排序每请求计算便宜,或部分预计算(如一个地点的基础热度分)并与实时距离结合。

第 12 步 — 关键取舍

• Geohash vs quadtree。Geohash 极简单且骑在任何 DB 索引上但有固定格子在密集区溢出;quadtree 适应密度并约束结果大小但是个内存结构、维护更费力。
• 精度 vs 结果数。更长 geohash 前缀(更小格子)返回更少、更紧的候选但对给定半径可能需更多邻居格子;更短前缀返回更多候选去过滤。
• 静态数据 → 狠狠缓存。读多、很少变化的性质使激进缓存和复制成为主导扩展策略,更新的最终一致可接受。
• 静态地点 vs 移动对象。这个设计假设近静态点;跟踪移动对象(司机)需要一个频繁更新的内存索引——一个不同问题。