摘要
快照隔离 (SI) 是一种多版本并发控制算法，最早由 Berenson 等人 [1995] 描述。SI 之所以有吸引力，是因为它提供了一种可以避免许多常见并发异常的隔离级别，并且已由 Oracle 和 Microsoft SQL Server 实现（有一些细微的差别）。SI 并不保证在所有情况下都可序列化，但例如，TPC-C 基准测试应用程序 [TPC-C] 在 SI 下执行时不会出现序列化异常。所有主要数据库系统产品都提供默认的非序列化隔离级别，这些级别通常比 SI 更常遇到序列化异常，我们怀疑许多大型站点每天都会因此发生大量隔离错误，导致数据仓库应用程序中有时会出现损坏的数据。较低隔离级别的经典理由是，当应用程序被证明不会导致严重错误时，可以在这些级别下运行以提高效率，但供应商很少或根本没有向应用程序程序员和 DBA 提供有关如何避免此类错误的指导。本文提出了一种理论，用于描述在 SI 下何时会出现应用程序的非序列化执行。在文章的最后，我们将应用该理论来证明 TPC-C 基准测试应用程序在 SI 下没有序列化异常，然后讨论如何将此证明推广到其他应用程序。我们还讨论了如何修改在 SI 下不可序列化的应用程序的程序逻辑，以保证可序列化性。
作者：
- ALAN FEKETE, University of Sydney
- DIMITRIOS LIAROKAPIS, ELIZABETH O’NEIL, and PATRICK O’NEIL, University of Massachusetts
- DENNIS SHASHA, Courant Institute
MOTIVATION AND PRELIMINARIES
许多数据库研究人员认为并发控制是一个已解决的问题，因为存在一组经过验证的可序列化充分条件。问题是这些充分条件可能导致并发控制瓶颈，因此大多数商业系统默认提供较低隔离级别并发设置，而这些设置不能保证可序列化 [Berenson et al 1995]。这给理论家提出了一项新任务：发现如何以最低成本保证这种较低隔离级别的正确性。在本文中，我们将讨论称为快照隔离（SI）的隔离级别。SI 在下面的第 1.1 节中定义，是一种多版本并发控制机制，可防止许多经典的序列化异常，但在某些情况下允许非序列化执行。由于其良好的性能，尤其是它不会阻止读取，它被广泛使用；一些主要供应商仅支持 SI 而不是传统的可序列化性。
本文的贡献是为数据库管理员提供工具来确定特定数据库应用程序（由几个在快照隔离下运行的交互程序组成）是否只会产生可序列化执行奠定理论基础。如果情况并非如此，我们将提供有关如何修改应用程序以保证可序列化执行的指导。为了证明我们理论的适用性，我们展示了如何分析在 Oracle DBA 上运行的 TPC-C 应用程序，该应用程序被指定为 SERIALIZABLE 隔离级别（快照隔离的一种形式）。我们注意到，当 TPC-C 基准的两名官方审计员被要求证明 Oracle SERIALIZABLE 隔离级别在 TPC-C 应用程序上以可序列化的方式起作用时，他们通过“认真思考”来做到这一点（Francoi 的 Raab 和 Tom Sawyer，个人通讯，1995）。值得注意的是，没有理论手段来证明这样的事实，我们在本文中纠正了这一缺陷。
在下文中，我们定义了一个交易应用程序，该应用程序包括一组交易程序，这些程序为企业执行某种集成的服务集，例如，执行在银行的收银员窗口发生的所有服务：存款、提款、转账等。我们假设我们已提供交易程序的所有程序逻辑，其中每一个都包含许多访问和更新数据库的声明，这些声明位于开始和结束（提交或中止）每个事务执行的操作之间。然而，这些事务程序不应被认为是在特定的、命名的数据项上直线执行，尽管教科书中通常假设这种情况，其中多事务历史符号是由（1.1）中给出的历史定义的。
\[ R_1(X)R_2(X)W_2(X)C_2W_1(X)A_1 \]
虽然这种符号对于表示事务程序的特定执行很有用，但我们通常无法在编译时分析程序以确定将访问哪些特定数据项。此类程序是用执行 SQL 陈述的编程语言实现的，并用适当的参数（例如，银行应用程序中的客户 ID）来确定要访问哪个客户帐户。程序检索和更新由这些参数确定的数据项，但编译时分析无法知道将访问哪些特定数据项，因为不同的数据项将由不同的参数值确定。此外，对所传递的参数和程序在数据库中访问的其他数据进行条件测试可能会导致分支，这可能会导致许多不同的执行，访问数据库中完全不同的部分，因此直线执行同样是不现实的。我们的模型相当通用，但对于我们理论的实际应用来说，通常会避免程序中不同的逻辑分支产生功能上不同的事务任务。相反，我们通常期望每个程序执行执行单个事务类型的逻辑，与 TPC-C 基准规范[TPC-C]中描述的事务类型相当。
Versioned Historiesand Snapshot Isolation
为了推理在 SI 下在数据库上执行一组应用程序的过程，我们需要一个足够丰富的历史形式表示，以描述数据项的多个版本和面向集合的数据访问。我们使用 Adya 等人 [2000] 的模型。（不过，我们的许多符号和一些定义与 Adya 等人 [2000] 的有所不同。）
TRANSACTIONAL HISTORY THEORY
在本节中，我们将根据执行模型来开发该理论，在该模型中，对数据项执行读取和写入，并且谓词读取返回一组数据项标识。在抽象理论中，我们不需要指定任何特定的数据项粒度。但是，在第 4 节中，当我们将该理论应用于 TPC-C 时，我们将数据项视为一行中的单个字段，那些喜欢更具体概念的读者也可以自由地将字段粒度用于其他部分。
