系统设计面试：设计附近地点搜索服务

题干与适用场景

设计一个全球附近地点搜索服务。目录保存 5000 万个餐厅、商店和公共设施；用户按当前位置、500 米到 50 公里的半径、类别和营业状态，获取距离最近的 20 个结果。搜索峰值为每秒 20 万次，商家创建、搬迁、关闭等更新峰值为每秒 100 次，端到端读取 p99 目标为 150 毫秒。

本题把地点视为低频更新的静态实体。司机、骑手或朋友位置的秒级更新、匹配与防止重复分配属于另一套动态位置系统。距离按地球表面的地理距离计算；路线时间、个性化和广告竞价不在核心范围。容量和 SLO 都是面试假设。

核心难点是二维半径搜索。普通经纬度 B-tree 很难直接跳到查询圆内的记录。推荐路径是先用空间索引或离散网格找到一定包含正确答案的候选集，再计算精确距离、过滤、排序和截断。网格命中只是粗筛，不能把同格或相邻格误当成“半径内”。

面试官考察点

第一个信号是先定义正确性。结果必须在半径内、满足过滤条件，并按确定性顺序返回最近 20 个。候选集必须覆盖跨格边界的地点；粗筛后还要做精确距离复核。只查用户所在的一个 geohash，会漏掉隔着格边界但只有几十米的商家。

第二个信号是根据更新模式选索引。静态商家可以从 PostGIS GiST、R-tree 或数据库自带的距离索引开始；读量和全球分片压力上升后，再把地点映射到 H3、S2 或 geohash 单元。直接宣布“用 Redis GEO”没有解释查询圆、精度、热点和真实距离。

第三个信号是识别空间数据不均匀。海洋和乡村几乎为空，城市中心一个格可能很热。按固定经纬度范围平均分片会产生热点；需要按粗粒度空间前缀路由，并让高密度格拆分或加读副本。大半径请求还会跨多个分片，不能假设一次查询永远命中一个节点。

最后要把分页、一致性和故障连起来。按距离分页时，用户坐标、过滤条件、目录版本、最后距离和地点 ID 都属于游标契约。更新或分片超时会改变结果集；强回答会声明 best-effort 还是快照语义，并让部分结果可识别。

回答前需要澄清的问题

• 地点是静态还是持续移动？ 本题更新峰值只有每秒 100 次，适合缓存和异步索引。移动实体需要更短新鲜度、写优化索引和匹配一致性。
• “最近”指直线地理距离还是路线时间？ 本题先按地理距离。路线时间需要道路图和单独的 ETA 服务，通常只对粗筛后的少量候选计算。
• 结果必须完整，还是允许只返回前 20 个近似候选？ 本题要求半径过滤正确，并在已索引目录中返回确定性的最近 20 个；空间格只能生成候选。
• 营业状态多新才可接受？ 地点位置和类别可容忍一分钟级传播，临时营业状态若要求秒级，应独立存储和短 TTL 合并，不能跟低频目录共用一个更新承诺。
• 是否需要深分页？ 附近搜索通常只需前几页。本题允许最多 100 个结果；若要求扫描全部 50 公里结果，应改成异步导出或区域浏览接口。
• 跨分片失败时能否返回部分结果？ 默认返回带 partial=true 和缺失区域的可识别部分结果；严格场景可以失败重试，不能把部分结果伪装成完整最近集合。

30 秒回答框架

“我会把写路径和搜索路径分开。地点主数据写入带版本的目录库，并异步更新空间索引。每个地点保存精确经纬度、粗粒度路由格和搜索分辨率格。查询先验证半径与过滤条件，用 H3、S2、geohash 邻格集合或 PostGIS 距离索引取得覆盖查询圆的候选，再计算精确球面距离、过滤并按 (distance, place_id) 排序取前 20 个。

空间前缀负责路由，高密度格可拆分，跨格查询并行访问有限分片并做全局 top-k 合并。缓存键包含格集合、半径桶、过滤条件和目录版本，更新通过地点版本使受影响格失效。游标绑定原查询与目录快照，避免换位置后继续翻页。最后用边界、日期变更线、极区、热点城市、搬迁、分片超时和缓存陈旧测试正确性与 p99。”

分步骤深入解答

第一步：固定 API、数据模型和不变量

API 只接受有界半径、合法坐标、允许的过滤条件和有限页长。响应返回计算距离、目录版本、结果是否完整以及下一页游标。

GET /v1/places/nearby?lat=&lng=&radius_m=&category=&open_at=&limit=&cursor=

Place {
  place_id, lat, lng, search_cell, routing_cell,
  category, status, hours_version, location_version, updated_at
}

Cursor {
  query_hash, catalog_version, last_distance_m, last_place_id
}

维护四个不变量：结果满足半径与过滤条件；候选阶段不能漏掉圆内地点；最终顺序是 (distancem, placeid)；旧位置版本不能覆盖新位置。经纬度要使用统一坐标系并验证范围，内部距离单位统一为米。

第二步：选择最简单能达标的空间索引

第一版可用支持空间索引的关系数据库。半径查询先用可索引的包围盒缩小集合，再用精确距离函数过滤。官方 earthdistance 文档也明确指出，索引框会包含圆外点，因此需要第二次距离检查。这条“候选超集后精确复核”的规则不依赖具体产品。

当单库无法承受全球 20 万 QPS 或需要明确空间路由时，将地点编码到固定分辨率的 H3、S2 或 geohash 格。查询圆转换为覆盖它的格集合，读取每格倒排列表，再去重和精排。H3 层级可快速改变分辨率，但父子格的地理包含存在近似边界；仍需精确点到点检查。

固定分辨率容易两头受损：格太大时候选放大，格太小时 50 公里查询枚举太多格。可按半径选择少量预定义分辨率，并为地点预计算这些层级，或让大半径走更粗的索引。分辨率选择必须由候选放大率、扇出和 p99 压测决定。

第三步：执行候选查询与全局 top-k

查询服务把圆转换为候选格，确保包含所有相交格而不只包含中心格。对每个格并行读取符合粗过滤的地点 ID 和坐标，设定总截止时间和每分片预算。重复地点按 place_id 去重，随后计算精确地理距离，删除圆外点，再应用权限、状态和类别过滤。

每个分片可先返回本地前 k 个，但必须证明截断安全：若每个分片都按同一最终距离排序并返回至少全局 k 个候选，则任何分片第 k+1 个都不可能进入全局前 k。聚合器用大小为 k 的最大堆合并，时间复杂度与返回候选数线性相关，内存为 O(k)。

大半径或密集城市可能产生过多候选。服务设置最大候选数，但不能静默截断后宣称结果精确。可以自适应提高格精度、把类别过滤下推、分批扩圈直到已找到 20 个且未搜索区域的最短可能距离超过当前第 20 名，或返回明确的资源限制错误。

第四步：分片、热点与容量预算

用粗粒度 routingcell 将格目录映射到分片，而不是按 placeid 随机分片，否则一次空间查询会广播到所有分片。目录服务维护路由表和 epoch。一个查询读取同一 epoch；发现路由变更则重试，避免拆分过程中漏读。

5000 万个地点若每条搜索索引记录连同 ID、坐标、过滤字段和开销按 128 到 256 字节估算，主搜索索引约为 6 到 12 GiB，复制、多个分辨率和数据库开销会继续放大。这个量级可以分区并驻留在读优化节点，但不能据此断言某一种数据库必然够用。

20 万 QPS 若平均扇出 6 个格读取，会产生约 120 万次格读取每秒。缓存和批量读取必须降低后端操作数。热门格按读流量加副本；超密格细分为子格。稀疏格合并只影响存储与路由，查询覆盖仍由几何逻辑决定。

第五步：写入、缓存和一致性

地点服务验证所有权后更新主记录，并递增 location_version。变更事件包含旧格、新格和版本。索引消费者先把新版本写入新格，再移除旧格；读路径按版本去重，所以重放安全，延迟删除也不会让旧记录胜出。搬迁跨分片时不依赖分布式事务保证瞬时原子，而是暴露索引延迟并通过版本收敛。

缓存分两层：格到候选 ID 的缓存，以及完整地点对象缓存。候选缓存键包含索引版本、格、类别和状态桶；最终响应缓存还必须包含坐标桶、半径桶、过滤条件和目录版本，命中率通常更低。更新发布旧格和新格的失效事件，并保留短 TTL 作为丢失失效消息的上界。

open_at 若随分钟变化，不应每分钟清空所有空间缓存。缓存静态候选与营业规则，在查询节点按请求时间求值；只有临时关闭等高时效状态使用小型覆盖层。这样营业状态变化不会重建整个地理索引。

第六步：稳定分页和故障语义

游标对用户坐标、半径、过滤条件和 catalogversion 求哈希，并保存最后的 (distancem, place_id)。下一页拒绝不同查询参数。若支持短生命周期快照，就从同一目录版本读取；若只提供 best-effort，响应必须说明更新可能造成跨页重复或遗漏，并在客户端按 ID 去重。

聚合器给每个分片短于 150 毫秒总目标的截止时间。一个分片超时后，不能称返回结果为全局最近 20 个，因为缺失分片可能有更近地点。面向探索的 API 可返回 partial=true、缺失格和可重试游标；严格调用方收到明确的不可用错误。熔断只隔离故障分片，不能把整个全球索引打开或关闭。

跨区域部署优先在本地读取完整目录副本或按地理区域分区。跨国数据边界影响地点元数据和审计，但公开商家坐标仍要经过来源授权。区域故障时只能故障转移到已有足够新鲜索引的区域，并返回 as_of，不能临时查询主目录全表兜底。

第七步：用几何反例和故障注入验证

正确性测试用暴力全表距离计算作为小数据 oracle。随机生成点和半径，对比索引结果；专门覆盖格边界与角点、经度正负 180 度、极区、半径恰好相等、重复坐标、零结果、20/21 名距离相同及地点跨格搬迁。每次都断言无漏项、无圆外项和稳定 tie-break。

性能测试分别覆盖空旷区域、普通城市和超密热点，测量格扇出、候选放大率、精确距离计算数、缓存命中率、分片 p95/p99、聚合时间与端到端 p99。故障注入包括一个格副本变慢、路由 epoch 变更、失效消息丢失、消费者重放、跨分片搬迁中断和区域切换。

上线采用影子查询：新索引与旧的可信实现同时读取一小部分流量，比较前 20 集合、顺序、距离和缺失率。任何性能提升都不能掩盖 false negative；附近搜索漏掉正确地点是索引正确性故障。

高质量示范回答

“我先把它限定为静态地点检索，不处理移动司机。写端由地点目录保存精确经纬度和单调位置版本，并通过事件更新空间索引。读端不对经纬度做全表距离排序，而是把查询圆转换成一组完全覆盖它的候选格。可以先用 PostGIS 的空间索引；到全球读量需要空间路由时，再使用 H3、S2 或 geohash。格只负责粗筛，候选必须计算精确地理距离，过滤后按距离和地点 ID 稳定排序。

我会用粗格路由到分片，高密度格可拆分，热门格加读副本。查询并行读取有限分片，每个分片返回本地 top-k，聚合器合并全局 top-k。候选太多时扩大过滤下推或逐圈搜索；不能静默截断。缓存格候选和地点对象，键带索引版本，地点搬迁同时失效旧格与新格，消费者用位置版本抵抗重放。

游标绑定坐标、半径、过滤条件、目录版本和最后的距离/地点 ID。分片超时会让全局最近结果无法证明，因此探索接口标记 partial 并列出缺失格，严格接口失败。验证时我用暴力距离计算做 oracle，随机对比并重点攻击格边界、日期变更线、极区、同距离 tie、搬迁和路由变更；再在热点城市与故障注入下验证 150 毫秒 p99。”

常见错误

• 只查中心 geohash → 查询圆跨越格边界时漏掉近邻 → 读取所有相交格并做精确距离复核。
• 把相邻格当成半径内 → 格的外角可能远超半径 → 网格生成候选，球面距离决定最终包含。
• 按地点 ID 随机分片 → 每次附近搜索广播全局 → 按粗空间前缀路由，并为热点格拆分或复制。
• 固定一种最细分辨率 → 小半径候选少但大半径格扇出爆炸 → 用少量受控层级并依据测量选择。
• 缓存只包含经纬度 → 不同半径、类别或目录版本互相污染 → 把完整查询契约和版本纳入键。
• 地点搬迁先删后加 → 处理失败时地点暂时消失 → 先写带新版本的新格，再删除旧格并按版本去重。
• 分片超时仍返回“最近 20 个” → 缺失分片可能包含更近结果 → 标记部分结果或让严格请求失败。
• 只测纽约市中心 → 边界、极区和稀疏区域错误被掩盖 → 用暴力 oracle、随机属性测试和专门几何反例。

追问及应对

追问一：为什么不直接用 PostGIS 完成全部需求？

可以先这样做。空间数据库已经提供正确的索引候选和距离函数，团队能以更少组件获得可靠版本。只有当 20 万 QPS、全球路由、热点隔离或成本测量证明单一数据库拓扑无法达标时，才引入离散格索引和独立搜索层。迁移时用影子查询比较完整结果，不能只比较延迟。

追问二：如何保证查询格不会漏掉圆内地点？

使用库提供的圆覆盖或多边形覆盖操作，而不是自行猜相邻格数量。覆盖集合可以包含多余格，但不能缺少与圆相交的格。读取后用精确距离删除 false positive。测试用全表 oracle 对随机圆、格角、日期变更线和极区做集合差异；任何 false negative 都阻断发布。

追问三：如果 50 公里查询覆盖成千上万个细格怎么办？

切换到预计算的更粗层级，让格数量保持有界，再依赖类别下推和精确距离复核。也可以逐圈扩展：已取得 20 个结果且未访问区域到中心的最短可能距离大于当前第 20 名时停止。大半径仍超过资源预算就拒绝或转异步，不能悄悄少查。

追问四：如何扩展成附近司机匹配？

先承认问题已经改变。司机位置需要秒级写入和过期，索引按城市或格分区，更新要覆盖乱序与幽灵司机；候选检索后还要按 ETA、司机状态和公平性排名。最终分配必须通过带版本的条件更新或单一所有者防止双重派单，不能依赖最终一致的空间索引完成占用。

追问五：营业状态每分钟变化会不会让缓存失效风暴？

把静态空间候选与动态状态分层。格缓存保存地点 ID、位置和类别；查询时从营业规则计算 open_at，临时关闭由小型实时覆盖层提供。只有位置或类别变化才失效空间候选。监控覆盖层新鲜度，缺失时返回状态未知或采用业务批准的降级规则。