Zookeeper(1) - 理论基础

一、概述

相比单体应用而言分布式应用（因系统的范围比较大，所以笔者习惯使用“应用”这个概念，下文同）具有分布性、对等性、并发性等特点。同样也需要解决缺少全局时钟、通信异常、脑裂（分区异常）、三态（成功、失败、超时）、节点故障等问题；

其中最重要的就是数据一致性问题。分布式一致性一般分为强一致性、弱一致性和最终一致性三种模式，最常被应用的是弱一致性和最终一致性这两种模式（最终一致性是弱一致性的一种特例，强调在限定的时间内数据达到最终一致性），弱一致性又可细分为会话一致性和用户一致性。还有一种是以牺牲性能为代价的设计，可初步认为是极限情况下的弱一致性的一种体现。

zookeeper（以下简称zk）是一个典型的分布式数据一致性的解决方案，分布式应用程序可以基于zk实现数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、master选举、分布式锁和分布式队列等。zk提供了一个类似于 Linux 文件系统的树形结构（可认为是轻量级的内存文件系统，但只适合存少量信息不适合存储大量文件或者大文件），为保证可用性同时提供了节点监控与通知机制。

zk是数据弱一致性的一种实现，通过“长”连接的方式实现了性能和数据实时的均衡，进而达到一种准实时的效果。这里的长连接是介于传统长连
 接和定时轮询的一种优化方案。有兴趣的小伙伴可以网上查查各个配置数据库的实现机制。

整体构架如下图所示：

1.1、zk提供的一致性特性

顺序一致性：从同一个客户端发起的事务请求，最终将会严格地按照其发起顺序被应用到zk中，这是由zxid编号这个设计来决定的；
原子性：所有事务的请求结果在整个集群中所有机器上的应用情况是一致的，也就是说要么在整个集群中所有机器上都成功应用了某一个事务要么都没有应用，没有中间状态；
单一视图：无论客户端连接的是哪个zk服务器，其看到的服务端数据模型都是一致的；
可靠性：一旦服务端成功应用了一个事务，并完成对客户端的响应，那么该事务所引起的服务端状态变更将会被一直保留下来，除非有另一个事务又对其进行了变更；
准实时性：zk仅仅保证在一定的时间内，客户端最终一定能够从服务端上读到最终的数据状态；

1.2、zk应用场景

这里只简单描述下通用的场景，后续会详细补充下各个场景的详细设计。通常zk可被用于以下几类软件设计中：

数据共享/同步：通过一个共享的、树型结构的名字空间来进行相互协调；
构建集群：zk使得分布式程序能够通过一个共享的树形结构的名字空间来进行相互协调，即zk服务器内存中的数据模型由一系列被称为ZNode的数据节点组成，将全量的数据存储在内存中，以此来提高服务器吞吐减少延迟；
顺序访问：对于客户端的每个写请求，zk都会分配一个全局唯一的递增编号，这个编号反映了所有事务操作的先后顺序；
高性能：将全量数据存储在内存中直接服务于客户端的所有非事务请求，因此它尤其适用于以读操作为主的应用场景；

1.3、ACID设计模型

1.3.1、CAP模型

CAP模型：（C可用性、A一致性、P分区容错）：CAP可以想像成一个三角形的三条边，在保持三角形面积不变的前提下，最多只能延迟两条边，即在设计时一般会选择两项，比如放弃P意味着放弃了扩展性。

在实际应用中通常都会放弃C，放弃C实际是放弃强一致性采用最终一致性的做法；以实际效果而言，P相当于对通信的时限要求，系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，如果情况比较严重就需要在C和A之间做出选择。以此类推，根据应用的实际情况适当调整CAP使应用达到理想的运行状态。

1.3.2、BASE模型

BASE模型：（基本可用、柔性状态、最终一致性）：基本可用是指降低性能或放弃边缘服务保主流程的做法，比如降级限流，软状态指允许数据存在中间状态，但这个中间状态不能影响系统的整体可用性，允许数据同步过程中存在延时。最终一致性强调的是所有副本在一定时间后达到完全同步的状态。柔性事务按技术实现可分为两阶段型、补偿型、异步确保型、最大努力通知型四种设计。其中两阶段就是通常所说的XA\JTA/JTA的技术实现。另外在一些大型系统中通常会引入TCC（try/catch/cancel）型事务来确保数据的最终一致性。

为了更好的理解base模型，以WS-BusinessActivity为例，这个框架提供了一种基于补偿的long-running的事务处理模型。服务器 A 发起事务，服务器 B 参与事务，服务器 A 的事务如果执行顺利，那么事务 A 就先行提交，如果事务 B 也执行顺利，则事务 B 也提交，整个事务就算完成。但是如果事务 B 执行失败，事务 B 本身回滚，这时事务 A 已经被提交，所以需要执行一个补偿操作，将已经提交的事务 A 执行的操作作反操作，恢复到未执行前事务 A 的状态。这样的 SAGA 事务模型，是牺牲了一定的隔离性和一致性的，但是提高了 long-running 事务的可用性。

异步确保型在长尾的分布式系统中比较常用，比如退款流程，按全链路来讲一个退款流程可能包括订单、仓储、物流、财务等节点，在pop模式中还包含人工审核流程。假想上述各节点如果出错就需要买家重新提交申请，那用户体验就会非常糟糕甚至会得到工商投诉。所以在这样的应用中采用异步补偿的方式来确保流程的正常执行是非常合适不过的，技术上一般会采用mq来实现异步操作。其本质就是通过将一系列同步的事务操作变为基于消息执行的异步操作, 避免了分布式事务中的同步阻塞操作的影响。概要设计如下：

Base可以参考笔者的另一篇文章 https://blog.51cto.com/arch/5295170 里面对异常的设计的实现

二、安装

笔者使用的是mac系统，所以下面的安装都是基于mac来操作的。

2.1、Homebrew安装

//安装：安装后的路径为/usr/local/Cellar
brew install zookeeper

//启动：进入到/usr/local/Cellar/zookeeper/3.7.0_1/bin目录下启动zookeeper
./zkServer start

./zkServer {start|start-foreground|stop|restart|status|upgrade|print-cmd}

2.2、Docker安装

需提前安装docker desktop软件，安装成功后进入到docker容器后如下图所示：

docker pull zookeeper //最新版本应该是3.8.0

2.3、zoo.cfg基础配置

先了解下基础的配置，详细的配置会在后续章节再描述，首先打开zoo.cfg文件，修改后要重新启动zk。

tickTime=2000 会话超时时间
initLimit=10 集群节点同步时间
syncLimit=5 集群主节点与从节点发送消息的请求和应答时间
dataDir=/usr/local/var/run/zookeeper/data/zk1 存储快照文件snapshot的目录
dataLogDir=/usr/local/zookeeper/dataLogDir/zk1 快日志文件，不配置会生成在dataDir文件夹下
clientPort=2182
server.1=127.0.0.1:2888:3888 右边可以配置两个端口，第一个端口用于F和L之间的数据同步，第二个端口用于Leader选举过程中投票通信，单机可不配置
touch myid.pid 在%dataDir%下创建myid.pid文件，内容为上面配置中server.后面的数字（此值1~255）
//server.1=127.0.0.1:2888:3888,这行也可以配置多个虚拟的，比如server.1=127.0.0.1:2888:3881 server.2=127.0.0.1:2889:3882 server.3=127.0.0.1:2887:3883

三、基本概念

3.1、集群

实际应用中zk都以集群的方式部署的。被实现为一个基于主从复制的高可用集群，即master/slave模式。通常在主从模式中把所有能够处理写操作的机器称为master节点，把所有通过异步/同步复制方式获取最新数据并提供读服务的机器为slave节点。

在zk中引入了leader、follower、observer三种角色，集群中的所有节点通过leader选举来选定一台被称为leader的机器并为客户端提供写服务（leader同一时间只有一个节点），follower和observer提供读服务（不同的是observer不参与leader选举和写操作的"过半写成功"策略）。

leader：是整个集群工作机制中的核心，一个zk集群同一时间只会有一个实际工作的leader，它会发起并维护与各 follower及observer间的心跳，主要职责是：

事务请求的唯一调度和处理者，保证集群事务处理的顺序性；
集群内部各服务器的调度者；

follower：跟随者，一个zk集群可能同时存在多个follower，它会响应leader 的心跳，主要职责是：

处理客户端的非事务请求，转发事务请求给leader服务器；
参与事务请求proposal的投票；
参与leader选举投票；

observer：加入更多的Observer 节点，可提高伸缩性，同时不影响吞吐率。

和follower唯一的区别在于，observer服务器只提供非事务服务不参与任何形式的投票，包括事务请求proposal的投票和leader选举投票，引入observer的目的是可以在不影响写性能的情况下提升集群的读性能；

3.2、会话

这里的会话专指指客户端会话，是指客户端和服务端之间的一个TCP长连接。zk对外的服务端口默认为2181，客户端启动的时候，首先会与服务器建立一个TCP连接，从第一次连接建立开始客户端会话的生命周期也开始了，通过这个连接客户端能够心跳检测保持与服务器间会话的有效性、向zk服务器发送请求并接受响应、接受来自服务器的Watch事件通知。

3.3、节点

zk将所有数据存储在内存中，数据模型是一棵树由斜杠/进行分割的路径（如/foo/path1）。每个zNode都会保存自己的数据内存，同时还会保存一些属性信息。zNode分为持久节点和临时节点两类，持久节点是指一旦这个zNode被创建了将一直保存在zk集群中除非主动进行zNode的移除操作，而临时节点的生命周期和客户端会话绑定，一旦客户端会话失效那么这个客户端创建的所有临时节点都会被移除。

另外，zk还允许用户为每个节点添加一个特殊的属性“SEQUENTIAL”，一旦节点被标记那么在这个节点被创建的时候，zk会自动在其节点后面追加一个整形数字（由父节点维护的自增数字）。节点类型可在zoo.cfg文件中配置，详细如下：

• PERSISTENT:持久的节点；
• EPHEMERAL:暂时的节点；
• PERSISTENT_SEQUENTIAL:持久化顺序编号目录节点；
• EPHEMERAL_SEQUENTIAL:暂时化顺序编号目录节点；

3.4、版本

对于每个zNode，zk都会为其维护一个叫作Stat的数据结构，Stat记录了这个zNode的三个数据版本，分别是version（当前zNode的版本）、cversion（当前zNode子节点的版本）、aversion（当前zNode的ACL版本）。

3.5、Watcher

zk允许客户端在指定节点上注册一些Watcher事务，以便在一些特定事件触发的时候，zk服务端会将事件通知到感兴趣的客户端。

3.6、ACL策略

zk采用ACL（Access Control Lists）策略来进行权限控制，共定义了如下五种权限：

CREATE：创建子节点的权限；
READ：获取节点数据和子节点列表的权限；
WRITE：更新节点数据的权限；
DELETE：删除子节点的权限；
ADMIN：设置节点ACL的权限；

四、分布式一致性算法模型

插入此节的目的是同大家一起回顾下分布式一致性的两种设计思想，我们常用的一些中间件、数据库基本全是采用了这两类模型的设计。

4.1、2PC

二阶段提交，数据库采用的模型。两个阶段的执行是一个串行的过程，由一个协调者协调各参与者。在分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时为了保持事务的 ACID 特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交（比如将更新后的数据写入磁盘）。

二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作，详细执行过程如下：

阶段一，事务询问

事务询问：协调者向所有参与者发送事务内容，等待参与者回应；
执行事务：参与者执行事务，记录Undo和Redo日志；
反馈事务询问响应：参与者返回给协调者Yes或No响应。当所有参与者全部返回Yes，进入提交事务阶段；存在No返回或者超时时会进入中断事务阶段；

阶段二，事务提交

发送事务提交请求；
各个参与者提交事务；
参与者反馈事务提交结果；
如果参与者全部返回Yes，完成事务；存在返回No，进入中断事务阶段；

中断事务阶段

发送回滚请求；
事务回滚；
反馈事务回滚结果；
完成中断事务；

2PC的缺点：

同步阻塞：各个参与者在等待其他参与者响应的同时，无法进行任何操作，处于阻塞状态；

单点问题：过度依赖协调者，一旦协调者出现问题，系统将无法正常运转；

脑裂问题：一旦协调者出现问题，比如当协调者向参与者发送 commit 请求之后，发生了局部网络异常或者在发送请求过程中协调者发生了故障，导致只有一部分参与者接受到了commit请求，这时便出现了数据部一致性的现象；

状态不确定：极限情况下当协调者发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

4.1、3PC

三阶段提交，在2PC的两个阶段中间插入了一个准备阶段，速个事务分为：第一阶段询问、第二阶段预处理、第三阶段处理。总结来看相比2PC主要有两个改动点。 1、同时在协调者和参与者中都引入超时机制；2、在第一阶段和第二阶段中插入一个准备阶段，保证了在最后提交阶段之前各参与节点的状态是一致的，另外在某此设计中如果第二阶段出现了问题，整个事务还是有一定的概率会进入第三阶段以此来增加应用的可用性，甚至可挂载纠正系统；

阶段一，CanCommit，事务询问

事务询问，询问各个参与者能否完成事务；
各个参与者返回响应，全部返回Yes，进入PreCommit阶段；

阶段二，PreCommit，事务预提交

发送预提交请求；
事务预提交：参与者执行事务操作，记录Undo和Redo日志；
参与者返回响应：全部返回Yes，继续三阶段；返回No，进入中断事务阶段；

阶段三，DoCommit，真正的事务提交

发送提交请求；
参与者正式执行事务提交操作；
返回协调者事务执行结果；
协调者完成事务：如果存在返回No或者返回超时，进入中断事务阶段；

中断事务阶段

回滚请求；
事务回滚；
反馈事务回滚结果；
完成中断事务；

3PC优缺点

优点是降低了阻塞范围，在等待超时后协调者或参与者会中断事务，避免了协调者单点问题，阶段3中协调者出现问题时，参与者会继续提交事务；

缺点是，引入preCommit阶段，在这个阶段如果出现网络分区，协调者无法与参与者正常通信，参与者依然会进行事务提交，造成数据不一致；

五、常见的算法实现

5.1、一致性Hash

一致性哈希算法(Consistent Hashing Algorithm)常用于负载均衡。比如Memcached client就是选择了这种算法，解决将 key-value 均匀分配到众多Memcached server上的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删节点的问题。一致性hash算法主要思想是环和虚拟节点，它具有以下特点：

平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用；
单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，当有新的缓冲加入到系统中时哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单求余算法 hash(object)%N 是做不到这一点的；
平滑性(Smoothness)：平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的；

5.1.1、实现原理

建构环形 hash 空间：通常的算法都是将 value 映射到一个32为的key值，也即是 0~2^32-1 次方的数值空间，我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环；
把需要缓存的内容（对象）映射到 hash 空间：比如 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布，差不多如上图所示；
把服务器（节点）映射到 hash 空间：即使用相同的 hash 算法将对象和 cache 都映射到同一个 hash 数值空间中，一般可以使用服务器(节点)机器的 IP 地址或者机器名作为 hash 输入；
把对象映射到服务节点：现在服务节点和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，首先确定对象 hash 值在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

考虑 cache 的变动，因为通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时，cache会失效，采用hash算法后当：

移除 cache：考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的对象。
添加 cache：再考虑添加一台新的 cache D 的情况，这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache 之间的对象，将这些对象重新映射到 cache D 上即可。

5.1.2、虚拟节点

hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念，它可以如下定义:

5.2、Paxos

Paxos 算法解决的是如何在一个分布式系统如何就某个值或决议达成一致问题。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

在Paxos中存在三种角色，分别为:

propose（提议者）：用来发出提案proposal， acceptor可以接受或拒绝提案，只要 Proposer 发出的提案被半数以上 acceptor 接受，proposer 就认为该提案里的value被选定了；
acceptor（接受者）：只要 Acceptor 接受了某个提案，acceptor 就认为该提案里的 value 被选定了；
learner(学习者）：学习被选定的提案，当提案被超过半数的acceptor接受后为被批准；

5.2.1、实现原理

第一阶段 prepare阶段（准leader确认）:

Proposer生成编号n并使用v作为value的提案(n, v)发送prepare请求给Acceptor中的大多数，一般是半数以上。
Acceptor收到prepare请求后，如果提案的编号大于它已经回复的所有prepare消息，则Acceptor将上次接收的提案和已接收的value回复给Proposer，并承若不再回复编号小于n的提案。如果Acceptor没有接收过prepare请求或收到的prepare请求的编号都比n小则回复该prepare请求。

第二阶段批准阶段（leader确认）:

当一个Proposer收到了多数Acceptor对prepare的回复后，就进入批准阶段。它要想回复prepare请求的Acceptor发送accept请求，包括编号n和上一阶段中返回的消息中的value。如果 Proposer 收到半数以上 Acceptor 对其发出的编号为n的 Prepare 请求的响应，那么它就会发送一个针对[N,V]提案的 Accept 请求给半数以上的 Acceptor。注意:V 就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定。
在不违背自己向其他Proposer的承诺的前提下，Acceptor收到accept请求后接收这个请求。

六、ZAB算法

zk并没有直接采用Paxos算法，而是采用了一种被称为ZAB(Zookeeper Atomic Broadcast) 的一致性协议作为其数据一致性的核心算法，也是半数同意算法的一种。ZAB协议是为Zookeeper专门设计的一种支持崩溃恢复的原子广播协议。

6.1、协议简述

所有事务请求必须由一个全局唯一的服务器来协调处理，称为leader服务器，而余下的其他服务器则成为follower服务器。leader服务器负责将一个客户端事务请求转换成一个事务proposal，并将该proposal分发给集群中所有的follower服务器。之后leader服务器需要等待所有follower服务器的反馈，一旦超过半数的follower服务器进行了正确的反馈后，那么leader就会再次向所有的follower服务器分发commit消息，要求其将前一个proposal进行提交。

ZAB协议需要确保那些已经在leader服务器上提交的事务最终被所有服务器都提交。如果让leader选举算法能够保证新选举出来的leader服务器拥有集群中所有机器最高编号（ZXID）的事务proposal，那么就可以保证这个新选举出来的leader一定具有所有已经提交的提案。

ZAB主要包括消息广播和崩溃恢复两个过程，在处理数据时分为三个阶段分别是：发现（Discovery）、同步（Synchronization）、广播（Broadcast），ZAB的每一个分布式进程会循环执行这三个阶段，称为主进程周期。每个进程都有可能处于如下三种状态之一：

LOOKING：Leader选举阶段；
FOLLOWING：Follower服务器和Leader服务器保持同步状态；
LEADING：Leader服务器作为主进程领导状态；

一个Follower只能和一个Leader保持同步，Leader进程和所有与所有的Follower进程之间都通过心跳检测机制来感知彼此的情况。若Leader能够在超时时间内正常收到心跳检测，那么Follower就会一直与该Leader保持连接，而如果在指定时间内Leader无法从过半的Follower进程那里接收到心跳检测或者TCP连接断开，那么Leader会放弃当前周期的领导，转换到LOOKING状态。

为了便于后述内容的描述，先了解两个术语：

6.1.1、epoch

可以理解为当前集群所处的年代或者周期，每个leader就像皇帝都有自己的年号，所以每次leader 变更之后都会在前一个年代的基础上加 1。这样就算旧的 leader 崩溃恢复之后也不会再起作用了，因为 follower 只听从当前年代的 leader 的命令。

6.1.2、zxid

全称是Transaction id，类似于 RDBMS 中的事务ID，用于标识一次更新操作的 Proposal(提议) ID。在 ZAB 协议的事务编号zxid设计中，zxid是一个 64 位的数字，其中低 32 位是一个简单的单调递增的计数器，针对客户端每一个事务请求计数器每次加1，采用自增设计的原因是为了保证事务的顺序性，高 32 位则代表 Leader 周期 epoch 的编号，每当选举产生一个新的 Leader 服务器时，就会从这个 Leader 服务器上取出其本地日志中最大事务的 ZXID，并从中读取 epoch 值，然后加 1，以此作为新的epoch，并将低 32 位从 0 开始计数。zxid(Transaction id)类似于 RDBMS 中的事务 ID，用于标识一次更新操作的 Proposal(提议) ID。

6.2、基本特性

ZAB协议需要确保已经在Leader服务器上提交的事务最终被所有服务器都提交；
ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务；
如果在崩溃恢复过程中出现一个需要被丢弃的提议，那么在崩溃恢复结束后需要跳过该事务Proposal；
ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功，那么应该在所有的机器上都被处理成功；

6.3、两种模式

6.3.1、崩溃恢复（选举）

当Leader服务器出现崩溃或者机器重启、集群中已经不存在过半的服务器与Leader服务器保持正常通信时，那么在重新开始新的一轮的原子广播事务操作之前，所有进程首先会使用崩溃恢复协议来使彼此到达一致状态，整个ZAB流程就会从消息广播模式进入到崩溃恢复模式。

进入恢复模式首选通过选举产生新的Leader服务器。当选举产生了新的Leader服务器同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议就会退出恢复模式，那么整个服务框架就可以进入消息广播模式。Leader选举算法不仅仅需要让Leader自身知道已经被选举为Leader，同时还需要让集群中的所有其他机器也能够快速地感知到选举产生的新的Leader服务器。

6.3.2、消息广播（数据同步）

ZAB协议的消息广播过程使用原子广播协议，类似于一个二阶段提交过程，针对客户端的事务请求Leader服务器会为其生成对应的事务Proposal，并将其发送给集群中其余所有的机器，然后再分别收集各自的选票，最后进行事务提交。

消息广播协议是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易保证消息广播过程中消息接受与发送的顺序性，借助以上技术在zk中每个事务Proposal按照其ZXID的先后顺序来进行排序和处理。在广播事务Proposal之前，Leader服务器会首先为这个事务Proposal分配一个全局单调递增的唯一zxid。

当一台同样遵守ZAB协议的服务器启动后加入到集群中，如果此时集群中已经存在一个Leader服务器在负责进行消息广播，那么加入的服务器就会自觉地进入数据恢复模式，先找到Leader所在的服务器并与其进行数据同步，然后一起参与到消息广播流程中。

6.4、四个阶段

整个过程简单来讲就是：发现选举产生PL(prospective leader)，PL收集Follower epoch(cepoch)，根据Follower的反馈，PL产生newepoch；然后PL补齐相比Follower多数派缺失的状态、之后各Follower再补齐相比PL缺失的状态，PL和Follower完成状态同步后PL变为正式Leader(established leader)。广播，Leader处理客户端的写操作，并将状态变更广播至Follower，Follower半数以上通过之后Leader发起将状态变更落地(deliver/commit)。

在正常运行过程中ZAB协议会一直运行上述过程进行消息广播流程，如果出现崩溃或其他原因导致Leader缺失那么此时ZAB协议会再次进入发现阶段，选举新的Leader。

6.4.1、Leader election(选举阶段-选举准Leader)

节点在一开始都处于选举阶段，只要有一个节点得到超半数节点的票数它就可以当选准 leader。只有到达广播阶段(broadcast) 准 leader 才会成为真正的 leader。这一阶段的目的是就是为了选出一个准 leader，然后进入下一个阶段。

6.4.2、Discovery(发现阶段-生成epoch)

在这个阶段followers 跟准 leader 进行通信，同步followers 最近接收的事务提议。这个一阶段的主要目的是发现当前大多数节点接收的最新提议，并且准 leader 生成新的 epoch，让 followers 接受，更新它们的 accepted Epoch。

6.4.3、Synchronization(同步阶段-follower副本)

同步阶段主要是利用 leader 前一阶段获得的最新提议历史，同步集群中所有的副本。只有当大多数节点都同步完成，准 leader 才会成为真正的 leader。 follower 只会接收 zxid 比自己的 lastZxid 大的提议。

6.4.4、Broadcast(广播阶段-leader消息广播)

到了这个阶段，zk集群才能正式对外提供事务服务，并且 leader 可以进行消息广播。同时如果有新的节点加入还需要对新节点进行同步。

6.5、Leader选举算法

原理简单来讲就每个server首先给自己投票，然后用自己的选票和其他 sever 选票对比权重大的胜出，使用权重较大的更新自身选票箱直到选举出唯一的一个server为止。在了解详细原理过程之前需要回顾几个术语：

epoch：代表一个Leader周期。每当一个新的leader做有一个唯一的epoch；
zxid：概念不再细说了只强调一点，每个leader都从0开始同时周期内zxid全局自增事务ID；SID: 对集群中的每一个server赋予一个id，标识着集群中的一台server不能重复；
quorum：过半机器数

选举过程（变更状态>投票>接收投票>处理投票>统计投票>变更状态），详细如下:

每个 server 询问其它的 server 要投票给谁。对于其他 server 的询问，server 每次根据自己的状态都回复自己推荐的 leader 的 id 和上一次处理事务的zxid；每次投票包含的最基本的元素为，所推举的服务器的myid和zxid，我们以(myid, zxid)的形式来表示；
收到所有 server 回复以后，就计算出 zxid 最大的哪个 server，并将这个 Server 相关信息设置成下一次要投票的 server；
计算这过程中获得票数最多的的 sever 为获胜者，如果获胜者的票数超过半数则改 server 被选为 leader。否则，继续这个过程，直到 leader 被选举出来；

举例说明，目前有 5 台服务器，每台服务器均没有数据，它们的编号分别是 1,2,3,4,5,按编号依次启动，它们的选择举过程如下:

1. 服务器 1 启动，给自己投票然后发投票信息，由于其它机器还没有启动所以它收不到反馈信息，服务器 1 的状态一直属于LOOKING；
2. 服务器 2 启动，给自己投票同时与之前启动的服务器 1 交换结果，由于服务器 2 的编号大所以服务器 2 胜出，但此时投票数没有大于半数，所以两个服务器的状态依然是 LOOKING；
3. 服务器 3 启动，给自己投票同时与之前启动的服务器 1,2 交换信息，由于服务器 3 的编 号最大所以服务器 3 胜出，此时投票数正好大于半数，所以服务器 3 成为领导者状态为LEADING，服务器 1,2 成为跟随者，状态为FOLLOWING;
4. 服务器 4 启动，给自己投票同时与之前启动的服务器 1,2,3 交换信息，尽管服务器 4 的编号大，但之前服务器 3 已经胜出，所以服务器 4 只能成为follower;
5. 服务器 5 启动，逻辑同服务器 4 成为follower;

七、ZAB与Paxos的异同

7.1、相同点

都存在一个类似于Leader进程的角色，由其负责协调多个Follower进程的运行；
Leader进程都会等待超过半数的Follower做出正确的反馈后才会将一个提议进行提交；
在ZAB协议中，每个Proposal中都包含了一个epoch值，用来代表当前的Leader周期，在Paxos算法中同样存在这样的一个标识，名字为Ballot。

7.2、区别

Paxos算法中，新选举产生的主进程会进行两个阶段的工作，第一阶段称为读阶段，新的主进程和其他进程通信来收集主进程提出的提议并将它们提交。第二阶段称为写阶段，当前主进程开始提出自己的提议；
ZAB协议在Paxos基础上添加了同步阶段，此时新的Leader会确保存在过半的Follower已经提交了之前的Leader周期中的所有事务Proposal；
ZAB协议主要用于构建一个高可用的分布式数据主备系统，而Paxos算法则用于构建一个分布式的一致性状态机系统；