日前，某线上项目监控信息突然报异常。登录机器后查看相关资源的使用情况，发现CPU使用率接近100%。通过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("匹配！！");}else{n(System..."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自动机实现的。这个正则表达式引擎在进行字符匹配时会回溯。一旦发生回溯，消耗的时间就会变得很长，可能是几分钟，也可能是几个小时，时间长短取决于回溯的次数和复杂程度。看到这里，你可能还不是很清楚什么是回溯，还有点迷糊。没关系，让我们从正则表达式的原理开始一点点。正则表达式引擎正则表达式是一种非常方便的匹配符号，但是要实现如此复杂而强大的匹配语法，就需要有一套算法来实现，而实现这种算法的东西就叫做正则表达式引擎。简单来说，正则表达式引擎的实现方式有两种：DFA自动机（DeterministicFinalAutomaton）和NFA自动机（NondeterministicFiniteAutomaton）。对于这两种自动机，它们各有不同，这里不打算深究它们的原理。简单地说，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开头，以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-~\/])+$有问题的网址是：http://www.fapiao。com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf我们将这个正则表达式分为三个部分：第1部分：验证协议。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。第二部分：验证域名。(([A-Za-z0-9-~]+).)+.第三部分：检查参数。([A-Za-z0-9-~\/])+$。我们可以发现，正则表达式验证协议的http://部分没有问题，但是在验证www.fapiao.com时，却使用了xxxx。该方法用于验证。所以其实匹配过程是这样的：匹配到www。匹配发票。读取下面的字符串进行匹配，最后发现没有点，就一个一个往回走。这是这个正则表达式的第一个问题。还有一个问题是，在正则表达式的第三部分，我们发现有问题的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.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!!");}}运行上面的程序，它会打印出match!!立即地。但这还不够。如果以后有其他网址出现乱码，我们又得重新修改。一定不现实！实际上，正则表达式中存在三种模式：贪婪模式、懒惰模式和独占模式。在关于数量的匹配中，有四种+?*{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-~\/])+$tooltip只用了58步就完成了检查。一个性格的差异，性能上的差异就是数万倍。Shuyi表示，一个小小的正则表达式竟然能拖累CPU，真是了不起。这也提醒了我们平时写程序的人。遇到正则表达式，一定要注意贪心模式和回溯问题，否则我们写的每一个表达式都是雷区。通过查阅网上资料，发现深圳阿里中心LAZADA的同学在2017年也遇到过这个问题。他们在测试环境也没有发现什么问题，但是上线的时候，100%出现了CPU问题。他们遇到的问题和我们几乎一模一样。有兴趣的朋友可以点击阅读原文查看他们后来总结的文章：一个由正则表达式引起的血案-明知见智-博客园虽然这篇已经写完了，但是关于NFA自动机的原理，特别是关于的解释lazymode和exclusivemode解释的还不够深入。因为NFA自动机真的不是那么好理解的，所以需要在这方面继续学习加强。欢迎有学识的朋友前来学习，交流，互相促进。
