1。血案缘起最近在做LazadaSellerCenter的自注册项目，店名验证规则比较复杂。需求：1.英文字母和大小写2.数字3.越南语4.一些特殊字符，比如“&”，“-”，“_”等看到这个需求，自然而然的就想到了正则表达式。Sothereisthefollowingexpression(comparedwith龊):^([a-za-z0-9.9._()\-]|[aaàà????áá??????????????aa??????????bbcdd??eeeeeeeeeghhiìì????íí??jjkllmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmnnoo's;?vVwWxXyY?????yY??zZ])+$在测试环境下，该表达式在功能上满足业务方的要求，发布到马来西亚线上环境。导致整个站点响应异常缓慢。通过dumpthreadtrace，发现线程都卡在了正则表达式校验中：一开始难以置信，一个正则表达式匹配过程怎么会导致CPU飙升？抱着半信半疑的态度查了资料才发现小正则的文章很多，平时写的也比较肤浅。只要能满足功能需求，就认为目的达到了，而可能带来的性能隐患则完全忽略不计。所谓的定期“回溯陷阱（CatastrophicBacktracking）”造成了这起血案。下面详细描述这个问题，以免重蹈覆辙。2、正则表达式引擎说起回溯陷阱，首先要从正则表达式引擎说起。正则引擎可以分为两大类：一类是DFA（确定性有限自动机），一类是NFA（不确定性有限自动机）。简单来说，NFA对应的是基于正则表达式的匹配，而DFA对应的是基于文本的匹配。DFA从匹配文本开始，从左到右，每个字符不会匹配两次，它的时间复杂度是多项式的，所以一般来说比较快，但是支持的feature少，不支持captureGroups，各种引用等；而NFA从正则表达式开始，不断读入字符，并尝试匹配当前正则。如果不匹配，则吐出字符并重试。通常它的速度比较慢，最优的时间复杂度是Polynomial，worstcaseexponential。但是NFA支持的特性更多，所以在大多数编程场景下（包括java、js），我们面对的都是NFA。以下面的表达式和文本为例，text='aftertonight'regex='to(nite|nighta|night)'根据匹配NFA时的正则表达式匹配文本，从t开始匹配a，失败，继续直到文本中的第一个t，然后比较o和e，失败，正则表达式回退到t，继续直到文本中的第二个t，然后o匹配文本中的o，继续，正则表达式有公式后的三个可选条件，依次匹配，第一个不匹配，第二个、第三个匹配，直到匹配。在DFA匹配中，它使用文本匹配正则表达式，从a开始匹配t，直到第一个t匹配正则t，但是e匹配o失败，继续直到文本中第一个t有两个ts匹配正则t，则o匹配o，当n发现正则中有三个可选匹配时，开始并行匹配，直到正文中的g使第一个可选条件不匹配，继续直到最后匹配。可以看出，在DFA匹配过程中，文本中的每个字符只进行了一次比较，没有吐出操作，应该比NFA快。另外，不管正则表达式怎么写，对于DFA来说，文本匹配的过程是一致的，都是从左到右依次匹配文本的字符。因此，DFA在匹配过程中与正则表达式无关，而NFA匹配不同的正则表达式效果相同，匹配过程完全不同。3.回溯说完了引擎，我们再来看看什么是回溯。对于下面这个表达式，相信大家都很清楚它的用意，ab{1,3}c表示中间的b需要匹配1~3次。那么对于文本“abbbc”，根据Part1中NFA引擎的匹配规则，其实是没有回溯的。表达式中的a匹配完成后，b正好匹配到文本中的3个b，然后c发生Match，一气呵成。如果我们将文本更改为“abc”怎么办？无非是少了一个字母b，但是发生了所谓的回溯。匹配过程如下图所示（橙色表示匹配，黄色表示不匹配），步骤1~2应该很容易理解，但是为什么要从步骤3开始，虽然文本中已经有一个b匹配b{1,3},后面会不会把字母c拉出来跟b{1,3}比较？这就是我们下面会提到的正则的贪心特性，也就是说b{1,3}会尽量去匹配最多的字符。在这个地方我们首先知道它必须匹配直到它撞到南墙。这种情况下，在第3步出现不匹配后，整个匹配过程并没有完成，而是像一个栈一样，吐出字符c，然后用正则表达式中的c去匹配文本匹配中的c.因此发生回溯。4.贪婪、懒惰和垄断让我们来看看贪婪模式是什么。以下特殊字符相信大家都知道它们的用法：i．?：告诉引擎匹配前导字符0次或一次。实际上，这意味着前导字符是可选的。二.+：告诉引擎匹配前导字符1次或多次。三.*：告诉引擎匹配前导字符0次或更多次。四.{min,max}：告诉引擎将前导字符匹配min到max次。min和max都是非负整数。如果有逗号而省略了max，则表示max没有限制；如果逗号和max都省略，则表示重复min次。默认情况下，这些特殊字符是贪心的，即会根据前导字符匹配尽可能多的内容。这也解释了为什么在第3部分的例子中，会发生第3步之后的事情。在上述字符后加上问号（？）可以开启惰性模式。在这种模式下，正则引擎尽可能少地重复匹配字符。匹配成功后，会继续匹配剩余的字符串。在上面的例子中，如果把正则改成ab{1,3}?c，匹配过程就变成了如下（橙色匹配，黄色不匹配），可以看出在非贪婪模式下，步骤2在b{1,3}之后？在正则模式中匹配文本b，然后使用c不回溯匹配文本中的c。如果在上面四个表达式后面加上一个加号（+），就会开启独占模式。和贪心模式一样，独占模式会匹配最长的。但是在独占模式下，正则表达式会尽可能匹配字符串，如果匹配不成功，则结束匹配，不回溯。我们以下面的表达式为例，ab{1,3}+bc如果我们使用文本“abbc”来匹配上面的表达式，匹配过程如下图所示（橙色表示匹配，黄色表示不匹配），你可以发现，在第2步和第3步中，b{1,3}+会匹配文本中的两个字母b，结果文本中只留下一个字母c。然后在第4步中，正则表达式中的b与文本中的c匹配，当匹配不到时，不进行回溯，此时整个文本无法匹配正则表达式。如果删除正则表达式中的加号(+)，则匹配整个文本。将以上三种模式的表达式列举如下，五、总结现在回过头来看一下文章开头那个很长的正则表达式。其实，经过简化，就是一个^[allowedcharacterset]+形式的表达式。字符集大小约为250，+号表示至少出现一次。根据上面提到的NFA引擎的贪心模式，当用户输入过长的字符串进行匹配时，一旦发生回溯，计算量会非常巨大。后来采用独占模式，CPU100%的问题也解决了。所以，自己写正则表达式的时候，千万不能马虎。在实现功能的情况下，必须慎重考虑是否会带来性能风险。【本文为专栏作者《阿里巴巴官方技术》原创稿件，转载请联系原作者】点此查看作者更多好文
