概述

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。

一致性算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

CAP定理

CAP 理论告诉我们，一个分布式系统不可能同时满足一致性（C:Consistency)，可用性（A: Availability）和分区容错性（P：Partition tolerance）这三个基本需求，最多只能同时满足其中的2个。

Base理论

BASE：全称：Basically Available(基本可用)，Soft state（软状态）,和 Eventually consistent（最终一致性）。

Base 理论是对 CAP 中一致性和可用性权衡的结果，其来源于对大型互联网分布式实践的总结，是基于 CAP 定理逐步演化而来的。其核心思想是：既是无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。

解释一下：什么是软状态呢？相对于原子性而言，要求多个节点的数据副本都是一致的，这是一种 “硬状态”。软状态指的是：允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时。

二阶段提交 2PC

二阶段提交协议（Two-phase Commit，即 2PC）是常用的分布式事务解决方案，即将事务的提交过程分为两个阶段来进行处理。在阶段二中，会根据阶段一的投票结果执行 2 种操作：执行事务提交，中断事务。

角色

• ① 协调者：事务的发起者
• ② 参与者：事务的执行者

阶段一

• 事务询问：协调者向所有的参与者询问，是否准备好了执行事务，并开始等待各参与者的响应。
• 执行事务：各参与者节点执行事务操作，并将 Undo 和 Redo 信息记入事务日志中。
• 各参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作，那么就反馈给协调者 Yes 响应，表示事务可以执行；如果参与者没有成功执行事务，就返回 No 给协调者，表示事务不可以执行。

阶段二

在阶段二中，会根据阶段一的投票结果执行 2 种操作：执行事务提交，中断事务。

执行事务提交步骤

• 发送提交请求：协调者向所有参与者发出 commit 请求。
• 事务提交：参与者收到 commit 请求后，会正式执行事务提交操作，并在完成提交之后释放整个事务执行期间占用的事务资源。
• 反馈事务提交结果：参与者在完成事务提交之后，向协调者发送 Ack 信息。
• 协调者接收到所有参与者反馈的 Ack 信息后，完成事务。

执行中断事务步骤

• 发送回滚请求：协调者向所有参与者发出 Rollback 请求。
• 事务回滚：参与者接收到 Rollback 请求后，会利用其在阶段一种记录的 Undo 信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。
• 反馈事务回滚结果：参与者在完成事务回滚之后，想协调者发送 Ack 信息。
• 中断事务：协调者接收到所有参与者反馈的 Ack 信息后，完成事务中断。

CASE1 执行提交

CASE2 执行回滚

二阶段提交缺点

二阶段提交看起来确实能够提供原子性的操作，但是不幸的事，二阶段提交还是有几个缺点的：

1. 阻塞问题： 2PC的提交在执行过程中，所有参与事务操作的逻辑都处于阻塞状态，也就是说，各个参与者都在等待其他参与者响应，无法进行其他操作；

2. 单点问题： 协调者是个单点，一旦出现问题，其他参与者将无法释放事务资源，也无法完成事务操作；

3. 数据不一致。当执行事务提交过程中，如果协调者向所有参与者发送Commit请求后，发生局部网络异常或者协调者在尚未发送完Commit请求，即出现崩溃，最终导致只有部分参与者收到、执行请求。于是整个系统将会出现数据不一致的情形；

4. 保守。2PC没有完善的容错机制，当参与者出现故障时，协调者无法快速得知这一失败，只能严格依赖超时设置来决定是否进一步的执行提交还是中断事务。

由于二阶段提交存在着诸如同步阻塞、单点问题、脑裂等缺陷，所以，研究者们在二阶段提交的基础上做了改进，提出了三阶段提交。

三阶段提交3PC

三阶段提交（Three-phase commit），也叫三阶段提交协议（Three-phase commit protocol），是二阶段提交（2PC）的改进版本。

与两阶段提交不同的是，三阶段提交有两个改动点。

• 引入超时机制。同时在协调者和参与者中都引入超时机制。
• 在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。

也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。

CanCommit阶段

3PC的CanCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

1. 事务询问 协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
2. 响应反馈 参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No

PreCommit阶段

协调者根据canCommit阶段参与者的反应情况来决定是否可以继续事务的PreCommit操作。根据响应情况，有以下两种可能。

假如协调者在CanCommit阶段从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。

1. 发送预提交请求 :协调者向参与者发送PreCommit请求，并进入Prepared阶段。
2. 事务预提交 :参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
3. 响应反馈 :如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。

假如canCommit阶段有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。

1. 发送中断请求: 协调者向所有参与者发送abort请求。
2. 中断事务: 参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

doCommit阶段

该阶段进行真正的事务提交，也可以分为以下两种情况。

执行提交

1. 发送提交请求: 协调接在preCommit阶段收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
2. 事务提交: 参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
3. 响应反馈: 事务提交完之后，向协调者发送Ack响应。
4. 完成事务: 协调者接收到所有参与者的ack响应之后，完成事务。

中断事务协调者在preCommit阶段没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。

1. 发送中断请求: 协调者向所有参与者发送abort请求
2. 事务回滚: 参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
3. 反馈结果: 参与者完成事务回滚之后，向协调者发送ACK消息4.中断事务 协调者接收到参与者反馈的ACK消息之后，执行事务的中断。

在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者abort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。）

三阶段提交优缺点：

3PC有效降低了2PC带来的参与者阻塞范围，并且能够在出现单点故障后继续达成一致；
但3PC带来了新的问题，在参与者收到preCommit消息后，如果网络出现分区，协调者和参与者无法进行后续的通信，这种情况下，参与者在等待超时后，依旧会执行事务提交，这样会导致数据的不一致。

Paxos算法

像 2PC 和 3PC 都需要引入一个协调者的角色，当协调者 down 掉之后，整个事务都无法提交，参与者的资源都出于锁定的状态，对于系统的影响是灾难性的，而且出现网络分区的情况，很有可能会出现数据不一致的情况。有没有不需要协调者角色，每个参与者来协调事务呢，在网络分区的情况下，又能最大程度保证一致性的解决方案呢。此时 Paxos 出现了。

Paxos 算法是 Lamport 于 1990 年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，Lamport在八年后重新发表，即便如此Paxos算法还是没有得到重视。2006 年 Google 的三篇论文石破天惊，其中的 chubby 锁服务使用Paxos 作为 chubbycell 中的一致性，后来才得到关注。

Paxos 协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数节点离线的情况下，剩余的多数节点仍然能够达成一致。即每个节点，既是参与者，也是决策者

Paxos角色

Paxos 协议的角色 主要有三类节点：

• 提议者（Proposer）：提议一个值；
• 接受者（Acceptor）：对每个提议进行投票；
• 告知者（Learner）：被告知投票的结果，不参与投票过程。

算法描述

- 第一阶段

   [a]: Proposer提出提案，編号Mn，并向过半数Acceptor发送編号Mn的Prepare请求。
   [b]: 如果Acceptor收到的Prepare请求的编号Mn > 其己答复的任何Prepare请求的编号，则Acceptor对该请求作出答复，并承诺不接受任何编号小于編号Mn的提案

- 第二阶段

   [a]: 如果Proposer从过半数Acceptor处收到对其Prepare请求（編号n）的响应，则向这些Acceptor发送一个Accept请求[Mn,Vn]，其中Vn是响应中编号最高的提案的值，或者如果响应报  告没有提案，则Vn是任何值。
   [b]:如果Acceptor收到Accept请求[Mn,Vn]，若该Acceptor尚未对编号大于Mn的Prepare请求作出过响应，则通提案。

正常情况的提案选择

情况1：S3先Accept S1的值，已返回Accept的ack，再见到S5的提案

关键点，S3 也接到了 S5 的prepare 提案，这时是否会有不一致的情况呢？

S3会把之前已接收的提案变号1和值x答复给S5，S5会替换Y为X然后应用编号2，x进行广播。

情况2：s3先Accept S1的值，再见到S5的提案，再返回Accept的ack

**关键点：**S3 也接到了 S5 prepare 提案，这时是否会有不一致的情况呢？

情况3：S3 还未经历 Accept 阶段时，就拿到了 S5 的 prepare 提案

关键点，S3 还未经历 Accept 阶段时，就拿到了 S5 的 prepare 提案，这时是否会有不一致的情况呢？

这种情况下S1的提案会应用失败，需要重新发起新的一轮提案。

情况4：形成活锁

原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。

Paxos 是允许多个 Proposer 的，因此如果按上图所示运行，则后一个提案总会让前面提案选中失败，显然死循环。

未完待续…
主页：大能老师
实战课：2022全新版！Java分布式架构设计与开发实战