需求
让我们设计一个实时建议服务，当用户输入文本进行搜索时，它会向用户推荐术语。类似服务：自动建议，提前键入搜索
难度：中等
1.Typeahead实时建议服务是什么？
Typeahead建议使用户能够搜索已知和经常搜索的术语。当用户输入搜索框时，它会根据用户输入的字符尝试预测查询，并给出完成查询的建议列表。提前输入建议有助于用户更好地表达其搜索查询。这不是关于加快搜索过程，而是关于指导用户并帮助他们构建搜索查询。
2.系统的要求和目标
功能要求：
当用户在查询中键入内容时，我们的服务应建议以用户键入的内容开头的前10个术语。
非功能要求：
建议应实时显示。用户应该能够在200毫秒内看到建议。
3.基本系统设计与算法
我们要解决的问题是，我们需要存储大量的“字符串”，以便用户可以使用任何前缀进行搜索。我们的服务将建议与给定前缀匹配的下一个术语。例如，如果我们的数据库包含以下术语：cap、cat、captain或capital，并且用户键入了“cap”，那么我们的系统应该建议使用“cap”、“captain”和“capital”。
由于我们必须以最小的延迟服务大量查询，因此我们需要提出一种能够高效存储数据的方案，以便能够快速查询数据。我们不能依赖某个数据库来实现这一点；我们需要在内存中以高效的数据结构存储索引。
最适合我们使用的数据结构之一是Trie（发音为“try”）。trie是一种树状数据结构，用于存储短语，其中每个节点以顺序方式存储短语的一个字符。例如，如果我们需要在trie中存储“cap、cat、caption、captain、capital”，它将如下所示：
现在，如果用户键入了“cap”，我们的服务可以遍历trie，转到节点“P”，查找以该前缀开头的所有术语（例如，cap-tion、cap-ital等）。
我们可以合并只有一个分支的节点以节省存储空间。上述trie可按如下方式存储：
我们应该有不区分大小写的trie吗？
- 为了简单和搜索用例，我们假设我们的数据不区分大小写。
如何找到最佳建议？
- 既然我们可以找到所有给定前缀的术语，那么我们如何知道我们应该建议的前10个术语呢？一个简单的解决方案是存储在每个节点终止的搜索计数，例如，如果用户搜索了大约100次“CAPTAIN”和500次“CAPTION”，我们可以将该数字与短语的最后一个字符一起存储。因此，如果用户输入了“CAP”，我们知道前缀“CAP”下搜索最多的单词是“CAPTION”。因此，给定一个前缀，我们可以遍历它下面的子树以找到最重要的建议。
给定前缀，遍历其子树需要多少时间？
- 考虑到我们需要索引的数据量，我们应该期待一棵大树。即使遍历一个子树也需要很长的时间，例如，“系统设计面试问题”这个短语有30层深。因为我们有非常严格的延迟要求，所以我们确实需要提高解决方案的效率。
我们可以在每个节点上存储最佳建议吗？
- 这当然可以加快我们的搜索速度，但需要大量额外的存储空间。我们可以在每个节点上存储前10条建议，然后返回给用户。为了达到所需的效率，我们必须承受存储容量的大幅增加。
- 我们可以通过只存储终端节点的引用而不是存储整个短语来优化存储。为了找到建议的术语，我们需要使用来自终端节点的父引用往回遍历。我们还需要存储每个引用的频率，以跟踪最佳建议。
我们将如何构建这个trie？
- 我们可以自下而上高效地构建我们的trie。每个父节点将递归调用所有子节点，以计算它们的顶级建议和计数。父节点将组合来自其所有子节点的顶级建议，以确定其最佳建议。
如何更新trie？
- 假设每天有50亿次搜索，每秒大约有6万次查询。如果我们尝试为每个查询更新trie，那么它将非常占用资源，这也会妨碍我们的读取请求。处理这个问题的一个解决方案是在一定的时间间隔后离线更新trie。
- 随着新查询的出现，我们可以记录它们并跟踪它们的频率。我们可以记录每个查询，也可以采样并记录每个1000次查询。例如，如果我们不想显示搜索次数少于1000次的术语，则可以安全地记录每1000次搜索的术语。
- 我们可以有一个Map-Reduce（MR）设置来定期（比如每小时）处理所有日志数据。这些乔布斯先生将计算过去一小时内所有搜索词的频率。然后我们可以用这些新数据更新我们的trie。我们可以拍摄trie的当前快照，并使用所有新术语及其频率进行更新。我们应该脱机执行此操作，因为我们不希望我们的读取查询被update trie请求阻止。我们有两个选择：
1.我们可以在每台服务器上复制一份trie，以便脱机更新。一旦完成，我们可以切换到开始使用它，并丢弃旧的。
2.另一个选择是，我们可以为每个trie服务器配置一个主从配置。我们可以在主服务器为流量服务时更新从服务器。一旦更新完成，我们就可以让从机成为我们的新主机。我们可以稍后更新我们的旧主机，然后它也可以开始服务于流量。
我们如何更新typeahead建议的频率？
- 因为我们在每个节点上存储我们的typeahead建议的频率，所以我们也需要更新它们。我们只能更新频率上的差异，而不是从头开始重新计算所有搜索词。如果我们要对过去10天内搜索的所有术语进行计数，我们需要从不再包含的时间段中减去计数，然后添加包含的新时间段的计数。我们可以根据每个项的指数移动平均值（EMA）加上和减去频率。在EMA中，我们更重视最新数据。它也被称为指数加权移动平均。
- 在trie中插入新术语后，我们将转到短语的终端节点并增加其频率。因为我们在每个节点中存储前10个查询，所以这个特定的搜索词可能会跳到其他几个节点的前10个查询中。因此，我们需要更新这些节点的前10个查询。我们必须从节点返回到根。对于每个父项，我们检查当前查询是否是前10个查询的一部分。如果是，我们更新相应的频率。如果没有，我们将检查当前查询的频率是否足够高，可以成为前10名的一部分。如果是这样，我们将插入此新术语，并删除频率最低的术语。
如何从trie中删除一个术语？
- 比如说，由于一些法律问题或仇恨或盗版等原因，我们必须从trie中删除一个术语。当定期更新发生时，我们可以从trie中完全删除此类术语，同时，我们可以在每个服务器上添加一个过滤层，在将其发送给用户之前删除任何此类术语。
对于建议，有哪些不同的排名标准？
- 除了一个简单的计数，术语排名，我们还必须考虑其他因素，例如，新鲜度，用户位置，语言，人口统计，个人历史等。
4.Trie的永久存储
如何将trie存储在文件中，以便我们可以轻松地重建trie—当机器重新启动时？
- 我们可以定期拍摄trie的快照并将其存储在文件中。这将使我们能够在服务器停机时重建trie。为了存储，我们可以从根节点开始，逐级保存trie。对于每个节点，我们可以存储它包含的字符以及它有多少子节点。在每个节点之后，我们应该放置其所有子节点。让我们假设我们有以下trie：
如果我们使用上述方案将这个trie存储在一个文件中，我们将有：“C2，A2，R1，T，P，O1，D”。由此，我们可以很容易地重建我们的trie。
如果您注意到了，我们不会在每个节点中存储顶级建议及其计数。很难存储这些信息；由于我们的trie是自上而下存储的，我们没有在父节点之前创建子节点，因此没有简单的方法来存储它们的引用。为此，我们必须重新计算所有具有计数的顶部术语。这可以在我们构建trie时完成。每个节点将计算其顶部建议并将其传递给其父节点。每个父节点将合并其所有子节点的结果，以找出其最重要的建议。
5.规模估计
如果我们正在建设一项与谷歌规模相同的服务，我们预计每天会有50亿次搜索，这将给我们每秒大约6万次查询。
由于在50亿个查询中会有很多重复项，我们可以假设其中只有20%是唯一的。如果我们只想为前50%的搜索词编制索引，我们就可以摆脱许多搜索频率较低的查询。让我们假设我们将有1亿个我们想要建立索引的唯一术语。
存储估计：
如果每个查询平均由3个单词组成，如果一个单词的平均长度为5个字符，那么我们将得到15个字符的平均查询大小。假设我们需要2个字节来存储一个字符，那么我们将需要30个字节来存储一个平均查询。因此，我们需要的总存储：
100 million * 30 bytes => 3 GB
我们可以期望这些数据每天都有增长，但我们也应该删除一些不再搜索的术语。如果我们假设每天有2%的新查询，并且如果我们在过去一年中保持索引，那么我们应该期望的总存储量为：
3GB (0.02 * 3 GB * 365 days) => 25 GB
6.数据分区
虽然我们的索引可以很容易地放在一台服务器上，但我们仍然可以对它进行分区，以满足我们对更高效率和更低延迟的要求。我们如何有效地划分数据以将其分发到多个服务器上？
- A.基于范围的分区：如果我们根据短语的第一个字母将短语存储在单独的分区中会怎么样。因此，我们将所有以字母“A”开头的术语保存在一个分区中，将以字母“B”开头的术语保存在另一个分区中，依此类推。我们甚至可以将某些不太常见的字母组合到一个数据库分区中。我们应该静态地提出这个分区方案，这样我们就可以始终以可预测的方式存储和搜索术语。
这种方法的主要问题是，它可能导致服务器不平衡，例如，如果我们决定将所有以字母“E”开头的术语放在一个DB分区中，但后来我们意识到，我们有太多以字母“E”开头的术语，无法放在一个DB分区中。
我们可以看到，对于每个静态定义的方案，上述问题都会发生。无法计算每个分区是否静态地适合一台服务器。
- B基于服务器最大容量的分区：假设我们基于服务器的最大内存容量对trie进行分区。只要服务器有可用内存，我们就可以将数据存储在服务器上。每当一个子树无法装入服务器时，我们就会在那里断开分区，将该范围分配给该服务器，然后移动到下一台服务器上重复此过程。假设我们的第一台trie服务器可以存储从“A”到“AABC”的所有术语，这意味着我们的下一台服务器将存储从“AABD”开始的术语。如果我们的第二台服务器最多可以存储“BXA”，那么下一台服务器将从“BXB”开始，依此类推。我们可以保留一个哈希表来快速访问此分区方案：
Server 1, A-AABC
Server 2, AABD-BXA
Server 3, BXB-CDA
对于查询，如果用户键入了“A”，我们必须同时查询服务器1和服务器2，以找到最重要的建议。当用户键入“AA”时，我们仍然需要查询服务器1和2，但当用户键入“AAA”时，我们只需要查询服务器1。
我们可以在trie服务器前面安装一个负载平衡器，它可以存储映射和重定向流量。此外，如果我们从多个服务器进行查询，我们需要在服务器端合并结果以计算总体的顶级结果，或者让我们的客户机这样做。如果我们更愿意在服务器端这样做，我们需要在负载平衡器和trie服务器之间引入另一层服务器（我们称之为聚合器）。这些服务器将聚合来自多个trie服务器的结果，并将最重要的结果返回给客户端。
基于最大容量的分区仍然可以将我们引向热点，例如，如果有很多查询以“cap”开头的术语，则持有它的服务器与其他服务器相比将具有较高的负载。
- C基于术语散列的分区：每个术语将被传递给一个散列函数，该函数将生成一个服务器编号，我们将把术语存储在该服务器上。这将使我们的术语分布随机，从而最小化热点。为了找到一个术语的提前输入建议，我们必须询问所有服务器，然后汇总结果。
7.隐藏物
我们应该意识到，缓存最热门的搜索词对我们的服务非常有帮助。将有一小部分查询负责大部分流量。我们可以在trie服务器前面有单独的缓存服务器，其中保存最频繁搜索的术语及其提前键入的建议。应用服务器应在点击trie服务器之前检查这些缓存服务器，以查看它们是否具有所需的搜索项。
我们还可以建立一个简单的机器学习（ML）模型，尝试根据简单的计数、个性化或趋势数据等预测每个建议的参与度，并缓存这些术语。
8.复制和负载平衡器
我们应该为trie服务器提供副本，以实现负载平衡和容错。我们还需要一个负载均衡器来跟踪数据分区方案，并根据前缀重定向流量。
9.容错性
当trie服务器停机时会发生什么情况？如上所述，我们可以采用主从式配置；如果主设备死亡，则从设备可以在故障转移后接管。任何恢复的服务器都可以基于最后一个快照重建trie。
10.实时建议客户端
我们可以在客户端上执行以下优化以改善用户体验：
- 1.只有在用户50毫秒未按任何键的情况下，客户端才应尝试点击服务器。
- 2.如果用户不断输入，客户端可以取消正在进行的请求。
- 3.最初，客户端可以等待用户输入几个字符。
- 4.客户端可以从服务器预取一些数据以保存将来的请求。
- 5.客户端可以在本地存储建议的最新历史记录。最近的历史上有很高的死亡率重复使用。
- 6.事实证明，与服务器建立早期连接是最重要的问题之一因素。一旦用户打开搜索引擎网站，客户端就可以打开与服务器的连接。因此，当用户键入第一个字符时，客户端不会浪费时间建立连接。
- 7.服务器可以将缓存的一部分推送到CDN和Internet服务提供商（ISP）以提高效率。
11.个性化
用户将收到一些基于其历史搜索、位置、语言等的typeahead建议。我们可以将每个用户的个人历史单独存储在服务器上，并将其缓存在客户端上。在发送给用户之前，服务器可以在最终集合中添加这些个性化术语。个性化搜索应该总是排在其他搜索之前。
参考资料
grok_system_design_interview.pdf
