分布式之系统底层原理（上）

作者：allanpan，腾讯 IEG 高级后台工程师

导言

分布式事务是分布式系统必不可少的组成部分，基本上只要实现一个分布式系统就逃不开对分布式事务的支持。本文从分布式事务这个概念切入，尝试对分布式事务以及分布式系统最核心的底层原理逐一进行剖析，内容包括但不限于 BASE 原则、两阶段原子提交协议、三阶段原子提交协议、Paxos/Multi-Paxos 分布式共识算法的原理与证明、Raft 分布式共识算法和分布式事务的并发控制等内容。

事务

事务是访问并可能更新各种数据项的一个程序执行单元(unit)。事务由一个或多个步骤组成，一般使用形如 begin transaction 和 end transaction 语句或者函数调用作为事务界限，事务内的所有步骤必须作为一个单一的、不可分割的单元去执行，因此事务的结果只有两种：1. 全部步骤都执行完成，2. 任一步骤执行失败则整个事务回滚。

事务最早由数据库管理系统(database management system，DBMS)引入并实现，数据库事务是数据库管理系统执行过程中的一个逻辑单位，由一个有限的数据库操作序列构成。数据库事务严格遵循 ACID 原则，属于刚性事务，一开始数据库事务仅限于对单一数据库资源对象的访问控制，这一类事务称之为本地事务 (Local Transaction)，后来随着分布式系统的出现，数据的存储也不可避免地走向了分布式，分布式事务（Distributed Transaction）便应运而生。

刚性事务

刚性事务（如单一数据库事务）完全遵循 ACID 规范，即数据库事务的四大基本特性：

• Atomicity（原子性）：一个事务（transaction）中的所有操作，或者全部完成，或者全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。即，事务不可分割、不可约简。

• Consistency（一致性）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设约束、触发器、级联回滚等。

• Isolation（隔离性）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括未提交读（Read uncommitted）、提交读（read committed）、可重复读（repeatable read）和串行化（Serializable）。

• Durability（持久性）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

刚性事务也能够以分布式 CAP 理论中的 CP 事务来作为定义。

柔性事务



在电商领域等互联网场景下，传统的事务在数据库性能和处理能力上都遇到了瓶颈。因此，柔性事务被提了出来，柔性事务基于分布式 CAP 理论以及延伸出来的 BASE 理论，相较于数据库事务这一类完全遵循 ACID 的刚性事务来说，柔性事务保证的是 “基本可用，最终一致”，CAP 原理相信大家都很熟悉了，这里我们讲一下 BASE 原则：

• 基本可用（Basically Available）：系统能够基本运行、一直提供服务。

• 软状态（Soft-state）：系统不要求一直保持强一致状态。

• 最终一致性（Eventual consistency）：系统需要在某一时刻后达到一致性要求。

柔性事务（如分布式事务）为了满足可用性、性能与降级服务的需要，降低一致性（Consistency）与隔离性（Isolation）的要求，遵循 BASE 理论，传统的 ACID 事务对隔离性的要求非常高，在事务执行过程中，必须将所有的资源对象锁定，因此对并发事务的执行极度不友好，柔性事务（比如分布式事务）的理念则是将锁资源对象操作从本地资源对象层面上移至业务逻辑层面，再通过放宽对强一致性要求，以换取系统吞吐量的提升。

此外，虽然柔性事务遵循的是 BASE 理论，但是还需要遵循部分 ACID 规范：

• 原子性：严格遵循。

• 一致性：事务完成后的一致性严格遵循；事务中的一致性可适当放宽。

• 隔离性：并行事务间不可影响；事务中间结果可见性允许安全放宽。

• 持久性：严格遵循。

本地事务

本地事务（Local Transaction）指的是仅仅对单一节点/数据库资源对象进行访问/更新的事务，在这种事务模式下，BASE 理论派不上用场，事务完全遵循 ACID 规范，确保事务为刚性事务。

分布式事务

在分布式架构成为主流的当下，系统对资源对象的访问不能还局限于单节点，多服务器、多节点的资源对象访问成为刚需，因此，本地事务无法满足分布式架构的系统的要求，分布式事务应运而生。

访问/更新由多个服务器管理的资源对象的平面事务或者嵌套事务称之为分布式事务（Distributed Transaction），分布式事务是相对于本地事务来说的。

平面事务：单一事务，访问多个服务器节点的资源对象，一个平面事务完成一次请求之后才能发起下一个请求。

嵌套事务：多事务组成，顶层事务可以不断创建子事务，子事务又可以进一步地以任意深度嵌套子事务。



对于分布式事务来说，有两个最核心的问题：

1. 如何管理分布式事务的提交/放弃决定？如果事务中的一个节点在执行自己的本地事务过程中遇到错误，希望放弃整个分布式事务，与此同时其他节点则在事务执行过程中一切顺利，希望提交这个分布式事务，此时我们应该如何做决策？

2. 如何保证并发事务在涉及多个节点上资源对象访问的可串行性（规避分布式死锁）？如果事务 T 对某一个服务器节点上的资源对象 S 的并发访问在事务 U 之前，那么我们需要保证在所有服务器节点上对 S 和其他资源对象的冲突访问，T 始终在 U 之前。

问题 1 的解决需要引入一类分布式原子提交协议的算法如两阶段提交协议等，来对分布式事务过程中的提交或放弃决策进行管理，并确保分布式提交的原子性。而问题 2 则由分布式事务的并发控制机制来处理。

原子提交协议

原子性是分布式事务的前置性约束，没有原子性则分布式事务毫无意义。

原子性约束要求在分布式事务结束之时，它的所有操作要么全部执行，要么全部不执行。以分布式事务的原子性来分析，客户端请求访问/更新多个服务器节点上的资源对象，在客户端提交或放弃该事务从而结束事务之后，多个服务器节点的最终状态要么是该事务里的所有步骤都执行成功之后的状态，要么恢复到事务开始前的状态，不存在中间状态。满足这种约束的分布式事务协议则称之为原子提交协议。

当一个分布式事务结束时，事务的原子特性要求所有参与该事务的服务器节点必须全部提交或者全部放弃该事务，为了实现这一点，必须引入一个协调者（Coordinator）的角色，从参与事务的所有服务器节点中挑选一个作为协调者，由它来保证在所有服务器节点上最终获得同样的结果。协调者的工作原理取决于分布式事务选用的协议。

一般来说，分布式事务中包含的两个最基础的角色就是：

• Coordinator -- 协调者

• Participants -- 参与者



单阶段原子提交协议

单阶段原子提交协议（one-phase atomic commit protocol, 1APC）是最简单的一种原子提交协议，它通过设置一个协调者并让它不断地向所有参与者发送提交（commit）或放弃（abort）事务的请求，直到所有参与者确认已执行完相应的操作。

1APC 协议的优点是简单易用，对一些事务不复杂的场景比较合适，但在复杂事务场景则显得捉襟见肘，因为该协议不允许任何服务器节点单方面放弃事务，事务的放弃必须由协调者来发起，这个设计会导致很多问题：首先因为只有一次通信，协调者并不会收集所有参与者的本地事务执行的情况，所以协调者决定提交还是放弃事务只基于自己的判断，在参与者执行事务期间可能会遇到错误从而导致最终事务未能真正提交，错误一般与事务的并发控制有关，比如事务执行期间对资源对象加锁，遇到死锁，需要放弃事务从而解开死锁，而协调者并不知道，因此在发起下一个请求之前，客户端完全不知道事务已被放弃。另一种情况就是利用乐观并发控制机制访问资源对象，某一个服务器节点的验证失败将导致事务被放弃，而协调者完全不知情。

两阶段提交协议

定义

两阶段提交协议（two-phase commit protocol, 2PC）的设计初衷是为了解决 1APC 不允许任意一个服务器节点自行放弃它自己的那部分本地事务的痛点，2PC 允许任何一个参与者自行决定要不要放弃它的本地事务，而由于原子提交协议的约束，任意一个本地事务被放弃将导致整个分布式事务也必须放弃掉。

两阶段提交协议基于以下几个假设：

• 存在一个节点作为协调者（Coordinator），分布式事务通常由协调者发起（当然也可以由参与者发起），其余节点作为参与者（Participants），且节点之间可以自由地进行网络通信，协调者负责启动两阶段提交流程以及决定事务最终是被提交还是放弃。

• 每个节点会记录该节点上的本地操作日志（op logs），日志必须持久化在可靠的存储设备上（比如磁盘），以便在节点重启之后需要恢复操作日志。另外，不记录全局操作日志。

• 所有节点不能发生永久性损坏，也就是说节点就算是损坏了也必须能通过可靠性存储恢复如初，不允许出现数据永久丢失的情况。

• 参与者对协调者的回复必须要去除掉那些受损和重复的消息。

• 整个集群不会出现拜占庭故障（Byzantine Fault）-- 服务器要么崩溃，要么服从其发送的消息。

原理

两阶段提交协议，顾名思义整个过程需要分为两个阶段：

1. 准备阶段（Prepare Phase）

2. 提交阶段（Commit Phase）

在进行两阶段提交的过程中，协调者会在以下四种状态间流转：

1. init

2. preparing

3. committed

4. aborted

而参与者则会在以下三种状态间流转：

1. working

2. prepared

3. committed

阶段 I（投票表决阶段）

1. 任意一个参与者发起分布式事务 T 并执行本地事务成功，接着将一条 <ready T> 记录追加到本地日志 buffer 中并 flush 到可靠性存储设备如磁盘上，从 working 状态进入 prepared 状态，然后向协调者发送 prepare T 消息；

2. 收到参与者发来的 prepare T 消息后，协调者将一条 <prepare T> 记录追加到日志中，然后从 init 状态进入 preparing 状态，紧接着向分布式事务的其他参与者发出 canCommit? 消息，发起事务表决过程；

3. 当参与者收到 canCommit? 请求后，除了发起事务的那一个之外，其他还在working 状态的参与者会先尝试执行本地事务，如果本地事务执行成功，则会往本地日志 buffer 写入一条 <ready T> 记录并 flush 到可靠性存储中，但不提交事务，进入 prepared 状态，然后回复一条 ready T 消息对此事务投 YES 票；如果本地事务执行失败，则参与者会往本地日志 buffer 写入一条 <don't commit T> 记录并 flush 到可靠性存储中，然后回复一条 don't commit T 消息投 NO 票。

阶段 II（收集投票结果完成事务）

1. 协调者收集所有的投票（包括它自己的投票）；(a) 如果所有的投票都是 ready T，则表示没有故障发生，那么协调者决定提交该事务，首先它会在其本地日志中追加一条 <commit T> 记录，从 preparing 状态进入committed 状态，然后向所有的参与者发送 doCommit 请求消息，要求参与者提交它们的本地事务；(b) 如果有任一个投票是 No，则协调者决定放弃掉该事务，首先它会往本地日志中追加一条记录，从 preparing 状态进入 aborted 状态，然后发送 doAbort 请求消息给所有的参与者，通知它们回滚各自的本地事务。

2. 投了 YES 票的参与者阻塞等待协调者给它发来 doCommit 或 doAbort 消息，如果接收到的是 doCommit 消息则提交本地事务并在此过程中记录日志 <commit T>，然后进入 committed 状态，最后回复一个 haveCommitted 的消息通知协调者本地事务已经成功提交；反之，如果收到的是 doAbort 消息则回滚本地事务并写入日志<abort T>，然后进入 aborted状态。

上面的过程是一种更通用的流程，即由任意的参与者发起一个分布式事务，而在实践中一般把分布式事务的发起交给协调者来做，减少事务发起者确认该事务已被提交所需等待的网络消息延迟：



性能

网络 I/O 开销

假设两阶段提交过程一切运行正常，即协调者和参与者都不出现崩溃和重启，网络通信也都正常。那么假设有一个协调者和 N 个参与者，两阶段提交过程中将会发送如下的消息：

• 任意一个参与者从 working 状态进入 prepared 状态并发送 Prepared 消息给协调者，1 条消息。

• 协调者收到消息后，向其他参与者发送 canCommit? 请求消息，N - 1 条消息。

• 收到 canCommit? 消息的参与者各自回复协调者投票消息，N - 1 条消息。

• 协调者统计投票情况之后，发送 doCommit 消息给其他参与者，N 条消息。

所以，事务发起者在经过 4 条网络消息延迟之后确认该分布式事务已被提交，而整个过程共计发送 3N - 1 条网络消息（因为 haveCommitted 在 2PC 仅仅是用于最后通知协调者而已，属于可有可无的一次网络消息，2PC 在该消息缺省的情况下也能正常运行，因此 haveCommitted 一般不计入网络延迟成本中）。

前面我们提到，在实践中一般是由协调者来发起事务，如果考虑这种情况的话，事务发起者 -- 协调者在经过 3 条网络消息延迟之后确认该分布式事务已经被提交，而整个过程实际发送的网络消息则变成 3N 条。

总而言之，两阶段提交协议的网络通信开销和集群节点的数量成 3 倍正比。

本地存储设备 I/O 开销

基于前文中叙述的两阶段提交协议的基本假设之一：每个节点会通过日志来记录在本地执行的操作，以便在节点发生故障并重启节点之后能利用日志恢复到故障前的状态，因此两阶段提交过程中除了网络 I/O 的开销之外，还有本地存储设备 I/O 的开销：

• 发起事务的参与者执行本地事务，1 次写操作。

• 其余参与者执行各自的本地事务，N - 1 次写操作。

• 协调者统计投票结果并决定提交事务，1 次写操作。

所以事务发起者在经过 3 次本地存储设备 I/O 延迟之后确认该事务已被提交，整个过程总计有 N + 1 次本地存储设备 I/O，而如果由协调者来发起事务的话，则还是需要 N + 1 次本地存储设备 I/O，但是只需要经过 2 次本地存储设备 I/O 延迟即可确认事务已被提交。

恢复

在分布式事务中，所有的参与者节点都可能发生故障，所以我们需要保证在该故障节点恢复时发生的一切都和分布式事务 T 的全局决策保持一致。节点在恢复的时候会读取 T 的最后一个本地日志记录并作出相应的操作：

1. 如果 T 的最后一条日志记录是 <commit T>，那么说明协调者在节点发生故障时的全局决策是提交 T，根据本地事务所使用的日志方式，在该节点上可能需要执行 redo T。

2. 如果 T 的最后一条日志记录是 <abort T>，那么说明协调者在节点发生故障时的全局决策是中止 T，根据本地事务所使用的日志方式，在该节点上可能需要执行 undo T。

3. 如果 T 的最后一条日志记录是 <don't commit T>，则和第 2 中情况类似，执行 undo T。

4. 如果 T 的最后一条日志记录是 <ready T>，这种情况比较麻烦，因为恢复节点无法确认在它故障之后协调者发出的最终全局决策是什么，因此它必须要和集群中其余至少一个节点取得联系，询问 T 的最终结果是什么：恢复节点先尝试询问协调者，如果此时协调者正在工作，则告知恢复节点 T 的最终结果，如果是提交就执行 redo T，中止就执行 undo T；如果协调者因故不在工作，则恢复节点可以要求其他某一个参与者节点去查看本地日志以找出 T 的最终结果并告知恢复节点。在最坏的情况下，恢复节点无法和集群中其他所有节点取得联系，这时恢复节点只能阻塞等待，直至得知 T 的最终结果是提交还是中止。

5. 如果本地日志中没有记录任何关于 T 在两阶段提交过程中的操作，那么根据前面的两阶段提交流程可知恢复节点还没来得及回复协调者的 canCommit? 请求消息就发生了故障，因此根据两阶段算法，恢复节点只能执行 undo T。

缺陷

1. 同步阻塞：两阶段提交协议是一个阻塞的协议，在第二阶段期间，参与者在事务未提交之前会一直锁定其占有的本地资源对象，直到接收到来自协调者的 doCommit 或 doAbort 消息。

2. 单点故障：两阶段提交协议中只有一个协调者，而由于在第二阶段中参与者在收到协调者的进一步指示之前会一直锁住本地资源对象，如果唯一的协调者此时出现故障而崩溃掉之后，那么所有参与者都将无限期地阻塞下去，也就是一直锁住本地资源对象而导致其他进程无法使用。

3. 数据不一致：如果在两阶段提交协议的第二阶段中，协调者向所有参与者发送 doCommit 消息之后，发生了局部网络抖动或者异常，抑或是协调者在只发送了部分消息之后就崩溃了，那么就只会有部分参与者接收到了 doCommit 消息并提交了本地事务；其他未收到 doCommit 消息的参与者则不会提交本地事务，因而导致了数据不一致问题。

XA 标准接口

2PC 两阶段提交协议本身只是一个通用协议，不提供具体的工程实现的规范和标准，在工程实践中为了统一标准，减少行业内不必要的对接成本，需要制定标准化的处理模型及接口标准，国际开放标准组织 Open Group 定义了分布式事务处理模型 DTP（Distributed Transaction Processing）Model，现在 XA 已经成为 2PC 分布式事务提交的事实标准，很多主流数据库如 Oracle、MySQL 等都已经实现 XA。

两阶段事务提交采用的是 X/OPEN 组织所定义的 DTP Model 所抽象的 AP（应用程序）, TM（事务管理器）和 RM（资源管理器） 概念来保证分布式事务的强一致性。 其中 TM 与 RM 间采用 XA 的协议进行双向通信。 与传统的本地事务相比，XA 事务增加了准备阶段，数据库除了被动接受提交指令外，还可以反向通知调用方事务是否可以被提交。 TM 可以收集所有分支事务的准备结果，并于最后进行原子提交，以保证事务的强一致性。



Java 通过定义 JTA 接口实现了 XA 模型，JTA 接口中的 ResourceManager 需要数据库厂商提供 XA 驱动实现， TransactionManager 则需要事务管理器的厂商实现，传统的事务管理器需要同应用服务器绑定，因此使用的成本很高。 而嵌入式的事务管器可以以 jar 包的形式提供服务，同 Apache ShardingSphere 集成后，可保证分片后跨库事务强一致性。

通常，只有使用了事务管理器厂商所提供的 XA 事务连接池，才能支持 XA 的事务。Apache ShardingSphere 在整合 XA 事务时，采用分离 XA 事务管理和连接池管理的方式，做到对应用程序的零侵入。

三阶段提交协议

由于前文提到的两阶段提交协议的种种弊端，研究者们后来又提出了一种新的分布式原子提交协议：三阶段提交协议（three-phase commit protocol, 3PC）。

三阶段提交协议是对两阶段提交协议的扩展，它在特定假设下避免了同步阻塞的问题。该协议基于以下两个假设：

1. 集群不发生网络分区；

2. 故障节点数不超过 K 个（K 是预先设定的一个数值）。

基于这两个假设，三阶段提交协议通过引入超时机制和一个额外的阶段来解决阻塞问题，三阶段提交协议把两阶段提交协议的第一个阶段拆分成了两步：1) 评估，2) 资源对象加锁，最后才真正提交：

1. CanCommit 阶段：协调者发送 CanCommit 请求消息，询问各个参与者节点，参与者节点各自评估本地事务是否可以执行并回复消息（可以执行则回复 YES，否则回复 NO），此阶段不执行事务，只做判断；

2. PreCommit 阶段：协调者根据上一阶段收集的反馈决定通知各个参与者节点执行（但不提交）或中止本地事务；有两种可能：1) 所有回复都是 YES，则发送 PreCommit请求消息，要求所有参与者执行事务并追加记录到 undo 和 redo 日志，如果事务执行成功则参与者回复 ACK 响应消息，并等待下一阶段的指令；2) 反馈消息中只要有一个 NO，或者等待超时之后协调者都没有收到参与者的回复，那么协调者会中止事务，发送 Abort 请求消息给所有参与者，参与者收到该请求后中止本地事务，或者参与者超时等待仍未收到协调者的消息，同样也中止当前本地事务。

3. DoCommit 阶段：协调者根据上一阶段收集到的反馈决定通知各个参与者节点提交或回滚本地事务，分三种情况：1) 协调者收到全部参与者回复的 ACK，则向所有参与者节点广播 DoCommit 请求消息，各个参与者节点收到协调者的消息之后决定提交事务，然后释放资源对象上的锁，成功之后向协调者回复 ACK，协调者接收到所有参与者的 ACK 之后，将该分布式事务标记为 committed；2) 协调者没有收到全部参与者回复的 ACK（可能参与者回复的不是 ACK，也可能是消息丢失导致超时），那么协调者就会中止事务，首先向所有参与者节点广播 Abort 请求消息，各个参与者收到该消息后利用上一阶段的 undo 日志进行事务的回滚，释放占用的资源对象，然后回复协调者 ACK 消息，协调者收到参与者的 ACK 消息后将该分布式事务标记为 aborted；3) 参与者一直没有收到协调者的消息，等待超时之后会直接提交事务。



事实上，在最后阶段，协调者不是通过追加本地日志的方式记录提交决定的，而是首先保证让至少 K 个参与者节点知道它决定提交该分布式事务。如果协调者发生故障了，那么剩下的参与者节点会重新选举一个新的协调者，这个新的协调者就可以在集群中不超过 K 个参与者节点故障的情况下学习到旧协调者之前是否已经决定要提交分布式事务，若是，则重新开始协议的第三阶段，否则就中止该事务，重新发起分布式事务。

在最后的 DoCommit 阶段，如果参与者一直没有收到协调者的 DoCommit 或者Abort 请求消息时，会在等待超时之后，直接提交事务。这个决策机制是基于概率学的：当已经进入第三阶段之后，说明参与者在第二阶段已经收到了 PreCommit 请求消息，而协调者发出 PreCommit 请求的前提条件是它在第二阶段开头收集到的第一阶段向所有参与者发出的 CanCommit 请求消息的反馈消息都是 YES。所以参与者可以根据自己收到了 PreCommit 请求消息这一既定事实得出这样的一个结论：其他所有参与者都同意了进行这次的事务执行，因此当前的参与者节点有理由相信，进入第三阶段后，其他参与者节点的本地事务最后成功提交的概率很大，而自己迟迟没有收到 DoCommit 或 Abort 消息可能仅仅是因为网络抖动或异常，因此直接提交自己的本地事务是一个比较合理的选择。

•