前幾天線上一個(gè)項(xiàng)目監(jiān)控信息突然報(bào)告異常，上到機(jī)器上后查看相關(guān)資源的使用情況，發(fā)現(xiàn) CPU 利用率將近 100%。通過 Java 自帶的線程 Dump 工具，我們導(dǎo)出了出問題的堆棧信息。

我們可以看到所有的堆棧都指向了一個(gè)名為 validateUrl 的方法，這樣的報(bào)錯(cuò)信息在堆棧中一共超過 100 處。通過排查代碼，我們知道這個(gè)方法的主要功能是校驗(yàn) URL 是否合法。

很奇怪，一個(gè)正則表達(dá)式怎么會導(dǎo)致 CPU 利用率居高不下。為了弄清楚復(fù)現(xiàn)問題，我們將其中的關(guān)鍵代碼摘抄出來，做了個(gè)簡單的單元測試。

  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!!");    }  }

當(dāng)我們運(yùn)行上面這個(gè)例子的時(shí)候，通過資源監(jiān)視器可以看到有一個(gè)名為 java 的進(jìn)程 CPU 利用率直接飆升到了 91.4% 。

看到這里，我們基本可以推斷，這個(gè)正則表達(dá)式就是導(dǎo)致 CPU 利用率居高不下的兇手！

于是，我們將排錯(cuò)的重點(diǎn)放在了那個(gè)正則表達(dá)式上：

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

這個(gè)正則表達(dá)式看起來沒什么問題，可以分為三個(gè)部分：

第一部分匹配 http 和 https 協(xié)議，第二部分匹配 www. 字符，第三部分匹配許多字符。我看著這個(gè)表達(dá)式發(fā)呆了許久，也沒發(fā)現(xiàn)沒有什么大的問題。

其實(shí)這里導(dǎo)致 CPU 使用率高的關(guān)鍵原因就是：Java 正則表達(dá)式使用的引擎實(shí)現(xiàn)是 NFA 自動機(jī)，這種正則表達(dá)式引擎在進(jìn)行字符匹配時(shí)會發(fā)生回溯（backtracking）。而一旦發(fā)生回溯，那其消耗的時(shí)間就會變得很長，有可能是幾分鐘，也有可能是幾個(gè)小時(shí)，時(shí)間長短取決于回溯的次數(shù)和復(fù)雜度。

看到這里，可能大家還不是很清楚什么是回溯，還有點(diǎn)懵。沒關(guān)系，我們一點(diǎn)點(diǎn)從正則表達(dá)式的原理開始講起。

正則表達(dá)式引擎

正則表達(dá)式是一個(gè)很方便的匹配符號，但要實(shí)現(xiàn)這么復(fù)雜，功能如此強(qiáng)大的匹配語法，就必須要有一套算法來實(shí)現(xiàn)，而實(shí)現(xiàn)這套算法的東西就叫做正則表達(dá)式引擎。簡單地說，實(shí)現(xiàn)正則表達(dá)式引擎的有兩種方式：DFA 自動機(jī)（Deterministic Final Automata 確定型有窮自動機(jī)）和 NFA 自動機(jī)（Non deterministic Finite Automaton 不確定型有窮自動機(jī)）。

對于這兩種自動機(jī)，他們有各自的區(qū)別，這里并不打算深入將它們的原理。簡單地說，DFA 自動機(jī)的時(shí)間復(fù)雜度是線性的，更加穩(wěn)定，但是功能有限。而 NFA 的時(shí)間復(fù)雜度比較不穩(wěn)定，有時(shí)候很好，有時(shí)候不怎么好，好不好取決于你寫的正則表達(dá)式。但是勝在 NFA 的功能更加強(qiáng)大，所以包括 Java 、.NET、Perl、Python、Ruby、PHP 等語言都使用了 NFA 去實(shí)現(xiàn)其正則表達(dá)式。

那 NFA 自動機(jī)到底是怎么進(jìn)行匹配的呢？我們以下面的字符和表達(dá)式來舉例說明。

  text="Today is a nice day."  regex="day"

要記住一個(gè)很重要的點(diǎn)，即：NFA 是以正則表達(dá)式為基準(zhǔn)去匹配的。也就是說，NFA 自動機(jī)會讀取正則表達(dá)式的一個(gè)一個(gè)字符，然后拿去和目標(biāo)字符串匹配，匹配成功就換正則表達(dá)式的下一個(gè)字符，否則繼續(xù)和目標(biāo)字符串的下一個(gè)字符比較。或許你們聽不太懂，沒事，接下來我們以上面的例子一步步解析。

• 首先，拿到正則表達(dá)式的第一個(gè)匹配符：d。于是那去和字符串的字符進(jìn)行比較，字符串的第一個(gè)字符是 T，不匹配，換下一個(gè)。第二個(gè)是 o，也不匹配，再換下一個(gè)。第三個(gè)是 d，匹配了，那么就讀取正則表達(dá)式的第二個(gè)字符：a。
• 讀取到正則表達(dá)式的第二個(gè)匹配符：a。那著繼續(xù)和字符串的第四個(gè)字符 a 比較，又匹配了。那么接著讀取正則表達(dá)式的第三個(gè)字符：y。
• 讀取到正則表達(dá)式的第三個(gè)匹配符：y。那著繼續(xù)和字符串的第五個(gè)字符 y 比較，又匹配了。嘗試讀取正則表達(dá)式的下一個(gè)字符，發(fā)現(xiàn)沒有了，那么匹配結(jié)束。

上面這個(gè)匹配過程就是 NFA 自動機(jī)的匹配過程，但實(shí)際上的匹配過程會比這個(gè)復(fù)雜非常多，但其原理是不變的。

NFA自動機(jī)的回溯

了解了 NFA 是如何進(jìn)行字符串匹配的，接下來我們就可以講講這篇文章的重點(diǎn)了：回溯。為了更好地解釋回溯，我們同樣以下面的例子來講解。

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

上面的這個(gè)例子的目的比較簡單，匹配以 a 開頭，以 c 結(jié)尾，中間有 1-3 個(gè) b 字符的字符串。NFA 對其解析的過程是這樣子的：

• 首先，讀取正則表達(dá)式第一個(gè)匹配符 a 和 字符串第一個(gè)字符 a 比較，匹配了。于是讀取正則表達(dá)式第二個(gè)字符。
• 讀取正則表達(dá)式第二個(gè)匹配符 b{1,3} 和字符串的第二個(gè)字符 b 比較，匹配了。但因?yàn)?b{1,3} 表示 1-3 個(gè) b 字符串，以及 NFA 自動機(jī)的貪婪特性（也就是說要盡可能多地匹配），所以此時(shí)并不會再去讀取下一個(gè)正則表達(dá)式的匹配符，而是依舊使用 b{1,3} 和字符串的第三個(gè)字符 b 比較，發(fā)現(xiàn)還是匹配。于是繼續(xù)使用 b{1,3} 和字符串的第四個(gè)字符 c 比較，發(fā)現(xiàn)不匹配了。此時(shí)就會發(fā)生回溯。發(fā)生回溯是怎么操作呢？
• 發(fā)生回溯后，我們已經(jīng)讀取的字符串第四個(gè)字符 c 將被吐出去，指針回到第三個(gè)字符串的位置。之后，程序讀取正則表達(dá)式的下一個(gè)操作符 c，讀取當(dāng)前指針的下一個(gè)字符 c 進(jìn)行對比，發(fā)現(xiàn)匹配。于是讀取下一個(gè)操作符，但這里已經(jīng)結(jié)束了。

下面我們回過頭來看看前面的那個(gè)校驗(yàn) URL 的正則表達(dá)式：

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

出現(xiàn)問題的 URL 是：

  http://www.fapiao.com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf

我們把這個(gè)正則表達(dá)式分為三個(gè)部分：

• 第一部分：校驗(yàn)協(xié)議。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。
• 第二部分：校驗(yàn)域名。(([A-Za-z0-9-~]+).)+。
• 第三部分：校驗(yàn)參數(shù)。([A-Za-z0-9-~\/])+$。

我們可以發(fā)現(xiàn)正則表達(dá)式校驗(yàn)協(xié)議 http:// 這部分是沒有問題的，但是在校驗(yàn) www.fapiao.com 的時(shí)候，其使用了 xxxx. 這種方式去校驗(yàn)。那么其實(shí)匹配過程是這樣的：

• 匹配到 www.匹配到 fapiao.
• 匹配到 com/dzfp-web/pdf/download?request=6e7JGm38jf.....，你會發(fā)現(xiàn)因?yàn)樨澙菲ヅ涞脑?，所以程序會一直讀后面的字符串進(jìn)行匹配，最后發(fā)現(xiàn)沒有點(diǎn)號，于是就一個(gè)個(gè)字符回溯回去了。

這是這個(gè)正則表達(dá)式存在的第一個(gè)問題。

另外一個(gè)問題是在正則表達(dá)式的第三部分，我們發(fā)現(xiàn)出現(xiàn)問題的 URL 是有下劃線（_）和百分號（%）的，但是對應(yīng)第三部分的正則表達(dá)式里面卻沒有。這樣就會導(dǎo)致前面匹配了一長串的字符之后，發(fā)現(xiàn)不匹配，最后回溯回去。

這是這個(gè)正則表達(dá)式存在的第二個(gè)問題。

解決方案

明白了回溯是導(dǎo)致問題的原因之后，其實(shí)就是減少這種回溯，你會發(fā)現(xiàn)如果我在第三部分加上下劃線和百分號之后，程序就正常了。

  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!!");    }  }

運(yùn)行上面的程序，立刻就會打印出match!!。

但這是不夠的，如果以后還有其他 URL 包含了亂七八糟的字符呢，我們難不成還再修改一遍?？隙ú滑F(xiàn)實(shí)嘛！

其實(shí)在正則表達(dá)式中有這么三種模式：貪婪模式、懶惰模式、獨(dú)占模式。

在關(guān)于數(shù)量的匹配中，有 + ? * {min,max} 四種兩次，如果只是單獨(dú)使用，那么它們就是貪婪模式。

如果在他們之后加多一個(gè) ? 符號，那么原先的貪婪模式就會變成懶惰模式，即盡可能少地匹配。但是懶惰模式還是會發(fā)生回溯現(xiàn)象的。例如下面這個(gè)例子：

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

正則表達(dá)式的第一個(gè)操作符 a 與 字符串第一個(gè)字符 a 匹配，匹配成功。于是正則表達(dá)式的第二個(gè)操作符 b{1,3}? 和 字符串第二個(gè)字符 b 匹配，匹配成功。因?yàn)樽钚∑ヅ湓瓌t，所以拿正則表達(dá)式第三個(gè)操作符 c 與字符串第三個(gè)字符 b 匹配，發(fā)現(xiàn)不匹配。于是回溯回去，拿正則表達(dá)式第二個(gè)操作符 b{1,3}? 和字符串第三個(gè)字符 b 匹配，匹配成功。于是再拿正則表達(dá)式第三個(gè)操作符 c 與字符串第四個(gè)字符 c 匹配，匹配成功。于是結(jié)束。

如果在他們之后加多一個(gè) + 符號，那么原先的貪婪模式就會變成獨(dú)占模式，即盡可能多地匹配，但是不回溯。

于是乎，如果要徹底解決問題，就要在保證功能的同時(shí)確保不發(fā)生回溯。我將上面校驗(yàn) URL 的正則表達(dá)式的第二部分后面加多了個(gè) + 號，即變成這樣：

  ^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)  (([A-Za-z0-9-~]+).)++  --->>> （這里加了個(gè)+號）  ([A-Za-z0-9-~_%\/])+$

這樣之后，運(yùn)行原有的程序就沒有問題了。

最后推薦一個(gè)網(wǎng)站，這個(gè)網(wǎng)站可以檢查你寫的正則表達(dá)式和對應(yīng)的字符串匹配時(shí)會不會有問題。

Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript

例如我本文中存在問題的那個(gè) URL 使用該網(wǎng)站檢查后會提示：catastrophic backgracking（災(zāi)難性回溯）。

當(dāng)你點(diǎn)擊左下角的「regex debugger」時(shí)，它會告訴你一共經(jīng)過多少步檢查完畢，并且會將所有步驟都列出來，并標(biāo)明發(fā)生回溯的位置。

本文中的這個(gè)正則表達(dá)式在進(jìn)行了 11 萬步嘗試之后，自動停止了。這說明這個(gè)正則表達(dá)式確實(shí)存在問題，需要改進(jìn)。

但是當(dāng)我用我們修改過的正則表達(dá)式進(jìn)行測試，即下面這個(gè)正則表達(dá)式。

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

工具提示只用了 58 步就完成了檢查。

總結(jié)

以上所述是小編給大家介紹的藏在正則表達(dá)式里的陷阱，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時(shí)回復(fù)大家的。在此也非常感謝大家對網(wǎng)站的支持！