一個正規表示式引發的血案,讓線上CPU100%異常!

一個正規表示式引發的血案,讓線上CPU100%異常!
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

作者:陳樹義 | 該文來自騰訊雲 社群 陳樹義的專欄

前幾天線上一個專案監控資訊突然報告異常,上到機器上後檢視相關資源的使用情況,發現 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]://)

執行上面的程式,立刻就會列印出match!!

正規表示式的第一個操作符 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 自動機確實不是那麼容易理解,所以在這方面還需要不斷學習加強。歡迎有懂行的朋友來學習交流,互相促進。


問答

如何瞭解正規表示式?

相關閱讀

正規表示式

正則擴充套件練習

C# 正規表示式

此文已由作者授權騰訊雲 社群釋出,原文連結:https://cloud.tencent.com/dev…

歡迎大家前往騰訊雲 社群或關注雲加社群微信公眾號(QcloudCommunity),第一時間獲取更多海量技術實踐乾貨哦~

相關文章

前端開發 最新文章