常见分布式应用系统设计图解(四):输入建议系统

输入建议系统,指的就是 “typeahead”,比如 Google 搜索,输入一个单词的前几个字母,后面最常用的几个搜索词会被联想出来。有时,它也需要具备一定程度的字符拼写错误自动更正能力。

比如上面这张截图,我输入了 “goog”,在输入框的下方列出了最常见的几个以 goog 开头的搜索短语。

  • 这个功能可以说不是搜索系统的核心功能,而且要求响应一定要非常迅速,考虑到无法避免的网络延迟,我们希望服务端的处理越快越好。响应数据不用非常准确,但是延迟响应肯定是一个糟糕的结果。所以我们希望服务端的处理的数据尽量都在内存中,几乎不需要怎么读取磁盘,整个过程也要保持简洁。
  • 用户侧的浏览器方面,有这么几件事情比较重要:缓存之前的提示数据;
    • 数据不一定只从服务端返回,浏览器也有本地的历史查询记录(比如 Cookie),提示列表可以是二者的并集;
    • 用户打开页面或者选中焦点框就要开始建立连接,从而在输入后节省连接建立时间;
    • 用户每输入一个字符,不要马上去询问服务器,而是等 100 毫秒,没有接着敲字符再发起请求;
    • 后发起的请求得到的结果要能覆盖先发起的,无论响应先到达还是后到达。
  • 为了尽量减少延迟,又考虑到一致性要求不高,CDN 是一个很好的选择。新生成的 Trie 树被推送到离用户较近的节点去。
  • 再来看服务端,大致分为三个步骤。
  • 第一个步骤是图中上面一行,用户的搜索数据或搜索日志,被异步系统处理并计数,写入右侧的数据库中,这个数据库可以考虑选用列数据库(比如 HBase),以提高批量处理的效率,主键可以是一个按序的时间段,以便后续处理。不需要统计全部搜索数据——可以是一个采样以降低数据规模,提高效率;也可以设置一个阈值,如果搜索次数低于阈值就忽略。
  • 第二个步骤是图中第二行靠右侧的部分,每隔一定时间,根据统计数据生成 Trie 树,并持久化到版本化的文件中。为什么用 Trie?因为对于输入建议这种需求,基本就是一种 “前缀查询”,经过压缩的 Trie 树查询的效率很高(其实 HashMap 也可以,但是对于 key,也就是输入前缀的空间占用非常浪费)。
  • 第三部分,考虑到树比较巨大,可以分布在若干个节点上,它的更新异步进行,即整棵树构筑完毕以后整体替换,而不是操纵正在被使用的单个节点。
  • 具体哪一些节点来负责树的哪一部分,这是一个策略问题,它由 Routing Manager 来决定,但是目标是尽量让请求均匀地分摊。比如前缀为 a~bc 的去集群 Partial Trie A,前缀为 bd~d 的去集群 Partial Trie B……这部分可以结合 Zookeeper 来实现。
  • 请求到来的时候,先到达 Typeahead Gateway,而具体请求分发的策略要根据 Routing Manager 来定,这个策略不需要每次都现询问,而可以本地缓存,定期更新。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

711 次阅读

Leave a Reply

Your email address will not be published.

back to top