常见分布式应用系统设计图解（四）：输入提示系统
source link: https://www.raychase.net/6299
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
输入提示系统，指的就是 “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 来定，这个策略不需要每次都现询问，而可以本地缓存，定期更新。
Recommend
-
37
“ Top K 系统 ” 是非常常见的一种子系统，基本上，就是从全量巨大的统计数据中，筛选出数值最大的 K 个来并按序展示。这样的筛选可以是全时间内的，也可以是最近某一段时间内的；可以是全分类的，也可以是某个特定分类的。 具体...
-
12
常见分布式应用系统设计图解（十）：电商秒杀系统 这篇是关于电商平台秒杀系统的。 首先，我觉得 “秒杀” 是一个中国色彩浓重的词，这样的概念在西方电商系统中也有，但只有在中国，本来业务量就已经如此之巨大了，还将其如此发扬开来。...
-
17
常见分布式应用系统设计图解（五）：Proximity 系统 今天是介绍 Proximity 系统，我不知道怎么翻译恰当，就保留英文原文。虽说词义上说的只是 “相似度”，但多数说的是 “地理” 上的相似度。因此，这一类系统多为基于地理上的邻近程度来提...
-
14
常见分布式应用系统设计图解（四）：输入建议系统 输入建议系统，指的就是 “typeahead”，比如 Google 搜索，输入一个单词的前几个字母，后面最常用的几个搜索词会被联想出来。有时，它也需要具备一定程度的字符拼写错误自动更正能力。
-
18
常见分布式应用系统设计图解（二）：Feed 流系统 今天记录 Feed 流系统的设计学习笔记，Feed 流常见系统包括 Twitter、微博、Instagram 和抖音等等，它们的特点是，每个用户都是内容创作者，每个用户也都是内容消费者，每个用户看到的内容都是不...
-
8
常见分布式应用系统设计图解（一）：即时消息系统 在自己学习各种各样软件系统，特别是分布式系统的过程中，我做了一些笔记，有许多常见的、经典的系统，是非常值得学习和总结的。它们数量不算多，但具有典型意义，可能这样的系统也就十几个。
-
10
这篇讲的是证券交易系统，这类系统包含的内容很多，但是我们还是把目光放在核心的交易部分，比如说股票交易。在某个可交易时间，如果卖家 A 要以至少 y 的价格卖掉股票 x，卖家 B 愿以至多 y 的价格买入股票 x，那么这个交易就可以发生。
-
10
短网址系统可能是最常见的分布式系统设计问题之一了，本身从业务需求上说，读远多过写，而且数据结构确定且简单，数据量小，还易于使用缓存，因此本身难度在分布式系统的问题里面算是比较低的。另外，这个系统本身 “分布式” 的特性也比较...
-
9
常见分布式应用系统设计图解（十四）：日志系统 典型的互联网应用的日志系统，从功能需求上看主要包括收集，存储和分析，以及展示这样三个部分，因此整个系统我觉得也可以按此思路大致可以分为三个部分： ...
-
9
常见分布式应用系统设计图解（十五）：支付系统 支付（Payment）系统可以很复杂，比如可以和银行打交道，和信用卡系统打交道。如果我们考虑用户在一家电商买东西，...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK