十三、设计搜索自动补全系统
在谷歌上搜索或在亚马逊购物时，当你在搜索框中输入时，一个或多个匹配的搜索词就会呈现在你面前。此功能被称为自动完成、提前键入、随键入搜索或增量搜索。图 13-1 展示了一个谷歌搜索的例子，当在搜索框中输入“晚餐”时，显示了一个自动完成的结果列表。搜索自动完成是许多产品的重要功能。这就引出了面试问题:设计一个搜索自动完成系统，也叫“设计 top k”或“设计 top k 最常搜索的查询”。
步骤 1 -了解问题并确定设计范围
解决任何系统设计面试问题的第一步是问足够多的问题来澄清需求。下面是一个应聘者与面试官互动的例子:
候选人 :是只支持搜索查询开头的匹配，还是也支持中间的匹配？
面试官 :只在搜索查询的开头。
候选人 :系统应该返回多少个自动完成建议？
面试官 : 5
候选人 :系统如何知道返回哪 5 条建议？
面试官 :这个是由人气决定的，由历史查询频率决定的。
考生 :系统支持拼写检查吗？
面试官 :不，不支持拼写检查或自动更正。
候选人 :搜索查询是英文的吗？
面试官 :是的。如果最后时间允许，可以讨论多语言支持。
候选人 :我们允许大写和特殊字符吗？
面试官 :不，我们假设所有的搜索查询都有小写字母字符。
候选人 :有多少用户使用该产品？
面试官:1000 万 DAU。
要求
下面是对需求的总结:
快速响应时间:当用户键入搜索查询时，自动补全建议必须足够快地出现。一篇关于脸书的自动完成系统的文章[1]揭示了该系统需要在 100 毫秒内返回结果。否则会造成口吃。
相关:自动完成建议应该与搜索词相关。
排序:系统返回的结果必须按人气或其他排名模型排序。
可扩展:系统可以处理高流量。
高可用:当系统的一部分离线、变慢或遇到意外网络错误时，系统应保持可用和可访问。
信封估算的背面
假设日活跃用户 1000 万(DAU)。
一个普通人每天会进行 10 次搜索。
每个查询字符串 20 字节数据:
假设我们使用 ASCII 字符编码。1 个字符= 1 个字节
假设一个查询包含 4 个单词，每个单词平均包含 5 个字符。
即每次查询 4×5 = 20 字节。
对于搜索框中输入的每个字符，客户端都会向后端发送一个请求，请求自动完成建议。平均而言，每个搜索查询发送 20 个请求。例如，当您输入完“晚餐”时，以下 6 个请求将被发送到后端。
搜索？q=d
搜索？q=di
搜索？q=din
搜索？q=dinn
搜索？q=dinne
搜索？q =晚餐
~每秒 24000 次查询(QPS)= 1000 万用户 10 次查询/天 20 个字符/ 24 小时/ 3600 秒。
高峰 QPS = QPS * 2 = ~ 4.8 万
假设 20%的日常查询是新的。1000 万 10 次查询/天每次查询 20 字节* 20% = 0.4 GB。这意味着每天有 0.4GB 的新数据添加到存储中。
第二步——提出高水平的设计并获得认同
在高层，系统被分成两部分:
数据收集服务:收集用户输入的查询，并实时汇总。对于大型数据集，实时处理是不实际的；然而，这是一个很好的起点。我们将在深潜中探索更现实的解决方案。
查询服务:给定一个搜索查询或前缀，返回 5 个最常搜索的词语。
数据收集服务
让我们用一个简单的例子来看看数据收集服务是如何工作的。假设我们有一个存储查询字符串及其频率的频率表，如图 13-2 所示。一开始，频率表是空的。之后，用户依次输入查询“twitch”、“twitter”、“twitter”和“twillo”。图 13-2 显示了频率表是如何更新的。
查询服务
假设我们有一个频率表，如表 13-1 所示。它有两个字段。
查询:存储查询字符串。
频率:表示查询被搜索的次数。
当用户在搜索框中键入“tw”时，会显示以下前 5 个搜索到的查询(图 13-3)，假设频率表基于表 13-1。
要获得前 5 个最常搜索的查询，请执行以下 SQL 查询:
当数据集很小时，这是一个可接受的解决方案。当它很大时，访问数据库成为一个瓶颈。我们将深入探讨优化。
第三步——设计深潜
在概要设计中，我们讨论了数据收集服务和查询服务。高层次的设计并不是最佳的，但它是一个很好的起点。在本节中，我们将深入探讨几个组件，并探索如下优化:
特里数据结构
数据收集服务
查询服务
扩展存储
特里运算
Trie 数据结构
关系数据库用于高层设计中的存储。然而，从关系数据库中获取前 5 个搜索查询是低效的。数据结构 trie(前缀树)用于克服这个问题。由于 trie 数据结构对系统至关重要，我们将投入大量时间来设计定制的 trie。请注意，有些想法来自文章[2]和[3]。
理解基本的 trie 数据结构对这个面试问题至关重要。然而，这与其说是系统设计问题，不如说是数据结构问题。况且网上很多资料都在解释这个概念。在本章中，我们将只讨论 trie 数据结构的概述，并重点讨论如何优化基本 trie 以提高响应时间。
Trie(读作“try”)是一种树状数据结构，可以紧凑地存储字符串。这个名字来自单词 re trie val，表明它是为字符串检索操作而设计的。trie 的主要思想包括以下内容:
trie 是一种树状的数据结构。
词根代表空字符串。
每个节点存储一个字符，有 26 个子节点，每个子节点对应一个可能的字符。为了节省空间，我们不画空链接。
每个树节点代表一个单词或一个前缀串。
图 13-5 显示了带有搜索查询“树”、“尝试”、“真实”、“玩具”、“愿望”、“胜利”的 trie。搜索查询用粗边框突出显示。
基本的 trie 数据结构在节点中存储字符。为了支持按频率排序，需要在节点中包含频率信息。假设我们有下面的频率表。
向节点添加频率信息后，更新后的 trie 数据结构如图 13-6 所示。
自动完成如何与 trie 一起工作？在深入算法之前，让我们定义一些术语。
p
n:一个 trie 的节点总数
c:给定节点的子节点数量
获得 top k 的步骤下面列出了搜索次数最多的查询:
1。找到前缀。时间复杂度: O(p) 。
2。从前缀节点开始遍历子树以获取所有有效的子节点。如果子元素可以形成有效的查询字符串，则它是有效的。时间复杂度:(c)
3。给孩子排序，得到 top k 。时间复杂度: O(clogc)
让我们用一个如图 13-7 所示的例子来解释这个算法。假设 k 等于 2，并且用户在搜索框中键入“tr”。算法工作如下:
第一步:找到前缀节点“tr”。
第二步:遍历子树，得到所有有效子树。在这种情况下，节点[tree: 10]、[true: 35]、[try: 29]是有效的。
第三步:对孩子进行排序，得到 top 2。[true: 35]和[try: 29]是前缀为“tr”的前 2 个查询。
图 13-7
这个算法的时间复杂度是上面提到的每一步花费的时间之和: O(p) + O(c) + O(clogc)
上面的算法很简单。然而，它太慢了，因为我们需要遍历整个 trie 来得到最坏情况下的 top k 结果。下面是两个优化:
1。限制前缀的最大长度
2。在每个节点缓存热门搜索查询
让我们来逐一看看这些优化。
限制前缀的最大长度
用户很少在搜索框中键入长搜索查询。因此，可以肯定地说 p 是一个小整数，比如说 50。如果我们限制前缀的长度，那么“查找前缀”的时间复杂度可以从 O(p) 降低到 O(小常数) 又名 O(1) 。
在每个节点缓存热门搜索查询
为了避免遍历整个 trie，我们在每个节点存储 top k 最常用的查询。由于 5 到 10 个自动完成建议对用户来说已经足够了， k 是一个相对较小的数字。在我们的具体例子中，只有前 5 个搜索查询被缓存。
通过在每个节点缓存前 5 个搜索查询，我们显著降低了检索前 5 个查询的时间复杂度。然而，这种设计需要大量空间来存储每个节点上的 top 查询。用空间换取时间是非常值得的，因为快速响应时间非常重要。
图 13-8 显示了更新后的 trie 数据结构。前 5 个查询存储在每个节点上。例如，前缀为“be”的节点存储以下内容:[best: 35，bet: 29，bee: 20，be: 15，beer: 10]。
让我们在应用了这两种优化之后再来看看算法的时间复杂度:
1。找到前缀节点。时间复杂度:O(1)T5】
2。返顶 k 。由于 top k 查询被缓存，这一步的时间复杂度为 O(1) 。
由于每一步的时间复杂度降低到了 O(1) ，我们的算法只需要O(1)就可以获取 top k 查询。
数据收集服务
在我们之前的设计中，无论用户何时输入搜索查询，数据都会实时更新。由于以下两个原因，这种方法不实用:
用户每天可能会输入数十亿次查询。在每次查询时更新 trie 会大大降低查询服务的速度。
一旦构建好 trie，顶级建议可能不会有太大变化。因此，不需要频繁更新 trie。
为了设计一个可扩展的数据收集服务，我们检查数据来自哪里以及如何使用数据。像 Twitter 这样的实时应用程序需要最新的自动完成建议。然而，许多谷歌关键词的自动完成建议可能不会每天都有很大变化。
尽管使用案例不同，但数据收集服务的基础仍然相同，因为用于构建 trie 的数据通常来自分析或日志服务。
图 13-9 显示了重新设计的数据收集服务。每个组件都被逐一检查。
分析日志。 它存储关于搜索查询的原始数据。日志是只追加的，没有索引。表 13-3 显示了一个日志文件的例子。
聚合器。 分析日志通常非常大，并且数据格式不正确。我们需要汇总数据，以便我们的系统能够轻松处理这些数据。
根据不同的使用情况，我们可能会以不同的方式汇总数据。对于 Twitter 这样的实时应用程序，我们在更短的时间间隔内聚合数据，因为实时结果很重要。另一方面，不太频繁地聚合数据，比如每周一次，对于许多用例来说可能已经足够了。在面试过程中，验证实时结果是否重要。我们假设 trie 每周重建一次。
汇总数据。
表 13-4 显示了一个汇总的每周数据的例子。“时间”字段表示一周的开始时间。“频率”字段是该周相应查询的出现次数的总和。
工人。 Workers 是一组定期执行异步作业的服务器。他们构建 trie 数据结构并将其存储在 Trie DB 中。
Trie 缓存。 Trie Cache 是一个分布式缓存系统，将 Trie 保存在内存中，以供快速读取。它每周拍摄一次数据库快照。
特里 DB。 Trie DB 是持久存储。存储数据有两种选择:
1。文档存储:由于每周都会构建一个新的 trie，所以我们可以定期对其进行快照、序列化，并将序列化后的数据存储在数据库中。像 MongoDB [4]这样的文档存储非常适合序列化数据。
2。键值存储:通过应用以下逻辑，可以用哈希表的形式[4]来表示 trie:
trie 中的每个前缀都映射到哈希表中的一个键。
每个 trie 节点上的数据映射到哈希表中的一个值。
图 13-10 显示了 trie 和哈希表之间的映射。
在图 13-10 中，左边的每个 trie 节点映射到右边的 <键、 > 值对。如果你不清楚键值存储是如何工作的，请参考第 6 章:设计键值存储。
查询服务
在高级设计中，查询服务直接调用数据库来获取前 5 个结果。图 13-11 显示了改进的设计，因为以前的设计效率很低。
1。搜索查询被发送到负载平衡器。
2。负载平衡器将请求路由到 API 服务器。
3。API 服务器从 trie 缓存中获取 Trie 数据，并为客户端构造自动完成建议。
4。如果数据不在缓存中，我们将数据补充回缓存中。这样，对同一前缀的所有后续请求都将从缓存中返回。当缓存服务器内存不足或脱机时，可能会发生缓存未命中。
查询服务要求闪电般的速度。我们建议进行以下优化:
AJAX 请求。对于 web 应用程序，浏览器通常发送 AJAX 请求来获取自动完成结果。AJAX 的主要好处是发送/接收请求/响应不会刷新整个网页。
浏览器缓存。对于许多应用程序，自动完成搜索建议可能不会在短时间内发生太大变化。因此，自动完成建议可以保存在浏览器缓存中，以允许后续请求直接从缓存中获得结果。谷歌搜索引擎使用相同的缓存机制。图 13-12 显示了当你在谷歌搜索引擎上输入“系统设计面试”时的回复标题。如你所见，谷歌在浏览器中缓存结果 1 小时。请注意:cache-control 中的“private”表示结果是为单个用户准备的，不得由共享缓存进行缓存。“max-age=3600”意味着缓存的有效期为 3600 秒，也就是一个小时。
数据采样:对于大规模系统来说，记录每个搜索查询需要大量的处理能力和存储。数据采样很重要。例如，每 N 个请求中只有 1 个被系统记录。
Trie 操作
Trie 是自动完成系统的核心组件。让我们看看操作(创建、更新和删除)是如何工作的。
创建
工作人员使用聚合数据创建 Trie。数据来源于分析日志/数据库。
更新
有两种方法可以更新 trie。
选项 1:每周更新 trie。一旦创建了新的 trie，新的 trie 就会替换旧的 trie。
选项 2:直接更新单个 trie 节点。我们尽量避免这种操作，因为它很慢。然而，如果 trie 的大小很小，这是一个可接受的解决方案。当我们更新一个 trie 节点时，它的祖先一直到根都必须被更新，因为祖先存储了子节点的顶部查询。 显示了一个更新操作如何工作的例子。在左侧，搜索查询“啤酒”的原始值为 10。在右侧，它被更新为 30。如您所见，该节点及其祖先的“beer”值更新为 30。
删除
我们必须删除可恶的、暴力的、露骨的或危险的自动完成建议。我们在 Trie 缓存前面添加了一个过滤层(图 13-14 ),过滤掉不想要的建议。有了过滤层，我们可以根据不同的过滤规则灵活地移除结果。不需要的建议被异步地从数据库中物理移除，因此正确的数据集将被用于在下一个更新周期中构建 trie。
扩展存储
既然我们已经开发了一个为用户提供自动完成查询的系统，当 trie 变得太大而不适合一台服务器时，是时候解决可伸缩性问题了。
由于英语是唯一受支持的语言，一种简单的方法是基于第一个字符进行切分。这里有一些例子。
如果我们需要两台服务器进行存储，我们可以在第一台服务器上存储以'ato 'm'开头的查询，在第二台服务器上存储以'n' to 'z'开头的查询。
如果我们需要三台服务器，我们可以将查询拆分为“ato“I”，“j”to“r”和“sto“z”。
按照这个逻辑，我们可以将查询拆分到 26 台服务器上，因为英语中有 26 个字母字符。让我们将基于第一个字符的分片定义为一级分片。为了存储超过 26 台服务器的数据，我们可以在第二层甚至第三层进行分片。比如以' a 开头的数据查询，可以拆分成 4 个服务器:' aa-ag '、 ah-an '、 ao-au '、以及'av-az '【T20]。
乍看之下，这种方法似乎很合理，直到你意识到以字母' c 开头的单词比以字母' x 开头的单词多得多。这就造成了分配不均。
为了缓解数据不平衡问题，我们分析了历史数据分布模式，并应用了更智能的分片逻辑，如图 13-15 所示。碎片映射管理器维护一个查找数据库，用于标识行应该存储在哪里。例如，如果对' s 和' u '、 v '、 w '、 x '、 y 和' z 有相似数量的历史查询
第四步——总结
完成深度调查后，面试官可能会问你一些后续问题。
面试官:你是如何扩展你的设计来支持多种语言的？
为了支持其他非英语查询，我们将 Unicode 字符存储在 trie 节点中。如果你不熟悉 Unicode，下面是它的定义:“一个编码标准涵盖了世界上所有书写系统的所有字符，现代的和古代的”[5]。
采访者:如果一个国家的顶级搜索查询与其他国家不同呢？
在这种情况下，我们可以为不同的国家建立不同的尝试。为了缩短响应时间，我们可以将尝试存储在 cdn 中。
采访者:我们如何支持趋势(实时)搜索查询？
假设一个新闻事件爆发，一个搜索查询突然流行起来。我们最初的设计行不通，因为:
离线工作人员尚未计划更新 trie，因为计划每周运行一次。
即使是预定的，构建 trie 的时间也太长了。
构建一个实时搜索自动完成是复杂的，超出了本书的范围，所以我们只给出一些想法:
通过分片减少工作数据集。
改变排名模型，给最近的搜索查询分配更多的权重。
数据可能以数据流的形式出现，所以我们无法一次访问所有数据。流数据意味着数据是连续生成的。流处理需要一套不同的系统:Apache Hadoop MapReduce [6]，Apache Spark Streaming [7]，Apache Storm [8]，Apache Kafka [9]等。因为所有这些主题都需要特定的领域知识，所以我们在这里不做详细介绍。
祝贺你走到这一步！现在给自己一个鼓励。干得好！
参考资料
【1】一个 Typeahead 的生命查询:https://www . Facebook . com/notes/Facebook-engineering/The-Life-of-a-type ahead-Query/389105248919/
【2】我们如何构建 Prefixy:一个可扩展的前缀搜索服务为自动完成供电:https://medium . com/@ Prefixy team/How-We-build-Prefixy-A-Scalable-Prefix-Search-Service-for-Powering-Autocomplete-c 20 f 98 e 2 eff 1
【3】前缀哈希树分布式哈希表上的一种索引数据结构:https://people.eecs.berkeley.edu/~sylvia/papers/pht.pdf
【5】Unicode 常见问题:T3】【https://www.unicode.org/faq/basic_q.html】T5】
【6】Apache Hadoop:T3】https://hadoop.apache.org/T5】
【9】阿帕奇卡夫卡:T3】https://kafka.apache.org/documentation/T5】
