图片 2

正则表达式回溯-导致CPU偏高

Posted by

最近了解了下有关正则表达式回溯的内容,想想就写下来,方便自己。

前几天线上一个项目监控信息突然报告异常,上到机器上后查看相关资源的使用情况,发现
CPU 利用率将近 100%。通过 Java 自带的线程 Dump
工具,我们导出了出问题的堆栈信息。

正则表达式匹配算法是建立在正则表达式引擎的基础上的,目前有两种引擎:DFA(确定型有穷自动机)和NFA(不确定型有穷自动机)。这两种引擎的区别主要在于被匹配对象不同。

图片 1

DFA是用文本去匹配表达式。而NFA是用表达式去匹配文本。这个了解一下就信了。目前我们用的是NFA自动机。

我们可以看到所有的堆栈都指向了一个名为 validateUrl
的方法,这样的报错信息在堆栈中一共超过 100
处。通过排查代码,我们知道这个方法的主要功能是校验 URL 是否合法。

为什么有时候正则表达式的使用会导致CPU飙升呢?这个与正则表达式的回溯有关。什么就正则表达式的回溯以及为什么会发生回溯呢?请看下面的例子。

很奇怪,一个正则表达式怎么会导致 CPU
利用率居高不下。为了弄清楚复现问题,我们将其中的关键代码摘抄出来,做了个简单的单元测试。

regex=”b{1,3}ac”;

public static void main(String[] args) {

text=”bbac”;

String badRegex =
“^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$”;

表达式在匹配文本的时候是一个一个的去校验。b{1,3}表示最少出现一个b,最多3个b连续出现。这样在我们的文本中出现了连续的两个b,所以文本是符合这条表达式的。但是由于NFA的贪婪特性,也就是会更多的去匹配文本。表达式会用第三个b去和文本中的所处第三位置的a去匹配,结果不符合。这样就结束了吗?并没有,接下来表达式会在已经匹配的三个字符中“吐”出字符a,这就是回溯。然后就从表达式中的a开始逐一匹配剩余文本ac。直到结束。

String bugUrl =
“”;

如果想要解决这种问题,就需要改变表达式的匹配模式。表达式有三种模式:贪婪模式、懒惰模式、独占模式。

if (bugUrl.matches) {

刚刚我们所用到的是贪婪模式,尽可能多的去匹配。

System.out.println(“match!!”);

而懒惰模式,尽可能少的去匹配,但仍会发生回溯。独占模式,尽可能多的去匹配,但不回溯。

} else {

那如何将表达式改为懒惰模式呢:

System.out.println(“no match!!”);

regex=”b{1,3}?ac”;

}

独立模式呢?

}

regex=”b{1,3}+ac”;这种就可以解决回溯的问题。

当我们运行上面这个例子的时候,通过资源监视器可以看到有一个名为 java
的进程 CPU 利用率直接飙升到了 91.4% 。

 

图片 2

 

看到这里,我们基本可以推断,这个正则表达式就是导致 CPU
利用率居高不下的凶手!

这些只是个人的理解,有什么不足之处,还望指出,如果不理解的可以参考:

于是,我们将排错的重点放在了那个正则表达式上:

 

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\/])+$

这个正则表达式看起来没什么问题,可以分为三个部分:

第一部分匹配 http 和 https 协议,第二部分匹配 www.
字符,第三部分匹配许多字符。我看着这个表达式发呆了许久,也没发现没有什么大的问题。

其实这里导致 CPU 使用率高的关键原因就是:Java
正则表达式使用的引擎实现是 NFA
自动机,这种正则表达式引擎在进行字符匹配时会发生回溯(backtracking)。
而一旦发生回溯,那其消耗的时间就会变得很长,有可能是几分钟,也有可能是几个小时,时间长短取决于回溯的次数和复杂度。

看到这里,可能大家还不是很清楚什么是回溯,还有点懵。没关系,我们一点点从正则表达式的原理开始讲起。

正则表达式引擎

正则表达式是一个很方便的匹配符号,但要实现这么复杂,功能如此强大的匹配语法,就必须要有一套算法来实现,而实现这套算法的东西就叫做正则表达式引擎。简单地说,实现正则表达式引擎的有两种方式:DFA
自动机
(Deterministic Final Automata 确定型有穷自动机)和NFA
自动机
(Non deterministic Finite Automaton 不确定型有穷自动机)。

对于这两种自动机,他们有各自的区别,这里并不打算深入将它们的原理。简单地说,DFA
自动机的时间复杂度是线性的,更加稳定,但是功能有限。而 NFA
的时间复杂度比较不稳定,有时候很好,有时候不怎么好,好不好取决于你写的正则表达式。但是胜在
NFA 的功能更加强大,所以包括 Java 、.NET、Perl、Python、Ruby、PHP
等语言都使用了 NFA 去实现其正则表达式。

那 NFA
自动机到底是怎么进行匹配的呢?我们以下面的字符和表达式来举例说明。

text=”Today is a nice day.”

regex=”day”

要记住一个很重要的点,即:NFA
是以正则表达式为基准去匹配的。也就是说,NFA
自动机会读取正则表达式的一个一个字符,然后拿去和目标字符串匹配,匹配成功就换正则表达式的下一个字符,否则继续和目标字符串的下一个字符比较。或许你们听不太懂,没事,接下来我们以上面的例子一步步解析。

首先,拿到正则表达式的第一个匹配符:d。于是那去和字符串的字符进行比较,字符串的第一个字符是
T,不匹配,换下一个。第二个是 o,也不匹配,再换下一个。第三个是
d,匹配了,那么就读取正则表达式的第二个字符:a。

读取到正则表达式的第二个匹配符:a。那着继续和字符串的第四个字符 a
比较,又匹配了。那么接着读取正则表达式的第三个字符:y。

读取到正则表达式的第三个匹配符:y。那着继续和字符串的第五个字符 y
比较,又匹配了。尝试读取正则表达式的下一个字符,发现没有了,那么匹配结束。

上面这个匹配过程就是 NFA
自动机的匹配过程,但实际上的匹配过程会比这个复杂非常多,但其原理是不变的。

NFA自动机的回溯

了解了 NFA
是如何进行字符串匹配的,接下来我们就可以讲讲这篇文章的重点了:回溯。为了更好地解释回溯,我们同样以下面的例子来讲解。

text=”abbc”

regex=”ab{1,3}c”

上面的这个例子的目的比较简单,匹配以 a 开头,以 c 结尾,中间有 1-3 个 b
字符的字符串。NFA 对其解析的过程是这样子的:

首先,读取正则表达式第一个匹配符 a 和 字符串第一个字符 a
比较,匹配了。于是读取正则表达式第二个字符。

读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b
比较,匹配了。但因为 b{1,3} 表示 1-3 个 b 字符串,以及 NFA
自动机的贪婪特性(也就是说要尽可能多地匹配),所以此时并不会再去读取下一个正则表达式的匹配符,而是依旧使用
b{1,3} 和字符串的第三个字符 b 比较,发现还是匹配。于是继续使用 b{1,3}
和字符串的第四个字符 c 比较,发现不匹配了。此时就会发生回溯。

发生回溯是怎么操作呢?发生回溯后,我们已经读取的字符串第四个字符 c
将被吐出去,指针回到第三个字符串的位置。之后,程序读取正则表达式的下一个操作符
c,读取当前指针的下一个字符 c
进行对比,发现匹配。于是读取下一个操作符,但这里已经结束了。

下面我们回过头来看看前面的那个校验 URL 的正则表达式:

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\/])+$

出现问题的 URL 是:

我们把这个正则表达式分为三个部分:

第一部分:校验协议。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。

第二部分:校验域名。(([A-Za-z0-9-~]+).)+。

第三部分:校验参数。([A-Za-z0-9-~\/])+$。

我们可以发现正则表达式校验协议 http:// 这部分是没有问题的,但是在校验
www.fapiao.com 的时候,其使用了 xxxx.
这种方式去校验。那么其实匹配过程是这样的:

相关文章

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注