前几天，某项目线上监控信息突然报异常。上机后查看相关资源的使用情况，发现CPU使用率接近***Java自带的threadsDump工具，我们导出了有问题的堆栈信息。我们可以看到所有的栈都指向了一个叫validateUrl的方法，栈中有100多条这样的错误信息。通过查看代码我们知道该方法的主要作用是验证URL是否合法。奇怪的是正则表达式会导致高CPU使用率。为了搞清楚复现问题，我们提取了关键代码，做了简单的单元测试。当我们运行上面的例子时，通过资源监视器可以看到一个名为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自动机将正则表达式的字符一个一个地读取出来，然后用它们来匹配目标字符串。如果匹配成功，则替换正则表达式的下一个字符，否则继续与目标字符串的下一个字符进行比较。可能大家不是很理解，没关系，我们结合上面的例子一步一步来分析。1首先，获取正则表达式的第一个匹配项：d。那么再和字符串的字符进行比较，字符串的第一个字符是T，如果不匹配，则替换为下一个。第二个是o，也不匹配，所以换一个。第三个是d，如果匹配，则读取正则表达式的第二个字符：a。2读取正则表达式的第二个匹配字符：a。然后继续和字符串的第四个字符a比较，再次匹配。然后读取正则表达式的第三个字符：y。3读取正则表达式的第三个匹配字符：y。然后继续和字符串的第五个字符y比较，再次匹配。尝试读取正则表达式的下一个字符，发现没有了，则匹配结束。上面的匹配过程就是NFA自动机的匹配过程，但是实际的匹配过程会比这个复杂很多，但是原理是一样的。NFA自动机的回溯了解了NFA是如何进行字符串匹配的，接下来我们就可以说说本文的重点：回溯。为了更好的说明回溯，我们还用下面的例子来说明。text="abbc"regex="ab{1,3}c"上面这个例子的目的比较简单，匹配一个以a开头，以c结尾，中间有1-3个b字符的字符串。NFA解析它的过程如下：1首先读取正则表达式的第一个匹配字符a，与字符串的第一个字符a进行比较，匹配。然后读取正则表达式的第二个字符。2读取正则表达式的第二个匹配字符b{1,3}，与字符串的第二个字符b比较，匹配。但是因为b{1,3}表示的是1-3个b串，以及NFA自动机的贪心特性（即尽可能多地匹配），所以此时不??会读取下一个正则表达式匹配的字符的公式，但仍然使用b{1,3}与字符串的第三个字符b进行比较，发现仍然匹配。于是继续用b{1,3}与字符串的第四个字符c进行比较，发现没有匹配。此时发生回溯。3回溯是如何发生的？发生回溯后，我们读到的字符串的第四个字符c会被吐出，指针返回到第三个字符串的位置。之后程序读取正则表达式的下一个运算符c，读取当前指针的下一个字符c进行比较，找到匹配。所以下一个运算符被读取了，但是它在这里结束了。我们回过头来看看之前验证URL的正则表达式：^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$有问题的网址是：http://www.javastack.cn/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf我们把这个正则表达式分为三个部分：^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。第二部分：验证域名。(([A-Za-z0-9-~]+).)+.第三部分：检查参数。([A-Za-z0-9-~\\/])+$。我们可以发现，正则表达式验证协议的http://部分没有问题，但是在验证www.javastack.cn时，却使用了xxxx。核实。所以其实匹配过程是这样的：1匹配到www。2匹配javastack。3匹配到cn/dzfp-web/pdf/download?request=6e7JGm38jf...，你会发现因为贪心匹配，所以程序会一直读取后面的字符串进行匹配，最后发现没有点，所以它一个一个地返回。这是这个正则表达式的第一个问题。还有一个问题是，在正则表达式的第三部分，我们发现有问题的URL有下划线（_）和百分号（%），而第三部分对应的正则表达式却没有。这样会导致之前要匹配一长串字符，如果有不匹配，***就往回走。这是这个正则表达式的第二个问题。解决方案了解到回溯是问题的原因后，其实就是为了减少这个回溯。你会发现，如果我在第三部分加上下划线和百分号，程序就正常了。运行上面的程序会立即打印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-~\\/])+$这样以后运行原程序就没有问题了。***推荐一个网站，可以检查你写的正则表达式匹配到对应的字符串会不会有问题[1]。比如我文章中有问题的网址，在与本站核实后会提示：catastrophicbackgracking（灾难性的bac??kgracking）。当你点击左下角的“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问题。他们遇到的问题和我们几乎一模一样。感兴趣的朋友可以点击文章[1]虽然这篇文章已经讲完了，但是NFA自动机的原理，尤其是惰性模式和独占模式的讲解，还是讲解的不够深入。因为NFA自动机真的不是那么好理解的，所以需要在这方面继续学习加强。欢迎有学识的朋友前来学习，交流，互相促进。
