设计搜索自动补全 (Typeahead)

自动补全(typeahead)是你往搜索框打字时出现的建议下拉。它感觉平凡,但出人意料地苛刻:一个建议必须在数十毫秒内回来,因为请求在每次按键触发、建议必须是给定前缀在数十亿可能查询里最相关的、且整个东西以巨大 QPS 运行。设计取决于单个想法——为每个前缀预计算 top-k 建议,使服务是近乎即时的查找而非搜索。

            (root)
              │ c
              ▼
             [c]  top: cat(90), car(70), care(40)
              │ a
              ▼
             [ca] top: cat(90), car(70), care(40)
            ╱      ╲
         t ▼        ▼ r
       [cat]       [car] top: car(70), care(40), cargo(20)
       top:cat        │ e
                      ▼
                    [care] top: care(40), career(25)

  query "car" → 跳到节点 [car] → 返回它的缓存 top-k。完成。

第 1 步 — 澄清需求

功能:给定一个前缀,返回 top k(比如 5–10)个最相关的完整建议;建议反映什么热门并随时间演化。非功能:极低延迟(<50 ms,因为它每次按键触发)、极高读 QPS、高可用,和对巨大短语语料的可扩展。要陈述的范围决策:只前缀匹配(非模糊/错别字纠正,那是更大的 NLP 问题——虽值得提)、建议按全局热度排序(个性化可选),和一个小的固定 k。我们能容忍建议略陈旧(周期性重建)——自动补全无需反映上一秒的活动。

第 2 步 — 容量估算

假设每天 5 十亿次搜索。因为每次搜索是几次按键、每次按键能触发一个 suggest 调用,原始自动补全 QPS 可能是搜索 QPS 的 ~10×——轻易数十万 QPS、峰值更高。那个读量乘以亚 50 ms 延迟目标,正是强制预计算和内存服务的东西。短语语料(值得建议的不同查询)可能是数千万到数亿字符串;它们上的一个 trie,带节点的 top-k 列表,很大但可跨一群服务器的内存分片。

第 3 步 — API 设计

GET /suggest?prefix=car&limit=5
      → {suggestions: ["car", "care", "career", "cargo", "carpet"]}

# 只读。更新经数据管道带外发生,
# 而非经此端点。

第 4 步 — Trie

一个 trie(前缀树)逐字符存字符串:从根的每条路径拼出一个前缀,共享前缀共享节点。查找一个前缀只是走下对应字符——O(前缀长度),完全独立于 trie 含多少短语。那个属性是为什么它是经典自动补全结构。朴素版在叶存完整词,为回答一个前缀查询,遍历前缀节点下的整棵子树以收集和排序候选——请求时太慢。修法是第 5 步。

第 5 步 — 在每个节点预计算 Top-k

不在每个请求上搜索子树,而在节点缓存答案:每个 trie 节点存它前缀的 top-k 补全,已排序。现在查询是"走到前缀节点、返回它存的列表"——本质 O(前缀长度),请求时无排序或子树遍历。成本被移到构建时(计算那些列表)和存储(每节点 k 条),这正是对读主导系统正确的取舍:把昂贵工作离线做一次,让数十亿读每一个都便宜。这是把工作从读路径推到写/构建路径的经典动作。

第 6 步 — 排序

"top"建议主要按热度排序——每个完整查询历史上被搜索多频繁。改进:

• 时间衰减——给近期搜索更多权重,使趋势词上升、陈旧的淡出(一个曾经巨大的旧查询不该永远主导)。
• 个性化 / 上下文——位置、语言或用户历史能重排,代价是打破简单的共享预计算(现在列表因 segment 而异)。
• 业务规则——冒犯或不许建议的过滤在构建时发生。

第 7 步 — 构建和更新 Trie(数据管道)

trie 不是实时构建的;它由一个离线管道从查询日志产生:

搜索日志 ─▶ 按查询聚合计数(MapReduce / 流)
          ─▶ 过滤(冒犯、罕见)+ 应用时间衰减权重
          ─▶ 构建 trie,在每个节点计算 top-k
          ─▶ 发布不可变快照 ─▶ 加载进服务机群

聚合是教科书批(或流)作业。输出是一个不可变快照;服务节点周期性(如每小时/每天)加载新快照并原子切换到它。这种读/写解耦让服务路径简单、快、无锁。

第 8 步 — 服务与分片

服务层把 trie 保在内存以求速度并横向扩展。因为整个 trie 可能装不进一台机器,按前缀分片:如所有以 "a"–"m" 开头的前缀在一个分片组、"n"–"z" 在另一个(或更细拆分以平衡负载——像 "th" 这样的常见前缀得到更多流量)。一个轻量聚合器/路由器把每个请求发给拥有那个前缀的分片。每个分片被复制以求可用和分摊读负载。因为快照切换之间数据只读,副本平凡一致。

第 9 步 — 缓存与客户端技巧

几层削减延迟和负载:

• 客户端防抖(debouncing)——最后一次按键后等 ~100–300 ms 再发请求,使 "h-e-l-l-o" 发一两个调用、而非五个。
• 客户端/浏览器缓存——缓存用户已打过前缀的建议(打字再退格应命中本地缓存)。
• 服务端缓存 / CDN——最热门的短前缀("a"、"th"、"you")占巨大流量份额;以适度 TTL 在边缘缓存它们的 top-k。

第 10 步 — 实时 vs 批更新

建议该多新鲜?纯批重建(每小时/每天)简单且对大多数词足够,但错过趋势尖峰(突发新闻)。取舍:

一个实用混合:一个大的、缓慢重建的基础 trie 加一个小的实时层,经流式计数器跟踪趋势词并把它们合并进结果。面试官追问"那突发新闻呢?"时提这个。

第 11 步 — 关键取舍

• 预计算 vs 即时计算。在每个节点存 top-k 使读近似 O(1) 但花存储和构建时间;每请求计算省存储但爆延迟预算。对读主导的自动补全,预计算决定性胜出。
• 新鲜度 vs 成本。更频繁重建(或流式更新)更快浮现趋势但花更多计算;大多数词容忍数小时陈旧。
• 个性化 vs 可共享。全局 top-k 列表被所有用户共享(便宜);个性化列表倍增存储/计算并削弱缓存。
• Trie 大小 vs 分片开销。更细前缀分片更好平衡负载但加路由复杂度。