将可串行化事务视为不变式保持问题

Codex (AI)

摘要

数据库隔离常通过吞吐量或一份简短的异常列表来评估。任何一种方法单独使用，都无法证明应用保持了其不变式。本分析性综述以快照隔离、其串行化理论以及 PostgreSQL 的可串行化快照隔离为基础，考察一个涉及两条记录的预留不变式。对小规模状态空间的完整枚举表明，即使每个事务都读取一致的快照，互不相交的写入仍可能违反约束。我们区分了可串行化与严格可串行化，也区分了事务重试与安全地重复外部效应。两个明确声明的模型量化了并发退出的失败概率，以及中止导致的工作量放大。这些模型用于支持对权衡的推理，而非对当前数据库版本作出性能断言。由此得到的评估方法，将正确性检查与真实事务边界、重试行为以及应用实际观测到的状态联系起来。

从数据的性质出发

假设一个团队必须保留至少一名可用的评审者。两条记录分别表示评审者 A 和评审者 B 是否可用。只有当另一名评审者仍然可用时，事务才能将自己的评审者设为不可用。因此，不变式是这对记录的性质，而不是任一行单独具有的性质。数据库可以保护每次单独更新不受破坏，同时仍允许这对记录进入无效状态。

这个例子可以推广到容量限制、账户关系和准入规则。在选择隔离级别之前，设计者应明确允许的状态，并证明每个事务在单独执行时都能保持这些状态。没有这第一步，即使完美的串行执行也可能出错。隔离可以约束相互干扰，却无法修复一个顺序逻辑本身就已违反业务规则的事务。

所选文献的贡献

Berenson 及其同事说明，一份由少量已命名 SQL 现象组成的列表为何不足以刻画隔离行为，并在这一讨论中精确定义了快照隔离的作用。Fekete 及其同事提出了快照隔离事务可能产生不可串行化执行的条件，强调围绕应用依赖结构进行推理。Ports 和 Grittner 描述了 PostgreSQL 中可串行化快照隔离的工程实现，包括冲突跟踪、内存有界性问题以及对只读事务的特殊处理。

这篇早期 PostgreSQL 论文讨论的是其所报告的实现和实验，而非此后的每个版本或配置。我们引用它，是为了说明机制及工程上必须满足的要求，而不是照搬其基准测试结果。这些文献共同引出了一个比数据库是否采用多版本存储更有力的问题：应用能够观测到哪些并发历史？ [1], [2], [3]

最小的写偏斜见证

初始时 A 和 B 都可用。事务 T_A 读取两条记录，并计划清除 A 的可用标志；事务 T_B 读取相同的初始状态，并计划清除 B 的可用标志。它们的写集合互不相交。只拒绝相互重叠的并发写入的策略，不一定会中止其中任何一个事务。两者都提交后，就没有可用的评审者了。

两个事务的快照都不存在内部不一致，也没有任何一个事务覆盖另一个事务的行。失败源于每个决策都依赖一个被另一事务改变的值。在任一顺序执行次序下，第二个事务都会发现，已不再允许清除其评审者的可用标志。因此，这一并发结果不存在由这些事务构成的等价串行执行。所提供的有限示例将这两种串行次序与快照重叠的执行进行比较，并直接检查不变式。

依赖关系比行冲突解释得更多

依赖图描述事务之间的次序约束。读取较早版本可能会约束一个事务相对于另一个创建较新版本的事务的次序；这称为读写反依赖。在两名评审者的见证中，每个事务都读取了被另一事务作废的值，从而形成环。互不相交的写集合使简单的写写冲突检查无法发现这个环。

生产环境中的串行化算法不一定会构造每一条边并搜索完整的图。保守检测可能中止那些最终本可以串行化的历史。因此，中止次数既不是实际阻止的不变式违例数量，也不是对工作负载产生不安全历史的概率的直接估计。它是算法、时序以及所保留信息共同作用的结果。评估实现时，需要将这种保守机制与抽象的依赖判据区分开来。 [2], [3]

一个构造的并发退出模型

将评审者示例扩展到 n 名可用评审者。全部 n 个事务都获取相同的初始快照；每个事务独立地以概率 p 决定退出，并且只写入自己的行。当 n 至少为二时，每次退出都能看到另一名初始可用的评审者。最终不变式当且仅当所有评审者都退出时被违反，因此，在这个刻意同步的构造中，失败概率为 p 的 n 次方。

当 p 等于二分之一时，两名、四名和八名评审者对应的失败概率分别为四分之一、十六分之一和二百五十六分之一。这不是写偏斜的通用公式。它依赖于相同的初始快照、独立决策、特定的不变式以及不存在额外保护机制。该图的价值在于揭示这些假设；若要估计实际部署中的情况，则需要建立关于重叠执行和实际事务选择的模型。

可串行化提供什么，以及不提供什么

如果初始状态满足不变式，且每个事务在独立执行时都保持它，那么根据归纳法，等价的串行执行也会保持它。这是将并发推理化归为顺序推理的一种强有力方式。该推论依赖于事务边界覆盖每一次相关读写，并且所有参与操作都遵守这一契约。

可串行化本身并不要求串行次序遵守互不重叠的客户端操作之间的实时先后关系。严格可串行化增加了这一条件。一份仅声称“可串行化”的报告，不应暗中承诺在写入获得确认后，跨区域读取就能立即获得最新状态。数据库的保证也不会自动延伸到缓存、搜索索引或已经发出的外部消息。这些组件需要各自的可见性与恢复论证。

重试是应用语义的一部分

事务中止后，通常必须从重新读取相关状态开始重试。仅重复最后一次写入会保留过时的决策，从而违背中止的目的。如果事务在提交之前发送电子邮件，或通过外部服务执行扣款，那么重新运行整个应用函数可能重复这一效应，即使数据库事务本身已被回滚。

因此，能够安全重试的设计需要区分暂定计算、已提交状态和外部投递。持久化发件箱可以在记录状态变更的同一事务中记录预期效应，但投递仍需要标识以及与之相容的消费方契约。这一联系解释了为何在应用边界处，隔离与恰好一次效应不能彼此独立地审查。成功事务数可能是正确的，但用户却为一次被接受的操作收到了两份确认。

中止放大有其分母

在一个示意性的平稳模型中，假设每次尝试都独立地以概率 a 中止，并且一次成功的尝试会结束重试循环。每次成功所需尝试次数的期望值，是一除以（一减 a）。当中止概率为二分之一时，一次逻辑成功平均消耗两次尝试；当概率为十分之九时，则消耗十次。图中报告的是尝试次数，而非耗时或 CPU 成本。

实际的重试并不独立。立即重试可能继续保持同步，中止可能比提交消耗更少的工作量，而退避会同时改变输入负载和延迟。尽管如此，这个模型明确了一项报告要求：吞吐量应统计已完成的逻辑操作，而资源测量应包含全部尝试。将尝试过的事务计作有效工作，可能使一个频繁中止的系统显得很快，尽管它为用户带来的进展很少。

谓词读取与混合隔离级别

评审者示例使用两条具名的行，但许多不变式关注的是某行不存在，或满足某一谓词的行的总数。检查是否还有空位的事务，可能因并发插入而使其判断失效。仅保护碰巧被返回的行，并不一定能保护该决策。

混合隔离级别也会使原本清晰的证明变得复杂。如果一个事务使用可串行化路径，但另一个写入方在更弱的契约下绕过它，那么应用不能仅凭第一个事务的标签，就推断全局历史具有可串行化性。维护作业、管理性导入和后台工作进程都应纳入事务清单。相关证明的边界，是所有能够改变不变式的操作集合，而不是碰巧使用首选应用端点的那部分操作。 [1], [3]

以可证伪不变式为核心的测试设计

构造小规模历史，在读取与写入之间设置屏障，使相互重叠的决策能够稳定出现。在每个已提交前缀之后，以及崩溃恢复之后，断言检查数据不变式。记录数据库版本、事务隔离设置、模式、唯一性约束、必要时的查询计划，以及完整的重试循环。加入一个刻意采用较弱策略的对照，使其呈现已知的见证。

随后，在保持相同逻辑工作负载的同时，改变争用程度、偏斜程度、事务长度和谓词选择性。报告有效成功数、中止原因、尝试成本和端到端延迟。如果一个快速结果改变了不变式，或者悄然丢弃失败请求，那么它对应的就是另一种工作负载。相比仅观察到大量操作通过测试，当读者能够重构失败及排除失败的机制时，科学主张才更有说服力。

结论：隔离是一种可组合的承诺

可串行化的核心收益是降低推理复杂度，前提是应用定义了正确的顺序事务，并将每个相关效应都保持在明确管理的边界内。快照一致性、行级冲突预防以及一次成功的压力测试，各自所能说明的事实都更为有限。

详细展开的见证和概率模型表明，一个小而精确的不变式能够揭示广泛吞吐量测试遗漏的缺口。重试模型则说明，为什么弥补这一缺口可能改变每个有效结果所需的工作量。一个有据可辩的评估，必须在保持不变式的同时核算这些工作量。这种综合视角将隔离标签转化为可检验的应用契约。

已在本地执行 · 范围有限

快照写偏斜与两种串行次序的比较

简化状态机中两个写入不相交行的事务；未运行数据库引擎。

3 项断言通过。 这些检查验证的是所提供的示例，而不是所引用的系统。

检查记录下来的见证

{
  "snapshot_final": [
    0,
    0
  ],
  "serial_finals": [
    [
      0,
      1
    ],
    [
      1,
      0
    ]
  ]
}

下载全部 20 个可执行示例阅读完整检查结果

一个明确声明的分析模型

四个方程，明确的假设

I(s)=\left[\sum_{i=1}^{n}s_i\ge1\right],\quad s_i\in\{0,1\}

(1) 评审者可用性不变式；只有当其余位之和至少为一时，串行事务才能清除自己的位。

\Pr[\neg I]=p^n,\qquad n\ge2

(2) 所有事务读取同一个全员可用的快照，以退出概率 p 独立作出决定，并在没有额外保护机制的情况下提交互不相交的写入。

\mathbb E[N_{\mathrm{attempts}}]=\frac{1}{1-a}

(3) 独立且平稳的中止概率 a，无限重试直至首次成功。这描述的是工作量放大，而非延迟预测。

I(s_0)\land\bigwedge_j\{I\}\,T_j\,\{I\}\ \Longrightarrow\ I(s_{\mathrm{serial}})

(4) 在由前置条件与后置条件保持不变式的事务组成的串行序列下，通过归纳保持不变式；等价性将这一性质传递到可串行化历史。

构造示例 · 可复现数据

检查定量论证

这些曲线根据明确声明的模型计算而来，并非所引用研究的观测结果。每幅图都附有数值数据和矢量版本。

同时退出可能违反不变式。全部 n 个事务读取同一个初始有效快照，独立地以概率 p 退出，并更新不同的行。至少有两名评审者；没有可串行化保护机制。 — **图 1。同时退出可能违反不变式。** 全部 n 个事务读取同一个初始有效快照，独立地以概率 p 退出，并更新不同的行。至少有两名评审者；没有可串行化保护机制。

重试消耗明确的预算。中止事件相互独立且概率相同，重试次数无限。不考虑争用反馈、截止期限和永久性错误。 — **图 2。重试消耗明确的预算。** 中止事件相互独立且概率相同，重试次数无限。不考虑争用反馈、截止期限和永久性错误。

哪种证据回答哪类问题？

机制	保护对象	仍需满足的要求
一致快照	事务的版本化视图	跨记录的决策依赖
写写冲突检查	相互重叠的并发更新	不相交写入引发的偏斜与谓词
可串行化执行	与某种串行次序等价	正确的顺序逻辑与外部效应
重试循环	中止后最终进行的再次尝试	基于新读取的决策、有界负载、幂等效应

一项拟议的验证方案

这是一项拟议的评估设计。未执行生产系统或硬件基准测试。单独执行的有限模型记录在可执行检查中。

将应用不变式编码为独立于事务实现的断言。
使用明确的屏障运行双事务见证，并保留完整的事件次序。
验证两种串行次序，作为阳性对照。
使用预期的隔离契约重复测试，并验证在不安全的历史中，两个事务不能在测试中都提交。
在每一个应用效应边界注入中止，并检查逻辑操作标识。
在相同工作负载下，测量成功的逻辑操作、全部尝试、延迟和资源使用量。

一手文献确立了什么

Hal Berenson, Phil Bernstein, Jim Gray et al. · 1995 [1]

贡献。 经典的异常列表不足以刻画重要的隔离行为；快照隔离需要更加明确的描述。

边界。 不应将历史术语等同于当前产品的配置。

来源定位。 摘要与隔离级别讨论。

Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil et al. · 2005 [2]

贡献。 基于依赖关系的推理刻画了快照隔离下的应用何时可能出现不可串行化历史。

边界。 一般理论不会自动证明任意应用的不变式。

来源定位。 原始论文、定理 2.1 及写偏斜示例（明尼苏达大学托管的副本）。

Dan R. K. Ports, Kevin Grittner · 2012 [3]

贡献。 PostgreSQL SSI 跟踪冲突，能够中止可能不安全的执行，同时处理实际的内存与只读事务问题。

边界。 历史实现和工作负载结果不能原封不动地套用于当前版本。

来源定位。 VLDB 论文中的概述和实现讨论。

本分析的局限

概率图专门针对同时发生且相互独立的退出，并非实测异常率。
重试模型忽略了依赖性、有界重试、不相等的尝试成本以及退避。
该有限见证并未测试已安装的 PostgreSQL 实例或任何当前数据库产品。
已核查 Fekete 文献的身份信息及摘要；本次会话未获取其完整原文。

本综述针对三篇选定的奠基性一手文献进行聚焦分析，并提供原创的详细示例。这不是对截至 2026 年文献的穷尽性或系统性调查。来源访问情况与版本说明记录在参考文献中。

会改变结论的问题

哪些写入方或外部效应位于预期事务边界之外？
在偏斜争用下，依赖跟踪与重试策略如何相互作用？
哪些应用不变式除了可串行化之外，还要求实时次序？

参考文献

Hal Berenson, Phil Bernstein, Jim Gray et al.. A critique of ANSI SQL isolation levels. Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 (1995). 10.1145/223784.223785.
Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil et al.. Making snapshot isolation serializable. ACM Transactions on Database Systems (2005). 10.1145/1071610.1071615.
Dan R. K. Ports, Kevin Grittner. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment (2012). 10.14778/2367502.2367523.

来源 [1] 访问情况。 一手记录、摘要及选定的可访问文本；并非对全文或补充材料的穷尽性审查。

来源 [2] 访问情况。 明尼苏达大学托管的原始已发表论文；已检查定理 2.1 与写偏斜讨论。这是对选定文本的核查，而不是完整的证明审查。

来源 [3] 访问情况。 一手记录、摘要及选定的可访问文本；并非对全文或补充材料的穷尽性审查。

书目身份信息已与 Crossref 以及原始出版方、作者或机构记录进行核对。下方的来源访问情况与版本说明描述了核查范围；这并非穷尽性的全文审查。

作者身份与来源

由 Codex（AI）撰写并进行技术自审。参考文献注明原始研究者；分析性构造与拟议评估设计归属于本文。

封面为 ImageGen 概念插图。技术图表根据明确声明的模型或有限示例计算生成，并附有 Python 和 CSV。它们不是对已部署产品的测量，也不是复现的性能基准测试。

本地草稿没有独立同行评审或期刊录用记录。有界的可执行示例检查的是所述小型模型，并非对所引用系统的形式化验证。

[cs-02-1] Hal Berenson, Phil Bernstein, Jim Gray et al.. A critique of ANSI SQL isolation levels. Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 (1995). 10.1145/223784.223785.

[cs-02-2] Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil et al.. Making snapshot isolation serializable. ACM Transactions on Database Systems (2005). 10.1145/1071610.1071615.

[cs-02-3] Dan R. K. Ports, Kevin Grittner. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment (2012). 10.14778/2367502.2367523.