正則性能調優

這篇文章主要是分享最近在開發中正則的學習心得體會。我們開發，一開始是采用python的正則庫，后來為了適應Spring Cloud兼容Java所以正則也相應的修改成為了Java版本，經過測試，Java在匹配速度上相對慢了好多，平臺一天需要處理一億多條日志，但按照當時的處理速度，每天差不多就只能處理了2千多萬條，這樣的速度，實在扎心，提單申請擴容，那邊的負責人說資源不足，好咯，將Java所使用的正則庫替換成C++，C++夠快了吧，不過，這個庫是通過犧牲功能換取性能來實現的。

正則表達式的原理

理論模型是有窮自動機,具體的實現為正則引擎(Regex Engine)分兩類確定型有窮自動機(Definite Finite Automata，DFA,其狀態都是確定)和非確定型有窮自動機(Non-definite Finite Automate，NFA,其狀態在某個時刻是不確定的)。DFA和NFA是可以證明存在等價關系,不過這是兩種不同的自動機。在這里，我才不會深入討論它們的原理。簡單地說，DFA 的時間復雜度是線性的。它更穩定，但功能有限。NFA 的時間復雜度相對不穩定。 根據正則表達式的不同，時間有時長，有時短。NFA 的優點是它的功能更強大，所以被 Java、.NET、Perl、Python、Ruby 和 PHP 用來處理正則表達式。 NFA 是怎樣進行匹配的呢？我用下面的字符串和表達式作為例子。

text="A lovely cat."
regex="cat"

NFA 匹配是基于正則表達式的。也就是說，NFA 將依次讀取正則表達式的匹配符，并將其與目標字符串進行匹配。如果匹配成功，它將轉到正則表達式的下一個匹配符。否則，它將繼續與目標字符串的下一個字符進行比較。 讓我們一步一步地來看一下上面的例子。

• 首先，提取正則表達式的第一個匹配符：c。然后，將它與字符串的第一個字符 A 進行比較。不匹配，所以轉到下一個。第二個字符是 l，也不匹配。繼續轉到下一個，也就是 o。匹配失敗。于是，繼續讀取text的字符直到c，匹配成功猴，讀取正則表達式的第二個字符： a。
• 正則表達式的第二個匹配符是：a。將它與字符串的第九個字符 a進行比較。又匹配了。于是繼續讀取正則表達式的第三個字符 t。
• 正則表達式的第三個匹配符是 t。讓我們繼續與字符串的第十個字符比較。匹配成功。接著，嘗試讀取正則表達式的下一個字符，發現沒有字符了，因此匹配結束。

回溯（backtracking）

為了應對NFA狀態不確定，可能會匹配出錯誤的結果，因此需要“嘗試失敗-重新選擇”的過程，現在，我已經解釋了 NFA 是如何進行字符串匹配的——回溯法。我們將使用下面的例子，以便更好的解釋回朔法。

text="xyyyyyyz"
regex="xy{1,10}z"

這是一個比較簡單的例子。正則表達式以 x 開始，以 z 結束。它們之間有以 1-10 個 y 組成的字符串。NFA 的匹配過程如下：

• 首先，讀取正則表達式的第一個匹配符 x，并將其與字符串的第一個字符 x 進行比較。兩者匹配，所以，接下來是移動到正則表達式的第二個字符。
• 讀取正則表達式的第二個匹配符 y{1,10}，將它與字符串的第二個字符 y 進行比較。它們又匹配了。y{1,10} 代表 1-10 個 y，基于 NFA 的貪婪特性（即，盡可能地進行匹配），此時它不會讀取正則表達式的下一個匹配符，而是仍然使用y{1,10} 與字符串的第三個字符 y 進行比較。它們匹配了。于是繼續用 y{1,10} 與字符串的第n個字符 y 進行比較，直到第七個，它們不匹配。 回溯就出現在這里
• 那么回溯是如何進行的？回溯后，字符串中已被讀取的第七個字符 y 將被放棄。指針將返回到字符串的第三個字符。接著，正則表達式的下一個匹配符 z 會被用來與待匹配字符串當前指針的下一個字符 z 進行對比。兩者是匹配的。這時，字符串最后一個字符已經被讀取。匹配結束。

正則表達式的三種模式

1. 貪婪模式
   • 這個就是最簡單的匹配模式，也是最先接觸的匹配模式
2. 勉強模式
   • 在正則表達式中添加一個?標志，貪婪模式將變成勉強模式。此時，它將盡可能少地匹配。然而，勉強模式下回溯仍可能出現。
3. 獨占模式
   • 如果添加+標志，則原來的貪婪模式將變成獨占模式。也就是說，它將匹配盡可能多的字符，但不會回溯。

text="xyyyyyyz"
regex="xy{1,10}?z"

正則表達式的第一個字符 x 與字符串的第一個字符 x 相匹配。正則表達式的第二個運算符 y{1,10}? 匹配了字符串的第二個字符 y 。由于最小匹配的原則，正則表達式將讀取第三個運算符 z，并與字符串第三個字符 y 進行比較。兩者不匹配。因此，程序進行回溯并將正則表達式的第二個運算符 y{1,10}? 與字符串的第三個字符 y 進行比較。還是匹配成功了。之后繼續匹配，正則表達式的第三個匹配符 c 與字符串的第七個字符 z 正相匹配。匹配結束。
這三種模式，在Python，Java這些常見的開發工具中是比較常用的，然而在C++中并不是合適，我們開發團隊經過一次次的修改、優化，在性能調優上才有了質的飛躍。

調優分析

下面以一份日志為例，介紹利用前面介紹的三種模式所開發出來的模型匹配。

[INFO][08:27:34.260][2b0e7244d940]:LOGIN| client_id=007102| ip=8.8.8.8| uin=66666666 | mailname=123456789@139.com| userip=223.3.3.3|

我們想要的就是將日志中的數據進行提取，獲得我們想要的內容，其中包括，clientIP、userID、user、mobileNumber這些，因為還有其他數據描述，后續提高數據挖掘的效率，和對安全風險的分析能力，我們也想對這些日志進行解析。一開始我們使用貪婪模式，也就是常見的使用*，看圖中箭頭方向，這個步長4635，大概需要11ms，步長其實就是回溯的次數，迭代計算這么多次，對于性能來說確實挺令人失望的，原因已經很明顯了，就是由于*導致的，貪婪匹配n次直到和下個符號不匹配為止，因此消耗了大量的計算性能，這個也是我們需要進行優化地方。

^[(?P<type>.)][(?P<null1>.)][(?P<null2>.)].\=(?P<cid>.)|.\=(?P<ip>.)|.\=(?P<uin>.)|.\=(?P<mailname>.)|.\=(?P<userip>.*)$

接下來開始調優對原來的貪婪模式追加勉強匹配（外文名詞翻譯真讓人抓狂），匹配效果卓著，原因在于勉強模式盡最大努力地減少了回溯次數，在原來的回溯全文之后的基礎上，該模式如果遇匹配上了下個字符，立即結束，比如匹配type這個字段，我們的原先的貪婪模式，沒遇到一次就會全文都匹配一遍之后在回到起點，確認匹配完成，而勉強模式則是在邊界就停下來，比如\],\[等字段。
到了這里我們并不滿足，是否還可以更快，對計算資源是否可以更友好？畢竟我們的計算資源很寶貴，于是可以繼續嘗試使用獨占模式。見下圖

^[(?P<type>.?)][(?P<null1>.?)][(?P<null2>.?)].?\=(?P<cid>.?)|.?\=(?P<ip>.?)|.\=(?P<uin>.?)|.?\=(?P<mailname>.?)|.?\=(?P<userip>.*?)$

在這個模式下我們的表達式性能得到了極大的提升，此時相較于初始版本，性能已經提高了十倍，稱之為勉強追加獨占模式，該匹配已經匹配了，基本上可以交差給服務器日夜不停工作了。

此時性能看起來已經達到了最優了，但我們要考慮到表達式的健壯性，畢竟在眾多的日志里，總會出現有些字段為空（并不是null）的情況，如下圖所示，我特意刪除一些字段，如果是空格還好，當不是的時候又應該怎么處理咧？

這里需要使用|這個符號，對這樣的場景經行適配,此時不管是空的還是有數據的都沒啥關系了，我們已經做好了應對準備。

^[(?P<type>.+?)][(?P<null1>.+?)][(?P<null2>.+?)].+?\=(?P<cid>.+?)|.+?\=(?P<ip>.+?)|.*\=(?P<uin>.+?)|.+?\=(?P<mailname>.+?)|.+?\=(?P<userip>.+?)$

最終版

[(?P<type>|.+?)][(?P<null1>|.+?)][(?P<null2>|.+?)].+?\=(?P<cid>|.+?)|.+?\=(?P<ip>|.+?)|.*\=(?P<uin>|.+?)|.+?\=(?P<mailname>|.+?)|.+?\=(?P<userip>.+|)

這里我特意刪除^和$這兩個字符，考慮到在這個場景下，其實沒必要規定起止符，因為我們是全文匹配的，起止符的出現反而需要計算機再驗證一次是否到了終點，確定一下自己是不是在起點，有點畫蛇添足。

結束語

在生產環境中學習很快，尷尬的就是沒時間沉淀，生產的過程中遇到了好多我覺得是經典的場景，時間不允許匆匆留在工作筆記中，還沒探究出所以然。之前以為我學會了正則，搞爬蟲嘛，對正則也是要有一定的理解的，在進行模型分析的這段時間越發看不懂正則，總覺得這個是在寫啥，官網說的是啥，看文檔，現在寫正則舒服很多了，處理日志各種不規范，提供的日志規范和接收到日志70%以上是不匹配的，還有拼寫錯誤 ，各種命名法， 形式翻新，永不重復，這叫一個皮。。。

推薦網站

在線正則測試網站
這個網站可以很明顯的提示我們表達式中的錯誤內容，或者說不符合語法規則的地方。跟我們說明該表達式的性能特點，消耗的資源等信息。