摘要
事务稳健性问题围绕着决定对于给定的工作负载，低于 SER 的隔离级别是否足以保证可序列化性。本文提出了针对隔离级别（多版本）读取已提交的稳健性的新特征。它支持具有控制结构（循环和条件）以及插入、删除和谓词读取的事务程序 - 触发幻影问题的场景，众所周知，幻影问题在这种情况下很难分析。该特征是图论性的，与数据库研究人员和实践者熟悉的并发控制文献中已知的先前决策机制并无不同。我们通过实验表明，我们的特征突破了界限，允许识别比以前更复杂的工作负载。
作者：
- 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
RUNNING EXAMPLE
DEFINITIONS
SERIALIZATION GRAPHS UNDER MVRC
ROBUSTNESS FOR TRANSACTION PROGRAMS
DETECTING ROBUSTNESS
EXPERIMENTAL VALIDATION
RELATED WORK
如介绍中所述，之前对事务程序的静态稳健性测试 [3, 20] 的工作是基于测试包含某些危险结构的静态依赖图中是否存在循环。本文进一步建立在上述思想的基础上，但在两个关键方面有所不同：（1）通过 BTP 的形式化，我们的方法可以轻松实现，并且不需要数据库专家来构建摘要图。唯一需要的手动步骤是根据 BTP 和外键约束对 SQL 代码进行建模。（2）首次结合了插入、删除以及谓词读取，为在实践中使用稳健性测试迈出了重要一步。
我们之前的工作 [44] 提供了一种完整的算法来决定针对 mvrc 的稳健性，但仅限于只能通过基于键的查找访问元组并且不允许更改键属性的设置。该方法不能扩展到包括插入、删除或谓词读取。事实上，我们在 [45] 中表明，对外键约束的扩展已经使问题变得不可判定。本文通过设计一个合理但不完整的算法来规避不可判定性。[26] 中的工作考虑了事务级别而非事务程序级别的稳健性，并且基于锁定而不是版本控制作为并发控制机制。、
Gan 等人 [21] 提出了 IsoDiff，这是一种用于检测和解决在读取已提交或快照隔离（而不是可序列化）下执行事务所导致的潜在异常的工具。与我们的方法类似，IsoDiff 基于检测具有特定结构的循环。对于读取已提交，IsoDiff 会搜索 I 型循环，但包括额外的时间约束和相关性约束以减少误报的数量。与我们的工作相比，IsoDiff 从数据库 SQL 跟踪中得出潜在事务，而我们通过 BTP 的形式化得出潜在事务。分析跟踪的一个潜在缺陷是它可能会忽略很少执行的事务，从而错误地认为应用程序是健壮的。IsoDiff 从这些跟踪中得出的相关性约束对应于在 BTP 上表达的外键约束。更微妙的区别是，作为 IsoDiff 的一部分提出的时间约束假设依赖关系 𝑏𝑖 →𝑠 𝑎𝑗 始终意味着操作 𝑏𝑖 发生在 𝑠 中的 𝑎𝑗 之前，从而隐式假设读取已提交的单一版本实现，而不是本文讨论的 mvrc。具体而言，如果 𝑏𝑖 →𝑠 𝑎𝑗 是 rw-antidependency，则 mvrc 允许 𝑏𝑖 发生在 𝑠 中的 𝑎𝑗 之后的情况。
其他工作研究了在以声明方式统一指定不同隔离级别的框架内的稳健性 [8, 11, 12]。这里的一个关键假设是原子可见性，要求每个事务的所有更新或所有更新都对其他事务可见。这项工作旨在实现更高的隔离级别，不能用于 mvrc，因为 mvrc 不承认原子可见性。
事务斩断将事务拆分为更小的部分以获得性能优势，并且如果对于斩断的每个可序列化执行，都有一个等效的可序列化原始事务执行 [39]，则是正确的。Cerone 等人 [12, 13] 研究了各种隔离级别下的斩断。事务斩断与针对 mvrc 的稳健性测试没有直接关系。
已经提出了许多在不牺牲可串行化性的情况下提高事务吞吐量的方法：改进的或新颖的悲观算法（参见例如 [24、34、36、42、47]）或乐观算法（参见例如 [9、10、15、16、22、23、25、27-29、31、37、38、49、50]），以及基于协调避免的方法（参见例如 [17、18、30、32、33、35、40、41、48]）。稳健性与这些方法的不同之处在于，它可以应用于标准 DBMS，而无需对数据库内部进行任何修改。相反，即使数据库系统提供较低的隔离级别，也可以利用稳健性属性来保证可串行化。
与稳健性检测正交，诸如 Elle [4] 之类的工具旨在检测在给定隔离级别下不应发生的异常。这些工具可用于检测数据库系统是否正确实现了声明的隔离级别，而稳健性则假设隔离级别已正确实现，以决定给定工作负载的每次可能执行是否可序列化。
我们对事务和冲突可序列化的形式化与 Adya 等人 [1] 提出的形式化密切相关，但也有一些重要的区别，我们将在下文中讨论。我们假设计划中的操作是全序而不是部分序，并且通过引入插入和删除使不同类型的写入操作更加明确。特别是，我们要求只有插入操作才能在未生成版本之后创建第一个可见版本，只有删除操作才能在计划中创建死版本。我们的定义还考虑了原子更新操作，它本质上是同一对象上的读取操作和写入操作，并且不能与计划中的其他操作交错。原子块通过允许事务中的任意操作序列充当一个原子操作，将这一假设更进一步。此外，我们假设所有操作都是针对具体（数据库）元组而不是抽象对象，并跟踪每个操作观察或修改的特定属性值。如 [44] 所示，明确考虑这些原子更新操作以及所访问的属性可以大大提高稳健性检测的有效性。
CONCLUSIONS
本文向实践中的稳健性测试迈出了重要一步：通过基于 BTP 的形式化方法，我们提供了一种稳健性测试算法，该算法 (1) 可以轻松实现；(2) 比最先进的算法有所改进，因为它包含了更大的操作集（插入、删除、谓词读取），并且可以检测更大的事务程序集以抵御 mvrc。未来，我们计划涵盖更具表现力的事务程序。
