分布式事务内幕

本文节选自《数据库系统内幕》第13章——分布式事务

为了在分布式系统中维持秩序，我们至少要保证一定程度的一致性。在11.5节中，我们讨论了单个对象、单个操作的一致性模型，这些模型帮助我们论证单个操作的正确性。但是，在数据库中我们经常需要原子地执行多个操作。

原子操作可以用状态转移来解释：在启动某个事务之前，数据库处于状态A；当事务完成的时候，状态从A变成B。从操作的角度看这很容易理解，因为事务没有附带一个事先确定好的状态。相反，事务从某个时间点开始将操作应用于数据记录。这使我们在调度和执行方面具有一定的灵活性：事务可以被重新排序甚至重试。

事务处理主要关注的是决定一个合法的执行历史，以建模和表示可能的交错执行方案。在这种情况下，历史代表一个依赖关系图：哪些事务在当前事务之前执行。如果一个执行历史与事务的某一串行历史等效（即具有相同的依赖关系图），则称它为可串行化的。你可以回顾5.3.1节执行历史的概念、历史的等效性、可串行化以及其他概念。总的来看，本章是第5章在分布式系统中的对应，第5章中我们讨论了节点本地的事务处理。

单分区事务可以使用我们在第5章中讨论过的悲观（基于锁或跟踪）或乐观（尝试并验证）并发控制方案，但是这些方法无法解决多分区事务的问题，因为多分区事务需要实现不同服务器之间的协调、分布式提交和回滚协议。

一般来说，从一个账户向另一个账户转账时，你希望同时完成扣减第一个账户余额和增加第二个账户余额这两个操作。但是，如果我们将事务分解为若干独立步骤，即便是扣减或增加余额操作乍一看也不是原子的：我们需要读取旧的余额，加上或减去所需的金额，然后保存该结果。这些子步骤中的每一步又涉及多个操作：节点收到请求、解析请求、在磁盘上找到数据、进行写操作、最终确认请求。即便如此也仍是一个相当高层的视角：哪怕执行一个简单的写入，我们也要做上百个小步骤。

这就意味着我们必须先执行事务，然后再让结果可见。在此之前，我们需要先定义什么是事务。事务是一组操作，一个原子的执行单元。事务的原子性意味着：要么它的全部结果都变得可见，要么全都不可见。例如，如果我们在一个事务内修改了几行甚至几张表，要么所有修改都被应用了，要么全都不被应用。

为了保证原子性，事务必须是可恢复的。换句话说，如果事务无法完成、被中止或超时，则其结果必须完全回滚。一个不可恢复的、部分执行的事务会让数据库处于不一致状态。总而言之，在事务执行失败的情况下，必须将数据库恢复到之前的状态，就像从未做过该事务一样。

另一个重要的方面是网络分区和节点故障：系统中的节点独立地发生故障并恢复，但是它们的状态必须保持一致。这意味着原子性要求不仅适用于本地操作，还适用于在其他节点上执行的操作：事务的修改必须要么持久化地传播到事务涉及的所有节点，要么一个都不传播[LAMPSON79]。

1 多个操作的原子性

为了让多个操作看起来是原子的，尤其是当其中一些是远程操作时，我们需要使用一类称为原子提交（atomic commitment）的算法。原子提交不允许参与者之间出现分歧：只要有一个参与者投票反对，事务就不能提交。同时，这意味着发生故障的进程也必须与其他参与者达成共识。它的另一个重要含义是，如果存在拜占庭故障，原子提交算法无法正常工作：这时进程可能会撒谎或是决定一个任意值，而这会破坏全体的共识[HADZILACOS05]。

原子提交试图解决的问题就是要对以下问题达成共识：是否要执行当前被提议的事务？事务参与者不能选择、影响或修改被提议的事务，更不能提出另一个事务，它们只能对自己是否愿意执行此事务进行投票[ROBINSON08]。

原子提交算法没有对准备（prepare）、提交（commit）和回滚（rollback）这些操作做出严格的语义限制，数据库开发者需要决定：

• 何时可以认为数据已准备好提交，这时只要交换一个指针便可以让修改对外可见。

• 如何执行提交本身，以让事务结果在最短的时间内变得可见。
  

• 如果算法决定不提交，如何回滚事务所做的更改。

第5章中，我们讨论了节点本地上的事务实现。

许多分布式系统使用原子提交算法，例如MySQL（用于分布式事务）和Kafka（用于生产者和消费者的交互[MEHTA17]）。

在数据库中，分布式事务是由一个通常叫作事务管理器的组件执行的。事务管理器是负责调度、协调、执行和跟踪事务的子系统。在分布式环境中，事务管理器负责确保节点本地的可见性保证与分布式原子操作规定的可见性相符合。换句话说，事务提交发生在所有分区以及所有副本之中。

我们将讨论两种原子提交算法：两阶段提交（它解决了提交的问题，但不允许协调者发生故障）和三阶段提交[SKEEN83]（它解决了非阻塞原子提交问题注1，即使协调者发生故障时，参与者也可以继续提交）[BABAOGLU93]。

2 两阶段提交

让我们从最简单的分布式提交协议开始，该协议能够保证多分区原子更新（关于分区的更多信息请参考13.6节）。两阶段提交（2PC）是数据库事务中的一个重要概念。2PC分为两个阶段：第一阶段中分发决定的值并收集投票；第二阶段，节点仅仅翻转开关，让第一阶段的结果变得可见。

2PC假定存在一个领导者（leader）或协调者（coordinator）负责保存状态、收集投票，并作为协商的主要参考依据。其余节点称为参与者（cohort）。通常情况下，每个参与者负责一个分区（即互不相交的数据集合），在这些数据上执行事务。协调者和每个参与者都会为所有执行过的步骤保留本地操作日志。参与者投票接受或拒绝协调者提议的某个值。通常来说，这个值就是要执行的分布式事务的标识符，但是2PC也可以用在其他场景下。

协调者可以是接收事务请求的节点，可以是用选主算法随机选出来的，可以是手动分配的，甚至可以是在系统的整个生命周期内都保持固定的。协议本身对协调者角色没有任何限制。出于可靠性或性能的原因，可以将该角色转移给其他参与者。

顾名思义，两阶段提交的执行分为两个步骤：

准备（prepare）阶段

        协调者通过发送Propose消息告诉参与者关于新事务的提议。参与者要决定它们是否可以提交自己那部分事务。如果参与者决定可以提交，就向协调者投赞成票。否则，它会要求协调者中止事务。所有参与者的决定都保留在协调者的日志中，并且每个参与者也会在本地保留一份它的决定。

提交（commit）/中止（abort）阶段

        事务中的操作可以修改多个分区上的状态（每个参与者代表一个分区）。但凡有一个参与者投票中止事务，则协调者也会向所有的参与者发送Abort消息。仅当所有参与者都投赞成票时，协调者才会向他们发送最终的Commit消息。

上述过程如图13-1所示。

准备阶段中，协调者分发提议的值，并收集各个参与者的投票：这个提议的值是否应该被提交。参与者可以选择拒绝协调者的提案，例如，当另一个冲突的事务已经提交了一个不同值的时候。

图13-1：两阶段提交协议。第一阶段中，向参与者通知新事务。第二阶段中，事务被提交或中止

协调者收集投票之后，可以决定要提交事务还是中止事务。如果所有参与者均投了赞成票，它会决定提交并发送Commit消息通知它们。否则，协调者会向各个参与者发送Abort消息，事务将被回滚。换句话说，如果任意一个节点拒绝该提案，则整个流程将会中止。

每个步骤中，协调者和参与者都必须将各个操作的结果写入持久性存储中，以便能够在发生本地故障的情况下重建状态并恢复，并且可以将结果转发给其他参与者使其能够重放操作。

在数据库的语境下，每次2PC通常负责一个事务。在准备阶段，事务内容（操作、标识符和其他元数据）从协调者发送给参与者。参与者在本地执行事务，并停留在部分提交状态（也称为预提交状态），以让协调者在下一阶段通过提交或中止来完成执行。事务提交时，其内容已持久地存储到所有其他节点上[BERNSTEIN09]。

2.1 2PC中的参与者故障

让我们考虑几种故障的场景。例如，如图13-2所示，如果其中一个参与者在提议阶段故障，则协调者无法继续进行提交，因为它要求所有投票都是赞成票。如果其中一个参与者不可用，则协调者将中止事务。该要求会影响到可用性：单个节点的故障就会阻止事务提交。一些系统，例如Spanner（参见13.5节），在Paxos组而不是单个节点上执行2PC，从而改进可用性。

图13-2：准备阶段中的参与者故障

2PC的核心思想在于参与者的承诺：一旦对提案做出了肯定的回应，它不能再反悔，因此只有协调者才能中止事务。  

如果其中一个参与者在接受提案后发生故障，它必须先了解投票的实际结果，然后才能知道正确的值，因为协调者可能由于其他参与者的投票而中止了提交。当参与者节点恢复时，它必须跟上协调者的最终决定。为此，我们通常将决策日志保留在协调者端，并将决定的值复制到故障的参与者。在此之前，参与者不能处理请求，因为它还处于不一致状态。

由于协议中存在多个阻塞操作，此时进程要等待其他参与者（当协调者收集投票时，或参与者正在等待提交/中止阶段时），因此，链路故障可能导致消息丢失，进程会无限地等待下去。如果提议阶段中协调者未收到来自某个副本的响应，它不会因此阻塞，因为它可以触发超时并中止事务。

2.2 2PC中的协调者故障

第二阶段中，如图13-3所示，如果某个参与者没有收到协调者的提交或中止指令，则应当尝试找出协调者做出的决定。协调者可能已经决定了该值，但未能传达给某个副本。在这种情况下，可以从其他参与者的事务日志或是备份协调者的日志中找到决策信息。从复制日志中确定提交决定是安全的，因为这个决定一定是已经达成一致的：2PC的最终目的就是在所有节点上提交或中止，在一个参与者中提交即意味着其他所有参与者都必须提交。

第一阶段中，协调者收集投票，继而也就获得了参与者的承诺：它们将等待其明确的提交或中止指令。如果协调者在收集投票后、广播投票结果之前发生故障，则参与者最终将处于不确定状态。如图13-4所示，参与者不知道协调者的决定，也不知道它是否已向某些参与者（可能也不可达）通知了事务结果[BERNSTEIN87]。

图13-3：提议阶段完成后，协调者发生故障

图13-4：协调者在联系参与者之前发生了故障

协调者无法继续进行提交或中止操作，这使得集群处于未决状态。这意味着在发生协调者永久性故障的情况下，参与者将无法得知最终决定。因为这个特性，我们说2PC是一种阻塞原子提交算法。如果协调者始终无法恢复，它的替代者只能再次为给定事务收集投票，并做出最终决定。

许多数据库使用2PC：MySQL、PostgreSQL、MongoDB注2等。因为其简单性（易于论证、实现和调试）和低开销（消息复杂度和协议往返次数低），两阶段提交经常用于实现分布式事务。实现正确的恢复机制并拥有备份协调者节点，以减少发生上述故障的可能性，这一点非常重要。

3 三阶段提交

为了让原子提交协议在协调者故障下保持健壮并避免进入未决状态，三阶段提交（3PC）协议增加了一个额外的步骤，并且双方都具有超时机制，使得参与者在协调者发生故障时仍能继续提交或中止（取决于系统状态）。3PC假定同步网络模型，且不存在通信故障[BABAOGLU93]。

3PC在提交/中止步骤之前添加了一个准备阶段，该阶段中协调者告知参与者在提议阶段收集的投票信息，即使协调者发生故障，协议也可以继续执行。3PC的所有其他性质都和2PC类似，包括要求有一个协调者。3PC的另一个有用的补充是参与者侧的超时，参与者根据进程当前正在执行的步骤，超时之时将强制进行提交或中止。

如图13-5所示，三阶段提交包含以下三个步骤：

提议（propose）阶段

        协调者发出提议值并收集投票。

准备（prepare）阶段

        协调者将投票结果通知参与者。如果投票通过并且所有参与者都决定要提交，则协调者会发送一条Prepare消息，指示它们准备提交。否则，将发送Abort消息并退出流程。

提交（commit）阶段

        协调者通知参与者提交事务。

图13-5：三阶段提交

在提议这一步中，类似于2PC，协调者分发提议值并收集参与者的投票，如图13-5 所示。如果协调者在此阶段崩溃导致操作超时，或者其中一个参与者投反对票，则事务中止。

收集投票后，协调者做出决定。如果协调者决定继续进行事务，则发出Prepare指令。协调者可能无法将Prepare消息发送给所有参与者，或是可能没有收到参与者的确认。这种情况下，参与者可能会在超时后中止事务，因为算法尚未完全进入到已准备状态。

一旦所有参与者成功进入已准备状态并且协调者收到了它们的准备确认，无论其中任何一方发生故障，事务都将被提交。之所以可以这样做是因为此阶段中所有参与者看到的状态是相同的。

在提交阶段，协调者将准备阶段的结果传达给所有参与者，重置它们的超时计数器并完成事务。

3PC中的协调者故障

所有的状态转换都要被协调，直到每个节点都完成上一个阶段之后，参与者才能继续进入下一个阶段：协调者必须等待副本才能继续。如果参与者在超时之前没有收到协调者的消息，并且没有走完准备阶段，它们可以中止事务。

正如我们之前讨论的，2PC无法从协调者故障中恢复，并且参与者可能卡在未决状态，直到协调者恢复为止。3PC避免了在这种情况下阻塞流程，并允许参与者以一个确定性的决策继续执行。

3PC的最坏场景是网络分区，如图13-6所示。一些节点已成功进入准备状态，在超时后将会继续进行提交。有些节点无法与协调者通信，因此会在超时后中止。这导致了脑裂：根据协议，一些节点会继续进行提交，另一些节点会中止，使得各个参与者处于不一致且矛盾的状态。

图13-6：第二阶段中，协调者发生故障

虽然从理论上说3PC确实在某种程度上可以解决2PC的阻塞问题，但却带来了更大的消息开销与潜在的不一致性，并且在出现网络分区的情况下无法很好地工作。这或许是3PC未被广泛使用的主要原因。

4 Calvin分布式事务

我们已经了解了同步的代价以及相关的几种事务方法。但是，还有其他方法可以减少争用并减少事务持有锁的总时间。一种方法是让各副本在获取锁并继续执行之前，就执行顺序和事务边界达成一致。如果我们能够做到这一点，节点故障就不会导致事务中止，因为节点可以从并行执行同一事务的其他参与者中恢复状态。

传统数据库使用两阶段锁或乐观并发控制来执行事务，并没有确定的事务顺序。这意味着必须协调各节点以保证事务顺序。而确定性事务顺序消除了执行阶段的协调开销，因为所有副本获得相同的输入，所以也会得到等同的输出。这种方法通常称为Calvin—一种快速的分布式事务协议[THOMSON12]。使用Calvin实现分布式事务的一个著名例子是FaunaDB。

为了获得确定性顺序，Calvin使用定序器（sequencer），它是所有事务的入口点。定序器决定事务的执行顺序，并建立全局事务输入序列。为了最大限度地减少竞争和批量决策，Calvin将时间线切分成epoch。定序器收集事务并将其分组到短时间窗口内（原论文使用10毫秒的窗口），这些窗口也就成为复制单元，因此不需要为每个事务单独进行通信。

当一个事务批被成功复制之后，定序器会将其转发给调度器（scheduler），它负责编排事务的执行。调度器使用确定性调度协议，可以并行执行部分事务，并同时保留定序器指定的串行执行顺序。将事务应用于特定状态只会产生由事务指定的更改，并且事务顺序是预先确定的，因此，各副本无须与定序器做更多的通信。

Calvin中的每个事务具有读取集（事务执行的依赖，即执行事务所需的当前状态的数据记录集合）和写入集（事务执行的结果，也就是它的副作用）。Calvin本身不支持事务依赖于额外的读取来决定读取集和写入集。

Calvin的工作者线程（由调度器管理）的执行过程分为四个步骤：

    1.　分析事务的读取集和写入集，用读取集确定节点本地的数据记录，并创建活跃参与者的列表（即包含写入集元素且将对这些数据进行修改的参与者）。

    2.　收集执行事务所需的本地数据，换句话说，收集恰好位于该节点上的读取集记录。收集到的数据记录将被转发给相应的活跃参与者。

    3.　如果当前工作线程正在一个活跃参与者节点上执行，它将接收到其他参与者发来的数据记录，对应于步骤2中执行的操作。

    4.　最后，执行一批事务，将结果持久化到本地存储中。不用将执行结果转发到其他节点，因为它们接收相同的事务输入，可以自己在本地执行并持久化结果。

一个典型Calvin的实现将定序器、调度器、工作者和存储子系统放在一起，如图13-7 所示。为了确保各个定序器就当前epoch/批包含哪些事务达成共识，Calvin使用Paxos共识算法（参见14.3节）或异步复制（其中某个专用副本作为领导者）。尽管使用领导者可以改善延迟，但节点必须重建故障领导者的状态才能继续，因此也带来了更高的恢复成本。

图13-7：Calvin的架构

5 Spanner分布式事务

Calvin常常被拿来和另一个称为Spanner[CORBETT12]的分布式事务方法进行对比。Spanner的实现（或派生）包括几个开源数据库，最著名的是CockroachDB和YugaByte DB。Calvin通过在定序器上达成共识来建立全局事务执行顺序，Spanner则在每个分区的共识组（换句话说，每个分片）上使用两阶段提交。Spanner的架构相当复杂，本书中我们仅介绍一些高层次上的细节。

为了实现一致性并建立事务的顺序关系，Spanner使用TrueTime：一种高精度的物理时钟API，同时也暴露时钟误差的范围，允许本地操作中引入人为的减速以等待时钟误差范围过去。

Spanner提供三种主要的事务类型：读写事务、只读事务和快照读。读写事务需要加锁，使用悲观的并发控制，并且存在领导者（leader）副本。只读事务是无锁的，可以在任何副本上执行。只有在读取最新时间戳时才需要领导者，领导者负责从Paxos 组中获取最后提交的值。对特定时间戳的读取是一致的，因为数据有版本，而快照的内容一旦写入就无法更改。每个数据记录都会被分配一个时间戳，记录了写入该值的事务的提交时间。这也意味着每条记录可能存在多个时间戳的版本。

图13-8展示了Spanner的架构。每个spanserver（副本，向客户端提供数据的服务器实例）包含多个tablet，每个tablet对应一个Paxos（参见14.3节）状态机。副本被分组为副本集，称为Paxos组，这是数据放置和复制的单元。每个Paxos组都有一个长期的领导者（参见14.3.4节）。在处理跨分片的事务时，领导者会相互通信。

图13-8：Spanner的架构

每个写入操作必须通过Paxos组的领导者，而读取可以直接在最新副本的tablet上进行。领导者上有锁表（lock table）和事务管理器，锁表用于使用两阶段锁（参见5.3.8节）机制来实现并发控制，事务管理器负责跨分片的分布式事务。需要同步的操作（例如事务内的写入和读取）必须先从锁表中获取锁，而其他操作（快照读）可以直接访问数据。

对于跨分片的事务，Paxos组领导者必须协调并执行两阶段提交以保证一致性，并使用两阶段锁保证隔离性。2PC算法要求所有参与者都存活才能成功提交，因而可能会损害可用性。而Spanner使用Paxos组代替单个节点作为参与者，解决了这一问题。这意味着即使组内的某些成员宕机，2PC也可以继续运行。在Paxos组内部，只有领导者节点会参与2PC。

Paxos组用于在多个节点之间一致地复制事务管理器的状态。在执行事务时，Paxos组的领导者首先获取写锁，并选择一个写入时间戳—该时间戳必须比之前任何事务的时间戳要大，并通过Paxos记录一条2PC的prepare日志。事务协调者收集时间戳，随后生成一个大于任何准备时间戳（prepare timestamp）的提交时间戳（commit timestamp），并通过Paxos记录一条commit日志。然后，事务协调者需要等待直到提交时间戳过后，因为它必须保证客户端只能看到时间戳已经过去的事务结果。之后，它将此时间戳发送给客户端和各个领导者，领导者将一条commit日志连同新的时间戳一同记录到其所在的Paxos组中，此时便可以释放锁。

单分片事务无须与事务管理器通信（并且之后也不必进行跨分区的两阶段提交），因为查询Paxos组和锁表足以保证事务顺序和分片内部的一致性。

Spanner读写事务提供了称为外部一致性（external consistency）的序列化顺序：事务时间戳反映了序列化顺序，即使在分布式事务中也是如此。外部一致性具有与可线性化（linearizability）等效的实时属性：如果事务T1在T2开始之前提交，则T1的时间戳小于T2的时间戳。

总结一下，Spanner使用Paxos进行一致的事务日志复制，使用两阶段提交进行跨分片事务，使用TrueTime进行确定性事务排序。相比Calvin [ABADI17]，Spanner跨分区事务的成本更高，因为多出了一个两阶段提交的过程。理解这两种方法都很重要，依靠它们，我们能够在分区的分布式数据存储中执行事务。

6 数据库分区

讨论Spanner和Calvin时，我们经常用到分区（partitioning）这个词。现在我们来更详细地讨论一下它。对于大多数现代应用程序而言，将所有数据存储在单个节点上是不现实的，因此许多数据库都使用分区：逻辑上将数据分成较小的、易于管理的段。

数据分区最直接的方法是将数据划分成多个范围，并允许每个副本集（replica set）只管理特定的范围（分区）。执行查询时，客户端（或查询协调者）需要基于路由键将读写请求路由到正确的副本集。这种分区方案通常称为分片（sharding）：每个副本集作为数据某个子集的单个来源。

为了最有效地使用分区，必须考虑负载和值的分布并据此确定分区大小。这意味着可以将读写负担较重的范围分裂成更小的分区，从而分散负载。同时，如果某些范围包含的值比其他范围更密集，最好也将它们分裂成更小的分区。例如，假如我们选择邮编作为路由键，由于人口分布并不均匀，一些邮编范围可能分配到更多的数据（比如人或订单）。

当集群添加或删除节点时，数据库必须重新分区数据以保持均衡。为了保证数据迁移过程的一致性，我们应当在更新集群元数据及开始将请求路由到新的位置目标之前先搬运数据。一些数据库可以进行自动分片（auto-sharding），使用算法来决定最佳分区方式，并重新放置数据。这些算法通常基于各分片的读取和写入负载以及数据量等信息来进行决策。

为了从路由键找到目标节点，一些数据库计算路由键的哈希值，并通过某种方式将哈希值映射到节点ID。使用哈希确定副本位置的一个优点是能够减少范围热点，因为哈希值与原始值的排列顺序不同。两个字典序接近的路由键原本会被放在同一副本集上，但如果用哈希值，则会被放在不同副本集上。

将哈希值映射到节点ID的最直接的方法是将哈希值除以集群大小再取其余数（取模）。如果系统中有N个节点，则目标节点ID可以通过hash(v) mod N算出。该方法的主要问题是，每当添加或删除节点、集群大小从N更改为N'时，hash(v) mod N'算出的很多值都和原来不同。这意味着大部分数据都要被移动。

一致性哈希

为了缓解该问题，一些数据库（例如Apache Cassandra和Riak）使用一种叫作一致性哈希（consistent hashing）的分区方案。如前所述，路由键的值被输入哈希函数，返回的哈希值被映射到一个环上，以便在超过最大值之后回卷到最小值。每个节点在环上拥有自己的位置，负责前一个节点到当前节点之间的值范围。

使用一致性哈希能减少维持数据均衡所需的移动次数：节点离开或加入只会影响到环上与该节点直接相邻的节点，而不影响整个集群。定义中的一致性表示：当哈希表大小发生变化时，如果我们有K个可能的哈希键和n个节点，平均而言，我们仅需移动K/n个键。也就是说，一致性哈希函数的输出受函数范围变化的影响最小[KARGER97]。

7 Percolator分布式事务

回到分布式事务上来，由于允许一些读取和写入异常，隔离级别可能很难论证。如果应用程序不要求可串行化，避免写入异常的一种方法是使用SQL-92中描述的快照隔离（Snapshot Isolation，SI）事务模型。

快照隔离保证事务内的所有读取结果与数据库的某个快照一致。快照中包含了在事务的开始时间戳之前提交的所有值。如果存在写-写冲突（即，两个并发执行的事务尝试写入同一单元格），那么只有一个能够提交成功。这种策略通常称为首个提交者胜利（first committer wins）。

快照隔离能避免读偏斜（read skew）—一种在读已提交隔离级别下允许的异常。例如，x、y之和应该等于100。事务T1执行操作read(x)读到值70。T2更新两个值write(x, 50)和write(y, 50)并提交。如果T1尝试运行read(y)，并根据T2新提交的y的值（50）继续执行事务，将会导致不一致。T1在T2提交之前读到的值x与新的y值彼此不一致。而快照隔离仅会让小于某个特定的时间戳的值对事务可见，新的y值对T1不可见[BERENSON95]。

快照隔离有几个实用的特性：

• 它只允许对已提交数据的可重复读取。

• 值是一致的，因为它们是从某个时间戳的快照中读取的。
  

• 冲突的写入将被中止并重试，以防止产生不一致。

尽管如此，快照隔离下的操作历史不是可串行化的。由于只有对相同单元格的冲突写入会被中止，因此仍可能发生写偏斜（write skew）（参见5.3.3节）。写偏斜发生在两个事务修改的值集合不相交时，每个事务本身的写入都不违反约束。两个事务都能提交，但两个事务的写入合在一起就会违反这些约束。

快照隔离提供的语义可以满足许多应用程序的需求，其主要优势在于读的效率较高，因为不需要加锁—快照数据是无法修改的。

Percolator是一个在分布式数据库Bigtable（参见1.3.4节）上实现事务API的库。这是在现有系统之上构建事务API的一个很好的例子。Percolator用不同的列保存数据记录、已提交的数据点位置（写入元数据）和锁信息。为了避免竞争条件，它使用Bigtable提供的条件修改API，该API允许在单个远程调用中执行读-修改-写操作。

每个事务必须和授时节点（timestamp oracle）通信两次（授时节点负责为整个集群提供单调递增的时间戳）：一次获取事务开始时间戳，另一次是在提交过程中。写入会先被缓存起来，最后由客户端驱动进行两阶段提交（请参阅13.2节）。

图13-9展示了在执行事务的各步骤期间表的内容如何变化：

• a) 初始状态。

  执行完上一个事务后，TS1是两个账户的最新时间戳。

  没有锁。

• b) 第一个阶段称为预写（prewrite）。

  事务尝试为所有写入的单元格加锁。

  其中一个锁被标记为主（primary）锁，用于客户端恢复。

  事务会检查是否存在可能的冲突：

  是否存在其他事务已经用更晚的时间戳写入了数据，或者在任何时间戳下是否存在未释放的锁。

  如果检测到冲突则中止事务。

• c) 如果成功获取了所有锁即排除了冲突的可能性，事务便可以继续执行。

  第二阶段中，客户端开始释放这些锁，首先释放主锁。

  它用写记录替换锁，通过该操作让写入对外可见，并更新写入元数据为最新数据点的时间戳。

由于客户端在提交事务时可能会发生故障，因此我们需要确保进行到一半的事务能被提交或回滚。如果之后的事务遇到一个不完整的状态，则应尝试释放主锁并提交事务。如果主锁已经释放，那么事务内容必须被提交。同一时刻只可以有一个事务持有某个锁，而且所有状态转换都是原子的，因此不存在两个事务都在尝试修改内容的情况。

快照隔离是一种很重要也很有用的抽象，经常用在事务处理中。它简化了语义，排除了一些异常情况，并为改善并发性和性能提供了机会，因此许多MVCC系统都提供这种隔离级别。

图13-9：Percolator事务的执行步骤。事务从账户2向账户1转账 $150

一个基于Percolator模型的数据库的例子是TiDB（Ti代表钛元素）。TiDB是一个强一致、高可用、可水平扩展的开源数据库，兼容MySQL。

8 协调避免

讨论可串行化性的成本并尝试减少协调量，同时仍提供强大的一致性保证的另一个例子是协调避免[BAILIS14b]。在保持数据完整性约束的前提下，只要操作满足约束融合性，协调是可以避免的。约束融合性（Invariant Confluence或I-Confluence）定义为这样一种属性：两个满足约束但存在分歧的数据库状态一定能够合并为一个有效的最终状态。这里说的约束对应ACID中的一致性。

由于可以将任何两个有效状态合并为一个有效状态，因此满足约束融合性的操作不需额外协调就可以直接执行，这显著地提高了性能和可扩展性。

为了保持约束，除了定义修改数据库的操作之外，我们还必须定义一个合并（merge）函数，它接受两个状态作为输入。当状态被独立地修改时，可以用合并函数将分歧的状态重新收敛。

事务在本地的数据库版本（快照）上执行。如果事务执行需要用到其他分区中的某些状态，就把该状态也放到本地。事务提交时，产生的本地快照的改动会被迁移并和其他节点的快照合并。允许协调避免的系统模型必须保证以下性质：

全局有效性

    无论对于合并后的状态，还是刚提交的存在分歧的状态，所需的约束条件始终是满足的，事务不会观察到无效的状态。

可用性

    如果所有包含状态的节点对客户端都是可达的，那么事务必然会成功提交，除非提交将违反某个事务约束，这种情况下事务会中止。

收敛

    节点可以独立维护其本地状态，但如果之后没有新的事务并且网络分区不会无限持续下去，它们一定能够达到相同的状态。

不需协调

    本地事务的执行独立于为其他节点执行的对本地状态的操作。

一个实现协调避免的例子是读原子性多分区（Read-Atomic Multi Partition, RAMP）事务[BAILIS14c]。RAMP使用多版本并发控制和当前进行中操作的元数据来从其他节点获取缺失的状态更新，从而允许读取和写入操作能够并发进行。例如，如果读取操作与某些修改相同的条目的写入操作存在重叠，这种情况可以被检测出来，必要时，还可以通过一轮额外的通信，利用正在进行的写入操作的元数据获取所需的信息来对其进行修复。

在分布式环境下使用基于锁的方法可能不是个好主意，相反，RAMP提供以下两个性质：

同步独立性

    一个客户端的事务不会阻塞、中止或是强迫另一个客户端的事务等待。

分区独立性

    客户端无须联系那些事务不涉及的分区。

RAMP引入了读原子性（read atomic）隔离级别：事务不会观察到来自进行中的、未提交的或中止事务的正在进行的状态变更。换句话说，事务更新要么全都对并发事务可见，要么全都不可见。根据该定义，读原子性隔离级别还排除了断裂读（fractured read）：即事务仅观察到其他事务执行的写入的一个子集。

RAMP提供原子的写可见性，而不需要互斥—其他解决方案（例如分布式锁）往往将这两者耦合在一起。这意味着事务不会相互阻塞。

RAMP分发事务元数据，这些元数据允许读取操作检测到并发进行的写入。通过元数据，事务可以检测到较新的记录版本，找到并获取最新的记录版本，然后对它们进行操作。为了避免协调，所有本地的提交决定也必须在全局范围内生效。在RAMP中，这是通过以下要求解决的：当某个分区中的写入变为可见时，此事务中所有其他分区的写入也必须可见。

为了使得读写操作不阻塞其他并发的读写操作，同时在本地和整个系统范围内（事务修改过的所有其他分区中）都保持读原子性隔离级别，RAMP使用两阶段提交来处理写入操作：

准备阶段

    第一阶段准备写操作并将其放到相应的目标分区中，但不使其对外可见。

提交/中止阶段

    第二阶段将事务的写操作进行的状态更改变得可见，使其在所有分区上原子地变得可用，或者回滚更改。

RAMP允许一个记录同时存在多个版本：最新值、进行中的未提交更改，以及被后来的事务覆盖掉的过期版本。之所以需要保留过期版本，仅仅是为了正在进行中的读取请求。只要所有并发的读操作结束，就可以丢弃过期的值。

为了防止、检测、避免并发操作之间的冲突，往往需要引入协调开销，因此，想让分布式事务高效且可扩展并不容易。系统越大，承载的事务越多，产生的协调开销也就越大。本节中描述的方法尝试用约束条件来确定可以避免协调的地方，从而减少协调的量，只在绝对必要时才付出全部的代价。

9 本章小结

本章中，我们讨论了实现分布式事务的几种方法。首先，我们讨论了两种原子提交算法：两阶段提交和三阶段提交。这两种算法的最大优点是易于理解和实现，但也有一些缺点。在2PC中，协调者（或至少是它的代替者）必须在整个提交过程中都存活，这会大大降低可用性。3PC在一些情况下取消了这个要求，但在网络分区的情况下可能发生脑裂。

现代数据库系统中的分布式事务通常使用共识算法来实现，我们将在第14章中进行讨论。例如，本章讨论的Calvin和Spanner都使用Paxos。

共识算法比原子提交算法更复杂，但是具有更好的容错性，并且将决策结果与发起者分离开来，允许参与者决定一个值，而不是决定是否接受那个值[GRAY04]。

更多阅读

如果你想了解更多本章中提到的概念，可以参考以下来源：

原子提交与本地事务处理及恢复子系统的集成

Silberschatz, Abraham, Henry F. Korth, and S. Sudarshan. 2010. Database Systems Concepts (6th Ed.). New York: McGraw-Hill.

Garcia-Molina, Hector, Jeffrey D. Ullman, and Jennifer Widom. 2008. Database Systems: The Complete Book (2nd Ed.). Boston: Pearson.

分布式事务领域的最新进展（按时间顺序排列，此列表并不详尽）

Cowling, James and Barbara Liskov. 2012. “Granola: low-overhead distributed transaction coordination.” In Proceedings of the 2012 USENIX conference on Annual Technical Conference (USENIX ATC �12): 21-21. USENIX.

Balakrishnan, Mahesh, Dahlia Malkhi, Ted Wobber, Ming Wu, Vijayan Prabha-karan, Michael Wei, John D. Davis, Sriram Rao, Tao Zou, and Aviad Zuck. 2013.“Tango: distributed data structures over a shared log.” In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP �13): 324-340.

Ding, Bailu, Lucja Kot, Alan Demers, and Johannes Gehrke. 2015. “Centiman: elastic, high performance optimistic concurrency control by watermarking.” In Proceedings of the Sixth ACM Symposium on Cloud Computing (SoCC �15): 262-275.

Dragojevi, Aleksandar, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, and Miguel Castro. 2015. “No compromises: distributed transactions with consistency, availability, and performance.” In Proceedings of the 25th Symposium on Operating Systems Principles(SOSP �15): 54-70.

Zhang, Irene, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2015. “Building consistent transactions with inconsistent replication.” In Proceedings of the 25th Symposium on Operating Systems Principles(SOSP �15): 263-278

《数据库系统内幕 》一书由机械工业出版社出版

 往期推荐：

— END —

技术琐话 

以分布式设计、架构、体系思想为基础，兼论研发相关的点点滴滴，不限于代码、质量体系和研发管理。