背景

昨天接触到一个很有意思的问题, 公司测试环境一台机器 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(灾难性回溯)

  __                    __                  
 / _| __ _ _ __   __ _ / _| ___ _ __   __ _ 
| |_ / _` | '_ \ / _` | |_ / _ \ '_ \ / _` |
|  _| (_| | | | | (_| |  _|  __/ | | | (_| |
|_|  \__,_|_| |_|\__, |_|  \___|_| |_|\__, |
                 |___/                |___/