图解：一致性协议算法

• 背景
• CAP 定理
• Base 理论
• 2PC
• 3PC
• Paxos算法
• Raft一致性算法
• 一致性协议之 ZAB
• NWR模型

背景

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

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

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 阶段一

1.事务询问

协调者向所有的参与者询问，是否准备好了执行事务，并开始等待各参与者的响应。

1.执行事务

各参与者节点执行事务操作，并将 Undo 和 Redo 信息记入事务日志中

1.各参与者向协调者反馈事务询问的响应

如果参与者成功执行了事务操作，那么就反馈给协调者 Yes 响应，表示事务可以执行；如果参与者没有成功执行事务，就返回 No 给协调者，表示事务不可以执行。

2PC 阶段二

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

执行事务提交步骤如下：

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

中断事务步骤如下：

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

从上面的逻辑可以看出，二阶段提交就做了2个事情：投票，执行。

举个例子：

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

1、同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。

2、单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）

3、数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。

4、二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

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

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响应，但是他有理由相信：成功提交的几率很大。）

小结

没有任何事情是完美的。特别是在分布式的情况下。事实上，分布式在某个程度上其实是人类社会发展的一个极佳写真。因为人类社会中个体的可靠性显然比分布式系统节点的可靠性要低很多。

三阶段提交也不完美。但是它比两阶段好。

两阶段的问题可以这样分解：

•协调者出错，参与者也出错；•协调者出错，参与者不出错；•协调者不出错，参与者出错；•协调者不出错，参与者也不出错。

显然第4种不是问题。所以实际上只有3个问题。而问题2可以通过简单地NEW一个新的协调者来解决。问题3的错则显然正是两阶段提交协议的解决目标，所以也没有问题。有问题的只有协调者出错，参与者也出错的问题。

无论2pc还是3pc只有在以下的情况才会出现数据不一致性：协调者挂了，备份协调者恢复协议时，某个参与者挂了，在剩下参与者都是“YES”的状态下, 备份协调者没法分辨挂了的参与者状态。（此处挂了可理解为宕机或者时网络连不上）

接下来将对上面段落使用一些替代词：协调者A，备份协调者B，挂了参与者C

•在2pc中，B需要分辨两种情形：1是C提交了事务（phase 2），2是C在原始投票是abort（phase 1）。如果B决定abort，会违反情形1，如果决定commit，则违背C在表决时的意愿，这个时候需要blocking 。（上面的"YES", 在这里可认为剩下的参与者在原始投票都是yes。）•在3pc中，B需要分辨两种情形：1是C提交了事务（phase 3），2是B不知道C有没有收到prepare commit(phase 2)，在这种情况下，因为我们已经phase 1对大家的意愿进行了收集，得到的都是commit，所以此处会用比较激进做法，非blocking，所以才有上面的脑裂容错策略，这样也会降低阻塞范围。

Paxos算法

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

Paxos在原作者的《Paxos Made Simple》中内容是比较精简的：

第一阶段

（a） 提议者选择一个提议编号n，并向大多数接受者发送一个编号n的准备请求。

（b） 如果承兑人收到的准备请求的编号n大于其已答复的任何准备请求的编号，则承兑人对该请求作出答复，并承诺不接受任何编号小于n且其已接受的编号最高的提案（如有）。

第二阶段

（a） 如果提案人从大多数接受人处收到对其准备请求（编号n）的响应，则它向这些接受人中的每一个发送一个接受请求，请求编号n的提案，其值为v，其中v是响应中编号最高的提案的值，或者如果响应报告没有提案，则v是任何值。

（b） 如果承兑人收到编号为n的提案的接受请求，则除非承兑人已对编号大于n的准备请求作出响应，否则接受该提案。

翻译一下：

Paxos问题指分布式系统中存在故障fault，但不存在恶意corrupt节点场景（消息可能丢失但不会造假）下的共识达成（Consensus）问题。

Paxos是第一个被证明的共识算法，原理基于两阶段提交并进行扩展。算法中将节点分为三种类型：

•倡议者proposer：提交一个提案，等待大家批准为结案，往往是客户端担任。•接受者acceptor：负责对提案进行投票，往往服务器担任。提议超过半数的接受者投票及被选中。•学习者learner：被告知提案结果，并与之统一，不参与投票过程。客户端和服务端都可担任。

每个节点在协议中可以担任多个角色。

Paxos的特点：

•一个或多个节点可以提出提议。•系统针对所有提案中的某个提案必须达成一致。•最多只能对一个确定的提案达成一致。•只要超过半数的节点存活且可互相通信，整个系统一定能达成一致状态。

第一阶段A

Proposer选择一个提议编号n，向所有的Acceptor广播Prepare（n）请求。

第一阶段B

Acceptor接收到Prepare（n）请求，若提议编号n比之前接收的Prepare请求都要大，则承诺将不会接收提议编号比n小的提议，并且带上之前Accept的提议中编号小于n的最大的提议，否则不予理会。

第二阶段A

Proposer得到了多数Acceptor的承诺后，如果没有发现有一个Acceptor接受过一个值，那么向所有的Acceptor发起自己的值和提议编号n，否则，从所有接受过的值中选择对应的提议编号最大的，作为提议的值，提议编号仍然为n。

第二阶段B

Acceptor接收到提议后，如果该提议编号不违反自己做过的承诺，则接受该提议。

Paxos 例子说明

楼主这个例子来自中文维基百科，但楼主为了形象化，辅以图片解释，但愿不会让人更迷糊。

例子：

在 Paxos 岛上，有A1, A2, A3, A4, A5 5位议员，就税率问题进行决议。我们假设几个场景来解释：

场景 1：

假设 A1 说：税率应该是 10%。而此时只有他一个人提这个建议。如下图：

很完美，没有任何人和他竞争提案，他的这个提案毫无阻挠的通过了。A2 - A5 都会回应他：我们收到了你的提案，等待最终的批准。而 A1 在收到 2 份回复后，就可以发布最终的决议：税率定位 10%，不用再讨论了。

这里有个注意的地方就是：为什么收到了 2 份回复就可以确定提案了呢？答：因为包括他自己，就达到 3 个人了，少数服从多数。如果各位听说过鸽笼原理/抽屉原理，就明白个大概了。有人说，鸽笼原理/抽屉原理就是 Paxos 的核心思想。

场景 2：

现在我们假设在 A1 提出 10% 税率提案的同时, A5 决定将税率定为 20%，如果这个提案要通过侍从送到其他议员的案头，A1 的草案将由 4 位侍从送到 A2-A5 那里。但是侍从不靠谱（代表分布式环境不靠谱），负责 A2 和 A3 的侍从顺利送达，而负责 A4 和 A5 的侍从则开溜了！

而 A5 的草案则送到了 A4 和 A3 的手中。

现在，A1 ，A2，A3 收到了 A1 的提案，A3，A4， A5 收到 A5 的提案，按照 Paxos 的协议，A1，A2，A4，A5 4个侍从将接受他们的提案，侍从拿着回复：我已收到你的提案，等待最终批准 回到提案者那里。

而 A3 的行为将决定批准哪一个。

当 A3 同时收到了 A1 和 A5 的请求，该如何抉择呢？不同的抉择将会导致不同的结果。

有 3 种情况，我们分析一下：

场景2：情况一

假设 A1 的提案先送到 A3 那里，并且 A3 接受了该提案并回复了侍从。这样，A1 加上 A2 加上 A3，构成了多数派，成功确定了税率为 10%。而 A5 的侍从由于路上喝酒喝多了，晚到了一天，等他到了，税率已经确定了，A3 回复 A5：兄弟，你来的太晚了，税率已经定好了，不用折腾了，听 A1 的吧。

如下图：

场景2：情况二

依然假设 A1 的提案先送到 A3 处，但是这次 A5 的侍从不是放假了，只是中途耽搁了一会。这次, A3 依然会将"接受"回复给 A1 .但是在决议成型之前它又收到了 A5 的提案。这时协议根据 A5 的身份地位有两种处理方式，但结果相同。

•当 A5 地位很高，例如 CEO，就回复 A5：我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%,请明察。•当 A5 没地位，普通码农一个，直接不回复。等待 A1 广播：税率定为 10% 啦！！！

如下图：

场景2：情况三

在这个情况中，我们将看见，根据提案的时间及提案者的权势决定是否应答是有意义的。在这里，时间和提案者的权势就构成了给提案编号的依据。这样的编号符合"任何两个提案之间构成偏序"的要求。

A1 和 A5 同样提出上述提案，这时 A1 可以正常联系 A2 和 A3，A5 也可以正常联系这两个人。这次 A2 先收到 A1 的提案; A3 则先收到 A5 的提案。而 A5 更有地位。

在这种情况下，已经回答 A1 的 A2 发现有比 A1 更有权势的 A5 提出了税率 20% 的新提案，于是回复A5说：我已收到您的提案，等待最终批准。

而回复 A5 的 A3 发现新的提案者A1是个小人物，没地位不予应答。

此时，A5 得到了 A2，A3 的回复，于是 A5 说：税率定为 20%，别再讨论了。

那 A4 呢？A4 由于睡过头了，迷迷糊糊的说：现有的税率是什么? 如果没有决定，则建议将其定为 15%.

这个时候，其他的议员就告诉他：哥们，已经定为 20% 了，别折腾了。洗洗继续睡吧。

整个过程如下图：

Paxos的死锁情况

“活锁”的根本原因在于两个proposer交替提案，避免“活锁”的方式为，如果一个proposer通过accpter返回的消息知道此时有更高编号的提案被提出时，该proposer静默一段时间，而不是马上提出更高的方案，静默期长短为一个提案从提出到被接受的大概时间长度即可，静默期过后，proposer重新提案。系统中之所以要有主proposer的原因在于，如果每次数据更改都用paxos，那实在是太慢了，还是通过主节点下发请求这样来的快，因为省去了不必要的paxos时间。所以选择主proposer用paxos算法，因为选主的频率要比更改数据频率低太多。但是主proposer挂了咋整，整个集群就一直处于不可用状态，所以一般都用租约的方式，如果proposer挂了，则租约会过期，其它proposer就可以再重新选主，如果不挂，则主proposer自己续租。

小结：

Paxos协议最终解决什么问题？

当一个提议被多数派接受后，这个提议对应的值被Chosen（选定），一旦有一个值被Chosen，那么只要按照协议的规则继续交互，后续被Chosen的值都是同一个值，也就是这个Chosen值的一致性问题。

Paxos 的目标：保证最终有一个提案会被选定，当提案被选定后，其他议员最终也能获取到被选定的提案。

Paxos 协议用来解决的问题可以用一句话来简化：将所有节点都写入同一个值，且被写入后不再更改。

Raft一致性算法

Raft算法是Paxos算法的一种简化实现。

包括三种角色：leader，candidate和follower。

•follow:所有节点都以follower的状态开始，如果没有收到leader消息则会变成candidate状态。•candidate：会向其他节点拉选票，如果得到大部分的票则成为leader，这个过程是Leader选举。•leader：所有对系统的修改都会先经过leader。

其有两个基本过程：

•Leader选举：每个candidate随机经过一定时间都会提出选举方案，最近阶段中的票最多者被选为leader。•同步log：leader会找到系统中log（各种事件的发生记录）最新的记录，并强制所有的follow来刷新到这个记录。

Raft一致性算法是通过选出一个leader来简化日志副本的管理，例如日志项（log entry）只允许从leader流向follower。

下面是动画演示Raft，清晰理解Raft共识如何达成。

http://thesecretlivesofdata.com/raft/

1.针对简化版拜占庭将军问题，Raft 解决方案

假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？

Raft 的解决方案大概可以理解成 先在所有将军中选出一个大将军，所有的决定由大将军来做。选举环节：比如说现在一共有3个将军 A, B, C，每个将军都有一个随机时间的倒计时器，倒计时一结束，这个将军就会把自己当成大将军候选人，然后派信使去问其他几个将军，能不能选我为总将军？假设现在将军A倒计时结束了，他派信使传递选举投票的信息给将军B和C，如果将军B和C还没把自己当成候选人（倒计时还没有结束），并且没有把选举票投给其他，他们把票投给将军A，信使在回到将军A时，将军A知道自己收到了足够的票数，成为了大将军。在这之后，是否要进攻就由大将军决定，然后派信使去通知另外两个将军，如果在一段时间后还没有收到回复（可能信使被暗杀），那就再重派一个信使，直到收到回复。

2.选主 Leader Election

2.1 正常情况下选主

假设现在有如图5个节点，5个节点一开始的状态都是 Follower。

在一个节点倒计时结束 (Timeout) 后，这个节点的状态变成 Candidate 开始选举，它给其他几个节点发送选举请求 (RequestVote)

其他四个节点都返回成功，这个节点的状态由 Candidate 变成了 Leader，并在每个一小段时间后，就给所有的 Follower 发送一个 Heartbeat 以保持所有节点的状态，Follower 收到 Leader 的 Heartbeat 后重设 Timeout。

这是最简单的选主情况，只要有超过一半的节点投支持票了，Candidate 才会被选举为 Leader，5个节点的情况下，3个节点 (包括 Candidate 本身) 投了支持就行。

2.2 Leader 出故障情况下的选主

一开始已经有一个 Leader，所有节点正常运行。

Leader 出故障挂掉了，其他四个 Follower 将进行重新选主。

4个节点的选主过程和5个节点的类似，在选出一个新的 Leader 后，原来的 Leader 恢复了又重新加入了，这个时候怎么处理？在 Raft 里，第几轮选举是有记录的，重新加入的 Leader 是第一轮选举 (Term 1) 选出来的，而现在的 Leader 则是 Term 2，所有原来的 Leader 会自觉降级为 Follower

2.3 多个 Candidate 情况下的选主

假设一开始有4个节点，都还是 Follower。

有两个 Follower 同时 Timeout，都变成了 Candidate 开始选举，分别给一个 Follower 发送了投票请求。

两个 Follower 分别返回了ok，这时两个 Candidate 都只有2票，要3票才能被选成 Leader。

两个 Candidate 会分别给另外一个还没有给自己投票的 Follower 发送投票请求。

但是因为 Follower 在这一轮选举中，都已经投完票了，所以都拒绝了他们的请求。所以在 Term 2 没有 Leader 被选出来。

这时，两个节点的状态是 Candidate，两个是 Follower，但是他们的倒计时器仍然在运行，最先 Timeout 的那个节点会进行发起新一轮 Term 3 的投票。

两个 Follower 在 Term 3 还没投过票，所以返回 OK，这时 Candidate 一共有三票，被选为了 Leader。

如果 Leader Heartbeat 的时间晚于另外一个 Candidate timeout 的时间，另外一个 Candidate 仍然会发送选举请求。

两个 Follower 已经投完票了，拒绝了这个 Candidate 的投票请求。

Leader 进行 Heartbeat， Candidate 收到后状态自动转为 Follower，完成选主。

以上是 Raft 最重要活动之一选主的介绍，以及在不同情况下如何进行选主。

3. 复制日志 Log Replication

3.1 正常情况下复制日志

Raft 在实际应用场景中的一致性更多的是体现在不同节点之间的数据一致性，客户端发送请求到任何一个节点都能收到一致的返回，当一个节点出故障后，其他节点仍然能以已有的数据正常进行。在选主之后的复制日志就是为了达到这个目的。

一开始，Leader 和 两个 Follower 都没有任何数据。

客户端发送请求给 Leader，储存数据 “sally”，Leader 先将数据写在本地日志，这时候数据还是 Uncommitted (还没最终确认，红色表示)

Leader 给两个 Follower 发送 AppendEntries 请求，数据在 Follower 上没有冲突，则将数据暂时写在本地日志，Follower 的数据也还是 Uncommitted。

Follower 将数据写到本地后，返回 OK。Leader 收到后成功返回，只要收到的成功的返回数量超过半数 (包含Leader)，Leader 将数据 “sally” 的状态改成 Committed。( 这个时候 Leader 就可以返回给客户端了)

Leader 再次给 Follower 发送 AppendEntries 请求，收到请求后，Follower 将本地日志里 Uncommitted 数据改成 Committed。这样就完成了一整个复制日志的过程，三个节点的数据是一致的，

3.2 Network Partition 情况下进行复制日志

在 Network Partition 的情况下，部分节点之间没办法互相通信，Raft 也能保证在这种情况下数据的一致性。

一开始有 5 个节点处于同一网络状态下。

Network Partition 将节点分成两边，一边有两个节点，一边三个节点。

两个节点这边已经有 Leader 了，来自客户端的数据 “bob” 通过 Leader 同步到 Follower。

因为只有两个节点，少于3个节点，所以 “bob” 的状态仍是 Uncommitted。所以在这里，服务器会返回错误给客户端

另外一个 Partition 有三个节点，进行重新选主。客户端数据 “tom” 发到新的 Leader，通过和上节网络状态下相似的过程，同步到另外两个 Follower。

因为这个 Partition 有3个节点，超过半数，所以数据 “tom” 都 Commit 了。

网络状态恢复，5个节点再次处于同一个网络状态下。但是这里出现了数据冲突 “bob" 和 “tom"

三个节点的 Leader 广播 AppendEntries

两个节点 Partition 的 Leader 自动降级为 Follower，因为这个 Partition 的数据 “bob” 没有 Commit，返回给客户端的是错误，客户端知道请求没有成功，所以 Follower 在收到 AppendEntries 请求时，可以把 “bob“ 删除，然后同步 ”tom”，通过这么一个过程，就完成了在 Network Partition 情况下的复制日志，保证了数据的一致性。

小结

Raft 是能够实现分布式系统强一致性的算法，每个系统节点有三种状态 Follower，Candidate，Leader。实现 Raft 算法两个最重要的事是：选主和复制日志。

一致性协议之 ZAB

什么是 ZAB 协议？ZAB 协议介绍

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。

ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议。

整个 Zookeeper 就是在这两个模式之间切换。简而言之，当 Leader 服务可以正常使用，就进入消息广播模式，当 Leader 不可用时，则进入崩溃恢复模式。

基于该协议，Zookeeper 实现了一种 主备模式 的系统架构来保持集群中各个副本之间数据一致性。其中所有客户端写入数据都是写入到 主进程（称为 Leader）中，然后，由 Leader 复制到备份进程（称为 Follower）中。【涉及到2PC单点问题的解决，崩溃恢复】

选择机制中的概念

1、Serverid：服务器ID

比如有三台服务器，编号分别是1,2,3。

编号越大在选择算法中的权重越大。

2、Zxid：数据ID

服务器中存放的最大数据ID。【zxid实际上是一个64位的数字，高32位是epoch（时期; 纪元; 世; 新时代）用来标识leader是否发生改变，如果有新的leader产生出来，epoch会自增，低32位用来递增计数。】

值越大说明数据越新，在选举算法中数据越新权重越大。

3、Epoch：逻辑时钟

或者叫投票的次数，同一轮投票过程中的逻辑时钟值是相同的。每投完一次票这个数据就会增加，然后与接收到的其它服务器返回的投票信息中的数值相比，根据不同的值做出不同的判断。

4、Server状态：选举状态

LOOKING，竞选状态。

FOLLOWING，随从状态，同步leader状态，参与投票。

OBSERVING，观察状态,同步leader状态，不参与投票。

LEADING，领导者状态。

选举消息内容

在投票完成后，需要将投票信息发送给集群中的所有服务器，它包含如下内容：服务器ID、数据ID、逻辑时钟、选举状态。

zookeeper是如何保证事务的顺序一致性的（保证消息有序） 在整个消息广播中，Leader会将每一个事务请求转换成对应的 proposal 来进行广播，并且在广播 事务Proposal 之前，Leader服务器会首先为这个事务Proposal分配一个全局单递增的唯一ID，称之为事务ID（即zxid），由于Zab协议需要保证每一个消息的严格的顺序关系，因此必须将每一个proposal按照其zxid的先后顺序进行排序和处理。

消息广播

1）在zookeeper集群中，数据副本的传递策略就是采用消息广播模式。zookeeper中农数据副本的同步方式与二段提交相似，但是却又不同。二段提交要求协调者必须等到所有的参与者全部反馈ACK确认消息后，再发送commit消息。要求所有的参与者要么全部成功，要么全部失败。二段提交会产生严重的阻塞问题。

2）Zab协议中 Leader 等待 Follower 的ACK反馈消息是指“只要半数以上的Follower成功反馈即可，不需要收到全部Follower反馈”。

消息广播具体步骤

1）客户端发起一个写操作请求。

2）Leader 服务器将客户端的请求转化为事务 Proposal 提案，同时为每个 Proposal 分配一个全局的ID，即zxid。

3）Leader 服务器为每个 Follower 服务器分配一个单独的队列，然后将需要广播的 Proposal 依次放到队列中取，并且根据 FIFO 策略进行消息发送。

4）Follower 接收到 Proposal 后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后向 Leader 反馈一个 Ack 响应消息。

5）Leader 接收到超过半数以上 Follower 的 Ack 响应消息后，即认为消息发送成功，可以发送 commit 消息。

6）Leader 向所有 Follower 广播 commit 消息，同时自身也会完成事务提交。Follower 接收到 commit 消息后，会将上一条事务提交。

zookeeper 采用 Zab 协议的核心，就是只要有一台服务器提交了 Proposal，就要确保所有的服务器最终都能正确提交 Proposal。这也是 CAP/BASE 实现最终一致性的一个体现。

Leader 服务器与每一个 Follower 服务器之间都维护了一个单独的 FIFO 消息队列进行收发消息，使用队列消息可以做到异步解耦。Leader 和 Follower 之间只需要往队列中发消息即可。如果使用同步的方式会引起阻塞，性能要下降很多。

崩溃恢复

崩溃恢复主要包括两部分：Leader选举 和 数据恢复

zookeeper是如何选取主leader的？

当leader崩溃或者leader失去大多数的follower，这时zk进入恢复模式，恢复模式需要重新选举出一个新的leader，让所有的Server都恢复到一个正确的状态。

Zookeeper选主流程 选举流程详述

一、首先开始选举阶段，每个Server读取自身的zxid。

二、发送投票信息

a、首先，每个Server第一轮都会投票给自己。

b、投票信息包含 ：所选举leader的Serverid，Zxid，Epoch。Epoch会随着选举轮数的增加而递增。

三、接收投票信息

1、如果服务器B接收到服务器A的数据（服务器A处于选举状态(LOOKING 状态)

1）首先，判断逻辑时钟值：

a）如果发送过来的逻辑时钟Epoch大于目前的逻辑时钟。首先，更新本逻辑时钟Epoch，同时清空本轮逻辑时钟收集到的来自其他server的选举数据。然后，判断是否需要更新当前自己的选举leader Serverid。判断规则rules judging：保存的zxid最大值和leader Serverid来进行判断的。先看数据zxid,数据zxid大者胜出;其次再判断leader Serverid,leader Serverid大者胜出；然后再将自身最新的选举结果(也就是上面提到的三种数据（leader Serverid，Zxid，Epoch）广播给其他server)

b）如果发送过来的逻辑时钟Epoch小于目前的逻辑时钟。说明对方server在一个相对较早的Epoch中，这里只需要将本机的三种数据（leader Serverid，Zxid，Epoch）发送过去就行。

c）如果发送过来的逻辑时钟Epoch等于目前的逻辑时钟。再根据上述判断规则rules judging来选举leader ，然后再将自身最新的选举结果(也就是上面提到的三种数据（leader Serverid，Zxid，Epoch）广播给其他server)。

2）其次，判断服务器是不是已经收集到了所有服务器的选举状态：若是，根据选举结果设置自己的角色(FOLLOWING还是LEADER)，退出选举过程就是了。

最后，若没有收集到所有服务器的选举状态：也可以判断一下根据以上过程之后最新的选举leader是不是得到了超过半数以上服务器的支持,如果是,那么尝试在200ms内接收一下数据,如果没有新的数据到来,说明大家都已经默认了这个结果,同样也设置角色退出选举过程。

2、 如果所接收服务器A处在其它状态（FOLLOWING或者LEADING）。

a)逻辑时钟Epoch等于目前的逻辑时钟，将该数据保存到recvset。此时Server已经处于LEADING状态，说明此时这个server已经投票选出结果。若此时这个接收服务器宣称自己是leader, 那么将判断是不是有半数以上的服务器选举它，如果是则设置选举状态退出选举过程。

b) 否则这是一条与当前逻辑时钟不符合的消息，那么说明在另一个选举过程中已经有了选举结果，于是将该选举结果加入到outofelection集合中，再根据outofelection来判断是否可以结束选举,如果可以也是保存逻辑时钟，设置选举状态，退出选举过程。【recvset：用来记录选票信息，以方便后续统计;outofelection：用来记录选举逻辑之外的选票，例如当一个服务器加入zookeeper集群时，因为集群已经存在，不用重新选举，只需要在满足一定条件下加入集群即可。】

描述Leader选择过程中的状态变化，这是假设全部实例中均没有数据，假设服务器启动顺序分别为：A,B,C。

Zab 协议如何保证数据一致性

假设两种异常情况：1、一个事务在 Leader 上提交了，并且过半的 Folower 都响应 Ack 了，但是 Leader 在 Commit 消息发出之前挂了。2、假设一个事务在 Leader 提出之后，Leader 挂了。

要确保如果发生上述两种情况，数据还能保持一致性，那么 Zab 协议选举算法必须满足以下要求：

Zab 协议崩溃恢复要求满足以下两个要求：1）确保已经被 Leader 提交的 Proposal 必须最终被所有的 Follower 服务器提交。2）确保丢弃已经被 Leader 提出的但是没有被提交的 Proposal。

根据上述要求 Zab协议需要保证选举出来的Leader需要满足以下条件：1）新选举出来的 Leader 不能包含未提交的 Proposal 。即新选举的 Leader 必须都是已经提交了 Proposal 的 Follower 服务器节点。2）新选举的 Leader 节点中含有最大的 zxid 。这样做的好处是可以避免 Leader 服务器检查 Proposal 的提交和丢弃工作。

Zab 如何数据同步

1）完成 Leader 选举后（新的 Leader 具有最高的zxid），在正式开始工作之前（接收事务请求，然后提出新的 Proposal），Leader 服务器会首先确认事务日志中的所有的 Proposal 是否已经被集群中过半的服务器 Commit。

2）Leader 服务器需要确保所有的 Follower 服务器能够接收到每一条事务的 Proposal ，并且能将所有已经提交的事务 Proposal 应用到内存数据中。等到 Follower 将所有尚未同步的事务 Proposal 都从 Leader 服务器上同步过啦并且应用到内存数据中以后，Leader 才会把该 Follower 加入到真正可用的 Follower 列表中。

Zab 数据同步过程中，如何处理需要丢弃的 Proposal

在 Zab 的事务编号 zxid 设计中，zxid是一个64位的数字。

其中低32位可以看成一个简单的单增计数器，针对客户端每一个事务请求，Leader 在产生新的 Proposal 事务时，都会对该计数器加1。而高32位则代表了 Leader 周期的 epoch 编号。

epoch 编号可以理解为当前集群所处的年代，或者周期。每次Leader变更之后都会在 epoch 的基础上加1，这样旧的 Leader 崩溃恢复之后，其他Follower 也不会听它的了，因为 Follower 只服从epoch最高的 Leader 命令。

每当选举产生一个新的 Leader ，就会从这个 Leader 服务器上取出本地事务日志充最大编号 Proposal 的 zxid，并从 zxid 中解析得到对应的 epoch 编号，然后再对其加1，之后该编号就作为新的 epoch 值，并将低32位数字归零，由0开始重新生成zxid。

Zab 协议通过 epoch 编号来区分 Leader 变化周期，能够有效避免不同的 Leader 错误的使用了相同的 zxid 编号提出了不一样的 Proposal 的异常情况。

基于以上策略:

当一个包含了上一个 Leader 周期中尚未提交过的事务 Proposal 的服务器启动时，当这台机器加入集群中，以 Follower 角色连上 Leader 服务器后，Leader 服务器会根据自己服务器上最后提交的 Proposal 来和 Follower 服务器的 Proposal 进行比对，比对的结果肯定是 Leader 要求 Follower 进行一个回退操作，回退到一个确实已经被集群中过半机器 Commit 的最新 Proposal。

小结

ZAB 协议和我们之前看的 Raft 协议实际上是有相似之处的，比如都有一个 Leader，用来保证一致性（Paxos 并没有使用 Leader 机制保证一致性）。再有采取过半即成功的机制保证服务可用（实际上 Paxos 和 Raft 都是这么做的）。

ZAB 让整个 Zookeeper 集群在两个模式之间转换，消息广播和崩溃恢复，消息广播可以说是一个简化版本的 2PC，通过崩溃恢复解决了 2PC 的单点问题，通过队列解决了 2PC 的同步阻塞问题。

而支持崩溃恢复后数据准确性的就是数据同步了，数据同步基于事务的 ZXID 的唯一性来保证。通过 + 1 操作可以辨别事务的先后顺序。

NWR模型

Amazon Dynamo的NWR模型。NWR模型把CAP的选择权交给了用户，让用户自己的选择你的CAP中的哪两个。

所谓NWR模型。N代表N个备份，W代表要写入至少W份才认为成功，R表示至少读取R个备份。配置的时候要求W+R > N。因为W+R > N， 所以 R > N-W 这个是什么意思呢？就是读取的份数一定要比总备份数减去确保写成功的倍数的差值要大。

也就是说，每次读取，都至少读取到一个最新的版本。从而不会读到一份旧数据。当我们需要高可写的环境的时候，我们可以配置W = 1 如果N=3 那么R = 3。这个时候只要写任何节点成功就认为成功，但是读的时候必须从所有的节点都读出数据。如果我们要求读的高效率，我们可以配置 W=N R=1。这个时候任何一个节点读成功就认为成功，但是写的时候必须写所有三个节点成功才认为成功。

NWR模型的一些设置会造成脏数据的问题，因为这很明显不是像Paxos一样是一个强一致的东西，所以，可能每次的读写操作都不在同一个结点上，于是会出现一些结点上的数据并不是最新版本，但却进行了最新的操作。

所以，Amazon Dynamo引了数据版本的设计。也就是说，如果你读出来数据的版本是v1，当你计算完成后要回填数据后，却发现数据的版本号已经被人更新成了v2，那么服务器就会拒绝你。版本这个事就像“乐观锁”一样。

但是，对于分布式和NWR模型来说，版本也会有恶梦的时候——就是版本冲的问题，比如：我们设置了N=3 W=1，如果A结点上接受了一个值，版本由v1 -> v2，但还没有来得及同步到结点B上（异步的，应该W=1，写一份就算成功），B结点上还是v1版本，此时，B结点接到写请求，按道理来说，他需要拒绝掉，但是他一方面并不知道别的结点已经被更新到v2，另一方面他也无法拒绝，因为W=1，所以写一分就成功了。于是，出现了严重的版本冲突。

Amazon的Dynamo把版本冲突这个问题巧妙地回避掉了——版本冲突这个事交给用户自己来处理。

于是，Dynamo引入了Vector Clock（矢量钟）这个设计。这个设计让每个结点各自记录自己的版本信息，也就是说，对于同一个数据，需要记录两个事：1）谁更新的我，2）我的版本号是什么。

下面，我们来看一个操作序列：

1）一个写请求，第一次被节点A处理了。节点A会增加一个版本信息(A，1)。我们把这个时候的数据记做D1(A，1)。然后另外一个对同样key的请求还是被A处理了于是有D2(A，2)。这个时候，D2是可以覆盖D1的，不会有冲突产生。

2）现在我们假设D2传播到了所有节点(B和C)，B和C收到的数据不是从客户产生的，而是别人复制给他们的，所以他们不产生新的版本信息，所以现在B和C所持有的数据还是D2(A，2)。于是A，B，C上的数据及其版本号都是一样的。

3）如果我们有一个新的写请求到了B结点上，于是B结点生成数据D3(A,2; B,1)，意思是：数据D全局版本号为3，A升了两新，B升了一次。这不就是所谓的代码版本的log么？

4）如果D3没有传播到C的时候又一个请求被C处理了，于是，以C结点上的数据是D4(A,2; C,1)。

5）好，最精彩的事情来了：如果这个时候来了一个读请求，我们要记得，我们的W=1 那么R=N=3，所以R会从所有三个节点上读，此时，他会读到三个版本：

•A结点：D2(A,2)•B结点：D3(A,2; B,1);•C结点：D4(A,2; C,1)

6）这个时候可以判断出，D2已经是旧版本（已经包含在D3/D4中），可以舍弃。

7）但是D3和D4是明显的版本冲突。于是，交给调用方自己去做版本冲突处理。就像源代码版本管理一样。

很明显，上述的Dynamo的配置用的是CAP里的A和P。