Cloudflare HTML 解析器的十年演化史(二)

本文是 Cloudflare HTML 解析系列的第二篇。上篇讲了从 2010 年到 2016 年，Cloudflare 如何从一堆临时解析器走向 LazyHTML。这篇从 2017 年接着讲——当 Cloudflare Workers 上线之后，为什么 LazyHTML 不够用了，以及 LOL HTML 如何从架构层面解决这个问题，尤其是它那个把 CSS 选择器转化成虚拟机程序的匹配引擎。

原文链接：https://blog.cloudflare.com/html-parsing-2/

背景：Workers 的出现，让问题变难了

2017 年，Cloudflare 推出了边缘计算平台 Cloudflare Workers。开发者很快意识到，他们也想用上 Cloudflare 内部那套 HTML 改写能力，并且希望通过 JavaScript API 来调用。

当时 Workers 上确实可以做 HTML 改写，用 Cheerio 这类第三方 JavaScript 库。但这些库根本不是为边缘场景设计的——它们需要把整个页面内容缓冲到内存里再处理，延迟高，内存占用也常常超出 Workers 运行时的限制。

那为什么不直接把 LazyHTML 接进来呢？

LazyHTML 在解析性能上是合适的，但它有两个问题直接挡住了路：

第一，API 不友好。LazyHTML 的输出是一个 HTML token 流——它告诉你"现在遇到了一个开始标签"、“现在遇到了一段文本”，具体怎么用由调用方决定。这对内部使用够了，但对开发者来说，他们更习惯 jQuery/Cheerio 那种 CSS 选择器风格的 API：rewriter.on("div.foo", handler)，直接指定选哪些元素，其他的不管。

第二，性能开销不可接受。LazyHTML 是一个"解析-改写-序列化"的流水线，它对整个页面的所有内容都产生 token。在 Workers 场景里，这些 token 需要被包装成 JavaScript 对象传给 V8 引擎（Workers 的运行时），用户代码处理完之后再解包回来送给序列化器。这种在语言边界上来回倒腾的开销，足以把 LazyHTML 在解析层面赚到的所有性能收益全部赔光。

要解决这两个问题，不能在 LazyHTML 上打补丁，需要一个从设计上就考虑到这些约束的新库。这就是LOL HTML（Low Output Latency HTML）的由来。

双解析器架构：最好的优化是"不做"

LOL HTML 最核心的设计决策，是它的双解析器架构。

它内部维护两个解析器，可以随时在二者之间切换：

Lexer（词法分析器）：完整的解析器，对所有内容产生完整的 token 输出——标签、属性、文本节点、注释……应有尽有。

Tag Scanner（标签扫描器）：轻量级的扫描器，只查找开始标签和结束标签，对其他所有内容一律跳过，甚至连属性都不解析，只提取标签名。

两者的切换逻辑：默认运行 Tag Scanner；当 Tag Scanner 扫到一个标签名，把它喂给 CSS 选择器匹配引擎；如果匹配上了（或者匹配需要属性信息才能判断），切换到 Lexer 获取完整信息；一旦离开所有选择器的匹配范围，立刻切换回 Tag Scanner。

这样设计的核心好处是：大量不在任何选择器匹配范围内的内容，完全不产生 token，也完全不传给 JavaScript VM。对于一个典型的页面，绝大多数标签不会匹配到任何选择器，Tag Scanner 直接划过去，没有任何 JavaScript 层面的开销。

用 Cloudflare 工程师的原话说：最好的优化，是根本不做这件事。

用 Rust 宏 DSL 代替 Ragel

上一代 LazyHTML 用 Ragel 来描述和生成状态机代码。LOL HTML 切换到了 Rust，但 Ragel 生成的是 C 代码，不能直接在 Rust 里用。

工程师于是用 Rust 的过程宏（procedural macro）自己实现了一套类似 Ragel 的 DSL，用于描述非确定有限自动机（NFA）的状态和转换动作。

一个状态定义的示例：

tag_name_state{whitespace=>(finish_tag_name?;-->before_attribute_name_state)b'/'=>(finish_tag_name?;-->self_closing_start_tag_state)b'>'=>(finish_tag_name?;emit_tag?;-->data_state)eof=>(emit_raw_without_token_and_eof?;)_=>(update_tag_name_hash;)}

这段 DSL 描述的是"处于 tag_name 状态时，遇到不同输入字节该做什么"，语法清晰易读。Rust 编译器把这段宏展开成高效的 Rust 代码，同时完成 NFA 优化——对于 Tag Scanner 这种大量动作都是 no-op（不操作）的情况，编译器会把这些空分支整个优化掉，连对应的状态都可能被消除。

两个不同的解析器，共用同一套 DSL 描述的状态机，只是动作实现不同。这样既避免了维护两套独立代码的风险，又充分利用了编译器的优化能力。

Token Outline：延迟求值，避免不必要的内存访问

Rust 有内存安全保证，但安全保证有时候是有运行时成本的。在解析器里，构建 token 对象是一个极高频的操作，每个 token 要包含指向输入字节数组的切片引用（&[u8]），Rust 的边界检查会在每次访问时执行。

LOL HTML 引入了一个叫做Token Outline的中间表示：不直接存字节切片，而是存数值索引范围（Range<usize>）：

// 直接存切片引用（有生命周期绑定，有边界检查开销）structStartTagToken<'i>{name:&'i[u8],attributes:Vec<(&'i[u8],&'i[u8])>,self_closing:bool}// Token Outline：存索引范围（延迟转换）structStartTagTokenOutline{name:Range<usize>,attributes:Vec<(Range<usize>,Range<usize>)>,self_closing:bool}

好处是双重的：第一，索引范围是纯整数操作，没有生命周期绑定，也没有频繁的边界检查；第二，当一个 token 横跨多个输入块（数据分包到达）时，只需要调整整数索引就能更新 token，不需要重新分配内存或重新构造引用。

实际的字节切片只在用户真正请求 token 内容时才按需转换（懒求值）。对于 Tag Scanner 跳过的大量内容，这个转换完全不会发生。

CSS 选择器匹配：一个意想不到的洞察

现在解析器有了，还需要一个 CSS 选择器匹配引擎。

团队最初想复用 Mozilla Servo 项目里的 CSS 选择器库，试了几天发现根本不合适：

• Servo 的选择器引擎是从右往左匹配的（先找最右边的简单选择器，再往上遍历祖先），浏览器这样设计是因为大多数元素不匹配最右边的选择器，可以快速剪枝。但 LOL HTML 的场景是：选择器数量极少，元素数量极多，从右往左意味着每个元素都要往上遍历所有祖先，还需要缓存所有已打开元素及其属性——内存约束直接拦死了这条路。
• 与双解析器架构的协作很别扭：先从 Tag Scanner 拿到标签名，匹配失败再从 Lexer 拿属性，Servo 的引擎不是为这种分阶段匹配设计的。

自己写，而且要从左往右匹配。这时候，一个精妙的洞察出现了。

把 CSS 选择器变成正则表达式

考虑这个 CSS 选择器：

body > div.foo img[alt] > div.foo ul

把它拆成各个组成部分：

body > div.foo img[alt] > div.foo ul ---- ------- -------- ------- -- (a) (b) (c) (b) (d)

每个部分是一个简单选择器，判断一个标签是否匹配它，只需要比对标签名和属性，是简单的条件判断。

现在把每个简单选择器抽象成一个"字符"：a、b、c、d。把层级组合子（>和空格）也对应到正则语法：

• >表示直接子元素，就是"紧接着下一个"；
• （空格）表示后代元素，就是"中间可以有任意多个其他元素"，对应正则里的.*。

整个选择器就变成了：

ab.*cb.*d

这是一个完全合法的正则表达式，可以在 HTML 标签 token 序列上执行匹配。HTML 的元素层级关系，等价于正则表达式对字符串的匹配关系。

虚拟机方式实现正则匹配

有了这个洞察，下一步是选择正则匹配算法。回溯式的算法会在最坏情况下有指数级复杂度，不合适。LOL HTML 选择了虚拟机（VM）方式，这也是 Rust 的regex库、以及很多现代正则引擎的实现方式。

VM 方式的核心思路：把正则表达式编译成一组"指令"，然后用一个虚拟机来"运行"这些指令，对输入进行匹配。VM 可以同时存在多个执行线程（对应 NFA 的多个并发状态），只要有一个线程匹配成功就返回匹配。

基本指令集包括：

• expect X：等待下一个输入，如果不等于 X 则终止当前线程；
• jmp L：跳转到标签 L；
• thread L1, L2：分裂出两个线程，分别从 L1 和 L2 继续执行；
• match：当前线程匹配成功。

hereditary_jmp：处理后代选择器的关键指令

对于后代选择器（空格组合子），标准正则的处理方式是thread + jmp的组合，但这会产生大量冗余指令。LOL HTML 为这个场景专门设计了一条指令：hereditary_jmp。

// 不用标准正则指令集 0| expect <body> 1| expect <div> 2| hereditary_jmp 3 // "从这里往后，每来一个新标签都尝试从标签3开始匹配" 3| expect <span> 4| match

hereditary_jmp的语义是：把自己的目标地址"遗传"给当前栈帧，每次有新的开始标签进来，VM 除了从头重新尝试匹配之外，还会检查栈上是否有活跃的hereditary_jmp，有的话就从对应位置继续匹配。

输入会"收缩"：用栈保存 VM 状态

这里有一个普通正则匹配没有的特殊情况：输入序列会缩短。

普通字符串只会往后增长，但 HTML 的元素层级是一个栈——<div>进栈，</div>出栈。遇到结束标签时，之前打开的元素就从层级栈里弹出了，VM 的匹配状态也需要随之回滚。

解决方案非常自然：把 VM 的状态也存在元素层级栈上。当expect指令在某个栈帧上成功匹配时，把"下一条指令的位置"记录在这个栈帧里。当结束标签让栈帧弹出时，那个栈帧携带的 VM 状态也一起消失，VM 自动回到之前的匹配状态。

额外的一个优化：为了避免每次新标签到来时都遍历整个栈去查找活跃的hereditary_jmp，每个栈帧还记录了"最近一个有活跃遗传跳转的祖先帧的索引"，查找变成了 O(1) 操作。

每个栈帧只需要存一个 64 位整数（标签名的哈希值），内存开销极低，符合边缘场景的约束。

选择器前缀去重：基数树

当同时有多个选择器时，它们可能共享前缀。比如：

body > div > link[rel] body > span body > span a

三个选择器都以body >开头。LOL HTML 把所有选择器组织成一棵类基数树，公共前缀只需要匹配一次。编译时把这棵树展平成一个指令向量，公共前缀对应的指令只出现一次，分叉点用thread指令分裂出多个线程分别处理不同的后缀。

宏指令与"[not] JIT 编译"

最后一个优化是指令粒度。VM 的基本指令每条只做一件很小的事，对于解析器这种极高频的场景，每个 token 都要执行多条基本指令，函数调用本身的开销累积起来也不可忽视。

LOL HTML 把多条基本指令合并成宏指令（macro-instruction），每个宏指令对应处理一个完整的输入 token。这类似于 CPU 微码（microcode）的概念——对外暴露的是粗粒度的宏指令接口，内部实现是一系列微操作。宏指令在编译期通过"[not] JIT 编译"生成，把expect、jmp、hereditary_jmp、match等基本操作内联进来，消除函数调用开销，同时也方便在需要从 Tag Scanner 切换到 Lexer 时暂停宏指令的执行、获取属性信息后再继续。

性能结果

经过以上所有设计，LOL HTML 的实测性能如下：

• Tag Scanner的速度大约是 LazyHTML 的两倍；
• Lexer的速度与 LazyHTML 相当，在较大输入上略有超越；
• 两者都比 Mozilla Servo 的 html5ever（同样是 Rust 实现）快数倍。

在实际使用中，对于大多数不包含匹配元素的页面内容，Tag Scanner 直接跳过，不产生任何 token 传给 JavaScript VM，这部分的实际加速远远不止上面的两倍。

两篇文章背后的一条主线

回顾这两篇博客，Cloudflare HTML 解析器的演化史背后有一条清晰的主线：每一次重写都是被新的约束逼出来的，而每一套新的约束都催生了新的设计思路。

2010 年，分包传输的约束催生了 Ragel 状态机；2016 年，需要真正合规的 HTML5 解析催生了 Parser Feedback Simulator 和 ASCII 兼容性洞察；2017 年，Workers 的 JavaScript VM 集成开销和 CSS 选择器 API 需求，催生了双解析器架构和把选择器转化成 VM 程序的匹配引擎。

每次看起来像是"回头重来"的重写，实际上都是在之前积累的洞察基础上往前走了一大步。LOL HTML 今天已经开源，是 Cloudflare WorkersHTMLRewriterAPI 的底层实现，也可以作为独立的 Rust HTML 解析库使用。

项目地址：https://github.com/cloudflare/lol-html