小心踩雷！一個小小的正則表示式竟把CPU拖垮......
通過 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 = "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 自動機，這種正則表示式引擎在進行字元匹配時會發生回溯(backtracking)。
而一旦發生回溯，那其消耗的時間就會變得很長，有可能是幾分鐘，也有可能是幾個小時，時間長短取決於回溯的次數和複雜度。
看到這裡，可能大家還不是很清楚什麼是回溯，還有點懵。沒關係，我們一點點從正則表示式的原理開始講起。
正則表示式引擎
正則表示式是一個很方便的匹配符號，但要實現這麼複雜，功能如此強大的匹配語法，就必須要有一套演算法來實現，而實現這套演算法的東西就叫做正則表示式引擎。
簡單地說，實現正則表示式引擎有兩種方式：
- 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 比較，匹配了。於是讀取正則表示式第二個字元。
- 讀取正則表示式第二個匹配符 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
我們把這個正則表示式分為三個部分：
校驗協議：^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)
- 校驗域名：(([A-Za-z0-9-~]+).)+
- 校驗引數：([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 包含了亂七八糟的字元呢，我們難不成還再修改一遍。肯定不現實嘛!
其實在正則表示式中有這麼三種模式：貪婪模式、懶惰模式、獨佔模式。
在關於數量的匹配中，有 + ? * {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-~\\/])+$
這樣之後，執行原有的程式就沒有問題了。
最後推薦一個網站，這個網站可以檢查你寫的正則表示式和對應的字串匹配時會不會有問題。
- Online regex tester and debugger：PHP，PCRE，Python，Golang and JavaScript
例如我本文中存在問題的那個 URL 使用該網站檢查後會提示：catastrophic backgracking(災難性回溯)。
當你點選左下角的「regex debugger」時，它會告訴你一共經過多少步檢查完畢，並且會將所有步驟都列出來，並標明發生回溯的位置。
本文中的這個正則表示式在進行了 11 萬步嘗試之後，自動停止了。這說明這個正則表示式確實存在問題，需要改進。
但是當我用我們修改過的正則表示式進行測試，即下面這個正則表示式：
^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$
工具提示只用了 58 步就完成了檢查，如下圖：
一個字元的差別，效能就差距了好幾萬倍。
總結
一個小小的正則表示式竟然能夠把 CPU 拖垮，也是很神奇了。這也給平時寫程式的我們一個警醒，遇到正則表示式的時候要注意貪婪模式和回溯問題，否則我們每寫的一個表示式都是一個雷。
通過查閱網上資料，我發現深圳阿里中心 LAZADA 的同學也在 2017 年遇到了這個問題。
他們同樣也是在測試環境沒有發現問題，但是一到線上的時候就發生了 CPU 100% 的問題，他們遇到的問題幾乎跟我們的一模一樣。
雖然把這篇文章寫完了，但是關於 NFA 自動機的原理方面，特別是關於懶惰模式、獨佔模式的解釋方面還是沒有解釋得足夠深入。
因為 NFA 自動機確實不是那麼容易理解，所以在這方面還需要不斷學習加強。歡迎有懂行的朋友來學習交流，互相促進。
作者：陳樹義
出處：轉載自「陳樹義」微信公眾號，一個有情懷的技術公眾號，立志用最簡單的語言，讓複雜的技術不再難懂。目前專注 Java 領域的技術分享，包括但不限於 Java 原始碼、SSM、ElasticSearch、JVM、SQL/">MySQL、MyCat 等技術領域。關注樹義君，讓你的技術成長不再困難。
