CPU过高问题排查之正则回溯

在实际的项目运行中，遇到cpu频繁升高导致服务器卡死的问题，经过一番的排查分析：发现是由于一段域名正则发生了回溯导致问题发生的。那么，接下来具体看看什么是正则回溯？

概念：

Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯。而一旦发生回溯，那其消耗的时间就会变得很长，有可能是几分钟，也有可能是几个小时，时间长短取决于回溯的次数和复杂度。

事例：

NFA自动机匹配原则, 如下例子正则匹配是拿regex的d跟text文本一个个匹配，d先个T匹配不匹配，d再跟o匹配不匹配，d跟d匹配则匹配，再拿regex的a跟text中d后面的a匹配能匹配，y跟y匹配能匹配，当然实际匹配比这个复杂很多。

text = Today is a nice day
regex = day

NFA自动回溯，例子是regex以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 进行对比，发现匹配则结束。

text = abbc
regex = ab{1,3}c

问题正则：

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\\/])+$

第二部分, 匹配到com/6sfs3sfsa-ggsfdsf-4wrwrwr-geerw-9d094636cab9?#, 你因为贪婪匹配的原因，所以程序会一直读后面的字符串进行匹配，最后发现没有点号，于是就一个个字符回溯回去了，这是第一个问题。

(([A-Za-z0-9-~]+).)+

第三部分, 需要匹配的链接是有特殊符号?#的，但是对应第三部分的正则表达式里面却没有。这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去，时间就比较长了。

([A-Za-z0-9-~\\/])+$

寄语

    有人在奔跑，有人在睡觉，有人在感恩，有人在抱怨，有目标的睡不着，没目标的睡不醒，努力才是人生应有的态度，睁开眼就是新的开始。