你写了一个正则表达式，5个字符，匹配成功。但在这0.003秒里，你的CPU刚刚执行了超过10亿次状态跳转——而你一无所知。
这不是魔法，是1968年就埋下的设计遗产。Ken Thompson在那年发明了Thompson构造法，把人类可读的字符模式，编译成一种叫NFA（非确定性有限自动机）的图结构。你的a(b|c)*d看起来人畜无害，引擎看到的却是一张分叉路网络：每个节点都可能同时走向多个出口。
NFA的"非确定性"是个双刃剑。它能并行探索所有匹配路径，但模拟这种并行需要昂贵的计算成本。于是现代引擎普遍采用子集构造算法，把NFA转换成DFA（确定性有限自动机）——每个输入字符只触发一次状态转移，时间复杂度压到O(1)。代价是状态数可能指数级膨胀：你的5字符模式，DFA状态可能上百。
回溯陷阱：90%程序员踩过的性能雷
但Python、Java、JavaScript、Ruby、PHP这些主流引擎，走的不是DFA路线。它们用回溯：一条路走到底，不通就退回来换条道。这方案写起来简单，却藏着一颗定时炸弹。
问题出在嵌套量词和重叠字符的组合。模式(a+)+b匹配字符串aaaaaaaaaaX时，引擎要穷举所有可能的a分组方式。10个a产生约1000条路径，20个a超过100万条，30个a突破10亿条。输入长度每加1，计算量翻倍。
这就是ReDoS（正则表达式拒绝服务攻击）：一个精心构造的30字符输入，能让CPU满载运行数小时。
2016年Cloudflare的一次 outage，源头正是这样一个正则。安全研究员在Stack Overflow的分析帖被点了超过4000次赞——因为太多人见过生产环境被正则拖垮的惨状。
你的正则是一门编程语言，只是没有IDE帮你debug
我们习惯了正则的"声明式"外表：写规则，得结果。但引擎内部，它正在被编译、优化、执行，和任何程序没有本质区别。区别在于，你写JavaScript时有ESLint，写SQL时有执行计划分析器，写正则时却只有——运气。
回溯引擎的复杂度分析是个未完全解决的难题。学术界有若干充分条件可以判定安全模式，但必要条件还在研究中。换句话说，确认一个正则不会ReDoS，有时比证明它会更难。
一些团队开始用RE2这类DFA优先的引擎替代默认实现。Google开源的RE2明确拒绝回溯，牺牲部分高级特性（如反向引用）换取线性时间保证。GitHub的代码搜索、Gmail的过滤器，底层都是这类方案。
但迁移成本不低。JavaScript开发者没法换引擎，只能依赖lint工具（如eslint-plugin-redos）做静态扫描。2023年的一项研究显示，npm前1000个包中仍有12%包含潜在ReDoS模式——而维护者大多不知情。
防御策略：不是不写正则，是知道自己在写什么
工程上的妥协方案是输入截断和超时熔断。Cloudflare在事故后给WAF规则加了长度限制：超过一定字符的匹配请求直接拒绝。这治标不治本，但有效。
更根本的做法是模式审查。避免嵌套量词（(a+)+）、避免量词修饰重叠字符类（(\d+)+$）、用占有量词（++、*+）禁止回溯——如果引擎支持的话。Java和Python的部分版本有，JavaScript没有。
正则可视化工具能帮上忙。Debuggex、RegExr这些网站把NFA状态图画出来，让你看见引擎眼中的世界。一个看起来"应该很快"的模式，展开后可能是张蜘蛛网。
视频作者用动画演示了Thompson构造的每一步：字符变节点，括号变分支，量词变循环。这种可视化1968年只能靠纸笔画，现在浏览器里就能跑。技术民主化的好处是，你终于有机会理解自己写的每一行代码——如果愿意花时间的话。
下次写正则前，你会先想想它可能被喂进什么输入吗？还是说，"匹配成功"四个字，就足够让你按下commit键了？
热门跟贴