)\nline = '9' * 30 + 'x'\nprint(pattern.match(line))\n```\n\n看上去人畜无害:开头结尾都是数字,中间 30 个 9 加一个 x。可这条正则在 Python 的 re 引擎里会卡得怀疑人生,因为 (\\d+)* 是个典型的嵌套量词陷阱。\n\n解释一下为什么慢。正则引擎匹配到末尾的 x 时发现对不上,就开始回溯,尝试 (\\d+) 每次多吞一个少吞一个的各种组合,把前面 30 个 9 的切分方式全试一遍,组合数是指数级的。30 个字符还算能忍,换成一整行日志几百上千个字符,直接卡到脚本超时。这个现象有个专门名字叫 catastrophic backtracking,灾难性回溯。\n\n网上经典的最小复现是 (a+)+b 去匹配一长串 a 结尾加个不是 b 的字符,效果一样,越长的输入越爆炸。特征是:输入越长,耗时不是线性涨而是指数涨,短文本没事、长文本卡死,特别迷惑人。\n\n定位到是正则的锅之后,修法分几层。第一层是看能不能把嵌套量词消掉。上面那个 ^(\\d+)*$ 的语义其实等价于\"整串都是数字\",直接写成:\n\n```python\nimport re\npattern = re.compile(r'^\\d+
)\n```\n\n一条量词,引擎线性扫描完事。我那个线上脚本里的正则也是把\"整段都是某类字符\"的意思写复杂了,摊平之后立刻不卡。很多灾难性回溯的正则,去掉一层嵌套量词就痊愈,先试这步。\n\n第二层是换支持原子组或占有量词的引擎。Python 自带的 re 不支持原子组,但第三方 regex 模块支持,语法是 (?>) 和 *+ 这种占有量词:\n\n```python\nimport regex\npattern = regex.compile(r'^(\\d+)*+
) # *+ 表示匹配了就吐回去\n```\n\n占有量词的意思是匹配到的字符绝不回溯,让引擎没有指数级的分支可试。如果必须保留嵌套结构,用 regex 模块把关键量词改成占有的,通常能压住。PCRE 系(PHP 的 preg、grep -P)也支持 (?>) 原子组,遇到同样问题可以加。\n\n第三层是给匹配加超时保护,别让一条正则把整个任务拖死。Python 的 re 没有内置超时,常见做法是把匹配丢到子进程或者线程里跑,超时就杀掉。第三方 regex 模块有 timeout 参数,直接能设:\n\n```python\nimport regex\ntry:\n regex.match(r'(\\d+)*
, '9'*1000 + 'x', timeout=1)\nexcept regex.TimeoutError:\n print(\"正则超时,匹配被打断\")\n```\n\ntimeout 单位是秒,超时抛 TimeoutError,比整个进程卡死强太多。\n\n还有一个思路是换引擎。RE2 那类基于自动机的引擎没有回溯,最坏也是线性时间,代价是不支持反向引用这类高级特性。Google 的 RE2、Rust 的 regex crate 都是这个路线。日志匹配这种场景如果正则不涉及反向引用,换 RE2 系的库一劳永逸。Python 里可以用 re2 绑定,或者用 grep 的 RE2 实现。我自己现在处理用户输入的正则时,默认不信任,先拿个长输入做冒烟测试,几毫秒内跑不完就说明有风险。\n\n想量化一条正则危不危险,拿不同长度的输入实测最直接:\n\n```python\nimport re, time\nfor n in (10, 20, 30):\n s = '9' * n + 'x'\n t = time.time()\n re.match(r'^(\\d+)*
, s)\n print(n, round(time.time() - t, 4))\n```\n\n耗时从 10 到 20 到 30 如果翻着倍涨,基本就是指数级回溯。除了嵌套量词,(a|a)+ 这种互相重叠的分支同样是雷区,引擎要为每个选择点保存现场,分支和量词一叠加照样爆炸。还有把捕获组和 `正则一匹配就卡死 CPU 飙满,八成是灾难性回溯 - notebase.cn 结尾锚点凑在一起的长链,也容易触发同样的病。排查时先在脑子里把正则拆成\"量词套量词\"\"重叠分支\"两种模式去套,命中任何一种就先怀疑回溯。\n\n想在命令行里快速验证一条会不会炸,grep -P 用的是 PCRE 引擎,支持占有量词,比如 `grep -P '^\\d++
file`,`++` 表示数字匹配上了就绝不吐回去,等价于给这段上了保险,输入再长也是线性扫描,不会卡死。\n\n排查这类问题的固定动作我也想清楚了:先看 CPU 是不是单核打满、任务卡在哪个函数,确认是 re.match 这类匹配调用后,把输入截断成 10 个字符、20 个字符、40 个字符分别计时,耗时翻着倍涨基本就是指数级回溯;然后把正则在脑子里拆层,看有没有 (xx+)* 这种嵌套量词,有就摊平或者换占有量词。到现在我对不同引擎的回溯细节也没全背下来,但记住一条就够了:别写能互相嵌套的量词,匹配长文本前先小样测试。","is_owner":false,"date":"2026/9/2","category":"编程开发"}