CHAPTER 13:《DESIGN A SEARCH AUTOCOMPLETE SYSTEM》 第13章 《设计搜索自动补全系统》

当搜索谷歌或在亚马逊购物时，当您键入搜索框时，1或搜索词的更多匹配项会呈现在你面前。这个特性被称为自动补全、提前输入、按需搜索或增量搜索。如图13-1所示当输入“dinner”时，显示自动完成结果列表的谷歌搜索示例进入搜索框。搜索补全是许多产品的一个重要功能。这导致我们给面试的问题:设计一个搜索自动补全系统，也叫“design top k”或者“设计前k个最受搜索的查询”。

步骤1 -了解问题并建立设计范围

解决任何系统设计面试问题的第一步是问足够多的问题澄清要求。下面是应聘者和面试官互动的例子:
候选人:匹配只支持在搜索查询的开头还是在也是中等吗?
面试官:只在搜索查询的开始。
候选人:系统应该返回多少个自动补全建议?
面试官:5
候选人:系统怎么知道返回哪5个建议?
采访者:这是由流行度决定的，由历史查询频率决定的。
候选人:系统支持拼写检查吗?
面试官:不支持拼写检查或自动更正。
候选人:搜索查询是用英语写的吗?
面试官:是的。如果最后时间允许，我们可以讨论多语言支持。
候选人:我们允许大写和特殊字符吗?
面试官:不，我们假设所有搜索查询都是小写字母字符。
候选人:有多少用户使用这个产品?
采访者:1000万DAU。
需求
以下是需求摘要:

• 响应时间快:当用户输入搜索查询时，必须显示自动补全建议足够快。一篇关于Facebook自动补全系统[1]的文章揭示了系统需要在100毫秒内返回结果。否则会导致口吃。
• 相关性:自动补全建议应该与搜索关键词相关。
• 排序:系统返回的结果必须按照流行度或其他排序模型。
• 可扩展:系统可以处理高流量。
• 高可用性:系统应保持可用性和可访问性系统脱机、变慢或出现意外网络错误。

后面的包络估计

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

第二步——提出高层次的设计，并获得认可

在高层上，系统可以分为两部分。
数据收集服务:收集用户输入的查询并实时聚合。

• 实时处理对于大数据集来说并不实用;然而，这是一个好的开始点。我们将深入探索一个更现实的解决方案。
• 查询服务:给定一个搜索查询或前缀，返回5个最常被搜索的词。
  数据收集服务
  让我们用一个简化的例子来看看数据收集服务是如何工作的。假设我们有一个频率表，存储查询字符串及其频率，如图13-2所示。在开始时，频率表为空。之后，用户输入查询" twitch "， " twitter "，依次是“twitter”和“twillo”。频率表的更新方式如图13-2所示。
  

查询服务
假设我们有一个如表13-1所示的频率表。它有两个字段。

• Query:存储查询字符串。
• 频率(Frequency):表示查询被搜索的次数。
  当用户在搜索框中输入“tw”时，显示搜索次数最多的5个查询(图13-3)，假设频率表是基于表13-1得到的。
  
  要获得前5个频繁搜索的查询，执行以下SQL查询:
  
  当数据集比较小时，这是一个可以接受的解决方案。当它很大时，访问数据库成为瓶颈。我们将深入探索优化。

步骤3 -深入设计

在高层设计中，我们讨论了数据收集服务和查询服务。高级别的设计不是最优的，但它可以作为一个很好的起点。在本节中，我们将深入探讨深入了解一些组件并探索优化方法，如下所示:Trie数据结构数据收集服务;

• 查询服务
• 扩展存储空间
• Trie运算

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

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

Trie(发音为“try”)是一种类似树的数据结构，可以紧凑地存储字符串。的Name来自word retrieval，这表明它是为字符串检索而设计的操作。trie的主要思想包括以下几个部分:

• trie是一种类似树的数据结构。
• 根表示一个空字符串。
• 每个节点存储一个字符，有26个子节点，每个子节点对应一个可能的字符。来为了节省空间，我们不会绘制空链接。
• 每个树节点表示一个单词或前缀字符串。
  图13-5展示了一个包含搜索查询" tree “、” try “、” true “、” toy “、” wish “、” win "的树结构。搜索查询用较粗的边框高亮显示。
  
  基本的trie数据结构将字符存储在节点中。为了支持频率排序，频率信息需要包含在节点中。假设我们有以下频率表。
  
  添加频率信息后，更新后的trie数据结构如图13-6所示。
  
  自动补全在trie中是如何工作的?在深入研究算法之前，让我们先定义一些条款。
• p:前缀长度
• n:树中节点的总数
• c:给定节点的子节点数

获取前k个被搜索次数最多的查询的步骤如下:

1. 查找前缀。时间复杂度:O§。
2. 从前缀节点开始遍历子树，获取所有有效的子节点。child是有效的，如果它是
   可以形成有效的查询字符串。时间复杂度:O?
3. 对子进程进行排序，得到前k个。时间复杂度:O(clogc)
   我们用一个如图13-7所示的例子来解释这个算法。假设k等于
   2，用户在搜索框中输入tr。该算法的工作原理如下:
   • 第一步:查找前缀节点“tr”。
   • 第二步:遍历子树，获取所有有效的子节点。在这个例子中，nodes [tree: 10]， [true:[try: 29]都是有效的。
   • 第三步:对子元素排序，得到前2个。[true: 35]和[try: 29]是使用前缀“tr”。

该算法的时间复杂度是上述每一步花费的时间之和:
O§ + O? + O(clogc)
上面的算法很简单。但是，它太慢了，因为我们需要遍历整个trie树在最坏情况下得到前k个结果。下面是两种优化方法:

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

让我们逐一来看这些优化。
限制前缀的最大长度
用户很少在搜索框中输入冗长的查询。因此，可以肯定地说p很小整数，比如50。如果我们限制前缀的长度，“查找”的时间复杂度将会降低前缀’ '可由O§缩减为O(小常数)，即O(1)。
在每个节点缓存top
搜索查询为了避免遍历整个trie树，我们将前k个最常用的查询存储在每个节点上。由于5 ~ 10条自动补全建议对用户来说已经足够了，所以k是一个相对较小的数字。在我们的特定情况下，只有前5个搜索查询被缓存。
通过在每个节点缓存top搜索查询，显著降低了时间复杂度检索前5个查询。然而，这种设计需要大量的空间来存储顶级查询每一个节点。用空间换取时间是非常值得的，因为快速响应时间非常重要。更新后的trie数据结构
如图13-8所示。前5个查询存储在每个节点上。为例如，前缀为“be”的节点存储如下信息:[best: 35, bet: 29, bee: 20, be: 15，啤酒:10)。

在应用了这两种优化之后，让我们重新审视一下算法的时间复杂度:

1. 查找前缀节点。时间复杂度:O(1)
2. 返回前k个查询。由于前k个查询被缓存，这一步的时间复杂度为O(1)。

由于每一步的时间复杂度降低到O(1)，因此算法只需执行一次O(1)来获取前k个查询。
数据收集服务
在我们之前的设计中，每当用户输入搜索查询时，数据都会实时更新。这种方法是不实际的，原因如下。

• 用户每天可能输入数十亿次查询。在每个查询中更新trie显著降低查询服务的速度。
• trie构建完成后，Top建议可能不会有太大变化。因此，没有必要经常更新trie树。

为了设计一个可扩展的数据收集服务，我们要研究数据的来源和方式使用数据。像Twitter这样的实时应用程序需要最新的自动补全建议。然而，对于许多谷歌关键字的自动补全建议可能不会有太大的变化每天。
尽管用例存在差异，但数据收集服务的底层基础保持不变，因为用于构建trie树的数据通常来自分析或日志记录服务。
图13-9展示了重新设计的数据收集服务。每个组件都被检查一个由一个。

分析日志。它存储有关搜索查询的原始数据。日志只支持追加，不支持索引。日志文件示例如表13-3所示。

聚合器。分析日志的大小通常非常大，数据不正确格式。我们需要聚合数据，以便系统可以轻松地处理它。

根据不同的用例，我们可能会以不同的方式聚合数据。对于实时应用例如Twitter，我们在较短的时间间隔内聚合数据，因为实时结果很重要。另一方面，不那么频繁地聚合数据，比如一周一次，可能更好对于许多用例来说已经足够了。在面试过程中，验证实时结果是否有效重要的。我们假设trie是每周重建一次的。
聚合数据。
表13-4展示了一个每周汇总数据的例子。“time”字段表示开始一周的时间。“frequency”字段是对应查询出现次数的总和在那个星期。

工人。worker是一组定期执行异步任务的服务器。它们构建trie数据结构并将其存储在trie DB中。
单词查找
树缓存。Trie缓存是一种分布式缓存系统，它将Trie树保存在内存中以实现快速读取。它每周对数据库进行快照。单词查找树DB。
Trie DB是持久存储。有两种存储数据的方式。

1. 文档存储:由于一个新的trie树是每周构建的，我们可以定期对它进行快照，对其进行序列化，并将序列化后的数据存储在数据库中。像MongoDB[4]这样的文档存储非常适合序列化数据。
2. 键值存储:通过应用。可以将trie树表示为散列表形式[4]
   以下逻辑:
   • 将trie树中的每个前缀映射到散列表中的一个键。
   • 将每个trie节点上的数据映射到散列表中的一个值。

trie树和hash表的映射关系如图13-10所示。
在图13-10中，左边的每个trie节点都被映射到<key, value>右边是一对。如果如果你不清楚键值存储是如何工作的，请参考第6章。
查询服务
在高层设计中，查询服务直接调用数据库获取前5个结果。图13-11展示了改进后的设计，原来的设计效率很低。

3. 搜索查询被发送到负载均衡器。
4. 负载均衡器将请求路由到API服务器。
5. API服务器从trie缓存中获取trie数据并为其构造自动补全建议客户端。
6. 如果数据不在Trie缓存中，我们将数据补充回缓存。这样，所有对相同前缀的后续请求将从缓存返回。缓存未命中当缓存服务器内存不足或脱机时发生。

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

• AJAX请求;对于web应用程序，浏览器通常发送AJAX请求来获取自动完成的结果。AJAX的主要好处是发送/接收请求/响应不会刷新整个网页。
• 浏览器缓存。对于许多应用程序来说，自动补全搜索建议可能行不通短时间内变化很大。因此，自动补全建议可以保存在浏览器中缓存以允许后续请求直接从缓存中获取结果。谷歌搜索引擎使用相同的缓存机制。响应头如图13-12所示你在谷歌搜索引擎上输入“系统设计面试”。如你所见，谷歌在浏览器中缓存结果1小时。请注意:“私有”是缓存控制的意思结果只针对单个用户，不能被共享缓存缓存。“maxage=3600”表示缓存有效期为3600秒，也就是一小时。
  
• 数据采样:对于一个大型系统，记录每个搜索查询需要大量的数据处理能力和存储能力。数据采样很重要。例如，只有1个每N个请求都会被系统记录下来。
  单词查找树操作
  Trie是自动补全系统的核心组件。让我们看看trie算法是如何运行的(创建、更新和删除)工作。
  创建
  Trie是由worker使用聚合的数据创建的。数据的来源来自分析日志/ DB。
  更新
  有两种方法可以更新trie。
  选项1:每周更新trie。一旦创建了一个新的trie树，新的trie树就会取代旧的trie树一个。
  选项2:直接更新每个trie节点。我们尽量避免这种操作，因为它是缓慢。然而，如果trie树的大小很小，它是一个可以接受的解决方案。当我们更新Trie节点，它的祖先节点一直到根节点都必须更新，因为祖先节点存储在顶部儿童问题。图13-13展示了更新操作的工作原理。在在左侧，搜索查询" beer "的原始值为10。在右侧，它被更新到30。可以看到，该节点及其祖先节点的“beer”值被更新为30。
  
  删除
  我们必须删除仇恨、暴力、色情或危险的自动补全建议。我们在Trie缓存前面添加了一个过滤层(图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所示。分片映射管理器维护一个查找数据库，以确定行应该存储在哪里。例如，如果有一个s和u、v、w、x、y和z的历史查询次数加起来差不多，我们可以维护两个分片:一个用于s，另一个用于u到z。

步骤4 -打包

在你完成深入调查后，面试官可能会问你一些后续问题。
面试官:你如何扩展你的设计以支持多种语言?
为了支持其他非英语查询，我们将Unicode字符存储在trie节点中。如果你是如果你不熟悉Unicode，下面是它的定义:“一种编码标准涵盖所有世界上所有书写系统的汉字，现代和古代的“[5]”。
面试官:如果一个国家的搜索结果和其他国家不一样怎么办?
在这种情况下，我们可能会为不同的国家构建不同的尝试。提高响应速度此时，我们可以将try语句存储在cdn中。
面试官:我们如何支持趋势化(实时)搜索查询?
假设发生了一个新闻事件，搜索查询突然变得流行起来。我们最初
设计将无法工作，因为:

• 离线的worker还没有计划更新trie，因为这是计划运行的
• 每周一次。即使安排了，构建trie树也需要很长时间。

构建实时搜索自动补全功能很复杂，超出了本书的范围所以我们只给出一些想法:通过分片减少工作数据集;

• 改变排名模型，为最近的搜索查询分配更多的权重。
• 数据可能以流的形式出现，因此我们不能一次访问所有数据。流媒体
• 数据是指数据不断产生。流处理需要一组不同的系统:Apache Hadoop MapReduce[6]、Apache Spark Streaming[7]、Apache Storm[8]、Apache Kafka[9]等。因为所有这些主题都需要特定的领域知识，我们在这里不讨论细节。

恭喜你走到了这一步!现在给自己一点鼓励吧。好工作!

参考资料
[1]预输入查询的寿命:https://www.facebook.com/notes/facebookengineering/ The - Life -of-a- Typeahead - Query /389105248919/
我们如何构建Prefix:一个可扩展的前缀搜索服务，支持自动完成:
https://medium.com/@prefixyteam how-we-built-prefixy-a-scalable-prefix-search-service for-powering-autocomplete-c20f98e2eff1
[3]前缀哈希树一种分布式哈希表上的索引数据结构:
https://people.eecs.berkeley.edu/~sylvia/papers/pht.pdf
[4] MongoDB wikipedia: https://en.wikipedia.org/wiki/MongoDB
[5] Unicode常见问题:https://www.unicode.org/faq/basic_q.html
[6] Apache hadoop: https://hadoop.apache.org/
[7] Spark streaming: https://spark.apache.org/streaming/
[8] Apache storm: https://storm.apache.org/
[9] Apache kafka: https://kafka.apache.org/documentation/