Lesson 0017 · 系统设计 · Phase 5 进阶案例 · 细节版
大案例 V：搜索自动补全（Typeahead）
与你的 Mission 的关系
补全是「用预计算换运行时」思想的最佳教学案例：查询期零计算、一切在离线管道算好。这种「重 offline 轻 online」的思路在工作中无处不在（报表、风控名单、推荐召回）。同时它是 P99 延迟工程的最小完整案例。
件 ①需求表（Step 1）
| 类别 | 内容 |
|---|---|
| 功能（MVP） | 输入前缀 → 返回 top-10 候选短语（按近期搜索热度排序）。扩展提一句：个性化重排、纠错（did you mean）、热搜榜 |
| 非功能 | P99 < 50ms（每个按键字符都触发一次请求，慢了用户直接输入完整词）；可用性 99.9%（补全挂了搜索还能用，非致命但体验重灾）；候选词每日更新可接受（不要求秒级实时） |
| 规模假设 | 2 亿 DAU；每次搜索会话平均触发 10 次补全请求 |
件 ②容量估算（Step 2，全程算式）
| 指标 | 算式 | 架构暗示 |
|---|---|---|
| 读 QPS | 2 亿 × 10 次/天 = 20 亿请求/天 ÷ 86400 ≈ 2.3 万/s；峰值 ×4（晚间）≈ 9 万/s | 纯读 + P99 紧 → 结果必须进程内存可寻址（一次网络往返都不想多） |
| 响应大小 | 10 条候选 × ~100B ≈ 1KB/请求 → 出站 90MB/s 峰值 | 响应加 Gzip；CDN 不适用（个性化/时效），走内网内存服务 |
| 候选规模 | 历史去重查询短语 ~5 亿；有效前缀节点 ~5000 万 | 单机内存放不下全部 → 按前缀分片（件 ⑥） |
| 日志管道 | 搜索日志 20 亿行/天 → 聚合后写入 10 万级前缀的 top-K 表 | 离线批处理，日级重建 + 近线增量（件 ⑤） |
件 ③API 定义（Step 3）
GET /suggest?q={prefix}&limit=10&user_ctx={可选脱敏上下文}
resp: {items: [{phrase, score, source}], version}
# source: "offline"（离线库）| "nearline"（近线热词）——便于排查
# version: 当前快照版本号——发布原子性的调试抓手
# 错误：空结果返回 items: []（HTTP 200），前端自行降级件 ④数据 Schema（Step 3）
| 存储 | 结构与设计 |
|---|---|
| Trie 内存结构（热层，进程内） | 节点 = 前缀；每个节点预存该前缀的 top-25 候选（排好序，取 10 留冗余）。查询 = 前缀定位节点 + 读数组，O(前缀长度)，零运行时排序 |
| 前缀 → 候选 KV（全量层） | key = 前缀（分片键），value = top-K 列表。覆盖长尾前缀，容忍 P99 略高的回源 |
| 聚合表（离线产物） | phrase, prefix, count_1d, count_7d, weighted_score, status(过审标记)。weighted_score = Σ count_i × decay^i（见件 ⑥） |
| 热词旁路表（近线层，Redis） | window_key(分钟) → 增量计数；超过阈值的前缀进入近线候选，带 TTL |
件 ⑤两条管道的完整时序（Step 3，本课核心）
【离线管道（日级重建，保证质量）】
搜索日志 → MQ(L7) → 日聚合 worker（MapReduce 式批处理）
→ 时间衰减加权 + 敏感词过滤 + 拼音/别名展开
→ 构建 Trie + 预排 top-K → 序列化快照 → 原子发布（版本切换，双版本共存灰度）
【近线管道（分钟级，抓突发热词）】
搜索日志 → MQ → 滑动窗口计数（Redis INCR）
→ 突增前缀（如「台风路径」）→ 敏感过滤 → 写热词旁路表（TTL 数小时）
【在线查询（P99 < 50ms 的预算分配）】
用户输入 → 接入层（5ms）→ 查进程内 Trie（<1ms，命中即返回）
→ miss（长尾前缀）→ 查 KV 全量层（+10ms）
→ merge 近线热词旁路（<1ms，Redis）→ 返回
→ 二次 miss（乱敲键盘）→ 返回空 + 客户端本地缓存空结果 60s（防穿透，L5）件 ⑥关键组件选型对比
| 决策点 | 选项 A | 选项 B | 结论与代价 |
|---|---|---|---|
| 数据结构 | Trie（前缀树），节点预排 top-K | 实时查 ES 的 prefix/match_phrase | Trie：查询 O(L) + P99 可控 + 成本低；代价：构建复杂、更新慢。ES 通用灵活但每次查询都是计算，P99 与成本双输——专用系统赢在预计算 |
| 热度算法 | 原始计数（count） | 时间衰减加权：score = Σ count_d × 0.8^d | 必须加权：否则「去年世界杯」永远霸榜、季节性词永远过时。代价：每天全量重算（可接受，日级管道） |
| 分片方式 | 按前缀首字符（简单） | 按前缀哈希一致性分片（L6） | 哈希分片：均匀 + 平滑扩容；代价：跨片聚合查询没有（本场景天然按前缀命中单片，无此需求——分片键与查询对齐的正面教材） |
| 新词时效 | 只靠日级重建（简单，热词晚 24h） | 近线旁路层（分钟级突增检测 + 合并） | 双层合并：热词分钟级可达；代价：旁路排序是粗排（计数序），与精排可能不一致——可接受，时效 > 精度 |
件 ⑦失败模式与应对（Step 4）
| 故障 | 应对 |
|---|---|
| 快照发布缺陷（新版本 top-K 全错） | 版本化发布 + 双版本共存，按流量灰度；异常（命中率骤降）一键回滚上一版本——预计算系统的发布必须可原子回滚 |
| 单 Trie 分片过热（「a」「s」等首字符前缀流量畸重） | 热分片多副本（读扩展）；或热前缀单独拆服务；监控按前缀分位的 QPS 分布 |
| 乱敲键盘打爆长尾查询（穿透） | 空结果短缓存（60s）+ 接入层限流 + 客户端输入去抖（debounce 200ms 才发请求） |
| 热词旁路被刷（恶意制造假热词） | 旁路候选必须过同一套敏感过滤 + 来源去重（同 IP/设备计数封顶）；旁路词降权展示 |
| 个性化泄露隐私 | 重排只在服务端内存做（用历史指纹，不落盘明细）；响应不携带用户标识 |
件 ⑧演进路线（v1 → v2）
- v1：单机 Trie + 日级重建脚本，词库 100 万——一天搞定，够用一年；
- v2：日志管道化（MQ + 聚合 worker）、KV 全量层、版本化发布；
- v3：近线热词旁路、个性化重排、多语言/拼音展开、多机房就近部署（快照分发到各机房内存）。
件 ⑨面试官追问预测
| 追问 | 答案要点 |
|---|---|
| 「为什么不用 Redis 存前缀→候选就完了？」 | 可以（v2 形态），但 P99 受一次网络 RTT + Redis 抖动影响；进程内 Trie 把热路径压到微秒级。Redis 适合做全量层/旁路，不适合扛 9 万 QPS 的 P99 主路径 |
| 「中文没有空格分词，前缀树怎么建？」 | 按字符粒度建 trie（中文每字一节点）；拼音前缀在构建期展开映射（「lj」→「历史」类）；分词是搜索主链路的问题，补全只需前缀匹配 |
| 「top-25 预存，为什么是 25 不是 10？」 | 个性化重排需要候选池（从 25 里选 10）；过滤掉敏感词后仍够返回 10 条。冗余是给过滤和重排留的余量 |
| 「怎么评估补全系统的质量？」 | 在线指标：补全点击率（CTR）、补全→搜索转化率、P99；离线指标：候选覆盖率、热词时效性（热词出现到进补全的分钟数） |
| 「输入到一半停住了，怎么省请求？」 | 客户端 debounce（200ms）+ 首字符结果客户端缓存（「a」的候选可以本地复用给「ap」前几条）+ 请求合并 |
§·随堂检测
§·检索练习
盖住全部内容：① 画出离线/近线/在线三层管道；② 解释「预计算换运行时」在本案的具体体现（三处）；③ P99 < 50ms 的预算是怎么分配到各跳的。
核对要点
① 日级：日志→MQ→聚合→Trie 快照→原子发布；分钟级：日志→窗口计数→热词旁路；在线：接入→Trie→KV→旁路合并。② 预计算三处：top-K 排序在离线算完、拼音/别名展开在离线做、敏感过滤离线做（在线只做合并与查找）。③ 接入 5ms + Trie <1ms +（miss 时）KV +10ms + 旁路 <1ms，总预算大头留给网络与意外。
§·本周行动
行动任务（约 20 分钟）
打开百度/Google 做侦探实验：① 输入一个突发热词的前半（如正在发生新闻的关键字），观察几分钟内补全出现的时间差——推断近线管道的存在与窗口；② 故意乱敲键盘，观察是空结果还是「纠错建议」——推断它们的降级设计；③ 输入拼音首字母（如 "yj"），观察是否出中文候选——推断构建期展开。
§·延伸资源
- 首选精读：Alex Xu Vol.1「Design a Typeahead Suggestion」章——与本案对照（它用「计数器服务+聚合」路线，比较两版取舍）[1]
- 数据结构：Trie（维基百科）——补全前缀树的经典定义[2]
- 相关课回看：L5（空结果缓存防穿透）、L6（前缀分片）、L7（日志管道）
- 下一课 → Lesson 0018 分布式网页爬虫
💬 想深入「个性化重排怎么做才不泄露隐私」或「拼音展开的工程细节」？直接问。