正则性能：回溯陷阱与优化手法

一条看起来人畜无害的正则，可以让服务在几十个输入字符上跑满 CPU 几分钟。这类事故的特征是：输入不长、CPU 打满、没有堆栈增长（不是死循环，是在穷举），而且只在特定格式的字符串上出现。理解引擎的执行模型之后，这类问题是可以提前看出来的。

回溯引擎的执行模型

主流语言（PCRE、Python re、Java Pattern、JavaScript、.NET）的正则引擎都是回溯型 NFA。它的工作方式不是”并行尝试所有可能”，而是深度优先：选定一条路径走到底，走不通就退回最近的分支点，换一条再走。

关键点在于：引擎为了能回溯，需要记住每个量词、每个分支当时”还能怎么换”。这些可选项构成一个搜索空间。当多个量词的作用范围重叠时，同一个字符串能被拆分成指数级多种组合，引擎在最终失败前会把它们全部试一遍。

量词有贪婪与懒惰两种，但两者都回溯——.* 先吃到底再往回吐，.*? 先不吃再往前吃，穷举的路径集合是同一批，只是顺序不同。把 .* 改成 .*? 通常解决不了灾难性回溯，这是常见误解。

下面是一个可复现的例子：

import re, time
p = re.compile(r'^(a+)+$')          # 注意：末尾锚点与输入中的 X 让它必须穷举
s = 'a' * 26 + 'X'
t = time.time(); p.search(s); print(time.time() - t)

a 的个数每加一个，耗时大致翻倍。26 个字符已经足以让等待变得明显，30 个字符通常是秒级到分钟级。这就是 ReDoS 的基本形态：输入长度线性增长，耗时指数增长。

灾难性回溯的形态

经典形态是嵌套量词 + 一个注定失败的后缀：

(a+)+b        (a|aa)+b        (s*w+)*$        ^(.*,)*$

(a+)+ 为什么爆炸：外层 + 要把一段连续的 a 切成若干份，每份交给内层 a+。对 n 个 a，切分方案数是 2^(n-1)。只有当字符串后面加了 b 之外的字符，引擎才会把所有这些方案试完；如果输入以 b 结尾，它往往第一条路径就成了。

这也解释了为什么灾难性回溯总是”在失败的输入上出现”——匹配成功时引擎可以提前收工，失败时它必须证明确实没有路径可行。

如何识别危险模式

判断一条正则是否有指数级风险，看三件事：

量词是否嵌套：(x+)+、(x*)*、(x+)*，以及通过分组间接形成的嵌套 ((w+s?)+)+。
相邻量词的作用范围是否重叠：(a+)(a+)、(s*w+)* 里的 s* 与外层 * 都能匹配空白，同一段字符可以由不同的量词”认领”，组合数就爆了。
是否存在必须失败的分支：交替分支 (a|aa) 加上一个无法匹配的后续条件。

一个实用的自检方法：拿 X 重复 20、22、24、26 次构造输入，测耗时。如果耗时大致翻倍，就找到了问题。这类基准应该进 CI，尤其是那些接受外部输入的正则（用户自定义过滤规则、日志解析规则、WAF 规则）。

优化手法

限定字符类。把宽泛的 . 换成排除型字符类，既减少路径又提高精度。

危险：<tag>.*</tag>            # .* 会跨过多个 tag
安全：<tag>[^<]*</tag>

让它无法重叠。把”两个都能吃同一类字符”的结构改成只有一个能吃。

危险：s*(.*)s*$
安全：s*(.*?)s*$  仍不安全 → 改为 ^s*(S.*?)s*$
更稳：^s*(.*S)?s*$          # 只有一个位置能匹配末尾空白

去掉嵌套量词。绝大多数嵌套都是写错了，语义上并不真的需要。

危险：^([a-z]+)*$
安全：^[a-z]*$
危险：(d+|w+)+
安全：[w]+

用原子组或占有量词锁住已匹配的部分。原子组 (?>...) 和占有量词 *+ ++ ?+ {n,m}+ 的作用是：这一段匹配完之后不再交还字符，直接丢弃回溯状态。

危险：^(a+)+b
安全：^(?>a+)+b      # 或 ^a++b（支持占有量词的引擎）

代价是语义会变：原子组可能拒绝掉原本能匹配的字符串。上例中 (?>a+)+b 仍能在 aaab 上工作，但在需要”内层少吞一个”的场景下会失配。用之前要确认语义等价性。

把不确定的分支改写成确定的。交替分支的顺序和可选性直接影响回溯量。

危险：(a|ab)+c        # a 与 ab 重叠
安全：a(?:b)?a?  →  更直接：(?:ab|a)+c 仍重叠
稳妥：a(?:ba)*bc      # 重写为无重叠形式

拆分。用两三次简单匹配代替一次复杂匹配。例如先按行切分再逐行匹配，比在一条正则里处理整个文件快得多，也更可读。

预检。在正则之前加廉价判断：长度上限、必须包含的字符、前缀检查。这能把绝大多数恶意输入挡在门外。

危险写法	问题	安全写法
`(a+)+b`	嵌套量词，指数分支	`a+b` 或 `[a]+b`
`..=`	两个 `.*` 争抢同一段	`[^=]*=`
`^(sw+)$`	`s*` 与外层重叠	`^w+(s+w+)*$`
`<div>.*</div>`	跨越边界的贪婪匹配	`<div>[^<]*</div>`
`(a\|aa)+`	分支可重叠	`a+`
`^(d+,?)+$`	可选逗号造成多解	`^d+(,d+)*$`

超时保护

优化之外还需要兜底，因为总会有规则来自配置或用户输入。

语言层面的支持差异很大：

运行时	引擎特性	超时手段
Go regexp	RE2，线性时间保证	天然免疫，但无反向引用与前瞻
.NET	回溯型	构造时传 `matchTimeout`
Java	回溯型	无内置，可用独立线程 + 中断，或换 RE2/JNI 实现
Python	回溯型	无内置，可用 `signal.alarm` 或子进程包裹
JavaScript	回溯型	无内置，需 Web Worker + 终止，或限制输入长度

通用做法是加输入长度上限。既然耗时随长度指数增长，把输入限制在一个较小的值（例如几百字符）就能把最坏情况压到可接受范围。对于必须处理长输入的场景，先切段再匹配。

另一条防线是把正则匹配放到独立进程或带超时的工作单元里，超时即失败并记录告警——这至少保证一个坏规则不会拖垮整个服务。

什么时候放弃正则

正则擅长的是”正则语言”：可以被有限状态机识别的模式。以下这些信号出现时，继续堆正则只会越写越糟：

需要匹配嵌套结构。HTML、JSON、带括号的表达式。正则无法可靠地做配对计数（PCRE 的递归扩展能勉强做到，但可读性极差且仍然脆弱）。
需要上下文相关的判断。”这个引号内的逗号不算分隔符”——需要状态，正则没有状态。
一个正则超过两三个屏幕。此时没人能维护它，也不会有人敢改。
规则来自业务且会频繁变化。这类场景应该写成小的解析函数，可测、可调试、可加注释。

替代方案按复杂度递增：先试按分隔符切分 + 简单匹配；不行就写手写状态机（几十行的字符扫描循环，通常比复杂正则更快也更好懂）；结构性强的直接用现成解析器（HTML 用 DOM 解析，日志用结构化格式而非正则抽取）。

选型时可以直接问一句：这个模式能被有限状态机识别吗？答案是否定的，就该换工具。RE2 类引擎不提供反向引用和前瞻，正是因为它坚持线性时间保证——这个取舍本身就说明了正则的能力边界在哪里。