我们通过Java自带的threaddump工具导出了问题的堆栈信息。我们可以看到所有的栈都指向了一个叫validateUrl的方法，栈中有100多条这样的错误信息。通过查看代码我们知道该方法的主要作用是验证URL是否合法。奇怪的是正则表达式会导致高CPU使用率。为了搞清楚复现问题，我们提取了关键代码，做了简单的单元测试。publicstaticvoidmain(String[]args){StringbadRegex="^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\\/])+$";StringbugUrl="http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";if(bugUrl.matches(badRegex)){System.out.println("匹配.!");out.else{System.out.println("匹配！！");println("nomatch!!");}}当我们运行上面的例子时，通过资源监视器，我们可以看到名为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自动机，这个正则表达式引擎在进行字符匹配时会回溯。一旦发生回溯，消耗的时间就会变得很长，可能是几分钟，也可能是几个小时，时间长短取决于回溯的次数和复杂程度。看到这里，你可能还不是很清楚什么是回溯，还有点迷糊。没关系，让我们从正则表达式的原理开始一点点。正则表达式引擎正则表达式是一种非常方便的匹配符号，但是要实现如此复杂而强大的匹配语法，就需要有一套算法来实现，而实现这种算法的东西就叫做正则表达式引擎。简而言之，有两种方法可以实现正则表达式引擎：DFAAutomata。(DeterministicFinalAutomataDeterministicfiniteautomaton)NFA自动机。(NonDeterministicFiniteAutomatonUncertainfiniteautomaton)对于这两种自动机，它们有各自的区别，这里不去深究它们的原理。简单地说，DFA自动机在时间复杂度上是线性的，更稳定，但功能有限。NFA的时间复杂度比较不稳定，有时候很好，有时候不太好，好不好看你写的正则表达式。但优点是NFA更强大，所以包括Java、.NET、Perl、Python、Ruby、PHP等语言都使用NFA来实现它们的正则表达式。NFA自动机如何匹配？让我们以下面的字符和表达式为例：text="Todayisaniceday."regex="day"重要的是要记住NFA是基于正则表达式来匹配的基础。也就是说，NFA自动机将正则表达式的字符一个一个地读取出来，然后用它们来匹配目标字符串。如果匹配成功，则替换正则表达式的下一个字符，否则继续与目标字符串的下一个字符进行比较。可能你不明白，没关系，我们结合上面的例子一步一步来分析：首先，得到正则表达式的第一个匹配字符：d。所以与字符串的字符进行比较，字符串的第一个字符为T，不匹配则替换。第二个是o，也不匹配，所以换一个。第三个是d，如果匹配，则读取正则表达式的第二个字符：a。读取正则表达式的第二个匹配项：然后继续和字符串的第四个字符a比较，再次匹配。然后读取正则表达式的第三个字符：y。读取正则表达式的第三个匹配项：y。然后继续和字符串的第五个字符y比较，再次匹配。尝试读取正则表达式的下一个字符，发现没有了，则匹配结束。上面的匹配过程就是NFA自动机的匹配过程，但是实际的匹配过程会比这个复杂很多，但是原理是一样的。NFA自动机的回溯了解了NFA是如何进行字符串匹配的，接下来我们就可以说说本文的重点：回溯。为了更好的解释回溯，我们还用下面的例子来解释：text="abbc"regex="ab{1,3}c"上面例子的目的比较简单，匹配以a开头，以a结尾c、中间A串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-~\\/])+$有问题的网址是：http://www.fapiao...[tT]{2}[pP][sS]://)验证域名：(([A-Za-z0-9-~]+).)+学校验证参数：([A-Za-z0-9-~\\/])+$我们可以发现正则表达式验证协议http://没有问题，但是对于www.fapiao.com使用xxxx时是有效的。这边走。那么匹配过程是这样的：匹配到www。匹配发票。匹配到com/dzfp-web/pdf/download?request=6e7JGm38jf...，你会发现因为贪心匹配，程序会一直读取下面的字符串匹配，***发现没有点，所以它一个一个地返回。这是这个正则表达式的第一个问题；另一个问题是在正则表达式的第三部分。我们发现有问题的URL有下划线（_）和百分号（%），而第三部分对应的正则表达式却没有。这样会导致之前要匹配一长串字符，如果有不匹配，***就往回走。这是这个正则表达式的第二个问题。解决方案了解到回溯是问题的原因后，其实就是为了减少这个回溯。你会发现，如果我在第三部分加上下划线和百分号，程序就正常了。publicstaticvoidmain(String[]args){StringbadRegex="^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~_%\\\\/])+$";StringbugUrl="http://www.发票.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";if(bugUrl.matches(badRegex)){System.out.println("match!!");{System.}elout.println("nomatch!!");}}运行上面的程序，马上会打印出match!!，但这还不够，如果以后有其他的url包含乱码，我们就会有再修改一下，肯定不现实！其实正则表达式有三种模式：贪心模式，懒惰模式，独占模式。在数量匹配上，有四种+?*{min,max}两次，如果只单独使用，那么就是贪心模式，如果在它们后面加一个?符号，原来的贪心模式就会变成惰性模式，即尽可能少的匹配。但是惰性模式还是会回溯。TODO比如下面这个例子：text="abbc"regex="ab{1,3}?c"正则表达式的第一个运算符a匹配字符串的第一个字符a，匹配成功。那么第二个运算符b{1,3}呢？正则表达式的匹配到字符串的第二个字符b，匹配成功。由于最小匹配原则，使用正则表达式的第三个运算符c来匹配字符串的第三个字符b，没有匹配到。那么回去匹配第二个运算符b{1,3}呢？正则表达式与字符串的第三个字符b，匹配成功。然后取正则表达式的第三个运算符c去匹配字符串的第四个字符c，匹配成功。所以结束了。如果在他们后面加上+号，原来的贪心模式就会变成排他模式，即尽量匹配，但不要回溯。所以，要想彻底解决问题，就必须在保证功能的同时保证不发生回溯。我在正则表达式的第二部分后面加了一个+号来验证上面的URL，变成这样：^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)++--->>>（这里加了一个+号）([A-Za-z0-9-~\\/])+$这样以后运行原程序就没有问题了。***推荐一个网站，这个网站可以检查你写的正则表达式匹配到对应的字符串会不会有问题。在线正则表达式测试器和调试器：PHP、PCRE、Python、Golang和JavaScript例如，本文中出现问题的URL在使用本网站检查后会提示：灾难性回溯（catastrophicbackgracking）。当你点击左下角的“regexdebugger”时，它会告诉你检查了多少步，并会列出所有的步骤并指出发生回溯的位置。本文中的正则表达式在尝试110,000次后自动停止。这说明这个正则表达式确实有问题，需要改进。但是当我使用修改后的正则表达式进行测试时，它是以下正则表达式：^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$工具提示只需要58步完成检测，如下图所示：一个字符的差异，性能上的差异是几万倍。综上所述，一个小小的正则表达式就能拖垮CPU，这已经很了不起了。这也提醒了我们平时写程序的人。遇到正则表达式，一定要注意贪心模式和回溯问题，否则我们写的每一个表达式都是雷区。通过查阅网上资料，我发现深圳阿里中心LAZADA的同学在2017年也遇到过这个问题，他们在测试环境中也没有发现任何问题，但是上线的时候出现了100%的CPU问题。他们遇到的问题和我们几乎一模一样。这篇文章虽然写完了，但是NFA自动机的原理，尤其是惰性模式和独占模式的讲解，还是讲解的不够深入。因为NFA自动机真的不是那么好理解的，所以需要在这方面继续学习加强。欢迎有学识的朋友前来学习，交流，互相促进。作者：陈淑仪来源：转载自“陈淑仪”微信公众号，一个贴心的技术公众号，立志用最简单的语言，让复杂的技术不再难懂。目前专注于Java领域的技术分享，包括但不限于Java源码、SSM、ElasticSearch、JVM、MySQL、MyCat等技术领域。关注数一君，让你的技术成长不再难。
