专业书籍精读 · System Design Interview 卷一 · 第 13 章
System Design Interview Vol 1 · Ch 13 · Alex Xu · 2020
你在搜索框里刚敲下两个字母，下面立刻掉出一串候选词，点一下就走——这就是搜索自动补全。《系统设计面试》第 13 章要你把它从零设计出来。它看着最不起眼，却是全书里「读」和「写」悬殊得最厉害的一道题。
你以为自动补全是「一边打字一边帮你搜」。恰恰相反——它从来不搜。真要现搜一次，人早把整个词打完了。它做的是查一张早就排好的表：你敲的每一个字母，只是去表里认领一份写好的答案。
难在量。一千万人每天各搜十次，就是一天一亿次搜索；可一次搜索平均要敲二十个字母，而每敲一下都是一次请求——后台一天就要接住二十亿次，平均每秒两万多次，高峰翻倍。而且每一次都得在一眨眼之内回来，慢一点下拉框就会一顿一顿地跳。让数据库现去几十亿条历史搜索里翻「以 tr 开头、最热门的五条」，一次都嫌慢，何况每秒两万次。
两个关键动作。
第一，把所有历史搜索按字母排成一棵岔路树：敲 t 走一条岔路，再敲 r 又分一次岔——树上每个路口就代表一个开头。这样「走到 tr 这个路口」只跟你敲了几个字母有关，跟库里存着几亿还是几十亿条完全无关。
第二步才是真正的窍门：在每个路口提前立一块路牌，写死「从这儿往下走，最热门的就是这五条」。于是查询彻底不用再往下走——走到路口，把牌子上的字抄给你就完事。牌子上写什么，是每周夜里把上一周的搜索日志重新统计、重排一遍写上去的，和白天的查询根本不打照面。
代价也很清楚：牌子是上周立的，昨天才火起来的新词今天补不出来——想让突发热词几分钟内进候选，就得另搭一条实时通道，复杂度和成本一起翻上去，多数场景并不值得。
自动补全不是搜索，是查表：把热门搜索排成一棵按字母分岔的树，在每个岔路口提前把「最热的五条」写死；白天只管取牌子，重写牌子的活留给每周一次的离线任务。
想进到具体机制、量级和示意图？ → 切到精读版
这一章教你把一个看起来是「实时搜索」的功能，彻底改造成一次预计算查表。核心是三步：用前缀树（trie）把「按前缀定位」的代价和数据总量脱钩；在每个节点上预存 top-k，把查询从「遍历子树再排序」压成 O(1) 取值；再把系统劈成离线重建与在线只读两条互不干扰的路径。学会这三步，你拿到的是一整类问题的通用套路：极端读多写少、且延迟预算只有几十毫秒。
本章属于卷一 Part II「系统案例」，紧接第 12 章聊天系统之后。它把读写比推到了极端：写路径可以离线到以周计，读路径却要顶住每秒数万次、且每次都在百毫秒内返回。它对应各家的搜索框，也通向第 14、15 章共用的那套骨架——离线批量算好、在线只读服务。
先把量级算清楚，否则一切讨论都是空谈。按书里的假设：1000 万日活、人均每天 10 次搜索，即一天 1 亿次搜索；一条查询平均 20 个字符，而每敲一个字符就发一次补全请求——请求量被放大 20 倍，约 20 亿次 / 天 ≈ 24,000 QPS，峰值按两倍估约 48,000 QPS。书中还援引 Facebook typeahead 的公开说法：延迟要压在 100 毫秒上下，慢了就会出现肉眼可见的卡顿。
两个数字并排一放，问题的形状就出来了：「写」——有人搜了一个新词——晚几小时甚至几天生效都无所谓；而「读」要在数万 QPS 下、每次几十毫秒内，从几十亿条历史查询里挑出前缀匹配且最热的 5 条。
不解决会怎样？最直觉的做法是建一张 frequency(query, frequency) 表，再 SELECT ... WHERE query LIKE 'tr%' ORDER BY frequency DESC LIMIT 5。这在几万行上毫无问题；到几十亿行，前缀 LIKE 要扫掉索引一大段、再对结果集全量排序，单次几百毫秒起步——乘上 24,000 QPS，数据库当场躺平。所以这一章真正的命题不是「怎么查得更快」，而是「怎么让查询根本不必去查」。
trie 把所有历史查询按字符逐层分叉存起来：往下每层吃掉一个字符，从根走到某节点的路径就是一个前缀，节点上挂着以它为前缀的查询与频次。英文小写下每个节点最多 26 个孩子。
第一个好处是走到前缀节点的代价只跟你敲了几个字符有关：敲 p 个字符走 p 步，记作 O(p)——库里存 100 万条还是 100 亿条都一样。再加一条工程约束：用户几乎不会输入超过 50 个字符，把最大前缀长度截在这个量级，O(p) 实际上就是常数。
但只走到这一步，trie 还救不了你。找到 tr 这个节点之后，你要的是「以 tr 开头、最热的 5 条」，这意味着遍历它下面整棵子树收集候选、再按频次排序。设子树里有 c 条查询，代价是 O(c + c log c)——前缀越短，c 越大。用户敲下第一个字母 t 的那一刻，c 可能是上千万。最该快的那一次查询，恰恰是最慢的一次。
转折在这里：既然「以 tr 开头最热的 5 条」在两次离线重建之间根本不会变，为什么要当着用户的面现算？于是在每个节点上直接存一份 top-5。查询退化成两步——沿前缀走到节点（常数步）、把存好的列表返回（一步），整体 O(1)，与数据规模彻底无关。
代价有两笔。一是空间：每个节点多存 5 个引用，内存占用显著上升，这也是后面必须分片的直接原因。二是写放大：某条查询的频次一变，从它到根这条路径上每个祖先节点的 top-5 都可能要重排——一次更新要往上改 p 个节点。这笔账在线上付不起，于是逼出了下一步。
既然更新贵、而候选列表又不需要秒级新鲜，那就干脆不在线更新 trie。系统被劈成互不干扰的两半：
离线数据通道——查询日志持续落盘，聚合器按周把它压成一张 (query, frequency) 汇总表，构建 worker 依据它从头造一棵全新的 trie，造完整体替换线上快照。新旧两份在切换瞬间并存，所以重建全程不影响线上查询。
在线查询通道——击键 → 负载均衡 → API 服务 → 内存里的 trie 缓存直接返回 5 条；只有未命中（刚扩容、刚重启）才回落到持久化的 Trie DB。
Trie DB 有两种常见落法：文档型（如 MongoDB）把整棵 trie 序列化成一份文档、重建时整份替换；或者键值型——把 trie 压平成哈希表，键是前缀、值是那份 top-5。后者值得琢磨：一旦每个节点的答案都预存好，树形结构在读路径上已经没用了，剩下的只是一张 前缀 → 五条候选 的映射。trie 是构建期的脚手架，不是服务期的必需品。
这三条不动架构，却直接决定成本。
浏览器缓存。补全结果在小时级内几乎不变，那就让浏览器自己缓住。书里给的实证是 Google 的补全响应带着 cache-control: private, max-age=3600——私有、缓一小时：同一用户一小时内重复敲同样前缀，请求根本不出浏览器。
AJAX 请求。异步发出、只局部更新下拉框，不刷新整页——这是「每敲一键发一次请求」能被接受的前提。
日志采样。频次统计只为排序，就没必要每次请求都记：每 N 次只记 1 次。日志量降到 N 分之一，而热门查询之间的相对排序基本不受影响——典型的「用统计精度换存储与带宽」。
「按前缀找最热的几条」有四种典型做法，代价差得很远：
表 1 · 四种前缀查询方案对比
| 做法 | 单次查询代价 | 适用规模 | 主要代价 |
|---|---|---|---|
| 关系表 + LIKE 'p%' | 索引前缀扫 + 全量排序，百毫秒级 | 几万行 / 内部工具 | QPS 一高就打穿数据库 |
| 倒排索引全文检索 | 十毫秒级，但它是为「搜文档」设计的 | 确实需要中间词 / 模糊匹配时 | 资源重；对「每键一查」仍偏贵 |
| 朴素 trie（不预存） | O(p + c + c log c)，前缀越短越慢 | 演示 / 小词表 | 最该快的短前缀恰恰最慢 |
| trie + 节点 top-k 预存 | O(1) | 十亿级词表、数万 QPS | 内存显著上升；更新必须离线 |
选定方案后，还有三个会被面试官追问的选择点：
表 2 · 三个选型点：什么场景该选哪个
| 选择点 | 选 A | 选 B | 怎么选 |
|---|---|---|---|
| 更新节奏 | 每周离线重建：简单、稳、线上零写压力 | 流式近实时：突发热词分钟级可见 | 默认 A。只有「热词本身就是产品价值」（新闻、大促）才上 B，代价是一整条流处理链路 |
| Trie DB 形态 | 文档型整份序列化：契合树形，重建即整份替换 | KV 扁平化为 前缀 → top-5：读路径最简、最好水平扩 | 只做前缀补全就选 B；若还要按子树做别的计算，留着树形选 A |
| 分片规则 | 按首字母切 26 片：实现最简单 | shard map manager 按历史分布切 | 务必选 B——字母分布极不均，等分必出热点 |
分片这条最容易答错。单机放不下整棵 trie 之后，第一反应是按首字母分 26 片，不够就按前两个字母分 676 片；但字母频率天然倾斜，等分必有分片先被打爆。正解是引入 shard map manager——按历史分布维护一张「前缀区间 → 分片」的映射，它本身很小，可缓存在每台 API 服务上。
这一章的价值不在「trie 怎么写」，而在它把一类问题的解法固定了下来：当读远多于写、且答案在两次更新之间不变时，就把答案预先算好，把系统劈成离线重建 + 在线只读两条路径。 这个骨架后面会反复撞见——第 11 章信息流的写时扇出、第 14 章视频的转码预生成，本质是同一招。
书里还给了两条延伸：不同国家热门查询不同，可按国家分别建 trie、放到 CDN 就近服务；多语言则是把节点从 26 个字母扩到 Unicode 字符。
面试里的评分点也很集中：算不算得出「每键一请求」的 20 倍放大、说不说得出朴素 trie 恰恰在短前缀上最慢、分片时会不会掉进「平均分 26 片」的坑。
LIKE 前缀查询——补全的正确心智是查表。① 问题形状：1000 万 DAU × 每天 10 次搜索 × 每条 20 字符，每键一请求把量放大 20 倍 → 约 24,000 QPS、峰值约 48,000，且要在 100 毫秒内返回。
② 核心命题不是「怎么查得更快」，而是让查询根本不必去查——补全是查表，不是搜索。
③ trie 把「按前缀定位」的代价降到 O(p)，与库里数据量无关；再截断最大前缀长度，实际上就是常数。
④ 但朴素 trie 在短前缀上最慢（要遍历整棵子树再排序）——而那恰恰是最该快的一次。
⑤ 关键一招：每个节点预存 top-5，查询变 O(1)；代价是内存上升与写放大（一次更新要改一路祖先）。
⑥ 因此系统劈成两条路径：离线按周重建 + 整体替换快照、在线只读内存缓存。预存之后树形在读路径上还能退化成 前缀 → top-5 哈希表——trie 只是构建期脚手架。
⑦ 三个便宜优化：浏览器缓存（Google 用 max-age=3600）、AJAX 局部更新、日志采样。
⑧ 分片别按首字母等分：字母分布倾斜，要用 shard map manager 按历史分布切。已知局限：实时热词、拼写纠错与个性化都不在这套设计里。