摘要
事务处理是大多数数据库应用程序的核心部分。虽然可序列化性仍然是理想事务语义的黄金标准，但许多数据库系统通过选择较低的隔离级别来提高事务吞吐量，但代价是引入潜在的异常。事务通常不是任意的，而是受到在应用程序级别定义的一组事务程序的约束（例如 TPC-C 的情况），这意味着并非所有潜在异常都能有效实现。本文的核心问题是：在特定事务程序的上下文中，何时隔离级别低于可序列化性，才能提供与可序列化性相同的保证？我们将后者称为稳健性问题。本文调查了针对（多版本）读取提交的稳健性测试的最新结果，重点关注完整条件而非充分条件。我们展示了如何将稳健性测试提升到事务模板和程序以增加实际适用性。我们讨论了未解决的问题并强调了未来研究的有希望的方向。
作者：
- 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
客户端通过发出事务与 DBMS 进行交互，从概念层面上讲，事务是涉及多个数据库对象的复杂操作。例如，事务可能将特定金额的资金从储蓄账户转移到同一客户的支票账户。DBMS 保证事务完全执行或根本不执行（原子性），即使在发生故障的情况下也是如此。通过在事务中交错操作来促进对数据的并发访问，同时通过可序列化的隔离级别保证一致性。可序列化确保事务的并发执行效果始终等同于串行执行。因此，数据库系统保证每个事务的完美隔离，这对应用程序程序员来说至关重要，因为它允许他们将注意力集中在单个事务的正确性属性上。
然而，确保可串行化需要付出不小的性能代价 [48]。已经提出了许多提高事务吞吐量的方法：改进的或新的悲观算法（参见 [24、34、36、42、49]）或乐观算法（参见 [10、11、16、17、22、23、25、27-29、31、37、38、50、51]），以及基于协调避免的方法（参见 [18、19、30、33、35、40、41]）。许多数据库系统提供的正交方法是通过提供各种隔离级别来权衡隔离保证以提高性能。尽管通常默认配置了低于可串行化的隔离级别（例如，参见 [4]），但是在这样的隔离级别下并发执行事务并非没有风险，因为它可能会引入某些异常。然而，有时可以在低于可串行化的隔离级别下执行一组事务而不会引入任何异常。例如，在快照隔离下运行的 TPC-C 基准测试应用程序 [43] 就是这种情况。在这种情况下，该组事务被称为对特定隔离级别具有鲁棒性。更正式地说，如果在指定隔离级别下允许的每种可能的事务交错都是可序列化的，则一组事务对给定的隔离级别具有鲁棒性。检测鲁棒性是非常可取的，因为它可以以较低隔离级别的性能为代价来保证完美的隔离。
Fekete 等人 [21] 发起了快照隔离背景下的鲁棒性研究，将其称为可接受性问题，并提供了静态依赖图中不存在具有特定类型边的循环的充分条件。这些算法是合理的，但不完整，因为它们可能导致假阴性，但永远不会导致假阳性。Bernardi 和 Gotsman [9] 扩展了这一结果，通过提供充分条件来决定针对不同隔离级别的鲁棒性，这些隔离级别可以在声明性框架中定义，正如 Cerone 等人 [12] 所介绍的那样。该框架提供了各种隔离级别（包括快照隔离）的统一规范，这些隔离级别承认原子可见性，即要求每个事务的所有更新对其他事务都可见或都不可见的条件。原子可见性假设是关键，因为它允许通过事务级别上的一致性公理而不是每个事务内各个操作的粒度来指定隔离级别。充分条件再次基于不存在具有某些类型边的循环。一个相关但不同的概念是事务斩断，它将事务拆分成更小的部分以获得性能优势，并且如果对于斩断的每个可序列化执行，都有一个等效的可序列化原始事务执行，则是正确的[39]。Cerone 等人[13, 14]研究了不同隔离级别下的斩断。
虽然健壮性在文献中得到了相当多的关注，但现有的大多数工作都集中在快照隔离 [2, 6, 20, 21] 或更高的隔离级别 [7, 9, 12, 15] 上。到目前为止，对较低隔离级别（例如读已提交隔离级别的不同变体）的健壮性只受到了很少的关注（一个值得注意的例外是 Alomari 和 Fekete 的工作 [3]）。这可能看起来令人惊讶，因为读已提交非常常见，通常甚至是相当多数据库系统的默认隔离级别 [5]，也是少数提供高可用性事务的隔离级别之一 [4]。由于读已提交提供的性能损失较低，因此建立针对此隔离级别的健壮性可以实现快速并发执行，同时保证完美的隔离。
在本文中，我们调查了针对（多版本）读取提交的稳健性问题的最新研究[26，45–47]。一种独特的方法是，我们首先关注健全和完整的算法，然后通过越来越普遍的事务程序形式化，为这些结果的实际应用设定步骤。
在第 3 节中，我们研究了简化设置下的稳健性，其中事务只是读写序列，其结构以及它们将访问的数据库中的对象都是预先知道的。此设置与 Fekete [20] 考虑的设置最相似，他获得了用于确定针对快照隔离的稳健性的可靠且完整的特征。我们提供了针对单版本和多版本读取提交的稳健性的完整特征。
在实践中，事务通常由（有限）数量的事务程序生成（例如，通过 API 提供）。例如，TPC-C 基准 [43] 包含五个不同的事务程序，从中可以实例化无限数量的具体事务。在第 4 节中，我们将前面的结果（部分）扩展为事务程序的形式化，我们将其称为事务模板，从概念上讲，它们是带有参数的函数。然后，鲁棒性成为可以在 API 设计时离线测试的静态属性。当模板集通过测试时，可以将数据库隔离级别设置为该 API 的读取已提交，而不必担心引入异常。我们获得了一个完善的算法来决定事务模板对多版本读取已提交的鲁棒性。当考虑到其他约束（如外键约束）时，可以确定更大的事务模板集是鲁棒的。虽然这些约束使得鲁棒性问题通常无法判定，但有一些限制使问题变得可判定甚至可处理。
第 4 节中介绍的机制的一个主要缺点是它不能扩展到谓词读取、插入或删除，这些操作在现实世界的事务中很常见。因此，我们在第 5 节中不再寻求获得合理和完整的特征，而是讨论如何测试更一般的事务程序的稳健性，这些程序形式化为包含谓词读取、插入、删除以及控制结构的 BTP。一个主要优点是，一旦 SQL 事务程序被转换成 BTP 的形式，稳健性测试就会完全自动进行，不再需要数据库管理员的干预来预测可能的冲突，就像早期的稳健性工作一样。
在第 6 节中，我们讨论了未来工作的方向。本文的处理水平相当高。因此，我们参考 [44] 进行更深入的讨论和缺少的正式定义。
PRELIMINARIES
我们首先介绍必要的定义。我们对事务和冲突可序列化的形式化基于 [20]。这些定义与 Adya 等人 [1] 提出的形式化密切相关，但我们假设调度中的操作是全序而不是部分序。
Transactions and Schedules
Conflict Serializability
Isolation Levels
ROBUSTNESS FOR TRANSACTIONS
我们首先考虑受限设置中的稳健性，其中假设所考虑的事务集是预先知道的。尽管这种受限设置几乎没有直接的实际意义，原因很简单，因为事务集 T 通常不是预先知道的，但我们在下一节中表明，所获得的结果可以推广到应用程序级别的离线稳健性测试，其中与数据库的交互通过由一组固定的事务程序组成的 API 进行。
稳健性属性 [9]（在 [20, 21] 中也称为可接受性）保证给定隔离级别的给定事务集的所有调度的可序列化性：
Single Version Read (Un)Committed
定理 14
对于一个事务集合 \(\T\)：
- 如果 \(\T\) 的一个调度 \(s\) 的依赖图有一个环 \(C\)，则 \(C\) 在 \(IG(\T)\) 中是一个可转移环；
- 如果 \(IG(\T)\) 中存在一个非平凡的环 \(C\)，则 \(IG(\T)\) 中存在一个可转移环 \(C'\)；
- 对于基于 \(IG(\T)\) 中的一个可转移环 \(C\) 的可拆分调度 \(s\)，\(C\) 在 \(CG(s)\) 中式一个环。
Multiversion Read Committed
我们将注意力转移到多版本读取已提交 (mvrc)，这是读取已提交隔离级别的变体，适用于多版本调度。此隔离级别允许事务读取对象的最后提交版本，而不必等待其他事务提交。
定义 25
当一个调度 \(s\) 是 read-last-committed 且不包括脏写时该调度被 mvrc 允许。
STATIC ROBUSTNESS TESTING FOR TEMPLATES
接下来，我们将稳健性测试视为应用程序级别的静态离线问题。我们假设事务只能通过由一组固定的事务程序组成的 API 生成。例如，TPC-C 基准 [43] 由五个不同的事务程序组成，可以从中实例化无限数量的具体事务。一组有限的事务程序（如 TPC-C）对 mvrc 具有稳健性，当且仅当可以从这些程序实例化的每一组事务对 mvrc 具有稳健性。如果答案是肯定的，则可以安全地将隔离级别设置为 mvrc，而无需放弃可序列化性。
我们的方法基于事务程序的形式化，称为事务模板，有助于对 mvrc 的稳健性进行细粒度推理。形式化的关键方面如下：• 从概念上讲，事务模板是带有参数的函数，例如，可以从数据库系统内的存储过程派生。抽象概括了通常在并发控制研究中研究的事务 - 读写操作序列 - 通过使工作对象可变，由输入参数确定。这些参数被输入以增加分析的额外能力。
- 我们支持原子更新（即，读取后写入同一个数据库对象，以对其值进行相对更改），这使我们能够将一些工作负载识别为稳健的，否则将不会如此；
- 此外，我们在字段的粒度上对读写的数据库对象进行建模，而不仅仅是整个元组，从而进一步解耦冲突并允许识别在元组级别上无法识别为稳健的其他情况；
- 元组之间的依赖关系由功能约束建模。
该模型也有一些限制。我们假设有一组固定的只读属性，这些属性无法更新，用于选择要更新的元组。最典型的例子是作为参数传递给事务模板的主键值。在许多工作负载中，无法更新主键并不是一个重要的限制，因为出于监管或数据完整性的原因，一旦分配了键，就永远不会更改。我们在第 5 节中展示了如何以牺牲完整性为代价来超越这些限制。
Formalization of Transaction Templates
Detecting robust subsets
对于仅具有变量等式函数约束的事务模板，确定其对 mvrc 的鲁棒性需要多项式时间 [45]。算法 1 不能直接用于测试事务模板的鲁棒性，因为有无数个事务集与给定的一组事务模板一致。但是，算法 1 可以推广到表示潜在冲突的事务模板级别的干扰图：当这些操作的变量通过变量赋值映射到同一个元组时，潜在冲突的操作会导致冲突操作。决策算法的关键在于，当存在反例多版本拆分计划时，所需的变量实例可以紧凑地表示。
对于具有一般函数约束的交易模板，确定针对 mvrc 的鲁棒性是不可判定的 [47]。当函数约束满足某些限制时，可判定性可以保留。例如，当函数约束允许多树双射时，鲁棒性在 nlogspace 中 [47]。与数据库模式相关的一元函数会诱导一个模式图，将一个关系的元组映射到另一个关系（参见图 8 中的 SmallBank+ 基准）。非正式地说，多树双射意味着应该对函数 (𝑓1, 𝑔1) 进行分区。 , (𝑓𝑛, 𝑔𝑛)，使得每个 𝑓𝑖 和 𝑔𝑖 互为逆，且对于每个 (𝑓𝑖 , 𝑔𝑖) 限制为一个选择的模式图是多树。7 此外，当模式图是非循环时，鲁棒性在 expspace 中 [47]。
Robustness of SmallBank+ and TPC-Ckv
图 9 概述了 SmallBank+ 和 TPC-Ckv 基准测试中检测到的对 mvrc 具有鲁棒性的最大子集（TPC-Ckv 是 TPC-C 的一个版本，其中选择仅限于基于密钥）。交易模板以缩写形式呈现（例如，Bal 指余额）。为了评估抽象的不同特征的影响，我们考虑了不同的设置：“仅 R & W”是通过读取然后写入来建模更新的设置，其中忽略属性和功能约束（即，在整个元组的级别考虑冲突并允许违反功能约束）。
“原子更新”设置是将更新明确建模为原子更新的扩展。与“仅 R & W”设置相比，此设置已经允许检测相对较大的稳健集。事实上，对于 SmallBank+，集合 {Am, DC, TS} 是一个稳健子集，表明在 mvrc 下允许的任何使用这三个模板的任意数量实例的计划都是可序列化的！此外，对于 TPC-Ckv，检测到更大的稳健子集。
接下来，“Attr conflicts”将属性纳入分析（即在属性级别指定冲突）。这种粒度差异对 TPC-Ckv 有深远影响，如图 9 第三行所示：发现四个模板（共五个！）的稳健子集：{Del、Pay、NO、SL}。对于 SmallBank+ 而言，没有任何改进，因为此基准的几乎所有冲突都基于储蓄和支票中的相同余额属性。我们强调，如果数据库系统的并发控制子系统以元组而不是单个属性的粒度工作，则对属性粒度冲突的分析仍然有意义：属性级冲突的稳健性意味着这些系统的稳健性。
最后，“函数约束”在设置中包含了函数约束。对于 SmallBank+ ，添加函数约束允许将 GoPremium 添加到每个最大稳健集，这与以下事实形成对比：如果没有函数约束，集合 {GoPremium} 本身甚至对 mvrc 都不稳健。对于 TPC-Ckv，添加函数约束不会导致对 mvrc 具有更大稳健性的子集。
When robustness fails: promotion
当一组事务模板对 mvrc 代码修改技术不够稳健时，可以应用该技术使其变得稳健。Alomari 和 Fekete [3] 提出了一种技术，该技术依赖于向数据库添加新元组，这些新元组充当有问题的事务组合的锁，从而强制这些事务不能相互交错。
我们根据定义 26 中的见解提出了一种模板修改技术：通过将 R 操作提升为写回读取值的 U 操作，可以创建一组等效的、对 mvrc 具有鲁棒性的事务模板。这样的更改不会改变事务模板的效果，但新引入的写操作将触发数据库中的并发机制。我们强调，这是一种通用技术，始终可以用来构建一组等效的鲁棒模板：定义 26 要求操作 𝑏1 与 𝑎1 是 rw 冲突的（条件 (3)），但不与 𝑎1 是 ww 冲突的（条件 (1)），因此将所有 R 操作提升为 U 操作足以保证对 mvrc 的鲁棒性。例如，可以通过将模板 Balance 和 WriteCheck 中对 Savings 和 Checking 类型元组的所有读取操作更改为原子更新，使 SmallBank+ 基准测试对 mvrc 具有鲁棒性。我们参考 [45] 进行更详细的讨论。
STATIC ROBUSTNESS TESTING FOR PROGRAMS
第 4 节中的方法的一个缺点是它无法扩展以考虑关键属性或谓词读取的更新。在本节中，我们将讨论一种正交方法，其中我们要求健全性但不再要求完整性。我们为事务程序提供了一个正式的 BTP 模型，其中考虑了谓词读取、插入、删除以及控制结构。然后通过测试所谓的摘要图中是否存在某些循环来获得稳健性测试。所提出方法的主要优点是摘要图的构建仅取决于相应 SQL 程序的 BTP 形式化，并且可以自动构建：无需领域专家或数据库管理员干预来预测可能的冲突。
Auction Example
我们通过基于拍卖服务的运行示例来说明该方法，其中数据库模式由三个关系组成：Buyer(id, calls)、Bids(buyerId, bid) 和 Log(id, BuyerId, bid)，第 1 场：PODS 开幕式、主题演讲和 Streaming PODS '22，2022 年 6 月 12 日至 17 日，美国宾夕法尼亚州费城，其中每个关系的主键都带有下划线，Bids 和 Log 中的 BuyerId 是引用 Buyer(id) 的外键。关系 Buyer 列出了所有潜在买家，Bids 跟踪每个潜在买家的当前出价，Log 保存所有出价的记录。每个买家都可以通过 API 调用与拍卖服务进行交互。出于记录目的，属性 Buyer(calls) 会计算买家拨打的总电话次数。 API 通过两个事务程序与数据库交互：FindBids(𝐵,𝑇 ) 和 PlaceBid(𝐵,𝑉 )，其 SQL 代码如图 10 所示。FindBids 返回所有高于阈值 𝑇 的当前出价，而 PlaceBids 将买家 𝐵 的出价提高到价值 𝑉（如果 𝑉 高于当前出价，否则当前出价保持不变）并将此新出价作为新元组插入 Log 中。这两个程序都会增加对 𝐵 的调用次数。
Basic Transaction Programs
Foreign Keys
mvrc, Dependencies and Conflict Serializability
Linear Transaction Programs
Detecting Robustness against mvrc
RESEARCH DIRECTIONS
尽管数据库并发控制在过去十年中并未受到数据库理论研究界的太多关注，但我们确实认为许多有趣的挑战仍未得到解答。我们讨论了未来工作的一些可能方向：
- 尽管存在更通用的概念，如视图可序列化或最终状态可序列化 [32]，但所有关于稳健性的工作都是在冲突可序列化的设置下进行的。有趣的是，看看是否也可以在这些设置中获得与快照隔离 [20]、读取已提交 [26] 和多版本读取已提交 [45] 类似的稳健性测试特征。如何将这些推广到事务模板，以及它们在实践中是否会有所不同。
- 这项工作的总体目标是开发选择适当隔离级别的机制。稳健性提供了轻松的心态：在不放弃可序列化的情况下，增加较低隔离级别的吞吐量保证。但是当工作负载不稳健时该怎么办？一种选择是通过代码修改技术（例如，[3, 45]）使工作负载变得稳健，但这也会降低性能。从理论角度来看，有两种正交方法浮现在脑海中。本文考虑的稳健性是一种二元属性：工作负载是稳健的，或者不是稳健的。是否有可能量化健壮性的失败，例如，计划不可序列化的概率？另一个方向是考虑混合隔离级别，允许在不同的隔离级别下执行不同的事务。我们不是想决定健壮性，而是想找到隔离级别的最佳分配。Fekete [20] 研究了快照隔离和可序列化的分配问题，[1] 考虑了混合隔离级别，但缺乏分配问题的一般理论。
- 考虑到函数约束，事务模板的稳健性是不可判定的。虽然已经获得了一些可判定的限制，但我们对不可判定性的具体要求并没有很好的理解。我们认为仍然可以获得更大的可判定设置。
- 第 5 节中提到的结果是迈向实践中稳健性测试的第一步。缺点是没有考虑 SQL 语句中使用的谓词条件。看看如何将当前方法推广到这个目的将会很有趣。这可能需要对事务程序代码的中间表示进行推理，并且可以从编程语言和编译器领域的技术中受益。
