本文节选自《数据库系统内幕》第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所示。
准备阶段中，协调者分发提议的值，并收集各个参与者的投票：这个提议的值是否应该被提交。参与者可以选择拒绝协调者的提案，例如，当另一个冲突的事务已经提交了一个不同值的时候。
协调者收集投票之后，可以决定要提交事务还是中止事务。如果所有参与者均投了赞成票，它会决定提交并发送Commit消息通知它们。否则，协调者会向各个参与者发送Abort消息，事务将被回滚。换句话说，如果任意一个节点拒绝该提案，则整个流程将会中止。
每个步骤中，协调者和参与者都必须将各个操作的结果写入持久性存储中，以便能够在发生本地故障的情况下重建状态并恢复，并且可以将结果转发给其他参与者使其能够重放操作。
在数据库的语境下，每次2PC通常负责一个事务。在准备阶段，事务内容（操作、标识符和其他元数据）从协调者发送给参与者。参与者在本地执行事务，并停留在部分提交状态（也称为预提交状态），以让协调者在下一阶段通过提交或中止来完成执行。事务提交时，其内容已持久地存储到所有其他节点上[BERNSTEIN09]。
