前几天线上一个项目监控信息突然报告异常，上到机器上后查看相关资源的运用状况，发现 CPU 应用率将近 100%。经过 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 = "?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 协议，第二部分婚配 字符，第三部分婚配许多字符。我看着这个表达式发愣了许久，也没发现没有什么大的成绩。
其实这里招致 CPU 运用率高的关键缘由就是：Java 正则表达式运用的引擎完成是 NFA 自动机，这种正则表达式引擎在停止字符婚配时会发作回溯(backtracking)。而一旦发作回溯，那其消耗的时间就会变得很长，有能够是几分钟，也有能够是几个小时，时间长短取决于回溯的次数和复杂度。
假设想学习Java工程化、高功用及散布式、深化浅出。微效劳、Spring，MyBatis，Netty源码剖析的冤家可以加我的Java初级交流：854630135，群里有阿里大牛直播解说技术，以及Java大型互联网技术的视频收费分享给大家。
看到这里，能够大家还不是很清楚什么是回溯，还有点懵。没关系，我们一点点从正则表达式的原理末尾讲起。
正则表达式引擎
正则表达式是一个很方便的婚配符号，但要完成这么复杂，功用如此弱小的婚配语法，就必需要有一套算法来完成，而完成这套算法的东西就叫做正则表达式引擎。复杂地说，完成正则表达式引擎的有两种方式：DFA 自动机(Deterministic Final Automata 确定型有穷自动机)和 NFA 自动机(Non deterministic Finite Automaton 不确定型有穷自动机)。
关于这两种自动机，他们有各自的区别，这里并不计划深化将它们的原理。复杂地说，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。那着继续和字符串的第五个字符 y 比较，又婚配了。尝试读取正则表达式的下一个字符，发现没有了，那么婚配完毕。
下面这个婚配进程就是 NFA 自动机的婚配进程，但实践上的婚配进程会比这个复杂十分多，但其原理是不变的。
NFA自动机的回溯
了解了 NFA 是如何停止字符串婚配的，接上去我们就可以讲讲这篇文章的重点了：回溯。为了更好地解释回溯，我们异样以下面的例子来解说。
text="abbc"
regex="ab{1,3}c"
下面的这个例子的目的比较复杂，婚配以 a 扫尾，以 c 开头，中间有 1-3 个 b 字符的字符串。NFA 对其解析的进程是这样子的：
首先，读取正则表达式第一个婚配符 a 和 字符串第一个字符 a 比较，婚配了。于是读取正则表达式第二个字符。
(责任编辑：admin)