搜索此博客

元数据

关于广义的分布式系统和其他奇闻异事。本网站上的观点仅代表我个人。

《并发控制》书籍第二章：可串行化理论（Serializability Theory）

• 获取链接

• Facebook

• X

• Pinterest

• Email

• 其他应用

• 2025年5月14日

《数据库系统中的并发控制与恢复 (1987)》一书的第二章，由 Bernstein, Hadzilacos, 和 Goodman 编写，是对可串行化理论（Serializability Theory）的基础性处理。它精确、正式，但又简单而优雅，这在系统领域的基础理论中是一种罕见的组合。数据库在这方面很幸运：可串行化理论既强大又清晰。

本章逐步构建了该理论，介绍了：

1. Histories（历史）
2. Serializable histories（可串行化历史）
3. The Serializability Theorem（可串行化定理）
4. Recoverability and its variants（可恢复性及其变体）
5. Generalized operations beyond reads/writes（超越读/写的广义操作）
6. View equivalence（视图等价）

每个部分都清晰地阐述了定义的动机，提出了严谨的形式主义，并通过精心挑选的例子来说明思想。

2.1 Histories（历史）

本节奠定了基础。它开始得很慢，没有做任何花哨的事情。它首先定义了事务内的操作形成良好偏序的含义。这种事务内的排序自然延伸到事务间的操作，形成一个超集关系。在此基础上，本书定义了一个历史，作为一组事务的操作的偏序。操作包括读取 (r₁[x])、写入 (w₁[x])、提交 (c₁) 和中止 (a₁)。这里的下标表示这些操作都属于事务 T₁。历史模型模拟了来自不同事务的这些操作的交错，尊重每个事务的顺序并确保所有冲突的操作都被排序。

这里的抽象很优雅。该模型省略了值、条件、赋值以及调度器不可见的任何内容。只有依赖结构才重要。这种极简主义是一种优势：它提供了足够的理由来推理正确性。本节还仔细处理了不完整的历史（即前缀），这对于建模崩溃和恢复至关重要。

讨论非常以调度器为中心。由于调度器是负责强制执行可串行化的组件，因此该模型是根据调度器可以观察和采取行动的内容量身定制的。但这导致了一些错失的机会，我将在下面的 2.6 节“视图等价”中提到。

2.2 Serializable Histories（可串行化历史）

这是事情变得真实的地方。目标是定义并发执行（历史）何时“与”某个串行执行“一样好”。本节有一个简单的计划：定义历史之间的等价性（冲突等价），定义串行历史，最后说如果一个历史等价于某个串行历史，那么该历史是可串行化的。

本章介绍了序列化图（SG）。节点是已提交的事务。边捕获冲突：如果 T_i 在 T_j 读取或写入 x 之前写入 x，我们添加一条边 T_i → T_j。

形式主义是严谨的，但并不繁重。一个很好的例子是图 2-1（第 30 页），它比较了等价和非等价的历史。（小错误：H₃ 中的第二个 w₁[x] 应该是 w₁[y]。）

定理 2.1（可串行化定理）：一个历史是可串行化的当且仅当它的序列化图是无环的。

这是一个漂亮的结论：可串行化简化为冲突图中的循环检查。

功劳归功于应得的人。在这种情况下，又是 Jim Gray！在本节末尾有一个致谢，声明：这里使用的等价性和可串行化的定义以及可串行化定理来自 "Gray, J.N., Lorie, R.A., Putzulo, G.R., Traiger, I.L. Granularity of Locks and Degrees of Consistency in a Shared Database. Research Report, IBM, September, 1975."

2.3 The Serializability Theorem（可串行化定理）

本节证明了关于等价于串行执行的大定理。

直观地说，如果 SG(H) 是无环的，我们可以将其拓扑排序成一个等价于 H 的串行历史。如果 SG(H) 有一个环，那么 H 不能被串行化。

该图显示了一个例子。 SG(H) 中的边约束了任何有效的串行顺序。循环意味着矛盾的约束，因此，没有有效的串行顺序。

2.4 Recoverable Histories（可恢复的历史）

可串行化确保在无崩溃的世界中正确性。但在实践中，系统会崩溃，事务会中止，并且部分执行很重要。为了解释故障，本节定义了越来越严格的概念：

• Recoverable (RC)（可恢复）：如果 T_j 从 T_i 读取，那么 T_i 必须在 T_j 之前提交。
• Avoids Cascading Aborts (ACA)（避免级联中止）：T_j 只能从已提交的事务读取。
• Strict (ST)（严格）：读取和覆盖只能在前一个写入者提交或中止之后发生。

定理 2.2：ST ⊂ ACA ⊂ RC

图 2-2 说明了包含层次结构。这些属性与 SR 的交集定义了可以容忍故障并支持恢复的现实计划。

请注意，RC、ACA 和 ST 是前缀提交封闭属性，也就是说，如果它们对历史 H 成立，它们也对 H 的任何前缀成立。很好很干净。

2.5 Operations Beyond Reads and Writes（超越读取和写入的操作）

我很高兴看到这一节。作者展示了该理论如何推广到读取和写入之外的操作，只要我们适当地重新定义冲突的概念。

如果两个操作的执行顺序影响：数据库的最终状态，或者操作返回的值，则两个操作冲突。图 2-3 给出了兼容性矩阵，用于捕获读取/写入/递增/递减之间的冲突关系。 Increment(x) 将 1 添加到数据项 x，而 Decrement(x) 从 x 中减去 1。Inc 或 Dec 不会将值返回给发出它的事务。

示例历史 H₁₁ 显示了如何构造 SG(H)，即使使用这些新操作也是如此。该理论提升得很干净。由于 SG(H_11) 是无环的，因此广义可串行化定理表明 H_11 是 SR。它等价于串行历史 T1 T3 T2 T4，可以通过拓扑排序 SG(H_11) 获得。 DAGs FTW!

尽管如此，这仍然是一个有限的讨论。它不够表达性，无法建模更一般的交换律。但 CRDT 的种子就在这里。在 CRDT 中，您根据操作是否在所有交错下交换来建模操作。有一个正在进行的研究方向 试图围绕更通用的操作和单调性概念构建一个好的理论。

2.6 View Equivalence（视图等价）

本节介绍视图可串行化 (VSR)，它是冲突可串行化的一种更宽松的替代方案。如果满足以下条件，则两个历史在视图上是等效的：

• 一个历史中的每个读取都从另一个历史中的同一个写入读取。
• 每个数据项的最终写入在两个历史中都是相同的。

VSR 比 CSR 允许更多的调度。考虑下面的例子。 T3 覆盖 x 和 y 挽救了局面，并掩盖了 T1 和 T2 中的冲突。有趣的特例！

本书说测试 VSR 是 NP 完全的，这扼杀了它对调度器的有用性。作者认为，所有实际的调度器都使用冲突可串行化，并且视图可串行化的强制执行成本太高。然而，他们承认它在概念上很有用，特别是在推理多副本数据库（第 5 章和第 8 章）时。

阅读本节时，我有一个有趣的问题。视图可串行化是否与客户端中心一致性相同？它们看起来非常相似。正如 Crooks 等人在 PODC 2017 中讨论的那样，客户端中心一致性 根据读取观察到的内容来定义正确性。 VSR 同样是观察性的。

因此，虽然 VSR 在调度方面并不实用，但它在定义分布式系统中的观察一致性方面找到了第二次生命。我认为这棵树上有更多的果实。