掃二維碼與項(xiàng)目經(jīng)理溝通
我們?cè)谖⑿派?4小時(shí)期待你的聲音
解答本文疑問(wèn)/技術(shù)咨詢/運(yùn)營(yíng)咨詢/技術(shù)建議/互聯(lián)網(wǎng)交流
通過(guò) Java 自帶的線程 Dump 工具，我們導(dǎo)出了出問(wèn)題的堆棧信息。
公司專注于為企業(yè)提供網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、微信公眾號(hào)開發(fā)、商城網(wǎng)站建設(shè)，成都小程序開發(fā)，軟件按需開發(fā)網(wǎng)站等一站式互聯(lián)網(wǎng)企業(yè)服務(wù)。憑借多年豐富的經(jīng)驗(yàn)，我們會(huì)仔細(xì)了解各客戶的需求而做出多方面的分析、設(shè)計(jì)、整合，為客戶設(shè)計(jì)出具風(fēng)格及創(chuàng)意性的商業(yè)解決方案，創(chuàng)新互聯(lián)更提供一系列網(wǎng)站制作和網(wǎng)站推廣的服務(wù)。
我們可以看到所有的堆棧都指向了一個(gè)名為 validateUrl 的方法，這樣的報(bào)錯(cuò)信息在堆棧中一共超過(guò) 100 處。
通過(guò)排查代碼，我們知道這個(gè)方法的主要功能是校驗(yàn) URL 是否合法。很奇怪，一個(gè)正則表達(dá)式怎么會(huì)導(dǎo)致 CPU 利用率居高不下。
為了弄清楚復(fù)現(xiàn)問(wèn)題，我們將其中的關(guān)鍵代碼摘抄出來(lái)，做了個(gè)簡(jiǎn)單的單元測(cè)試。
- 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í)候，通過(guò)資源監(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á)式看起來(lái)沒(méi)什么問(wèn)題，可以分為三個(gè)部分：
我看著這個(gè)表達(dá)式發(fā)呆了許久，也沒(méi)發(fā)現(xiàn)什么大的問(wèn)題。
其實(shí)這里導(dǎo)致 CPU 使用率高的關(guān)鍵原因就是：Java 正則表達(dá)式使用的引擎實(shí)現(xiàn)是 NFA 自動(dòng)機(jī)，這種正則表達(dá)式引擎在進(jìn)行字符匹配時(shí)會(huì)發(fā)生回溯(backtracking)。
而一旦發(fā)生回溯，那其消耗的時(shí)間就會(huì)變得很長(zhǎng)，有可能是幾分鐘，也有可能是幾個(gè)小時(shí)，時(shí)間長(zhǎng)短取決于回溯的次數(shù)和復(fù)雜度。
看到這里，可能大家還不是很清楚什么是回溯，還有點(diǎn)懵。沒(méi)關(guān)系，我們一點(diǎn)點(diǎn)從正則表達(dá)式的原理開始講起。
正則表達(dá)式引擎
正則表達(dá)式是一個(gè)很方便的匹配符號(hào)，但要實(shí)現(xiàn)這么復(fù)雜，功能如此強(qiáng)大的匹配語(yǔ)法，就必須要有一套算法來(lái)實(shí)現(xiàn)，而實(shí)現(xiàn)這套算法的東西就叫做正則表達(dá)式引擎。
簡(jiǎn)單地說(shuō)，實(shí)現(xiàn)正則表達(dá)式引擎有兩種方式：
對(duì)于這兩種自動(dòng)機(jī)，他們有各自的區(qū)別，這里并不打算深入它們的原理。簡(jiǎn)單地說(shuō)，DFA 自動(dòng)機(jī)的時(shí)間復(fù)雜度是線性的，更加穩(wěn)定，但是功能有限。
而 NFA 的時(shí)間復(fù)雜度比較不穩(wěn)定，有時(shí)候很好，有時(shí)候不怎么好，好不好取決于你寫的正則表達(dá)式。
但是勝在 NFA 的功能更加強(qiáng)大，所以包括 Java 、.NET、Perl、Python、Ruby、PHP 等語(yǔ)言都使用了 NFA 去實(shí)現(xiàn)其正則表達(dá)式。
那 NFA 自動(dòng)機(jī)到底是怎么進(jìn)行匹配的呢?我們以下面的字符和表達(dá)式來(lái)舉例說(shuō)明：
- text="Today is a nice day."
- regex="day"
要記住一個(gè)很重要的點(diǎn)，即：NFA 是以正則表達(dá)式為基準(zhǔn)去匹配的。
也就是說(shuō)，NFA 自動(dòng)機(jī)會(huì)讀取正則表達(dá)式的一個(gè)一個(gè)字符，然后拿去和目標(biāo)字符串匹配，匹配成功就換正則表達(dá)式的下一個(gè)字符，否則繼續(xù)和目標(biāo)字符串的下一個(gè)字符比較。
或許你們聽不太懂，沒(méi)事，接下來(lái)我們以上面的例子一步步解析：
第二個(gè)是 o，也不匹配，再換下一個(gè)。第三個(gè)是 d，匹配了，那么就讀取正則表達(dá)式的第二個(gè)字符：a。
上面這個(gè)匹配過(guò)程就是 NFA 自動(dòng)機(jī)的匹配過(guò)程，但實(shí)際上的匹配過(guò)程會(huì)比這個(gè)復(fù)雜非常多，但其原理是不變的。
NFA 自動(dòng)機(jī)的回溯
了解了 NFA 是如何進(jìn)行字符串匹配的，接下來(lái)我們就可以講講這篇文章的重點(diǎn)了：回溯。
為了更好地解釋回溯，我們同樣以下面的例子來(lái)講解：
- text="abbc"
- regex="ab{1,3}c"
上面這個(gè)例子的目的比較簡(jiǎn)單，匹配以 a 開頭，以 c 結(jié)尾，中間有 1-3 個(gè) b 字符的字符串。
NFA 對(duì)其解析的過(guò)程是這樣子的：
所以此時(shí)并不會(huì)再去讀取下一個(gè)正則表達(dá)式的匹配符，而是依舊使用 b{1,3} 和字符串的第三個(gè)字符 b 比較，發(fā)現(xiàn)還是匹配。
于是繼續(xù)使用 b{1,3} 和字符串的第四個(gè)字符 c 比較，發(fā)現(xiàn)不匹配了。此時(shí)就會(huì)發(fā)生回溯。
之后，程序讀取正則表達(dá)式的下一個(gè)操作符 c，讀取當(dāng)前指針的下一個(gè)字符 c 進(jìn)行對(duì)比，發(fā)現(xiàn)匹配。于是讀取下一個(gè)操作符，但這里已經(jīng)結(jié)束了。
下面我們回過(guò)頭來(lái)看看前面的那個(gè)校驗(yàn) URL 的正則表達(dá)式：
- ^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$
出現(xiàn)問(wè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]://)
那么匹配過(guò)程是這樣的：
這是這個(gè)正則表達(dá)式存在的***個(gè)問(wèn)題;另外一個(gè)問(wèn)題是在正則表達(dá)式的第三部分。
我們發(fā)現(xiàn)出現(xiàn)問(wèn)題的 URL 是有下劃線(_)和百分號(hào)(%)的，但是對(duì)應(yīng)第三部分的正則表達(dá)式里面卻沒(méi)有。
這樣就會(huì)導(dǎo)致前面匹配了一長(zhǎng)串的字符之后，發(fā)現(xiàn)不匹配，***回溯回去。這是這個(gè)正則表達(dá)式存在的第二個(gè)問(wèn)題。
解決方案
明白了回溯是導(dǎo)致問(wèn)題的原因之后，其實(shí)就是減少這種回溯，你會(huì)發(fā)現(xiàn)如果我在第三部分加上下劃線和百分號(hào)之后，程序就正常了。
- 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)行上面的程序，立刻就會(huì)打印出 match!!。但這是不夠的，如果以后還有其他 URL 包含了亂七八糟的字符呢，我們難不成還再修改一遍。肯定不現(xiàn)實(shí)嘛!
其實(shí)在正則表達(dá)式中有這么三種模式：貪婪模式、懶惰模式、獨(dú)占模式。
在關(guān)于數(shù)量的匹配中，有 + ? * {min,max} 四種兩次，如果只是單獨(dú)使用，那么它們就是貪婪模式。
如果在他們之后加多一個(gè) ? 符號(hào)，那么原先的貪婪模式就會(huì)變成懶惰模式，即盡可能少地匹配。但是懶惰模式還是會(huì)發(fā)生回溯現(xiàn)象的。
TODO 例如下面這個(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è) + 符號(hào)，那么原先的貪婪模式就會(huì)變成獨(dú)占模式，即盡可能多地匹配，但是不回溯。
于是乎，如果要徹底解決問(wèn)題，就要在保證功能的同時(shí)確保不發(fā)生回溯。我將上面校驗(yàn) URL 的正則表達(dá)式的第二部分后面加多了個(gè) + 號(hào)，即變成這樣：
- ^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)
- (([A-Za-z0-9-~]+).)++ --->>> （這里加了個(gè)+號(hào)）
- ([A-Za-z0-9-~\\/])+$
這樣之后，運(yùn)行原有的程序就沒(méi)有問(wèn)題了。
***推薦一個(gè)網(wǎng)站，這個(gè)網(wǎng)站可以檢查你寫的正則表達(dá)式和對(duì)應(yīng)的字符串匹配時(shí)會(huì)不會(huì)有問(wèn)題。
例如我本文中存在問(wèn)題的那個(gè) URL 使用該網(wǎng)站檢查后會(huì)提示：catastrophic backgracking(災(zāi)難性回溯)。
當(dāng)你點(diǎn)擊左下角的「regex debugger」時(shí)，它會(huì)告訴你一共經(jīng)過(guò)多少步檢查完畢，并且會(huì)將所有步驟都列出來(lái)，并標(biāo)明發(fā)生回溯的位置。
本文中的這個(gè)正則表達(dá)式在進(jìn)行了 11 萬(wàn)步嘗試之后，自動(dòng)停止了。這說(shuō)明這個(gè)正則表達(dá)式確實(shí)存在問(wèn)題，需要改進(jìn)。
但是當(dāng)我用我們修改過(guò)的正則表達(dá)式進(jìn)行測(cè)試，即下面這個(gè)正則表達(dá)式：
- ^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$
工具提示只用了 58 步就完成了檢查，如下圖：
一個(gè)字符的差別，性能就差距了好幾萬(wàn)倍。
總結(jié)
一個(gè)小小的正則表達(dá)式竟然能夠把 CPU 拖垮，也是很神奇了。這也給平時(shí)寫程序的我們一個(gè)警醒，遇到正則表達(dá)式的時(shí)候要注意貪婪模式和回溯問(wèn)題，否則我們每寫的一個(gè)表達(dá)式都是一個(gè)雷。
通過(guò)查閱網(wǎng)上資料，我發(fā)現(xiàn)深圳阿里中心 LAZADA 的同學(xué)也在 2017 年遇到了這個(gè)問(wèn)題。
他們同樣也是在測(cè)試環(huán)境沒(méi)有發(fā)現(xiàn)問(wèn)題，但是一到線上的時(shí)候就發(fā)生了 CPU 100% 的問(wèn)題，他們遇到的問(wèn)題幾乎跟我們的一模一樣。
雖然把這篇文章寫完了，但是關(guān)于 NFA 自動(dòng)機(jī)的原理方面，特別是關(guān)于懶惰模式、獨(dú)占模式的解釋方面還是沒(méi)有解釋得足夠深入。
因?yàn)?NFA 自動(dòng)機(jī)確實(shí)不是那么容易理解，所以在這方面還需要不斷學(xué)習(xí)加強(qiáng)。歡迎有懂行的朋友來(lái)學(xué)習(xí)交流，互相促進(jìn)。
作者：陳樹義
出處：轉(zhuǎn)載自「陳樹義」微信公眾號(hào)，一個(gè)有情懷的技術(shù)公眾號(hào)，立志用最簡(jiǎn)單的語(yǔ)言，讓復(fù)雜的技術(shù)不再難懂。目前專注 Java 領(lǐng)域的技術(shù)分享，包括但不限于 Java 源碼、SSM、ElasticSearch、JVM、MySQL、MyCat 等技術(shù)領(lǐng)域。關(guān)注樹義君，讓你的技術(shù)成長(zhǎng)不再困難。
本文標(biāo)題：小心踩雷！一個(gè)小小的正則表達(dá)式竟把CPU拖垮......
分享URL：http://uogjgqi.cn/article/cogcsph.html
我們?cè)谖⑿派?4小時(shí)期待你的聲音
解答本文疑問(wèn)/技術(shù)咨詢/運(yùn)營(yíng)咨詢/技術(shù)建議/互聯(lián)網(wǎng)交流
微信二維碼
微信二維碼
移動(dòng)版官網(wǎng)