正则表达式导致CPU100%

前言

线上机器cpu百分百,通过dump分析,发现问题出在一个正则表达式匹配方法。^([A-Za-z]+\s*)+$

原因

正则表达式有三种匹配模式:贪婪模式懒惰模式独占模式。有个很好用的正则表达式网站:https://regex101.com/,我们先看几个示例,再来分析这几种模式。
^([A-Za-z]+\s*)+$ 这个正则表达式是匹配类似这种字符串Aa bB cB
^匹配开头;[A-Za-z]+匹配多个英文字母;\s*匹配多个空格;+匹配多个前面括号中的正则字符串格式。

当字符串是a1时候,执行了8步。

WechatIMG272.png

当字符串是aa1时候,执行了16步。

WechatIMG273.png

当字符串是aaaaaaa1时候,执行了512步。

WechatIMG274.png

当字符串是aaaaaaaaaaaaaaaaa1时候,524228步。

WechatIMG275.png

当再增加一个a的时候,提示catastrophic backtracking灾难性的回溯)。

WechatIMG276.png

[A-Za-z]+在匹配aaaaaaaaaaaaa1的时候,会默认采用贪婪模式尽可能多的匹配,当碰到末尾的1时候,会从当前匹配位置的前一位开始,往后继续匹配正则,以此进行回溯,这就导致了指数级的step增长。
我们可以将[A-Za-z]+改成[A-Za-z]++,把贪婪模式改成独占模式,这样表示尽可能多的匹配,且不会回溯。当我们增加?的时候,就表示懒惰模式,最短匹配。

采用独占模式的时候,8步。

WechatIMG279.png

总结

^([A-Za-z]+\s*)+$改成^([A-Za-z]++\s*)+$问题解决。在写正则表达式的过程中,需要多思考一下是否存在灾难性的回溯。

在C#中,禁用非回溯,使用的是(?> )。需要将^([A-Za-z]+\s*)+$改成^((?>[A-Za-z]+)\s*)+$