作者：陳樹義
我們可以看到所有的堆棧都指向了一個名為 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-~/])+$
這樣之後，運作原有的程式就沒有問題了。
例如我本文中存在問題的那個 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 拖垮，也是很神奇了。這也給平時寫程式的我們一個警醒，遇到正規表達式的時候要注意貪婪模式和回溯問題，否則我們每寫的一個表達式都是一個雷。
雖然把這篇文章寫完了，但是關于 NFA 自動機的原理方面，特别是關于懶惰模式、獨占模式的解釋方面還是沒有解釋得足夠深入。因為 NFA 自動機确實不是那麼容易了解，是以在這方面還需要不斷學習加強。歡迎有懂行的朋友來學習交流，互相促進