系统设计::设计一个搜索自动补全系统

设计一个搜索自动补全系统

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

理解问题并确定设计范围

处理任何系统设计面试问题的第一步是提出足够的问题来澄清需求。下面是一个应聘者与面试官互动的例子。

应聘者：是否只支持在搜索查询的开始阶段进行匹配，还是在中间也支持？ 面试官：只有在搜索查询的开始阶段。 应聘者：系统应该返回多少个自动补全的建议？ 面试官：5 应聘者：系统如何知道要返回哪 5 条建议？ 面试官：这是由受欢迎程度决定的，由历史查询频率决定。 应聘者：系统是否支持拼写检查？ 面试官：不，不支持拼写检查或自动更正。 应聘者：搜索查询是用英语吗？ 面试官：是的。如果最后时间允许，我们可以讨论多语言支持。 应聘者：我们是否允许大写字母和特殊字符？ 面试官：不，我们假设所有的搜索查询都是小写字母。 应聘者：有多少用户使用该产品？ 面试官：1000 万 DAU。

以下是需求的摘要。

  • 快速响应时间。当用户输入搜索查询时，自动补全的建议必须足够快地显示出来。一篇关于 Facebook 自动补全系统的文章[1]显示，该系统需要在 100 毫秒内返回结果。否则会造成卡顿。
  • 相关性。自动补全的建议应该与搜索词相关。
  • 排序。系统返回的结果必须按照流行度或其他排名模式进行排序。
  • 可扩展性。系统可以处理高流量。
  • 高可用性。当系统的一部分脱机、速度减慢或遇到意外的网络错误时，系统应保持可用和可访问。

粗略估计

假设有 1000 万日活跃用户（DAU）。

  • 一个人平均每天进行 10 次搜索。
  • 每个查询字符串有 20 个字节的数据。
  • 假设我们使用 ASCII 字符编码。1 个字符 = 1 个字节
  • 假设一个查询包含 4 个词，每个词平均包含 5 个字符。
  • 那就是每个查询有 4 x 5 = 20 字节。
  • 对于在搜索框中输入的每一个字符，客户端都会向后台发送一个自动补全建议的请求。平均来说，每个搜索查询会发送 20 个请求。例如，在你输入完"dinner"时，以下 6 个请求被发送到后端。
    search?q=d
    search?q=di
    search?q=din
    search?q=dinn
    search?q=dinne
    search?q=dinner
  • ~24,000 次/秒（QPS）= 10,000,000 用户 * 10 次/天 * 20 个字符/24 小时/3600 秒。
  • 峰值 QPS = QPS * 2 = ~48,000
  • 假设每天的查询中有 20% 是新的。1000 万 * 10 次查询/天 * 每次查询 20 字节 * 20% = 0.4GB。这意味着每天有 0.4GB 的新数据被添加到存储中。

提出高层次的设计并获得认同

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

  • 数据收集服务。它收集用户的输入查询，并实时汇总它们。对于大型数据集来说，实时处理并不实际；但是，这是一个很好的起点。我们将在深入研究中探索一个更现实的解决方案。
  • 查询服务。给定一个搜索查询或前缀，返回 5 个最常搜索的术语。

数据收集服务

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

查询服务

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

  • 查询：它存储查询字符串。
  • 频率：它代表一个查询被搜索的次数。

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

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

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

深入设计

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

  • Trie 数据结构
  • 数据收集服务
  • 查询服务
  • 扩展存储
  • Trie 操作

Trie 数据结构

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

了解基本的 trie 数据结构对于这个面试问题是至关重要的。然而，这更像是一个数据结构问题，而不是一个系统设计问题。此外，许多在线材料都解释了这个概念。在本章中，我们将只讨论 trie 数据结构的概述，并着重讨论如何优化基本 trie 以提高响应时间。

Trie（发音"try”）是一种树状的数据结构，可以紧凑地存储字符串。这个名字来自于检索一词，表明它是为字符串检索操作设计的。trie 的主要思想包括以下内容。

  • trie 是一个树状的数据结构。
  • 根代表一个空字符串。
  • 每个节点存储一个字符，有 26 个子节点，每个子节点代表一个可能的字符。为了节省空间，我们不画空链接。
  • 每个树节点代表一个单词或一个前缀字符串。

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

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

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

自动补全是如何在 Trie 中工作的？在深入研究算法之前，让我们定义一些术语。

  • p：前缀的长度
  • n：trie 中的节点总数
  • c：一个给定节点的子节点的数量

获得前 k 个搜索次数最多的查询的步骤如下。

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

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

  • 第 1 步：找到前缀节"tr"。
  • 第 2 步：遍历子树，得到所有有效的子节点。在这种情况下，节点[tree: 10]、[true: 35]、[try: 29]是有效的。
  • 第 3 步：对子节点进行排序，得到前两名。[true: 35]和[try: 29]是前缀"t"的前两个查询。

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

上述算法是直截了当的。然而，它太慢了，因为在最坏的情况下，我们需要遍历整个 trie 来获得前 k 个结果。下面是两个优化方案。

  1. 限制前缀的最大长度
  2. 缓存每个节点上的顶级搜索查询 让我们逐一看看这些优化措施。

限制前缀的最大长度 用户很少在搜索框中输入一个长的搜索查询。因此，可以说 p 是一个小的整数，比如 50。如果我们限制前缀的长度，“查找前"的时间复杂度就可以从 O(p)减少到 O(小常数)，也就是 O(1)。

在每个节点上缓存顶级搜索查询 为了避免遍历整个三角形，我们在每个节点上存储前 k 个最常用的查询。由于 5 到 10 个自动补全的建议对用户来说已经足够了，所以 k 是一个相对较小的数字。在我们的具体案例中，只有前 5 个搜索查询被缓存。

通过在每个节点缓存顶级搜索查询，我们大大降低了检索前 5 个查询的时间复杂性。然而，这种设计需要大量的空间来存储每个节点的顶级查询。用空间换取时间是非常值得的，因为快速响应时间非常重要。

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

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

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

数据收集服务

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

  • 用户每天可能会输入数十亿次的查询。在每次查询中更新 trie 会大大减慢查询服务的速度。
  • 一旦建立了 trie，顶级建议可能不会有太大变化。因此，没有必要经常更新 trie。

为了设计一个可扩展的数据收集服务，我们研究了数据的来源和数据的使用方式。像 Twitter 这样的实时应用需要最新的自动补全建议。然而，许多谷歌关键词的自动补全建议可能每天都不会有太大变化。

尽管用例不同，数据收集服务的底层基础仍然是相同的，因为用于建立三角形的数据通常来自分析或日志服务。

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

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

聚合器。

分析日志的大小通常非常大，而且数据的格式也不对。我们需要聚合数据，以便我们的系统可以轻松处理这些数据。

根据不同的用例，我们可能会以不同的方式聚合数据。对于 Twitter 这样的实时应用，我们会在较短的时间间隔内聚合数据，因为实时结果很重要。另一方面，对于许多用例来说，聚集数据的频率较低，比如每周一次，可能就足够了。在采访过程中，验证实时结果是否重要。我们假设 Trie 每周都会重建。

聚合的数据。

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

工作者。工作者是一组服务器，以固定的时间间隔执行异步工作。他们建立 Trie 数据结构并将其存储在 Trie DB 中。

Trie Cache。Trie Cache 是一个分布式缓存系统，它将 Trie 保存在内存中，以便快速读取。它每周对数据库进行一次快照。

Trie DB。Trie DB 是持久性存储。有两个选项可用于存储数据。

  1. 文件存储。由于每周都会建立一个新的 Trie，我们可以定期对其进行快照，将其序列化，并将序列化的数据存储在数据库中。像 MongoDB[4]这样的文档存储很适合序列化的数据。
  2. 键值存储。通过应用以下逻辑，一个 trie 可以用哈希表的形式来表示 [4]。
    • trie 中的每个前缀都被映射到哈希表中的一个键。
    • 每个 trie 节点上的数据被映射到哈希表中的一个值。

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

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

查询服务

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

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

查询服务需要快如闪电的速度。我们提出以下优化方案。

  • AJAX 请求。对于网络应用，浏览器通常会发送 AJAX 请求来获取自动补全的结果。AJAX 的主要好处是，发送/接收请求/响应时不会刷新整个网页。
  • 浏览器缓存。对于许多应用程序，自动补全搜索建议可能不会在短时间内
  • 短时间内变化不大。因此，自动补全的建议可以保存在浏览器缓存中，以允许后续请求直接从缓存中获得结果。谷歌搜索引擎也使用同样的缓存机制。图 13-12 显示了当你在 Google 搜索引擎上输"系统设计面"时的响应头。正如你所看到的，Google 将结果在浏览器中缓存了 1 小时。请注意：cache-control 中"privat"意味着结果是为单个用户准备的，不能被共享缓存所缓存。“maxage=360"意味着缓存的有效期为 3600 秒，也就是一个小时。
  • 数据采样。对于一个大规模的系统，记录每个搜索查询需要大量的处理能力和存储。数据采样很重要。例如，每 N 个请求中只有 1 个被系统记录下来。

Trie 操作

Trie 是自动补全系统的一个核心组成部分。让我们来看看 Trie 操作（创建、更新和删除）是如何工作的。

创建

Trie 是由工人使用聚合的数据创建的。数据的来源是来自分析日志/数据库。

更新

有两种方法来更新 trie。

选项 1：每周更新 trie。一旦一个新的 trie 被创建，新的 trie 将取代旧的 trie。

选项 2：直接更新单个 trie 节点。我们尽量避免这种操作，因为它很慢。然而，如果 trie 的大小较小，它是一个可以接受的解决方案。当我们更新一个 trie 节点时，它的祖先一直到根都必须被更新，因为祖先存储了子节点的顶级查询。图 13-13 显示了一个更新操作的例子。在左边，搜索查"啤"的原始值是 10。在右边，它被更新为 30。正如你所看到的，该节点和它的祖先"啤"值被更新为 30。

删除

我们必须删除仇恨的、暴力的、色情的、或危险的自动补全建议。我们在 Trie Cache 前面添加一个过滤层（图 13-14）来过滤掉不需要的建议。有了过滤层，我们就可以根据不同的过滤规则灵活地删除结果。不需要的建议被异步地从数据库中移除，这样正确的数据集将在下一个更新周期中被用于构建 Trie。

扩展存储

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

由于英语是唯一被支持的语言，一种天真的分片方式是基于第一个字符。下面是一些例子。

  • 如果我们需要两台服务器来存储，我们可以在第一台服务器上存储从’a’到’m’的查询，而在第二台服务器上存储’n’到’z’的查询。
  • 如果我们需要三台服务器，我们可以把查询分成’a’到’i’，‘j’到’r’，’s’到’z’。

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

乍一看，这种方法似乎很合理，直到你意识到，以字母’c’开头的单词比’x’多得多。这就造成了分布不均。为了缓解数据不平衡问题，我们分析了历史数据分布模式，并应用了更智能的分片逻辑，如图 13-15 所示。分片地图管理器维护着一个查找数据库，用于识别行应该被存储在哪里。例如，如果"u”、“v”、“w”、“x"的历史查询数量相似，我们可以维护两个分片：一个用"s”，另一个用”““z”。

总结

在你完成深层研究后，你的面试官可能会问你一些后续问题。

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

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

采访者。如果一个国家的顶级搜索查询与其他国家不同怎么办？

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

采访者。我们如何支持趋势性（实时）的搜索查询？

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

  • 离线工人还没有被安排更新 Trie，因为这被安排在每周的基础上运行。
  • 即使它被安排了，也需要太长的时间来建立三角形。

构建实时搜索自动补全系统很复杂，超出了本书的范围，所以我们只给出一些想法。

  • 通过分片减少工作数据集。
  • 改变排名模型，给最近的搜索查询分配更多的权重。
  • 数据可能以流的形式出现，所以我们不能一次就获得所有的数据。流式数据意味着数据是连续产生的。流处理需要一套不同的系统。Apache Hadoop MapReduce [6], Apache Spark Streaming [7], Apache Storm[8]、Apache Kafka [9]等。因为所有这些主题都需要特定的领域知识，所以我们在此不做详述。

恭喜你走到这一步! 现在给自己拍拍背吧。干得好!

参考资料

[1] The Life of a Typeahead Query
[2] How We Built Prefixy: A Scalable Prefix Search Service for Powering Autocomplete
[3] Prefix Hash Tree An Indexing Data Structure over Distributed Hash Tables
[4] MongoDB wikipedia
[5] Unicode frequently asked questions
[6] Apache hadoop
[7] Spark streaming
[8] Apache storm
[9] Apache kafka