calvin

卡尔文：快速分布式事务的分区数据库系统

摘要

许多分布式存储系统通过分区和复制实现了高吞吐量的数据访问，每个系统都有自己的优势和权衡。但是，为了实现高可扩展性，当今的系统通常会减少事务支持，不允许单个事务跨越多个分区。 Calvin是一个实用的事务调度和数据复制层，它使用确定性排序保证显著降低与分布式事务一起处理通常令人望而却步的争用成本。与以前的确定性数据库系统原型不同，Calvin支持基于磁盘的存储，在商品计算机群集上近乎线性地扩展，并且没有单点故障。通过复制事务输入而不是效果，Calvin还能够支持多个一致性级别（包括跨地理距离副本的Paxos基础强一致性），而无需事务吞吐量成本。

数据和定义

C.2.4[Distributed Systems]:分布式数据库

H.2.4[Database Management]:系统-并发，分布式数据库，事务处理

关键字

确定性、分布式数据库系统、复制、事务处理

背景和简介

分布式数据库系统设计的几种当前趋势之一是放弃支持传统的ACID数据库事务。一些系统，如亚马逊的Dynamo[13]， MongoDB[24]，CouchDB[6]和Cassandra[17]不提供任何事务支持。其他事务仅提供有限的事务性，例如单行事务更新（例如 Bigtable[11]）或访问仅限于数据库小子集(例如Azure[9]、 Megastore[7]和 Oracle NoSQL Database[26]) 的事务。这些系统不支持完全 ACID 事务的主要原因是提供线性外向可扩展性。其他系统（例如 VoltDB [27， 16]）支持完整的 ACID，但在处理访问跨多个分区数据的事务时停止（或限制）并发事务执行。

减少事务支持大大简化了构建线性可扩展分布式存储解决方案的任务，这些解决方案旨在为"令人尴尬的可分区"应用服务。但是，对于不容易分区的应用程序，确保原子性和隔离性的负担通常由应用程序程序员承担，从而导致代码复杂性增加、应用程序开发速度变慢以及客户端事务调度性能低。

Calvin 旨在与非事务存储系统一起运行，将其转换为提供高可用性和完整 ACID 事务的共享无（近）线性可扩展的数据库系统。这些事务可能跨跨共享无群集的多个分区。Calvin 通过提供存储系统上方的层来完成此目的，该层用于处理分布式事务的调度以及系统中的复制和网络通信。在面对分布式事务时允许可伸缩性的关键技术特性是能够消除分布式提交协议的确定性锁定机制。

分布式事务的成本

分布式事务一直以来都是由数据库社区按照1980年代System R[22]的架构所倡导的方式实现的。 System R式分布式事务妨碍吞吐量和延长延迟的主要机制是要求所有参与的机器在提交时达成协议，以确保原子性和持久性。为了确保隔离，在此协议协议的整个期间，必须持有事务的所有锁，这通常是两阶段提交。

协议协议期间持有锁的问题在于，两阶段提交需要所有参与计算机之间的多个网络往返，因此运行协议所需的时间通常比执行所有本地事务逻辑所需的时间大得多。如果一些常用的记录经常涉及分布式事务，那么在这些记录上持有锁的额外时间会对总体事务吞吐量产生极其有害的影响。我们指的是事务保留其锁的总持续时间，我们将事务持有其锁的总持续时间(包括所需提交协议的持续时间)称为事务的争用空间。尽管本文中的大多数讨论都假定了悲观并发控制机制，但扩展事务的争用占用空间的成本在乐观模式中同样适用——由于级联中止的可能性，通常更糟。

对两阶段提交的某些优化（如将多个并发事务提交决策组合为单轮协议）可以降低两阶段提交中的CPU和网络开销，但不会降低其争用成本。虽然检测和纠正死锁通常不会带来令人望而却步的系统开销，但它会导致事务中止和重新启动，从而在某种程度上增加延迟并降低吞吐量。

副本一致性

分布式数据库系统设计的第二个趋势是减少复制的一致性保证。 Dynamo、SimpleDB、Cassandra、Voldemort、Riak和PNUTS等系统都降低了复制数据的一致性保证[13，1，17，2，3，12]。降低这些系统的副本一致性的典型原因是CAP定理[5，14]，为了使系统实现24/7全局可用性。即使在一个网络分区时仍然可用，系统必须提供较低的一致性保证。然而，去年，这种趋势开始逆转——部分原因可能是全球信息基础设施的不断完善，使得部分网络分区越来越罕见——有几个新系统支持强一致的复制。例如，谷歌的Megastore[7]和IBM的Spinnaker[25],通过Paxos[18，19]实现副本同步。

同步更新具有一个低延迟成本的一致性协议，这依赖于副本之间的网络延迟。这种成本可能很大，因为副本在地理上通常分开，以减少相关的故障可能。但是，这本质上是一种延迟成本，不一定影响争用或吞吐量。

在不增加争用的情况下达成协议

Calvin的低成本分布式事务和同步副本方法如下：当多台计算机需要就如何处理特定事务达成一致时，它们在事务边界之外（即获取锁并开始执行事务之前）执行。

达成如何处理事务的协议后，必须根据计划节点失败执行到完成，相关问题不会导致事务中止。如果节点发生故障，它将从并行执行同一计划的副本中恢复，或者，它可以重播该节点的计划活动的历史记录。并行计划执行和计划历史记录重播都需要活动计划来确定性的，否则副本可能会出现分歧或历史记录可能会错误地重复。

为了支持这种确定性保证，同时在事务执行中最大化并发性，Calvin使用基于我们在以前工作中介绍的确定性锁协议[28]。

由于所有Calvin节点都就要尝试事务按什么顺序达成协议，因此它能够完全避开分布式提交协议，从而减少分布式事务的争用占用空间，尽管存在多分区事务，但几乎以线性方式进行扩展。我们的实验表明，在高争用工作负载下，Calvin明显优于传统的分布式数据库设计。我们发现，在亚马逊云中的一个商用集群上每秒可以运行50万次TPC-C交易，这可以与目前在TPC-C网站上发布的在更高端的硬件上获得的世界记录竞争。

这篇论文的要点如下：

事务调度和数据复制层的设计，将非事务存储系统转换为近线性扩展的shared-nothing的数据库系统，该系统可提供高可用性、强一致性和完整的ACID事务。
确定性并发控制协议的具体实现，它比以前的方法更具可扩展性，并且不会引发潜在的单点故障。
一种数据预提取机制，利用事务执行之前执行的计划阶段，允许事务对驻留在磁盘上的数据进行操作，而无需在整个磁盘查找期间扩展事务的争用空间。
快速检查点方案，加上Calvin的决定论保证，完全消除了对物理重做日志及其相关开销的需要。

下面将继续讨论确定性数据库的背景。在第3节中，将介绍calvin的架构体系。在第4节中，将介绍calvin如何处理访问磁盘数据的事务。在第5节，将介绍calvin定期实现完整数据库快照的机制。在第6节，我们设计了一系列的实验，用来衡量calvin在不同负载下的吞吐量和延迟。我们在第7节介绍相关的工作，在第8节讨论未来的工作，并在第9节结束。

确定性数据库系统

在传统的（System R*类型）分布式数据库系统中，提交分布式事务时需要共识协议，主要原因是确保事务的所有影响都以原子方式成功实现持久存储 - 无论是涉及事务的所有节点都同意"提交"其本地更改，还是没有一个节点同意。阻止节点提交其本地更改（因此导致整个事务中止）的事件分为两类：非确定性事件（如节点故障）和确定性事件（例如，如果库存物料低于零，则强制中止的事务逻辑）。

事务因任何非确定性事件而必须中止，没有任何根本原因;当系统选择由于外部事件而中止事务时，则是出于实际考虑。毕竟，强制系统中的所有其他节点等待出现非确定性事件（如硬件故障）的节点恢复，可能会使系统长期保持等待状态。

但是，如果存在副本，没有与失败节点并行执行完全相同的操作，则依赖于与受事件影响节点通信以执行事务的其他节点无需等待失败的节点恢复到其原始状态，而是可以请求副本节点处理当前或将来事务所需的任何数据。此外，事务可以提交，因为副本节点能够完成事务，并且失败的节点最终将能够在恢复时共同复制事务。

因此，如果存在一个副本，该副本正在与遇到非确定性故障的节点并行处理相同的事务，则无需在出现此类故障时中止事务。惟一的问题是，副本需要经过相同的数据库状态序列，以便在事务的中间立即替换失败的节点。同步复制每个数据库状态更改的开销太大，无法实现。相反，确定性数据库系统同步复制批量事务请求在传统的数据库实现中,简单的复制事务输入通常不足以确保副本不偏离,因为数据库保证他们将处理事务的方式在逻辑上等同于一些串行事务的顺序输入, 而且这两个副本可能会选择过程相当于不同的串行输入订单,例如由于不同的线程调度,网络延迟或其他硬件约束。但是，如果修改数据库的并发控制层，按商定的事务输入（并且对数据库进行其他几个次要修改[28]）的顺序获取锁，则可以制作所有副本来模拟相同的串行执行顺序，并且可以保证数据库状态不会偏离。

这种确定性数据库允许两个副本通过复制数据库输入来保持一致，如上所述，这些主动复制节点的存在使分布式事务能够在存在非确定性故障时提交其工作（这可能发生在事务中间）。这就消除了在分布式事务结束时使用共识协议的主要理由（需要检查可能导致事务中止的节点故障）。上述中止的另一个潜在原因,事务中的确定性逻辑（例如，如果库存为零，应中止事务）, 不一定必须作为在事务结束时执行共识协议的一部分。相反，事务中涉及的每个节点都等待来自每个节点的单向消息，该消息可能确定地中止事务，并且只有在收到这些消息后才提交。

系统架构

Calvin设计为作为可扩展的事务层，高于实现基本CRUD接口（创建/插入、读取、更新和删除）的任何存储系统之上。尽管可以运行在分布式非事务存储系统（如SimpleDB或Cassandra）上运行 Calvin，如果存储系统不是开箱即用的，那么解释Calvin的架构就更直接了。例如，存储系统可能是安装在多台独立计算机上的单节点键值存储。在此配置中，Calvin 将数据分区组织到每个节点上的存储系统中，并协调事务执行过程中节点之间必须发生的所有网络通信。

在图1中介绍了calvin的整体架构，calvin本质上将系统分为了三个独立的处理层：

排序层（sequencer) 拦截事务性输入，并将它们放入全局事务性输入序列中——这个序列将是所有副本在执行期间确保串行等价的事务的顺序。因此，序列器也处理这个输入序列的复制和记录。
调度层（scheduler）使用确定性锁方案编排事务执行，以保证与序列层指定的串行顺序等价，同时允许事务由一个事务执行线程池并发执行。(尽管它们显示在图1中的调度器组件下面，但这些执行线程在概念上属于调度层。)
存储层处理所有物理数据存储布局。Calvin事务使用简单的CRUD接口访问数据;任何支持类似接口的存储引擎都可以很容易地插入到Calvin中。

Figure 1: System Architecture of Calvin

这三个层都是水平伸缩的，它们的功能在一个无共享节点集群中分区。部署中的每个节点通常运行每个层的一个分区。（图l中的灰框表示群集中的物理计算机）。将在下边章节讨论这三层的实现。

通过将复制机制、事务功能和并发控制(在排序层和调度层中)与存储层分离，calvin的设计与高度单一的传统数据库设计明显不同，传统数据库设计高度单一，物理访问方法、缓冲区管理器、锁管理器和日志管理器高度集成并相互依赖。这种解耦使得很难实现某些流行的恢复和并发技术，例如基于物理日志的ARIES算法和next-key locking技术来处理幻像（handle phantoms）（即在并发控制内的逻辑属性上使用物理代理）。 Calvin并不是试图分离数据库中的事务组件与其他组件的唯一尝试。由于云计算的出现和它带来的高度模块化的服务，数据库社区对将这些功能分离成不同的模块化系统组件重新产生了兴趣[21]。

序列和复制

在以前与确定性数据库系统的工作中，我们实现了排序层功能作为一个简单的回声（echo）服务-一个单独的节点接受事务请求，记录到磁盘，并按时间戳顺序转发到适当数据库节点的每个副本中。单节点排序器的问题有：

(a)它们表示潜在的单点故障

(b)随着系统的增长，单节点排序器的恒定吞吐量绑定使整个系统可伸缩性快读降低。

Calvin的排序层分布在整个系统副本中，并且在每个副本中的每台计算机上分区。

Calvin将时间划分为以10毫秒为单位的时间段，在此期间，每个机器的序列器组件会收集来自客户端的事务请求。在这个时间段结束时，到达序列器节点的所有请求都被编译为批处理。这是事务输入副本发生的点（下面讨论）。

成功复制序列器的批处理后，它会向其副本中每个分区上的调度程序发送一条消息，其中包含(1)序列器的唯一节点ID (2)纪元编号epoch number(10ms同步，在整个系统中递增)。(3)接收者需要参与的所有事务输入。这允许每个调度器通过（确定性deterministic、循环的方式round-robin）这个纪元（epoch)的所有排序的批来拼凑自己的全局事务顺序视图。

同步和异步复制

Calvin目前支持两种复制事务的输入模式：异步复制和Paxos-based的同步复制。在这两种模式下，节点被组织成复制组。每个复制组都包含特定分区的所有副本。例如，在图1的部署中，副本A(replica A)中的分区1（partition 1）和副本B(replica B)中的分区1（partition 1）共同组成一个复制组。

在异步复制模式下，一个副本被指定为主副本，所有事务请求将立即转发到位于此副本节点的排序器。编译每个批处理后，每个主副本排序器组件将批处理转发到其复制组中的所有其他从序列器上。这样做的优点是，在主副本事务开始执行之前，延迟非常低，但故障转移的复杂性会很大。在主排序器发生故障时，必须在同一副本中的所有节点与故障节点复制组上的所有成员之间达成一致，涉及（a）哪个批处理是失败的排序器发送的最后一个有效批处理，（b）批包含的事务有哪些，因为每个调度器仅发送它实际需要执行的每个批处理的部分视图。

Calvin还支持基于Paxos的事务输入同步复制。在这个模式下，复制组内的所有序列器都使用Paxos就每个纪元事务的组合批处理达成一致。 Calvin目前实现使用Zookeeper，这是一种高可靠的分布式协调服务，通常为分布式数据库系统用于检测信号、配置同步和命名服务[15]。 Zookeeper未针对存储高数据量进行优化，并且可能会产生比最有效的Paxos实现更高的延迟。但是，对于本文运行的所有试验， Zookeeper会处理必要的吞吐量来复制Calvin的事务性输入，并且由于这个同步步骤不会扩展争用，事务性吞吐量完全不受这个预处理步骤的影响。同时实施Calvin序列器之间的更简化Paxos协议来改进Calvin代码库，而不是使用Zookeeper开箱即用的协议，对于延迟敏感的应用程序可能很有用，但不会提高事务吞吐量。

Figure 2: Average transaction latency under Calvin’s different replication modes.

图2可以看到在不同复制模式下，Calvin的平均事务延迟。上述数据是使用4台EC2 High-CPU机器每个副本，运行40000 microbenchmark事务每秒（10000每节点），其中10%是多分区（关于实验附加内容请参考第6章）。报告的两个Paxos延迟都使用了三副本（共12个节点）。当所有副本在一个数据中心运行时，副本之间的ping时间约为1ms。跨数据中心复制时，一个在亚马逊云的美国东数据中心，一个在亚马逊云的美国西数据中心，一个亚马逊的EU数据中心。它们之间的ping值在100到170ms之间。更改Calvin的复制模式不会影响总事务吞吐量。

调度和并发控制

当数据库系统的事务组件从存储组件中拆解时，它不能再对数据层的物理更新进行任何假设，也不能引用物理数据结构（如页面和索引），也不能知道事务对数据库中数据的物理布局的副作用。日志记录和并发协议必须具有逻辑性，仅指记录键，而不是物理数据结构。幸运的是，在确定性数据库系统中，无法执行物理日志记录并不是一个问题;由于数据库的状态可以从数据库输入中确定，因此逻辑日志记录非常简单（输入由序列层记录，检查点由存储层记录 - 请参阅第5章，以进一步讨论Calvin中的检查点）。

尽管对于并发控制来说，只访问逻辑记录，出现问题的概率略高，因为锁定键的范围和对幻像更新的健壮性通常需要对数据进行物理访问。为了处理这个问题，Calvin可以使用最近提出的另一种用于非绑定数据库系统的方法，即创建可以在事务层[20]中逻辑锁定虚拟资源，不过这个特定的实现仍需要未来的工作。

Calvin的确定性锁管理器是整个调度层的一部分，每个节点的调度程序只负责锁定存储在该节点存储层中的记录，即使存在访问其他节点记录的事务。锁协议类似于严格的两阶段锁，但是增加了两个变量：

对于任何一对事务A和事务B都请求某个本地记录R上的排它锁，如果事务A按照排序层提供的顺序出现在B之前，那么A必须在B之前请求对R的锁。在实践中，Calvin通过在单个线程中序列化所有锁请求来实现这一点。线程扫描序列层发送的串行事务顺序;对于每个条目，它请求事务在其生命周期中需要的所有锁。 (因此，所有事务都必须提前声明其完整的读/写集;第3.2.1节讨论了其中的局限性。)
锁管理器必须严格按照事务请求锁的顺序向请求事务授予每个锁。因此在上面的例子中，B在R上的锁不能被授予，直到A获得了R上的锁，执行到完成并释放了锁。

客户端指定事务逻辑使用基本的CRUD接口访问数据的C++接口函数。事务代码不需要完全了解分区（尽管用户可以指定在计算机之间应如何对键进行分区）,因为Calvin截获事务代码中出现的所有数据访问，并自动执行所有远程读取结果转发。

一旦一个事务在这个协议下获得了它的所有锁（因此可以完全安全地执行）,它就会移交给一个工作线程执行。每个工作线程实际执行的事务分为五个阶段：

读/写集分析。 事务执行读取在提交事务请求时执行的第一件事是分析事务的读写集，注意（a）本地存储的读写集的元素（即线程正在执行的节点）,以及（b）存储写入元素集参与的节点集，这些节点在事务中称为活动参与者；仅存储读取集元素的参与者节点称为被动参与者。
执行本地读取。 接下来，工作线程将访问本地存储中读取集中所记录的值。根据存储接口的不同，这可能意味着将记录的副本复制到本地缓存层，或者只是保存指向记录可以找到内存位置的指针。
提供远程读取服务。 本地读取阶段的所有结果都转发到每个积极参与节点上对应的工作线程。由于被动参与者不修改任何数据，他们不需要执行实际的事务代码，并且不需要收集任何远程读取结果。如果辅助线程在被动参与节点上执行，则在此阶段之后完成。
收集远程读取结果。 如果辅助线程在积极参与的节点上执行，则它必须执行事务代码，因此它必须首先获取所有读取结果，本地读取的结果（在第二阶段获得）和远程读取结果（由每个参与节点在第三阶段适时转发）。在此阶段中，工作线程收集后一组读取结果。
事务逻辑执行和应用写入。 工作线程收集所有读取结果后，继续执行所有事务逻辑，应用任何本地写。可以忽略非本地写入，因为它们将被相应的节点上对等事务执行线程视为本地写入，并该节点执行。

假设分布式事务在每个参与节点上几乎同时开始执行（并不总是这样-第6章将对此进行更详细的论述）, 则所有读取都并行执行，并且所有远程读取结果也并行执行，不同节点的工作线程无需在事务执行时彼此请求数据。

依赖事务

必须执行读取才能确定其完整读/写集（我们术语中，dependent transcations称为依赖事务）事务在Calvin中不受本机支持，因为Calvin的确定性锁协议要求在事务开始执行之前预先了解所有事务的读写集。相反，Calvin支持一种称为乐观锁位置预测（OLLP）的方案，它可以通过修改客户端事务代码本身[28]以极低的开销成本实现。其理念是，依赖事务之前应有一个廉价、低隔离、不重复、只读侦查查询，该查询执行所有必要的读操作以发现事务的完整读/写集，然后发送实际事务到全局序列中执行，使用侦查查询的结果读/写。因为它是侦查查询的记录读（实际事务的读/写集）之间发生了变化的执行侦查查询和实际执行事务，读取结果必须重新核对，如果侦查读写集不再有效，进程必须（确定地）重新启动。

在此类事务中特别常见的是那些必须执行二级索引查找以确定其完整读/写集的事务。由于二级索引的修改成本通常相对较高，因此他们很少保留在值更新频率极高的字段中。例如，关于“存货项目名称”或“纽约证券交易所股票代号”的二级索引将是常见的，而在诸如“存货项目数量”或“纽约证券交易所股票价格”等不稳定的字段上创建二级索引将是不常见的。因此，在大多数常见的现实工作负载下，我们很少期望OLLP方案导致重复的事务重新启动。

TPCC基准测试中的“付款”事务类型是此类事务的示例。由于TPCC工作负载从未修改支付转换操作的读写集可能依赖的索引，因此，使用OOLP时不必重新启动付款事务。

基于磁盘存储的Calvin

之前关于确定性数据库系统的工作附带了一个警告，即确定性执行仅适用于完全驻留主内存中的数据库[28]。其理由是，确定性数据库系统相对于传统非确定性数据库系统的一个主要缺点是，非确定性数据库系统能够保证与任何串行排序等价，因此可以任意重新排序事务，而像Calvin这样的系统则受制于排序器选择的顺序。

For example, if a transaction (let’s call it A) is stalled waiting for a disk access, a traditional system would be able to run other transactions (B and C, say) that do not conflict with the locks already held by A. If B and C’s write sets overlapped with A’s on keys that A has not yet locked, then execution can proceed in manner equivalent to the serial order B−C−A rather than A−B−C. In a deterministic system, however, B and C would have to block until A completed. Worse yet, other transactions that conflicted with B and C—but not with A—would also get stuck behind A. On-the-fly reordering is therefore highly effective at maximizing resource utilization in systems where disk stalls upwards of 10 ms may occur frequently during transaction execution.

例如，如果一个事务（事务A）在等待磁盘访问时停滞，则传统数据库能运行与已持有锁不冲突的其他事务（事务B和事务C），如果B和C的写入集和A尚未锁定的键重叠，则执行可以以等效于排序A-B-C的B-C-A的方式执行。但是，在确定性系统中， B和C必须阻塞，直到A完成。更糟的是，其他与B和C有冲突但和A没有冲突的事务也会落后于A。因此，在事务执行过程中磁盘暂停时间经常超过10毫秒的系统中，动态重新排序对于最大限度地利用资源非常有效。

Calvin遵循这个指导设计原则，避免了确定性在基于磁盘数据库上下文中的这种缺点：在获得锁之前，尽可能将繁重的任务移动到事务处理管道的较早位置。

当序列器组件收到出现磁盘停滞的事务请求时，它会在事务请求转发到调度层之前引入人为的延迟转发，同时向相关存储组件 “warm up”的磁盘上访问驻留记录。如果人工延迟大于或等于在执行期间执行磁盘驻留记录放入内存所花费的时间，那么当事务实际执行时，它将只访问内存缓存记录。注意,这个方案的事务总延迟不应该大于在传统系统的磁盘IO 进行执行期间(因为在这两种情况下都发生完全相同的磁盘操作集),但任何磁盘延迟都没有增加事务的争用。

为了清楚地演示此技术的适用性（和缺陷）,我们为Calvin实现了一个简单的基于磁盘的存储系统，其中冷数据被写入本地文件系统，并且仅在事务需要时读取到内存驻留键表。当运行每台10000microbenchmark事务时（有关实验的详细信息请参考第6章）,Calvin的总事务吞吐量不受访问磁盘存储的事务存在的影响，只要磁盘的事务不超过0.9 （10000个事务中的90个）。但是，这个数字取决于使用的服务器的特定硬件配置。我们运行了低端硬件的实验，发现可支持的磁盘访问事务的数量受本地磁盘最大吞吐量（不是争用占用空间）的有效限制。由于microbenchmark工作负载涉及随机访问需要不同的文件，因此每台机器每秒90个磁盘访问事务足以将磁盘随机访问吞吐量变成瓶颈。使用高端磁盘(或闪存)，可以支持更多的基于磁盘的事务，而不会影响总的吞吐量。

为了更好的理解Calvin与其他磁盘配置、闪存、网络存储等对接的潜力，我们还实现了一个存储引擎，其中冷数据存储在单独计算机的内存中，该计算机只能在预先指定的延迟（模拟网络或存储访问延迟）后才为数据请求服务。使用这个设置，我们发现每台计算机都能支持相同的负载，即每秒10000个事务，无论有多少这些事务访问过冷数据，及时在极高的争用项（争用指数contention index0.01)。

我们发现在协调确定性执行与基于磁盘的存储方面存在两个主要挑战。首先，必须准确预测磁盘延迟，以便事务延迟到适当的时间量。其次，序列器层必须准确追踪所有存储节点中哪些键存在内存中，以便确定合适需要预取。

磁盘I/O延迟预测

准确预测从磁盘到内存获取记录所需要的的时间并非易事。读取磁盘驻留服务器所占用的时间可能因多原因而有很大差异：

头部和主轴移动的可变物理距离
之前队列磁盘的IO操作
远程读取的网络延迟
故障转移
由于遍历基于磁盘的数据结构（例如树）需要执行多个IO操作

因此，无法完美地预测延迟，任何启发式的使用有时会导致低估，有时还会导致高估。当调整Calvin在高争用条件下对磁盘驻留数据执行良好性能时，磁盘IO延迟被证明是一个特别有趣和关键的参数。我们发现，如果序列器选择保守的高估计值，并且延迟转发事务的时间超过可能必要的时间，则磁盘访问导致的争用成本将最小化（因为提取几乎总是在事务需要读取记录之前完成），但代价是总体事务延迟。过高的估计值还可能导致存储系统的内存超载，等待请求安排的事务变成"冷"记录。

但是，如果序列器低估了磁盘I/O延迟，并且没有将事务延迟足够长的时间，则它将被安排得太快并在执行期间停止，直到所有读取完成。由于锁的保持时间较长，为了保持高吞吐量，可能需要很高的争用占用空间成本。

所以，在评估磁盘IO延迟时，总事务延迟和争用之间存在根本的权衡。在上述两项实验中，我们调整了延迟预测，使至少99%的磁盘访问事务在其相应的预取请求完成后被调度。使用基于文件系统的简单存储引擎，这意味着引入40ms 的人工延迟，但即使在非常高的争用（争用指数0.01）下，这足以维持吞吐量。在较低争用（争用指数0.001）下，我们发现，除了将事务请求收集成批(平均5毫秒)所导致的默认延迟之外，没有必要延迟。对这个特殊的延迟争用折衷进行更详尽的探索将是未来研究的一个有趣方向，特别是当我们进一步试验将Calvin连接到各种商业可用的存储引擎时。

全局热点记录追踪

为了使序列器在预热读取集时准确确定哪些事务要延迟调度，每个节点的序列器组件必须跟组系统中当前内存中的数据，而不仅仅是由序列器节点上的存储组件管理的数据。虽然这对于本文中的实验是可行的，但这不是一个可扩展的解决方案。如果每个排序都未追踪热键的全局列表，一个解决方案是将所有事务从计划时间延迟到允许允许有足够时间进行预取。这可防止磁盘寻求扩展争用占用空间，但会在每个事务中产生延迟。另一个解决方案（仅适用于单分区事务）是让计划程序跨所有副本同步追踪其本地热数据，然后允许调度程度确定地决定延迟请求单分区事务（尝试读取冷数据）的锁。更全面的探索这一战略，包括研究如何为多部门事务实施该战略，仍是今后的工作。

检查点

确定性数据库系统有两个属性，可以简化确保容错的任务。首先，主动复制允许客户端在发生崩溃时立即将故障转移到另一个副本。

其次，只记录事务性输入—不需要支付物理重做日志的开销。重放事务性输入的历史记录足以将数据库系统恢复到当前状态。但是，在每次失败时都重放数据库从一开始就有的整个历史是低效的(而且荒谬的)。相反，Calvin定期采用完整数据库状态的检查点，以提供恢复期间开始重播的起点。

Calvin支持三种检查点模式:朴素同步检查点，an asynchronous variation of Cao et al.’s Zig-Zag algorithm [10]，以及只有在存储层支持完全多版本化时才支持的异步快照模式。

第一种模式使用活动复制系统中固有的冗余来创建系统检查点。系统可以定期冻结整个副本，并生成系统的完整版本快照。由于这一次只在一个快照上发生，因此客户端看不到副本不可用的时间段。这种方法的一个问题是，接受检查点的副本可能明显落后于其他副本，如果由于另一个副本的硬件故障而调用该副本，则可能出现问题。此外，副本可能会花费大量时间来赶上其他副本，特别是在负载沉重的系统中。

Calvin的第二检查点模式是紧密基于Cao等人的Zig-Zag算法[10]。Zig-Zag在给定的数据存储中存储每条记录的两个副本，分别为AS[K]0和AS[K]1，加上每条记录另外两个比特，MR[K]和MWK。MR[K]指定从数据库中读取记录K时应该使用哪个记录版本，而MW[K]指定更新记录K时要覆盖哪个版本。所以记录K的新值总是写为AS[K]MW[K]，每次更新K时MR[K]等于MW[K]。

Zig-Zag的每个检查点周期开始于在数据库完全停顿的物理一致性点上，将数据库中所有密钥K的MW[K]设置为¬MR[K]。因此，AS[K]MW[K]总是存储记录的最新版本，而AS[K]MW[K]总是存储最近检查点开始之前写入的最后一个值。因此，异步检查点线程可以通过每个键K，以AS[K]]¬MW[K]的形式登录到磁盘，而不必担心记录被打破了。

利用Calvin的全局串行顺序，我们实现了一个曲折的变体，它不需要静默数据库来创建物理一致性点。相反，Calvin捕获关于虚拟一致性点的快照，虚拟一致性点只是全局串行顺序中的一个预先指定的点。当一个虚拟点的一致性方法,Calvin的存储层开始保持两个版本的每个记录存储系统中的“之前”的版本, 这只能通过交易之前更新虚拟点的一致性,和一个“后”版本,由事务写入后出现虚拟点的一致性。一旦一致性虚拟点之前的所有事务都完成执行，每个记录的“前”版本就有效地不可变了，一个异步检查点线程就可以开始将它们检查点指向磁盘。一旦检查点完成，任何复制版本都将被垃圾收集: 所有同时拥有“之前”版本和“之后”版本的记录将丢弃它们的“之前”版本，这样在下一次检查点开始之前，每个版本只保留一条记录。

上面描述的Calvin的第一个检查点模式涉及到在检查点期间完全停止事务执行，而在异步检查点线程处于活动状态时，该模式只会带来适度的开销。图3显示了Calvin在一个典型的检查点捕获期间的最大吞吐量。这个测量是在运行微基准测试的单机Calvin部署上进行的，该部署处于低争用状态(有关我们的实验设置的更多信息，请参阅第6节)。虽然由于(a)获取检查点的CPU成本和(b)访问记录时少量的锁存争用，总吞吐量有所降低，但异步地向存储写入稳定值不会增加锁争用或事务延迟。

Calvin还能够利用存储引擎，这些引擎显式地跟踪除了当前版本之外的每条记录的所有最新版本。多版本存储引擎允许在不获取任何锁的情况下执行只读查询，以增加内存使用为代价，减少总体争用和总的并发控制开销。在这种模式下运行时，Calvin的检查点方案采用普通的“SELECT *”查询形式，对所有记录进行查询，查询结果被记录到磁盘上的一个文件中，而不是返回给客户端。

Figure 3: Throughput over time during a typical checkpointing period using Calvin’s modified Zig-Zag scheme.

性能和可扩展性

为了研究Calvin在各种共同参数下的性能和可伸缩性特征，我们使用两个基准进行了许多实验：TPC-C benchmark和Microbenchmark，以便更好地控制基准参数的多样化。除非另有说明，否则所有实验均使用高CPU/超大型实例在Amazon EC2上运行，这些实例承诺7GB内存和20个EC2计算单元—8个虚拟内核，每个实例具有2.5EC2计算单元。

TPC-C benchmark

Figure 4: Total and per-node TPC-C (100% New Order) throughput, varying deployment size.

TPC-C基准由几类事务组成，但大部分工作负载（包括几乎所有需要高度隔离的分布式事务）由"New Order"事务组成，该事务模拟客户在电子商务应用程序上下订单。由于实验的重点是分布式事务，因此我们的TPCC实现仅针对新订单事务进行。如果我们运行完整的TPC-C基准，我们期望获得类似的性能和可伸缩效果。

图4显示了总吞吐量和每台机器吞吐量（TPCC New Order事务执行每秒）作为节点数关系的图，每个节点存储包括10个TPCC仓库的数据分区，为了充分体现Calvin对分布式事务的处理情况，多仓库新订单事务（约占新订单交易总数的10%）始终访问第二个仓库，该仓库和第一个不在一台机器上。

由于每个分区包含10个warehouse，并且New Order更新了某些仓库的10“districts”,因此最多可以在任何节点上同时执行100 个新订单事务（因为每个分区的惟一区域不超过100个，而且每个新订单事务都需要一个区域上的独占锁）。因此，将锁的持有时间降至最低至关重要，因为系统的吞吐量受这个并发事务完成（释放锁）的速度限制，以便新事务可以获取该区域上的独占锁并开始启动。

如果Calvin在共识协议（如分布式新订单事务的两阶段提交）期间持有锁，则吞吐量将严重受限。（第6.3节提供了与实现两阶段提交的传统系统的详细比较。)如果没有共识协议，Calvin能够在大于10个节点的集群中实现每个节点5000个事务每秒，并线性扩展。（下一节将描述Calvin在较小集群上每节点实现更多事务的原因。）因此，我们的Calvin实现能够在100个节点集群上实现近50万次TPCC事务/秒。指的注意的是，目前TPCC世界纪录的保持着， Oracle运行504161新订单事务每秒。尽管运行在比我们用于实验的机器高得多的高端硬件[4]。

6.2 Microbenchmark experiments

Figure 5: Total and per-node microbenchmark throughput, varying deployment size.

为了更准确地检查合并分布式事务和高争用时产生的成本，我们实现了一个微基准测试，该基准与TPCC的新订单事务共享某些特征，同时减少了总体开销并允许对工作负载进行更精细的调整。基准测试的每个事务读取10条记录，并对结果进行约束检查，仅在通过约束检查时更新每个记录上的计数器。在微基准事务所记录的10条记录中，一条是从一组热记录中选择的，其余记录是从一组大得多的记录中选择的，除非微基准事务跨越两台机器，在这种情况下，它会在参与事务的每台机器上访问一个热记录。通过更改热记录的数量，我们可以微调争用。在随后的讨论中，我们使用术语争用指数（contention index)来引用在特定节点上执行事务时更新的热记录分数。例如，争用指数为0.001意味着每个事务从1000条热记录中选择要在每个参与节点上更新一条（即最多可以同时执行1000个事务）,而争用指数1表示每个事务都涉及到热记录（即事务必须完全串行执行）。

图5显示我们将微基准缩放为100个Calvin节点的不同争用设置的实验，并且具有不同数量的分布式事务。在非常低争用下添加节点时，每个节点的吞吐量将下降到稳定量大约10台节点，然后保持不变，以线性方式对许多节点进行分析。在较高争用（争用指数0.01类似于TPCC争用级别）,随着机器的增加，我们会看到更长的、更渐进的每节点吞吐量下降，更缓慢地接近一个稳定的量。

多种因素促成了calvin这种可伸缩曲线的形状。在所有情况下，一台节点和两台节点之间的急剧下降是每个多部分事务必须执行的额外工作的CPU成本的结果：

序列化和反序列化远程读取结果
等待获取远程读取结果的事务之间的上下文切换
在所有参与的节点上设置、执行和清理事务后，即使它只计算一次总吞吐量

在丢弃掉这类初始化后，随着节点的加入而进一步下降的原因（即使争用和参与分布式事务的节点数都保持不变）也相当微秒。假设，在高争用负载下，节点A开始执行需要从节点B远程读取分布式事务，但B尚未访问该事务（B可能仍在处理序列中的早期事务，并且在序列中所有以前的事务获得锁之前，它无法处理事务）。节点A也许能够开始执行一些其他非冲突事务，但很快它只需要等待 B赶上，就可以提交挂起的分布式事务并执行后续冲突事务。通过这种机制，任何特定节点的领先或落后是有限的，争用越高，它的极限越紧。随着机器的增加，会发生两件事：

Slow machines。 并不是所有EC2实例都等于高性能，有时一个EC2用户卡住。如图5中的实验结果，使用相同的EC2实例，所有三行都显示了6到8台机器之间突然下降，很明显缓慢机器的添加是在6到8节点的时候。
Execution progress skew。 由于许多因素，例如OS线程调度、可变的网络延迟和事务序列之间争用的随机变化，这些机器偶尔会略微领先或落后于其他机器。机器越多，就越有可能在任何时候至少有一台因为某种原因稍微落后。

系统总吞吐量对执行进度倾斜的敏感性在很大程度上取决于两个因素：

机器数量。 机器越少，增加节点越容易发生倾斜。例如，假设n台机器中的每台机器都花费了k时间执行进度倾斜（即落后包）。那么在每一时刻都有1-(1-k)^n概率至少有一台节点在减慢系统的速度。随着n的增长，这个概率趋近于1，每增加一台机器，倾斜效应就越小。
争用级别。 争用率越高，每台机器的随机减速就越有可能导致其他机器也降低它们的执行速度。在低争用(争用指数= 0.0001) 情况下，我们看到每个节点的吞吐量只有在添加前几台机器时急剧下降，然后在大约10个节点时趋于平稳，因为执行进度倾斜的逐渐减小的增长对总吞吐量的影响相对较小。在较高的争用(争用指数= 0.01)情况下，我们看到了更剧烈的初始下降，在曲线开始变平之前需要添加更多的机器，因为即使是执行进度倾斜水平上的微小增量增加也会对吞吐量产生显著影响。

处理高争用

大多数现实世界的工作负载在大多数时候都有低争用，但是出现少量的极热数据项并不罕见。因此，我们在这些工作负载下对Calvin进行了实验，我们认为这种工作负载是很少实际系统尝试支持分布式事务的主要原因: 结合许多高争用的多分区事务。因此，在这个实验中，我们并不关注实际工作负载的全部，而是只考虑由高争用多分区事务组成的工作负载的子集。其他事务仍然可能与这些高度冲突的事务(除了那些非常热的事务之外)发生冲突，因此工作负载的这个子集的吞吐量可能与整个系统吞吐量紧密耦合。

Figure 6: Slowdown for 100% multipartition workloads, varying contention index.

图6显示了4节点和8节点Calvin系统在运行100%多分区事务时(与运行完全可分割、低争用版本的相同工作负载相比)变慢的因素，这取决于争用。回想一下，争用索引是每个事务锁定的热记录总数的一部分，因此争用指数为0.01意味着最多可以并发执行100个事务，而争用指数为1则强制事务完全串行地运行。

因为现代分布式系统的实现没有实现系统R风格的两阶段提交分布式事务,与任何早期系统不会成为同类对比, 我们包括比较contention-based放缓的一个简单的模型的系统。我们假设在非多分区、低争用的情况下，该系统将获得与Calvin类似的吞吐量(每台机器大约每秒27000个微基准事务)。为了计算多分区事务引起的速度下降，我们考虑了两阶段提交引起的争用占用空间的扩展。由于给定一个争用索引C，最多可以并发执行1/C事务，因此在提交时运行2PC的系统每秒执行的事务总数永远不会超过1/C、D2PC，其中D2PC是两阶段提交协议的持续时间。

典型的EC2数据中心节点之间的往返ping延迟约为1毫秒，但包括消息多路复用、序列化/反序列化和线程调度的延迟，在我们的系统中，事务执行线程之间的单向延迟几乎从不小于2毫秒，而且通常更长。因此，在我们的系统模型中，开销类似于Calvin，我们期望在每个分布式事务上持有大约8ms的锁。注意，这个模型有点理想化，因为假定事务的争用占用空间只包括两阶段提交的延迟。其他导致Calvin实际减速的因素在这个模型中被完全忽略，包括:

多分区事务的CPU成本
启动2PC之前到达本地提交/中止决策的延迟(在实际系统中可能需要额外的远程读操作)
执行进度倾斜(假设所有节点都开始执行每个事务，然后以完美的同步方式执行2PC)

执行进度倾斜(假设所有节点都开始执行每个事务，然后以完美的步调执行2PC)，在高争用分布式事务的上下文中，会比该模型预测的速度慢得多。

图6所示的结果中有两个非常显著的特性。首先，在低争用的情况下，Calvin得到了大约5到7倍的速度降低—— 从27000减少到大约5000(4个节点)或4000(8个节点)/秒的事务——正如我们在前面的实验中看到的，从1台机器减少到4或8台。对于本实验中检查的所有争用级别，4个节点和8个节点情况下吞吐量的差异是不同节点之间工作负载执行进度倾斜的结果; 正如可以预测的那样，这种倾斜对吞吐量的不利影响在较高的争用级别上要严重得多。

第二，正如预期的那样，在非常高的争论中，尽管我们忽略了一些预期的成本，运行两阶段提交的系统模型比Calvin产生的速度明显要慢得多。这就证明了(a)分布式提交协议是大多数现代分布式系统决定不支持ACID事务背后的主要因素， (b) Calvin缓解了这个问题。

未来工作

在当前实现中，Calvin通过从最近的完整快照中恢复崩溃的机器，然后重放所有最近的事务来处理硬件故障。但是，由于同一副本中的其他节点可能依赖于从受影响的机器进行的远程读取，因此，在恢复完成之前，副本的其余部分的吞吐量很容易变慢或停止。

在未来，我们打算开发一个更加无缝的故障转移系统。例如，使用简单的技术，故障可以完全不可见。所有副本的集合可以分为复制子组——通常在同一局域网络上的彼此相邻的副本对或三副本。在一个副本中的数据库节点A与多部分事务执行值相关的传出消息不仅发送到同一副本中的预期节点B，还发送到复制子组中节点B的每个副本，以防子组节点A副本发生故障。这种冗余技术伴随着各种权衡，如果分区间网络通信有可能成为瓶颈（特别是因为确定性系统中的活动复制已经提供了高可用性），则无法实现这种权衡，但它说明了在发生故障时实现高度"无问题"系统。

这两种方法之间的一个很好的折衷办法可能是集成一个组件，该组件可监视每个节点的状态，可以检测故障，并通过指导故障计算机的其他副本适当地转发远程读取消息，为具有故障节点的副本精心安排更快的故障转移。这样的组件还可以很好地监视只读查询、动态数据迁移和重新分区以及负载监控的负载平衡。

结论

本文介绍了Calvin，这是一个事务处理和复制层，旨在将通用的、非事务性的、未复制的数据存储转换为完全ACID的、一致复制的分布式数据库系统。Calvin支持数据库的水平可伸缩性和不受约束的acid兼容分布式事务，同时支持异步和基于paxos的同步复制，既可以在单个数据中心内进行，也可以跨地理上分离的数据中心进行。通过使用确定性框架，Calvin能够消除分布式提交协议，这是现代分布式系统最大的可伸缩性障碍。因此，Calvin在简化的TPC-C基准上实现了接近世界纪录的事务吞吐量。

致谢

这项工作是由NSF在IIS-0845643和IIS-0844480赠款下赞助的。Kun Ren获得中国国家自然科学基金61033007、国家973基金2012CB316203资助。本材料中所表达的任何意见、发现、结论或建议均为作者个人观点，并不一定反映国家科学基金会NSF或中国国家自然科学基金会的观点。

引用

[1] Amazon simpledb. <http://aws.amazon.com/simpledb/>.

[2] Project voldemort. <http://project-voldemort.com/>.

[3] Riak. <http://wiki.basho.com/riak.html>.

[4] Transaction processing performance council.<http://www.tpc.org/tpcc/>.

[5] D. Abadi. Replication and the latency-consistency tradeoff. <http://dbmsmusings.blogspot.com/2011/12/replication-andlatency-consistency.html>.

[6] J. C. Anderson, J. Lehnardt, and N. Slater. CouchDB: The Definitive Guide. 2010.

[7] J. Baker, C. Bond, J. Corbett, J. J. Furman, A. Khorlin, J. Larson, J.-M. Leon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, 2011.

[8] P. A. Bernstein, C. W. Reid, and S. Das. Hyder - a transactional record manager for shared flash. In CIDR, 2011.

[9] D. Campbell, G. Kakivaya, and N. Ellis. Extreme scale with full sql language support in microsoft sql azure. In SIGMOD, 2010.

[10] T. Cao, M. Vaz Salles, B. Sowell, Y. Yue, A. Demers, J. Gehrke, and W. White. Fast checkpoint recovery algorithms for frequently consistent applications. In SIGMOD, 2011.

[11] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: a distributed storage system for structured data. In OSDI, 2006.

[12] B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. Pnuts: Yahoo!’s hosted data serving platform. VLDB, 2008.

[13] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s highly available key-value store. SIGOPS, 2007.

[14] S. Gilbert and N. Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 2002.

[15] P. Hunt, M. Konar, F. P. Junqueira, and B. Reed. Zookeeper: Wait-free coordination for internet-scale systems. In In USENIX Annual Technical Conference.

[16] E. P. C. Jones, D. J. Abadi, and S. R. Madden. Concurrency control for partitioned databases. In SIGMOD, 2010.

[17] A. Lakshman and P. Malik. Cassandra: structured storage system on a p2p network. In PODC, 2009.

[18] L. Lamport. The part-time parliament. ACM Trans. Comput. Syst., 1998.

[19] L. Lamport. Paxos made simple. ACM SIGACT News, 2001.

[20] D. Lomet and M. F. Mokbel. Locking key ranges with unbundled transaction services. VLDB, 2009.

[21] D. B. Lomet, A. Fekete, G. Weikum, and M. J. Zwilling. Unbundling transaction services in the cloud. In CIDR, 2009.

[22] C. Mohan, B. G. Lindsay, and R. Obermarck. Transaction management in the r* distributed database management system. ACM Trans. Database Syst., 1986.

[23] E. Pacitti, M. T. Ozsu, and C. Coulon. Preventive multi-master replication in a cluster of autonomous databases. In Euro-Par, 2003.

[24] E. Plugge, T. Hawkins, and P. Membrey. The Definitive Guide to MongoDB: The NoSQL Database for Cloud and Desktop Computing. 2010.

[25] J. Rao, E. J. Shekita, and S. Tata. Using paxos to build a scalable, consistent, and highly available datastore. VLDB, 2011.

[26] M. Seltzer. Oracle nosql database. In Oracle White Paper, 2011.

[27] M. Stonebraker, S. R. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era (it’s time for a complete rewrite). In VLDB, 2007.

[28] A. Thomson and D. J. Abadi. The case for determinism in database systems. VLDB, 2010.

[29] A. Whitney, D. Shasha, and S. Apter. High volume transaction processing without concurrency control, two phase commit, SQL or C++. In HPTS, 1997.