微信号:gh_8590062d6d9b

介绍:原创/翻译的编程小知识, 目标是每篇文章只需一分钟时间阅读, 利用碎片时间学习技术

一次正则表达式回溯导致的Stack Exchange宕机

2016-07-21 13:08 Yu Hao

昨天(2016.07.20), Stack Exchange 网站发生了一次34分钟的宕机。 事后, 他们发了一篇文章分享这次宕机的原因和解决方法。

34分钟中, 10分钟用于找出问题在哪里, 14分钟用于修复bug, 10分钟用于恢复服务

宕机的直接原因是, 一个格式不正常的问题, 导致了正则表达式引擎占用了极高的CPU。 而这个问题出现在首页, 使得首页的显示变得很慢。 而后台的健康检查(health check)以首页为准做负载均衡, 最终导致服务器不正常。

出错的正则表达式是^[\s\u200c]+|[\s\u200c]+$, 用来去掉字符串的开头或结尾的连续空白字符(\u200c 是一个 Unicode 空白符)。 复现问题的最小正则表达式是 \s+$. 而导致错误的问题中, 在一行注释里, 包含有大约20000个连续空白字符。

当字符串包含有20000个连续空白符, 但不是在字符串结尾的时候, 正则表达式引擎就会从第一个空白符开始匹配, 匹配到第20000个, 发现后一个字符既不是空白字符, 又不是字符串结尾, 于是回头从第二个字符开始匹配, 匹配19999个字符后, 同样的结果, 再回头从第三个字符开始, 以此类推。 这就是正则表达式的回溯(back tracking)机制。 “检查一个字符是否是空白字符”一共需要20000+19999+19998+…+3+2+1 = 199990000次, 这并不是最经典的正则表达式回溯灾难, 但已经足够了。

这次宕机的解决方法? 用检测子字符串代替了正则表达式。



“阅读原文”指向原博文,或直接访问 http://stackstatus.net/ 最新的一篇即是。

 
一分钟的编程知识 更多文章 常量0是几进制的数? int main()还是void main() 为什么计算机启动叫做boot? 自然界的二叉树欣赏 Vim学习的个人心得
猜您喜欢 段子:别跟我谈梦想,我的梦想是不上班! 视觉直观感受 7 种常用排序算法 《近匠》透镜:代码级定位,让App性能监控更从容 写给程序猿的把妹指南:自身建设篇 深入理解PHP7之zval