背景
昨天接触到一个很有意思的问题, 公司测试环境一台机器 CPU 跑到了 400%,导致该机器上的所有服务都挂掉了。
最后查到的原因竟然是正则表达式所引起的,大大出乎意料啊。虽然早就知道正则效率很差,但绝对没有想到会导致整个机器上服务崩溃的情况。
先简单展示下问题正则:
String regex = "(\\w+,?)+";
String val = "abcdefghijklmno,abcdefghijklmno+";
System.out.println(val.matches(regex));
最终的执行时间是 17s 左右。
相反,如果改成 String val = "abcdefghijklmno,abcdefghijklmno"
,实际执行时间 1ms 左右。
哈哈,完全不是一个量级的结果。
最后,当然是要找原因了:< 当然,有其它重要的事在耽搁,没时间去看 Java Regex 源码。不过,从正则本身下手反而是个好事情。毕竟几乎所有的编程语言都有对正则的支持。而同样的,都存在着这样的问题。那就可以大胆猜想其实是和语言本身无关,而在于正则规范本身了。
先给个结果,罪魁祸首就是指数爆炸
追本溯源
这里并不准备一步一步地阐述正则的,如果真的是零基础的话,推荐先看一下 学习正则
就事论事,还是以 regex ::= (\w+,?)+
作为示例来进行说明。
首先需要了解的是 val.matches(regex)
所要进行的工作是判断 val
全串是否符合 regex
正则模式。而正则所要做的工作就是尝试所有的匹配可能性(当然,对于 val
这个串来说,最后匹配到 abcd..,abcd..mno+
的 +
的时候一定是失败的,因为 regex
并不匹配 +
)
简单扩展一下对尝试所有匹配可能性
这句话的描述:
我们以 ()
对应 regex
中的一组 (\w+,?)
,而最后一个 +
表示一个或多个(即允许存在多个()
)
对 val
串的匹配可能性有
(abcdefghijklmno,)(abcdefghijklmno)+
(abcd)(efghijklmno,)(abcdefghijklmno)+
(abcdefghijklmno,)(abcdef)(ghijklmno)+
(abc)(defghijklmno,)(abcde)(fg)(hijklmno)+
…
有相当多的匹配可能,不再一一详述(事实上,光靠个人手工根本列举不完。
那么到底会有多少中匹配可能性呢?
下面我们就来简单计算一下:
首先,我们把 (\w+,?)+
这个正则扩展一下,它与下列这些串都是等价的 (\w+,|\w+)+
, (\w+,)?(\w+)?(\w+,?)+
, (\w+,)?(\w+)?(\w+)?(\w+,?)+
…
也就是说,我们能够至少把 abcdefghijklmno,abcdefghijklmno+
按照匹配串划分出1组,2组,3组…30组(因为每个组至少需要一个\w
)
不过这个按照1组,2组…去计算可能性的话实在是费力不讨好的事情。用组合数学来考虑这个问题
首先,整个 abcdefghijklmno,abcdefghijklmno+
的开始应该有一个左括号 (
,即 (abcdefghijklmno,abcdefghijklmno+
其次,到 ,
为止至少应该有一个右左括号 )(
,即 (abcdefghijklmno,)(abcdefghijklmno+
再次,由于到 o+
为止一定匹配失败,因此,+
之前应该有一个 )
, 即 (abcdefghijklmno,)(abcdefghijklmno)+
至于其他字符间的空隙,除了 o,
之间不能存在右左括号 )(
,其他字符间都可以随意插入 )(
(至于为什么是右左括号,表示前一个组的结束与新的组的开始)
那么总共有多少种可能?
插入零个右左括号
)(
, $C_{28}^0$ = 1 种可行方案插入一个右左括号
)(
, $C_{28}^1$ = 28 种可行方案 (总共 28 个可用字符间隙)插入两个右左括号
)(
, $C_{28}^2$ 种可行方案…
插入28个右左括号
)(
, $C_{28}^{28}$ 种可行方案
累加的结果为 $C_{28}^1 + C_{28}^2 + C_{28}^3 + … + C_{28}^{28} = 2^{28}$
可想而知为什么会花 17s 了吧。毕竟达到了 2500 万以上的计算量级,加上 regex 本身就是偏慢的。
至于为什么把 abcdefghijklmno,abcdefghijklmno+
串的 +
去掉就变快了?理由也很简单,matches(regex)
在正则串与原串匹配上之后就会快速结束,因为结果只需要告知某次匹配成功了即可。而失败的匹配会不断地尝试所有的可能性。
解决方案
至于解决方案,从上面的原因就可以看到,拒绝在贪婪组模式下((...)+
) 的组内多模式匹配可能。即 (a+a+)+
是不能被允许的,而 (a+b+)+
是可靠的。
写得仓促,如有根源性错误,欢迎指正。
参考
Catastrophic Backtracking(灾难性回溯)
__ __
/ _| __ _ _ __ __ _ / _| ___ _ __ __ _
| |_ / _` | '_ \ / _` | |_ / _ \ '_ \ / _` |
| _| (_| | | | | (_| | _| __/ | | | (_| |
|_| \__,_|_| |_|\__, |_| \___|_| |_|\__, |
|___/ |___/