共计 4531 个字符，预计需要花费 12 分钟才能阅读完成。
几天前，一个在线项目的监控系统突然报告了一个例外。在检查相关资源的使用情况后，我们发现 CPU 利用率接近 100%。然后我们使用 Java 附带的 thread 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?request=6e7JGxxxxx4ILd-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，在执行字符匹配时执行回溯。一旦发生回溯，所需的时间将变得非常长。可能是几分钟甚至几个小时。时间量取决于回溯的数量和复杂性。
顺便说一下，也许有些人仍然不清楚回溯是什么。没关系，让我们从正则表达式的原则入手。
正则表达式引擎
正则表达式是一组方便的匹配符号。要实现这种复杂而强大的匹配语法，我们必须拥有一组算法，并且算法的实现称为正则表达式引擎。简而言之，有两种方法可以实现正则表达式引擎：（DFA确定性最终自动机）和NFA（非确定性有限自动机）。
这两个自动机是不同的，我们不会深入研究它们的原理。简单地说，时间复杂度 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。让我们继续将它与字符串的第五个字符匹配，然后匹配。然后尝试读取正则表达式的下一个字符，发现没有，所以匹配结束。
以上是匹配过程，NFA实际匹配过程要复杂得多。但是，匹配原则是一样的。
Backtracking(回溯)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 是：
http://www.fapiao.com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf
我们将正则表达式分为三个部分：
- 第 1 部分：验证协议。
^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。 - 第 2 部分：验证域。
(([A-Za-z0-9-~]+).)+。 - 第 3 部分：验证参数。
([A-Za-z0-9-~\\/])+$。
可以发现正则表达式验证协议的部分没有问题 http://，但在验证时www.fapiao.com，它使用 xxxx. 验证方式。所以匹配过程是这样的：
- 匹配到
www。 - 匹配到
fapiao。 - 匹配
com/dzfp-web/pdf/download?request=6e7JGm38jf.....，您将看到由于贪婪的性质，程序将始终尝试读取后续字符串以匹配，最后它发现没有点，因此它开始逐个字符回溯。
这是正则表达式中的第一个问题。
另一个问题是正则表达式的第三部分。可以发现有问题的 URL 有下划线（_）和百分号（%），但对应于第三部分的正则表达不具备。因此，只有在匹配一长串字符后，才会发现它不匹配，然后再回溯。
这是这个正则表达式中的第二个问题。
解释
已经了解到回溯是导致问题的原因。因此问题的解决方案是减少回溯。实际上，您会发现如果将下划线和百分号添加到第三部分，程序将变为正常。
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?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
if (bugUrl.matches(badRegex)) {System.out.println("match!!");
} else {System.out.println("no match!!");
}
}运行上面的程序，它将打印出来 match!!。
如果将来还有其他包含杂乱字符的 URL 怎么办？再改一次？当然这不现实！
事实上，正则表达式有三种模式：贪婪模式 ， 不情愿模式 和占有模式。
如果? 在正则表达式中添加一个符号，则 Greedy 模式将变为 Reluctant 模式，也就是说，它将尽可能少地匹配。但是，在 Reluctant 模式下仍会发生回溯。例如：
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-~]+).)++ --->>>（added + here）([A-Za-z0-9-~_%\\\/])+$现在运行该程序没有问题。
最后，我推荐一个网站，可以检查你写的正则表达式是否有问题以及相应的字符串匹配。
Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript
例如，使用站点检查后将提示本文中存在问题的 URL：灾难性的回溯。
单击左下角的“正则表达式调试器”时，它将告诉您已检查了多少步骤，并将列出所有步骤并指出回溯发生的位置。
本文中的正则表达式在 110,000 步尝试后自动停止。它表明正则表达式确实存在问题，需要改进。
但是当我用修改后的正则表达式测试它时如下：
^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$
提示完成检查只需要 58 步。
一个字符的差异会导致巨大的性能差距。
最后
令人惊讶的是，一个小的正则表达式可以让 CPU 死掉。当遇到正则表达式时它也给我们敲响了警钟，使用时应该注意贪婪模式和回溯问题。
