案例 11：搜索自动补全（Typeahead）

用户每敲一个字就发一次请求，结果要在下一次按键之前回来。这道题考的是把“离线算好”和“在线查得快”拆开。

1. 澄清需求

功能需求

• 输入前缀，返回前 k 条建议（通常 5～10 条），按热度排序
• 建议来自历史搜索词；突发热点（比如重大新闻）要在几分钟内出现
• 过滤违规和敏感词
• 可选：个性化（用户自己的历史）、多语言和地区

非功能需求

• 低延迟：端到端 p99 < 100ms，服务端处理控制在 10ms 量级
• 高可用：补全挂了不能影响搜索本身，最差就是不显示建议
• 读远多于写；数据最终一致即可，几分钟到几小时的滞后可以接受

2. 规模估算

• DAU 1 亿，每人每天搜 10 次，每次平均触发 6 次补全请求（已经做了防抖）→ 每天约 60 亿次请求 ≈ 7 万 QPS，峰值 15～20 万 QPS
• 候选词只保留最热的 1,000 万条，平均 20 字节 → 原始文本约 200MB
• 为每个前缀预存 top-10 的引用：前缀数量在几千万量级，每个存 10 个 4 字节 ID → 几 GB

结论：整份索引放得进单机内存。扩展主要靠加副本扛 QPS，未必需要分片。

3. API

GET /v1/suggest?q=app&limit=8&locale=en-US
→ 200 { "q": "app", "suggestions": ["apple", "app store", "apple stock"] }

缓存头分两种情况：

• 非个性化结果：Cache-Control: public, max-age=300，浏览器和 CDN 都能缓存。缓存 key 必须包含 locale：这里 locale 在 URL 参数里，自然是 key 的一部分；如果改成从 Accept-Language 头判断，就要在 CDN 上把它加进缓存 key
• 个性化结果（混入了用户自己的搜索历史）：必须用 Cache-Control: private 或 no-store，绝不能进 CDN 这类共享缓存，否则别人会看到你的搜索记录

4. 核心数据结构

方案一：Trie，并在节点上缓存 top-k

flowchart TD
  accTitle: 在节点上缓存 top-k 的 Trie
  root(("root")) --> a["a"]
  root --> b["b"]
  a --> ap["p（top：apple、app store、apply）"]
  ap --> app["p（top：apple、app store、apple stock）"]
  app --> appl["l"]
  app --> apps["s"]

• 每个节点存“以该前缀开头”的 top-k 结果。查询就是沿前缀走 L 步，直接返回，复杂度 O(L)
• 不缓存 top-k 的话，要遍历整棵子树再排序。短前缀（如 “a”）的子树巨大，延迟不可接受
• 代价：内存变大，计数变化时要更新路径上多个节点

方案二：前缀 → top-k 的哈希表

• 离线算好每个前缀（限制最大长度，比如 25 个字符）的 top-k，存进内存哈希表或 Redis
• 查询就是一次精确查找，天然适合按前缀哈希分片
• 本质上是把 Trie “压扁”，面试中讲清楚其中一种即可

方案三：现成组件，比如 Elasticsearch 的 completion suggester（基于 FST）。可以提，但面试官通常想看你自己设计。

5. 高层架构

flowchart TD
  accTitle: 搜索自动补全的高层架构
  browser["Browser"] --> cdn["CDN"] --> suggest["Suggest Service（内存索引，多副本）"]
  snap[("Object Storage：索引快照 v123")] -->|"定期加载新快照"| suggest
  builder["Index Builder（批处理，每小时/每天）"] --> snap
  browser -->|"搜索日志"| kafka["Kafka"] --> agg["聚合（带时间衰减的计数）"] --> builder
  kafka --> trend["流式热点检测（分钟级）"] --> hot["热点小索引"]
  hot -->|"查询时合并"| suggest

读写路径完全分开：

• 写（离线）：搜索日志进 Kafka → 按查询词聚合计数 → 过滤敏感词 → 构建索引 → 生成不可变快照，上传对象存储
• 读（在线）：服务节点启动或收到通知时加载新快照，在内存里建好之后原子切换指针；旧版本保留，出问题可以回滚

6. 深挖

6.1 排序与新鲜度

只按历史总次数排序，老词会永远霸榜。常见打分方式：

score = Σ（某时间窗口内的次数 × 衰减系数），窗口越久远系数越小

更省事的写法是指数衰减：每次搜索的贡献随时间按 0.5^(Δt / 半衰期) 减小，半衰期取几天。这样每个词只需存“当前分数 + 上次更新时间”，新的搜索到来时先把旧分数按经过的时间衰减，再加 1，不用保存每个时间窗口的计数。

热点问题：每小时一次的批处理太慢。再加一条流式链路，用滑动窗口计数（或 Count-Min Sketch 做近似计数）找出最近几分钟增长最快的词，放进一个小的热点索引。查询时把主索引和热点索引的结果合并，再取 top-k。

6.2 为什么用快照，而不是在线改 Trie

在线更新要给节点加锁，而且一个词的计数变化可能影响路径上 L 个节点的 top-k，读写冲突严重。补全对新鲜度的要求是分钟级，所以“离线构建 + 整体替换”更简单、更安全，还能按版本回滚。

6.3 扩展与分片

• 先复制：每个副本持有全量索引，无状态，加机器就能扩容
• 索引真的太大时再分片。不要按首字母范围分片：s、c、p 开头的词远多于 x、z，负载严重不均
• 前缀 → top-k 的哈希表可以直接按前缀哈希分片，每次查询只打到一个分片
• 多地区：每个地区/语言一套独立索引，就近部署

6.4 缓存

• 1～2 个字符的前缀最热，而且同一 locale 下所有人结果相同，最适合 CDN 和浏览器缓存
• 服务端再加一层进程内 LRU
• 个性化结果不能进共享缓存：要么单独请求个性化部分，要么在客户端把本地历史和通用结果合并

6.5 客户端优化（常被忽略的加分项）

• 防抖：停止输入约 100～150ms 后再发请求
• 处理乱序：发新请求时取消旧请求，或者只渲染与输入框当前内容匹配的响应，避免旧结果覆盖新结果
• 本地复用：已经拿到 “app” 的结果，输入 “appl” 时可以先在本地过滤显示
• 预取：输入框获得焦点时预取热门词

6.6 降级

补全服务超时或故障，前端直接不显示建议，搜索照常可用。补全是锦上添花，不能变成单点故障。

6.7 中文：拼音与首字母

中文用户敲进来的前缀可能是汉字（“天气”），也可能是全拼（“tianqi”“tianq”）或首字母（“tq”），输入法还没上屏的拼音也会作为请求发过来。做法：

• 离线建索引时，给每个候选词生成多种 key：汉字本身、全拼、首字母。比如“天气预报”生成 天气预报、tianqiyubao、tqyb，三种 key 都指向同一个词，各自参与前缀 → top-k 的计算
• 多音字要按词注音，不能逐字查表：“重庆”的“重”读 chong，“银行”的“行”读 hang，逐字转换会生成错误的 key
• 汉字加拼音的混合输入（“天qi”）可以先匹配已上屏的汉字部分，再用拼音过滤，也可以先不支持、留作追问
• 代价：拼音 key 会让索引膨胀几倍；首字母 key 冲突很多（“tq”可能是天气、提前、太强），排序更依赖热度

7. 常见追问

• Trie 节点怎么存 top-k？ 存查询 ID 和分数，k 很小，用有序数组即可
• 怎么支持拼写纠错？ 用编辑距离等方法生成候选，属于扩展，可以提但不必展开
• 中文怎么处理？ 前缀可能是汉字、全拼或首字母，为每个词额外生成拼音 key（见 6.7）
• 紧急下架一个违规词？ 维护黑名单，在线查询时再过滤一遍，不用等下次重建

8. 易错点

• 查询时现场遍历子树排序
• 每次按键都打到数据库
• 按首字母范围分片
• 忘了客户端防抖和响应乱序

9. 回答分级

数据结构与读路径

• Bad：每次按键查一次数据库，或者查询时遍历子树再排序。
• Good：Trie 的每个节点缓存 top-k，或者预计算“前缀 → top-k”哈希表，一次查找 O(L)；估算出整个索引放得进一台机器的内存，先用多副本扩展。
• Great：读写彻底分离：离线构建不可变快照，在线加载后原子切换，保留旧版本用于回滚；需要分片时按前缀哈希，不按首字母范围；短前缀放在 CDN 和浏览器缓存，个性化结果绝不进共享缓存。

排序与新鲜度

• Bad：只按历史总次数排序，老词永远霸榜；为了追热点在线修改 Trie。
• Good：按时间衰减打分，每小时或每天重建一次索引。
• Great：用指数衰减，每个词只存“分数 + 上次更新时间”；另加一条流式链路（滑动窗口或 Count-Min Sketch），找出几分钟内快速上升的词放进小的热点索引，查询时合并；紧急下架靠查询时的黑名单，不必重建。

客户端与降级

• Bad：不做防抖，晚到的旧响应覆盖了新输入的结果；补全超时就让搜索框报错。
• Good：防抖 100~150 ms，丢弃与当前输入不匹配的响应；超时就不显示建议，搜索照常可用。
• Great：用本地缓存的 “app” 结果过滤出 “appl” 的建议，输入框获得焦点时预取；中文场景为每个词生成汉字、全拼和首字母几套 key，按词处理多音字，并说明首字母冲突多、排序更依赖热度。

10. 不同级别的期望