专业书籍精读 · System Design Interview 卷二 · 第 3 章
System Design Interview Vol 2 · Ch 3 · Alex Xu & Sahn Lam · 2022
你在路口掏出手机打开地图，两秒钟街道就铺满屏幕；再点一下导航，它说「23 分钟到，走高架快 6 分钟」。这一章就是从零把这套东西造出来：地图是怎么出现的、路是怎么找的、那句「23 分钟」是哪来的。
这个每天十亿人用的系统，里头大部分东西都不是现算的。你看到的地图，是一堆早就画好、搁在硬盘上的小方块图片——跟你是谁、几点打开，全无关系。真正必须现算的只有一件事：路上这会儿堵不堵。
两个「装不下」。第一，整张世界地图要是做成一张图，它大到没有哪台手机下载得完；第二，全世界的路连起来是一张上亿个路口的大网，想在里面找最短路，这张网塞不进一台机器的内存。难处不在算得慢，在东西太大、搬不动。
地图切成方块。把世界地图像切蛋糕一样切成一堆小方块，每块单存一张图。你屏幕就那么大，一次只要挨着你的那几块，几百 KB 就够，其余几百万块跟你无关。而且每种精细度各存一套：看整个省份时给你粗的那套（只有高速和大城市），放大到街区才换上细的。
找路也一样，先看大地图再看小地图。人问路就这么干：出门先琢磨怎么上高速（要看细节），上了高速一路开到目标城市（这一段只需要一张很粗的地图，没人关心沿途每条小巷），下了高速再看街道（又换回细节）。机器用的是同一招：中间那一大段只加载「只画了高速的粗地图」，所以它一辈子都不必把整张路网搬进内存。
堵不堵，是所有人的手机一起告诉它的。每台开着地图的手机匿名回报一句「我这会儿移动得多快」。成千上万个这样的点拼起来，就是一张实时路况图。Google 2009 年公开讲过这件事，他们自己的说法是：参与的人越多，结果对每个人就越准。
一句话：不变的东西提前画好、搬到离你最近的机房；会变的东西才现算。地图一年变不了几回，所以它能当静态图片发出去，便宜得几乎不花钱；路况每分钟都在变，所以它必须实时算，也只有它值得花这份钱。代价也得说清：那份好用的实时路况，是用所有人的位置换来的——做过匿名处理，但不等于没有代价。
地图 = 一堆提前切好的方块图片 + 一张分了粗细层次、按需加载的路网 + 一份所有人共同贡献的实时路况。难点从来不是算法，而是怎么把大到搬不动的东西切小。
想进到具体机制、量级和示意图？ → 切到精读版
这一章造的不是「一个算最短路的服务」，而是一条把静态与动态彻底分开的流水线：地图几何与路网图都在离线阶段被切成瓦片（tile）烘好，当静态文件经 CDN 发给十亿人；只有路况与 ETA 值得实时计算。记住一句反直觉的话——Google Maps 的工程难点不在 Dijkstra，而在把装不下的东西切小、按需加载；同一个「瓦片」思想在这一章被用了两次，一次用在显示，一次用在路由。
卷二第 3 章，紧接 Ch1「附近服务」与 Ch2「附近的好友」——三章都是地理题，但前两章只回答「谁在附近」，这一章第一次要画出地图本身、还要在路网上找路，是这组里最重的一道。对应现实里 Google Maps、Apple 地图、高德，以及 OpenStreetMap + OSRM 这一类开源栈。
作者把需求缩到三件事：位置上报、导航（含 ETA）、地图渲染。难的不是任何一件的逻辑，而是它们各自的量级彼此差了几个数量级——用一套方案去伺候它们必然失败。几个具体数字把难度摆出来：
4²¹ ≈ 4.4 万亿张；每张 100KB 就是约 440PB，把 0–21 级加起来再多三分之一（等比和），接近 590PB。但地球表面大半是海洋、沙漠、无人区——不存没人看的地方，量级就落回几十 PB。这是本章第一个判断：存储问题是靠「别存」解决的，不是靠压缩。不解决会怎样？你会得到一个每次打开都要实时渲染、每次导航都要遍历全球路网的系统：成本和延迟都不可能成立。
先用墨卡托投影把球面摊成一张正方形世界图。级别 0 是整张世界 = 1 张瓦片；每升一级，每边切两半，所以第 z 级有 4ᶻ 张瓦片——这就是「瓦片金字塔」。客户端拿自己的视口中心经纬度和当前级别，自己算出该要哪几张瓦片的 URL，直接向 CDN 取；一屏大约 6–10 张，传输量在百 KB 级。
这里有个容易被跳过的设计后果：渲染这条路上根本不需要一个「瓦片服务」。没有服务端逻辑、不查数据库，就是一堆可被内容寻址的静态文件。于是同一片城区被千万人反复看时，缓存命中率可以做到极高，CDN 几乎吃掉全部流量，源站只在地图数据更新（通常以周 / 月计）时重新烘一批。十亿用户的读量，被一条「静态化」的判断消掉了绝大部分。
栅格瓦片是服务端画好的图片，客户端只管贴图；矢量瓦片传的是几何数据（这条路从哪到哪、属几级路、叫什么名），由客户端现场绘制。矢量的好处是一份数据能覆盖连续缩放与旋转——放大时路线与文字仍然锐利，不必为每个中间比例重新下载；体积更小，还顺手解决了夜间模式与多语言标注。代价是客户端得有绘图能力（移动端 GPU 本身够用），首屏多一次解析与绘制。Google Maps 在 2010 年 12 月的 Android 5.0 版本上公开转向矢量绘制，同时开始缓存常去区域、让弱网下也能用。
判据一句话：要不要连续缩放，决定渲染该放在哪一端。
把路网当图：路口是节点、路段是边、边权是通行时间，导航就是求最短路。但直接在洲际路网上跑 Dijkstra，卡住的地方不是算法复杂度，而是图装不进内存、也不该装。
做法是把「瓦片」思想搬过来一次：离线流水线把路网切成路由瓦片（routing tile），并做成若干级——细的那级含所有街巷，粗的那级只留高速与主干道，瓦片之间互相记着「我和哪些瓦片相连」。最短路服务从起点所在的细瓦片开始搜，一离开起点足够远就切到粗瓦片，长途的中段只在高速层上走，接近终点再落回细瓦片。于是加载量跟路线长度成比例，而不是跟地球大小成比例。这正是人问路的顺序：先看门口街道，上了高速只需要一张省级图，下高速再换回街道。
A* 这类启发式能剪掉方向明显不对的搜索，但真正的数量级收益来自分层与预处理，不是启发函数。工业界更激进的一手叫收缩层次（contraction hierarchies，CH）：离线按重要性逐个「收缩」节点、补上捷径边，查询时只往上走，洲际路线能压到毫秒级，开源路由器 OSRM 就是这么做的。代价很实在：预处理与边权绑定——边权一变（实时路况来了）就得重算，所以实时路况一般不直接塞进 CH，而是在它之上叠一层修正，或换用为「权重可换」而设计的变体。
客户端把位置攒成批（约 15 秒一发）上报；位置服务把它写进 Cassandra 这类高写入吞吐的存储，同时投进 Kafka，下游几路消费者各取所需：一路把同一路段上的若干匿名速度点聚合成「这段现在多快」，得到实时路况；一路喂 ETA 模型；还有一路做路网数据的长期修正（新修的路、标错的单行道）。Kafka 在这里的作用是「一次写入、多方派生」——这也是全书反复出现的模式。
ETA 不是「距离 ÷ 限速」，而是一次预测：历史上这个时段这条路多快，叠上现在的实测。Google 与 DeepMind 在 2020 年公开的做法，是把路网切成Supersegments（共享车流量的相邻路段簇），用图神经网络预测通行时间。
还有个容易漏掉的结论：导航在工程上是一条持续的会话，不是一次请求。客户端全程上报，服务端发现前方路况变差就重算、下发新路线——所谓「自适应重算」。
这一章的灵魂是把三条路径按「变不变」分开定价：地图几何几乎不变 → 烘成静态文件、越靠边缘越好；路网图变得慢 → 离线预处理换查询延迟；路况每分钟都变 → 只有它配得上实时计算。
表 1 · 地图渲染：栅格瓦片 vs 矢量瓦片
| 栅格瓦片（服务端出图） | 矢量瓦片（客户端绘制） | |
|---|---|---|
| 传什么 | 画好的位图，客户端只贴图 | 几何 + 属性，客户端现场画 |
| 连续缩放 / 旋转 | 每个比例都得另取一套，中间态会糊 | 一份数据覆盖连续缩放与旋转，文字始终锐利 |
| 传输量 | 较大，且每级独立 | 较小，可跨级复用 |
| 换皮（夜间 / 多语言） | 要重烘整套瓦片 | 同一份几何换画法即可 |
| 代价 | 存储与回源带宽 | 客户端算力与首屏绘制；实现复杂 |
| 选它当 | 客户端很弱、或出图极度定制（卫星图、地形底图） | 移动端主流选择：要连续缩放、要省流量、要离线缓存 |
表 2 · 路由：四种做法的预处理 / 查询 / 动态性三角
| 做法 | 离线预处理 | 查询代价 | 对实时路况 | 适用 |
|---|---|---|---|---|
| 全图 Dijkstra | 无 | 随图规模爆炸，洲际不可用 | 天然适应（边权随便改） | 单城小图、教学 |
| A* 启发式 | 无 | 比 Dijkstra 少搜很多，但仍随距离线性退化 | 天然适应 | 中等规模、边权常变 |
| 分层路由瓦片 | 中：切瓦片、建层级（以周 / 月为节奏重烘） | 与路线长度成比例，内存占用可控 | 较好：瓦片内边权可更新 | 本章方案：全球规模 + 要跟路况 |
| 收缩层次 CH | 重：全图收缩 + 捷径边 | 毫秒级，最快 | 差：边权一变就要重算预处理 | 静态权重的离线 / 开源路由（如 OSRM） |
表 3 · 位置上报：每秒直报 vs 批量上报
| 每秒一报（HTTP 长连接） | 攒 15 秒批量发 | |
|---|---|---|
| 写 QPS（350 万并发导航） | 约 350 万/秒 | 约 23 万/秒 |
| 手机电量 / 流量 | 最先垮的是电量 | 显著省电省流 |
| 路况新鲜度 | 最新 | 最多滞后 15 秒——对路况聚合完全够用 |
| 结论 | 路况是统计量而非某人的精确轨迹，用新鲜度换成本明显划算；真正不能滞后的是「偏离路线 → 重新规划」，它走另一条更快的通路。 | |
对着面试或架构评审，这一章最值钱的不是背出 A*，而是开口第一句就把静态与动态切开：十亿 DAU 的读量大头是静态瓦片，应该死死压在 CDN 上；真正要花服务端钱的只有位置写入与路况 / ETA。谁先说出这条分界线，谁就已经答对了一半。
真实系统的对应也很清楚：Google Maps（瓦片金字塔 + CDN + 矢量客户端渲染 + 众包路况）、Mapbox（把矢量瓦片做成了事实标准 MVT）、OpenStreetMap + OSRM / Valhalla（开源路由，CH 与分层两条路线的公开实现）、Uber（ETA 预测与派单路径）。
① 一句话：这是一条把静态与动态分开的流水线——地图与路网离线烘成瓦片经 CDN 发出去，只有路况 / ETA 实时算。
② 需求缩到三件事：位置上报、导航（含 ETA）、地图渲染；它们的量级差几个数量级，必须各用一套方案。
③ 瓦片金字塔：第 z 级 4ᶻ 张；第 21 级约 4.4 万亿张 ≈ 440PB，靠「不存没人看的地方」压回几十 PB。
④ 客户端能自己算出瓦片 URL，所以渲染路径上没有服务，只有 CDN 上的静态文件——十亿读量的大头就这样被消掉。
⑤ 栅格 vs 矢量：要不要连续缩放与旋转决定渲染放哪端；移动端主流是矢量，还顺带解决换皮与离线。
⑥ 路由的关键不是算法而是分层 + 按需加载：中段只走高速层，加载量随路线长度而非地球大小增长。
⑦ CH 能把查询压到毫秒级，代价是预处理与边权绑定，实时路况下要另叠修正。
⑧ 上报攒 15 秒批量发：写 QPS 从约 350 万降到 23 万，最大的收益是手机电量；路况是统计量，滞后 15 秒无妨。
⑨ 位置进 Kafka 后「一次写入、多方派生」：实时路况、ETA 模型、路网修正各取一路。
⑩ 导航是持续会话而非一次请求：全程上报、路况变差即重算下发；ETA 是预测问题（Google / DeepMind 的 Supersegments + 图神经网络）。