过 Java 自带的线程 Dump 工具我们导出了出问题的堆栈信息。我们可以看到所有的堆栈都指向了一个名为 validateUrl 的方法这样的报错信息在堆栈中一共超过 100 处。通过排查代码我们知道这个方法的主要功能是校验 URL 是否合法。很奇怪一个正则表达式怎么会导致 CPU 利用率居高不下。为了弄清楚复现问题我们将其中的关键代码摘抄出来做了个简单的单元测试。public static void main(String[] args) { String badRegex ^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]).)([A-Za-z0-9-~\\\\/])$; String bugUrl http://www.fapiao.com/dddp-web/pdf/download?request6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf; if (bugUrl.matches(badRegex)) { System.out.println(match!!); } else { System.out.println(no match!!); } }当我们运行上面这个例子的时候通过资源监视器可以看到有一个名为 java 的进程 CPU 利用率直接飙升到了 91.4% 。看到这里我们基本可以推断这个正则表达式就是导致 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 自动机到底是怎么进行匹配的呢我们以下面的字符和表达式来举例说明。textToday is a nice day. regexday要记住一个很重要的点即NFA 是以正则表达式为基准去匹配的。也就是说NFA 自动机会读取正则表达式的一个一个字符然后拿去和目标字符串匹配匹配成功就换正则表达式的下一个字符否则继续和目标字符串的下一个字符比较。或许你们听不太懂没事接下来我们以上面的例子一步步解析。首先拿到正则表达式的第一个匹配符d。于是那去和字符串的字符进行比较字符串的第一个字符是 T不匹配换下一个。第二个是 o也不匹配再换下一个。第三个是 d匹配了那么就读取正则表达式的第二个字符a。读取到正则表达式的第二个匹配符a。那着继续和字符串的第四个字符 a 比较又匹配了。那么接着读取正则表达式的第三个字符y。读取到正则表达式的第三个匹配符y。那着继续和字符串的第五个字符 y 比较又匹配了。尝试读取正则表达式的下一个字符发现没有了那么匹配结束。上面这个匹配过程就是 NFA 自动机的匹配过程但实际上的匹配过程会比这个复杂非常多但其原理是不变的。文章首发于【博客园-陈树义】点击跳转到原文《藏在正则表达式里的陷阱》NFA自动机的回溯了解了 NFA 是如何进行字符串匹配的接下来我们就可以讲讲这篇文章的重点了回溯。为了更好地解释回溯我们同样以下面的例子来讲解。textabbc regexab{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 是http://www.fapiao.com/dzfp-web/pdf/download?request6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf我们把这个正则表达式分为三个部分第一部分校验协议。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。第二部分校验域名。(([A-Za-z0-9-~]).)。第三部分校验参数。([A-Za-z0-9-~\\/])$。我们可以发现正则表达式校验协议http://这部分是没有问题的但是在校验 www.fapiao.com 的时候其使用了xxxx.这种方式去校验。那么其实匹配过程是这样的匹配到 www.匹配到 fapiao.匹配到com/dzfp-web/pdf/download?request6e7JGm38jf.....你会发现因为贪婪匹配的原因所以程序会一直读后面的字符串进行匹配最后发现没有点号于是就一个个字符回溯回去了。这是这个正则表达式存在的第一个问题。另外一个问题是在正则表达式的第三部分我们发现出现问题的 URL 是有下划线_和百分号%的但是对应第三部分的正则表达式里面却没有。这样就会导致前面匹配了一长串的字符之后发现不匹配最后回溯回去。这是这个正则表达式存在的第二个问题。