$$
\def\Var{\mathsf{Var}}
\def\IG{\mathsf{IG}}
\def\T{\mathcal{T}}
\def\S{\mathcal{S}}
$$
摘要
在在线事务处理（OLTP）系统中，可序列化是事务执行的一个关键属性；如果没有它，由于并发活动，可能会违反数据的完整性约束。可以通过使用严格的两阶段锁定（S2PL）等可序列化并发控制机制来保证可序列化，而不考虑应用程序逻辑。然而，这种机制导致的并发性降低通常过于严重，因此数据库管理系统（DBMS）为数据库管理员（DBA）提供了使用不同并发控制机制的机会，前提是这样做是安全的。然而，此前几乎没有理论可以指导 DBA 判断何时是安全的！
在本文中，我们讨论了如何为一组事务分配适当的隔离级别（从而使用特定的并发控制机制），同时确保每次执行都是冲突可序列化的。当每个事务可以选择使用 S2PL 或快照隔离（SI）时，我们精确地描述了可接受的分配，并提供了一个简单的基于图的算法来确定最弱的可接受分配。
本文涉及的类别和主题描述包括：数据库管理系统中的事务处理。关键词包括：并发控制、可序列化、异常、一致性、快照隔离、两阶段锁定。
INTRODUCTION
数据库管理系统（DBMS）在工业中被广泛应用于在线事务处理（OLTP），在这种场景下，快速响应且独立编码的应用程序被用来执行商业活动（例如，修改库存、财务和客户数据以反映一次销售的发生）。在这种系统中，数据完整性至关重要，它既涉及数据值与现实世界状态的一致性，也涉及表达数据内部一致性的约束的有效性（例如，参照完整性，或者汇总数据与被汇总数据的相等性）。在 OLTP 系统中，数据完整性面临许多威胁，但一个重要的威胁来自独立应用程序的并发活动；如果没有对交织执行进行仔细控制（即并发控制），诸如“丢失更新”或“不一致读取”等异常可能会导致数据被破坏。
“ACID 事务”的抽象概念，尤其是 DBMS 机制如何防止对数据完整性的并发风险，是 Jim Gray 因其在 1998 年获得图灵奖的伟大贡献之一。这些思想已经发展成为一个强大的理论，包含两个主要方面。一个方面是识别那些被认为是正确的交织（因为它们不会威胁到数据完整性）；另一方面是开发（并证明其正确性）控制这些交织的算法。长期以来，可序列化一直被认为是事务执行的适当正确性标准。可序列化执行是指每个提交的事务看到的值，以及最终状态包含的值，与在完全无并发的串行或批处理执行中运行事务时相同。可序列化执行的优点在于，只要初始状态满足任何完整性约束，并且每个单独运行的事务程序从满足约束的状态出发产生另一个这样的状态，那么我们就可以确信最终状态的数据满足任何完整性约束。也就是说，如果应用程序被逐一检查，DBA 就不必担心它们的交织会引发微妙的问题。
在文献中，有许多并发控制机制可以确保所有执行都是可序列化的（无论运行什么事务）。然而，在实践中，很明显，严格的两阶段锁定机制（采用某种形式的索引锁定）是保证可序列化的主导方式。许多商业系统，包括 IBM 的 DB2、微软的 SQL Server 和 Sybase 的 ASE，都是基于这种算法构建的。不幸的是，即使系统设计者发明了所有可能的改进，执行两阶段锁定时并发性降低的性能影响仍然被认为是严重的，事实上，这些引擎上的大多数事务都使用较低的隔离级别，其中共享锁被提前释放或根本不被获取。
另一种多版本并发控制方法出现在包括 Oracle 和 PostgreSQL 在内的系统中。这种方法完全避免使用共享锁，而是通过访问旧版本的数据（这些数据无论如何都可能被保留用于回滚目的）来实现。这种算法称为快照隔离（SI），它避免了所有已知的并发异常，如不一致读取和丢失更新。然而，正如在[2]中证明的那样，这种算法并不能确保所有事务的执行都是可序列化的，并且可能会导致违反完整性约束。简而言之，快照隔离的并发控制机制意味着事务 T 看到的是在 T 开始之前提交的所有事务产生的数据库状态。因此，如果 T1 和 T2 是使用快照隔离机制的并发事务，它们彼此都不会看到对方的修改（而在串行执行中，因此也在可序列化执行中，其中一个事务会看到另一个事务的修改）。
在本文中，我们考虑了如何利用 DBMS 支持不同事务使用不同隔离级别（从而使用不同的并发控制机制）的能力。虽然实践者经常这样做，但此前几乎没有理论可以指导他们明智地做出这些决策。特别是，我们考虑一个 DBA 可以选择对某些事务使用严格的两阶段锁定机制，而其他事务则使用快照隔离机制。这将在微软 SQL Server 即将发布的 Yukon 版本中变得非常容易，DBA 可以在每个程序中在首次访问数据库之前包含“SET ISOLATION LEVEL”语句，而引擎同时支持“ISOLATION LEVEL SNAPSHOT”和“ISOLATION LEVEL SERIALIZABLE”（后者将使用两阶段锁定）。在 Oracle 中，以“SET ISOLATION SERIALIZABLE”开头的事务将使用快照隔离，但可以通过在默认的“读已提交”隔离级别下使用“LOCK TABLE name IN SHARE MODE”在读取表之前显式设置共享锁来获得两阶段锁定。
我们提供了一种理论，使 DBA 能够决定，对于每种可能的并发机制分配，分配是否可接受，即所有可能产生的执行是否都是可序列化的（因此是否能够保持数据的完整性）。当然，总是至少有一种可接受的分配：对每个事务都使用两阶段锁定。然而，正如我们将展示的那样，我们的理论可以证明其他分配是否也可接受，而且通常 DBA 能够证明许多事务可以被允许使用快照隔离机制。
在第 2 节中，我们解释了涉及的并发控制机制的细节，并总结了我们所依据的现有定义和理论。在第 3 节中，我们分析了单次执行中的冲突，并展示了在任何非可序列化执行中都成立的一些属性。第 4 节则研究了一组事务以及分配给这些事务的并发控制机制；我们的主要结果是定理 3，它精确地描述了何时一个分配具有所有可能产生的执行都是冲突可序列化的属性。第 5 节研究了所有可能的可接受分配的空间，并展示了保持可接受性的分配操作。第 6 节总结全文。
Related Work
关于可序列化理论和并发控制的文献浩如烟海。请参阅[4, 8, 6, 12]以获取相关介绍和参考文献。然而，这些先前的工作大多只考虑那些在没有任何应用程序知识或完整性约束的情况下就能保证正确性的情况，这并不适用于 SI。快照隔离机制首次在研究文献[2]中被描述，该文献还证明了这种机制并不能在所有情况下保证正确性。先前的工作[5]展示了当所有程序都使用 SI 进行并发控制时，如何为某些应用程序组合证明可序列化。与本文不同的是，这些工作并未考虑运行不同算法的事务的混合。
长期以来，研究传统一直致力于处理将不同的并发控制技术应用于数据的不同部分（要么是每个对象，要么是联邦系统中的每个站点）的混合。[11]详细分析了何时可以组合每个对象的并发控制算法，但每个算法都需要在没有具体应用程序知识的情况下保证本地可序列化（与 SI 不同）。这一研究方向在许多涉及联邦或多数据库系统的论文中得以延续；在那里，由于机制可能未知或不兼容，因此需要额外的协调，例如访问票据项。在[10]中，这种方法被应用于包含使用 SI 的站点以及使用确保本地可序列化的算法（如两阶段锁定）的联邦系统。需要注意的是，所有这些工作都与我们的讨论不具可比性，因为在我们的讨论中，不同的并发方法是与每个单独的事务相关联的，而不是与数据的不同部分相关联。
另一种确保混合隔离级别正确性的方法见于[3]，它使用对所需完整性约束的具体知识，并且证明的条件是给定的约束得以保持，而不是本文中更一般的可序列化。
BACKGROUND MATERIAL
Combinatorics definitions
Concurrency Control Algorithms
传统上，数据库并发控制主要基于锁机制。大多数产品允许每个事务显式设置和释放某些锁，并且它们还提供了基于事务声明隔离级别的隐式机制；数据库管理系统（DBMS）引擎随后会在访问的各种数据项上设置锁，并确保不能在任何数据项上持有冲突的锁（如果事务请求了一个无法获得的锁，则会阻塞，直到锁变为可用）。为了确保可接受的性能，需要处理许多微妙的问题，包括检测和处理死锁、在多个粒度上使用锁（以及适当的意向模式以保持它们的协调）以及在使用索引进行谓词读取时适当地设置锁，这会计算出哪些记录匹配查询的 WHERE 子句（见的第 7.8 节）。
对于完全隔离，关键特性是锁必须一直持有，直到事务完成（这意味着锁遵守“两阶段”规则，即一旦事务释放了任何锁，它就不能再获得新的锁）。在本文中，我们将此称为严格两阶段锁定（S2PL）并发控制。SQL 标准使用“SERIALIZABLE”隔离级别这一术语，并不假设使用特定的严格两阶段锁定算法。然而，我们的理论关键依赖于特定机制，即持有提交期间的锁，因此我们将在本文中始终将这种隔离级别称为 S2PL。我们保留“可序列化”这一术语，用于标准理论定义，即多个事务的交错执行，其中一些事务可能被声明为不同的隔离级别，但它们的交错方式与串行执行模式中看到的值相同，并且最终状态也相同。我们注意到，当每个事务都使用 S2PL 隔离机制时，整个执行是可序列化的。
开创性的论文部分上攻击了传统的隔离定义，指出了一种避免所有传统异常执行的算法，然而它允许非可序列化的交错执行，从而可能导致违反完整性约束。这种并发控制算法称为快照隔离（SI），并且已经在许多广泛使用的 DBMS 引擎中实现，例如 Oracle 和 PostgreSQL（然而，这两个产品在应用程序员声明事务应为“可序列化”时，不恰当地使用了该算法）。即将发布的微软 SQL Server 的 Yukon 版本也将提供这种算法，作为一种较弱的隔离级别替代 S2PL。
SI 是一种多版本机制：它同时保留一个数据项的多个版本，并允许事务访问最新值以外的其他版本。在许多实现中，保留版本是为了支持可能的回滚事件。当使用 SI 机制的事务 T 希望访问一个数据项时，它看到的是在 T 开始时最近一次提交的版本（唯一例外是当 T 自身对数据项进行了修改；在这种情况下，T 看到的是它自己最近一次创建的版本）。这种使用 T 开始时的状态（称为 T 的快照）的方式也适用于在评估 WHERE 子句时的索引。实际上，T 的更新被保留在一个私有空间中，直到 T 提交时，T 创建的版本才会被安装并变得对所有事务可见。
为了避免丢失更新，使用 SI 机制的事务 T 在提交时不会被允许覆盖在其活动期间安装的版本（因此这些版本不在 T 的快照中）。这被称为“第一个提交者获胜”规则。尽管中没有提到，但像 Oracle 这样的 SI 实现确保由 SI 事务 T 创建的数据项 x 的版本必须从 T 将其版本移出私有空间的那一刻起，直到（包括）T 提交时版本被安装的瞬间，由排他锁保护。排他锁必须按照正常规则获得（例如，必须在包含粒度上获得意向锁，如果另一个事务持有冲突的锁，则不能获得该锁等）。我们需要这一点，因为它确保 SI 和 S2PL 事务避免与彼此的丢失更新交错。
我们对 SI 机制的描述相当宽泛。我们的结果也适用于各种特殊情况，例如某些 SI 实现不为 SI 事务 T 使用私有空间。相反，它们允许 T 在原地进行更新，T 在创建版本时获取排他锁，并在那时执行不覆盖其他版本的检查；然后 T 持有锁直到提交。这具有上述属性（锁从版本进入公共空间的那一刻起一直持有，直到 T 提交，并且 T 不会提交如果它创建了一个覆盖在其活动期间安装的版本的版本），因此我们的理论将同样适用于这种实现，就像它适用于为每个 SI 事务使用私有空间并在 T 提交时才将版本从私有空间移动到共享数据库的实现一样。
Multiversion serializability theory
GLOBALINTERFERENCETHEORY
暴露边和保护边的定义：
关键事务的定义：
定理 3
对于事务集合 $\T$，一个分配 $\S$ 是可接受的，当且仅当没有 $\IG(\T)$ 中关键点（pivot）在 $\S$ 中。
简言之，所有关键事务用 S2PL 机制，其他事务用 SI 机制，则整个 $\T$ 是可序列化的。
CONCLUSIONS AND FURTHER WORK
我们已经提出了第一套理论框架，用于判断在一个系统中，当不同事务使用不同的并发控制机制时，所有执行是否都可序列化。此外，我们还能够精确地描述哪些事务需要被分配为使用严格的两阶段锁定（S2PL），哪些事务可以被允许使用快照隔离（SI）或 S2PL。这些结果可以用于在数据库管理系统（DBMS）中运行事务，例如即将发布的微软 SQL Server 的 Yukon 版本，该系统提供了两种并发控制机制；这些结果也可以用于在 Oracle 平台上运行事务，其中 SI 是默认提供的，但应用程序可以通过在读取之前设置（并持有）显式的共享锁来获得 S2PL。
在未来的工作中，我们打算研究不同可接受分配的性能影响。直觉上认为，最大可接受分配（尽可能少地使用 S2PL，尽可能多地使用 SI）可能会带来最高的吞吐量，但这需要仔细验证。我们还将寻求将我们的结果整合到工具中，这些工具可以检查混合的应用程序（这些应用程序不是显式的读写序列，而是包含 SQL 语句和控制流），以确定每个程序的合适隔离级别。在更理论的方向上，我们希望将我们的工作扩展到描述可接受分配的场景，其中一些事务使用“读已提交”隔离级别（即，它们在读取之前获取短时间的共享锁），而其他事务则使用 SI 和 S2PL。
