前幾天線上一個項目監(jiān)控信息突然報告異常恬叹，上到機器上后查看相關資源的使用情況撮胧，發(fā)現(xiàn) CPU 利用率將近 100%伪煤。通過 Java 自帶的線程 Dump 工具，我們導出了出問題的堆棧信息。
我們可以看到所有的堆棧都指向了一個名為 validateUrl 的方法柿估，這樣的報錯信息在堆棧中一共超過 100 處。通過排查代碼，我們知道這個方法的主要功能是校驗 URL 是否合法脸狸。
很奇怪，一個正則表達式怎么會導致 CPU 利用率居高不下。為了弄清楚復現(xiàn)問題炊甲，我們將其中的關鍵代碼摘抄出來泥彤，做了個簡單的單元測試。
publicstaticvoidmain(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!!");? ? }}
當我們運行上面這個例子的時候卿啡，通過資源監(jiān)視器可以看到有一個名為 java 的進程 CPU 利用率直接飆升到了 91.4% 吟吝。
學習Python中的小伙伴，需要學習資料的話颈娜，可以前往我的微信公眾號：速學Python剑逃，后臺回復：簡書，即可拿Python學習資料
這里有我自己整理了一套最新的python系統(tǒng)學習教程官辽，包括從基礎的python腳本到web開發(fā)蛹磺、爬蟲、數(shù)據(jù)分析野崇、數(shù)據(jù)可視化称开、機器學習等。送給正在學習python的小伙伴乓梨！這里是python學習者聚集地鳖轰，歡迎初學和進階中的小伙伴！
看到這里扶镀，我們基本可以推斷蕴侣，這個正則表達式就是導致 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 使用率高的關鍵原因就是：Java 正則表達式使用的引擎實現(xiàn)是 NFA 自動機挽封，這種正則表達式引擎在進行字符匹配時會發(fā)生回溯（backtracking）。而一旦發(fā)生回溯臣镣，那其消耗的時間就會變得很長辅愿，有可能是幾分鐘，也有可能是幾個小時忆某，時間長短取決于回溯的次數(shù)和復雜度点待。
看到這里，可能大家還不是很清楚什么是回溯弃舒，還有點懵癞埠。沒關系，我們一點點從正則表達式的原理開始講起。
正則表達式引擎
正則表達式是一個很方便的匹配符號燕差，但要實現(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 是有下劃線（_）和百分號（%）的，但是對應第三部分的正則表達式里面卻沒有甥角。這樣就會導致前面匹配了一長串的字符之后腰埂，發(fā)現(xiàn)不匹配，最后回溯回去蜈膨。
這是這個正則表達式存在的第二個問題屿笼。
解決方案
明白了回溯是導致問題的原因之后，其實就是減少這種回溯翁巍，你會發(fā)現(xiàn)如果我在第三部分加上下劃線和百分號之后驴一，程序就正常了。
publicstaticvoidmain(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 包含了亂七八糟的字符呢驰凛，我們難不成還再修改一遍胸懈。肯定不現(xiàn)實嘛恰响！
其實在正則表達式中有這么三種模式：貪婪模式趣钱、懶惰模式、獨占模式胚宦。
在關于數(shù)量的匹配中首有，有?+ ? * {min,max}?四種兩次，如果只是單獨使用枢劝，那么它們就是貪婪模式井联。
如果在他們之后加多一個 ? 符號，那么原先的貪婪模式就會變成懶惰模式您旁，即盡可能少地匹配烙常。但是懶惰模式還是會發(fā)生回溯現(xiàn)象的。例如下面這個例子：
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)站可以檢查你寫的正則表達式和對應的字符串匹配時會不會有問題。
Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript
例如我本文中存在問題的那個 URL 使用該網(wǎng)站檢查后會提示：catastrophic backgracking（災難性回溯）苫幢。
當你點擊左下角的「regex debugger」時访诱，它會告訴你一共經(jīng)過多少步檢查完畢，并且會將所有步驟都列出來韩肝，并標明發(fā)生回溯的位置触菜。
本文中的這個正則表達式在進行了 11 萬步嘗試之后，自動停止了伞梯。這說明這個正則表達式確實存在問題玫氢，需要改進。
但是當我用我們修改過的正則表達式進行測試谜诫，即下面這個正則表達式漾峡。
^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$
工具提示只用了 58 步就完成了檢查。
一個字符的差別喻旷，性能就差距了好幾萬倍生逸。
