Typeahead 系统设计：大规模搜索自动补全如何工作

在搜索框里输入“how to”，还没打完下一个词，建议就出现了。这项功能几乎在每次按键时都要为每位用户响应一次请求，而且必须让人感觉是瞬时的：可以追溯到几十年前的响应时间研究认为，“系统即时响应”的界限大约是 0.1 秒。自动补全中没有哪一部分单独来看是难的。挑战在于，要在极高的请求速率下，把简单的事情压进紧张的延迟预算里，同时让建议保持新鲜，并且绝不出现你不想展示的内容。

本文设计一个 typeahead 服务：需求与容量、top-k 前缀索引、服务与分片、离线构建流水线、热门查询、缓存、个性化和过滤，并配有一张同时展示两部分的图。

需求

功能性需求：

• 为一个前缀返回前 5 到 10 个补全结果，主要按热度排序。
• 在几分钟内而不是几天后反映新的热点。
• 绝不展示违反你的政策的建议。

非功能性需求：

• 端到端约 100 ms，扣除网络时间后，留给后端的预算只有几十毫秒。
• 高可用：建议失败时搜索仍能使用，因此要优雅降级。
• 低成本：它在每次按键时都会运行。

容量

假设每天有 5,000 万用户，每人每天搜索 10 次；在客户端不再每输入一个字符就发一次请求之后，每次搜索约有 6 次建议请求：

有两个观察决定了设计。短前缀高度重复：每个输入“w”的人问的都是同一个问题。而且一个前缀的答案变化很慢，因此可以提前算好。

客户端承担一半的工作

• 防抖。 在最后一次按键后等待 100 到 200 ms 再发送请求，这样打字快的人不会每个字符触发一次请求。
• 取消过时的请求。 发出新前缀时，中止上一个请求，并忽略针对旧前缀的迟到响应。
• 在本地缓存。 如果“how t”返回的十个结果都以“how to”开头，客户端无需发送请求，就能为“how to”过滤出结果。
• 静默降级。 如果建议调用失败或太慢，就什么都不显示；搜索必须照常可用。

top-k 前缀索引

经典结构是字典树（trie），每个节点是一个前缀，其子节点在它后面再加一个字符。在请求时遍历字典树并在整棵子树中查找最热门的查询，对热门前缀来说太慢了。取而代之的是预先计算答案：在每个前缀节点上存储已经排好序的前 k 个补全结果。一次查找就变成了一次读取。

许多实现干脆跳过基于指针的字典树，存储一个从前缀到其 top-k 列表的扁平映射，并设定最大前缀长度上限，因为很长的前缀很少见，可以退回到较慢的路径。根据聚合计数构建这样一个映射的代码很短：

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

输出是只读的，会加载到每个服务节点的内存中。如果你已经在运行 Elasticsearch，它的 completion suggester 以功能的形式提供了同样的思路：文档描述的数据结构能实现快速查找，但构建成本高，并存储在内存中，这正是本设计所做的取舍。

服务与分片

建议服务对前缀进行规范化（转小写、去除首尾空白、Unicode 规范化），从索引中读取 top-k 列表，合并热门结果和个人结果，过滤后返回。它读取的一切都在内存中。

当索引超出一台机器的容量时，就对它分片。按首字母分片看似自然，却严重不均：以“s”开头的查询远多于以“x”开头的。改为对前缀做哈希，或按实测流量的区间切分，并为每个分片配置副本，这样节点故障只会降低容量。由于索引是离线重建的，副本之间从不需要就写入达成一致；每个副本加载的都是同一个快照。

离线构建流水线

1. 收集。 搜索前端把每一次完成的查询记录到 Kafka 这样的数据流中。
2. 聚合。 一个批处理任务在某个时间窗口内统计查询，例如最近 30 天，并给近几天更高的权重；同时丢弃低于阈值的罕见查询，以保护隐私并去除噪声。
3. 过滤。 在任何内容成为建议之前，先应用屏蔽列表和政策分类器。
4. 构建。 按上述方法计算前缀索引，并把它作为带版本的快照写入对象存储。
5. 部署。 服务节点把新快照与旧快照并排加载，原子地切换，并保留上一个版本以便快速回滚。

每小时或每天重建一次，就能让主索引对大多数查询来说足够新鲜。

热门查询

一条突发新闻会在几分钟内产生一个新的热门查询，远早于下一次批量构建。为此加一个小型实时层：流处理器在滑动窗口中统计查询，找出上升速度远超其基线的查询，并以前缀为键写入 Redis 这样的快速存储。建议服务把它们与批处理结果合并。让这一层保持小巧并严格过滤；有组织的攻击正是会在这里试图植入建议。

每一层都做缓存

短前缀最热，也最容易缓存，因为它们对每个人都一样。个性化结果无法在 CDN 上缓存，这也是让个性化保持轻量的原因之一。

个性化、拼写错误与过滤

• 个人历史。 把用户自己最近的查询与全局建议混合在一起很有帮助，而且如果最近的查询保存在设备上或一个小型的按用户存储中，成本也很低。
• 拼写错误。 在距前缀一次编辑以内做模糊匹配，可以挽救“pyhton”。它的成本更高，因此许多系统先尝试精确前缀，只有在结果太少时才退回到模糊匹配。
• 过滤要做两次：离线时，在查询进入索引之前；在线时，对照一个无需重建、几分钟内就能更新的快速屏蔽列表。

Typeahead 图

这张图的读法如下：

• 在线框架是每次按键的路径：浏览器、CDN 缓存、API 网关和建议服务。
• 建议服务读取两个内存前缀分片和 Redis 热点存储，再合并并过滤结果。
• 离线框架是构建路径：来自 Kafka 的查询日志、聚合任务，以及对象存储中带版本的索引快照。
• 从对象存储指向分片的虚线连线是快照加载，也是两部分之间唯一的连接。
• Markdown 块展示了延迟预算和容量数字。

清晰地绘制读密集型系统

• 把在线和离线分开。 两部分的延迟预算、故障模式和负责人都不同，图应该让人一眼看出这一点。
• 画出每一层缓存及其过期时间。在读密集型系统中，缓存就是架构的大部分。
• 画出两部分之间唯一的连接：这里是一个带版本的快照。它解释了更新如何到达用户，以及回滚如何进行。
• 在在线路径上标注延迟预算。

通用方法请参阅系统设计图示例。缓存策略图更深入地介绍了缓存层，日志聚合则遵循数据管道架构图中的模式。

在 Archboard 中构建

1. 使用 Google 或 GitHub 登录，并新建一张图。
2. 添加两个基础节点包中的 框架 节点：Online, per keystroke 和 Offline, hourly build。
3. 在在线框架中，为浏览器添加一个网络节点包中的 设备 节点，添加云节点包中的 CDN 和 API 网关，为建议服务添加一个 计算实例 节点，为前缀分片添加两个数据节点包中的 Redis 节点，再为热门查询添加一个 Redis 节点。
4. 在离线框架中，为查询日志添加一个数据节点包中的 Kafka 节点，为聚合任务添加一个云节点包中的 计算实例 节点，并为索引快照添加一个数据节点包中的 对象存储库。
5. 从左到右画出请求路径，在其下方画出构建路径，并从快照到分片画一条虚线连线。
6. 添加一个基础节点包中的 Markdown 块，写明延迟预算和容量。

这个示例共用 13 个图表节点，在 Free 套餐的限制之内。

常见问题

自动补全使用什么数据结构？ 字典树，或从前缀到结果的扁平映射，并在每个前缀上预先计算好前 k 个补全结果。预计算让每次查找都变成一次内存读取。

自动补全需要多快？ 从按键到出现建议约 100 ms，会让人感觉是瞬时的。扣除网络时间后，留给后端的只有几十毫秒，这就是索引放在内存中的原因。

建议如何保持最新？ 批处理流水线每小时或每天根据查询日志重建索引，实时层则在几分钟内补充快速上升的查询。

每次按键都应该发送自动补全请求吗？ 不应该。在客户端做 100 到 200 ms 的防抖，取消过时的请求，并为更长的前缀复用缓存结果。这能大幅减少请求量。

如何把冒犯性的建议挡在外面？ 在查询进入索引之前离线过滤，设置最低热度阈值，并在线对照一个可以快速更新的屏蔽列表检查结果。

免费开始 — 1 个席位，无需信用卡。