第 6 章 弱隔离与分布式（Weak Isolation and Distribution）

原文：Readings in Database Systems, Fifth Edition (2015)，Chapter 6: Weak Isolation and Distribution，Introduced by Peter Bailis。原书文本采用 CC BY-NC-SA 4.0 许可；本译文按同一许可发布。

导读：Peter Bailis

选读论文

• Atul Adya, Barbara Liskov, and Patrick O'Neil. “Generalized Isolation Level Definitions.” ICDE, 2000.
• Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. “Dynamo: Amazon's Highly Available Key-Value Store.” SOSP, 2007.
• Eric Brewer. “CAP Twelve Years Later: How the ‘Rules’ Have Changed.” IEEE Computer, 45, 2 (2012).

传统数据库智慧认为，可串行化事务是并发编程问题的经典解决方案，但在真实数据库中，情况很少如此。实践中，数据库系统压倒性地实现的是不可串行化的并发控制，让用户暴露在一种可能性之下：他们的事务看起来并不是按某个串行顺序执行的。在本章中，我们讨论为什么这种所谓“弱隔离”的使用如此广泛，这些不可串行化隔离模式实际做了什么，以及为什么推理它们如此困难。

概览与普遍性

即使在数据库系统最早期，系统构建者也已经意识到，实现可串行化是昂贵的（见第 3 章）。要求事务看起来像是顺序执行，会对数据库能够达到的并发程度产生深远影响。如果事务访问数据库中互不相交的数据项集合，那么可串行化实际上是“免费的”：在这些不相交访问模式下，可串行化调度允许数据并行。不过，如果事务竞争同一批数据项，在最坏情况下，系统完全无法并行处理它们。这个性质是可串行化的根本性质，与具体实现无关：因为在所有工作负载下，事务都不能安全地独立取得进展，也就是说它们必须协调，所以任何可串行化实现实际上都可能要求串行执行。实践中，这意味着事务可能需要等待，从而降低吞吐并增加延迟。事务处理专家 Phil Bernstein 指出，与最常见弱隔离级别之一 Read Committed 相比，可串行化通常会在单节点数据库上带来三倍性能惩罚 [29]。取决于实现方式，可串行化还可能导致更多中止、重启事务和/或死锁。在分布式数据库中，这些成本会增加，因为网络通信昂贵，会增加执行串行临界区所需时间，例如持锁时间；我们已经观察到，在不利条件下性能惩罚可能达到多个数量级 [20]。

因此，数据库系统设计者往往没有实现可串行化，而是实现更弱的模型。在弱隔离下，事务不保证观察到可串行化行为。相反，事务会观察到一系列异常，或者说“现象”：这些行为不可能出现在串行执行中。具体异常取决于提供的模型，但示例包括：读取另一个事务产生的中间数据、读取已中止数据、在同一事务执行期间为同一项读取两个或更多不同值，以及由于对同一项的并发写入而“丢失”某些事务效果。

这些弱隔离模式惊人地普遍。在最近一项针对十八个 SQL 和 “NewSQL” 数据库的调查中 [18]，我们发现十八个数据库中只有三个默认提供可串行化，而八个数据库，包括 Oracle 和 SAP 的旗舰产品，完全不提供可串行化！术语使用经常不准确，使这种情况进一步复杂化。例如，Oracle 的 “serializable” 隔离保证实际上提供的是 Snapshot Isolation，也就是一种弱隔离模式 [59]。厂商之间还存在向底线竞赛的现象。轶事般地说，当事务处理市场中的主要玩家厂商 A 把默认隔离模式从可串行化切换到 Read Committed 后，仍然默认使用可串行化的厂商 B 开始在与厂商 A 的 bake-off 中丢失销售合同。厂商 B 的数据库显然更慢，客户为什么要选择 B 而不是 A？毫不意外，厂商 B 现在也默认提供 Read Committed 隔离。

关键挑战：推理异常

弱隔离之所以有问题，主要原因是，取决于应用，弱隔离异常可能导致应用层不一致：在可串行化执行中每个事务所保持的不变量，在弱隔离下可能不再成立。例如，如果两个用户试图同时从一个银行账户取款，而他们的事务运行在一种允许对同一数据项并发写入的弱隔离模式下，例如常见的 Read Committed 模型，那么用户可能成功取出超过账户余额的钱。也就是说，每个事务都读取当前金额，每个事务都计算取款后的金额，然后每个事务都把“新”总额写回数据库。这并不是假想场景。在最近一个生动例子中，攻击者系统性地利用了 Flexcoin 比特币交易所中的弱隔离行为；通过反复、程序化地触发 Flexcoin 应用中的非事务性 read-modify-write 行为，这是 Read Committed 隔离下的漏洞，在更复杂访问模式下 Snapshot Isolation 也会有类似风险，攻击者得以取出超过应得数量的比特币，并使交易所破产 [2]。

也许令人惊讶的是，在我与开发者谈论他们使用事务的情况时，很少有人甚至知道自己运行在不可串行化隔离下。事实上，在我们的研究中，我们发现许多由 ORM 支持的开源应用假设存在可串行化隔离；当它们部署在商品数据库引擎上时，这会导致一系列可能的应用完整性违规 [19]。那些知道弱隔离存在的开发者，倾向于在应用层采用一系列替代技术，包括显式获取锁，例如 SQL “SELECT FOR UPDATE”，以及引入虚假冲突，例如在 Snapshot Isolation 下写入一个 dummy key。这非常容易出错，也抵消了事务概念的许多好处。

不幸的是，弱隔离的规范往往不完整、含糊，甚至不准确。这些规范有很长历史，可以追溯到 20 世纪 70 年代。虽然它们随着时间已有改进，但仍然存在问题。

最早的弱隔离模式是以操作方式定义的：正如我们在第 3 章看到的，Read Committed 等流行模型最初是通过修改读锁持有时长发明出来的 [72]。Read Committed 的定义是：“短时间持有读锁，长时间持有写锁。”

ANSI SQL 标准后来试图为若干弱隔离模式提供一种与实现无关的描述，使其不仅适用于基于锁的机制，也适用于多版本和乐观方法。不过，正如 Gray 等人在 [27] 中描述的，SQL 标准既含糊又规范不足：英文描述存在多种可能解释，形式化也没有捕捉基于锁的实现中的所有行为。此外，ANSI SQL 标准没有覆盖所有隔离模式：例如，在 Gray 等人在 1995 年论文中定义 Snapshot Isolation 之前，厂商已经开始发布提供 Snapshot Isolation 的生产数据库，并把它标记为 serializable！（遗憾的是，截至 2015 年，ANSI SQL 标准仍未改变。）

更复杂的是，Gray 等人 1995 年修订后的形式化也存在问题：它关注与锁相关的语义，并排除了一些在多版本并发控制系统中可能被认为安全的行为。因此，在 Atul Adya 1999 年博士论文 [6] 中，他提出了迄今为止我们拥有的最佳弱隔离形式化。Adya 的论文把多版本序列化图 [28] 的形式化适配到弱隔离领域，并根据这些图上的限制来描述异常。我们收录了 Adya 对应的 ICDE 2000 论文，但隔离爱好者应该阅读完整博士论文。不幸的是，Adya 模型在某些情况下仍然规范不足，例如，如果没有读操作，G0 到底意味着什么？此外，这些保证在不同数据库中的实现也不相同。

即使有完美规范，弱隔离仍然是真正难以推理的挑战。为了判断弱隔离是否“安全”，程序员必须在脑中把应用层一致性关注点翻译成底层读写行为 [11]。这荒谬地困难，即使对经验丰富的并发控制专家也是如此。事实上，人们可能会疑惑：如果可串行化被削弱，事务还剩下什么好处？为什么推理 Read Committed 隔离会比完全没有隔离更容易？考虑到 Oracle 这样的许多数据库引擎都运行在弱隔离下，现代社会到底是如何正常运转的？无论用户是在预订航班、管理医院，还是进行股票交易。文献给出的线索很少，这对事务概念在今天实践部署中的成功提出了严肃疑问。

我遇到过的最有说服力的解释是：弱隔离在实践中似乎“还可以”，因为今天很少有应用经历高度并发。没有并发时，大多数弱隔离实现都会给出可串行化结果。反过来，这也产生了一组富有成果的研究结果。即使在分布式环境中，弱隔离数据库也能交付“consistent”结果：例如，在 Facebook，其最终一致存储返回的结果中只有 0.0004% 是“stale” [106]，其他人也发现了类似结果 [23, 159]。不过，虽然对许多应用来说弱隔离显然不是问题，但它可能成为问题：正如 Flexcoin 例子所说明的，只要存在错误可能性，应用作者就必须警惕地考虑并处理与并发相关的异常，或者明确选择忽略它们。

弱隔离、分布式与 “NoSQL”

随着互联网规模服务和云计算兴起，弱隔离变得更加普遍。正如我之前提到的，分布式会加剧可串行化的开销；在部分系统故障，例如服务器崩溃时，事务可能无限期停滞。随着越来越多程序员开始编写分布式应用并使用分布式数据库，这些关注点变成了主流问题。

过去十年中，人们引入了一系列针对分布式环境优化的新数据存储，统称为 “NoSQL”。“NoSQL” 这个标签不幸地过载了，它指代这些存储的许多方面，从不支持字面意义上的 SQL，到更简单的数据模型，例如键值对，再到很少或完全没有事务支持。今天，就像类 MapReduce 系统一样（第 5 章），NoSQL 存储正在加入许多这些功能。不过，一个值得注意的根本差异是，这些 NoSQL 存储经常专注于通过更弱模型提供更好的操作可用性，并明确关注容错。（有点讽刺的是，虽然 NoSQL 存储通常与使用不可串行化保证相关联，经典 RDBMS 默认也并不提供可串行化。）

作为这些 NoSQL 存储的例子，我们收录了 Amazon 的 Dynamo 系统论文，该论文发表于 SOSP 2007。Dynamo 被引入，是为了给 Amazon 购物车提供高可用、低延迟操作。这篇论文在技术上很有趣，因为它结合了若干技术，包括 quorum replication、Merkle tree anti-entropy、一致性哈希和版本向量。这个系统完全非事务化，不提供任何类型的原子操作，例如 compare and swap，并依赖应用作者来调和发散更新。在极限情况下，任何节点都可以更新任何项（在 hinted handoff 下）。

通过使用合并函数，Dynamo 采用了一种“乐观复制”策略：先接受写入，再调和发散版本 [138, 70]。一方面，把一组发散版本呈现给用户，比像 Read Committed 隔离那样简单丢弃某些并发更新更友好。另一方面，程序员必须推理合并函数。这引发许多问题：什么才是应用合适的合并？如何避免丢弃已提交数据？如果某个操作本来就不应该并发执行怎么办？一些开源 Dynamo 克隆，例如 Apache Cassandra，不提供合并算子，而是简单地根据数值时间戳选择一个“获胜”写入。另一些系统，例如 Basho Riak，采用了可自动合并数据类型的“库”，例如计数器，称为 Commutative Replicated Data Types [142]。

Dynamo 也不承诺读取的新鲜度。相反，它保证如果写入停止，最终某个数据项的所有副本都会包含同一组写入。这种最终一致性是一个非常弱的保证：技术上，一个最终一致数据存储可以在不确定长的时间内返回陈旧数据，甚至垃圾数据 [22]。实践中，数据存储部署经常返回较新的数据 [159, 23]，但即便如此，用户仍必须推理不可串行化行为。此外，在实践中，许多存储提供被称为“会话保证”的中间隔离形式，它确保用户能读到自己的写入，但不保证读到其他用户的写入；有趣的是，这些技术在 20 世纪 90 年代初作为移动计算 Bayou 项目的一部分被开发出来，最近又重新受到关注 [154, 153]。

权衡与 CAP 定理

我们还收录了 Brewer 对 CAP 定理的 12 年回顾。CAP 定理最初是在 Brewer 构建 Inktomi 之后提出的，Inktomi 是最早的可扩展搜索引擎之一。Brewer 的 CAP 定理简洁描述了协调需求，或者说“可用性”，与可串行化等强保证之间的权衡。虽然更早的结果已经描述过这种权衡 [91, 47]，但 CAP 成为 21 世纪中期开发者的集结口号，并产生了相当大影响。Brewer 的文章简要讨论了 CAP 的性能含义，以及在不依赖协调的情况下维持某些一致性标准的可能性。

可编程性与实践

正如我们已经看到的，弱隔离是真正的挑战：它在性能和可用性上的好处意味着，尽管我们对其行为了解很少，它仍然在部署中极为流行。即使拥有完美规范，现有弱隔离表述仍然会极难推理。为了判断弱隔离是否“安全”，程序员必须在脑中把应用层一致性关注点翻译成底层读写行为 [11]。这荒谬地困难，即使对经验丰富的并发控制专家也是如此。

因此，我相信存在一个重要机会：研究那些不承受可串行化的性能和可用性开销、但比现有保证更直观、更可用、更可编程的语义。历史上，弱隔离一直极难推理，但这并不必然如此。我们和其他人发现，若干高价值使用场景，包括索引和视图维护、约束维护，以及分布式聚合，经常实际上并不需要协调就能获得“正确”行为；因此，对于这些使用场景，可串行化是过度的 [17, 21, 136, 142]。也就是说，通过向数据库提供关于应用的额外知识，数据库用户可以鱼与熊掌兼得。进一步识别并利用这些使用场景，是一个非常适合研究的领域。

结论

总结来说，弱隔离之所以普遍，是因为它有许多好处：更少协调、更高性能和更大可用性。不过，它的语义、风险和使用情况，即使在学术语境中也理解不足。考虑到大量研究都投入到可串行化事务处理，而许多人认为这已经是“已解决问题”，这种情况尤其令人困惑。可以说，弱隔离甚至更值得接受这种彻底处理。正如我强调的，仍然存在许多挑战：现代系统到底如何正常工作？用户又应该如何编写弱隔离程序？目前，我给出以下几点启示：

• 不可串行化隔离由于其与并发相关的好处，在实践中非常普遍，无论是在经典 RDBMS 中，还是在最近兴起的 NoSQL 系统中。
• 尽管如此普遍，许多现有不可串行化隔离表述仍然规范很差，并且难以使用。
• 对新形式弱隔离的研究表明，可以在不付出可串行化代价的情况下，保留有意义的语义并改善可编程性。