每当您在 Google 上开始键入搜索内容时，您都会收到一个建议列表，您键入的字母越多，建议就越准确。如果你像我一样，你总是想知道这是如何工作的——是存储了倒置的索引，还是其他的东西？
此处合适的数据结构是 Trie。
您可能还喜欢：实施低级别 Trie：用C++求解。
系统要求
考虑到 Google 的规模，我们需要牢记的因素包括延迟、一致性和可用性。理想的延迟应该非常低，对要键入的每个字母给出/更改建议。接下来，系统需要一直可用;但是，可以在此处包含一致性。每次键入内容时，都会更改以前存储的查询的频率，这会影响建议。轻微的延迟在这里是好的，最终的一致性也将工作。
概念：
接近#1
Trie 将单词表示为树，每个字母作为节点，其子节点的下一个字母，等等。Google 还以三元形式存储每个单词/句子。请考虑此处，父节点为”h”，其子节点为”a”，然后是”r”，等等。每个节点可以有 26 个子节点。现在，每个节点还可以存储搜索的每个字母的频率。
例如，节点”h”存储搜索频率为”h”。其子节点”a”存储”ha”等搜索频率。现在，如果我们想要显示前 N 个建议，假设您键入了”h”，建议应显示”哈里波特”或”哈里风格”。然后，我们需要将父节点的所有建议排序到频率的每个级别，并显示它。这意味着扫描数 TB 的数据，由于延迟是我们的目标，因此这种扫描方法不起作用。
接近#2
为了使此方法更高效，我们可以在每个节点上存储更多的数据以及搜索频率。让我们从它下面的子树中在每个节点存储前 N 个查询。这意味着节点”h”将存储查询，如”哈里波特”，”哈利·戴维森”等。如果你沿着树遍历到”竖”（即你键入”harl”），节点，”l”，将有查询，如”哈利戴维森”，”哈利奎恩”等。
此方法比前一种方法更好，因为读取相当有效对于每个父查询，我们检查当前查询是否属于前 N 个查询。如果是这样，我们将相应的频率替换为更新的频率。如果没有，我们会检查当前查询的频率是否足够高，足以成为前 N 的一部分。
如果是这样，我们会用频率更新前 N。尽管这种方法有效，但它确实会影响我们的读取效率 – 每次写入/更新时，我们都需要对节点进行锁定，这样用户就不会得到过时值，但如果考虑最终一致性，那么这可能不是太大的问题。用户可能会获得一段时间的过时值，但最终，它会获得一致。不过，我们还是会研究这种方法的扩展。
接近#3
作为前一种方法的扩展，我们可以脱机存储数据。我们可以将查询的哈希映射存储到其频率，一旦频率达到设置的阈值，我们可以将其映射到服务器。
缩放
现在，不会只有一台大型服务器存储所有 PB 的数据;我们会垂直扩展生活 – 有一个更好的方法。我们可以按前缀在不同服务器上分发数据（分片）。例如，”a”、”aa”、”aab”等前缀将放在服务器#1上，等等。我们可以使用负载均衡器将前缀的映射与服务器编号保持一起。
但请考虑这一点，与字母”a”相比，某些具有”x”、”xa”、”yy”等数据的数据的服务器流量会更少。因此，每台服务器上都可以进行阈值检查;如果负载超过该流量，则数据可以分布在其他分片中。
如果您担心单点故障，则可能有许多服务器充当负载均衡器，因此，如果任何负载均衡器出现故障，则由另一个服务器替换。您可以使用ZooKeepers持续运行状况检查负载平衡器并相应地操作。