Cloudflare HTML 解析器的十年演化史(一)
原文链接：https://blog.cloudflare.com/html-parsing-1/ 很多人第一反应是：浏览器不是都有现成的 HTML 解析器吗？直接用不就好了？ 问题在于，Cloudflare 的场景和浏览器完全不同。 浏览器解析 HTML 的目标是构建一棵 DOM 树，供渲染引擎使用。整个文档下载完之后，交给解析器，慢慢建树，内存够用就行。浏览器甚至可以边解析边让用户等，因为用户本来就在等页面加载。 Cloudflare 的场景是：数据流从源站流过来，流经 Cloudflare 的边缘节点，流向用户。边缘节点需要在数据经过时实时改写 HTML，改完之后继续往前传。整个过程中： 这就是流式 HTML 改写器（Streaming HTML Rewriter）的设计目标：数据流进来，边解析边改，改完边往外发，全程缓冲的数据尽可能少。 2010 年，Cloudflare 想给客户提供一个功能：自动混淆页面上的邮件地址，防止爬虫收集。思路很直接——找到页面里长得像邮件地址的字符串，把它编码，再注入一段 JavaScript 在浏览器端解码还原，对真实用户透明，但爬虫拿不到明文地址。 听起来很简单，实际上第一个坑就来了：数据是分包到达的。 网络传输的数据按包分割，你无法控制一个邮件地址 解决方案是把正则表达式转换成状态机（finite automata），用工具 Ragel 来生成高效的状态机代码。状态机的好处是可以在字节流上增量执行：处理完当前包之后，保存当前状态，等下一个包来了接着跑，不需要缓冲整个文档。 但邮件地址不是孤立存在的——它可能出现在 HTML 注释里，可能出现在 2011 年，Cloudflare 又想加 HTML 压缩（minification）功能。他们引入了一个叫 jitify 的外部库。问题出现了：jitify 有自己的 HTML 处理规则，和已有的邮件混淆模块的规则不兼容。两个并行运行的"解析器"，各自有各自的状态，各自有各自的 bug，还会产生组合 bug。 这是临时方案堆叠的经典结局：每加一个新功能，系统就多一层脆弱性。 到 2016 年，工程师们意识到必须打破这个循环，彻底重写，基于 HTML5 规范从零构建一个真正的流式解析器。这个项目最终产出了 LazyHTML（已开源：https://github.com/cloudflare/lazyhtml ）。 构建过程中踩了几个有意思的坑，每一个都值得展开讲。 HTML5 规范对 HTML 解析的定义方式，是一个词法分析器（tokenizer）+ 一个树构建器（tree builder）协同工作的状态机。关键在于：树构建器会反过来驱动词法分析器——词法分析器的当前状态，取决于已经构建好的 DOM 树的状态。 换句话说，你不构建 DOM，就没办法正确地切分 token。 这也是为什么大多数 HTML 解析器都选择把整个文档读完，然后一次性建树——流式解析和规范要求之间天然存在矛盾。 Cloudflare 的解法是引入一个"树构建器反馈模拟器"（Parser Feedback Simulator）。它不真正建树，但它跟踪足够多的上下文信息，让词法分析器相信它在和一个正常的树构建器交互。经过在大量真实页面上的测试，这个模拟器能正确处理互联网上绝大多数写得乱七八糟的页面。 这个思路来自对已有开源 HTML5 解析器 parse5 的研究，部分测试用例也回馈给了上游项目。 流式改写 HTML 还有一个棘手问题：字符编码。HTML 文档可以用 UTF-8、GBK、Latin-1 等各种编码，而且编码信息可能藏在文档里面（比如 如果要先确认编码再处理，就需要缓冲大量数据，违背了流式处理的初衷。如果解码之后再处理，还要面对不同编码的字节序问题，实现复杂度极高。 工程师发现了一个关键性质：HTML 规范允许的所有字符编码（除了 UTF-16 和 ISO-2022-JP），都是 ASCII 兼容的。也就是说，所有 ASCII 字符在这些编码中的字节表示与纯 ASCII 完全相同，非 ASCII 字符的字节值一定在 ASCII 范围之外。 而 HTML 语法中，所有有意义的边界字符（ 做法是：对 UTF-16 文档做嗅探并直接跳过（这类文档在现实中不到 0.1%）；对其他文档，原样处理字节流，只操作 ASCII 范围内的 token 边界。 这个洞察直接避免了解码和重编码的开销，既提升了性能，也规避了一大类潜在的编码相关安全漏洞。 规范中要求把 U+0000（NUL 字符）替换为 U+FFFD（替换字符）的条款，LazyHTML 选择了静默忽略。因为 U+FFFD 是非 ASCII 字符，在不同编码下字节表示不同，不知道编码就没法正确处理。而且使用"胖指针"（length + pointer）而非 C 风格 null 结尾字符串之后，NUL 字符本身也不会带来安全问题。 当一个 HTTP 响应的 Cloudflare 的实测数据给出了一个令人绝望的答案：大约 25% 声称是 原因很简单：PHP 的默认 如果 Cloudflare 的 HTML 改写器对所有 工程师在代码里留了一段注释，坦诚记录了这个痛苦的现实（原文大意）： 最终形成的内容嗅探逻辑要检测：二进制数据、JSON、AMP 页面、XML（许多 XML 文档也错误地标注为 这是规范与现实之间鸿沟的典型写照。 HTML 解析的一个高频操作是比较标签名：当前遇到的标签是 朴素实现是逐字节比较。对于短标签名（大多数 HTML 标签名都很短）来说，这没什么问题，但这是一个在每个 token 上都要执行的操作，在 Cloudflare 的流量规模下，积少成多。 LazyHTML 用了一个精妙的哈希方案： 所有标准 HTML 标签名只包含小写 ASCII 字母和数字 1-6（用于 这样，任意一个标准标签名都能被编码成一个唯一的 64 位整数，标签名比较就变成了一次整数相等比较。 这个哈希甚至不需要额外的遍历——可以在解析标签名的同时，逐字节更新哈希值，完全零额外开销。 有一个小陷阱：32 种字符里必须用到 经过以上所有设计权衡，LazyHTML 问世。它通过了 HTML5 规范官方测试套件，团队还把几处规范描述中的歧义和可简化之处回馈给了规范本身。 在 2016 年 9 月的基准测试中，以改写 HTML5 规范文档本身（7.9 MB 的 HTML 文件）为测试用例，对比了同时期流行的 HTML 解析器（仅 tokenization 模式，不构建 AST），LazyHTML 的速度比其他解析器快了约一个数量级。 在对 HTTP Archive 中 238 万份真实 HTML 文档的测试中，LazyHTML 没有在任何一份文档上崩溃。约 0.2% 的文档超出了缓冲区限制——这些文档实际上是 JavaScript、RSS 或其他内容，只是被错误标注成了 回顾这整段历程，有几个模式一再出现： 特殊场景催生专用方案，专用方案积累成负担。 邮件混淆、HTML 压缩，每个功能都带着自己的解析逻辑和边界处理，最终形成了一堆互相干扰、难以维护的代码。这种债务没有办法靠局部修修补补偿还，只能重写。 规范描述的是理想，现实是混乱的。 约束是创造力的来源。 不能用 DOM，催生了 Parser Feedback Simulator；不能做字符编码解码，促使工程师发现了 ASCII 兼容性这个性质；内存极度受限，逼出了 5 位哈希标签名比较。如果没有这些约束，LazyHTML 就只是又一个普通的 HTML 解析器。 第二篇博客将描述 LazyHTML 的下一代继承者：LOL HTML——一个用 Rust 写成、支持 CSS 选择器 API 的流式改写器，也就是今天 Cloudflare Workers 本文基于 Cloudflare 工程博客系列文章第一篇，梳理了 Cloudflare 从 2010 年起构建 HTML 流式解析器的完整历程。这不是一篇"又一个 HTML 解析器"的介绍，而是一个工程团队在极端性能约束下，反复与现实妥协、不断重建的真实故事。
为什么 Cloudflare 需要自己的 HTML 解析器
v0：从一个"简单"的需求开始
user@example.com 会不会被切成两个包——前半个包里是 user@exam，后半个包里才是 ple.com。如果只处理当前包，就会漏掉跨包的邮件地址；如果把所有包缓冲起来再处理，延迟就不可接受了。<script> 标签里，这些地方的邮件地址不应该被混淆。于是工程师在状态机里加了跳过注释和标签的逻辑。这是 Cloudflare HTML "解析"能力的起点，虽然那时还远远谈不上是一个解析器。v1：从头来过，做一个合规的 HTML5 解析器
坑一：HTML5 解析规范要求有 DOM，但我们不能建 DOM
坑二：字符编码——绕开解码，一个聪明的洞察
<meta charset="...">），需要读了 1KB 内容之后才能确定。<、>、"、= 等）全部是 ASCII 字符。这意味着：只要不修改非 ASCII 内容，完全可以在不知道文档编码的情况下安全地解析和改写 HTML。坑三：Content-Type 是谎言，25% 的流量声称是 HTML 但并不是
Content-Type 是 text/html 时，你会认为里面是 HTML，对吧？text/html 的响应，实际上根本不是 HTML。Content-Type 就是 text/html。大量开发者写了返回 JSON 的接口、输出图片的脚本，却从来没有手动设置 Content-Type，于是服务器就用默认值把这些响应都标注成了 text/html。text/html 响应都盲目处理，后果是：把 JSON 响应当 HTML 解析时，可能错误地把 a<b 识别成一个不完整的 HTML 标签，然后在末尾注入脚本代码，直接把 API 响应破坏掉。亲爱的后来者，我也不喜欢这个 hack，但写这段代码的时候互联网是个糟糕的地方。大量网站用 PHP 默认的
Content-Type: text/html 来返回 JSON API 响应、私钥、二进制图片……我们只能在正式解析之前，先确认第一个非空白字符是不是 <，来提高我们猜对的概率。text/html）……整个检测流程复杂到可以画成一张相当大的流程图。坑四：标签名比较——一个用 5 位哈希换来的单指令比较
<a> 还是 <div> 还是 <script>？<h1> 到 <h6>）。这意味着只需要 32 个不同的字符值就能覆盖所有可能。用 5 位来编码每个字符，一个 64 位整数可以容纳 64 ÷ 5 = 12 个字符——而所有标准 HTML 标签名都不超过 12 个字符（最长的是 blockquote，9 个字符）。00000 这个 5 位值，如果字母 'a' 被编码为 00000，那么 ab 和 aab 的哈希值就会相同（前导零不影响整数值）。解决方法也简单：把数字 1-6 编码为 00000-00101，字母从 00110 开始编码。由于 HTML 规范规定标签名的第一个字符必须是字母，不可能是数字，前导零的冲突就被规避掉了。LazyHTML 的最终成绩
text/html（排除两个已知问题广告网络的文档后，这个比例降至 0.03%）。一条演化主线背后的工程教训
Content-Type: text/html 有 25% 在说谎，大量页面的 HTML 不符合规范但浏览器能正常渲染，规范要求的 NUL 字符替换在不知道编码的情况下无法安全实现……每个"按规范来"的方案，都需要一层针对现实世界的适配。HTMLRewriter API 的底层实现。