在搜索框输入部分关键字后，自动补全后面的关键字，本质是top k问题。

Step 1 - 明确需求

以下是一些可供参考的需求探讨示例：

  1. 补齐的关键字是只需要从头开始匹配，还是需要从中间匹配？=> 只需要从头开始匹配
  2. 需要提示几个可供补全的关键字提示？=> 5
  3. 根据什么因素确定需要补全哪5个关键字？=> 根据历史查询选出最受欢迎的5个关键字
  4. 需要支持拼写检查吗？=>不需要
  5. 只支持英文吗？=>暂时是，后续可讨论多语言设计 
  6. 需要考虑大小写和特殊字符吗？=>不需要，假设所有补全都按小写字母来补全
  7. 日活多少？=> 1000万

此外还一些额外要求：

  • 快速的响应时间：当用户输入搜索词时，必须快速地显示搜索提示。
  • 关联程度：自动补全的搜索建议应该与搜索词相关。
  • 排序：返回的结果必须按一定规则排序，比如受欢迎程度或是其他算法。
  • 可扩展：系统必须能够应对高并发流量。
  • 高可用性：系统必须在部分组件下线，或是网络出现异常时仍然能够可用。

规模预估：

  • 假设每天有1000万活跃用户
  • 平均每个用户一天查询10次
  • 每次查询长度为20个字符：
    • 假设使用ASCII编码，1字符=1字节
    • 假设每次查询包含4个单词，每个单词平均5个字符
  • 每次输入一个字符时，客户端发送一次请求给后端以获取搜索提示。平均下来，一次查询要发送20个请求。
  • QPS: 1000万 * 10 *20  / 24 / 3600 ~=24000
  • 峰值QPS：QPS *2 ~= 48000
  • 假设20%的每日查询是新内容，那么 1000万 * 10 * 20 * 20% = 0.4GB，也就是第天要新增0.4GB新数据。

Step 2 - 概要设计

将系统分成两部分：

  • 数据收集服务：负责收集用户的搜索词，然后进行聚合分析。
  • 查询服务：给定一个关键词前缀，返回5个最常用的搜索词

数据收集服务

简单来说，就是记录每个搜索词被搜索的次数，如下：

查询服务

假设已经有了搜索词的频率表，它包含下面两列：

  • 搜索词
  • 搜索次数

当用户输入"tw"时，将显示以下5个推荐的搜索词。

这5个推荐词的生成可以使用下面的SQL语句：

上面的方式在数据规模较小时比较实用，但当数据规模庞大时，数据库查询会成为系统性能瓶颈。

Step 3 - 详细设计

深入设计并优化以下组件：

  • 前缀树结构
  • 数据收集服务
  • 查询服务
  • 扩展数据存储
  • 前缀树操作

前缀树结构

使用前缀树来处理top k查询问题，它的基本设计如下：

  • 使用树状结构存储
  • 根结点代表空字符串
  • 每个节点存储一个字符，并且拥有26个子节点，每个代表一个可能的字符。
  • 从根结点到每个子节点构成了一个单词或单词前缀

以下是搜索“tree”, “try”, “true”, “toy”, “wish”, “win”之后生成的一棵前缀树：

基本的前缀树只存储字符，为了支持按出现频率排序，需要在每个节点加上出现频率，假设出现频率如下：

加上出现频率后，前缀树如下：

在讨论自动补全之前，先定义一些术语：

  • p：前缀的长度
  • n：前缀树的节点数量
  • c：给定节点的子节点个数

根据给定前缀查询top k个搜索词的过程如下：

  1. 找到给定前缀在前缀树中的出现位置，时间复杂度：O(p)
  2. 遍历给定前缀所在节点的子节点，时间复杂度：O(c)
  3. 对子节点进行排序，获取top k，时间复杂度：O(clogc)

以下面的前缀树作为示例来演示一下前缀树的查找过程，这里假设k=2，用户输入是"be"，则算法的工作流程如下：

  • 步骤1：找到前缀节点"be"。
  • 步骤2：遍历所有子节点，这里是 [beer: 10], [best:35], [bet: 29] 三个节点。
  • 步骤3：对子节点进行排序，获取top 2，这里是 [best: 35]， [bet: 29]两个结点。

以上算法的时间复杂度是：O(p) + O(c) + O(clogc)

上面的算法在最坏情况下可能要遍历整棵前缀树，下面是两项优化措施：

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

限制前缀的最大长度

用户通常不会查询一个很长的单词，所以可以将p设置成一个较小值，比如50。限制长度之后，查询前缀的算法复杂度将近似O(1)。

节点缓存top k查询结果

为了避免每次查询都遍历一次子节点，我们可以在每个节点缓存top k的查询结果。因为一般只需要推荐5~10个搜索建议，所以k不会很大，不会消耗大量内存，这里以k = 5作为示例。

通过在节点上缓存top k查询结果，可以显著降低重复查询的时间，相当于以空间换时间。

以下是一个带top k缓存的前缀树，每个节点都缓存了top 5的查询结果。

在应用以上两项优化措施后，新的算法复杂度将变成：

  1. 查询前缀所在节点：O(1)。
  2. 返回top k：O(1)，因为节点已经缓存了结果。

数据收集服务

在前面的设计中，用户每搜索一次，前缀树就被更新一次，这种设计存在以下两个显著的问题：

  • 每天都有成千上万的用户在搜索，每次搜索都更新数据显然不现实
  • 一段时间内的搜索建议一般不会有很大的改变，因此没必要频繁更新前缀树

以下是重新设计过的数据搜集服务以及各个组件的描述：

分析日志（analytics logs）

存储了原始的搜索数据，随时间增加，未索引化，以下是一个示例。

聚合器（aggregator）

分析日志通常体积巨大，并且未被格式过，因此首先需要对日志进行聚合，以生成适合后续处理的数据。

根据应用场景，可以采用不同的聚合方式，比如对于实时类应用，可以采用间隔较小的聚合器，以生成实时的分析结果。对于实时性不敏感的应用，则可以采用间隔较大的聚合器，比如每周聚合一次。

聚合数据（aggregated data）

以下是一个聚合之后的数据示例，时间一栏按周进行分隔，频率一栏对应出现次数。

工作集群

以异步的方式定期性执行构造前缀树并存储到前缀树数据库的任务。

前缀树缓存

分布式缓存系统，将前缀树缓存到内存以方便快速读取。前缀树缓存每周从数据库中更新一次数据。

前缀树数据库

用于永久存储前缀树，有两个可供参考的选项：

  1. 文档型数据库：前缀树每周构造一次，可以在每次构造时将其序列化并存储到文档型数据库中，比如MongoDB。
  2. 键值数据库：可以将前缀树将下面的逻辑映射成一张哈希表：
    1. 每个前缀映射成哈希表中的一个key
    2. 每个前缀节点的数据可以映射成哈希表中的value

以下是一个使用哈希表存储前缀树的示例：

查询服务

查询流程如下：

  1. 查询请求首先发给负载均衡器。
  2. 负载均衡将请求转发给API服务器。
  3. API服务器从前缀树缓存中获取数据并构造响应
  4. 如果前缀树缓存中不包含当前查询，则从数据库中查询并缓存起来。

另外，查询服务要求轻量迅速，可以使用下列方式进行优化：

  • 使用AJAX请求，避免刷新页面。
  • 浏览器端缓存。在浏览器端缓存查询建议，使用HTTP协议的cache-control字段控制。
  • 数据采样：对于大规模系统而言，记录每次查询可能会占用大量资源，所以可以对查询进行采样，比如每N个查询记录一次。

前缀树操作

前缀树是本系统的核心，以下是一些前缀树的操作（创建，更新，删除）。

创建

工作集群使用聚合之后的数据创建，聚合之后数据来自于分析日志。

更新

有两种更新方式。

选项1：每周更新一次，使用新创建的前缀树替换老的前缀树。

选项2：直接更新前缀树的结点，只适用于小规模系统，在规模较大时速度很慢，因为每更新一个节点，该节点的所有父级以上节点也要同步更新，以下是一个更新示例：

删除

为构建社会主义和协社会，有时需要删除一些不合时宜的搜索词。这里我们在API服务器和前缀树缓存之间加上一层过滤，根据设置不同的过滤规则，可以过滤掉不适合的搜索建议。为了以防万一，被过滤的搜索建议应该直接物理删除。

数据库伸缩设计

用于解决前缀树过于庞大，无法使用单服务器进行保存的问题。

由于本系统只支持英文字母，一种简单的办法就是根据第一个字符进行分片，比如：

  • 如果有两台服务器，那么可以将'a'~'m'的前缀树存放在第一台服务器上，'n'~'z'存储在另一台服务器上。
  • 如果有三台服务器，则分为'a'~'i'，'j'~'r'，以及's'~'z'。

通过这种逻辑，我们可以将可以将前缀树分片到至多26台服务器上，因为只有26个英文字母。如果还需要扩展服务器，则只能将分片扩展到前两个字符，比如以字符'a'开头的服务器可以再进行分片：'aa~ag', 'ah~an', 'ao~au', 'av~az'。

上面的方式带来的问题就是字母并不是平均分布的，比如以'c'开头的单词比以'x'开头的单词多，这会导致分片不均匀。为了减轻数据不均匀的问题，我们可以在上面分片方式的基础上，通过参考历史数据来进行智能分片，比如通过历史数据发现，'s'开头的查询次数和'u', 'v', 'w', 'x', 'y', 'z'加起来的查询次数相当，那么就可以使用两个分片来存储，一个存储's'，另一个存储'u'~'z'。

上面的智能分布可以通过一个分片管理器来处理，这个分片管理器可以返回某个前缀对应的数据库分布。

Step 4 - 总结

以下是一些可供讨论的点。

如何支持非英语的语言？

使用Unicode构造前缀树。

如何应对不同地区的搜索建议不一样的问题？

对不同的地区构造不同的前缀树，并且使用CDN来加速前缀树的读取。

如何为搜索建议提供实时预估？

假如爆发了某个热点事件，那么对应的搜索词会马上被大量搜索。当前系统并不能应对这种情况，因为前缀树是一周构造一次的，而且即使是马上重新构造，也需要大量时间来完成。以下是一些可供参考的方案：

  • 通过分片来减少工作数据量
  • 修改排名规则，将相关搜索词的权重提高。
  • 将输入当成流来对待，不用每次都处理全部数据，处理数据流可以使用Apache Hadoop MapReuce, Apache Spark Streaming, Apache Storm, Apache Kafka等工具。