摘要:我將上面校驗的正則表達式的第二部分后面加多了個號,即變成這樣這里加了個號這樣之后,運行原有的程序就沒有問題了。
正則表達式是程序員經(jīng)常使用的工具之一。本文作者通過一個正則表達式的陷阱,先深入剖析了出現(xiàn)問題的原因,后給出怎么處理這類問題的方法。最后還給出了一些檢測常見正則表達式問題的工具,十分值得深入研究。
前幾天線上一個項目監(jiān)控信息突然報告異常,上到機器上后查看相關(guān)資源的使用情況,發(fā)現(xiàn) CPU 利用率將近 100%。通過 Java 自帶的線程 Dump 工具,我們導出了出問題的堆棧信息。
我們可以看到所有的堆棧都指向了一個名為 validateUrl 的方法,這樣的報錯信息在堆棧中一共超過 100 處。通過排查代碼,我們知道這個方法的主要功能是校驗 URL 是否合法。
很奇怪,一個正則表達式怎么會導致 CPU 利用率居高不下。為了弄清楚復現(xiàn)問題,我們將其中的關(guān)鍵代碼摘抄出來,做了個簡單的單元測試。
當我們運行上面這個例子的時候,通過資源監(jiān)視器可以看到有一個名為 java 的進程 CPU 利用率直接飆升到了 91.4% 。
看到這里,我們基本可以推斷,這個正則表達式就是導致 CPU 利用率居高不下的兇手!
于是,我們將排錯的重點放在了那個正則表達式上:
^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~/])+$
這個正則表達式看起來沒什么問題,可以分為三個部分:
第一部分匹配 http 和 https 協(xié)議,第二部分匹配 www. 字符,第三部分匹配許多字符。我看著這個表達式發(fā)呆了許久,也沒發(fā)現(xiàn)沒有什么大的問題。
其實這里導致 CPU 使用率高的關(guān)鍵原因就是:Java 正則表達式使用的引擎實現(xiàn)是 NFA 自動機,這種正則表達式引擎在進行字符匹配時會發(fā)生回溯(backtracking)。而一旦發(fā)生回溯,那其消耗的時間就會變得很長,有可能是幾分鐘,也有可能是幾個小時,時間長短取決于回溯的次數(shù)和復雜度。
看到這里,可能大家還不是很清楚什么是回溯,還有點懵。沒關(guān)系,我們一點點從正則表達式的原理開始講起。
正則表達式引擎
正則表達式是一個很方便的匹配符號,但要實現(xiàn)這么復雜,功能如此強大的匹配語法,就必須要有一套算法來實現(xiàn),而實現(xiàn)這套算法的東西就叫做正則表達式引擎。簡單地說,實現(xiàn)正則表達式引擎的有兩種方式:DFA 自動機(Deterministic Final Automata 確定型有窮自動機)和 NFA 自動機(Non deterministic Finite Automaton 不確定型有窮自動機)。
對于這兩種自動機,他們有各自的區(qū)別,這里并不打算深入將它們的原理。簡單地說,DFA 自動機的時間復雜度是線性的,更加穩(wěn)定,但是功能有限。而 NFA 的時間復雜度比較不穩(wěn)定,有時候很好,有時候不怎么好,好不好取決于你寫的正則表達式。但是勝在 NFA 的功能更加強大,所以包括 Java 、.NET、Perl、Python、Ruby、PHP 等語言都使用了 NFA 去實現(xiàn)其正則表達式。
那 NFA 自動加到底是怎么進行匹配的呢?我們以下面的字符和表達式來舉例說明。
text="Today is a nice day."regex="day"
要記住一個很重要的點,即:NFA 是以正則表達式為基準去匹配的。也就是說,NFA 自動機會讀取正則表達式的一個一個字符,然后拿去和目標字符串匹配,匹配成功就換正則表達式的下一個字符,否則繼續(xù)和目標字符串的下一個字符比較。或許你們聽不太懂,沒事,接下來我們以上面的例子一步步解析。
首先,拿到正則表達式的第一個匹配符:d。于是那去和字符串的字符進行比較,字符串的第一個字符是 T,不匹配,換下一個。第二個是 o,也不匹配,再換下一個。第三個是 d,匹配了,那么就讀取正則表達式的第二個字符:a。
讀取到正則表達式的第二個匹配符:a。那著繼續(xù)和字符串的第四個字符 a 比較,又匹配了。那么接著讀取正則表達式的第三個字符:y。
讀取到正則表達式的第三個匹配符:y。那著繼續(xù)和字符串的第五個字符 y 比較,又匹配了。嘗試讀取正則表達式的下一個字符,發(fā)現(xiàn)沒有了,那么匹配結(jié)束。
上面這個匹配過程就是 NFA 自動機的匹配過程,但實際上的匹配過程會比這個復雜非常多,但其原理是不變的。
NFA自動機的回溯
了解了 NFA 是如何進行字符串匹配的,接下來我們就可以講講這篇文章的重點了:回溯。為了更好地解釋回溯,我們同樣以下面的例子來講解。
text="abbc"regex="ab{1,3}c"
上面的這個例子的目的比較簡單,匹配以 a 開頭,以 c 結(jié)尾,中間有 1-3 個 b 字符的字符串。NFA 對其解析的過程是這樣子的:
首先,讀取正則表達式第一個匹配符 a 和 字符串第一個字符 a 比較,匹配了。于是讀取正則表達式第二個字符。
讀取正則表達式第二個匹配符 b{1,3} 和字符串的第二個字符 b 比較,匹配了。但因為 b{1,3} 表示 1-3 個 b 字符串,以及 NFA 自動機的貪婪特性(也就是說要盡可能多地匹配),所以此時并不會再去讀取下一個正則表達式的匹配符,而是依舊使用 b{1,3} 和字符串的第三個字符 b 比較,發(fā)現(xiàn)還是匹配。于是繼續(xù)使用 b{1,3} 和字符串的第四個字符 c 比較,發(fā)現(xiàn)不匹配了。此時就會發(fā)生回溯。
發(fā)生回溯是怎么操作呢?發(fā)生回溯后,我們已經(jīng)讀取的字符串第四個字符 c 將被吐出去,指針回到第三個字符串的位置。之后,程序讀取正則表達式的下一個操作符 c,讀取當前指針的下一個字符 c 進行對比,發(fā)現(xiàn)匹配。于是讀取下一個操作符,但這里已經(jīng)結(jié)束了。
下面我們回過頭來看看前面的那個校驗 URL 的正則表達式:
^([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
我們把這個正則表達式分為三個部分:
第一部分:校驗協(xié)議。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。
第二部分:校驗域名。(([A-Za-z0-9-~]+).)+。
第三部分:校驗參數(shù)。([A-Za-z0-9-~/])+$。
我們可以發(fā)現(xiàn)正則表達式校驗協(xié)議 http:// 這部分是沒有問題的,但是在校驗 www.fapiao.com 的時候,其使用了 xxxx. 這種方式去校驗。那么其實匹配過程是這樣的:
匹配到 www.
匹配到 fapiao.
匹配到 com/dzfp-web/pdf/download?request=6e7JGm38jf.....,你會發(fā)現(xiàn)因為貪婪匹配的原因,所以程序會一直讀后面的字符串進行匹配,最后發(fā)現(xiàn)沒有點號,于是就一個個字符回溯回去了。
這是這個正則表達式存在的第一個問題。
另外一個問題是在正則表達式的第三部分,我們發(fā)現(xiàn)出現(xiàn)問題的 URL 是有下劃線(_)和百分號(%)的,但是對應(yīng)第三部分的正則表達式里面卻沒有。這樣就會導致前面匹配了一長串的字符之后,發(fā)現(xiàn)不匹配,最后回溯回去。這是這個正則表達式存在的第二個問題。
解決方案
明白了回溯是導致問題的原因之后,其實就是減少這種回溯,你會發(fā)現(xiàn)如果我在第三部分加上下劃線和百分號之后,程序就正常了。
運行上面的程序,立刻就會打印出match!!。
但這是不夠的,如果以后還有其他 URL 包含了亂七八糟的字符呢,我們難不成還再修改一遍。肯定不現(xiàn)實嘛!
其實在正則表達式中有這么三種模式:貪婪模式、懶惰模式、獨占模式。
在關(guān)于數(shù)量的匹配中,有 + ? * {min,max} 四種兩次,如果只是多帶帶使用,那么它們就是貪婪模式。
如果在他們之后加多一個 ? 符號,那么原先的貪婪模式就會變成懶惰模式,即盡可能少地匹配。但是懶惰模式還是會發(fā)生回溯現(xiàn)象的。TODO例如下面這個例子:
text="abbc"regex="ab{1,3}?c"
正則表達式的第一個操作符 a 與 字符串第一個字符 a 匹配,匹配成。于是正則表達式的第二個操作符 b{1,3}? 和 字符串第二個字符 b 匹配,匹配成功。因為最小匹配原則,所以拿正則表達式第三個操作符 c 與字符串第三個字符 b 匹配,發(fā)現(xiàn)不匹配。于是回溯回去,拿正則表達式第二個操作符 b{1,3}? 和字符串第三個字符 b 匹配,匹配成功。于是再拿正則表達式第三個操作符 c 與字符串第四個字符 c 匹配,匹配成功。于是結(jié)束。
如果在他們之后加多一個 + 符號,那么原先的貪婪模式就會變成獨占模式,即盡可能多地匹配,但是不回溯。
于是乎,如果要徹底解決問題,就要在保證功能的同時確保不發(fā)生回溯。我將上面校驗 URL 的正則表達式的第二部分后面加多了個 + 號,即變成這樣:
^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)++ ? ?--->>> (這里加了個+號)([A-Za-z0-9-~/])+$
這樣之后,運行原有的程序就沒有問題了。
最后推薦一個網(wǎng)站,這個網(wǎng)站可以檢查你寫的正則表達式和對應(yīng)的字符串匹配時會不會有問題[1]。
例如我本文中存在問題的那個 URL 使用該網(wǎng)站檢查后會提示:catastrophic backgracking(災(zāi)難性回溯)。
當你點擊左下角的「regex debugger」時,它會告訴你一共經(jīng)過多少步檢查完畢,并且會將所有步驟都列出來,并標明發(fā)生回溯的位置。
本文中的這個正則表達式在進行了 11 萬步嘗試之后,自動停止了。這說明這個正則表達式確實存在問題,需要改進。
但是當我用我們修改過的正則表達式進行測試,即下面這個正則表達式。
^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~/])+$
工具提示只用了 58 步就完成了檢查。
一個字符的差別,性能就差距了好幾萬倍。
樹義有話說
一個小小的正則表達式竟然能夠把 CPU 拖垮,也是很神奇了。這也給平時寫程序的我們一個警醒,遇到正則表達式的時候要注意貪婪模式和回溯問題,否則我們每寫的一個表達式都是一個雷。
通過查閱網(wǎng)上資料,我發(fā)現(xiàn)深圳阿里中心 LAZADA 的同學也在 17 年遇到了這個問題。他們同樣也是在測試環(huán)境沒有發(fā)現(xiàn)問題,但是一到線上的時候就發(fā)生了 CPU 100% 的問題,他們遇到的問題幾乎跟我們的一模一樣。有興趣的朋友可查看他們后期總結(jié)的文章[2]
雖然把這篇文章寫完了,但是關(guān)于 NFA 自動機的原理方面,特別是關(guān)于懶惰模式、獨占模式的解釋方面還是沒有解釋得足夠深入。因為 NFA 自動機確實不是那么容易理解,所以在這方面還需要不斷學習加強。歡迎有懂行的朋友來學習交流,互相促進。
文中鏈接:
[1] https://regex101.com
[2] http://www.cnblogs.com/study-everyday/p/7426862.html
歡迎加入本站公開興趣群軟件開發(fā)技術(shù)群
興趣范圍包括:Java,C/C++,Python,PHP,Ruby,shell等各種語言開發(fā)經(jīng)驗交流,各種框架使用,外包項目機會,學習、培訓、跳槽等交流
QQ群:26931708
Hadoop源代碼研究群
興趣范圍包括:Hadoop源代碼解讀,改進,優(yōu)化,分布式系統(tǒng)場景定制,與Hadoop有關(guān)的各種開源項目,總之就是玩轉(zhuǎn)Hadoop
QQ群:288410967?
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/3948.html
摘要:我們把需要的函數(shù)拿出來,看起來會爽的多看到這里是不是就很清晰了簡單的構(gòu)造函數(shù)加原型的繼承結(jié)合上面兩問該問題可以這樣寫回到了用構(gòu)造函數(shù)調(diào)用的模式 先把面試題貼出來: //請回答下面函數(shù)依次執(zhí)行出什么; function Foo () { bar = function () { console.log(1) } return this; } Foo....
摘要:怎么樣,好不好,機房將于月日月日推出月驚爆促銷活動,多重驚喜供您選擇爆款僅美金秒殺爆款產(chǎn)品持續(xù)熱賣洛杉磯硅谷香港日本站群恢復銷售香港產(chǎn)品新增防御最高口口不限流量產(chǎn)品超低價熱賣。RAKsmart怎么樣,RAKsmart好不好,RAKsmart機房將于8月2日~8月31日推出8月驚爆促銷活動,多重驚喜供您選擇;爆款I(lǐng)3-2120僅30美金秒殺、爆款產(chǎn)品持續(xù)熱賣、洛杉磯+硅谷+香港+日本站群恢復銷...
RAKsmart怎么樣,RAKsmart好不好, RAKsmart機房將于8月2日~8月31日推出8月驚爆促銷活動,多重驚喜供您選擇;爆款I(lǐng)3-2120僅30美金秒殺、爆款產(chǎn)品持續(xù)熱賣、洛杉磯+硅谷+香港+日本站群恢復銷售、香港產(chǎn)品新增DDOS防御最高100G、G口/10G口不限流量產(chǎn)品超低價熱賣。活動時間:美國西岸圣何塞時間 08/02/2021~08/31/2021活動產(chǎn)品推薦:活動一:I3-...
RAKsmart怎么樣,RAKsmart好不好,RAKsmart機房將于8月2日~8月31日推出8月驚爆促銷活動,多重驚喜供您選擇;爆款I(lǐng)3-2120僅30美金秒殺、爆款產(chǎn)品持續(xù)熱賣、洛杉磯+硅谷+香港+日本站群恢復銷售、香港產(chǎn)品新增DDOS防御最高100G、G口/10G口不限流量產(chǎn)品超低價熱賣。RAKsmart官方網(wǎng)站點擊進入RAKsmart官方網(wǎng)站促銷活動活動產(chǎn)品推薦:活動一:I3-2120僅...
摘要:總的來說,可以稱為文本主導的正則引擎,可以稱為表達式主導的正則引擎。首先,正則表達式在計算機看來只是一串符號,正則引擎首先肯定要解析它。精通正則表達式書中說引擎不支持非貪婪模式,很明顯不是引擎。正則表達式中可以商榷的部分就叫做備選狀態(tài)。 本文是『horseshoe·Regex專題』系列文章之一,后續(xù)會有更多專題推出GitHub地址:https://github.com/veedrin/...
閱讀 2883·2021-11-24 09:39
閱讀 2455·2019-08-30 15:53
閱讀 3025·2019-08-30 13:47
閱讀 1296·2019-08-30 12:50
閱讀 1481·2019-08-29 16:31
閱讀 2642·2019-08-29 13:14
閱讀 1559·2019-08-29 10:55
閱讀 790·2019-08-26 13:32