typeahead

typeahead

1.查询qps，索引容量

2.离线数据流如何建设

2.1LogData数据量太大，可以降频

2.2DataCollection提取LogData计算高频词汇，例如今天天气，10M

2.3数据如何分片，

    2.3.1采用consistency hash

    2.3.2range方式，需要有服务采取一些策略调度数据，避免某些服务负载

2.4数据如何推送到线上：

    2.4.1可以离线pipeline方式，推送到线上，每台机器内存double buffer trie，单个shard需要需有      三副本

    2.4.2数据是全量更新，还是增量更新

    2.4.3 如何不存在Pipeline的支持，可以单个shard使用Raft协议进行复制，Leader节点后台线程     读取磁盘文件，有数据更新apply对应的(K,V)，Leader append entries到follower节点，follower      节点WAL (K,V)，超过n/2+1个节点WAL，Leader on_apply到后台buffer，置换double buffer节        点

    2.4.4服务启动，机器节点故障，内存数据会丢失。数据需要定时snapshot，将内存trie                serialization 到磁盘

3.在线系统如何搭建

3.1内存trie，每个trie node都存储top个数个单词，避免每次查询的时候O(26^n)，high latency

3.2优化可以在客户端

    3.2.1client可以pre-fetch预取一些结果，等到user下一个输入，只需在client端做一些match

    3.2.2client可以缓存history历史查询结果，使用LRU方法剔除历史记录

4.算法解析

231 · 自动补全_INGNIGHT的专栏-CSDN博客

剑指 Offer 37. 序列化二叉树