需要澄清的问题
- 是否是前缀匹配 (是）
- 要返回多少个条目 （5）
- 是按popularity做选择吗 （是）
- 是否要支持多语言 （先不用）
- 是否要支持特殊字符和大小写敏感 （只考虑英文字母）
- 多少DAU （1 billion）
功能性需求
输入，一段想要搜索内容的前缀
输出，返回可能匹配的top 10 suggestion
非功能性需求
10亿用户，平均每人每天搜索5次，平均每次输入10个字符
QPS = 1B * 5 * 10 / 100K = 200K
PEAK QPS 200K * 5 = 1M
性能：
因为打字速度也很快，如果响应时间过长，就会影响用户体验。
比如用户已经输了apple, 你还刚能返回 app的结果，
所以 latency < 100ms
可扩展：
支持水平扩展，应对高峰流量
高可用：
可以容错，当部分服务离线，断网，服务依然可用
high-level 设计
服务应该分为2个部分，在线去接受用户的query请求，离线去计算所有 query的popularity，并且把结果放进cache，供线上服务最快使用。
这样设计的思想是，这个服务是一个读多写少的服务，而且用户对数据的实时性不那么敏感。
- 数据收集服务： 当用户搜索敲下回车后，往日志里添加一条记录。每天定时任务去计算所有搜索词条被搜过的次数，并排序
- 搜索建议服务： client端发送HTTP请求，返回符合前缀的TOP 10热门搜索词条。
如果数据量很小：
select * from frequency_query where query like 'prefix%' order by frequency desc limit 5
上述sql ，可以对query建索引。
进一步优化
第一种优化思路 是我们可以用key/ value store去做存储。那么我们需要做的事情就是在离线，把所有QUERY的前缀集合，都当做KEY，然后把top5 维护好写进 K/V STORE里。
1649681694(1).png
那么当用户在搜索框中输入QUERY 敲击回车，数据收集服务 会更新 query -> cnt 的表。然后每天更新一次数据，构建出 prefix -> top 10的表 供搜索建议服务使用。
在构建prefix -> top 10，可以用分布式计算框架，比如MAP的是时候，就把一个单词拆成多个前缀，到REDUCE那，去筛选TOP10。
这种优化思路的好处是现成的KEY / VALUE 的数据库是比较多的。缺点是比较耗存储。
当然还有另一种优化思路，就是用trie树，优点是节约空间，缺点是没有现成的数据库可以使用。所以需要自己序列化和反序列化。
当然如果把整个数据结构缓存进内存里，那么性能也是足够好的。
1649684125(1).png
我们把上面这颗trie树，大概序列化为“C2,A2,R1,T,P,O1,D”
如果您注意到，我们并没有在每个节点中存储顶级建议及其计数。 我们很难储存这些信息; 由于我们的trie是自上而下存储的，所以在父节点之前没有创建子节点，所以没有简单的方法来存储它们的引用。 对于这个，我们必须重新计算上面所有有计数的项。 这可以在我们构建trie时完成。 每个节点将计算出它的首选建议，并将其传递给它的父节点。 每个父节点将合并其所有子节点的结果，以确定其最优建议。
1649686673(1).png
那么在反序列化的时候，需要做MERGE所有孩子的CNT操作，然后存下TOP5。
每一次MERGE的时间复杂度 大概是（假设有K个孩子）k + 5 * logk
TIRE树如何更新？
离线更新，然后先发布到 secondary的内存中，再做一个主从切换。
如何做一个过滤层？
我们需要删除，暴力的，色情的，或危险的搜索建议内容。 我们在Trie Cache前面添加一个过滤器层来过滤掉 不必要的建议。 有了一个过滤器层，我们可以灵活地删除结果基于不同的过滤规则。 另外需要一个异步任务从数据库中物理地删除不需要的建议以便在下一个更新周期中使用正确的数据集来构建trie。
1649685415(1).png
如何分片
a.基于范围的分区:如果我们根据短语的第一个字母将它们存储在单独的分区中会怎么样? 所以我们把所有以字母A开头的项保存在一个分区中把以字母B开头的项保存在另一个分区中，以此类推。 我们甚至可以把某些不太经常出现的字母组合成一个分区。 我们应该静态地提出这种分区方案，以便始终能够以可预测的方式存储和搜索术语。
这种方法的主要问题是,它可能导致不平衡的服务器,例如,如果我们决定把所有条款从字母“E”成一个分区,但后来我们意识到我们有太多的条件,从字母“E”,我们不能适应一个分区。
我们可以看到，上述问题将发生在每一个静态定义方案。 不可能计算出我们的每个分区是否静态地适合一台服务器。
b.根据服务器的最大容量进行分区:假设我们根据服务器的最大内存容量对trie进行分区。 只要服务器有可用的内存，我们就可以一直将数据存储在服务器上。 每当一个子树不能装入服务器时，我们就在那里分割我们的分区，将这个范围分配给这个服务器，然后转移到下一个服务器，重复这个过程。 假设我们的第一个三服务器可以存储从“A”到“AABC”的所有术语，这意味着我们的下一个服务器将存储从“AABD”开始的术语。 如果我们的第二个服务器可以存储到' BXA '，下一个服务器将从' BXB '启动，以此类推。 我们可以保留一个哈希表来快速访问这个分区方案:
服务器1,A-AABC
服务器2,AABD-BXA
服务器3 BXB-CDA
对于查询，如果用户输入了“A”，我们必须查询服务器1和服务器2，以找到最前面的建议。 当用户输入' AA '时，我们仍然需要查询服务器1和服务器2，但当用户输入' AAA '时，我们只需要查询服务器1。
我们可以在我们的trie服务器前面有一个负载均衡器，它可以存储这个映射并重定向流量。 此外，如果要从多个服务器查询，要么需要在服务器端合并结果来计算总的最优结果，要么让客户端这样做。 如果我们希望在服务器端这样做，我们需要在负载均衡器和trie服务器之间引入另一层服务器(我们称它们为聚合器)。 这些服务器将聚合来自多个trie服务器的结果，并将顶部的结果返回给客户机。
基于最大容量的分区仍然可以将我们引向热点，例如，如果有很多以“cap”开头的术语的查询，那么持有它的服务器将比其他服务器有更高的负载。
c.根据词的哈希进行分区:每个词都会被传递给一个哈希函数，哈希函数会生成一个服务器号，我们会将词存储在该服务器上。 这将使我们的术语分布变得随机，从而最小化热点。 这个方案的缺点是，为了找到一个词的提前输入建议，我们必须询问所有的服务器，然后聚合结果。
客户端优化
-
客户端应该只在用户没有按任何键200ms的情况下尝试敲击服务器。
-
如果用户一直在输入，客户端可以取消正在进行的请求。
-
最初，客户端可以等待用户输入几个字符。
-
客户端可以从服务器预取一些数据，以服务将来的请求。
1649686067(1).png
-
客户可以在本地存储建议的最近历史记录。近期历史有很高的重用率。
-
与服务器建立早期连接是最重要的因素之一。只要用户打开搜索引擎网站，客户端就可以打开与服务器的连接。因此，当用户键入第一个字符时，客户端不会在建立连接上浪费时间。
-
为了提高效率，服务器可以将部分缓存推送给cdn和互联网服务提供商(isp)。
如何解决热门事件
构建另外一个系统，专门处理近2小时的热门搜索，这套系统因数据量小，就实时的在内存里维护2小时的热门数据的trie。
热门词的发现：比较2小时内，CNT明显高于历史的CNT的词条。把这些词条存下来，构建TRIE，来反向匹配用户请求。
随后用户的请求会汇总2个系统的结果，一个是普通的搜索建议，另一个是热门的搜索建议。
follow up
你如何扩展你的设计以支持多种语言?
为了支持其他非英语查询，我们将Unicode字符存储在trie节点中。
如果一个国家的搜索结果与其他国家不同呢?
在这种情况下，我们可以为不同的region建立不同的trie。 改善响应时间，我们可以在cdn中存储尝试。
网友评论