如何构建Google搜索自动完成功能

每当您开始在google上输入搜索内容时，您都会获得推荐列表，并且键入的字母越多，推荐的准确性就越高。如果您像我一样，您总是想知道这是如何工作的-是存储倒排索引还是其他内容？

这里适合的数据结构是Trie。

系统要求

考虑到Google的规模，我们需要牢记的因素是延迟，一致性和可用性。一个理想的延迟应该是非常低的，给人/每个信你可以键入改变的建议。接下来，系统需要一直可用。但是，这里可以包含一致性。每次键入内容时，它都会更改以前存储的查询的频率，这会影响建议。此处稍有延迟是可以的，最终的一致性也将起作用。

方法1

特里表示一个单词为树，每个字母为节点，下一个字母为子节点，依此类推。Google还会以Trie的形式存储每个单词/句子。在这里考虑，父节点是“ h”，其子节点是“ a”，然后是“ r”，依此类推。每个节点可以有26个子节点。现在，每个节点还可以存储搜索到的每个字母的频率。

例如，节点“ h”存储搜索频率“ h”，其子节点“ a”存储搜索频率“ ha”，依此类推，现在，如果我们要显示前N条建议，请说键入“ h”，建议应该显示“ harry potter”或“ harry styles”。然后，我们需要将父节点中的所有建议排序到频率的每个级别并进行显示，这意味着扫描数TB的数据，并且因为延迟是我们的目标，所以这种扫描方法将行不通。

方法＃2

为了使这种方法更有效，我们可以在每个节点上存储更多数据以及搜索频率。让我们在它下面的子树中的每个节点上存储前N个查询。这意味着节点“ h”将存储“哈里·波特”，“哈雷·戴维森”等查询。如果将树遍历到“ harl”（即键入“ harl”），则节点“ l”将具有诸如“ harley davidson”，“ harley quinn”之类的查询。

与前一种方法相比，这种方法更好，因为读取效率很高。每当节点的频率更新时，我们都会从该节点回溯到其父节点，直到到达根节点为止。对于每个父级，我们检查当前查询是否是前N个查询的一部分。如果是，则将相应的频率替换为更新的频率。如果不是，则检查当前查询的频率是否足够高以成为前N个查询的一部分。

如果是这样，我们用频率更新前N个。尽管这种方法有效，但确实会影响我们的读取效率-每次执行写入/更新操作时，我们都需要在节点上加一个锁，这样用户就不会得到过时的值，但是如果我们考虑最终的一致性，则可能没什么大问题。用户可能会暂时获取过时的值，但是最终它将保持一致。尽管如此，我们将研究这种方法的扩展。

方法3

作为先前方法的扩展，我们可以离线存储数据。我们可以将查询的哈希图存储到其频率，一旦频率达到设置的阈值，便可以将其映射到服务器。

缩放比例

现在，将不会只有一台大型服务器来存储所有PB级数据。我们会垂直扩展生活–有更好的方法。我们可以通过前缀在各种服务器上分发数据（分片）。例如，前缀“ a”，“ aa”，“ aab”等将在服务器＃1上等等。我们可以使用负载均衡器来保留带有服务器编号的前缀映射。

但是考虑到这一点，与字母“ a”相比，某些具有“ x”，“ xa”，“ yy”等数据的服务器将具有较少的流量，因此，可以对每个服务器进行阈值检查；如果负载如果流量超过该流量，则可以在其他分片之间分发数据。

如果您担心单点故障，则可能有许多服务器充当负载平衡器，因此，如果任何负载平衡器发生故障，则将其替换为另一个。您可以使用ZooKeepers持续运行状况检查负载平衡器并采取相应的措施。