本文首发自「慕课网」，想理解更多IT干货内容，程序员圈内热闻，欢送关注"慕课网"！

作者：大熊老师 | 慕课网讲师

在常见的分布式系统中，总会产生诸如机器宕机或网络异样（包含音讯的提早、失落、反复、乱序，还有网络分区）等状况。
一致性算法须要解决的问题就是如何在一个可能产生上述异样的分布式系统中，疾速且正确地在集群外部对某个数据的值达成统一，并且保障不管产生以上任何异样，都不会毁坏整个零碎的一致性。

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 执行回滚

二阶段提交毛病
二阶段提交看起来的确可能提供原子性的操作，然而可怜的事，二阶段提交还是有几个毛病的：

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

单点问题： 协调者是个单点，一旦呈现问题，其余参与者将无奈开释事务资源，也无奈实现事务操作；

数据不统一：当执行事务提交过程中，如果协调者向所有参与者发送Commit申请后，产生部分网络异样或者协调者在尚未发送完Commit申请，即呈现解体，最终导致只有局部参与者收到、执行申请。于是整个零碎将会呈现数据不统一的情景；

激进：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 的，因而如果按上图所示运行，则后一个提案总会让后面提案选中失败，显然死循环。

欢送关注「慕课网」帐号，咱们会始终保持内容原创，提供IT圈优质内容，分享干货常识，大家一起独特成长吧！

本文原创公布于慕课网 ，转载请注明出处，谢谢合作