一致性算法2PC、3PC、Paxos、Raft、ZAB

发表于2021-03-08更新于2022-06-05字数统计8.4k阅读时长45分

一致性算法2PC、3PC、Paxos、Raft、ZAB

文章目录

简述

一个分布式系统可能面临多个问题：

  1. 消息传递异步无序: 现实网络不是一个可靠的信道，存在消息延时、丢失，节点间消息传递做不到同步有序
  2. 节点宕机: 节点持续宕机，不会恢复
  3. 节点宕机恢复: 节点宕机一段时间后恢复，在分布式系统中最常见
  4. 网络分化: 网络链路中的某个部位出现问题
  5. 拜占庭将军问题: 在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的，所以所有的一致性算法的 必要前提 就是安全可靠的消息通道，发出的信号不会被篡改。

拜占庭将军问题：是指 拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，只能依靠通讯员进行传递命令，但是通讯员中存在叛徒，它们可以篡改消息，叛徒可以欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。

而为什么要去解决数据一致性的问题？你想想，如果将网上商城购物系统拆分成了订单和积分子系统，这两个子系统部署在不同的机器上了，万一在消息的传播过程中积分系统宕机了，总不能你这边下了订单却没加积分吧？你总得保证两边的数据需要一致吧？

一、2PC（两阶段提交）

千万不要吧PC理解成个人电脑了，其实他们是 phase-commit 的缩写，即阶段提交。

2PC(tow phase commit)两阶段提交，所谓的两个阶段是指：第一阶段：准备阶段，第二阶段：提交阶段。

在我们所需要解决的是在分布式系统中，整个调用链中，我们所有服务的数据处理要么都成功要么都失败，即所有服务的 原子性问题 。

两阶段提交是一种保证分布式系统数据一致性协议，它本身是一致强一致性算法，现在很多数据库都是采用的两阶段提交协议来完成 分布式事务 的处理。

在两阶段提交中，主要涉及到两个角色，分别是协调者和参与者。

第一阶段：当要执行一个分布式事务的时候，事务发起者首先向协调者发起事务请求，然后协调者会给所有参与者发送 prepare 请求（其中包括事务内容）告诉参与者你们需要执行事务了，如果能执行我发的事务内容那么就先执行但不提交，执行后请给我回复。然后参与者收到 prepare 消息后，他们会开始执行事务（但不提交），并将 Undo 和 Redo 信息记入事务日志中，之后参与者就向协调者反馈是否准备好了。

第二阶段：第二阶段主要是协调者根据参与者反馈的情况来决定接下来是否可以进行事务的提交操作，即提交事务或者回滚事务。

比如这个时候 所有的参与者 都返回了准备好了的消息，这个时候就进行事务的提交，协调者此时会给所有的参与者发送 Commit 请求 ，当参与者收到 Commit 请求的时候会执行前面执行的事务的 提交操作 ，提交完毕之后将给协调者发送提交成功的响应。

而如果在第一阶段并不是所有参与者都返回了准备好了的消息，那么此时协调者将会给所有参与者发送 回滚事务的 rollback 请求，参与者收到之后将会 回滚它在第一阶段所做的事务处理 ，然后再将处理情况返回给协调者，最终协调者收到响应后便给事务发起者返回处理失败的结果。

优点：原理简单，实现方便

缺点：单点问题，同步阻塞，，数据不一致，容错性不好

  • 单点故障问题，如果协调者挂了那么整个系统都处于不可用的状态了。
  • 阻塞问题，在二阶段提交的过程中，整体链路所有的节点都在等待其他节点的响应，无法进行其他操作。这种同步阻塞极大的限制了分布式系统的性能。
  • 数据不一致问题，比如当第二阶段，协调者只发送了一部分的 commit 请求就挂了，那么也就意味着，收到消息的参与者会进行事务的提交，而后面没收到的则不会进行事务提交，那么这时候就会产生数据不一致性问题。
  • 容错性不好，二阶段提交协议没有设计较为完善的容错机制，任意一个节点是失败都会导致整个事务的失败。

二、3PC

三阶段提交（Three-phase commit），是二阶段提交（2PC）的改进版本。与两阶段提交不同的是，三阶段提交有两个改动点。

  1. 引入超时机制。同时在协调者和参与者中都引入超时机制。
  2. 在第一阶段和第二阶段中插入一个准备阶段，保证了在最后提交阶段之前各参与节点的状态是一致的。也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。

3PC是弱一致性算法，因为它引入超时时间，系统中的所有数据副本经过一定时间后，最终才能能够达到一致的状态

各个阶段的执行过程如下：

  1. CanCommit阶段：协调者向所有参与者发送 CanCommit 请求，参与者收到请求后会根据自身情况查看是否能执行事务，如果可以则返回 YES 响应并进入预备状态，否则返回 NO 。
  2. PreCommit阶段：协调者根据参与者返回的响应来决定是否可以进行下面的 PreCommit 操作。如果上面参与者返回的都是 YES，那么协调者将向所有参与者发送 PreCommit 预提交请求，参与者收到预提交请求后，会进行事务的执行操作，并将 Undo 和 Redo 信息写入事务日志中 ，最后如果参与者顺利执行了事务则给协调者返回成功的响应。如果在第一阶段协调者收到了 任何一个 NO 的信息，或者 在一定时间内 并没有收到全部的参与者的响应，那么就会中断事务，它会向所有参与者发送中断请求（abort），参与者收到中断请求之后会立即中断事务，或者在一定时间内没有收到协调者的请求，它也会中断事务。
  3. DoCommit阶段：这个阶段其实和 2PC 的第二阶段差不多，如果协调者收到了所有参与者在 PreCommit 阶段的 YES 响应，那么协调者将会给所有参与者发送 DoCommit 请求，参与者收到 DoCommit 请求后则会进行事务的提交工作，完成后则会给协调者返回响应，协调者收到所有参与者返回的事务提交成功的响应之后则完成事务。若协调者在 PreCommit 阶段 收到了任何一个 NO 或者在一定时间内没有收到所有参与者的响应 ，那么就会进行中断请求的发送，参与者收到中断请求后则会 通过上面记录的回滚日志 来进行事务的回滚操作，并向协调者反馈回滚状况，协调者收到参与者返回的消息后，中断事务。

上图是 3PC 成功运行时的流程图，可以看到 3PC 在很多地方进行了超时中断的处理，比如协调者在指定时间内为收到全部的确认消息则进行事务中断的处理，这样能 减少同步阻塞的时间 。还有需要注意的是，3PC 在 DoCommit 阶段参与者如未收到协调者发送的提交事务的请求，也会在一定时间内进行事务的提交。为什么这么做呢？是因为这个时候我们肯定保证了在第一阶段所有的协调者全部返回了可以执行事务的响应，这个时候我们有理由相信其他系统都能进行事务的执行和提交，所以不管协调者有没有发DoCommit 请求给参与者，进入第三阶段参与者都会进行事务的提交操作。

总之，3PC 通过一系列的超时机制很好的缓解了阻塞问题，但是最重要的一致性并没有得到根本的解决，比如由于网络原因，协调者发送的abort中断请求没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort请求并执行回滚的参与者之间存在数据不一致的情况。

所以，要解决一致性问题还需要靠 Paxos 算法

三、Paxos 算法

该算法的提出者莱斯利·兰伯特在前面几篇论文中都不是以严谨的数学公式进行的。其实这个paxos算法也分成两阶段。

Paxos 算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致 。这 个“值”可能是一个数据的某，也可能是一条LOG等；根据不同的应用环境这个“值”也不同。在 Paxos 中主要有三个角色，分别为 Proposer提案者、Acceptor表决者、Learner学习者。

3.1 第一阶段：prepare 阶段

Proposer提案者选择一个具有全局唯一性的、递增的提案编号N，即在整个集群中是唯一的编号 N，在第一阶段是只将编号为N的Prepare请求发送给所有的表决者。

如果一个Acceptor表决者收到一个编号为N的Prepare请求，如果N小于它已经响应过的提案编号，则拒绝或不响应。若N大于该Acceptor已经响应过的所有Prepare请求的编号（maxN），那么Acceptor会将以前接受过的最大编号的提案作为响应反馈给 Proposer ，同时该Acceptor承诺不再接受任何编号小于N的提案。

3.2 第二阶段：accept 阶段

如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么此时 Proposer 会给所有的 Acceptor 发送真正的提案（你可以理解为第一阶段为试探），这个时候 Proposer 就会发送提案的内容和提案编号。

表决者收到提案请求后会比较本身已经接受过的最大提案编号和该提案编号，如果该提案编号 大于等于 已经接受过的最大提案编号，那么就 accept 该提案（此时执行提案内容但不提交），随后将情况返回给 Proposer 。如果不满足则不回应或者返回 NO 。

当 Proposer 收到超过半数的 accept ，那么它这个时候会向所有的 acceptor 发送提案的提交请求。需要注意的是，因为上述仅仅是超过半数的 acceptor 批准执行了该提案内容，其他没有批准的并没有执行该提案内容，所以这个时候需要向未批准的 acceptor 发送提案内容和提案编号并让它无条件执行和提交，而对于前面已经批准过该提案的 acceptor 来说 仅仅需要发送该提案的编号 ，让 acceptor 执行提交就行了。

而如果 Proposer 如果没有收到超过半数的 accept 那么它将会将 递增 该 Proposal 的编号，然后 重新进入 Prepare 阶段 。

Learner学习被选定的第二阶段达成的某个值（决议），这里我们称之为Value。Learner学习方式有三种方案：

3.3 paxos 算法的死循环问题

有的人说是活锁，我认为是死锁，因为比较两个proposer都没有完成Paxos的第二阶段，一直在重复自增提案编号，导致谁都无法最终完成提案，即造成两个进程争夺资源（这里提案编号资源），互相等待对方的资源，谁也不肯放弃，从而造成死锁。

选择一个主Proposer，并规定只有主Proposer才能提出议案。这样一来，只要主Proposer和过半的Acceptor能够正常进行网络通信，那么肯定会有一个提案被批准（第二阶段的accept），则可以解决死循环导致的活锁问题。

Paxos是基于消息传递的具有高度容错性的分布式一致性算法。Paxos算法引入了过半的概念，解决了2PC，3PC的太过保守的缺点，且使算法具有了很好的容错性，另外Paxos算法支持分布式节点角色之间的转换，这极大避免了分布式单点问题的出现，因此Paxos算法既解决了无限等待问题，也解决了脑裂问题，是目前来说最优秀的分布式一致性算法。其中，Zookeeper的ZAB算法和Raft一致性算法都是基于Paxos的。

3.4 举例说明

假设：只有User1、User2、User3 三个人决定1+1等于几！

第一阶段

  1. User1 提案编号为 1 并发送给User2和User3。

因User2 和User3 并没有接受过小于编号为1的提案，所以它们可以接受该提议，并反馈给User1 不再接受小于编号1的提案。这时User1收到多数人的回复，将进入第2阶段。（如果收到的回复并不能形成多数人，那么将再次进入阶段1）

  1. User2 提案编号为2 ，并发送给User1和User3。‘

User1第一次收到提案，它并没有同意过小于编号为2的提议，所以它可以接受该提议。User3由于接受过User1编号为1的提案，但User2的提案编号 2 > 1 所以User3也可以同意User2的提议，并反馈不再接受小于2的提议。User2也收到多数人的回复，将进行第2阶段。

  1. User3提案编号为3 ，并发送给user1 和user2 .

因user1收到user3编号为3的提案 > user2编号为2的提案，所以接受user3的提案。因user2收到User3编号为3的提案 > user1 编号为1的提案，所以接受user3的提案。至此user3也收到多数人回复，将进行第2阶段。

第二阶段

  1. user1 发送编号为1的提议，提议内容为：1+1=1；并发送给user2和User3 。

由于user2已经声明不再接受小于3的提案，所以拒绝user1的提案。由于User3已经声明不再接受小于2的提案，所以同样拒绝User1的提案。User1提议被多数人拒绝，再次进入阶段1

  1. user2 发送编号为2的提议，提议内容为：1+1=2；并发送给User1和User3

由于User1已经声明不再接受小于3的提案，所以拒绝user2的提议。由于User3已经声明不再接受小于2的提案，该提案编号=2所以user3同意User2的提议。但User2并没有获得多数人的同意，所以同样进行阶段1.

  1. User3 发送编号为3的提议，提议内容为：1+1=3；并发送给User1和User2;

由于 user1 声明不再接受小于3的提案，所以同意User3的提议。由于 user2 声明不再接受小于3的提案，所以同意User3的提议。

至此最终User3可以获得多数人的同意。

虽然上面没有说自己同意自己，但我认为自己可以同意自己，毕竟如果有三台机器，总不可能让另外两台都同意吧，这不就成了在投票阶段3台决定Leader了。

四、Raft

Raft 也是一个一致性算法，和 Paxos 目标相同。但他还有另一个名字：易于理解的一致性算法。也就是说，他的目标就是成为一个易于理解的一致性算法。以替代 Paxos 的晦涩难懂。

什么是 Raft 算法

首先说什么是 Raft 算法：Raft 是一种为了管理复制日志的一致性算法。

什么是一致性呢？

Raft 的论文这么说的：一致性算法允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。

这里的一致性针对分布式系统。

领导人选举

Raft 通过选举一个高贵的领导人，然后给予他全部的管理复制日志的责任来实现一致性。

而每个 server 都可能会在 3 个身份之间切换：

领导者 候选者 跟随者

而影响他们身份变化的则是 选举。当所有服务器初始化的时候，都是 跟随者，这个时候需要一个 领导者，所有人都变成 候选者，直到有人成功当选 领导者。角色轮换如下图：

而领导者也有宕机的时候，宕机后引发新的 选举，所以，整个集群在选举和正常运行之间切换，具体如下图：

从上图可以看出，选举和正常运行之间切换，但请注意， 上图中的 term 3 有一个地方，后面没有跟着 正常运行 阶段，为什么呢?

答：当一次选举失败（比如正巧每个人都投了自己），就执行一次 加时赛，每个 Server 会在一个随机的时间里重新投票，这样就能保证不冲突了。所以，当 term 3 选举失败，等了几十毫秒，执行 term 4 选举，并成功选举出领导人。

接着，领导者周期性的向所有跟随者发送心跳包来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。

要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后请求其他服务器为自己投票。那么会产生 3 种结果：

a. 自己成功当选 b. 其他的服务器成为领导者 c. 僵住，没有任何一个人成为领导者

注意：

每一个 server 最多在一个任期内投出一张选票（有任期号约束），先到先得。要求最多只能有一个人赢得选票。一旦成功，立即成为领导人，然后广播所有服务器停止投票阻止新得领导产生。僵住怎么办？Raft 通过使用随机选举超时时间（例如 150 - 300 毫秒）的方法将服务器打散投票。每个候选人在僵住的时候会随机从一个时间开始重新选举。以上，就是 Raft 所有关于领导选举的策略。

日志复制

一旦一个领导人被选举出来，他就开始为客户端提供服务。客户端发送日志给领导者，随后领导者将日志复制到其他的服务器。如果跟随者故障，领导者将会尝试重试。直到所有的跟随者都成功存储了所有日志。

下图表示了当一个客户端发送一个日志给领导者，随后领导者复制给跟随者的整个过程

4 个步骤：

  1. 客户端提交
  2. 复制数据到所有跟随者
  3. 跟随者回复 确认收到
  4. 领导者回复客户端和所有跟随者 确认提交。

可以看到，直到第四步骤，整个事务才会达成。中间任何一个步骤发生故障，都不会影响日志一致性。

Raft算法具备强一致、高可靠、高可用等优点，具体体现在：

强一致性：虽然所有节点的数据并非实时一致，但Raft算法保证Leader节点的数据最全，同时所有请求都由Leader处理，所以在客户端角度看是强一致性的。

高可靠性：Raft算法保证了Committed的日志不会被修改，State Matchine只应用Committed的日志，所以当客户端收到请求成功即代表数据不再改变。Committed日志在大多数节点上冗余存储，少于一半的磁盘故障数据不会丢失。

高可用性：从Raft算法原理可以看出，选举和日志同步都只需要大多数的节点正常互联即可，所以少量节点故障或网络异常不会影响系统的可用性。即使Leader故障，在选举超时到期后，集群自发选举新Leader，无需人工干预，不可用时间极小。但Leader故障时存在重复数据问题，需要业务去重或幂等性保证。

高性能：与必须将数据写到所有节点才能返回客户端成功的算法相比，Raft算法只需要大多数节点成功即可，少量节点处理缓慢不会延缓整体系统运行。

五、ZAB

作为一个优秀高效且可靠的分布式协调框架，ZooKeeper 在解决分布式数据一致性问题时并没有直接使用 Paxos ，而是专门定制了一致性协议叫做 ZAB(ZooKeeper Automic Broadcast) 原子广播协议，该协议能够很好地支持 崩溃恢复 。

5.1 ZAB 中的三个角色

ZAB 中三个主要的角色，Leader 领导者、Follower跟随者、Observer观察者 。

  • Leader ：集群中 唯一的写请求处理者 ，能够发起投票（投票也是为了进行写请求）。
  • Follower：能够接收客户端的请求，如果是读请求则可以自己处理，如果是写请求则要转发给 Leader 。在选举过程中会参与投票，有选举权和被选举权 。
  • Observer ：就是没有选举权和被选举权的 Follower 。

在 ZAB 协议中对 zkServer(即上面我们说的三个角色的总称) 还有两种模式的定义，分别是 消息广播 和 崩溃恢复 。

5.2 ZXID和myid

ZooKeeper 采用全局递增的事务 id 来标识，所有 proposal(提议)在被提出的时候加上了ZooKeeper Transaction Id 。ZXID是64位的Long类型，这是保证事务的顺序一致性的关键。ZXID中高32位表示纪元epoch，低32位表示事务标识xid。你可以认为zxid越大说明存储数据越新，如下图所示：

  1. 每个leader都会具有不同的epoch值，表示一个纪元/朝代，用来标识 leader周期。每个新的选举开启时都会生成一个新的epoch，从1开始，每次选出新的Leader，epoch递增1，并会将该值更新到所有的zkServer的zxid的epoch。
  2. xid是一个依次递增的事务编号。数值越大说明数据越新，可以简单理解为递增的事务id。每次epoch变化，都将低32位的序号重置，这样保证了zxid的全局递增性。

每个ZooKeeper服务器，都需要在数据文件夹下创建一个名为myid的文件，该文件包含整个ZooKeeper集群唯一的id（整数）。例如，某ZooKeeper集群包含三台服务器，hostname分别为zoo1、zoo2和zoo3，其myid分别为1、2和3，则在配置文件中其id与hostname必须一一对应，如下所示。在该配置文件中，server.后面的数据即为myid

1
2
3
server.1=zoo1:2888:3888
server.2=zoo2:2888:3888
server.3=zoo3:2888:3888

5.3 历史队列

每一个follower节点都会有一个先进先出（FIFO)的队列用来存放收到的事务请求，保证执行事务的顺序。所以：

  • 可靠提交由ZAB的事务一致性协议保证
  • 全局有序由TCP协议保证
  • 因果有序由follower的历史队列(history queue)保证

5.4 消息广播模式

ZAB协议两种模式：消息广播模式和崩溃恢复模式。

说白了就是 ZAB 协议是如何处理写请求的，上面我们不是说只有 Leader 能处理写请求嘛？那么我们的 Follower 和 Observer 是不是也需要 同步更新数据 呢？总不能数据只在 Leader 中更新了，其他角色都没有得到更新吧。

第一步肯定需要 Leader 将写请求 广播 出去呀，让 Leader 问问 Followers 是否同意更新，如果超过半数以上的同意那么就进行 Follower 和 Observer 的更新（和 Paxos 一样）。消息广播机制是通过如下图流程保证事务的顺序一致性的：

  1. leader从客户端收到一个写请求
  2. leader生成一个新的事务并为这个事务生成一个唯一的ZXID
  3. leader将这个事务发送给所有的follows节点，将带有 zxid 的消息作为一个提案(proposal)分发给所有 follower。
  4. follower节点将收到的事务请求加入到历史队列(history queue)中，当 follower 接收到 proposal，先将 proposal 写到硬盘，写硬盘成功后再向 leader 回一个 ACK
  5. 当leader收到大多数follower（超过一半）的ack消息，leader会向follower发送commit请求（leader自身也要提交这个事务）
  6. 当follower收到commit请求时，会判断该事务的ZXID是不是比历史队列中的任何事务的ZXID都小，如果是则提交事务，如果不是则等待比它更小的事务的commit(保证顺序性)
  7. Leader将处理结果返回给客户端

过半写成功策略：Leader节点接收到写请求后，这个Leader会将写请求广播给各个Server，各个Server会将该写请求加入历史队列，并向Leader发送ACK信息，当Leader收到一半以上的ACK消息后，说明该写操作可以执行。Leader会向各个server发送commit消息，各个server收到消息后执行commit操作。

这里要注意以下几点：

  • Leader并不需要得到Observer的ACK，即Observer无投票权
  • Leader不需要得到所有Follower的ACK，只要收到过半的ACK即可，同时Leader本身对自己有一个ACK
  • Observer虽然无投票权，但仍须同步Leader的数据从而在处理读请求时可以返回尽可能新的数据

另外，Follower/Observer也可以接受写请求，此时：

  • Follower/Observer接受写请求以后，不能直接处理，而需要将写请求转发给Leader处理
  • 除了多了一步请求转发，其它流程与直接写Leader无任何区别
  • Leader处理写请求是通过上面的消息广播模式，实质上最后所有的zkServer都要执行写操作，这样数据才会一致

而对于读请求，Leader/Follower/Observer都可直接处理读请求，从本地内存中读取数据并返回给客户端即可。由于处理读请求不需要各个服务器之间的交互，因此Follower/Observer越多，整体可处理的读请求量越大，也即读性能越好。

5.5 崩溃恢复模式

恢复模式大致可以分为四个阶段：选举、发现、同步、广播。

  1. 选举阶段（Leader election）：当leader崩溃后，集群进入选举阶段（下面会将如何选举Leader），开始选举出潜在的准 leader，然后进入下一个阶段。
  2. 发现阶段（Discovery）：用于在从节点中发现最新的ZXID和事务日志。准Leader接收所有Follower发来各自的最新epoch值。Leader从中选出最大的epoch，基于此值加1，生成新的epoch分发给各个Follower。各个Follower收到全新的epoch后，返回ACK给Leader，带上各自最大的ZXID和历史提议日志。Leader选出最大的ZXID，并更新自身历史日志，此时Leader就用拥有了最新的提议历史。（注意：每次epoch变化时，ZXID的第32位从0开始计数）。
  3. 同步阶段（Synchronization）：主要是利用 leader 前一阶段获得的最新提议历史，同步给集群中所有的Follower。只有当超过半数Follower同步成功，这个准Leader才能成为正式的Leader。这之后，follower 只会接收 zxid 比自己的 lastZxid 大的提议。
  4. 广播阶段（Broadcast）：集群恢复到广播模式，开始接受客户端的写请求。

在发现阶段，或许有人会问：既然Leader被选为主节点，已经是集群里数据最新的了，为什么还要从节点中寻找最新事务呢？这是为了防止某些意外情况。所以这一阶段，Leader集思广益，接收所有Follower发来各自的最新epoch值。

这里有两点要注意：

（1）确保已经被Leader提交的提案最终能够被所有的Follower提交

假设 Leader (server2) 发送 commit 请求（忘了请看上面的消息广播模式），他发送给了 server3，然后要发给 server1 的时候突然挂了。这个时候重新选举的时候我们如果把 server1 作为 Leader 的话，那么肯定会产生数据不一致性，因为 server3 肯定会提交刚刚 server2 发送的 commit 请求的提案，而 server1 根本没收到所以会丢弃。

那怎么解决呢？

这个时候 server1 已经不可能成为 Leader 了，因为 server1 和 server3 进行投票选举的时候会比较 ZXID ，而此时 server3 的 ZXID 肯定比 server1 的大了（后面讲到选举机制时就明白了）。同理，只能由server3当Leader，server3当上Leader之后，在同步阶段，会将最新提议历史同步给集群中所有的Follower，这就保证数据一致性了。如果server2在某个时刻又重新恢复了，它作为Follower 的身份进入集群中，再向Leader同步当前最新提议和Zxid即可。

（2）确保跳过那些已经被丢弃的提案

假设 Leader (server2) 此时同意了提案N1，自身提交了这个事务并且要发送给所有 Follower 要 commit 的请求，却在这个时候挂了，此时肯定要重新进行 Leader 的选举，假如此时选 server1 为 Leader （这无所谓，server1和server2都可以当选）。但是过了一会，这个 挂掉的 Leader 又重新恢复了 ，此时它肯定会作为 Follower 的身份进入集群中，需要注意的是刚刚 server2 已经同意提交了提案N1，但其他 server 并没有收到它的 commit 信息，所以其他 server 不可能再提交这个提案N1了，这样就会出现数据不一致性问题了，所以 该提案N1最终需要被抛弃掉 。

5.6 脑裂问题

脑裂问题：所谓的“脑裂”即“大脑分裂”，也就是本来一个“大脑”被拆分了两个或多个“大脑”。通俗的说，就是比如当你的 cluster 里面有两个节点，它们都知道在这个 cluster 里需要选举出一个 master。那么当它们两之间的通信完全没有问题的时候，就会达成共识，选出其中一个作为 master。但是如果它们之间的通信出了问题，那么两个结点都会觉得现在没有 master，所以每个都把自己选举成 master，于是 cluster 里面就会有两个 master。

ZAB为解决脑裂问题，要求集群内的节点数量为2N+1, 当网络分裂后，始终有一个集群的节点数量过半数，而另一个集群节点数量小于N+1（即小于半数）, 因为选主需要过半数节点同意，所以任何情况下集群中都不可能出现大于一个leader的情况。

因此，有了过半机制，对于一个Zookeeper集群，要么没有Leader，要没只有1个Leader，这样就避免了脑裂问题。

【参考资料】

  1. https://snailclimb.gitee.io/javaguide/#/docs/system-design/distributed-system/zookeeper/zookeeper-plus
  2. https://mp.weixin.qq.com/s/b5mGEbn-FLb9vhOh1OpwIg