设计附近服务

一句话

你以为「附近的餐厅」是一道搜索题，其实是一道降维题：这一章从头到尾只在做一件事——把经纬度这对二维坐标压成一个一维的键（geohash 字符串，或 S2 的 64 位整数），好让 B-tree 索引、键值存储、缓存这些「只会按一个键排队」的老工具重新变得可用。围绕这条主线，本章还甩出两个反直觉的结论：半径不是查询参数，是索引精度参数；数据只有几十 GB 而读 QPS 有 5000，所以该加副本、不该分片。

Glossary · 术语表

坐标

本章是卷二的开篇，也是全书「地理三连」的第一环：Ch1 附近服务（不会动的店）→ Ch2 附近的好友（每几秒换一次位置的活人）→ Ch3 Google Maps（路网与导航）。三章共用同一套空间索引，变的只是数据的更新频率——所以这一章是地基，后两章都建在它上面。现实里它对应 Yelp / 大众点评 / Google Maps 的「附近」标签页，以及任何「按位置找东西」的需求。

这章要解决什么

先把规模摆出来（书里的口径）：1 亿日活、2 亿家商户，假设每人每天搜 5 次，搜索 QPS = 1 亿 × 5 ÷ 86400 ≈ 5000。功能上只要三件事：按（经度、纬度、半径）返回附近商户；商户主能增删改自己的店，且不要求实时生效（第二天可见就行）；用户能看商户详情。

题眼藏在「不解决会怎样」里。最朴素的写法是一行 SQL：WHERE lat BETWEEN … AND lng BETWEEN …。它在 2 亿行上跑不动，原因不是没建索引，而是两个索引用不到一块儿去：数据库通常只能挑一个索引走，比如先按纬度筛出一条横跨整个地球的窄带，再逐行回表核对经度。中间结果动辄百万行，而这题的延迟要求是几百毫秒。所以必须在查询之前，就把二维的邻近关系预先编码进某个一维的键里。

核心内容，讲透

一、先把二维压成一维：所有方案的共同形状

最容易想到的补救是均匀网格：把地图切成边长固定的方格，每家店记下自己在哪一格。它确实做到了降维，但格子里的数量极不均匀——曼哈顿一格能塞几万家，太平洋上一格空着。

真正好用的方案都有同一个形状：把平面递归地对半切，再把「每一刀切在哪边」按顺序写成一串码。二维的邻近关系于是被编码进了一维键的前缀里——共同前缀越长，说明两点被同一批刀切在了同一侧，也就越近。

二、Geohash：半径其实是精度旋钮

Geohash 是上面那把刀的标准实现：经度区间与纬度区间交替对半分，每分一次记一位，再把二进制串按 5 位一组编成 base32 字符——编码每长一个字符，格子面积缩到约 1/32。量级：码长 4 约 39 km × 20 km，码长 5 约 4.9 km × 4.9 km，码长 6 约 1.2 km × 0.6 km。

于是「半径 → 精度」就变成一张查表。书里给的对应是：0.5 km → 6、1 km → 5、2 km → 5、5 km → 4、20 km → 4。这正是那句「半径不是查询参数，是索引精度参数」的含义：你不拿半径去算距离，你拿它挑格子大小，先把候选集从 2 亿缩到几百，距离留到最后一步再精确算。

书里点名了两个必踩的坑，都必须当场解决：

① 边界问题。两个点可能只隔几米，却被一刀切在两个格子里，前缀完全不同——极端情况是跨赤道或本初子午线，第一个字符就不一样。所以「前缀相同 ⇒ 位置相近」成立，但反过来「前缀不同 ⇒ 位置远」是错的。解法很朴素：查询时把自己这一格 + 周围 8 格一起取，共 9 格。

② 凑不够数。半径内的商户太少（郊区、或者叠加了「营业中」这类过滤之后）。解法同样朴素：去掉编码的最后一个字符，格子放大约 32 倍再查一次，不够就再去一个字符。

三、四叉树：让格子跟着密度走

Geohash 的格子是「按地球切」的，四叉树的格子是「按数据切」的：从整张地图起步，只要某个方块里的商户超过阈值（书里取 100 家），就把它切成四块，递归到每个叶子装不超过 100 家为止。曼哈顿会被切得很深，太平洋一个节点就够。好处是取回来的候选数量天然均匀，而且天然支持「返回最近的 k 家」——geohash 只回答「这格里有谁」，要 k 近邻还得自己一圈圈往外扩。

关键区别是：它不是数据库里的表，而是每台 LBS 服务器启动时在内存里建的一棵树。书里的内存账：2 亿商户 ÷ 100 = 200 万个叶子，内部节点约为叶子的 1/3、约 67 万个；每个叶子存 100 个 8 字节商户 id 即 800 字节，合计约 1.71 GB——一台机器装得下。

代价全出在更新上：商户增删要动树形，实时更新得加锁、很难做对。书里的选择是每晚整棵重建 + 灰度上线，一次只把一小批服务器摘出轮转、重建、放回——因为建一棵 2 亿商户的树是分钟级的事，这期间那台机器不能服务。这也解释了需求里那句「商户更新不要求实时生效」：那条让步正是为了买下这个方案。

四、S2 与希尔伯特曲线：另一条一维化的路

S2 是 Google 的球面网格库，走的是第三条路：先把球面（而不是把地图当平面）投到一个外接立方体的六个面上，再用希尔伯特曲线——一条不断折返、走遍所有格子且相邻格子在曲线上也相邻的路径——把二维格子串成一条线，每个格子拿到一个 64 位整数 cell id。降维的目的和 geohash 一样，只是刀法更讲究：它在球面上做，避免了把地球当平面的形变。

它独有的能力是 region cover：任意形状的一片区域（一个行政区、一个配送范围）都能被一组大小不一的格子覆盖——大格子填中间，小格子贴边缘。这让「用户有没有进出某片不规则区域」这类地理围栏（geofencing）判断变得简单。代价是概念与实现都复杂得多，不是白板上现推得出来的东西。

五、存储、缓存与整体架构：这题反着来

表结构简单到出乎意料：一张 business 存商户详情，一张 geospatial_index 做空间索引，只有两列——geohash 和 business_id，一家店在一个 geohash 下就是一行。查询就是 WHERE geohash IN (那九个格子)。

接着书给出一个跟卷一前几章都反着来的判断：这张表根本不用分片。两列、2 亿行，几十 GB 量级，一台像样的机器放得下；真正的压力是 5000 QPS 的读，不是容量。所以答案是加读副本——写走主库，读扇到 N 台副本，加机器就线性抬读吞吐。容量和流量是两个独立的旋钮，别拿分片去拧流量那个。

缓存这一层有个极容易写错的细节：缓存键必须是 geohash，绝不能是用户的经纬度。用户坐标精确到小数点后六位、走一步就变，拿它当键命中率恒为 0；而 geohash 是「一格」，同一格里的所有人共享同一份答案——这是把缓存从摆设变成主力的一行之差。缓存两类：geohash → 商户 id 列表，以及 business_id → 商户详情。

整套架构因此长成两条几乎不相干的路：读路（用户 → LBS → Redis → 索引表读副本）与写路（商户主 → 商户服务 → 主库 → 异步复制到副本）。LBS 无状态、只读，按峰值横向加机器即可；商户主的写 QPS 低到可以忽略。复制滞后带来的「改完没马上生效」，正好落在需求允许的范围内。

关键权衡与选型

表 1 · 四种做法的分野

表 2 · 决赛圈：geohash vs 四叉树（本章的主对照）

表 3 · 这一题为什么不分片

把三张表拧成一句判据：商户会变、要半径查询 → geohash；密度悬殊、要 k 近邻 → 四叉树；要覆盖不规则区域 / 做地理围栏 → S2。而无论选哪个索引，最后一步都躲不掉：候选集取回来之后，必须按真实距离精确算一遍再排序——格子只负责把 2 亿缩到几百，不负责给答案。

为什么重要 / 落到真实系统

这一题的价值在于它示范了一个通法：当查询维度和索引结构对不上时，先想办法降维，而不是换数据库。同一手法反复出现——全文检索把文档降成词的倒排表，向量检索用 LSH 把高维向量降成哈希桶。geohash 只是它在地理上的一个实例。

面试里，能主动说出「这里不该分片，该加副本」和「缓存键得用 geohash 不能用经纬度」这两句，比背下 geohash 的编码规则值钱得多——它们证明你在算负载，而不是在背方案。

易错点与争议

• 把九宫格的结果当最终答案：格子是方的、范围是圆的，九格里必然混进半径之外的店。最后一步的精确距离过滤不能省——这是本章最常见的翻车点。
• 把「前缀相同 ⇒ 相近」反过来用：前缀不同完全可能只隔几米。整个边界问题就是从这个误解里长出来的。
• 把某个精度当固定答案：「用 5 位 geohash」不是结论，是「半径 → 精度」表里的一行；半径一变就得换。
• 条件反射式分片：这题数据小、QPS 高，分片是过度设计。判据是容量而不是流量。
• 忘了排序与分页：候选集拿回来还要按距离或评分排序、分页；「营业中」「评分 4 星以上」这类过滤也只能在这一步做——空间索引只按位置筛，别的一概不管。
• 隐私与合规：用户位置属于个人数据，GDPR / CCPA 下既要能删，也常要求留在本区域内。书里把它写进了非功能需求却没展开，面试里补一句是加分项。
• 时代局限与争议：本书把 geohash 当默认解，而工业界今天更常见的是 S2 与 H3；PostGIS、Elasticsearch 这类现成的空间索引也让「自己造一张 geohash 表」不再是唯一选项。另外，四叉树「每晚重建」一旦碰上要求实时更新的数据就直接不成立——下一章「附近的好友」正是如此，那里的位置每几秒就变一次。

要点