草草聊事

一个小小的正则如何把 CPU 拖垮？——正则回溯灾难

2026/06/19
1
0

一个小小的正则如何把 CPU 拖垮？——正则回溯灾难

系列：线上问题实战录 | CPU 飙高类 · 第 4 篇 本文所有命令和输出均来自真实复现环境，可照步骤重现

1. 问题现象

1.1 告警

周三下午 14:23，网关群弹出告警：

告警群消息

CPU 99.7%，接口 p99 从 50ms 飙到 12s，下游开始连锁超时。

1.2 止血

回滚最近一次提交后重启，曲线恢复。

所有人盯着 git log 找那个「只改了一行正则」的提交。

2. 排查过程（完整复现）

2.1 Git 记录——罪魁祸首

回滚后发现，问题出在一小时前上线的路由校验正则：

上线记录

diff 只有一行：从简单的精确匹配改成了 ^([a-z0-9]+)*[0-9]+$，加了一层嵌套量词。

2.2 top——CPU 156%

登上机器，top 确认 Java 进程 PID：

top 命令

load average: 12.45，Java 进程 CPU 156%（双核打满一核半）。

2.3 jstack——147 个线程全卡在正则

$ jstack 28341 | grep -A 20 'http-nio-8080-exec-' | head -120

jstack 线程堆栈

关键信息： - 147 个 RUNNABLE 线程，全部在 java.util.regex.Pattern$Curly.match 和 Pattern$Loop.match 之间来回跳 - 调用栈反复出现 Curly.match0 → Loop.match → GroupHead.match 循环 - 没有锁等待、没有 IO 阻塞——纯 CPU 计算耗尽的

这就是正则回溯的典型特征：线程状态全是 RUNNABLE，但进度就是推不动。

2.4 perf——CPU 热区 67% 在 Matcher::match

$ perf top -p 28341 -b --stdio

perf 分析

perf 报告显示 Matcher::match 占 67.24% CPU，其次 Pattern::Curly::match0 12.56%。没有可疑的 GC 或 IO 开销。

结合 jstack 的循环调用栈，可以断定：正则引擎在大量回溯。

3. 根因分析

3.1 什么是正则回溯

正则引擎使用 NFA（非确定有限自动机）实现匹配。当正则中有量词嵌套时，引擎会尝试所有可能的分支组合，直到匹配成功或穷举所有可能。

我们的正则 ^([a-z0-9]+)*[0-9]+$：

  • ([a-z0-9]+) 匹配一个或多个字母/数字
  • (...)* 外层量词，匹配零次或多次
  • [0-9]+$ 必须以数字结尾

对输入 abcdef（全部是字母，不以数字结尾），引擎的尝试过程：

第 1 层:  "abcdef"  作为一组 → 后面没数字了 → 回溯
第 2 层:  "abcde" + "f"        → "f" 不是数字 → 回溯
第 3 层:  "abcd" + "ef"        → "ef" 不是数字 → 回溯
第 4 层:  "abcd" + "e" + "f"   → ...
...

每增加一个字符，回溯次数翻倍。对于 n 个字符，最坏情况下的回溯路径数 = 2^(n-1)。

输入长度 回溯路径数 理论耗时
10 512 微秒级
20 524,288 毫秒级
30 5.3 亿 百毫秒级
50 5.6 × 10^14 小时级

这就是「灾难性回溯」（Catastrophic Backtracking）。

3.2 V1 与 V2 性能对比

Demo 项目中内置了 benchmark：

$ mvn compile -q && java -cp "target/classes:..." cn.opencao.demo.RegexBenchmark

benchmark 结果

长度 V1（贪婪回溯） V2（独占模式） 差异
5 0.030ms 0.011ms 3x
10 0.018ms 0.005ms 4x
20 0.034ms 0.003ms 13x
30 0.070ms 0.003ms 21x
40 0.147ms 0.003ms 47x
50 0.224ms 0.004ms 64x

V1 的耗时随输入长度指数增长，V2 的耗时基本恒定。

生产上被攻击的输入长达 200+ 字符，每个请求消耗数秒 CPU，147 个线程同时回溯——CPU 直接打满。

4. 修复方案

4.1 独占量词（一行改动）

V1 问题代码：

Pattern.compile("^([a-z0-9]+)*[0-9]+$");
//                       ^^^^
//             贪婪量词 → 发生回溯

V2 修复代码：

Pattern.compile("^([a-z0-9]+)*+[0-9]+$");
//                       ^^^^^
//             占有量词 → 绝不回溯

代码对比

修复后代码

只加了一个 +，将 * 改为 *+（possessive quantifier），效果： - 匹配所有字符后直接锁定，绝不释放 - 匹配失败立即返回 false，不走回溯

4.2 验证

$ curl -s 'http://localhost:18080/check/v2?input=abcdefghijklmnopqrstuvwxyz' | python3 -m json.tool

curl 验证

修复后，无论输入多长，响应时间始终 < 0.01ms。

4.3 补充防御

除了独占量词，还可以：

  1. 预编译 Pattern：避免每次都 Pattern.compile()
  2. 限制输入长度：网关层对参数做 maxLength 校验
  3. 使用非捕获组：(?:) 代替 () 减少内存开销
  4. 减少分支选择：提取公共前缀，如 ab(cd|ef) 代替 (abcd|abef)

5. 避坑建议

  1. 警惕嵌套量词：(a+)+b、(a*)*b、(.+)*c 都是经典陷阱
  2. 优先用独占模式：量词后加 +，*+、++、?+、{n,m}+
  3. 测试边界输入：超长纯字母、特殊字符组合都要覆盖
  4. 工具辅助：regex101.com 可直观观察回溯步数
  5. 上线前审查：正则 review check-list 应包含回溯风险评估

总结

正则回溯是个容易写但难发现的 Bug。它在测试环境表现正常（短输入），上线后遇到恶意或异常输入才引爆。一行正则，一根 CPU 线。

排查要点： - jstack 看到大量线程在 Curly.match / Loop.match 循环 = 回溯 - perf 看到 Matcher::match CPU 占比异常高 = 回溯 - 量词后加 + 改为独占模式 = 修复

附：完整命令清单

进程与线程级 CPU 排查

top -b -n 1 | head -25                              # 查看进程 CPU 排行

线程堆栈分析

jstack 28341 | grep -A 20 'http-nio-8080-exec-' | head -120  # 查看卡在正则的线程堆栈
jstack 28341 | grep -c 'Pattern\\.Curly\\|Pattern\\.Loop\\|Pattern\\.GroupHead'  # 统计卡在正则路径的线程数
jstack 28341 | grep 'java.lang.Thread.State' | sort | uniq -c  # 线程状态统计

CPU 热点与系统分析

perf top -p 28341 -b --stdio 2>/dev/null | head -30  # CPU 热点采样
cat /proc/28341/status | grep -E 'Threads|voluntary'   # 线程数与上下文切换

接口耗时验证

curl -s -o /dev/null -w "timing: %{time_total}s\n" 'http://localhost:18080/check/v1?input=abcdefghijklmnopqrstuvwxyz'  # V1 回溯版 ~12s
curl -s 'http://localhost:18080/check/v1?input=abcdefghij' | python3 -m json.tool  # V1 短输入 (10 字符)
curl -s 'http://localhost:18080/check/v1?input=abcdefghijklmnopqr' | python3 -m json.tool  # V1 中长输入 (18 字符)
curl -s -o /dev/null -w "timing: %{time_total}s\n" 'http://localhost:18080/check/v2?input=abcdefghijklmnopqrstuvwxyz'  # V2 独占模式 0.01s
curl -s 'http://localhost:18080/check/v2?input=abcdefghijklmnopqrstuvwxyz' | python3 -m json.tool  # V2 26 字符
curl -s 'http://localhost:18080/check/v2?input=abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz' | python3 -m json.tool  # V2 52 字符

性能基准测试

curl -s 'http://localhost:18080/benchmark?length=30' | python3 -m json.tool  # V1 vs V2 (长度 30)
curl -s 'http://localhost:18080/benchmark?length=50' | python3 -m json.tool  # V1 vs V2 (长度 50)
mvn compile -q && java -cp "target/classes:..." cn.opencao.demo.RegexBenchmark  # 本地 benchmark

📖 全文带可复现 Demo 和排查截图 🔗 个人博客：https://opencao.cn 📺 公众号：Ai拆代码的曹操 🌟 知识星球：源阅会 (82877104)