Skip to content

十三、设计搜索自动补全系统

在谷歌上搜索或在亚马逊购物时,当你在搜索框中输入时,一个或多个匹配的搜索词就会呈现在你面前。此功能被称为自动完成、提前键入、随键入搜索或增量搜索。图 13-1 展示了一个谷歌搜索的例子,当在搜索框中输入“晚餐”时,显示了一个自动完成的结果列表。搜索自动完成是许多产品的重要功能。这就引出了面试问题:设计一个搜索自动完成系统,也叫“设计 top k”或“设计 top k 最常搜索的查询”。

A screenshot of a cell phone  Description automatically generated

步骤 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 显示了频率表是如何更新的。

A screenshot of a cell phone  Description automatically generated

查询服务

假设我们有一个频率表,如表 13-1 所示。它有两个字段。

查询:存储查询字符串。

频率:表示查询被搜索的次数。

A screenshot of a cell phone  Description automatically generated

当用户在搜索框中键入“tw”时,会显示以下前 5 个搜索到的查询(图 13-3),假设频率表基于表 13-1。

A screenshot of a cell phone  Description automatically generated

要获得前 5 个最常搜索的查询,请执行以下 SQL 查询:

A screenshot of a cell phone  Description automatically generated

当数据集很小时,这是一个可接受的解决方案。当它很大时,访问数据库成为一个瓶颈。我们将深入探讨优化。

第三步——设计深潜

在概要设计中,我们讨论了数据收集服务和查询服务。高层次的设计并不是最佳的,但它是一个很好的起点。在本节中,我们将深入探讨几个组件,并探索如下优化:

特里数据结构

数据收集服务

查询服务

扩展存储

特里运算

Trie 数据结构

关系数据库用于高层设计中的存储。然而,从关系数据库中获取前 5 个搜索查询是低效的。数据结构 trie(前缀树)用于克服这个问题。由于 trie 数据结构对系统至关重要,我们将投入大量时间来设计定制的 trie。请注意,有些想法来自文章[2]和[3]。

理解基本的 trie 数据结构对这个面试问题至关重要。然而,这与其说是系统设计问题,不如说是数据结构问题。况且网上很多资料都在解释这个概念。在本章中,我们将只讨论 trie 数据结构的概述,并重点讨论如何优化基本 trie 以提高响应时间。

Trie(读作“try”)是一种树状数据结构,可以紧凑地存储字符串。这个名字来自单词 re trie val,表明它是为字符串检索操作而设计的。trie 的主要思想包括以下内容:

trie 是一种树状的数据结构。

词根代表空字符串。

每个节点存储一个字符,有 26 个子节点,每个子节点对应一个可能的字符。为了节省空间,我们不画空链接。

每个树节点代表一个单词或一个前缀串。

图 13-5 显示了带有搜索查询“树”、“尝试”、“真实”、“玩具”、“愿望”、“胜利”的 trie。搜索查询用粗边框突出显示。

A close up of a device  Description automatically generated

基本的 trie 数据结构在节点中存储字符。为了支持按频率排序,需要在节点中包含频率信息。假设我们有下面的频率表。

A screenshot of a cell phone  Description automatically generated

向节点添加频率信息后,更新后的 trie 数据结构如图 13-6 所示。

A close up of a device  Description automatically generated

自动完成如何与 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 个查询。

Diagram  Description automatically generated

图 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]。

A close up of a map  Description automatically generated

让我们在应用了这两种优化之后再来看看算法的时间复杂度:

1。找到前缀节点。时间复杂度:O(1)T5】

2。返顶 k 。由于 top k 查询被缓存,这一步的时间复杂度为 O(1) 。

由于每一步的时间复杂度降低到了 O(1) ,我们的算法只需要O(1)就可以获取 top k 查询。

数据收集服务

在我们之前的设计中,无论用户何时输入搜索查询,数据都会实时更新。由于以下两个原因,这种方法不实用:

用户每天可能会输入数十亿次查询。在每次查询时更新 trie 会大大降低查询服务的速度。

一旦构建好 trie,顶级建议可能不会有太大变化。因此,不需要频繁更新 trie。

为了设计一个可扩展的数据收集服务,我们检查数据来自哪里以及如何使用数据。像 Twitter 这样的实时应用程序需要最新的自动完成建议。然而,许多谷歌关键词的自动完成建议可能不会每天都有很大变化。

尽管使用案例不同,但数据收集服务的基础仍然相同,因为用于构建 trie 的数据通常来自分析或日志服务。

图 13-9 显示了重新设计的数据收集服务。每个组件都被逐一检查。

A close up of a map  Description automatically generated

分析日志。 它存储关于搜索查询的原始数据。日志是只追加的,没有索引。表 13-3 显示了一个日志文件的例子。

A screenshot of a cell phone  Description automatically generated

聚合器。 分析日志通常非常大,并且数据格式不正确。我们需要汇总数据,以便我们的系统能够轻松处理这些数据。

根据不同的使用情况,我们可能会以不同的方式汇总数据。对于 Twitter 这样的实时应用程序,我们在更短的时间间隔内聚合数据,因为实时结果很重要。另一方面,不太频繁地聚合数据,比如每周一次,对于许多用例来说可能已经足够了。在面试过程中,验证实时结果是否重要。我们假设 trie 每周重建一次。

汇总数据。

表 13-4 显示了一个汇总的每周数据的例子。“时间”字段表示一周的开始时间。“频率”字段是该周相应查询的出现次数的总和。

A screenshot of a cell phone  Description automatically generated

工人。 Workers 是一组定期执行异步作业的服务器。他们构建 trie 数据结构并将其存储在 Trie DB 中。

Trie 缓存。 Trie Cache 是一个分布式缓存系统,将 Trie 保存在内存中,以供快速读取。它每周拍摄一次数据库快照。

特里 DB。 Trie DB 是持久存储。存储数据有两种选择:

1。文档存储:由于每周都会构建一个新的 trie,所以我们可以定期对其进行快照、序列化,并将序列化后的数据存储在数据库中。像 MongoDB [4]这样的文档存储非常适合序列化数据。

2。键值存储:通过应用以下逻辑,可以用哈希表的形式[4]来表示 trie:

trie 中的每个前缀都映射到哈希表中的一个键。

每个 trie 节点上的数据映射到哈希表中的一个值。

图 13-10 显示了 trie 和哈希表之间的映射。

A screenshot of a cell phone  Description automatically generated

在图 13-10 中,左边的每个 trie 节点映射到右边的 <键、 > 值对。如果你不清楚键值存储是如何工作的,请参考第 6 章:设计键值存储。

查询服务

在高级设计中,查询服务直接调用数据库来获取前 5 个结果。图 13-11 显示了改进的设计,因为以前的设计效率很低。

A close up of a map  Description automatically generated

1。搜索查询被发送到负载平衡器。

2。负载平衡器将请求路由到 API 服务器。

3。API 服务器从 trie 缓存中获取 Trie 数据,并为客户端构造自动完成建议。

4。如果数据不在缓存中,我们将数据补充回缓存中。这样,对同一前缀的所有后续请求都将从缓存中返回。当缓存服务器内存不足或脱机时,可能会发生缓存未命中。

查询服务要求闪电般的速度。我们建议进行以下优化:

AJAX 请求。对于 web 应用程序,浏览器通常发送 AJAX 请求来获取自动完成结果。AJAX 的主要好处是发送/接收请求/响应不会刷新整个网页。

浏览器缓存。对于许多应用程序,自动完成搜索建议可能不会在短时间内发生太大变化。因此,自动完成建议可以保存在浏览器缓存中,以允许后续请求直接从缓存中获得结果。谷歌搜索引擎使用相同的缓存机制。图 13-12 显示了当你在谷歌搜索引擎上输入“系统设计面试”时的回复标题。如你所见,谷歌在浏览器中缓存结果 1 小时。请注意:cache-control 中的“private”表示结果是为单个用户准备的,不得由共享缓存进行缓存。“max-age=3600”意味着缓存的有效期为 3600 秒,也就是一个小时。

A screenshot of a social media post  Description automatically generated

数据采样:对于大规模系统来说,记录每个搜索查询需要大量的处理能力和存储。数据采样很重要。例如,每 N 个请求中只有 1 个被系统记录。

Trie 操作

Trie 是自动完成系统的核心组件。让我们看看操作(创建、更新和删除)是如何工作的。

创建

工作人员使用聚合数据创建 Trie。数据来源于分析日志/数据库。

更新

有两种方法可以更新 trie。

选项 1:每周更新 trie。一旦创建了新的 trie,新的 trie 就会替换旧的 trie。

选项 2:直接更新单个 trie 节点。我们尽量避免这种操作,因为它很慢。然而,如果 trie 的大小很小,这是一个可接受的解决方案。当我们更新一个 trie 节点时,它的祖先一直到根都必须被更新,因为祖先存储了子节点的顶部查询。 显示了一个更新操作如何工作的例子。在左侧,搜索查询“啤酒”的原始值为 10。在右侧,它被更新为 30。如您所见,该节点及其祖先的“beer”值更新为 30。

A close up of a piece of paper  Description automatically generated

删除

我们必须删除可恶的、暴力的、露骨的或危险的自动完成建议。我们在 Trie 缓存前面添加了一个过滤层(图 13-14 ),过滤掉不想要的建议。有了过滤层,我们可以根据不同的过滤规则灵活地移除结果。不需要的建议被异步地从数据库中物理移除,因此正确的数据集将被用于在下一个更新周期中构建 trie。

A close up of a logo  Description automatically generated

扩展存储

既然我们已经开发了一个为用户提供自动完成查询的系统,当 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 有相似数量的历史查询

A picture containing text, map  Description automatically generated

第四步——总结

完成深度调查后,面试官可能会问你一些后续问题。

面试官:你是如何扩展你的设计来支持多种语言的?

为了支持其他非英语查询,我们将 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

【4】MongoDB 百科:

【5】Unicode 常见问题:T3】【https://www.unicode.org/faq/basic_q.html】T5】

【6】Apache Hadoop:T3】https://hadoop.apache.org/T5】

【7】火花四射:

【8】阿帕奇风暴:

【9】阿帕奇卡夫卡:T3】https://kafka.apache.org/documentation/T5】



回到顶部