数据库系统中的协调规避

论文地址： 数据库系统中的协调规避 – Bailis et al. 2014

本文的标题正是我们本周一直关注的主题——如何减少分布式系统所需的协调量。（前两周刚花了两周时间来研究这种协调在需要时的成本和复杂性，这似乎是合适的）。关于TPC-C基准，有一个特别令人震惊的结果——在从一个全新的角度看待这个问题之后，在不破坏TPC-C所要求的任何不变量的情况下，作者能够创建一个线性可伸缩的系统，其中200台服务器处理1270万tps，大约是次优系统的25倍。

当我读到像谷歌和亚马逊这样的大型系统论文时，让我印象深刻的一件事是，分布式系统设计涉及到许多权衡，这些公司的运营规模使得他们可以构建定制的分布式系统，使这些权衡以最适合他们的工作负载的方式进行。不是所有的人都有同样的奢侈能够做到这一点！但正如我们在Bloom and CALM和CRDTs中所看到的，我们可以尝试以最小化协调需求的方式构建应用程序。应用程序和底层数据存储之间的这种协作似乎是解锁下一级进度的关键。这就是贝里斯等人的研究领域。本文重点研究。

最小化并发执行操作之间的协调或阻塞通信是最大限度地提高数据库系统的可伸缩性、可用性和高性能的关键。然而，无限制的无协调执行可能会损害应用程序的正确性或一致性。什么时候需要协调才能正确？可序列化事务的经典用法足以维护正确性，但并非所有应用程序都需要，从而牺牲了潜在的可伸缩性。在本文中，我们开发了一个形式化的框架，不变合流，它决定了应用程序是否需要协调才能正确执行。

当应用程序程序员以不变量的形式表达他们的正确性标准时，不变量合流框架能够确定哪些操作可以在没有协调的情况下安全地执行。

不变量定义为副本上数据库状态的谓词-给定数据库的状态，它可以是真或假。例如，外键约束。如果副本上的所有不变量均为真，则称副本不变量有效（I-valid）；如果所有副本始终包含I-valid状态，则称系统全局I-valid。在系统模型中…

每个事务在其本地副本上提交，每个事务的结果反映在事务的本地服务器状态中。事务完成后，服务器交换状态，并在应用合并运算符后聚合到同一状态。稍后在任一服务器上执行的任何事务都将获得包含两个事务的效果的副本。

当应用程序需要协调以确保正确性时，它既依赖于它的不变量，也依赖于它的事务。取一个不变量I和一组事务T。假设不变量保持的起始状态（I-valid）。每个事务都应该把我们带到一个新的状态，在这个状态下，不变量也会保持不变。通过将这些链接在一起，我们可以推断数据库可能进入的状态，包括合并在不同副本上启动的事务时的状态。

如果给定一个不变的I和一组事务T（带有合并函数T），存在一个（部分有序的）事务和合并函数调用序列，从而产生Si，并且事务执行或合并调用产生的每个中间状态也是I-valid，则Si是I-T-可达状态。我们称这些以前的州为祖先州。注意，每个祖先状态要么是I-T-reachable，要么是初始状态。

本文的中心概念I-confluence现在可以定义为：

如果对于具有共同祖先状态的所有I-T-可到达状态Di、Dj，与Dj合并的Di是I-有效的，则事务集T相对于不变I是I-合流的。

粗略地翻译一下，我们可以让状态发散，然后再将其与合并操作结合起来，不变量将始终保持不变。如果我们有I-合流，那么我们不需要协调：

一个全局I有效的系统可以执行一组具有协调自由、事务可用性和收敛性的事务T，前提是且仅当T是I合流的I……如果I合流成立，则存在一个正确的、无协调的事务执行策略；如果不是，则任何可能的实现都不能保证这些提供的不变量和事务的属性。

如果I-合流不成立，那么至少有一个事务序列将不得不放弃可用性或协调自由，否则系统将不得不放弃合流。考虑到这些选择，加入一些协调似乎是最好的选择！非正式规则是“只有当所有本地提交决策都全局有效时，才能避免协调。”

I-confluence分析独立于任何给定的实现，有效地将先前关于可伸缩性、可用性和低延迟的讨论“提升”到应用程序级别（即，不是“I/O”）的正确性。这提供了对无协调执行的含义的有用处理，而无需对物理数据位置和服务器数量等低级属性进行推理。

这当然依赖于开发人员正确地指定不变量：

I-合流分析只防止违反任何提供的不变量。如果不变量的指定不正确或不完整，则I合流数据库系统可能会违反应用程序级的正确性。如果用户不能保证其不变量和操作的正确性和完整性，他们应该选择更保守的分析或机制，例如采用可序列化的事务。因此，我们开发的I-confluence分析为开发人员提供了一个强大的选择，但只有在正确使用的情况下。如果使用不当，I-confluence会导致错误的结果，或者，如果根本不使用，开发人员必须使用现有的替代方法。

语言设计支持更自动化的I-合流分析是未来研究的一个领域。作者发现，手工进行I-confluence分析“并不琐碎，但在实践中是可行的”

针对I-合流分析了几种SQL约束。例如，一个非空约束很容易被证明是I-合流的。主键和唯一约束在insertion下不是I-confluent，但它们在reads和deletes下。如果将唯一值的创建委托给数据库，并且它有一个确保副本之间唯一性的方案（例如，通过包含唯一副本id），那么插入也可以使I-confluent。外键约束下的插入和级联删除一样是I-合流的，但是任意删除记录是不安全的。

论文的第2节很好地展示了协作的成本有多高，而且随着协作伙伴之间的RTT的增加和参与者数量的增加，协作成本会越来越高。一个能够在本地网络上的两个服务器之间协调超过1000 tps的系统，当在所有8个EC2可用性区域进行协调时，可以看到性能下降到只有2 tps。我假设你已经确信协调是很昂贵的，接下来我们来看看我们能做些什么来避免它。

为了避免不断增长的不可变集，许多数据库都使用了其他策略，如最后一个写入获胜：

…如果我们使用“last writer wins”合并策略实现用户的帐户余额，则执行两个并发取款事务可能会导致数据库状态仅反映一个事务（丢失更新异常的典型示例）。为了避免这些异常的变体，许多乐观的、无协调的数据库设计都建议使用抽象数据类型（adt），为各种用途（如计数器、集合和映射）提供合并函数，以确保所有更新都反映在最终的数据库状态中。例如，数据库可以通过记录每个事务在计数器上执行增量操作的次数来表示简单的计数器ADT。I-合流分析也适用于这些adt及其相关不变量。

例如，行级别的“大于”阈值不变量对于计数器递增和赋值是I-confluent，但对于递减则不是。

如果用户希望“阅读他们的文章”或希望获得更强大的“会话”保证（例如，在每个用户或每个会话的基础上保持最近状态），他们必须保持与给定（一组）副本的亲和力或“粘性”。这些保证也可以在I-confluence模型中表示，并且不需要在不同用户或会话的事务之间进行协调。

对于这个理论来说，当作者在TPC-C新订单基准工作负载上尝试这些想法时，发生了什么？

TPC-C基准是数据库并发控制的金标准，近年来已成为衡量分布式数据库并发控制性能的标准。TPC-C实际需要多少协调来执行合规性？

在TPC-C中发现的12个不变量中，有10个是I-合流的！这意味着这十个项目存在一些不需要协调的执行策略。当然，您仍然需要构建一个实现这一点的实现。

作为一种尊重外键和物化视图不变量的无协调执行策略，我们可以使用RAMP事务，它提供跨服务器的原子可见事务更新，而不依赖于正确性的协调。简言之，RAMP事务使用有限的多版本控制和元数据来确保读写器始终可以并发进行：任何读操作与另一个客户端对同一项的写操作重叠的客户端都可以使用存储在项中的元数据从相应的服务器获取任何“丢失”的写操作。

（我们将在早报的未来版本中更详细地讨论RAMP交易）。

对于TPC-C中剩下的两个不变量，其中一个与基准允许异步和批处理模式运行的事务相关。这就留下了一个约束，即新的订单id是按顺序分配的。这里总是有可能回到可串行化的隔离，但是作为一个更有效的解决方案，作者引入了一个间接层，并将新的订单ID分配推迟到提交时间。

实际上，新的订单ID分配可以在提交时使用嵌套的原子事务，任何两个事务之间的所有协调都限制在一个服务器上。

听起来像个计划…

随后，我们在分布式数据库原型中实现了上述执行策略，以量化TPC-C新订单中与协调相关的开销。简言之，避免协调查询计划在200台服务器上线性扩展到每秒超过1270万个事务，同时大大优于分布式两阶段锁定。

总之：

这些结果开始量化避免并发控制的协调效果。如果考虑到应用程序级的不变量，数据库只需在必要时付出协调的代价。我们感到惊讶的是，“评估OLTP系统性能的当前行业标准”如此易于协调，避免了执行，至少是按照官方TPC-C规范定义的遵从执行…。有趣的是，我们与现实世界的应用程序程序员和数据库开发人员的对话和经验并没有发现与我们在这里所研究的完全不同的不变量。通过一个简单的思维实验，识别社交网站所需的不变量，可以得到许多不变量，但没有一个是特别奇特的（例如，用户名唯一性、更新之间的外键约束、隐私设置）。然而，我们认为对现实世界不变量的进一步研究是未来研究的一个必要领域。在此期间，这些初步结果暗示了避免协调的可能性以及如果应用程序不合流的话协调的成本。