摘要
流行的隔离级别多版本读已提交（RC）用牺牲强大的可串行化保证来换取事务吞吐量的提高。尽管如此，事务工作负载有时可以在 RC 下执行，同时仍能以较低的成本保证可串行化。这样的工作负载被称为对 RC 具有鲁棒性。本文概述了确定对 RC 的鲁棒性。特别是，我们讨论了如何通过事务模板的形式化来获得合理完整的测试。然后，我们通过使用功能约束来扩展事务模板，从而提高其建模能力，这些功能约束可用于捕获外键等数据依赖关系。我们表明，加入功能约束可以将更多的工作负载识别为鲁棒的，而不是其他情况。即使鲁棒性问题在其最一般的形式下变得不可判定，我们仍确定对功能约束的各种限制会导致可判定甚至可处理的结果，这些结果可用于对实际场景的 RC 鲁棒性进行建模和测试。
作者：
- Brecht Vandevoort, UHasselt, Data Science Institute, ACSL, Belgium
- Bas Ketsman, Vrije Universiteit Brussel, Belgium
- Christoph Koch, École Polytechnique Fédérale de Lausanne, Switzerland
- Frank Neven, UHasselt, Data Science Institute, ACSL, Belgium
INTRODUCTION
可序列化是理想事务语义的黄金标准，许多研究和技术开发都致力于创建提供最大事务吞吐量的系统。然而，在实践中，可以使用不同强度的替代隔离级别层次结构，允许用户权衡语义保证以获得更好的性能。一个突出的例子是隔离级别（多版本）读取已提交 (RC)，它不保证可序列化，但可以比隔离级别 Serializable 更有效地实现。我们在本文中讨论的核心问题是：在 RC 下运行事务工作负载何时是安全的？
许多研究人员都研究过所谓的事务稳健性问题 [1-4、6-10、16、18]，该问题围绕着确定对于给定的工作负载，低于 Serializable 的隔离级别是否足以保证可序列化性。具体而言，如果在指定的隔离级别下允许的执行程序的所有可能的交错都是可序列化的，则一组事务程序被称为对给定的隔离级别具有稳健性。众所周知的 TPCC 基准测试对快照隔离具有稳健性 [10]，这一事实可能最好地证明了非平凡稳健的工作负载确实存在。更具体地说，在快照隔离下允许的任何调度，只要只包含来自 TPC-C 的事务程序的实例，都是可序列化的。
在数据库上执行事务程序会导致对具体数据库对象进行一系列读写操作，我们将其简称为事务。当多个程序同时执行时，由此产生的交错事务序列称为调度。在这样的调度中，事务在访问相同的数据库对象时可以引入依赖关系。例如，如果事务 T1 写入一个对象，而另一个事务 T2 随后读取该对象，则 T2 依赖于 T1。调度 s 的依赖图 CG(s) 是以 s 的事务为顶点、以事务之间的依赖关系为边的图。众所周知，当且仅当调度的依赖图是无环的，调度才是（冲突）可序列化的 [14]。
对于指定为一组具体事务的给定工作负载，其稳健性显然是可判定的，因为可以简单地枚举所选隔离级别下允许的所有调度，并验证它们的依赖关系图是否是非循环的。但是，存在更有效的方法，这些方法基于特定反例调度的特征，当一组事务对隔离级别不稳健时，必须存在该反例调度。这些方法如下：在基于读写锁实现并发控制的单版本数据库中，针对读取未提交和读取已提交的拆分调度和多拆分调度 [12]；针对（多版本）读取已提交的多版本拆分调度 [16]；以及针对快照隔离的多版本拆分调度 [9, 13]。然后，判定稳健性就简化为寻找遵循特定形式的反例调度。
这些结果不会立即扩展到将工作负载指定为一组事务程序（例如，TPC-C 基准）的情况。实际上，事务程序代表了无限数量的具体事务实例，从而产生无限数量的可能调度。在这种情况下，检测稳健性的常用方法是基于在静态依赖图中总结所有潜在调度 [6,10]。更具体地说，该图中的顶点是事务程序，如果存在一对事务 T1 和 T2，分别从 P1 和 P2 实例化，其中 T2 依赖于 T1，则存在从程序 P1 到程序 P2 的边。通过构造，该图包含可以从给定的事务程序集派生的所有可能的调度依赖图。具体而言，非可序列化调度的依赖图中的每个循环都由静态依赖图中的一个循环见证。因此，稳健性的充分条件依赖于静态依赖图中没有循环。请注意，这只是鲁棒性的充分条件，因为静态依赖图中的循环并不一定意味着存在不可序列化的调度。
已经确定了额外的隔离级别特定条件，这些条件必须适用于依赖图中出现非稳健性的循环：快照隔离的危险结构 [10] 和读取已提交的逆流边缘的存在 [2]。因此，只要静态依赖图中的所有循环不满足相应条件，就可以保证对这些隔离级别的稳健性。我们强调，这种方法依赖于静态依赖图的构建，而这本身就是一项不简单的任务。事实上，需要对每对程序进行手动分析以识别可能的依赖关系。IsoDiff [11] 通过分析执行跟踪（即通过执行事务程序获得的一组具体事务）来自动化此构建。但这种方法的缺点是它可能会错过不经常执行的程序，因此不在执行跟踪中。因此，IsoDiff 可能会错误地将应用程序识别为对较低的隔离级别具有稳健性。
我们在稳健性方面的工作与刚才提到的方法有以下不同：
- 我们引入了一种形式化方法来表达事务程序，称为事务模板，它有助于根据反例计划进行推理，本质上允许自动构建静态依赖图而无需人工干预；
- 我们提供了一个既健全又完整的针对多版本读取已提交的稳健性决策程序。
与早期的工作相比，早期的工作只提供了健全但不完整的方法，我们的方法能够检测更多和更大的工作负载组，以抵御读取已提交。我们方法的一个限制是，我们必须假设有一组固定的只读属性，这些属性无法更新，用于选择元组。最典型的例子是作为参数传递给事务模板的主键值。我们参考[16]进行更深入的讨论。在 [20] 中，我们提出了一个充分条件（但不再完整）用于测试模板扩展的鲁棒性，其中元组的所有属性都可以修改，并且包含插入、删除和谓词读取。
本文旨在更通俗易懂地概述 [16] 和 [18] 中提出的主要思想。许多概念只是非正式地介绍，有关更多详细信息，请参阅原始论文。有关我们工作的更完整概述，请参阅 [17]。有关针对数据库理论家的并发控制介绍，请参阅 [14] 和 [13]。有关相关工作的更完整讨论，请参阅 [16, 18]。
DEFINITIONS
TRANSACTION TEMPLATES
ROBUSTNESS
FUNCTIONAL CONSTRAINTS
Templates admitting multi-tree bijectivity
Templates over acyclic schemas
CONCLUSION
我们对最近关于确定事务模板对 RC 的鲁棒性的工作进行了高层次概述。应该清楚的是，这些技术只能在事先知道允许的事务模板集（例如，通过 API 公开时）时使用，并且在可以插入完全任意的事务时不适用。正如介绍中已经提到的，我们的技术只有在存在一组固定的只读属性时才有效，这些属性无法更新，并且用于选择要更新的元组。我们不相信这些限制可以轻易解除。尽管如此，我们确实认为，通过研究事务模板获得的见解可以帮助建立充分（但不再完整）的条件来测试一般事务程序对 RC 的鲁棒性。我们在 [20] 中介绍了这方面的一些初步结果。
一个相关的问题是，当发现一组事务模板对 RC 不具有鲁棒性时，可以做些什么。在 [16] 中，我们提出了一种模板修改技术，该技术基于这样的见解：可以通过将 R 操作提升为写回读取值的 U 操作来创建一组对 RC 具有鲁棒性的等效事务模板。这样的更改不会改变事务模板的效果，但新引入的写入操作将触发数据库中的并发机制。Alomari 和 Fekete [2] 提出了一种修改技术，该技术依赖于向数据库添加新元组，这些元组充当有问题的事务组合的锁，从而强制这些事务不能相互交错，从而确保对 RC 的鲁棒性。一种完全不同的方法是不再要求所有事务都必须在相同的隔离级别下执行，而只为有问题的事务分配更严格的隔离级别。快照隔离和两相锁 [9] 以及 RC、快照隔离和可序列化快照隔离 [21] 的事务级别上已研究了相应的分配问题。在事务模板的上下文中研究分配问题将会很有趣。
