前幾天線上一個項目監控信息突然報告異常，上到機器上後查看相關資源的使用情況，發現 CPU 利用率將近 100%。通過 Java 自帶的線程 Dump 工具，我們導出了出問題的堆棧信息。我們可以看到所有的堆棧都指向了一個名為 validateUrl 的方法，這樣的報錯信息在堆棧中一共超過 100 處。通過排查代碼，我們知道這個方法的主要功能是校驗 URL 是否合法。很奇怪，一個正則表達式怎麽會導致 CPU 利用率居高不下。為了弄清楚復現問題，我們將其中的關鍵代碼摘抄出來，做了個簡單的單元測試。當我們運行上面這個例子的時候，通過資源監視器可以看到有一個名為 java 的進程 CPU 利用率直接飆升到了 91.4% 。

      看到這裏，我們基本可以推斷，這個正則表達式就是導致 CPU 利用率居高不下的兇手！於是，我們將排錯的重點放在了那個正則表達式上：這個正則表達式看起來沒什麽問題，可以分為三個部分：第一部分匹配 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 自動加到底是怎麽進行匹配的呢？我們以下面的字符和表達式來舉例說明。要記住一個很重要的點，即：NFA 是以正則表達式為基準去匹配的。也就是說，NFA 自動機會讀取正則表達式的一個一個字符，然後拿去和目標字符串匹配，匹配成功就換正則表達式的下一個字符，否則繼續和目標字符串的下一個字符比較。或許你們聽不太懂，沒事，接下來我們以上面的例子一步步解析。首先，拿到正則表達式的第一個匹配符：d。於是那去和字符串的字符進行比較，字符串的第一個字符是 T，不匹配，換下一個。第二個是 o，也不匹配，再換下一個。第三個是 d，匹配了，那麽就讀取正則表達式的第二個字符：a。讀取到正則表達式的第二個匹配符：a。那著繼續和字符串的第四個字符 a 比較，又匹配了。那麽接著讀取正則表達式的第三個字符：y。讀取到正則表達式的第三個匹配符：y。那著繼續和字符串的第五個字符 y 比較，又匹配了。嘗試讀取正則表達式的下一個字符，發現沒有了，那麽匹配結束。上面這個匹配過程就是 NFA 自動機的匹配過程，但實際上的匹配過程會比這個復雜非常多，但其原理是不變的。

     NFA 自動機的回溯。了解了 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 進行對比，發現匹配。於是讀取下一個操作符，但這裏已經結束了。

   一個小小的正則表達式竟然能夠把 CPU 拖垮，也是很神奇了。這也給平時寫程序的我們一個警醒，遇到正則表達式的時候要註意貪婪模式和回溯問題，否則我們每寫的一個表達式都是一個雷。其實在網上查閱資料的過程中，我發現深圳阿裏中心 LAZADA 的同學也在 17 年遇到了這個問題。他們同樣也是在測試環境沒有發現問題，但是一到線上的時候就發生了 CPU 100% 的問題，他們遇到的問題幾乎跟我們的一模一樣。有興趣的朋友可以點擊閱讀原文查看他們後期總結的文章：一個由正則表達式引發的血案 -雖然把這篇文章寫完了，但是關於 NFA 自動機的原理方面，特別是關於懶惰模式、獨占模式的解釋方面還是沒有解釋得足夠深入。因為 NFA 自動機確實不是那麽容易理解，所以在這方面還需要不斷學習加強。歡迎有懂行的朋友來學習交流，互相促進。