一文通吃：从 ZooKeeper 一致性，Leader选举讲到 ZAB 协议与 PAXOS 算法（下）

一、ZooKeeper集群保证数据一致性
    （一）一致性
    （二）zookeeper保证数据一致性的协议
二、Zookeeper集群Leader选举
    （一）ZooKeeper集群中三种类型的节点
    （二）ZAB 中的节点有四种状态
    （三）Leader选举过程
三、ZAB协议
    （一）ZAB 协议 ZXID 是如何生成的
    （二）ZAB协议——崩溃恢复模式
    （三）ZAB协议——消息广播模式
四、Paxos算法
    （一）关于ZAB协议中Leader的单点问题
    （二）Paxos是什么
    （三）问题背景
    （四）相关概念
    （五）Paxos算法处理过程
    （六）总结：Paxos算法

一文通吃：从 ZooKeeper 一致性，Leader选举讲到 ZAB 协议与 PAXOS 算法（上）_慕课手记 (imooc.com)

上篇文章，我们介绍了ZooKeeper集群保证数据一致性和Zookeeper集群Leader选举，这边文章我们接着介绍ZAB协议和Paxos算法

ZAB协议

在ZooKeeper在处理事务型请求的时候有提到一个协议，就是ZAB协议，然后在Leader选举时，ZooKeeper也是基于这个协议来进行实现的。所以实际上在整个ZooKeeper集群模式里面，这个ZAB协议是非常重要的。

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。ZAB协议是为分布式协调服务 ZooKeeper 专门设计的一种支持 崩溃恢复和原子广播协议，这里需要注意，它并不是通用的分布式一致性算法，而是ZooKeeper 自己量身定制的，这样的好处就是它相对来说比较简单，没那么复杂，而且跟 ZooKeeper 完美契合。

ZAB 协议 ZXID 是如何生成的

基于这个协议，ZooKeeper 实现了各个副本之间数据一致性，并且集群初始化的时候，或者主节点发生故障的话，需要通过这个协议来选举Leader节点，这里我们来看一下这个问题：

数据一致性的保证和选举Leader节点都是非常依赖事务ID的，在ZAB协议里面叫做 ZXID ，那么这个 ZXID 是如何设计的？它是不是只是一个单纯的从小到大递增的过程？

那么我们结合这个问题来看一下这个 ZXID 是如何生成的

在 ZAB 协议的事务编号 ZXID 设计中，ZXID 是一个 64 位的数字，其中：

低 32 位：可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader 都会产生一个新的事务 Proposal 并对该计数器进行 + 1 操作。
高 32 位：则代表了 Leader 服务器上取出本地日志中最大事务 Proposal 的 ZXID，并从该 ZXID 中解析出对应的 epoch 值，然后再对这个值加一。

高 32 位代表了每代 Leader 的唯一性，低 32 代表了每代 Leader 中事务的唯一性。同时，也能让 Follwer 通过高 32 位识别不同的 Leader。

基于这样的策略，当一个包含了上一个Leader周期中尚未提交过的事务Proposal的服务器启动加入到集群中，发现此时集群中已经存在leader,将自身以Follower角色连接上Leader服务器之后，Leader服务器会根据自己服务器上最后被提交的Proposal来和Follower服务器的Proposali进行比对，发现follower中有上一个leader)周期的事务Proposal时，Leader会要求Follower进行一个回退操作（回退到一个确实已经被集群中过半机器提交的最新的事务Proposal.)。

ZAB协议——崩溃恢复模式

当整个集群启动过程中，或者当 Leader 服务器出现网络中弄断、崩溃退出或重启等异常时，Zab协议就会进入崩溃恢复模式，选举产生新的Leader。

一但出现崩溃，会导致数据不一致，ZAB的崩溃恢复开始起作用。有如下两个确保：

ZAB协议需要确保已经在Leader提交的事务最终被所有服务器提交。
ZAB协议需要确保丢弃只在Leader服务器上被提出的事务。

针对上两个要求，如果Leader选举算法保证新选举出来的Leader服务器拥有集群中所有机器最高编号（ZXID最大）的事务Proposal，那么就能保证新的Leader 一定具有已提交的所有提案，更重要是，如果这么做，可以省去Leader服务器检查Proposal的提交和丢弃工作的这一步。

一旦Leader服务器出现崩溃，或者说网络原因导致Leader服务器失去了与过半的Follower的联系，那么就会进入崩溃恢复模式。为了保证程序的正常运行，整个恢复过程后需要选举一个新的Leader服务器。因此，ZAB协议需要一个高效可靠的Leader选举算法，从而确保能够快速的选举出新的Leader。同时，新的Leader选举算法不仅仅需要让Leader自己知道其自身已经被选举为Leader，同时还需要让集群中所有的其它机器也能够快速的感知选举产生的新的Leader服务器。

ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功，那么应该在所有的机器上都被处理成功，哪怕机器出现崩溃。

ZAB协议——消息广播模式

当新的Leader出来了，同时，已有过半机器完成同步之后，ZAB协议将退出恢复模式。进入消息广播模式。这时，如果有一台遵守Zab协议的服务器加入集群，因为此时集群中已经存在一个Leader服务器在广播消息，那么该新加入的服务器自动进入恢复模式：找到Leader服务器，并且完成数据同步。同步完成后，作为新的Follower一起参与到消息广播流程中。

如果集群中其它机器收到客户端事务请求后，那么会先转发Leader服务器，由Leader统一处理。

在zookeeper集群中，数据副本的传递策略就是采用消息广播模式。zookeeper中数据副本的同步方式与二段提交相似，但是却又不同。二段提交要求协调者必须等到所有的参与者全部反馈ACK确认消息后，再发送commit消息。要求所有的参与者要么全部成功，要么全部失败。二段提交会产生严重的阻塞问题。
Zab协议中 Leader 等待 Follower 的ACK反馈消息是指“只要半数以上的Follower成功反馈即可，不需要收到全部Follower反馈”
整个过程中，Leader为每个事务请求生产对应的Proposal，在广播前，为这个事务分配一个全局唯一ID，为ZXID（事务ID），必须按照递增的事务顺序进行处理。

ZAB协议中涉及的二阶段提交和2pc有所不同。在ZAB协议的二阶段提交过程中，移除了中断逻辑，所有Follower服务器要么正常反馈Leader提出的事务Proposal，要么就抛弃Leader服务器。ZAB协议中，只要集群中过半的服务器已经反馈ACK，就开始提交事务了，不需要等待集群中所有的服务器都反馈响应。这种模型是无法处理Leader服务器崩溃退出而带来的数据不一致问题的，因此在ZAB协议中添加了另一个模式，即采用崩溃恢复模式来解决这个问题。此外，整个消息广播协议是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易保证消息广播过程中消息接受与发送的顺序性。

在整个消息广播过程中，Leader服务器会为每个事务请求生成对应的Proposal来进行广播，并且在广播事务Proposal之前，Leader服务器会首先为这个事务分配一个全局单调递增的唯一ID，我们称之为事务ID（即ZXID）。由于ZAB协议需要保证每一个消息严格的因果关系，因此必须将每一个事务Proposal按照其ZXID的先后顺序来进行排序与处理。

在消息广播过程中，Leader服务器会为每一个Follower服务器各自分配一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列中，并且根据FIFO策略进行消息发送。每一个Follower服务器在接受到这个事务Proposal之后，都会首先将其以事务日志的形式写入到本地磁盘中去，并且在成功写入后反馈给Leader服务器一个ACK响应。当Leader服务器接收到超过半数Follower的ACK响应后，就会广播一个Commit消息给所有Follower服务器以通知其将事务进行提交，同时Leader自身也会完成事务的提交，而每一个Follower服务器收到Commit消息之后，也会完成对事务的提交。

小结：

ZAB的两种基本模式？

崩溃恢复：在正常情况下运行非常良好，一旦Leader出现崩溃或者由于网络原因导致Leader服务器失去了与过半Follower的联系，那么就会进入崩溃恢复模式。为了程序的正确运行，整个恢复过程后需要选举出一个新的Leader,因此需要一个高效可靠的选举方法快速选举出一个Leader。
消息广播：类似一个两阶段提交过程，针对客户端的事务请求， Leader服务器会为其生成对应的事务Proposal,并将其发送给集群中的其余所有机器，再分别收集各自的选票，最后进行事务提交。

哪些情况会导致ZAB进入恢复模式并选取新的Leader?

启动过程或Leader出现网络中断、崩溃退出与重启等异常情况时。

当选举出新的Leader后，同时集群中已有过半的机器与该Leader服务器完成了状态同步之后,ZAB就会退出恢复模式。

Paxos算法

关于ZAB协议中Leader的单点问题

我们已经学习了ZooKeeper的ZAB协议，我们知道了这个协议，它是根据ZooKeeper自身的功能特点，去实现的一致性协议，通过这个协议可以保证ZooKeeper集群它的数据写操作可以有序地进行，从而能够保证集群节点间的数据同步时保证一致性。然后在这个过程中，Zookeeper集群的Leader节点，其中着重要作用，所有的写操作都需要经过它来进行处理、协调。这样的好处就是多个节点之间的数据同步处理起来比较简单，我们可以反过来想一下，假如，它不是这种方式的话，就是不止一个节点来处理写请求的话，那它同步数据的时候会有什么困难呢？

我们假设有5个节点，server 1 ～ server 5，它们的初始值都是0，现在我们假设这个集群节点没有Leader节点，或者说我们这个集群有多个节点可以处理写请求，我们这里假设server 5和server 2都可以处理写请求。

现在我们假设Client1 向server 5发现写请求，把v=0改为v=1，同时Client2也发起写请求，将v=0改v=2，那么这个时候同步会出现什么问题呢？如下图，我们会发现写顺序无法得到保障，由于网络问题，节点再进行数据同步的时候存在先后，导致有的先接收到v=1，再接收到v=2，但有的节点又是先接收v=2再接收v=1，由于server 5 和server 2之间没有任何“协作”，这样就会导致集群各个节点最终的状态不一样，一致性不能得到保障。

所以ZooKeep的里面，就是通过引入一个Leader节点，来协调不同的写请求。这样就能在这个节点的保证写操作的有序性，以及同步的有序性，最终保证集群同步之后所有节点数据是一致的。

如图由于Leader的存在，Client1和Client2的操作都转发到Leader统一进行处理。那么Leader就可以控制这两个操作的先后，以及得到每一个操作数据同步的结果情况。这样，假如Client1优先被执行，那么Leader节点就会首先应用v=1，然后把v=1同步到各个节点，然后再处理Clinet2的操作，这样就不会出现数据不一致的问题。

那你可能会想，那就介入一个Leader角色不就万事大吉了吗？但是，你想想，Leader模式可能会存在的问题？很明显可以想到：

Leader单个节点负载过高
Leader存在单点故障的风险

那么鱼与熊掌，能否兼得？既可以不采用单个Leader的模式，避免单点问题，同时又能够解决前面我们说的，在写数据的时候，多个节点之间发生的数据不一致的情况。

那么答案其实是有的，这个就是另一个分布式一致性算法——Paxos

Paxos是什么

其实Paxos算法在整个分布式领域具有非常重要的地位，它的出现其实要比ZooKeeper更早一些，它是莱斯利·兰伯特（Leslie Lamport，此人在微软研究院）于1990年提出的一种基于消息传递的一致性算法。而ZooKeeper的ZAB协议其实也是基于Paxos去定制化改造的。所以相比较而言，Paxos是更加通用的，更具普遍性的分布式一致性算法，而它的目标，就是解决分布式系统如何就某个值（决议）达成一致这样一个问题。

问题背景

典型的场景就像我们刚才分析的那个场景，如何去保证，我们多个写操作的数据同步到整个集群的时候，能够保证一致。这个算法就是可以去解决这样一个问题。

这里的核心思想是这样的，就是多个写操作就是对应多个命令，然后我们要保证每个节点一致的话，可以把问题转换这样，就是让这些节点，它们去执行这些命令的时候，顺序都是一致的，这样达到的最终效果就能够让各个节点的数据保持一致。所以每当集群的节点接收到一个写请求的时候，它不像ZooKeeper一样直接交给大佬去处理，而是向集群的其它节点发起协商，让这些有决策权的节点一起参与决议，来决定这个请求能不能够现在受理，然后大家就一起投票表决，超过半数的话就说明通过决议。这个过程有点像我们前面在讲ZooKeeper的Leader选举，但细节还是不一样的，接下来我们就来详细的学一下Paxos算法的运行流程

Paxos算法处理过程

好，接下来，我们就结合前面的场景，还有刚才对Paxos的解析，我们结合一个案例场景来看一下这个过程

我们还是按照前面集群5个节点的例子来进行讲解，对应到右边，我们可以看到这个集群节点有两个Proposer和三个Acceptor，那么对这两个节点来说，它们就可以去接收这个写操作。然后接收到之后，接下来呢就会去向这个Acceptor来做一个询问和协商。那么协商完之后就会去应用这个写操作。

那么整一个场景就是这样子，我们逐步来看一下。这里呢我们把这个图形转换一下。那么整一个过程我们可以把它理解为就是一个两阶段的一个处理过程。然后首先第一阶段就是我们这里可以看到，对于这个Proposer它首先就会来向三个Acceptor来发起这个Propose请求是吧，然后发起这个请求的时候同时。会带上一个编号，这里呢这个编号就是100。

那么这个呢就是第一步。好，然后接下来这三个Acceptor接收到这个report请求之后，那么这个时候呢它们就会记录下当前这个编号是100，然后因为当前这三个Acceptor暂时呢就是还没有接收过其它的这个请求。(暂时没有接受过其它的提议)那么就是三个Acceptor就会做这样一个回应，告诉这个Proposer没有接受过其它的这个提议。

好，然后接下来第三步，这个时候呢这个Proposer一接收到这个前面的这个响应之后，那这个时候它就可以来发起这个第二阶段的一个请求。那么第二阶段的请求呢就是一个Accept的一个请求，(对应到前面说到的提案)。那么这里我们可以看到就是这个Accept这个请求里面就是会有这个编号100，同时呢还会有这个提案的内容（v=1）.
对于这三个请求，它们的这个情况会有一点不一样。
那么首先就是发到这个Accept1这里，它是能够正常到达，然后就是发到另外两个Acceptor的这个请求，因为这个网络的问题，暂时就还没有到达。所以呢我们这里通过虚线表示这两个请求暂时没有到达这个两个Acceptor的节点。

好，然后接着这个时候呢这个Proposer2它同样接收到一个写请求，这个时候同样就会来发起一个prepaper的一个请求。就像前面这个Proposer1一样，它首先就是会来发起这个第一阶段的一个请求，然后它这个时候呢会带上一个编号是（101），就是在前面的基础上会来做一个加一操作。那么针对这个prepaper（101），我们可以看到这里有三个请求，然后同样的就是有的请求到达了这个Acceptor1节点，有的还没有是吧？那么我们可以看到就是Acceptor1还有Acceptor3，它们这两个收到了这个prepaper（101）请求，那么这个时候它们会发生什么情况呢？我们可以先想一下。
然后这里我们再注意一下，就是对这个Acceptor1，因为它前面我们可以看到前面它是这个Accept请就是已经到达这个Acceptor1了所以呢这个时候它就可以去向这个Proposer1做这个响应。因为它第一阶段接收到prepaper的编号是100然后，第二阶段接收到的这个Accept请求编号也是100，所以呢这个编号是对得上的。这个时候呢它就可以去把前面的这个提案的内容v=1给应用到当前的这个节点上面来。所以呢我们这里可以看到，现在这个Acceptor1上面这个v它是已经等于1了，然后它就响应给这个Proposer1。这个时候Proposer1，就收到了这个一票的响应。

好，然后我们接着往下看，我们来看一下这个对于这个prepaper（101）这个请求，它到达两个Acceptor节点之后，它会发生什么情况。那么这里我们可以看到就是对这个Acceptor1还有这个Acceptor3，它们这两个节点接收到这个prepaper（101）之后，它们的情况会有一点不一样。
Acceptor3它的一个处理
那么首先我们来看一下这个Acceptor3，因为前面它是没有接收到这个Accept(100,1)的这个提案的。所以呢这个时候它的这个值是零，并且id是100。当它接收到这个prepaper（101）之后，这个时候呢因为这个id的编号前面是100，然后现在呢又是101，所以呢很明显这个101是大于100的。并且由于这个Acceptor3它还没有响应过这个提案，所以呢现在这个Acceptor3它首先就会把这个id改为这个101，因为这个101它现在是这个最大的编号。同时它会去告诉这个Proposer2说我现在还没有接受过其它的提案，你可以来发起这个提案。
Acceptor1它的一个处理
然后我们看左边这个Acceptor1，那这个Acceptor1就有点不一样了。因为前面呢它已经接受过这个propose这个提案，所以呢这个时候它除了去把这个编号就是这个id从100改为101之外，同时会去告诉这个Proposer2，说我前面已经接受过另外一个提案，然后它提案的内容是v=1。
所以呢对于这个Proposer2来说，它现在就会去学习到这样一个提案的内容，就是v=1。那么对这个Proposer2来说，它后面在进行第二阶段处理的时候，它就会把这个v=1作为提案的内容发出来。这就是我们前面提到的这个学习提案的过程。

好，然后接着我们继续再来往下看。这个时候呢对于这个Proposer1它发起的这个提案，它现在就到达了Acceptor2，Acceptor3这两个节点。那么到达这两个节点的时候，我们可以看到它这个提案发过来的时候编号是100，然后这个时候这个Acceptor2它的这个id是100，但是这个Acceptor3因为它前面已经接受过这个Proposer2的一个请求，所以呢它这个时候它的id已经是101。
那么我们来看一下这个时候会发生什么情况。那么这里我们可以看到，对于这个Acceptor2来说，它现在就能够去接受这个propose的提案，是吧？因为这个编号是对得上的，那么它就会去告诉这个Proposer1它接受了这个提案。
那么到目前为止呢，这个Proposer1就接收到了这个Acceptor1还有Acceptor2这两个响应的这个提案，就是通过了这个半数以上的这个Acceptor的一个决议，是吧。
所以呢到目前为止，这个Proposer1它现在上面的这个值它就可以变成1了。因为它的这个提案呢已经通过超过半数的Acceptor的表决是吧。然后我们再来看一下，对于这个Acceptor3来说，因为这个100它是小于101的，所以呢对于Proposer1。它发起的这个提案到达节点上的时候，它现在因为这个编号已经小于节点上上面的这个编号，所以呢这个时候它这个提案会被节点上拒绝。那么这个时候呢对于这个节点上来说，它上面的这个v还是0，因为它把这个提案给拒绝回去了。但是呢这个拒绝它并不影响这个Proposer1，它上面的值变为1，是吧？因为它已经通过了半数以上的这个Acceptor的一个表决。
好，然后我们再来看一下这个Acceptor2。这个时候呢它才接收到前面这个。Proposer2它发起的这个prepaper（101）这个请求。那么根据我们前面的分析，这个时候呢这个101它是100。好，那么它就可以去接收这个prepaper（101）。然后因为这个Acceptor2这个时候呢它已经接受过这个Proposer1的这个提案，是吧？所以呢它同样会把这个v=1这样的一个提案内容告诉这个Proposer2。那么这里同样是一个学习提案的一个过程。就是这个Acceptor2会把这个v=1这样一个提案内容响应给这个Proposer2。然后我们接着再来往下看。这个时候呢对于这个Proposer2来说，他前面已经得到这三个Acceptor的响应，就是在第一阶段prepaper请求的时候，已经接收到这三个Acceptor的响应，并且这个Proposer2他从这个Acceptor1还有从这个Acceptor2，从他们这两个节点都学习到了这样一个新的提案，就是v=1。

所以呢在最后一步就是发起这个提案这一步他会把这个提案内容就是v=1，放到他的提案内容里面，然后去向三个Acceptor节点，还发起这个Accept请求。
这里我们可以看到就是三个Accept请求，它的编号呢是101，然后它的值是等于1，就是他从前面的这个学习过程中得到的一个提案内容。那么现在对于这个Acceptor3来说，这个编号呢现在就是101能够匹配上，然后这个时候呢他就可以把这个提案内容给应用到这个节点上面。所以呢这个时候我们可以看到，这个节点上它的值呢也是变为了这个1。
那么这个就是Paxos 算法它在这个场景下它的一个处理过程。

总结：Paxos算法

① Proposer生成提案

1、Proposer选择一个新的提案，编号N
2、向半数以上的Acceptor发送请求：Prepare(N)
3、Acceptor接受之后做出如下响应之后：
  a. Acceptor不再接受任何编号小于N的提案
  b. 如果Acceptor已经接受过提案，则向Proposer响应已经接受过的编号小于N的最大编号的提案
4. 如果Proposer收到了半数以上的Acceptor的响应，那么它就可以生成编号为N，值为V的提案[N,V]，并且向Acceptor发送请求：Accept(N, V)

//这里的V是所有的响应中，编号最大的提案的值，如果所有的响应中都没有提案，此时V就可以由Proposer自己决定

② Acceptor决策提案

1、Acceptor可以接受Prepare和Accept请求
2、并且，它可以选择忽略请求，而不影响算法安全性
3、对于这两种请求，Acceptor这样决策：
  a. 对于Prepare(N)，且N大于该Acceptor已经响应过的所有Prepare请求编号，它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor不再接受编号小于N的提案
  b. 对于Accept(N, V)，且N大于该Acceptor已经响应过的所有Prepare请求编号，它就接受该提案
4、Acceptor只需记住：编号最大的请求和编号最大的提案

③Paxos算法描述

Paxos算法分为两个阶段。具体如下：

阶段一：
(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
(b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
阶段二：
(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

以上就是文章全部内容，谢谢阅读。