系统设计 Lab
Search autocomplete 是在紧绷 latency 预算下的只读 top-k prefix 查询，由一条独立的聚合 pipeline 喂养 —— 而不是一条实时写路径。
调节按键查询速率、词表大小、返回多少条建议、p99 latency 预算、completion 要多新鲜，以及 region 数。设计会从单个内存 trie 演进到 cache 最热的 prefix、按 prefix 给 trie 分片、用一条流式 log 聚合 pipeline 保新鲜，再到 per-region 个性化。
分步讲解
一步一步把它想清楚
要点
常规演进场景
从左到右点击，就是预设的演示路径。每张卡片都会改变 workload 输入。
推荐形态
当前架构路径
Client
Client 每次按键发起一次 prefix 查询，并记录被选中的 query
Edge / API
API gateway 把 prefix 查询分发给 trie，并把被选中的 query 转发到 log
Prefix cache 为最常见的 prefix 提供 completion，不碰 trie
Trie service
Trie service 行走 prefix 树，返回匹配节点上存好的 top-k
Trie shard 把 prefix 树拆到多个节点上，让庞大词表既装得下又能扩展
聚合
Aggregator 统计 query 频率，重新算出 top-k 并写回 trie
Stream processor 从实时 log 增量更新计数，让趋势在几分钟内浮现
Query log
Query log 持久记录每个被选中的 query，作为 ranking 的 source of truth
瓶颈
查询 vs latency 预算
Trie 内存
Hot-prefix cache 压力
更新 / 新鲜度滞后
Shard fan-out
为什么会变
决策权衡
有出处支撑的规则
这些是模型背后那些经得起时间考验的 system design 论断。而 slider 的具体阈值，则被刻意标注为教学用的假设。
trie 回答 prefix 查询的耗时与 prefix 长度成正比
trie 以 prefix 的字符为 key，所以一次 completion 查询是 O(prefix 长度)，与存了多少 query 无关 —— 不像扫描整个词表那样。
NIST Dictionary of Algorithms and Data Structuresquery 热度高度倾斜，所以一个小 cache 就能覆盖大多数查询
搜索 query 流服从幂律：一小撮热门 query 占了很大一部分流量，所以 cache 最热的 prefix 就能吸收大多数读。
Baeza-Yates et al., "The Impact of Caching on Search Engines" (SIGIR)在每个节点预计算并存好 top-k，而不是在查询时才 ranking
提前把排好序的 completion 维护好（比如每个 prefix 一个 sorted set），就把一次查询变成读取一份已排序的 top-k，而不是临时聚合。
Redis Docs — autocomplete with sorted sets流式聚合能从一条无界 log 产出低延迟更新
一个有状态的 stream processor 在 query log 上维护滚动聚合，让更新后的 top-k 计数在数秒到数分钟内可用，而不用等一次批量重建。
Apache Flink Documentation教学用假设
- completion 被建模成可缓存的 prefix 查询；cache 覆盖率是从 query 热度倾斜近似出来的，不是实测的命中率。
- 单节点读 throughput 和内存 trie 容量都是保守的教学数字，不是厂商上限。
- 在热路径上 trie 是只读的；新鲜度只来自那条独立的聚合 pipeline，所以搜索 latency 和更新滞后是各自独立的预算。