Adya'99-Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed

摘要

当前的商业数据库允许应用程序开发人员为了性能而牺牲一致性。然而，现有的弱一致性级别的定义要么不够精确，要么不允许使用诸如乐观锁等高效的实现技术。排除这些技术尤其不幸，因为商业数据库支持乐观机制。此外，乐观锁很可能成为未来地理分布和移动系统中首选的实现技术。

本论文首次提出了现有 ANSI 隔离级别的独立于实现的规范，以及在商业系统中广泛使用的若干级别的规范，例如，游标稳定性、快照隔离。它还以独立于实现的方式为基于谓词的操作指定了各种保证。定义了两个新级别，为应用程序编写者提供有用的一致性保证；一个是确保一致读取的最弱级别，而另一个则捕获了悲观实现所提供的某些有用的一致性属性。我们使用基于图的方法以简单直观的方式定义不同的隔离级别。

论文描述了在分布式客户端-服务器环境中支持不同弱一致性级别的新实现技术。这些机制基于乐观锁，并利用多部分时间戳。提出了一种新技术，允许多部分时间戳随着系统中客户端和服务器数量的增加而良好扩展；该技术利用松散同步的时钟来从多部分时间戳中移除旧信息。

本论文还展示了一项模拟研究的结果，以评估我们的数据传输客户端-服务器系统中乐观方案的性能。结果表明，对于低争用工作负载，提供可串行化相对于提供较低一致性保证的机制的成本可以忽略不计；此外，即使对于中等到高争用的工作负载，可串行化的成本也很低。模拟研究还表明，我们基于多部分时间戳的机制在为只读和执行事务提供强一致性保证的同时，对 CPU、内存和网络成本的影响非常小。

致谢

我要感谢我的研究导师，Barbara Liskov，在她作为我研究生期间，为我提供了持续的支持和建议。我从她那里学到了许多关于如何进行良好研究的原则，特别是关于将系统设计的理论方面与实际实现结合起来。

我的论文委员会成员为改进这项工作的内容和展示提出了许多优秀的建议。John Guttag 和 John Chapin 提出了有助于阐明论文不同部分的建议。Jim Gray 提供了关于当前数据库系统的极其有用的反馈，这帮助我解决了定义弱一致性级别时的一些重要问题。

许多人为我在麻省理工学院的研究生生活提供了愉快的体验。如果我是一个更好的计算机科学家和更好的人，那是因为我的朋友和同事的陪伴和建议。他们对我产生了积极的影响，并在许多方面丰富了我的生活。

我在编程方法学小组的同事们提供了一个刺激的技术讨论环境。通过与 Andrew Myers 和 Miguel Castro 的互动，我学到了许多关于计算机系统的有趣方面。我与 Phillip Bogle、Chandrasekar Boyapati、Mark Day、Robert Gruber、Sanjay Ghemawat、Umesh Maheshwari 和 Quinton Zondervan 的讨论也对我大有裨益。Dorothy Curtis 和 Paul Johnson 在设备和软件方面多次帮助我。Kavita Bala、Radhika Nagpal 以及每个小组成员总是愿意参加我的练习演讲，并提供反馈以改进我的演讲。

我将永远珍惜与 PM 小组成员愉快轻松的经历。我喜欢与 Andrew Myers 一起策划电影之夜和解谜，与 Jason Hunter 讨论《星球大战》，与 Arvind Parthasarathi 和 Doug Wyatt 交换友好的玩笑，以及与 Chandrasekar Boyapati、Umesh Maheshwari、Quinton Zondervan 和小组中的其他人进行无数次的知识性对话。

Phil Bogle 和 Sudhendu Rai 一直是我不断鼓励和灵感的源泉。Sudhendu 关于研究和哲学的建议在改善我对生活的看法方面发挥了重要作用。Ujjwal Sinha 和 Ananda Sen Gupta 总是在我需要支持时出现。他们是极好的伙伴，我和他们一起看电影、聊天、短途旅行都很开心。Aman Rustagi、Sreeram 和 Sandeep Gupta 是我一直珍视的朋友，他们总是给予我美好的祝愿，我喜欢和他们在一起的时光。

言语无法表达我对父母的感激之情，他们应该为我生活中取得的任何积极成就获得赞誉。他们一直支持我所有的努力，并耐心地等待我完成博士学位。最后但同样重要的是，我的妻子 Vandana，在我努力完成论文的过程中一直非常支持和鼓励我。

Introduction

Existing Definitions

Proposed Specifications for Existing Isolation Levels

System Model and Terminology

Database Model

Transaction Histories

Predicates

Conflicts and Serialization Graphs

定义 2：Directly Read-Depends

$T_{j}$ 对 $T_{i}$ 直接读依赖，当且仅当 $T_{j}$ 对 $T_{i}$ 直接项读依赖或直接谓词读依赖。记为 $T_{i} \overset{wr}{\to} T_{j}$ 。

直接项读依赖（Directly item-read-depends）：我们说，如果 $T_{i}$ 安装了某个对象版本 $x_{i}$ 并且 $T_{j}$ 读取了 $x_{i}$ ，那么 $T_{j}$ 直接项读依赖于 $T_{i}$ 。

直接谓词读依赖（Directly predicate-read-depends）：如果 $T_{j}$ 执行了一个操作 $r_{j} (P : Vset (P))$ 并且 $x_{i} \in Vset (P)$ ，那么我们说事务 $T_{j}$ 直接谓词读依赖于 $T_{i}$ 。

Isolation Levels for Committed Transactions

Isolation Level PL-1

G0：写环，即完全由 $ww$ 边构成的环。

PL-1 不允许出现 G0。

Isolation Level PL-2

G1a: Aborted Reads.
G1b: Intermediate Reads.
G1c: Circular Information Flow.
G1-predA: Non-atomic Predicate-based Reads.
G1-predB: Non-atomic Predicate-based Reads with respect to Transactions.

Isolation Level PL-3

G2: Anti-dependency Cycles.

Isolation Level PL-2.99

G2-item: Item Anti-dependency Cycles.

Summary of Isolation Levels

异象编号	别称	描述
G0	Write Cycles	完全由 $ww$ 边构成的环。
G1a	Aborted Reads	读取已回滚的事务写的值。
G1b	Intermediate Reads	读到的值随后被同一事务覆盖。
G1c	Circular Information Flow	完全由依赖边组成的环。
G2	Anti-dependency Cycles	环包含一个或多个 $rw$ 边。
G2-item	Item Anti-dependency Cycles	环包含一个或多个项 $rw$ 边。

级别	禁止的现象	非正式描述（ $T_{i}$ 只有在以下情况下才能提交）
PL-1	G0	$T_{i}$ 的写操作完全隔离于其他事务的写操作
PL-2	G1	$T_{i}$ 仅读取了在 $T_{i}$ 提交时已经提交的事务的更新（以及 PL-1 的保证）
PL-2.99	G1, G2-item	$T_{i}$ 在数据项方面完全隔离于其他事务，且基于谓词的读取保证 PL-2
PL-3	G1, G2	$T_{i}$ 的所有操作都在任何其他事务的所有操作之前或之后

Mixing of Isolation Levels

Guarantees to Transactions in Mixed Systems

在混合系统中，每个事务在启动时指定其隔离级别；此信息作为历史记录的一部分被维护（在我们的示例中，我们不使用任何符号，而是在文本中简单地指示不同事务的级别），并用于构建混合序列图（MSG）。与 DSG 一样，MSG 包含对应于已提交事务的节点和对应于冲突的边；然而，只有与事务级别相关或必须的（obligatory）冲突才作为边出现在图中。如果事务 $T_{i}$ 在比事务 $T_{j}$ 更高的级别运行， $T_{i}$ 与 $T_{j}$ 冲突，且该冲突与 $T_{i}$ 的级别相关，则事务 $T_{i}$ 与事务 $T_{j}$ 有必须的冲突。例如，从 PL-3 事务到 PL-1 事务的反依赖边是必须的边，因为覆盖读取在 PL-3 级别很重要。

边的添加方式如下：由于写依赖在所有级别都相关，我们保留所有此类边。对于 PL-2 或 PL-3 节点 $T_{i}$ ，由于读取很重要，我们添加进入 $T_{i}$ 的读依赖边。同样，我们添加从 PL-3 事务到其他节点的所有出边的反依赖边。

现在我们可以定义混合历史记录的正确性：

定义 10：混合正确 Mixing-Correct

如果 $MSG (H)$ 是无环的，并且对于 PL-2 和 PL-3 事务不出现现象 G1a 和 G1b，则历史记录 H 是混合正确的。

上述定义可以重新表述为隔离定理 [GR93] 的类似物：

混合定理：

如果历史记录是混合正确的，则每个事务都获得与其级别相关的保证。

上述定理在历史记录级别上成立，与同步实现方式无关。注意，提供给每个级别的保证是相对于 MSG 的。原因是 MSG 考虑了其他级别事务的存在，而 DSG 只是简单地用所有边构建。正如我们下面讨论的，如果 PL-1 和 PL-2 事务“知道”它们在做什么，MSG 对于确定正确性是有用的，而 DSG 在不对较低级别事务的操作做出任何假设的情况下确保正确性。

混合系统也可以使用锁定（使用标准的短读/写锁组合）来实现，所有由锁定系统生成的历史记录都是混合正确的。现象 G1a 和 G1b 不能出现在 PL-2 或 PL-3 中，因为这样的事务只读取已提交事务的更新。此外，MSG 中没有环，因为存在以下属性：如果 MSG 中有从 $T_{i}$ 到 $T_{j}$ 的边，则意味着 $T_{j}$ 在锁定实现中在 $T_{i}$ 之后提交。对于写依赖边，长写锁确保 $T_{i}$ 被延迟直到 $T_{j}$ 提交。对于 PL-2 和 PL-3 事务的读依赖边，由于（至少）短读锁被获取，从 $T_{j}$ 到 $T_{i}$ 的读依赖边意味着 $T_{i}$ 被延迟直到 $T_{j}$ 提交。同样，从 PL-3 事务的反依赖边，PL-3 事务 $T_{j}$ 获取长读锁，从而确保如果事务 $T_{i}$ 覆盖 $T_{j}$ 的更新，则 $T_{i}$ 将在 $T_{j}$ 之后提交。因此，如果 MSG 中存在形式为 T1, T2, ..., Tn, T1 的环，则会导致矛盾，即 T1 在 T2 之前提交，T2 在 T1 之前提交。因此，MSG 必须是无环的，即任何由锁定实现允许的历史记录都是混合正确的。

混合系统也可以使用其他并发控制技术来实现。例如，乐观实现将尝试将每个提交事务放入基于其自身要求（针对其级别）和对更高级别运行事务的义务的序列中，并且如果无法做到这一点，则会中止该事务。第 5 章中提出了一个混合正确的乐观实现。

Consistency of Database State

即使一个历史 $H$ 满足混合定理，这并不意味着 $H$ 中的 PL-3 事务观察到一个一致的数据库状态，因为低级别的事务可能已经不一致地修改了已提交的状态。这个属性对于 [GR93] 中给出的隔离定理也是成立的。

例如，假设一个数据库包含三个对象 $x$ ， $y$ 和 $z$ 使得 $x_{0} = 25$ ， $y_{0} = 20$ ，而 $z_{0}$ 的值是 50。以下历史被执行：

begin m a t r i x H_{m i x i n g} : r_{1} (x_{0}, 25) r_{1} (y_{0}, 20) r_{1} (z_{0}, 50) r_{2} (x_{0}, 25) w_{1} (x_{1}, 40) w_{1} (y_{1}, 10) c_{1} r_{2} (y_{1}, 10)

在这个历史中， $T_{1}$ 和 $T_{3}$ 在 PL-3 下提交，而 $T_{2}$ 在 PL-2 下提交。这种历史在基于锁的实现中是可能的，其中 $T_{2}$ 在 $x$ 和 $y$ 上获取了短的读锁，而 $T_{1}$ 、 $T_{2}$ 和 $T_{3}$ 对所有其他访问获取了长的读/写锁。历史 $H_{m i x i n g}$ 的 DSG（数据依赖图）和 MSG（消息图）在图 3-7 中展示；为了简单起见，我们没有在图中展示 $T_{0}$ 。

假设事务正在维护一个不变式 $α + y \leq z$ 。 $T_{1}$ 和 $T_{2}$ 都根据它们的读取更新数据库以保持这个不变式。然而，由于 $T_{2}$ 基于读取事务 $T_{1}$ 的部分效果来做出决策，它不一致地更新了数据库。因此，尽管 $T_{3}$ 提供了 PL-3 隔离，它观察到了一个被破坏的不变式。

正如 [GR93] 中所述，为了确保 PL-3 事务观察到一个一致的状态，低级别的事务必须“知道”它们在做什么，即，即使它们观察到一个不一致的状态，它们也必须以某种方式一致地更新数据库。同样，一个无环的 MSG 确保如果每个低级别的事务在代码中正确处理不一致性，事务将更新并观察到一个一致的数据库状态。因此，尽管 $H_{m i x i n g}$ 是混合正确的，但由于 $T_{2}$ 在 PL-2 下提交并破坏了数据库一致性，它并没有导致 $T_{3}$ 观察到可串行化的状态。另一方面，DSG 考虑了所有边，因此在历史 $H_{m i x i n g}$ 中产生了一个循环（见图 3-7）。

Guarantees to SQL Statements

在大多数商业数据库系统中，使用像 SQL 这样的语言来访问和修改数据库对象。这些系统确保某些保证适用于事务执行的 SQL 语句。我们现在描述如何在我们的框架中提供此类保证。考虑以下 SQL 应用程序代码：

1	`INSERT INTO Highcom SELECT ename, salary, commission FROM Employee WHERE commission > 0.25 * salary UNION SELECT ename, salary, commission FROM Manager WHERE dept = Sales`

EagleBear2002 的博客

Adya'99-Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed

Introduction

Existing Definitions

Proposed Specifications for Existing Isolation Levels

System Model and Terminology

Database Model

Transaction Histories

Predicates

Conflicts and Serialization Graphs

Isolation Levels for Committed Transactions

Isolation Level PL-1

Isolation Level PL-2

Isolation Level PL-3

Isolation Level PL-2.99

Summary of Isolation Levels

Mixing of Isolation Levels

Guarantees to Transactions in Mixed Systems

Consistency of Database State

Guarantees to SQL Statements

Guarantees to SQL Statements

Correctness and Flexibility of the New Specifications

Consistency Guarantees for Executing Transactions

Summary

Specifications for Intermediate Isolation Levels

Optimistic Implementations for Client-Server Systems

Experimental Framework

Performance Results

Conclusions