限流组件自己成了瓶颈，把正则匹配换成前缀树后，QPS 直接翻了一倍
上周四晚上十一点半，全链路压测的 Grafana 面板上一片血红。我看着那个 QPS 曲线像心电图骤停一样直直往下掉，心想完蛋，明天又要被拉去开复盘会了。
压测目标是单机 10 万 QPS，结果跑到 6 万就上不去了。日志里没有下游超时，没有连接池耗尽，CPU 倒是飙到了 90% 多。我下意识以为是业务逻辑的问题，结果 pprof 一把抓下来，火焰图差点没把我送走——
限流组件自己的 matchRule 方法，吃掉了 67% 的 CPU 时间。
好家伙，限流组件自己成了瓶颈，这跟消防栓自己着火有什么区别。
根因：正则匹配的隐性成本
我们当时限流组件的规则匹配逻辑大概是这样的：
func (l *Limiter) matchRule(path string) *Rule {
for _, rule := range l.rules {
if rule.regex.MatchString(path) {
return rule
}
}
return nil
}
每个请求进来，都要遍历所有限流规则，然后用正则去匹配请求路径。一开始线上只有七八条规则，这完全不是问题。但随着微服务拆分，限流策略越来越精细化，规则数量从 7 条涨到了 40 多条。
40 多条规则，每条都编译成正则，每个请求都要挨个 MatchString。你算算：6 万 QPS × 40 次正则匹配 = 每秒 240 万次正则运算。正则引擎内部要维护状态机、回溯、字符类匹配，这些操作在热点路径上就是纯纯的 CPU 刺客。
更坑的是，这些正则里大部分都是简单的路径前缀匹配，比如 /api/user/*、/api/order/*，根本用不上正则的完整能力。用大炮打蚊子不说，还把自己震聋了。
方案选型：为什么是前缀树
发现问题的第二天，我拉了个小会讨论替代方案。三个选项摆桌上：
1. 哈希表直接匹配。 把路径当成 key 扔进 map 里，O(1) 查找，快是真快。但限流规则很多是前缀匹配模式，比如 /api/user/* 要覆盖 /api/user/info 和 /api/user/avatar，纯哈希表做不到通配。
2. 把正则提前编译好、复用对象。 我们其实已经这么做了，正则对象是预先 Compile 的，不存在重复编译的问题。瓶颈不在编译，在匹配本身的开销。
3. 前缀树（Trie）。 路径天然就是一段一段用 / 分隔的，把规则按段拆开插进树里，匹配的时候沿着树走就行。前缀匹配、通配符都能支持，而且时间复杂度只跟路径深度有关，跟规则总数解耦。
第三条路明显是最合适的。但说实话，我当时犹豫了一下——这玩意儿写起来会不会很麻烦？后来查了下，一个基本的前缀树实现也就 100 行左右，加上通配符支持不到 200 行，一个下午就能搞完。
实现：一个下午的改造
核心思路很简单：把 URL 路径按 / 切分成段，每一段作为树的一个节点。叶子节点上挂着对应的限流规则。
数据结构长这样：
type TrieNode struct {
children map[string]*TrieNode
rule *Rule // 叶子节点才有值
isWild bool // 通配符节点
}
type TrieMatcher struct {
root *TrieNode
}
插入规则的时候，/api/user/* 会被拆成 ["api", "user", "*"]，前两段正常插入，遇到 * 就把当前节点标记为通配符，然后把规则挂上去。
匹配的时候更有意思。请求路径 /api/user/info 拆成 ["api", "user", "info"]，从根节点开始一层层往下走。走到 user 节点时，先看看它是不是通配符节点，是的话直接返回规则；不是的话继续往 info 走。如果走到某层发现 info 不存在，就回退检查当前层有没有通配符节点——这就实现了前缀匹配。
func (t *TrieMatcher) Match(path string) *Rule {
segments := splitPath(path)
node := t.root
for i, seg := range segments {
// 优先精确匹配
if next, ok := node.children[seg]; ok {
node = next
continue
}
// 检查通配符
if wildNode, ok := node.children["*"]; ok {
return wildNode.rule
}
// 检查多段通配 **
if wildNode, ok := node.children["**"]; ok {
return wildNode.rule
}
return nil
}
// 精确匹配到叶子
if node.rule != nil {
return node.rule
}
// 检查当前节点是否有通配子节点
if wildNode, ok := node.children["*"]; ok {
return wildNode.rule
}
return nil
}
这里有个细节：支持 ** 多段通配。/api/** 能匹配 /api/user/info/detail 这种多级路径。实现也简单，** 节点一旦命中就直接返回规则，不需要继续往下匹配。
写完跑了一下单元测试，40 条规则全部通过。然后我把限流组件的初始化逻辑改了一行：
// 原来
matcher := NewRegexMatcher(rules)
// 现在
matcher := NewTrieMatcher(rules)
接口完全一致，上层代码零改动。
效果：QPS 直接翻倍
改完当晚重新跑压测，同样的 6 台机器，QPS 从 6.2 万直接飙到了 13.5 万，翻了整整一倍多。
CPU 使用率从 90%+ 降到了 50% 左右。再抓了一次 pprof，matchRule 方法的 CPU 占比从 67% 掉到了 4.3%，几乎可以忽略不计了。
P99 延迟也从 45ms 降到了 18ms。不是因为下游变快了，纯粹是之前每个请求都要在限流层排队等正则匹配，现在这个瓶颈消失了。
最让我意外的是内存占用反而降了。40 多个编译好的正则对象占了不少内存，而前缀树只有几百个节点，每个节点存一个 map 和一个指针，总内存从 80MB 左右降到了不到 2MB。
什么时候该用前缀树
事后复盘，我觉得这次改造能见效有两个前提条件：
规则数量够多。 如果只有三五条规则，正则匹配的开销根本感知不到，改不改区别不大。我们是从 7 条涨到 40 多条才暴露问题的。如果你的限流规则数量在 20 条以上，或者规则数量会持续增长，前缀树值得考虑。
规则形态简单。 大部分限流规则就是路径前缀匹配，正则的那些高级特性（捕获组、反向引用、复杂字符类）根本用不上。如果你的规则确实需要复杂的正则语义，那前缀树代替不了，但可以考虑把正则规则和前缀规则分开处理——大部分请求走前缀树快速路径，少数复杂规则走正则。
另外，前缀树的实现有很多变体。我们用的是最朴素的版本，每个节点一个 map[string]*TrieNode。如果对性能有极致追求，可以把 map 换成数组或 radix tree（压缩前缀树），进一步减少内存和提升查找速度。但对我们来说，朴素的实现已经够用了，再优化就是过度设计了。
这次经历给我最大的教训：永远不要相信"这个组件很简单，不会出问题"。 在低 QPS 下没问题的设计，到了高并发场景可能会变成灾难。限流组件本来是保护系统的，结果自己先崩了，这不就是最大的黑色幽默吗。
常见问题
前缀树能完全替代正则吗？
不能，也没必要。前缀树擅长处理路径前缀匹配这种层次化的模式，如果你的限流规则需要匹配 URL 参数、请求头或者复杂的正则表达式（比如 /api/v[0-9]+/user），正则依然是更好的选择。实际做法是混合使用：大部分规则走前缀树，少数复杂规则保留正则，匹配时先查前缀树，查不到再走正则兜底。
前缀树的通配符性能怎么样？
精确匹配最快，O(n)，n 是路径段数。单段通配符 * 也是 O(n)，只是多了一次 map 查找。多段通配符 ** 命中时直接返回，实际上比精确匹配还快。唯一的退化场景是大量通配符规则集中在同一层级，导致 map 变大，但实际场景中这种情况很少见。
如果路径段数特别深怎么办？
URL 路径很少超过 10 段。就算极端情况下有 20 段，前缀树的查找也只是 20 次 map 查找而已，跟正则的状态机回溯比起来完全不是一个量级。如果真的有超深路径，可以考虑用 radix tree 压缩连续的单分支节点，但大部分场景下不需要。
改造需要停服吗？
不需要。限流规则通常是从配置中心动态加载的，你只需要改匹配器的初始化逻辑，然后灰度发布就行。接口不变的情况下，上层代码零改动，风险很低。我们是在常规发布窗口里顺带改掉的，前后花了不到一天。