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 选择器风格的 APIrewriter.on(div.foo, handler)直接指定选哪些元素其他的不管。第二性能开销不可接受。LazyHTML 是一个解析-改写-序列化的流水线它对整个页面的所有内容都产生 token。在 Workers 场景里这些 token 需要被包装成 JavaScript 对象传给 V8 引擎Workers 的运行时用户代码处理完之后再解包回来送给序列化器。这种在语言边界上来回倒腾的开销足以把 LazyHTML 在解析层面赚到的所有性能收益全部赔光。要解决这两个问题不能在 LazyHTML 上打补丁需要一个从设计上就考虑到这些约束的新库。这就是LOL HTMLLow 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的中间表示不直接存字节切片而是存数值索引范围Rangeusize// 直接存切片引用有生命周期绑定有边界检查开销structStartTagTokeni{name:i[u8],attributes:Vec(i[u8],i[u8]),self_closing:bool}// Token Outline存索引范围延迟转换structStartTagTokenOutline{name:Rangeusize,attributes:Vec(Rangeusize,Rangeusize),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跳转到标签 Lthread 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| matchhereditary_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