8. 设计输入提示建议
难度等级：中等
让我们设计一个实时建议服务，当用户输入文本搜索时给用户推荐搜索项。类似服务：Auto-suggestions，Typeahead search。
1. 什么是输入提示建议？
输入提示建议允许用户搜索已知和被频繁搜索的搜索项。当用户在搜索框中输入时，该服务会基于用户输入的文字尝试预测查询语句，并给出可以填充完整查询语句的建议列表。输入提示查询帮助用户更好地表达搜索的语句。该服务的目的不在于加快搜索的过程，而是在用户组织搜索的语句时引导和帮助用户。
2. 系统的要求和目标
功能性要求
当用户输入查询语句时，我们的服务应该给出以用户的输入作为前缀的 10 个最靠前的搜索项的建议。
非功能性要求
建议应该实时显示。用户应该在 200 毫秒内看到建议内容。
3. 基本的系统设计和算法
我们需要解决的问题是用一种合适的方法存储大量的字符串，使得用户可以用任意前缀搜索。我们的服务将推荐匹配给定前缀的搜索项。例如，假设我们的数据库包含以下搜索项：cap、cat、captain 和 capital，用户输入了 cap，我们的系统应该建议 cap、captain 和 capital。
由于我们需要在最小的延迟下处理大量查询，我们的方案应该满足高效存储数据，使得数据可以被快速查找。我们不能依赖于数据库，我们需要将索引使用一种高效的数据结构存储在内存中。
可以满足我们的要求的最合适的数据结构之一是前缀树。前缀树是一种像树的数据结构，用于存储短语，每个结点按顺序存储短语中的一个字符。例如，假设我们需要将 cap、cat、caption、captain、capital 存入前缀树，则前缀树如下所示：
如果用户输入 cap，我们的服务可以在前缀树中遍历到结点 P，找到匹配该前缀的所有搜索项（例如，cap-tain、cap-ital 等）。
我们可以合并只有一个分支的结点以节约存储空间。上述前缀树可以按如下方式存储：
我们是否应该使用不区分大小写的前缀树？为了简化实现和方便用户搜索，我们假设数据是不区分大小写的。
如何找到最靠前的建议？在给定前缀的情况下可以找到所有的搜索项，我们如何知道哪 10 个最靠前的搜索项是我们应该建议的？一个简单的解决方案是记录在每个结点处结束的搜索次数，例如，假设用户搜索了 100 次 CAPTAIN 和 500 次 CAPTION，我们可以将数字存储在短语的最后一个字符中。此时如果用户输入 CAP，我们可以知道匹配前缀 CAP 的最靠前的搜索词是 CAPTION。因此，在给定前缀的情况下，我们可以遍历该前缀的子树找到最靠前的建议。
给定前缀，遍历子树需要多少时间？考虑到需要检索的数据量，我们应该预期有一个巨大的树。甚至遍历子树都需要很长时间，例如，短语 system design interview questions 的深度达到 30 层。由于我们的延迟要求很严格，我们确实需要改善我们的方案中的效率。
我们是否可以存储每个结点的最靠前建议？这样做确实可以提升搜索的速度，但是需要大量的额外存储。我们可以在每个结点处存储返回给用户的 10 个最靠前的建议。为了达到要求的效率，我们必须承受存储容量的大量增加。
我们可以通过只存储结束结点的引用而不是存储整个短语的方式优化存储。为了找到建议的搜索项，我们需要从结束结点开始使用父结点引用反向遍历。我们也需要存储每个引用的频率以维护最靠前的建议。
我们如何创建前缀树？我们可以使用自底向上的方式高效地创建前缀树。每个父结点将递归地调用所有的子结点，对子结点计算最靠前推荐和计数。父结点将结合所有子结点的最靠前推荐，决定自身的最靠前推荐。
如何更新前缀树？假设每天有 50 亿次搜索，即每秒有 6 万次查询。如果每次查询都更新前缀树，将会占用大量资源，也会阻碍读请求。处理这个问题的一个解决方案是在特定区间之后离线更新前缀树。
当新的查询进入时，我们可以使用日志记录这些查询，同时维护这些查询的频率。我们可以记录每一条查询，或者使用采样的方式，每 1000 条查询记录一条。例如，如果我们不想展示搜索次数少于 1000 次的搜索项，每 1000 条搜索项记录一次是更安全的。
我们可以使用映射归约（Map-Reduce，MR）的机制周期性地处理所有的日志数据，例如每小时一次。这些映射归约任务讲计算过去一个小时内的所有搜索项的频率。然后我们可以使用新数据更新前缀树。我们可以获取前缀树的当前快照，使用所有的新搜索项及其频率更新前缀树。为了避免更新前缀树的请求将读请求堵塞，我们应该离线更新前缀树。我们有两个方案：
我们可以在每台服务器上存储一份复制的前缀树，以实现离线更新。当更新完成时，我们可以开始使用新的前缀树，丢弃老的前缀树。
另一个方案是我们可以在每台前缀树服务器上安排一个主从配置。当主服务器处理流量时，我们可以更新二级服务器。当更新完成时，我们可以将二级服务器作为新的主服务器。后续可以更新老的主服务器并使其也能开始处理流量。
如何更新输入提示建议的频率？由于我们在每个结点中存储输入提示建议的频率，我们也需要更新频率。我们可以只更新频率的差值，而不是重新计算每个搜索项的频率。如果我们需要计算过去 10 天内搜索过的所有搜索项的计数，我们需要减去不再包含的时间段内的计数并加上新包含的时间段内的计数。我们可以基于每个搜索项的指数移动平均数（Exponential Moving Average，EMA）增加和减少频率。在指数移动平均数中，我们给最后的数据赋予更多的权重。该指标也称为指数加权移动平均数。
在前缀树中插入一个新搜索项之后，我们需要移动到短语的结束结点处更新其频率。由于我们在每个结点中存储最靠前的 10 个查询，有可能一个特定的搜索项进入了若干其他结点的最靠前的 10 个查询中。因此，我们需要更新那些结点的最靠前的 10 个查询。我们需要从结束结点开始向根结点反向遍历。对于每个父结点，我们检查当前查询是否在最靠前的 10 个查询中。如果成立，我们更新相应的频率。否则，我们检查当前查询的频率是否符合进入最靠前的 10 个查询。如果成立，我们插入这个新搜索项并移除频率最低的搜索项。
如何从前缀树中移除一个搜索项？假设我们因为法律问题、不喜欢某个搜索项、盗版等原因必须移除一个搜索项。当前缀树定期更新时，我们可以完全删除这样的搜索项。与此同时，我们可以在每台服务器上增加一个过滤层，在将推荐发送给用户之前移除所有的这些搜索项。
建议的不同排序标准有哪些？除了简单的计数以外，对于搜索项的排序，我们也必须考虑其他因素，例如：新鲜度、用户位置、语言、人口统计数据、个人历史等。
4. 前缀树的永久存储
如何将前缀树存入文件，使得我们可以方便地重建前缀树——当机器重启时需要这个功能？我们可以周期性地获取前缀树的快照存入文件。浙江允许我们在服务器宕机时重建前缀树。存储前缀树时，我们可以从根结点开始按层存储前缀树。对于每个结点，我们可以存储该结点包含的字符以及有多少子结点。在每个结点之后，我们应该存储其所有子结点。假设我们有如下前缀树：
如果我们使用上述方案将这个前缀树存入文件，存储的内容是：「C2,A2,R1,T,P,O1,D」。从该存储内容可以方便地重建前缀树。
你可能注意到，我们并没有在每个结点中存储最靠前的建议及其计数。这样的信息很难存储，由于我们的前缀树是自顶向下存储的，子结点不可能在父结点之前创建，因此没有简单的方法存储引用。对此，我们必须重新计算所有的最靠前搜索项和计数。这可以在构建前缀树时完成。每个结点将计算其最靠前的建议并将其传给父结点。每个父结点将合并所有子结点的结果，得到其最靠前的建议。
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 开始的搜索项放入一个数据库分区中，但是后面我们意识到以字母 E 开始的搜索项过多，无法放入一个数据库分区中。
我们可以看到，上述问题对于每个静态定义的机制都会发生。使用静态的方法无法计算每个分区是否可以放入一台服务器。
b. 基于服务器的最大容量划分：我们可以基于服务器的最大内存容量划分前缀树。当一台服务器有剩余内存时，我们可以在这台服务器上持续存储数据。当一个子树无法存入服务器时，我们在该子树的位置结束分区，将该范围赋给当前服务器，然后在下一台服务器上重复该过程。假设第一台前缀树服务器可以存储从 A 到 AABC 的所有搜索项，这意味着下一台服务器将存储从 AABD 开始的搜索项。如果第二台服务器可以存储到 BXA，下一台服务器将存储从 BXB 开始的搜索项，以此类推。我们可以维护一个哈希表快速访问划分机制：
1 号服务器，A-AABC；
2 号服务器，AABD-BXA；
3 号服务器，BXB-CDA。
查询时，如果用户输入 A，我们必须查询 1 号服务器和 2 号服务器寻找最靠前的推荐。如果用户输入 AA，我们仍必须查询 1 号服务器和 2 号服务器，但是如果用户输入 AAA，我们只需要查询 1 号服务器。
我们可以在前缀树服务器之前安排负载均衡器，负载均衡器存储哈希映射并重新分配流量。此外，如果我们从多台服务器查询，我们或者需要在服务器端合并结果以计算总体最靠前的结果，或者让客户端做这件事情。如果我们倾向于在服务器端做这件事情，我们需要在负载均衡器和前缀树服务器之间引入新的一层服务器（我们将其称为汇合器）。这些服务将回合多台前缀树服务器的结果并将最靠前的结果返回给客户端。
基于最大容量划分仍会导致聚集，例如，如果有大量查询的搜索项都以 cap 开始，存储该项的服务器将比其他服务器有更高的负载。
c. 基于搜索项的哈希划分：每个搜索项将被传给一个哈希函数生成服务器编号，我们将搜索项存储在那台服务器上。这样可以使得我们的搜索项随机分布，最小化聚集。为了找到输入提示建议，我们必须访问所有的服务器然后聚集结果。
7. 缓存
我们应该意识到缓存最靠前的搜索项对我们的服务是有极大的帮助的。很小的一部分查询将会承担绝大多数流量。我们可以在前缀树服务器之前安排独立的缓存服务器，缓存服务器存储最高频的搜索项和输入提示建议。应用服务器应该在联系前缀树服务器之前检查这些缓存服务器，寻找缓存服务器中是否有预期的搜索项。
我们也可以建立一个简单的机器学习模型，用于尝试基于简单计数、个性化、主流数据等方面预测建议，并缓存这些搜索项。
8. 备份和负载均衡
从负载均衡和容错的角度考虑，我们都需要对前缀树服务器做备份。我们也需要负载均衡器跟踪数据划分的方案，并基于前缀重新分配流量。
9. 容错
当前缀树服务器宕机时会发生什么？根据上述讨论，我们可以有一个主从配置。当主服务器宕机时，二级服务器可以在宕机之后接手。任何作为后备的服务器可以基于最后一个快照重新创建前缀树。
10. 输入提示客户端
我们可以在客户端执行以下优化以改善用户体验：
只有当用户在 50 毫秒内没有按下任意键时，客户端才应该联系服务器。
当用户持续输入时，客户端可以取消尚未完成的请求。
初始时，客户端可以等待用户输入几个字符之后再做处理。
客户端可以预先从服务器上获取一些数据以节省将来的请求。
客户端可以再本地存储最近的建议历史。最近的历史中有很大比例的内容会被复用。
和服务器建立早期连接是最重要的因素之一。当用户打开搜索引擎网页的时刻，客户端即可和服务器建立连接。因此当用户输入第一个字符时，客户端不需要浪费时间建立连接。
客户端可以将部分缓存内容存储到内容分发网络（CDN）和因特网服务供应商（ISP）上，以提升效率。
11. 个性化
用户将接收到基于他们的历史搜索、位置、语言等方面的输入提示建议。我们可以在服务器上独立地存储每个用户的个人历史，同时缓存到客户端。在将输入提示建议的最终集合发送给用户之前，服务器可以将个性化搜索项添加到最终集合中。个性化搜索项应该总是在其他搜索项之前出现。
Last updated