[翻译] Cloudflare 在 2019 年 7 月 2 日宕机的技术细节
最近 Cloudflare 的故障接二连三，在 Verizon 引起的 BGP 泄漏导致大部分地区网络离线以后，又因为软件错误导致了大规模 502，紧接着亚太多个 POP 又因为网络故障而降级运行。本文翻译了 Cloudflare 博客发布的关于大规模 502 故障的技术细节。
原文标题：Details of the Cloudflare outage on July 2, 2019
原文作者： John Graham-Cumming
原文链接 https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/
本文由 Sukka 翻译，首发于 Sukka’s Blog
差不多九年前，在 Cloudflare 成立一个月后。那时候 Cloudflare 还是一家规模很小的网络公司，我还是 Cloudflare 的客户、不是 Cloudflare 的员工，有一天告警系统警告我说我的网站 jgc.org 的权威 DNS 下线了。Cloudflare 刚刚开始使用 Protocol Buffer，结果搞砸了 DNS。
我直接就给 Matthew Prince（译者注：Cloudflare 的联合创始人、首席执行官）发了一封「我的 DNS 怎么不见了？」的电子邮件。他回复了一封 非常详细的、技术性的回复。于是我给他回信：
From: John Graham-Cumming
Date: Thu, Oct 7, 2010 at 9:14 AM
Subject: Re: Where's my dns?
To: Matthew Prince
Awesome report, thanks. I'll make sure to call you if there's a
problem. At some point it would probably be good to write this up as
a blog post when you have all the technical details because I think
people really appreciate openness and honesty about these things.
Especially if you couple it with charts showing your post launch
traffic increase.
I have pretty robust monitoring of my sites so I get an SMS when
anything fails. Monitoring shows I was down from 13:03:07 to
14:04:12\. Tests are made every five minutes.
It was a blip that I'm sure you'll get past. But are you sure you
don't need someone in Europe? :-)译者注：这封信大意是对 Cloudflare 开诚布公、公开技术细节的赞赏，并且询问 Cloudflare 在欧洲是否有职位空缺。
From: Matthew Prince
Date: Thu, Oct 7, 2010 at 9:57 AM
Subject: Re: Where's my dns?
To: John Graham-Cumming
Thanks. We've written back to everyone who wrote in. I'm headed in to
the office now and we'll put something on the blog or pin an official
post to the top of our bulletin board system. I agree 100%
transparency is best.译者注：这封信是 Matthew Prince 的回信，大意是 Cloudflare 会回复每一封邮件并认为开诚布公是不可或缺的。
如今，作为规模已经不可同日而语的 Cloudflare 的员工，现在轮到我成为那个写作的人，开诚布公描述我们犯下的错误、造成的影响、和我们是如何解决问题的。
7 月 2 日事故的回顾
在 Cloudflare，我们不断的改进 Cloudflare 管理的 WAF 规则集来应对不断出现的漏洞和威胁。比如两个月前，我们迅速发布了一条用于防御 SharePoint 高危漏洞的规则。Cloudflare WAF 的特征就是能够快速地在全球部署和更新。
在 7 月 2 日，我们在 Cloudflare 管理的 WAF 规则集中部署了一条新的规则。不幸的是，这个规则中包括了一个需要大量回溯查询的正则表达式，导致 Cloudflare 全球网络中负责处理 HTTP/HTTPS 流量的 CPU 性能冗余迅速地耗尽。这直接瘫痪了 Cloudflare 核心代理功能、CDN 缓存功能和 WAF 防御功能。
下图显示了负责处理 HTTP/HTTPS 流量的 CPU，这些 CPU 的使用率一度达到 100%。
这导致我们的客户的网站的访客会看到 502 错误页面。这个 502 页面是由前置的 Cloudflare Web Server 生成的。分配给 Cloudflare Web Server 的 CPU 核心仍然可用，但是他们无法获得后端的 HTTP/HTTPS 流量。
我们知道这对我们的客户的严重影响，我们对此感到非常羞愧。甚至在我们处理这一事故时，我们的修复操作甚至影响了我们自己内部的运营系统。
如果您是我们的客户，那么这一次事故将会是令人沮丧、导致难以置信的压力和灾难性的后果。对于我们来说，更令人沮丧的是我们已经 连续六年没有发生过这种全球性的宕机事故 了。
译者注：2013 年，Cloudflare 一条错误的 DDoS 流量清洗规则导致所有边界路由器宕机，进而导致 Cloudflare 的路由宣告中断、Cloudflare 从互联网上脱离。
这条导致 CPU 耗尽的 WAF 规则中的正则表达式如下，这是一条会引起大量回溯的正则表达式：
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))译者注：在译者翻译本文的时候，这条正则表达式甚至险些引起了译者的编辑器的崩溃。。。
虽然很多人都对这个表达式非常感兴趣（我们下面将会对这个表达式进行分析），但是 Cloudflare 为什么会宕机整整 27 分钟显然比正则表达式要重要得多。现在让我们介绍导致宕机的一系列事件和这些事件是如何使得我们无法快速介入解决的。如果你想了解关于正则表达式回溯的详细内容，你可以前往本文结尾的附录。
都发生了些什么
本篇文章所有的时间都是 UTC，现在让我们从头开始。
下午 13 时 42 分，一名在 Firewall 团队工作的工程师利用自动系统部署了一条对 XSS 检测规则的改动。这生成了一个「变动申请」的工单。我们使用 Jira 来管理这些工单，截图可以在下文中看到。
我们使用了一个综合测试系统，通过外部流量测试 Cloudflare WAF（我们会执行数百个这样的测试）的功能是否正常。变动部署三分钟以后，PagerDuty 立刻丢出了第一个告警，提示 WAF 存在问题；紧随其后的是更多的端到端测试失败的告警、大量 502 错误告警、全球范围的流量下降告警，以及我们位于全球各个城市的许多 POP 的 CPU 飙升提示信息。
译者注：PagerDuty 是一家位于加利福尼亚州旧金山的云计算公司，为 SaaS 平台提供告警响应平台服务。
我还在开会的时候，其中一些警告推送到了我的手表上。我立刻一跃而起离开了办公室，在我回到办公桌的路上是我撞见了一位部门工程师，他告诉我我们已经失去了全球 80% 的流量。我立刻前往 SRE 那里，团队们立刻开始进行调试。在宕机刚刚开始的时候，有人猜测这是某种我们以前从未见过的某种攻击。
Cloudflare 的 SRE 团队遍布全球各地以确保全天候都有团队成员在线。一般情况下，警报都仅出现在局部地区范围内、并且是由非常具体的问题导致的。这些问题我们每天都在内部的面板中进行监视、并且予以应对。但是这次的告警信息表明发生了非常非常严重的事情，SRE 立刻宣布发生了一起涉及到系统架构的 P0 事件。
当时位于伦敦的工程师团队正在我们的办公场所里听取技术讲座。讲座立刻被打断了、所有人立刻到大会议室集合，其他未到场的人则通过电话会议参与进来。我们需要所有团队成员立刻集结。
下午 14 时，我们定位到问题源于 WAF 组件，攻击的可能性立刻被排除了。负责性能的团队获取了实时的各个组件的 CPU 消耗数据，并通过 strace 确认了 WAF 组件是罪魁祸首。另一个团队看到了 WAF 报错的错误日志。下午 14 时 02 分，我提出建议使用 Global Kill 缓解问题时，整个团队的人都在看着我。Global Kill 是内置于 Cloudflare 的一个安全机制，可以快速地在全球范围内禁用某一个组件。
但是，对 WAF 组件执行 Global Kill 并非那么容易，因为有东西在阻碍着我们。我们使用的是自己的产品 Cloudflare Access 来对我们内部控制面板进行身份验证，现在这个产品已经瘫痪了。我们现在甚至不能访问其它内部的服务，比如我们的 Jira 和我们的构建系统。我们不得不使用一个不常用的旁路机制绕过限制（不过当故障结束后，另一个问题因此浮出水面）。不过终于，在下午 14 时 07 分我们终于对 WAF 组件执行了 Global Kill，并且在下午 14 时 09 分时，流量水平和 CPU 占有率回到了常态。Cloudflare 其它组件仍在正常工作。
接着我们开始着手于恢复 WAF 组件的功能。由于这次故障，我们非常谨慎地挑选了一个 POP。在将企业客户的流量从这个 POP 迁移走以后，我们对这个 POP 进行了两次灰度测试，确认了问题的来源和回滚是否能解决问题。
在下午 14 时 52 分，我们终于可以百分之百确认故障发生的原因并且部署了一个修复补丁。接着我们在全球范围内重新启动了 WAF 组件。
Cloudflare 内部的运营和管理机制
Cloudflare 拥有一支专门负责管理型 WAF 规则集的工程师团队。他们不断致力于改善检测率、降低误报、在新的威胁出现时做出反应。在过去的 60 天里，这个团队提交了 476 个变更请求，平均每 3 小时就有一个。
通常情况下，这些规则将会使用类似于 Simulate 的模式部署。真实客户的流量会经过新的规则的审查，但是我们不会拦截触发新的规则的流量。我们通过这种方法测试规则的有效性和误报率。但是，即使在 Simulate 模式下，规则也需要被执行，而在本次故障中，规则刚好包含了一个会大量消耗 CPU 的正则表达式。
正如你所见，一个 Change Request 包括一个部署计划，一个回滚计划和一个指向此类部署的内部标准操作流程（SOP）的链接，其中修改 WAF 规则的 SOP 允许在推送到全球进行部署。这与我们在 Cloudflare 发布其它软件不同。对于其他软件，Cloudflare 会先在内部网络中的测试 POP 进行测试、然后在部分地区进行灰度测试、最后推送给大量用户公测、最后才会在全球进行部署。
我们的软件发布版本的工作流大概像是这样：我们内部使用的是 BitBucket，当工程师推送一个提交以后，TeamCity 会进行一次持续集成，当构建通过以后提交就会分配 Reviewer。一旦这个提交通过了代码 Review，会重新执行一次单元测试。
如果构建和测试都通过了，我们会在 Jira 生成一个 Change Request。变更必须由相关的部门主管或者技术主管审核通过。一旦通过，这些变动会部署到我们内部的 POP——DOG PIG 和 Canaries。
译者注：TeamCity 是 JetBrains 于 2006 年 10 月 2 日推出的基于 Java 的构建管理和持续集成服务端软件。Jira 是 Atlassian 开发的一个缺陷跟踪管理系统，为针对缺陷管理、任务追踪和项目管理的商业性应用软件。Canary 意为金丝雀，在 19 世纪末，煤矿工在下井之前会先往井中投入一只金丝雀检测煤矿的瓦斯浓度。
DOG 和 Cloudflare 位于全球的 POP 一样，只不过位于 Cloudflare 内部网络之中，只被 Cloudflare 的雇员所使用。我们使用这个 POP 可以在代码被部署到生产环境之前就发现问题。
如果 DOG 通过了测试，我们会把代码部署到 PIG，这是一个用于小范围测试的 POP。我们将一部分免费用户的流量引入这个 POP 用于对新代码的测试。
如果小范围测试通过了，我们会在 Cloudflare 全球网络上选定三个 POP 作为 Canary POP，此时无论免费用户还是付费用户的流量都有可能通过 Canary POP，我们用这种方式对我们的新代码进行最后一次测试。
一旦 Canary 测试通过，代码就可以上线了。整个 DOG => PIG => Canary 的流程可能需要数小时甚至数天，具体取决于改动的类型。Cloudflare 的网络和客户的多样性使得我们能够在将新版本的软件部署到全球之前能够彻底地测试我们的代码。但是，为了能够快速地应对所有威胁，WAF 在整个工作流的设计中就没有使用这种测试流程。
WAF 威胁
在过去的几年中，我们看到各种常见的应用程序中出现井喷的高危漏洞。这是因为可用的软件测试工具越来越多，例如模糊测试。
比较常见的一种概念验证是在 GitHub 上快速发布，以便于运行和维护应用程序的团队可以进行测试以确保足够的保护。因此 Cloudflare 必须能够尽快的对新的攻击做出反应，以便让我们的用户能够有机会修补他们的软件。
我们今年 5 月份针对 SharePoint 的高危漏洞发布 WAF 规则就是一个很好的例子。在发布 CVE 以后，我们看到了大量试图入侵使用 SharePoint 的我们的客户的请求。我们的团队不断监控这些新的威胁并编写规则来为客户缓解威胁。
导致上周二宕机的 WAF 规则针对的是跨站攻击（XSS）。近年来，这种类型的攻击也在急剧增加。
托管型 WAF 规则更改的流程要求在全球范围内部署规则改动之前必须通过 CI 的测试。上周二部署的规则也通过了测试，在下午 13 时 31 分时团队中的工程师合并了 Pull Request。
在下午 13 时 37 分，TeamCity 编译并测试新的规则，并亮了绿灯。WAF 单元测试会测试 WAF 的核心功能，在单元测试运行以后，会通过大量 HTTP 请求测试 WAF 的拦截率和误报率。但是测试中没有监测 CPU 使用率。
测试就这样通过了。然后在下午 13 时 42 分，TeamCity 开始执行了自动部署。
QuickSilver
由于需要 WAF 规则来快速应对紧急的威胁，我们开发了一套内部的 QuickSilver Key-Value 数据库才存储和部署规则。我们可以在几秒钟内在全球范围内更改数据。我们的客户通过 API 或者操作面板更改配置时也都在使用同一种技术。这是我们能够快速响应更改的支柱。
我们从未讨论过我们的 QuickSilver。我们以前使用的是 Kyoto Tycoon，但是在我们的系统中遇到了瓶颈，于是我们开发了自己的 KV 数据库并部署在超过 180 个数据中心之中。我们使用 QuickSilver 储存和更新用户的配置更改、更新 WAF 规则、分发 Cloudflare Workers 之中的 JavaScript 代码。
不论是点击操作面板中的按钮和开关或者通过 API 调用，在全球范围内生效更改只需要几秒钟的时间。我们的客户非常喜欢这种快速生效的配置。对于 Cloudflare Workers 而言则是快速地在全球部署代码。平均而言，QuickSilver 每秒可以分发部署 350 次更改。
通常情况下这种速度是好事。因为这意味着当你启用某项功能或者清除 CDN 缓存的时候，你知道你的更改将会在全球范围内迅速生效。Cloudflare Workers 的代码也会使用相同的速度分发。
然而在这种情况下，这种速度意味着新的 WAF 规则只需要几秒钟就会部署到全球。你可能有注意到 Cloudflare 的 WAF 使用了 Lua。实际上，Cloudflare 在生产环境中 大量的使用 Lua。Lua 内部使用的是 PCRE，使用回溯法进行匹配，并且没有机制防止表达式失控。更多的细节我们会在下面进行讨论。
部署规则之前发生的所有事情都是「非常正确地」完成的——提交 Pull Request、进行持续集成、生成符合标准流程变更请求、并在全球范围内执行部署。
什么地方出了问题？
如上所述，我们每周都要部署几十条新的 WAF 规则，并且我们本来有许多系统可以防止该部署产生副作用。因此，当事情出错的时候，通常不会只有一个原因。如果我们只满足于找到一个原因，那么真正的大问题可能会被掩盖。这是我们找到的导致 Cloudflare 的 HTTP/HTTPS 业务宕机的几个漏洞：
- 一个工程师写出了一个很容易回溯的正则表达式
- 在之前对 WAF 重构的时候，错误地删除了一个保护 CPU 不被过度使用的保护机制
- 正在使用的正则表达式引擎不能保证在复杂的表达式下的可靠性
- 我们的测试套件没有检查 CPU 消耗
- 我们针对 WAF 的标准操作流程允许 WAF 规则变动快速部署到生产环境、即使这个变动并没有那么紧急可以进行阶段测试
- 执行回滚需要构建 WAF 两次
- 全球流量下降的警报用时很长时间才发出
- 我们并没有及时地更新我们的 StatusPage
- 由于 WAF 宕机，我们甚至无法访问我们的内部系统
- 我们的客户无法通访问操作面板或者 API，因为这些东西被部署在同一套服务上
上周二以后我们做了什么
首先，我们立刻停止了所有的 WAF 规则发布工作，并且我们立刻开始着手于
- 重新引入被删除的 WAF CPU 保护模块（已完成）
- 手动检查 Cloudflare 现有的 3868 条规则，查找可能存在的过度回溯（已完成）
- 为 WAF 单元测试引入性能分析（已完成）
- 切换到使用 re2 或者 Rust 的正则表达式引擎（预计在 7 月 31 日之前完成）
- 更改我们的标准操作流程，采用和 Cloudflare 其它软件版本相同的阶段部署方法，但同时保留了对于 WAF 规则的紧急部署
- 提供了紧急措施，能够让 Cloudflare 的 API 和操作面板可以脱离 Cloudflare 基础设施运行
- 自动更新 Cloudflare 的 StatusPage
长远地来看，我们终将抛弃 Lua 用作 WAF。我们正在移植 WAF 到我们新的 Firewall Rule 上。
结论
这对我们的客户和团队来说是一个很不安的事故。我们尽可能快的做出反应，并正在纠正我们流程中的缺陷。我们通过了更换我们的底层引擎以避免问题。
我们对这次宕机感到非常羞愧，并对我们产生的影响表示抱歉。我们相信这种全球性的宕机不会再发生了。
附录：关于正则表达式回溯
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))如果要了解这个正则表达式是如何把 CPU 榨干的，你首先要了解正则表达式引擎的工作原理。重要的部分是 .*(?:.*=.*)。(?: 和 ) 构成了一个非捕获组（即这个括号之内的表达式作为一个独立的表达式存在）。
因此，在讨论 CPU 为什么会耗尽时，我们可以将这部分 pattern 忽略掉，并最终简化成 .*.*=.*。这个表达式看起来非常简单，但是在「现实世界」之中（比如我们的 WAF）要求正则表达式引擎 匹配任何事物后面的任何东西 都可能导致灾难性的回溯。
在正则表达式之中，. 表示一个字符，.* 表示零个或者尽可能多的任意个数的字符（我们称之为贪婪匹配）。因此 .*.*=.* 就要求匹配尽可能多的字符、然后再尽可能匹配字符，找到一个 = 然后再匹配更多的字符。
考虑一下拿 x=x 作为 .*.*=.* 的测试字符串。= 之前的 .*.* 可以匹配到 x（其中一个 .* 匹配到 x，另一个 .* 匹配到零个字符），然后 = 之后的 .* 可以匹配到另一个 x。
但是这需要整整 23 步才能实现这个匹配的过程。因为 .* 是贪婪的，.*.*=.* 在匹配 x=x 的时候，第一个 .* 会直接匹配掉整个 x=x 的字符串；然后引擎开始考虑紧随其后的 .*，此时字符串中已经没有剩余的字符了（第一个 .* 把整个字符串全部匹配了），于是第二个 .* 匹配到了 0 个字符；接着引擎开始匹配 =，但是剩余的字符串里什么都没有，因此没法匹配到 =。匹配失败了。
这个时候正则表达式引擎开始回溯。它找到第一个正则表达式中出现的第一个 .*（在这个例子中就是正则表达式的开头），然后让第一个 .* 减少匹配一个字符（此时匹配到的是 x=）；这样第二个 .* 就会匹配到 x；但是当引擎试图匹配 = 时，匹配还是失败了。
于是正则表达式引擎再次回溯。这一回第一个 .* 匹配到的还是 x=，但是这一回，让第二个 .* 减少匹配一个字符（此时第二个 .* 匹配到零个字符）。但是这并没有用，x= 被第一个 .* 匹配过了，因此引擎在匹配 = 时还是失败了。
这一回正则表达式引擎回溯后让第一个 .* 匹配到 x，但是这时第二个 .* 开始贪婪的把 =x 匹配掉。你已经可以猜出来接下来会发生什么了。正则表达式引擎还得回溯一遍。
现在第一个 .* 依旧匹配 x，不过第二个 .* 减少匹配一个字符匹配到 =。正如你猜的那样，匹配依然会失败。
只有到第一个 .* 匹配到 x，第二个 .* 匹配零个字符时，正则表达式引擎才有可能匹配成功。是的，这需要 23 步。 我们使用 Perl Regexp::Debugger 展示了正则表达式引擎是如何回溯的：
那么，如果 x=x 变成了 x=xx，这就会需要 33 步。然后 x=xxx 需要 45 步。这可不是线性增加的。我们花了一个图表展示 = 后面 x 的个数和需要回溯的次数之间的关系。
当 = 后面由 20 个 x 时需要 555 步。甚至，如果没有 x=（即字符串里只有 20 个 x），那么引擎需要 4067 步才能发现匹配失败。
这个视频展示了正则表达式引擎如何花费 555 步匹配 x=xxxxxxxxxxxxxxxxxxxx：
很明显的，随着输入大小的增加，匹配用时会超线性增长，而且，如果正则表达式越复杂，情况可能就越糟糕。比如 .*.*=.*; （加了一个分号）可能会被用来匹配 foo=bar;。
这一回回溯将会变得非常具有灾难性。如果拿 x=x 去匹配需要花费 90 步而不是 23 步才能发现无法匹配，如果 = 后面有 20 个 x 那么需要 5353 步。我们画了一张新的图表，注意 Y 轴数字的数量级。
下面这个视频完整地展示了 x=xxxxxxxxxxxxxxxxxxxx 是如何花费 5353 步发现匹配失败的。
如果使用懒惰匹配法（匹配尽可能少的字符）而不是贪婪匹配法在这种情况下有助于减少回溯量。如果把正则表达式改成 .*?.*?=.*?，那么匹配 x=x 只需要 11 步而不是 23 步。因为紧跟在 .* 之后的 ? 告诉正则表达式引擎要匹配尽可能少的字符。但是懒惰匹配法并不能完全解决回溯问题。在 .*.*=.*; 这个正则表达式之中，回溯次数完全没有减少。
自 1968 年以来 Ken Thompson 写了一篇题为「编程技巧：正则表达式搜索算法」的论文以来，人们就找到了这个问题的解决方法。这篇论文描述了一种将正则表达式转译为 NFA（非确定性有限自动机）的机制，然后使用一种算法在 NFA 中跟踪状态的转换。这种算法在时间和匹配字符串大小之间存在的是线性关系。
Thompson 的论文虽然并没有讨论 NFA，但是线性时间算法已经解释得很清楚了，并且提出了一个为 IBM7094 生成的汇编语言代码的程序 ALGOL-60。这个实现可能是神秘的，但是算法并不是。
这张图展示了按照 Thompson 的算法绘制 .*.*=.* 的流程图。
0 有 5 个从 0 开始的状态，三个循环分别开始于状态 1 2 3。这三个循环对应表达式中的三个 .*。状态 4 是结束状态，到达这个状态表明匹配成功。
要了解如何使用这种状态图来匹配 .*.*=.*，让我们从字符串 x=x 开始，程序从状态 0 开始执行。
这个算法的关键在于状态机可以同时处于多个状态
甚至在没有读取任何输入之前都会转换到状态 1 和 2，如图所示。
根据这张图我们也能意识到它在考虑 x=x 时会发生什么。x可以通过总状态 1 转换回状态 1 来匹配，或者通过状态 2 转回状态 2 来进行另外的匹配。
所以匹配完第一个 x 以后，状态仍为 1 和 2，但是由于需要 = 号，状态 3 和 4 仍不可达。
接下来算法会考虑字符串 x=x 中的 =。这个 = 可以通过之前的两个循环从状态 1 和 2 转回状态 1 和 2，但是可以匹配到算法中的 = 并且可以将状态 2 转换为状态 3，滨海最终到达 4，如图所示。
接下来算法考虑字符串中最后一个 x，从状态 1 和 2 开始，相同的转换可以到达状态 1 和 2，状态 3 开始可以通过右部的匹配回到状态 3。此时 x=x 的每个字符都考虑到了，并且算法已经到达状态 4。每个字符都只被处理一次，因此处理次数是线性增长的。并且这种算法不需要回溯。
甚至早在匹配完 x= 以后状态 4 就已经达到，算法可以在不考虑最后一个 x 时即可匹配完成并退出。