知識星球點選上方“芋道原始碼”，選擇“置頂公眾號”
技術文章第一時間送達！
原始碼精品專欄
前幾天線上一個專案監控資訊突然報告異常，上到機器上後檢視相關資源的使用情況，發現 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 = "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 的同學也在 17 年遇到了這個問題。他們同樣也是在測試環境沒有發現問題，但是一到線上的時候就發生了 CPU 100% 的問題，他們遇到的問題幾乎跟我們的一模一樣。有興趣的朋友可以點選閱讀原文檢視他們後期總結的文章：一個由正則運算式引發的血案 – 明志健致遠 – 部落格園
雖然把這篇文章寫完了，但是關於 NFA 自動機的原理方面，特別是關於懶惰樣式、獨佔樣式的解釋方面還是沒有解釋得足夠深入。因為 NFA 自動機確實不是那麼容易理解，所以在這方面還需要不斷學習加強。歡迎有懂行的朋友來學習交流，互相促進。
如果你對 Dubbo 感興趣，歡迎加入我的知識星球一起交流。
目前在知識星球（https://t.zsxq.com/2VbiaEu）更新瞭如下 Dubbo 原始碼解析如下：
01. 除錯環境搭建
02. 專案結構一覽
03. 配置 Configuration
04. 核心流程一覽
05. 拓展機制 SPI
06. 執行緒池
07. 服務暴露 Export
08. 服務取用 Refer
09. 註冊中心 Registry
10. 動態編譯 Compile
11. 動態代理 Proxy
12. 服務呼叫 Invoke
13. 呼叫特性
14. 過濾器 Filter
15. NIO 伺服器
16. P2P 伺服器
17. HTTP 伺服器
18. 序列化 Serialization
19. 叢集容錯 Cluster
20. 優雅停機
21. 日誌適配
22. 狀態檢查
23. 監控中心 Monitor
24. 管理中心 Admin
25. 運維命令 QOS
26. 鏈路追蹤 Tracing
…
一共 60 篇++
原始碼不易↓↓↓↓↓
點贊支援老艿艿↓↓
