一個由正則表達式引發(fā)的血案
1. 血案由來
近期我在為Lazada賣家中心做一個自助注冊的項目，其中的shop name校驗規(guī)則較為復雜，要求：
1. 英文字母大小寫
2. 數(shù)字
3. 越南文
4. 一些特殊字符，如“&”，“-”，“_”等
看到這個要求的時候，自然而然地想到了正則表達式。于是就有了下面的表達式(寫的比較齪)：
- ^([A-Za-z0-9._()&'\- ]|
- [aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
在測試環(huán)境，這個表達式從功能上符合業(yè)務方的要求，就被發(fā)布到了馬來西亞的線上環(huán)境。結果上線之后，發(fā)現(xiàn)線上機器時有發(fā)生CPU飆到100%的情況，導致整個站點響應異常緩慢。通過dump線程trace，才發(fā)現(xiàn)線程全部卡在了這個正則表達式的校驗上：
一開始難以置信，一個正則表達式的匹配過程怎么可能引發(fā)CPU飚高呢?抱著懷疑的態(tài)度去查了資料才發(fā)現(xiàn)小小的正則表達式里面竟然大有文章，平時寫起來都是淺嘗輒止，只要能夠滿足功能需求，就認為達到目的了，完全忽略了它可能帶來的性能隱患。
引發(fā)這次血案的就是所謂的正則“回溯陷阱(Catastrophic Backtracking)”。下面詳細介紹下這個問題，以避免重蹈覆轍。
2. 正則表達式引擎
說起回溯陷阱，要先從正則表達式的引擎說起。正則引擎主要可以分為基本不同的兩大類：一種是DFA(確定型有窮自動機)，另一種是NFA(不確定型有窮自動機)。簡單來講，NFA 對應的是正則表達式主導的匹配，而 DFA 對應的是文本主導的匹配。
DFA從匹配文本入手，從左到右，每個字符不會匹配兩次，它的時間復雜度是多項式的，所以通常情況下，它的速度更快，但支持的特性很少，不支持捕獲組、各種引用等等;而NFA則是從正則表達式入手，不斷讀入字符，嘗試是否匹配當前正則，不匹配則吐出字符重新嘗試，通常它的速度比較慢，最優(yōu)時間復雜度為多項式的，最差情況為指數(shù)級的。但NFA支持更多的特性，因而絕大多數(shù)編程場景下(包括java，js)，我們面對的是NFA。以下面的表達式和文本為例，
- text = ‘after tonight’
- regex = ‘to(nite|nighta|night)’
在NFA匹配時候，是根據(jù)正則表達式來匹配文本的，從t開始匹配a，失敗，繼續(xù)，直到文本里面的第一個t，接著比較o和e，失敗，正則回退到 t，繼續(xù)，直到文本里面的第二個t，然后 o和文本里面的o也匹配，繼續(xù)，正則表達式后面有三個可選條件，依次匹配，第一個失敗，接著二、三，直到匹配。
而在DFA匹配時候，采用的是用文本來匹配正則表達式的方式，從a開始匹配t，直到第一個t跟正則的t匹配，但e跟o匹配失敗，繼續(xù)，直到文本里面的第二個 t 匹配正則的t，接著o與o匹配，n的時候發(fā)現(xiàn)正則里面有三個可選匹配，開始并行匹配，直到文本中的g使得第一個可選條件不匹配，繼續(xù)，直到最后匹配。
可以看到，DFA匹配過程中文本中的字符每一個只比較了一次，沒有吐出的操作，應該是快于NFA的。另外，不管正則表達式怎么寫，對于DFA而言，文本的匹配過程是一致的，都是對文本的字符依次從左到右進行匹配，所以，DFA在匹配過程中是跟正則表達式無關的，而 NFA 對于不同但效果相同的正則表達式，匹配過程是完全不同的。
3. 回溯
說完了引擎，我們再來看看到底什么是回溯。對于下面這個表達式，相信大家很清楚它的意圖，
- ab{1,3}c
也就是說中間的b需要匹配1~3次。那么對于文本“abbbc”，按照第1部分NFA引擎的匹配規(guī)則，其實是沒有發(fā)生回溯的，在表達式中的a匹配完成之后，b恰好和文本中的3個b完整匹配，之后是c發(fā)生匹配，一氣呵成。如果我們把文本換成“abc”呢?無非就是少了一個字母b，卻發(fā)生了所謂的回溯。匹配過程如下圖所示(橙色為匹配，黃色為不匹配)，
1~2步應該都好理解，但是為什么在第3步開始，雖然已經(jīng)文本中已經(jīng)有一個b匹配了b{1,3}，后面還會拉著字母c跟b{1,3}做比較呢?這個就是我們下面將要提到的正則的貪婪特性，也就是說b{1,3}會竭盡所能的匹配最多的字符。在這個地方我們先知道它一直要匹配到撞上南墻為止。 在這種情況下，第3步發(fā)生不匹配之后，整個匹配流程并沒有走完，而是像棧一樣，將字符c吐出來，然后去用正則表達式中的c去和文本中的c進行匹配。這樣就發(fā)生了一次回溯。
4. 貪婪、懶惰與獨占
我們再來看一下究竟什么是貪婪模式。
下面的幾個特殊字符相信大家都知道它們的用法：
i. ?: 告訴引擎匹配前導字符0次或一次。事實上是表示前導字符是可選的。
ii. +: 告訴引擎匹配前導字符1次或多次。
iii. *: 告訴引擎匹配前導字符0次或多次。
iv. {min, max}: 告訴引擎匹配前導字符min次到max次。min和max都是非負整數(shù)。如果有逗號而max被省略了，則表示max沒有限制;如果逗號和max都被省略了，則表示重復min次。
默認情況下，這個幾個特殊字符都是貪婪的，也就是說，它會根據(jù)前導字符去匹配盡可能多的內(nèi)容。這也就解釋了為什么在第3部分的例子中，第3步以后的事情會發(fā)生了。
在以上字符后加上一個問號(?)則可以開啟懶惰模式，在該模式下，正則引擎盡可能少的重復匹配字符，匹配成功之后它會繼續(xù)匹配剩余的字符串。在上例中，如果將正則換為
- ab{1,3}?c
則匹配過程變成了下面這樣(橙色為匹配，黃色為不匹配)，
由此可見，在非貪婪模式下，第2步正則中的b{1,3}?與文本b匹配之后，接著去用c與文本中的c進行匹配，而未發(fā)生回溯。
如果在以上四種表達式后加上一個加號(+)，則會開啟獨占模式。同貪婪模式一樣，獨占模式一樣會匹配最長。不過在獨占模式下，正則表達式盡可能長地去匹配字符串，一旦匹配不成功就會結束匹配而不會回溯。我們以下面的表達式為例，
- ab{1,3}+bc
如果我們用文本"abbc"去匹配上面的表達式，匹配的過程如下圖所示(橙色為匹配，黃色為不匹配)，
可以發(fā)現(xiàn)，在第2和第3步，b{1,3}+會將文本中的2個字母b都匹配上，結果文本中只剩下一個字母c。那么在第4步時，正則中的b和文本中的c進行匹配，當無法匹配時，并不進行回溯，這時候整個文本就無法和正則表達式發(fā)生匹配。如果將正則表達式中的加號(+)去掉，那么這個文本整體就是匹配的了。
把以上三種模式的表達式列出如下，
5. 總結
現(xiàn)在再回過頭看看文章開頭的那個很長的正則表達式，其實簡化之后，就是一個形如
^[允許字符集]+
的表達式。該字符集大小約為250，而+號表示至少出現(xiàn)一次。按照上面說到的NFA引擎貪婪模式，在用戶輸入一個過長字符串進行匹配時，一旦發(fā)生回溯，計算量將是巨大的。后來采用了獨占模式，CPU 100%的問題也得到了解決。
因此，在自己寫正則表達式的時候，一定不能大意，在實現(xiàn)功能的情況下，還要仔細考慮是否會帶來性能隱患。
【本文為51CTO專欄作者“阿里巴巴官方技術”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】
