化疑为象
Boomslang,以及当不确定性有了名字之后,什么变了
在此之前,一个新的隔离性检查问题,就意味着一个新的检查器。换一个隔离级别,换一个支持范围查询的数据库,换一个会把同一个值写两遍的应用:每一种都打破了前一个检查器的某个假设,于是有人再写一个。发表在 ATC 2026 上的 Boomslang 主张,一个新问题的代价应该是一个模块,而不是一个检查器。另外还有一段我在 ATC 上的报告视频。
底下的那个问题
一个隔离性检查器回答一个问题。给定一份记录——客户端向数据库发了什么、收回了什么——是否存在一个被所承诺的隔离级别允许的执行,能够解释它?读过《一致性检查,就是新的验证器》的读者会认出这个形状:它就是存在性的正确性定义,最古老、也最具体的形式。
这个问题之所以难,是因为记录里漏掉了东西。它不说一个键上的各次写入是按什么顺序装上去的。如果两个事务写了同一个值,它不说某次读看到的是哪一个。如果一次范围查询跳过了某个键,它不说这个键是从未插入过,还是已被删除。检查在一般情况下是 NP 完全的,而搜索就发生在这些不确定之处。
早先的检查器,包括我参与过的 Cobra,各自靠把其中一块假设掉来处理它:写入的值都是唯一的,或者数据库会记录版本顺序。每个假设让一个检查器变快,适配一类负载。真实的应用却时时打破它们。
叠加态
Boomslang 的想法是不再假设,而是给不确定性一个名字。一个叠加态(superposition),用论文的话说,是”一组互斥的可能性,其中任何一个都可以解释记录的一部分”。未知的版本顺序是一个叠加态。一次有歧义的读也是,一次物理删除也是,一个被范围查询跳过的键也是。不同来源的疑问,变成了同一种对象。
叠加态,就是把”存在”拆成了许多小的、局部的片段。检查器不再对一个执行做全局搜索,而是持有许多小选择,每个选择在少数几个备选中恰好取一个,再问:是否存在某种组合,使依赖图里不出现被禁止的环。
一旦不确定性成了一等对象,检查器就有了编译器的形状。前端在客户端记录每个操作的输入和输出,并把记录解析成一张图。模块把它降为一种中间表示,由已知的边和叠加态组成。优化遍剪掉会闭合环的备选,并为搜索排序。后端把剩下的交给一个懂无环性的 SAT 求解器。
这个形状换来了什么
一个隔离级别变成了一个模块。论文实现了其中八个,从读已提交到严格可串行化,每个不到 370 行。它还在这个框架里重新实现了三个早先的检查器:Cobra 本身大约 16,600 行,在这里变成了 271 行。这个检查器在 TiDB 里发现了一个新 bug,还在 PostgreSQL 里发现了一个涉及范围查询的环,而现有的检查器捕捉不到它。
这些都不改变最坏情况。问题仍然是 NP 完全的,记录仍然必须包含所有相关的事务,而一个模块被信任去说清它的隔离级别意味着什么。一个错误的模块,会给出一个自信的错误答案。
我在意这个形状,原因要回到那篇一致性检查的文章。它以一个猜测作结:如果系统变得量身定制,各有各的协议、各有各的弱化保证,那么检查器也得量身定制,而且很可能由编写这些系统的同一批机器来写。一个检查器很难生成。一个针对固定中间表示的 300 行模块却不难,而且短到一个人读得完。这个结构已经经受过一次易手:一个编程智能体把 Boomslang 移植到了 C。
一个编译器,许多级别
隔离性检查并不需要为每种场景准备一个检查器。它需要的是一个把记录里的疑问写下来的地方,以及一些小模块,说清每种保证禁止什么。搜索依然困难。变了的,是提出一个新问题的价格:过去是一篇论文,现在是一个模块。
参考文献
- Jian Zhang, Shuai Mu, and Cheng Tan. Boomslang: A Modular Framework for Database Transaction Isolation Checking. SIGOPS ATC 2026.
- Cheng Tan, Changgeng Zhao, Shuai Mu, and Michael Walfish. Cobra: Making Transactional Key-Value Stores Verifiably Serializable. OSDI 2020.