十年歧途:一个正则表达式的故事
今天我要分享两个关于正则表达式的故事:微小的不精确性,最终导致全球 iOS 设备累计浪费超过 5000 万小时 CPU 时间。
温馨提示:本文包含大量技术细节,非技术人员阅读可能略有难度。
Safari 内容拦截器工作原理
首先需要说明 iOS 版 AdGuard 依赖于 Safari 内置的内容拦截器机制。
目前也支持替代方案 declarativeNetRequest(英文简称:DNR),部分兼容 Chrome 和 Firefox。有趣的是,在 Safari 中 DNR 规则在底层会被静默转换为内容拦截器规则。
2015年10月发布初代 AdGuard iOS 版时,我们立即就遭遇了一个棘手的问题:传统广告过滤器一直使用专属过滤规则语法,这种语法专为网页过滤设计且功能强大。但 Apple 却推出了与社区习惯迥异的自有方案。
前瞻提示:当 Chrome 引入 declarativeNetRequest 时也选择了自成体系,至少在其 URL 匹配语法上更接近我们熟悉的规范。
下图展示标准的 AdGuard 规则转换为 Safari 支持语法的过程:
注意 URL 模式的变化:在 AdGuard 过滤器中,我们使用针对 URL 特制的类通配符语法。原因很简单:传统正则表达式在此场景下运行效率过低。
正则表达式实现机制
Safari 内容拦截器则依赖正则表达式。并且是以高度简化的形式实现,以便最终能编译成可以加速匹配的结构化数据。
技术细节说明:Safari 会将正则表达式模式编译为 DFA 字节码,并通过定制解释器执行。详见 WebKit 源码:DFABytecodeInterpreter.cpp。
正则表达式确实比标准广告拦截语法更灵活。这种灵活性在网页内容过滤场景中实际用途有限,但其代价却是极其消耗资源的规则编译过程,以及严格的规则数量限制。我们曾详细讨论过 Safari 的这些问题,而其中多数问题至今依然存在。
模式转换方案 v1.0
回到2015年,我们需要解决的核心问题是如何将 AdGuard 的 URL 模式转换为 Safari 可接受的正则表达式。
当时面临两大挑战:
第一,必须压缩最终规则集的总量。当时 Safari 有5万条规则的硬性限制(解决方案详见我们关于 Safari 广告拦截的专题文章)。
当前规则上限已提升至15万条,但由于进程内存限制,实际仅能使用 6-8 万条。我们曾多次向 Apple 反馈(Apple Feedback Assistant 报告编号:FB19728743、FB13282146),但仍未解决。
第二,必须确保生成的正则表达式具备足够高的执行效率,且轻量化到 iOS 设备可顺利编译。在那个时期,我们经常发现系统因资源占用过高而终止 com.apple.Safari.ContentBlockerLoader
进程。
经过大量人工测试后,我们最终确定了在当时看来最优的转换方案:
||
符号(“开始与 URL”)转换为^[htpsw]+://([a-z0-9-]\.)?
^
符号(“分隔符”) 转换为[/:&?]
我们自信地认为已经做足了功课,以后可以高枕无忧,维持原有方案。这一搁置便是近十年。
我们错了
这一切始于一份新的错误报告。问题在于我们的标准转换方法轻微改变了特殊符号 ||
的语义,在 iOS 端它最终仅匹配单级子域名,而 AdGuard 所有其他版本中该符号可匹配所有层级。
解决方案其实非常简单:直接采用 WebKit 开发者在 2015 年推荐的原始正则表达式(也就是我们当年认定为“非最优”的方案)。但由于当时过度自信,我们直到最近才重新验证这个方案。
真正需要修改的规则极其简单:
- 将
||
转换为^[^:]+://+([^:/]+\.)?
- 在多数情况下将
^
转换为[/:]
但这样做真的会有巨大差异吗?事实证明,天差地别。
大错特错
换上新的正则表达式后,我们进行了快速测试,而测试结果令人震惊。Safari 中的规则加载速度不是简单得提升,而是实现了质的飞跃。
用数据说话:Safari 中跟踪保护过滤器的编译速度提升至5.5倍,基础过滤器的编译速度提升至2.8倍。
为使效果更直观,请观看以下演示视频:
当我们统计过去十年 AdGuard 用户总量及其过滤器重编译次数后,发现 iOS 设备上额外浪费的 CPU 时间至少达到 5000 万小时。
这个错误令我们深感惭愧,尤其是意识到正确答案始终近在眼前。回溯过往,这些新正则表达式显然比我们当初选择的方案具有更快的编译和执行速度。
我们当年的错误究竟何在?我认为根源在于存在缺陷的测试方法:我们试图“肉眼判断”,而没有做到:
- 明确定义评估标准:内存占用、运行速度及内容拦截器的实际浏览器表现。
- 最关键的是:掌握精准测量这些指标的方法(不应依赖活动监视器或
top
命令的粗略观察,而需使用专业分析工具)
值得庆幸的是,这个问题现已解决。衷心希望我们已汲取必要教训,未来不再犯类似的错误。