1. 背景

现在几乎每人每天都会使用搜索引擎（如 Google, Baidu, Bing）去搜索自己想要的信息，而且为了让用户的体验更好，当我们输入关键字时，搜索栏会出现一连串相关联的当前热门关键词，如 图1.1 所示：

图1.1 Typeahead

这篇文章主要是简单粗略地讲讲个人对这种功能（Typeahead）实现的一些见解，接下来的讨论都是用 Google Suggestion 为例进行的。

2. 场景

从 图1.1 我们可以知道每当我们输入一个单词，Google 都会发送一个 search 请求去请求跟输入相关联的推荐词。

• DAU (Daily Active User) : 10亿（1B）
• Search 接口调用 : 1B 4 100 ~~ 400B
• QPS : 400B / 86400 ~~ 4.6M
• Peak QPS : QPS * 2 ~~ 9.2M

3. 服务（Service）

每当我们在 Google 搜索页面输入关键字，我们都会得到一些基于我们输入的关键字的当前热门关键词，这有点像我之前的一篇文章讲的 Top K 问题，有兴趣的同事可以看看这篇文章。即是我们根据输入的关键字，查找以我们输入的关键字为 prefix 的关键词，从中再寻找 top k 热门的关键词。

其中我们主要需要两个 Service：

• Query Service (用来查询 prefix top k 问题)
• Data Collection Service (用来存储当前各种热门关键字)

这两个主要的 Service 的工作流程如图 3.1 所示：

图3.1 工作流程

4. 存储（Storage）

我们现在知道要实现 Typeahead 最主要的两个服务是 Query Service 和 Data Collection Service，其中影响 Query Service 最主要的就是数据的存储了。

4.1 直接存储热门词的频数

那么数据应该如何存储呢？最直接的方法就是存下每个热门词及其对应被搜索的次数，table 如下:

hot_keywords

如果我们输入 abc 那么我们可以直接根据 prefix 搜索数据库，搜索语句如下：

select * from hot_keywords where keyword like ‘${key}%’ order by hit_count desc limit 10;

看来这样是可以搜索出我们需要的结果，但这样做会有什么问题吗?

这个方法的缺点就是慢，为什么会慢呢？

因为我们使用的是范围查找，like 操作是非常耗时的。上面的搜索语句中的

where keyword like ‘abc%’

等同于

where keyword >= ‘abc’ and keyword < ‘abd’;

4.2 空间换时间

既然范围搜索非常的慢，那我们就可以从空间换时间这一方向着手优化。接着我们再使用一张表，如下

prefix_keywords

那用我们直接搜 prefix 就可以得到我们要的结果了，非常暴力且高效。

那么问题又来了，我们怎么从 hot_keywords 这张表 得到 prefix_keywords 这张表呢? 方法有很多，我这里提供一种粗略的方法。

从 hot_keywords 这张表的每个 keyword 逐一添加 prefix，把 prefix 添加到 prefix_keywords 这张表里面，当某个 prefix 对应的 keywords 超过 10 个时，遍历这 10 个 keywords，找到其 hit_count 最小的 keyword 和当前计算的 keyword 的 hit_count 进行对比，如果当前计算的 keyword 的 hit_count 比较大，则替换当前 hit_count 最小的 keyword，否则不做任何操作。

虽然这么做非常高效，但是这个表实在太大了，当然也浪费钱，也不好维护，毕竟热门词每隔一段时间就会变化。那我们能不能使用一个又高效又不怎么占用磁盘空间的方法去做这个事情呢？接下来我们就来看看 Trie。

4.3 Trie

Trie ( Prefix Tree ) 是一种哈希树的变种，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。

关于 Trie 的介绍，可以先看看这篇文章，因为接下来的描述都是基于 Trie 来展开的。

4.3.1 keyword -> hit_count

Trie 记录每个keyword，Trie 里面每一个 node 代表一个字母，以及在每个 keyword 的最后一个字母记录这个 keyword 对应的 hit_count，如图4.1所示：

图4.1 Trie ( keyword -> hit_count )

这样每当我们输入一个关键字，就以这个关键字为 prefix，在 Trie 上搜索出以这个关键字为 prefix 的所有的 keywords 及其对应的 hit_count。这样我们就可以从中找出最热门的词作为推荐，我们就回到 top k 问题的求解了。

这样设计虽然非常直接，但有个问题，就是速度非常慢，为什么呢？

假如我们一开始输入 a，这样我们遍历 Trie 的时候就会去找到所有prefix 为 a 的 keywords，然后再一一对比它们的 hit_count，取其中最大的前十个，随着热门词越来越多，Trie 也会变得越来越大，这样搜索起来就非常慢了。

关于计算提速，最常见的方法就是空间换时间，通过增大空间来减少搜索的时间。接下来我们来看看如何优化 Trie。

4.3.2 prefix -> hot keywords

4.3.1 里面介绍的 Trie 里面每个 node 记录一个字母，并且在每个 keyword 的最后一个字母存下其对应的 hit_count。现在 Trie 里面的每个 node 依旧是存储一个字母，但是我们现在不在每个 keyword 的最后一个字母存下其 hit_count，相对应的我们在每个 node 上面存下以此为 prefix 的前十个热门词。这样我们直接以输入的关键字作为 prefix 在 Trie 上找到其最后一个字母所在的 node，在此 node 上可以直接得到其前十个热门词，如图4.2所示：

图4.2 Trie ( prefix -> hot keywords )

那么问题来了，我们怎么更新这个热门词呢?

就像之前说的那样，如果某个 prefix 的最后一个字母所在的 node 存下的热门词超过 10 个，我们找到其中 hit_count 最小的 keyword，和当前 keyword 的 hit_count 对比，如果当前 keyword 的 hit_count 比较大，则替换成当前的 keyword，否则不做任何操作。

4.4 保存数据

从上面的描述我们可以知道 Trie 肯定是保存在内存里面的，但是有个问题呀，就是万一断电或机器 down 掉，内存里面的数据就消失了，那么就要考虑如何保存数据了。

我们可以把内存的数据（即 Trie）进行序列化和持久化（即 serialize / deserialize）。在磁盘上保存序列化的 Trie 数据，这样就不怕内存的数据丢失了。万一内存的数据丢失了，我们可以直接从磁盘上把序列化的数据反序列一下就可以重新得到我们要的 Trie。

4.5 原始数据

现在我们来回归到最初，我们这些热门词都是怎么得到的？

当然这些热门词会随着时间的变化而变化，但是热门词都是从用户数据里面得到的。每当我们在搜索栏输入一个词，都会有一个表去记录下这个词，如下：

log_data

从 log_data 这个表按时间范围进行分组整合就可以得到 hot_keywords 这个表了，如下：

hot_keywords

5. Scale

5.1 海量热门词

我们知道热门词会不断增加，万一热门词太多，我们的内存装不下那么多数据，那该怎么办呢？一台机器干不了，那就多台机器来操作呗，如图5.1所示：

图5.1 分布式处理

5.2 首字母

我们想到，可以用热门词首字母进行划分不同的机器，即是不同的热门词根据首字母的不同会分配到不同的机器上，这样就可以把数据给分散到不同的机器上了。

但这样做有一个 bias 问题，就是某些以 a 开头的热门词比较多，那么那台机器的负载量就非常的重；某些以 b 开头的热门词比较少，那么那台机器就会非常空闲。

所以这么划分是不合理的，毕竟我们要讲究负载均衡嘛。

5.3 Consistent Hashing

最直接的方法就是使用一致性哈希对热门词进行划分到不同的机器上，如图5.2所示：

图5.2 一致性哈希处理

5.4 海量 log data

随着用户越来越多，log 数据会以急速增长，那我们如果要对 log 数据进行整合处理，那是非常的耗时的。那么我们使用 Probabilistic Logging，也可以说是采样率，即是在用户每次搜关键词时，不用每次都把该数据记录下来，可以以一定的概率去存储这个关键词。

5.5 前端缓存

很多时候，搜索系统需要快速的把一些推荐词给展示出来，我们可以看到每当我们往搜索栏输入一个字母 Google 都会发送一个请求。比如我们输入 appl，那么 Google 会发送四次请求，如下：

那其实我们可以每当用户输入一个新的字母时，在浏览器端加上缓存，缓存下之前的搜索结果，这样下次我们搜索相同的关键词时，就不用向服务器发送请求，直接从浏览器缓存里把之前的推荐词数据拿出来（当然，缓存数据的读写都会有一个数据解密和加密的过程）。比如我们刚输入 appl，然后接着删除 l 和 p ，可以看到 Google 并没有继续发请求，如下：

6. 最后

整篇文章粗略简单地讨论了 Typeahead 的一些设计思考，如果大家有不懂的地方，比如什么是 Trie，如何实现 Trie，什么是 Consistent Hashing，如何实现序列化和反序列化 Trie 等等，或者有不认同的地方，或者有感兴趣的其它话题，都可以在评论区 @ 我 一下，我找个时间再写一些大家感兴趣的文章。

最后谢谢大家的浏览，希望大家喜欢。

晚安，

我是小黎同学，温润依旧。