系统设计：设计一个搜索自动完成系统（13）

Published: at 22:01:14

当你在谷歌上搜索或在亚马逊购物时，在搜索框中输入，会有一个或多个与搜索词相匹配的内容呈现给你。这一功能被称为自动完成、提前输入、边输入边搜索或增量搜索。图13-1是谷歌搜索的一个例子，当在搜索框中输入”dinner”时，显示了一个自动完成的结果列表。搜索自动完成是许多产品的一个重要功能。这就把我们引向了面试问题：设计一个搜索自动完成系统，也叫 “设计 top k “或 “设计 top k 搜索最多的查询”。

第1步：了解问题并确定设计范围

解决任何系统设计面试问题的第一步是提出足够多的问题来阐明需求。 这是候选人与面试官互动的示例：

候选人：是否只支持在搜索查询的开始阶段进行匹配，还是在中间也支持？

面试官：只有在搜索查询的开始阶段。

候选人：系统应该返回多少个自动完成的建议？

面试官：5

候选人：系统如何知道要返回哪5条建议？

面试官：这是由受欢迎程度决定的，由历史查询频率决定。

应聘者：系统是否支持拼写检查？

面试官：不，不支持拼写检查或自动更正。

候选人：搜索查询是用英语吗？

面试官：是的。如果最后时间允许，我们可以讨论多语言支持。

候选人：我们允许大写字母和特殊字符吗？

面试官：不，我们假设所有的搜索查询都是小写字母。

候选人：有多少用户使用该产品？

面试官：1000万DAU。

需求

以下是对要求的总结：

粗略估算

第2步：提出高层次的设计方案并获得认同

在高层次上，该系统被分解成两个部分。

数据收集服务

让我们用一个简化的例子来看看数据收集服务是如何工作的。假设我们有一个频率表，存储查询字符串和它的频率，如图13-2所示。在开始时，频率表是空的。后来，用户依次输入查询 “twitch”、“twitter”、“twitter “和 “twillo”。图13-2显示了频率表的更新情况。

查询服务

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

Query：它存储查询字符串。

Frequency：它代表一个查询被搜索的次数。

当用户在搜索框中输入 “tw “时，假设频率表以表13-1为基础，就会显示以下前5个被搜索的查询（图13-3）。

要获得前5个经常搜索的查询，执行以下SQL查询。

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

第3步：深入设计

在高层次设计中，我们讨论了数据收集服务和查询服务。高层设计并不是最优的，但它是一个很好的起点。在这一节中，我们将深入研究几个组件，并探讨以下的优化方法。

Trie 数据结构

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

了解基本的tree数据结构对于这个面试问题来说是至关重要的。然而，这更像是一个数据结构问题，而不是一个系统设计问题。此外，许多在线材料都解释了这个概念。

在本章中，我们将只讨论trie数据结构的概述，并重点讨论如何优化基本trie以提高响应时间。

Trie（发音为“try”）是一种树状数据结构，可以紧凑地存储字符串。 该名称来自单词检索（retrieval），这表明它是为字符串检索操作而设计的。

trie 的主要思想包括以下内容：

图13-5显示了一个带有搜索查询 “tree”、“try”、“true”、“toy”、“wish”、“win “的 trie。搜索查询以较粗的边框突出显示。

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

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

自动完成是如何在Trie中工作的？在深入研究该算法之前，让我们先定义一些术语：

下面列出了获得前 k 个搜索最多的查询的步骤：

  1. 找到前缀。时间复杂度：O(p)。
  2. 从前缀节点遍历子树，得到所有有效的子节点。如果一个子节点能够形成一个有效的查询字符串，它就是有效的。时间复杂度：O(c)
  3. 对孩子节点进行排序并获得前 k。 时间复杂度：O(clogc)

让我们用一个如图13-7所示的例子来解释这个算法。假设k等于2，一个用户在搜索框中输入 “tr”。该算法的工作原理如下。

这个算法的时间复杂度是上述每个步骤所花费的时间之和。O(p) + O(c) + O(clogc)

上述算法很简单，但是，它太慢了，因为在最坏的情况下，我们需要遍历整个 trie 来获得前 k 个结果。

下面是两个优化方案。

  1. 限制前缀的最大长度
  2. 缓存每个节点的热门搜索查询

限制前缀的最大长度

用户很少在搜索框中键入长搜索查询。 因此，可以安全地说 p 是一个小整数，比如 50。如果我们限制前缀的长度，“查找前缀”的时间复杂度可以从 O(p) 降低到 O(small constant)， 又名 O(1)。

缓存每个节点的热门搜索查询

为了避免遍历整个 trie，我们在每个节点存储前 k 个最常用的查询。 由于 5 到 10 个自动完成建议对用户来说就足够了，因此 k 是一个相对较小的数字。 在我们的具体案例中，只有前 5 个搜索查询被缓存。

通过在每个节点缓存热门搜索查询，我们显着降低了检索前 5 个查询的时间复杂度。 但是，这种设计需要大量空间来存储每个节点的热门查询。

以空间换时间是非常值得的，因为快速响应时间非常重要。

图13-8显示了更新后的 trie 数据结构。每个节点上都存储了前5个查询。例如，前缀为 “be “的节点存储以下内容。[best: 35, bet: 29, bee: 20, be: 15, beer: 10]。

让我们重新审视一下应用这两个优化后的算法的时间复杂性。

  1. 找到前缀节点。时间复杂度：O(1)
  2. 返回前 k。 由于缓存了前 k 个查询，因此这一步的时间复杂度为 O(1)。 随着每个步骤的时间复杂度降低到 O(1)，我们的算法只需要 O(1) 来获取前 k 个查询。

数据收集服务

在我们以前的设计中，每当用户键入一个搜索查询，数据就会实时更新。由于以下两个原因，这种方法并不实用。

为了设计可扩展的数据收集服务，我们检查数据的来源和使用方式。 像 Twitter 这样的实时应用程序需要最新的自动完成建议。 但是，许多 Google 关键字的自动完成建议每天可能不会有太大变化。

尽管用例不同，但数据收集服务的底层基础保持不变，因为用于构建 trie 的数据通常来自分析或日志服务。

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

查询服务

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

  1. 一个搜索查询被发送到负载均衡器。
  2. 负载均衡器将请求路由到API服务器。
  3. API服务器从Trie Cache获得Trie数据，并为客户端构建自动完成建议。
  4. 如果数据不在Trie Cache中，我们会将数据补充到缓存中。这样一来，所有对同一前缀的后续请求都从缓存中返回。当缓存服务器没有内存或脱机时，就会发生缓存缺失。

查询服务需要闪电般的速度。 我们提出以下优化：

Trie 操作

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

创建

Trie 是由工作人员使用聚合数据创建的。 数据源来自 Analytics Log/DB。

更新

有两种方法可以更新 trie。

方法一：每周更新 trie。一旦创建了新的 trie，新的 trie 将取代旧的 trie。

方法二：直接更新单个 trie 节点。 我们尽量避免这种操作，因为它很慢。 但是，如果 trie 的大小很小，这是一个可以接受的解决方案。 当我们更新一个 trie 节点时，它一直到根的祖先都必须更新，因为祖先存储子节点的热门查询。 图 13-13 显示了更新操作如何工作的示例。 在左侧，搜索查询“beer”的原始值为 10。在右侧，它更新为 30。如您所见，节点及其祖先的“beer”值已更新为 30。

删除

我们必须删除仇恨、暴力、色情或危险的自动完成建议。 我们在 Trie 缓存前面添加一个过滤层（图 13-14）以过滤掉不需要的建议。

拥有过滤层使我们能够灵活地根据不同的过滤规则删除结果。

不需要的建议会以异步方式从数据库中物理删除，以便在下一个更新周期中使用正确的数据集来构建 trie。

扩展存储

现在我们已经开发了一个系统，将自动完成的查询带给用户，现在是时候解决当 trie 增长到无法在一台服务器中容纳时的可扩展性问题了。

由于英语是唯一被支持的语言，一种简单的分片方式是基于第一个字符。这里有一些例子。

按照这个逻辑，我们可以将查询分成26个服务器，因为英语中有26个字母。让我们把基于第一个字符的分片定义为第一层分片。要存储超过26个服务器的数据，我们可以在第二层甚至第三层进行分片。例如，以’a’开头的数据查询可以分成4个服务器：‘aa-ag’，‘ah- an’，‘ao-au’和’av-az’。

乍一看，这种方法似乎很合理，直到你意识到以字母’c’开头的单词比’x’多得多。这就造成了分布不均。

为了缓解数据不平衡问题，我们分析历史数据分布模式并应用更智能的分片逻辑，如图 13-15 所示。 分片映射管理器维护一个查找数据库，用于标识应将行存储在何处。 例如，如果对“s”和“u”、“v”、“w”、“x”、“y”和“z”的合并历史查询数量相似，我们可以维护两个分片：一个 用于“s”，一个用于“u”到“z”。

第4步：总结

在你完成深入探讨后，你的面试官可能会问佴一些后续问题。

面试官：你如何扩展你的设计以支持多语言？

为了支持其他非英语查询，我们将 Unicode 字符存储在 trie 节点中。 如果您不熟悉 Unicode，这里是定义：“一种编码标准涵盖了世界上所有现代和古代书写系统的所有字符”[5]。

面试官：如果一个国家/地区的热门搜索查询与其他国家/地区不同怎么办？

在这种情况下，我们可能会为不同的国家建立不同的 trie。 为了缩短响应时间，我们可以将 trie 存储在 CDN 中。

面试官：我们如何支持趋势（实时）搜索查询？

假设一个新闻事件爆发了，一个搜索查询突然变得很流行。我们原来的设计将无法工作，因为：

构建一个实时搜索的自动完成器是很复杂的，超出了本书的范围，所以我们只给出一些想法：

恭喜你走到了这一步！现在给自己一个鼓励，干得漂亮！

参考资料