Design Google Autocomplete Feature
Last updated
Last updated
Use trie data structure
top K words for every node
Autocomplete 又被称作 Typeahead，指用户在搜索框中打字的同时，搜索框进行补全，并给出多个用户可能想搜索的关键词。这个功能使得用户在搜索体验更加顺畅。
Autocomplete 主要考察两条数据流，一是如何收集高频搜索关键词，二是如何实时补全用户打了一半的关键词前缀。
实时补全关键字。
基于流行的搜索关键词进行关键词补全
关键词补全选项至多10个
流行程度是基于搜索次数，越新的搜索的权重越高
延迟 (Latency) - 非常低，端到端延迟需低于打字速度
正确性 (Correctness) - 匹配到的关键词是符合前缀并排在流行程度前十的
可扩展性 (Scalability) - 支持亿级 DAU
实时性 (Realtime) - 每小时根据新的流行搜索结果更新 Autocomplete 的返回结果
拼写检查
个性化补全
英语以外的多语言支持
搜索 DAU 1 Billion
每个搜索 DAU 平均每天进行 10 次搜索
读 QPS - 1B * 10 * 5 (Autocomplete query per search) = 50B / 86400 ~= 50k QPS
写 QPS - 1B * 10 / 86400 ~= 10k QPS
数据流如下：
用户在搜索框中打入关键词
搜索服务返回结果的同时，将关键词通过 Kafka 之类的 Message Queue 异步传递，供下游服务读取
关键词计数器是一个下游的 MapReduce Job。它会按照固定的时间间隔（比如每分钟）对所有这段时间内的关键词做归并计数。
从非功能性需求里看，我们不需要支持实时更新 Autocomplete 所基于的数据，所以我们可以容忍每分钟对数据进行归并。这样可以大大减少对下游服务以及数据库的 Write QPS。利用 MapReduce 可以在帮助系统扩展到亿级用户。
关键词计数完成之后，我们就可以进行流行指数的计算了。根据需求，我们需要给最新的关键词搜索更高的权重。下面我们看看可以实现这个计算的几种方案。
保留完整历史，每分钟根据新的数据，过去一段时间里的每分钟数据以及以一定的权重规则计算
不使用历史数据，只根据当前词条的流行指数和最新的数据按一定规则分配权重，比如公式可以是 - 新的流行指数 = 当前流行指数 * 0.99 + 该词条过去一分钟内的访问次数
权衡以上的两种方案，方案二在计算上会简单很多，并且符合需求中的权重变化要求，省去了大量的重复计算。方案一会在计算时有很大的灵活性，比如它允许任意变化过去词条的权重。实际操作中，为了降低不必要的计算量，我们可以采用方案二，但仍然在数据仓库 (Data Warehouse) 中保留历史数据，一旦有了重新调整权重的需求，可以从头开始重新计算。
利用以上的计算方案，我们可以为每一个曾经出现过的关键词统计出相应的流行指数。这些流行指数会被存储在数据库或者数据仓库中。数据库和数据仓库两者的区别在于读写速度，由于我们允许每小时更新，对读写速度要求很低，倾向于使用数据仓库降低存储的成本。
为了让 Autocomplete 服务在用户使用时达到极低的延迟，我们需要对流行指数数据库中存储的信息做预处理。考虑到用户请求本质上是根据前缀补全并排序，我们引入处理前缀查询专用的数据结构 Trie。Walid Wahed, Tiffany Han, Jay Shenk. (2018). How We Built Prefixy: A Scalable Prefix Search Service for Powering Autocomplete
以上就是 Trie 的结构，将单词按照前缀分组形成树状结构。
4.3.1 方案一
最直接简单的做法是在每一个节点存储几点信息：
is_word - 该节点是不是完整的单词
popularity_score - 如果该节点是完整单词，它的流行指数
pointers - 指向下一级的节点的指针
在匹配前缀时，我们沿着树状结构找到符合这个前缀的 Root Node，遍历之下的所有节点，排序找到流行指数最高的前十，并返回结果。
假设前缀长度是 L, 该前缀下的所有节点数量是 N，需要返回的结果数量是 K, 以上算法的时间复杂度是 O(L + N + K + (N-K)logK)。其中 K + (N-K)logK 指的是维护一个大小为 K 的最小堆来存储流行指数最大的 K 个节点。实际情况下，由于 K 是一个较小的常数，复杂度可以简化为 O(L+N)。
方案一的问题可以从这个时间复杂度中想见，N 可能是一个很大的数字，我们在查询中对树的某一部分进行遍历会很消耗资源。
4.3.2 方案二
我们可以通过进一步的预处理将时间复杂度降低到 O(L)，即提前最每个节点下的前十最流行的关键词直接存在节点里，如上图所示。通过增加预处理的计算量，使得读取时间更快。在 Autocomplete 的应用场景下，由于我们可以限制 Trie 中的最大深度来给 L 一个限制，O(L) 相当于 O(1)，已经很理想了。
4.3.3 方案三
4.4.1 数据更新
每隔一段时间（比如每小时），一个 Cron Job 会启动并读取流行指数的数据库，通过计算得出每个前缀所对应的流行关键词，存入前缀数据库 KV Store，等待 Autocomplete 服务读取。
下面提两种计算过程的实现思路：
通过 MapReduce，对于每个关键词，Map 到一组一定长度范围内的前缀，随后 Reduce 成每个前缀对应的关键词及其流行程度，最后按照流行程度给关键词排序放入 KV Store。
使用一组服务器，共同构建一个 Trie，从最底下的叶节点开始，向上构建，每上一层的节点的十个流行关键词由下一层节点的所有流行关键词排序而成。在完成 Trie 构建后，将数据扁平化存入 KV Store。
4.4.2 Autocomplete 基本功能
有了前缀数据库中的数据，服务就可以是 Stateless 的。每次用户访问时， Gateway 就可以任意选择一台较空闲的 Autocomplete 服务器，让其根据用户发送的前缀，从数据库中读取前十的流行关键词。
4.4.3 Autocomplete 优化
由于该服务对延迟要求很高，我们可以考虑预先给客户端返回一些用户可能会在之后请求的前缀，比如用户请求的前缀是 pro，服务器会返回 pro, prod, proc, prof 等等前缀对应的前十流行关键词。这样用户在打入下一个字母的时候，客户端如果发现已经在之前的回复中预载了，就不需要再向服务器发送请求了，达到最流畅的用户体验。
为了更好地实现预加载，我们可以考虑
根据用户发出的前缀数据选出最有可能用户希望的前缀
使用额外的 LRU 缓存去记录最近的返回结果
Autocomplete 服务是无状态的，可以容易地横向扩展
Autocomplete Cache 使用分布式缓存
流行指数的运算采用 MapReduce 运算
Autocomplete 要求极低延迟，我们使用大量预处理和预加载来降低延迟
Autocomplete 服务延迟
Queue Health
Autocomplete builder load
数据更新延迟
缓存使用比例
Walid Wahed, Tiffany Han, Jay Shenk. (2018). How We Built Prefixy: A Scalable Prefix Search Service for Powering Autocomplete
Salvatore Sanfilippo. (2010). Auto Complete with Redis
请问这里"4.2 流行指数计算" 是Search Keyword Counter做的吗？还是说有另外的component做这个统计
•
•
分享 ›
严格来说，Search keyword counter 只算一定时间范围内（比如一分钟）的每个关键词的数量，不直接计算流行指数。需要另外的服务读取 Search Keyword counter (MapReduce Job) 的计算结果，读取当前的流行指数，并计算更新的流行指数+更新到流行指数数据库。
在 Google 搜索引擎系统设计题解一文中，我们已经讨论了搜索服务的设计。这里我们着重考虑如何收集搜索词条并将其转化为 Autocomplete 系统所需的数据形式。Google 搜索引擎系统设计题解Google 作为搜索引擎的标杆，帮助用户发现了互联网上无数的精彩。这道系统面试题着重考察同学对信息索引 (Index) 和查询 (Query) 的理解。这篇6000字题解就来帮你深挖小小的搜索框是如何帮我们从茫茫互联网上找到内容的。罗辑爱思系统设计
基于 Trie 的预处理的思路，我们可以更直接地使用 Hash Table 来存储所有前缀与前十流行的关键词的对应关系，复杂度同是 O(1)，但读取速度会更快。这样做的好处是不需要处理树状结构，可以很容易地存入 Redis 之类的 KV Store；缺点是数据形式不如树状结构紧凑，会耗费更多储存空间来存储前缀。在分布式系统中，我会优先考虑读取速度而牺牲存储。在之后的设计中，我们会基于方案三做设计。Walid Wahed, Tiffany Han, Jay Shenk. (2018). How We Built Prefixy: A Scalable Prefix Search Service for Powering Autocomplete
