system-design-notesTrie数据库的3种分片策略水平扩展Trie的完整方案【免费下载链接】system-design-notesNotes of the book System Desgin Interview - An Insiders Guide项目地址: https://gitcode.com/GitHub_Trending/sy/system-design-notessystem-design-notes 是基于《System Design Interview》一书整理的开源系统设计笔记项目。本文结合其中的「搜索自动补全」章节讲解 Trie 数据库的 3 种分片策略给出水平扩展前缀树的完整方案帮助新手理解搜索自动补全系统如何扛住数万 QPS。现代搜索框里输入 tw 就能立刻弹出 5 条建议——这是**搜索自动补全系统Typeahead**在工作。但当系统要支撑1000 万 DAU、48,000 峰值 QPS、每天 0.4GB 新增查询数据时Trie 数据库就无法再放在单机上了。本文带你完整走一遍解决方案Trie 如何存储搜索建议 → 每周重建的数据流水线 →3 种分片策略实现水平扩展→ 额外加速技巧。一、Trie前缀树搜索建议的数据结构基石 Trie前缀树是一种树状数据结构按前缀逐字符存储字符串公共前缀只存一次存储非常紧凑。在自动补全场景中每个节点还记录以该节点结尾的单词的热度值frequency。图基于历史查询构建的 Trie 前缀树叶节点如 try: 29、toy: 14、win: 50 记录了出现频率获取 top-k 建议只需 3 步定位前缀节点—— 按用户输入如 tw找到对应节点遍历子树—— 收集该前缀下所有合法候选词排序取 top-k—— 按热度排序返回前 5 个结果图用户输入 tw系统实时返回热度最高的 5 个候选词为避免每次请求都遍历整棵子树每个节点会额外缓存自己子树的 top-k 结果图每个 Trie 节点旁都缓存了该子树的 top-k 建议命中缓存即可直接返回无需再遍历排序二、Trie数据库的构建每周快照流水线 用户每天可能产生数十亿条查询每次查询都实时更新 Trie 显然不现实而且头部热门词变化很慢。因此系统采用异步流水线 每周快照的模式重建 Trie 数据库图Analytics Logs → Aggregators → Workers → Trie DB每周对数据库做一次快照写入 Trie Cache供内存快速读取流水线 4 个环节环节组件职责1Analytics Logs追加式存储原始查询日志不做索引2Aggregators聚合出频率表查询词 → 次数3Workers异步服务器根据频率表重建 Trie4Trie DB Trie Cache持久化存储 分布式内存缓存对外服务聚合阶段产出的频率表示例如下图聚合器产出的频率表是构建 Trie 前缀树的直接输入在存储层Trie 还可以被映射成一张哈希表Key-ValueKey 是前缀Value 是节点数据含 top-k 缓存。这种扁平化正是后面分片扩展的基础图Trie 中每个前缀映射为哈希表的一个 key节点数据映射为 value天然适合按 key 分片三、分片策略一按前缀范围水平分片 ✂️当单台服务器存不下、也扛不住整个 Trie 时第一招是按前缀范围把节点切分到多台服务器例如服务器 A负责a~m开头的子树服务器 B负责n~z开头的子树每台服务器只持有一棵子树。用户输入 tw 时请求直接路由到服务器 B——一次请求只命中一个分片非常适合读多写少的自动补全场景。四、分片策略二前缀内二次细分解决数据倾斜 ⚖️一级分片有个问题流量极度不均。t、w 开头的查询量远多于 q、z热门分片会成为热点。解决办法是在前缀内部继续细分把热点范围拆成更小的子区间例如aa-ag、ah-an每个子区间放到独立服务器上让负载趋于均衡。 本质上是递归的区间划分先按首字母切再按次字母切——和键值存储中哈希桶继续分裂的思路一脉相承。五、分片策略三Shard Map Manager统一路由与负载均衡 ️分片之后还剩一个问题请求到底该发给哪台服务器答案是引入一个中心化的分片映射管理器Shard Map Manager维护前缀区间 → 服务器的路由表图Web 服务器先向 Shard Map Manager 询问该前缀在哪个分片再到对应数据库分片取数据两步请求流程查路由表—— 询问 Shard Map Manager 该前缀属于哪个分片从分片取数—— 请求被转发到目标服务器直接读其内存中缓存的 Trie 节点这相当于在分片集群前加了一层路由/负载均衡层扩容时新增机器、更新路由表即可无需搬迁历史数据新机器上线就能承接新分片的流量。六、Trie分片之外的3个加速技巧 限制前缀长度用户几乎不会输入超过 50 个字符的查询把前缀长度截断到 50可大幅缩小搜索空间AJAX 轻量请求 浏览器缓存热门前缀的结果直接存在浏览器缓存里连网络往返都省掉过滤层拦截不良建议在 Trie Cache 前加一层过滤器把违规词按规则过滤并异步物理删除数据库中的脏数据图Trie Cache 与 API 服务器之间加入 Filter Layer按规则剔除不合适的前缀建议七、总结水平扩展Trie数据库的完整方案 #分片策略解决的问题1前缀范围一级分片a-m/n-z单机存储与承载瓶颈2前缀内二次细分aa-ag/ah-an热点前缀导致的数据倾斜3Shard Map Manager 统一路由分片寻址、负载均衡与弹性扩容再配合每周快照重建流水线与节点级 top-k 缓存这套方案可以让 Trie 数据库从单机平滑扩展到多机集群从容支撑数万 QPS 的搜索自动补全服务。延伸阅读 本章完整笔记13. Search Autocomplete/Readme.md一致性哈希分片第 5 章05. Consistent Hashing/Readme.md键值存储分片设计第 6 章06. Key-Value Store/Readme.md【免费下载链接】system-design-notesNotes of the book System Desgin Interview - An Insiders Guide项目地址: https://gitcode.com/GitHub_Trending/sy/system-design-notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考