关于分布式事务:分布式事务系统之底层原理揭秘

博客原文

分布式事务 / 零碎之底层原理揭秘

导言

分布式事务是分布式系统必不可少的组成部分，基本上只有实现一个分布式系统就逃不开对分布式事务的反对。本文从分布式事务这个概念切入，尝试对分布式事务最外围的底层原理逐个进行分析，内容包含但不限于 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，则协调者决定放弃掉该事务，首先它会往本地日志中追加一条 <abort T> 记录，从 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 音讯可能仅仅是因为网络抖动或异样，因而间接提交本人的本地事务是一个比拟正当的抉择。

三阶段提交协定次要着重于解决两阶段提交协定中因为协调者单点故障而引发的同步阻塞问题，尽管相较于两阶段提交协定有所优化，但还是没解决可能产生的数据不统一问题，比方因为网络异样导致局部参与者节点没有收到协调者的 Abort 申请音讯，超时之后这部分参与者会间接提交事务，从而导致集群中的数据不统一，另外三阶段提交协定也无奈解决脑裂问题，同时也因为这个协定的网络开销问题，导致它并没有被宽泛地应用，无关该协定的具体细节能够参阅本文最初的延长浏览一节中的文献进一步理解，这里不再深刻。

共识算法

共识（Consensus），很多时候会见到与一致性（Consistency）术语放在一起探讨。谨严地讲，两者的含意并不完全相同。

一致性的含意比共识宽泛，在不同场景（基于事务的数据库、分布式系统等）下意义不同。具体到分布式系统场景下，一致性指的是多个正本对外出现的状态。如后面提到的程序一致性、线性一致性，形容了多节点对数据状态的独特保护能力。而共识，则特指在分布式系统中多个节点之间对某个事件（例如多个事务申请，先执行谁？）达成一致意见的过程。因而，达成某种共识并不意味着就保障了一致性。

实际中，要保证系统满足不同水平的一致性，往往须要通过共识算法来达成。

共识算法解决的是分布式系统对某个提案（Proposal），大部分节点达成一致意见的过程。提案的含意在分布式系统中非常宽泛，如多个事件产生的程序、某个键对应的值、谁是主节点……等等。能够认为任何能够达成统一的信息都是一个提案。

对于分布式系统来讲，各个节点通常都是雷同的确定性状态机模型（又称为状态机复制问题，State-Machine Replication），从雷同初始状态开始接管雷同程序的指令，则能够保障雷同的后果状态。因而，零碎中多个节点最要害的是对多个事件的程序进行共识，即排序。

算法共识 / 一致性算法有两个最外围的束缚：1) 安全性（Safety），2) 存活性（Liveness）：

• Safety：保障决定（Value）后果是对的，无歧义的，不会呈现谬误状况。

  • 只有是被提案者提出的提案才可能被最终批准；
  • 在一次执行中，只批准（chosen）一个最终决定。被少数承受（accept）的后果成为决定；

• Liveness：保障决定过程能在无限工夫内实现。

  • 决定总会产生，并且学习者最终能取得被批准的决定。

Paxos

Google Chubby 的作者 Mike Burrows 说过，there is only one consensus protocol, and that’s Paxos”– all other approaches are just broken versions of Paxos.

意即 世上只有一种共识算法，那就是 Paxos，其余所有的共识算法都只是 Paxos 算法的完好版本。尽管有点果断，然而自从 Paxos 问世以来，它便简直成为了分布式共识算法的代名词，起初的许多利用宽泛的分布式共识算法如 Raft、Zab 等的原理和思维都能够溯源至 Paxos 算法。

Paxos 是由 Leslie Lamport (LaTeX 发明者，图灵奖得主，分布式畛域的世界级巨匠) 在 1990 年的论文《The PartTime Parliament》里提出的，Lamport 在论文中以一个古希腊的 Paxos 小岛上的议会制订法律的故事切入，引出了 Paxos 分布式共识算法。

Basic Paxos

业界个别将 Lamport 论文里最后提出分布式算法称之为 Basic Paxos，这是 Paxos 最根底的算法思维。

Basic Paxos 算法的最终目标是通过谨严和牢靠的流程来使得集群基于某个提案（Proposal）达到最终的共识。

根底概念

• Value：提案值，是一个形象的概念，在工程实际中能够是任何操作，如『更新数据库某一行的某一列』、『抉择 xxx 服务器节点作为集群中的主节点』。
• Number：提案编号，全局惟一，枯燥递增。
• Proposal：集群须要达成共识的提案，提案 = 编号 + 值。

Proposal 中的 Value 就是在 Paxos 算法实现之后须要达成共识的值。

Paxos 算法中有三个外围角色：

• Proposer：生成提案编号 n 和值 v，而后向 Acceptors 播送该提案，接管 Acceptors 的回复，如果有超过半数的 Acceptors 批准该提案，则选定该提案，否则放弃此次提案并生成更新的提案从新发动流程，提案被选定之后则告诉所有 Learners 学习该最终选定的提案值（也能够由 Acceptor 来告诉，看具体实现）。Basic Paxos 中容许有多个 Proposers。
• Acceptor：接管 Proposer 的提案并参加提案决策过程，把各自的决定回复给 Proposer 进行统计。Acceptor 能够承受来自多个 proposers 的多个提案。
• Learner：不参加决策过程，只学习最终选定的提案值。

在具体的工程实际中，一个节点往往会充当多种角色，比方一个节点能够既是 Proposer 又是 Acceptor，甚至还是 Learner。

算法流程

相较于间接给出 Paxos 算法的流程，我想因循 Lamport 巨匠的经典 Paxos 论文《Paxos Made Simple》中的思路：通过循序渐进的形式推导出 Paxos 算法。

首先须要理解 Paxos 算法中的两个重要的束缚：

C1. 一个 Acceptor 必须承受它收到的第一个提案。

C2. 只有当 超过半数 的 Acceptors 承受某一个提案，能力最终选定该提案。

C2 其实有一个隐含的推论：一个 Acceptor 能够承受多个提案，这也是为什么咱们须要给每一个提案生成一个编号的起因，用来给提案排序。

咱们后面提到过 Paxos 的最终目标是通过谨严和牢靠的流程来使得集群基于某个提案（Proposal）达到最终的共识，也就是说基于某一个提案发动的一次 Paxos 流程，最终目标是心愿集群对该提案达成统一的意见，而为了实现并维持集群中的这种一致性，前提是 Paxos 算法必须具备幂等性：一旦提案（Proposal）中的值（Value）被选定（Chosen），那么只有还在此次 Paxos 流程中，就算一直依照 Paxos 的规定反复步骤，将来被 Chosen 的 Value 都会是同一个。如果不满足这种幂等性，将可能导致不统一的问题。

因而，咱们能够把 Paxos 的根本命题提炼进去：

P1. 在一次 Paxos 流程中，如果一个值（Value）为 v 的提案（Proposal）被选定（Chosen）了，那么后续任何被最终选定的带有更大编号（Number）的提案中的 Value 也必须是 v。

提案在被最终选定之前必须先被 Acceptor 承受，于是咱们能够再进一步总结一个具备更强束缚的命题：

P2. 在一次 Paxos 流程中，如果一个值（Value）为 v 的提案（Proposal）被选定（Chosen）了，那么后续任何被 Acceptor 承受的带有更大编号（Number）的提案中的 Value 也必须是 v。

这还不是具备最强束缚的命题，因为提案在被 Acceptor 承受之前必须先由 Proposer 提出，因而还能够持续强化命题：

P3. 在一次 Paxos 流程中，如果一个值（Value）为 v 的提案（Proposal）被选定（Chosen）了，那么后续任何 Proposer 提议的带有更大编号（Number）的提案中的 Value 也必须是 v。

从上述的三个命题，咱们能够很容易地看进去，P3 能够推导出 P2，进而推导出 P1，也就是说这是一个归约的过程，因而只有 P3 成立则 P1 成立，也就是 Paxos 算法的正确性失去保障。

那么要如何实现呢 P3 呢？只需满足如下束缚：

C3. 对于一个被 Proposer 提议的提案中任意的 v 和 n，存在一个数量超过半数 Acceptors 的汇合 S，满足以下两个条件中的任意一个：

• S 中的任何一个 Acceptor 都没有承受过编号小于 n 的提案。
• S 中所有的 Acceptors 承受过的最大编号的提案的 Value 为 v。

为了满足 C3 从而实现 P3，须要引入一条束缚：Proposer 每次生成本人的 n 之后，发动提案之前，必须要先去『学习』那个曾经被选定或者将要被选定的小于 n 的提案，如果有这个提案的话则把那个提案的 v 作为本人的此次提案的 Value，没有的话才能够本人指定一个 Value，这样的话 Proposer 侧就能够保障更高编号的提案的值只会是已选定的 v 了，然而 Acceptor 侧还无奈保障，因为 Acceptor 有可能还会承受其余的 Proposers 的提案值，于是咱们须要对 Acceptor 也加一条束缚，让它承诺在收到编号为 n 的 v 之后，不会再承受新的编号小于 n 的提案值。

所以咱们能够失去一个 Paxos 在 Proposer 侧的算法流程：

1. Proposer 生成一个新的提案编号 n 而后发送一个 prepare 申请给 超过半数 的 Acceptors 汇合，要求汇合中的每一个 Acceptor 做出如下响应：

   (a) 向 Proposer 承诺在收到该音讯之后就不再承受编号小于 n 的提案。

   (b) 如果 Acceptor 在收到该音讯之前曾经承受过其余提案，则把以后承受的编号最大的提案回复给 Proposer。

2. 如果 Proposer 收到了 超过半数 的 Acceptors 的回复，那么就能够生成 (n, v) 的提案，这里 v 是所有 Acceptors 回复中编号最大的那个提案里的值，如果所有 Acceptors 回复中都没有附带上提案的话，则能够由 Proposer 本人抉择一个 v。
3. Proposer 将下面生成的提案通过一个 accept 申请发送给一个 超过半数 的 Acceptors 汇合。（须要留神的是这个汇合不肯定和第二步中的那个汇合是同一个。）

Paxos 在 Proposer 侧的算法流程曾经确定了，接下来咱们须要从 Acceptor 的视角来实现剩下的算法推导。后面咱们提到过，Acceptor 是能够承受多个 Proposers 的多个提案的，然而在收到一个 Proposer 的 prepare 音讯后会承诺不再承受编号小于 n 的新提案，也就是说 Acceptor 也是能够疏忽掉其余 Proposers 音讯（包含 prepare 和 accept）而不会毁坏算法的 安全性，当然了，在工程实际中也能够间接回复一个谬误，让 Proposer 更早晓得提案被回绝而后生成提案从新开始流程。这里咱们应该重点思考的场景是一个 Acceptor 承受一个提案申请的时候，依据后面 Proposer 要求 Acceptor 的承诺，咱们能够给 Acceptor 设置一个这样的束缚：

C4. 如果一个 Proposer 收回了带 n 的 prepare 申请，只有 Acceptor 还没有回复过任何其余编号大于 n 的prepare 申请，则该 Acceptor 能够承受这个提案。

因为 Acceptor 须要对 Proposer 做出不承受编号小于 n 的提案的承诺，因而它须要做长久化记录，那么它就必须是有状态的，也因而每个 Acceptor 都须要利用可靠性存储（日志）来保留两个对象：

1. Acceptor 承受过的编号最大的提案；
2. Acceptor 回复过的最大的 prepare 申请提案编号。

以上这就是 Acceptor 侧的束缚。接下来咱们就能够失去 Paxos 的整个算法流程了。

Paxos 算法能够演绎为两大根本过程：

1. 抉择过程；
2. 学习过程。

抉择过程

抉择过程分为两个阶段：

• 阶段一（Phase 1）：

  (a) Proposer 生成一个全局惟一且枯燥递增的提案编号 n，而后发送编号为 n 的 prepare 申请（P1a msg）给 超过半数 的 Acceptors 汇合。

  (b) 当一个 Acceptor 收到一个编号为 n 的 prepare 申请，如果 n 比它此前承受过其余的提案编号（如果有）都要大的话，那么将这个提案编号 n 写入本地日志，这里记为 max_n，而后作出『两个承诺，一个回复』:

  • 两个承诺：

    • 不再承受编号小于等于 n 的 prepare 申请
    • 不再承受编号小于等于 n 的 accept 申请

  • 一个回复：

    • 在不违反以前作出的承诺下，回复音讯（P1b msg），附带上本人曾经承受过的提案中编号最大的那个提案的 v 和 n，没有则返回空值。

  否则就疏忽该 prepare 音讯或者回复一个谬误。

• 阶段二（Phase 2）：

  (a) 当 Proposer 收到 超过半数 的 Acceptors 回复它的编号为 n 的 prepare 申请的响应，此时有两种可能：

  • Free：没有任何一个 Acceptor 的回复音讯中附带已被承受的提案，意味着以后流程中还没有提案值被最终承受，此时 Proposer 能够自在地抉择提案值 Value，最初发送一个蕴含 (n, v) 提案的 accept 申请音讯（P2a msg）给 Acceptors 汇合。
  • Forced：某些 Acceptors 的回复音讯中附带已被承受的提案，那么 Proposer 必须强制应用这些回复音讯中编号最大的提案 Value 作为本人的提案值，最初发送一个蕴含 (n, v) 提案的 accept 申请音讯（P2a msg）给 Acceptors 汇合。

  (b) 当 Acceptor 收到一个编号为 n 的提案的 accept 申请音讯，须要分两种状况解决：

  • 如果 n >= max_n（通常状况下这两个值是相等的），则承受该提案并回复音讯（P2b msg）。
  • 如果 n < max_n，则疏忽该 accept 音讯或者回复一个谬误（P2b error）。

学习过程

抉择过程完结之后，咱们失去了一个提案值，接下来就是要让集群中的所有 Learner『学习』到这个值了，以求达到集群的共识。

Learner 学习提案值的形式能够分成三种：

1. 任意一个 Acceptor 承受了一个提案后就立即将该提案发送给 所有 Learner。长处：Learner 能实时学习到被 Paxos 流程选定的 Value；毛病：网络通信次数太多，如果有 N 个 Acceptors 和 M 个 Learner，则须要的网络通信是 N*M 次。
2. 设置一个主 Learner，Acceptor 承受了一个提案后只将该提案发送给主 Learner，主 Learner 再转发给剩下的 Learners。长处：网络通信次数只需 N+M-1 次；毛病：主 Learner 有单点故障的危险。
3. Acceptor 承受了一个提案后将该提案发送给一个 Learner 汇合，由这个汇合去告诉剩下的 Learners。长处：用汇合代替单点，可靠性更高；毛病：减少零碎复杂度，须要保护一个 Learner 小集群。

至此，咱们就推导出了整个 Paxos 算法的流程：

算法证实

这一节咱们来证实 Paxos 算法的正确性。

上一节咱们曾经提炼进去了 Paxos 的根本命题 P1，并通过归约 P1 失去了约束性更强的另外两个命题 P2 和 P3，依据归约的原理，咱们晓得 P3 能够最终推导出 P1，也就是说如果要证实 Paxos 的根本命题 P1，只须要证实 P3 即可。为什么之前咱们要一直强化 Paxos 的命题呢？因为从数学的层面来讲，一个具备更强束缚（更多假如）的命题个别会更容易证实。

当初咱们把 P1, P2 和 P3 用更严格的数学语言来形容：

P1. 在一次 Paxos 流程中，如果一个蕴含 (n, v) 的提案被选定（Chosen），那么存在将来被选定的提案 (k, v1)，必然满足 k > n，v1 = v。

P2. 在一次 Paxos 流程中，如果一个蕴含 (n, v) 的提案被选定（Chosen），那么存在将来被超过半数的 Acceptors 承受的提案 (k, v1)，必然满足 k > n，v1 = v。

P3. 在一次 Paxos 流程中，如果一个蕴含 (n, v) 的提案被选定（Chosen），那么存在将来由 Proposer 提议的提案 (k, v1)，必然满足 k > n，v1 = v。

当初咱们利用数学归纳法来证实 P3：

假如 k = m 时 P3 成立，因为 (n, v) 曾经是被选定的提案，因而 Proposer 发动的从 n 到 k 的提案中的 Value 都会是 v，其中 m >= n，那么依据归约的原理可证 k = m 时 P1 也成立。

当初令 k = m+1，Proposer 发送带编号 k 的 prepare 申请音讯到 Acceptors 汇合。

因为此前曾经有了选定的提案，那么依据 Paxos 的束缚 C2 可知参加这一个提案投票的 Acceptors 汇合必然和上一个汇合有重合。

依据 Acceptors 汇合重叠和 Paxos 的 P1b 阶段可知，回复的音讯中必然附带有已被大多数 Acceptors 承受的提案 (i, v0)。

而后依据 P2a 阶段，Proposer 提案 (k, v1)，其中 v1 = v0。

还是依据 P1b，可知 i 是所有回复音讯里编号最大的，可得 i >= m，又依据 P1a 可知 i < k，因而能够得出提案 (i, v0) 中有 v0 = v。

可知当 k = m+1 时，提案 (k, v1) 中的 v1 = v。

依据数学归纳法的原理，咱们还须要找到一个特例来使得命题成立，而后由特例推广到广泛，咱们这里抉择 k = 1 作为特例，证实 k = 1 时 P3 成立：依据 Paxos 的束缚 C1 易知在 n = 0，k = 1 的场景下，P3 成立。

因而可依据数学归纳法基于 k = 1 进行推广至 k = m（m 代表任意自然数），最初 P3 命题得证。

再由归约的原理可知，P3 可推导出 P2，最初 P2 推导出 P1。至此，Paxos 算法原理正确性的证实实现。

上述的证实只是一种比较简单且浅显的证实办法，然而对于工程师了解 Paxos 原理来说曾经足够了，如果心愿进一步学习 Paxos 原理的严格数学证实，能够参阅 Leslie Lamport 的原始论文《The PartTime Parliament》，外面给出了 Paxos 算法的严格数学证实。

Multi-Paxos

自 Lamport 于 1990 年在论文《The PartTime Parliament》中提出 Paxos 算法之后，这个算法始终被评估为难以了解和实现，这篇论文中使用了大量的数学对 Paxos 的原理进行证实，而又因为 Lamport 在论文里用讲故事的模式解释 Paxos，进一步增大了人们彻底了解 Paxos 的难度，事实上 Lamport 的这篇论文也因而在发表过程中一波三折，这里不开展，有趣味的读者能够自行去理解这段这段背景故事。

因为业界在了解 Paxos 算法上继续的口碑载道，Lamport 在 2001 年发表了论文《Paxos Made Simple》，对原论文进行精简，以更通俗易懂的语言和模式论述 Paxos 算法，并在其中提出了更加具备工程实践性的 Multi-Paxos 的思维。

对于 Paxos 难以了解的问题上，我集体的一点愚见是：Paxos 算法的思维其实并不难理解，真正难的中央是：

1. Paxos 背地那一套残缺的数学原理和证实
2. 在简单分布式环境将 Paxos 进行工程落地

我集体倡议的 Paxos 学习材料是：《Paxos Made Simple》，《Paxos Made Live – An Engineering Perspective》以及 Paxos lecture (Raft user study)。第一篇论文能够说是 Lamport 1990 年那篇最后的论文的精简版，可读性进步了很多，论文里也没有应用任何数学公式，只需一点英文根底就能够通读，第二篇论文讲的则是 Google 外部基于 Multi-Paxos 实现的分布式锁机制和小文件存储系统，这是业界较早的实现了 Multi-Paxos 的大规模线上零碎，非常具备参考性，最初的 Youtube 视频则是 Raft 的作者 Diego Ongaro 为了比照 Raft 和 Multi-Paxos 的学习的难易水平而做的，非常适合作为学习 Paxos 和 Raft 的入门材料。

从上一节可知 Basic Paxos 算法有几个人造缺点：

• 只能就单个值（Value）达成共识，不反对多值共识。在理论的工程实际中往往是须要对一系列的操作达成共识，比方分布式事务，由很多执行命令组成。
• 至多须要 2 轮往返 4 次 prepare 和 accept 网络通信能力基于一项提案达成共识。对于一个分布式系统来说，网络通信是最影响性能的因素之一，过多的网络通信往往会导致系统的性能瓶颈。
• 不限度 Proposer 数量导致非常容易产生提案抵触。极其状况下，多 Proposer 会导致系统呈现『活锁』，毁坏分布式共识算法的两大束缚之一的活性（liveness）。

对于第三点，前文提到分布式共识算法必须满足两个最外围的束缚：安全性（safety）和活性（liveness），从上一节咱们能够看出 Basic Paxos 次要着重于 safety，而对 liveness 并没有进行强束缚，让咱们构想一种场景：两个 Proposers (记为 P1 和 P2) 轮替着发动提案，导致两个 Paxos 流程重叠了：

1. 首先，P1 发送编号 N1 的 prepare 申请到 Acceptors 汇合，收到了过半的回复，实现阶段一。
2. 紧接着 P2 也进入阶段一，发送编号 N2 的 prepare 申请到过半的 Acceptors 汇合，也收到了过半的回复，Acceptors 汇合承诺不再承受编号小于 N2 的提案。
3. 而后 P1 进入阶段二，发送编号 N1 的 accept 申请被 Acceptors 疏忽，于是 P1 从新进入阶段一发送编号 N3 的 prepare 申请到 Acceptors 汇合，Acceptors 又承诺不再承受编号小于 N3 的提案。
4. 紧接着 P2 进入阶段二，发送编号 N2 的 accept 申请，又被 Acceptors 疏忽。
5. 一直反复下面的过程 ……

在极其状况下，这个过程会永远继续，导致所谓的『活锁』，永远无奈选定一个提案，也就是 liveness 束缚无奈满足。

为了解决这些问题，Lamport 在《Paxos Made Simple》论文中提出了一种基于 Basic Paxos 的 Multi-Paxos 算法思维，并基于该算法引出了一个分布式银行零碎状态机的实现计划，感兴趣的读者无妨看一下。

Multi-Paxos 算法在 Basic Paxos 的根底上做了两点改良：

1. 多 Paxos 实例：针对每一个须要达成共识的单值都运行一次 Basic Paxos 算法的实例，并应用 Instance ID 做标识，最初汇总实现多值共识。
2. 选举繁多的 Leader Proposer：选举出一个 Leader Proposer，所有提案只能由 Leader Proposer 来发动并决策，Leader Proposer 作为 Paxos 算法流程中惟一的提案发起者，『活锁』将不复存在。此外，因为繁多 Proposer 不存在提案竞争的问题，Paxos 算法流程中的阶段一中的 prepare 步骤也能够省略掉，从而将两阶段流程变成一阶段，大大减少网络通信次数。

对于多值共识的优化，如果每一个 Basic Paxos 算法实例都设置一个 Leader Proposer 来工作，还是会产生大量的网络通信开销，因而，多个 Paxos 实例能够共享同一个 Leader Proposer，这要求该 Leader Proposer 必须是稳固的，也即 Leader 不应该在 Paxos 流程中解体或扭转。

因为 Lamport 在论文中提出的 Multi-Paxos 只是一种思维而非一个具体算法，因而对于 Multi-Paxos 的很多细节他并没有给出具体的实现计划，有些即使给出了计划也形容得不是很分明，比方他在论文中最初一节提出的基于银行零碎的状态机中的多 Paxos 实例解决，尽管给了具体的阐述，然而在很多要害中央还是没有指明，这也导致了后续业界里的 Multi-Paxos 实现各不相同。

咱们这里用 Google Chubby 的 Multi-Paxos 实现来剖析这个算法。

首先，Chubby 通过引入 Master 节点，实现了 Lamport 在论文中提到的 single distinguished proposer，也就是 Leader Proposer，Leader Proposer 作为 Paxos 算法流程中惟一的提案发起者，躲避了多 Proposers 同时发动提案的场景，也就不存在提案抵触的状况了，从而解决了『活锁』的问题，保障了算法的活性（liveness）。

Lamport 在论文中指出，抉择 Leader Proposer 的过程必须是牢靠的，那么具体如何抉择一个 Leader Proposer 呢？在 Chubby 中，集群利用 Basic Paxos 算法的共识性能来实现对 Leader Proposer 的选举，这个实现是具备人造合理性的，因为 Basic Paxos 自身就是一个十分牢靠而且通过严格数学证实的共识算法，用来作为选举算法再适合不过了，在 Multi-Paxos 流程期间，Master 会通过一直续租的形式来缩短租期（Lease）。比方在理论场景中，个别在长达几天的期间内都是同一个服务器节点作为 Master。万一 Master 故障了，那么剩下的 Slaves 节点会从新发动 Paxos 流程票选出新的 Master，也就是说主节点是始终存在的，而且是惟一的。

此外，Lamport 在论文中提到的过一种优化网络通信的办法：“当 Leader Proposer 处于稳固状态时，能够跳过阶段一，间接进入阶段二”，在 Chubby 中也实现了这个优化机制，Leader Proposer 在为多个 Paxos 算法实例服务的时候间接跳过阶段一进入阶段二，只发送 accept 申请音讯给 Acceptors 汇合，将算法从两阶段优化成了一阶段，大大节俭网络带宽和晋升零碎性能。

最初，Multi-Paxos 是一个 ” 脑裂 ” 容错的算法思维，就是说当 Multi-Paxos 流程中因为网络问题而呈现多 Leaders 的状况下，该算法的安全性（safety）束缚仍然能失去保障，因为在这种状况下，Multi-Paxos 实际上是进化成了 Basic Paxos，而 Basic Paxos 人造就反对多 Proposers。

在分布式事务中，Paxos 算法可能提供比两阶段提交协定更加牢靠的一致性提交：通过将提交 / 放弃事务的决定从原来两阶段协定中繁多的协调者转移到一个由 Proposer + Acceptors 组成的集群中。Lamport 已经发表过一篇《Consensus on Transaction Commit》的论文，通过将两阶段提交协定和基于 Paxos 实现的分布式提交协定做比照，对基于 Paxos 实现的提交协定有十分精彩的阐述，感兴趣的读者无妨一读。

Raft

Raft 算法实际上是 Multi-Paxos 的一个变种，通过新增两个束缚：

1. 追加日志束缚：Raft 中追加节点的日志必须是串行间断的，而 Multi-Paxos 中则能够并发追加日志（实际上 Multi-Paxos 的并发也只是针对日志追加，最初利用到外部 State Machine 的时候还是必须保障程序）。
2. 选主限度：Raft 中只有那些领有最新、最全日志的节点能力入选 Leader 节点，而 Multi-Paxos 因为容许并发写日志，因而无奈确定一个领有最新、最全日志的节点，因而能够抉择任意一个节点作为 Leader，然而选主之后必须要把 Leader 节点的日志补全。

基于这两个限度，Raft 算法的实现比 Multi-Paxos 更加简略易懂，不过因为 Multi-Paxos 的并发度更高，因而从实践上来说 Multi-Paxos 的性能会更好一些，然而到当初为止业界也没有一份权威的测试报告来撑持这一观点。

比照一下 Multi-Paxos 和 Raft 下集群中可能存在的日志程序：

能够看出，Raft 中永远满足这样一个束缚：follower log 肯定会是 leader log 的子集并且程序肯定是间断的，而 Multi-Paxos 则不肯定满足这个束缚，日志记录通常是乱序的。

因为 Raft 的核心思想源自 Multi-Paxos，在实现过程中做了很多改良优化，然而万变不离其宗，我置信了解了 Multi-Paxos 之后再去学习 Raft 会事倍功半（Raft 在诞生之初也是打着 ” 容易了解 ” 的旗号来对标 Paxos 的），因为后面曾经深度分析过 Paxos 算法的流程和原理了，碍于本文的篇幅所限，这里就不再对 Raft 算法的细节进行深入探讨了，如果无意深刻学习 Raft，能够从 The Raft Consensus Algorithm 处找到相干的论文、源码等材料进行全面的学习。

最初有一些概念要廓清一下，Basic Paxos 是一个通过了严格数学证实的分布式共识算法，然而因为前文提到的 Basic Paxos 算法利用在理论工程落地中的种种问题，事实中简直没有间接基于 Basic Paxos 算法实现的分布式系统，绝大多数都是基于 Multi-Paxos，然而 Multi-Basic 仅仅是一种对 Basic Paxos 的延长思维而非一个具体算法，问题在于目前业界并没有一个对立的 Multi-Paxos 实现规范，因而 Multi-Paxos 的工程实现是建设在一个未经严格证实的前提之上的，工程实现最终的正确性只能靠实现方本人去验证，而 Raft 则是一个具备统一标准实现的、正确性曾经过严格证实的 具体算法，因而在分布式系统的工程实际中大多数人往往还是会抉择 Raft 作为底层的共识算法。

算法类型

须要特地指出的一点是，依据解决的场景是否容许拜占庭（Byzantine）谬误，共识算法能够分为 Crash Fault Tolerance (CFT) 和 Byzantine Fault Tolerance（BFT）两类。

对于非拜占庭谬误的状况，曾经存在不少经典的算法，包含 Paxos（1990 年）、Raft（2014 年）及其变种等。这类容错算法往往性能比拟好，解决较快，容忍不超过一半的故障节点。

对于要能容忍拜占庭谬误的状况，包含 PBFT（Practical Byzantine Fault Tolerance，1999 年）为代表的确定性系列算法、PoW（1997 年）为代表的概率算法等。确定性算法一旦达成共识就不可逆转，即共识是最终后果；而概率类算法的共识后果则是长期的，随着时间推移或某种强化，共识后果被颠覆的概率越来越小，最终成为事实上后果。拜占庭类容错算法往往性能较差，容忍不超过 1/3 的故障节点。

本文次要探讨的分布式共识算法是 CFT 类算法，毕竟对于大多数分布式系统来说，集群节点和网络音讯个别都是可控的，零碎只会呈现节点故障而不会呈现像拜占庭谬误那样伪造的、欺骗性的网络音讯，在这种场景下，CFT 类算法更具备现实意义；BFT/PBFT 类算法更多是用在零碎被歹意入侵，成心伪造网络音讯的场景里。

并发管制

在分布式事务中，集群中的每个服务器节点要治理很多资源对象，每个节点必须保障在并发事务拜访这些资源对象时，它们可能始终保持一致性。因而，每个服务器节点须要对本人的治理的资源对象利用肯定的并发管制机制。分布式事务中须要所有服务器节点独特保障事务以串行等价的的形式执行。

也就是说，如果事务 T 对某一个服务器节点上的资源对象 S 的并发拜访在事务 U 之前，那么咱们须要保障在所有服务器节点上对 S 和其余资源对象的抵触拜访，T 始终在 U 之前。

锁并发管制

在分布式事务中，某个对象的锁总是本地持有的（在同一个服务器节点上）。是否加锁是由本地锁管理器（Local Lock Manager，LLM）决定的。LLM 决定是满足客户端持锁的申请，还是阻塞客户端发动的分布式事务。然而，事务在所有服务器节点上被提交或者放弃之前，LLM 不能开释任何锁。在应用加锁机制的并发管制中，原子提交协定在进行的过程中资源对象始终被锁住，并且是排他锁，其余事务无奈染指这些资源对象。但如果事务在两阶段提交协定的阶段一就被放弃，则互斥锁能够提前开释。

因为不同服务器节点上的 LLM 独立设置资源对象锁，因而，对于不同的事务，它们加锁的程序也可能呈现不统一。思考一个场景：事务 T 和 U 在服务器 X 和 Y 之间的交织执行：

1. 事务 T 锁住了服务器节点 X 上的资源对象 A，做写入操作；
2. 事务 U 锁住了服务器节点 Y 上的资源对象 B，做写入操作；
3. 事务 T 试图读取服务器节点 Y 上的资源对象 B，此时 B 被事务 U 锁住，因而 T 期待锁开释；
4. 事务 U 试图读取服务器节点 X 上的资源对象 A，此时 A 被事务 T 锁住，因而 U 期待锁开释。

在服务器节点 X 上，事务 T 在事务 U 之前；而在服务器节点 Y 上，事务 U 在事务 T 之前。这种不统一的事务秩序导致了事务之间的循环依赖，从而引起分布式死锁。分布式死锁须要通过特定的办法 / 算法来检测并解除，一旦检测到死锁，则必须放弃其中的某个事务来解除死锁，而后告诉事务协调者，它将会放弃该事务所波及的所有参与者上的事务。

工夫戳并发管制

对于繁多服务器节点的事务来说，协调者在每个事务启动时会为其调配一个全局惟一的工夫戳。通过依照拜访资源对象的事务工夫戳程序提交资源对象的版本来强制保障以事务执行的串行等价性。在分布式事务中，协调者必须保障每个事务都会附带全局惟一的工夫戳。全局惟一的工夫戳由事务拜访的第一个协调者发给客户端。如果任意一个服务器节点上的资源对象执行了事务中的一个操作，那么事务工夫戳会被发送给该服务器节点上的协调者。

分布式事务中的所有服务器节点独特保障事务以串行等价的形式执行。例如，如果在某服务器节点上，由事务 U 拜访的资源对象版本在事务 T 拜访之后提交；而在另一个服务器节点上，事务 T 和事务 U 又拜访了同一个资源对象，那么它们也必须依照雷同的秩序提交资源对象。为了保障所有服务器节点上的事务执行的雷同程序，协调者必须就工夫戳排序达成统一。工夫戳是一个二元组 < 本地工夫戳，服务器 ID > 对。在工夫戳的比拟排序过程中，首先比拟本地工夫戳，而后再比拟服务器 ID。

一个牢靠的工夫戳并发管制应该保障即便各个服务器节点之间的本地工夫不同步，也能保障事务之间的雷同程序。然而思考到效率，各个协调者之间的工夫戳还是最好还是要求大抵同步。这样的话，事务之间的程序通常与它们理论开始的工夫程序相一致。能够利用一些本地物理时钟同步办法来保障工夫戳的大抵同步。

如果决定利用工夫戳机制进行分布式事务的并发管制，那么还须要通过某些办法来解决事务抵触问题。如果为了解决抵触须要放弃某个事务时，相应的协调者会收到告诉，并且它将在所有的参与者上放弃该事务。这样，如果事务可能保持到客户端发动提交申请命令的那个时候，那么这个事务就总能被提交。因而在两阶段提交协定中，失常状况下参与者都会批准提交，惟一一种不批准提交的状况是参与者在事务执行过程中已经解体过。

乐观并发管制

加锁机制这一类乐观并发管制有许多显著的缺点：

• 锁的保护带来了很多新的开销。这些开销在不反对对共享数据并发拜访的零碎中是不存在的。即便是只读事务（如查问），就算这一类事务不会扭转数据的完整性，却依然须要利用锁来保证数据在读取过程中不会被其余事务批改，然而锁却只在最极其的状况下才会发挥作用。
• 锁机制非常容易引发死锁。预防死锁会重大升高并发度，因而必须利用超时或者死锁检测来解除死锁，但这些死锁解除计划对于交互式的程序来说并不是很现实。
• 锁周期过长。为了防止事务的连锁（雪崩）放弃，锁必须保留到事务完结之时能力开释，这再一次重大升高了零碎的并发度。

因为锁这一类的乐观并发管制有上述的种种弊病，因而研究者们提出了另一种乐观并发管制的机制，以求躲避锁机制的人造缺点，研究者们发现这样的一个景象：在大多数利用中两个客户端事务拜访同一个资源对象的可能性其实很低，事务总是可能胜利执行，就如同事务之间不存在抵触一样。

所以事务的乐观并发管制的基本思路就是：各个并发事务只有在执行实现之后并且收回 closeTransaction 申请时，再去检测是否有抵触，如果的确存在抵触，那么就放弃一些事务，而后让客户端重新启动这些事务进行重试。

在乐观并发管制中，每个事务在提交之前都必须进行验证。事务在验证开始时首先要附加一个事务号，事务的串行化就是依据这些事务号的程序实现的。分布式事务的验证由一组独立的服务器节点共同完成，每个服务器节点验证拜访本人资源对象的事务。这些验证在两阶段提交协定的第一个阶段进行。

对于分布式事务的并发管制就临时介绍到这里，如果想要持续深刻学习更多并发管制的细节，能够深刻浏览《分布式系统：概念与设计》、《数据库系统实现》和《数据库系统概念》等书籍或者其余材料。

总结

本文通过解说 BASE 准则 、 两阶段原子提交协定 、 三阶段原子提交协定 、Paxos/Multi-Paxos 分布式共识算法的原理与证实、Raft 分布式共识算法 和分布式事务的并发管制 等内容，为读者全面而又深刻地解说剖析了分布式事务的底层外围原理，特地是通过对原子提交协定中的 2PC/3PC 的论述和剖析，以及对分布式共识算法 Paxos 的原理分析和正确性的证实，最初还有对分布式事务中几种并发管制的介绍，置信可能让读者对分布式事务底层的一致性和并发管制原理有一个粗浅的认知，对当前学习和了解分布式系统大有裨益。

本文不仅仅是简略地介绍分布式事务的底层原理，更是在介绍原理的同时，通过层层递进的形式疏导读者去真正地了解分布式系统的底层原理和设计思路，而非让读者死记硬背一些概念，所以心愿通过这篇抛砖引玉的文章，可能对本文读者在当前学习、操作甚至是设计分布式系统以及分布式事务时的思路有所开辟。

参考 & 延长

• ACID
• Eventual consistency
• Atomic commit
• A Two-Phase Commit Protocol and its Performance
• The PartTime Parliament
• Paxos Made Simple
• Fast Paxos
• The Performance of Paxos and Fast Paxos
• Paxos Made Live – An Engineering Perspective
• Paxos (computer science))
• The Chubby lock service for loosely-coupled distributed systems
• Consensus on Transaction Commit
• Life beyond Distributed Transactions: an Apostate’s Opinion
• In Search of an Understandable Consensus Algorithm
• Paxos lecture (Raft user study)
• Distributed Systems: Concepts and Design
• How to Build a Highly Available System Using Consensus
• 数学归纳法
• 共识算法
• Distributed Transaction Processing: The XA Specification