1. Paxos 算法

对于 zk 理论的学习，最重要也是最难的知识点就是 Paxos 算法。

1.1 算法简介

Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的、具有高容错性的一致性算法。Google Chubby 的作者 Mike Burrows 说过，世上只有一种一致性算法，那就是 Paxos，所有其他一致性算法都是 Paxos 算法的不完整版。 Paxos 算法是一种公认的晦涩难懂的算法， 并且工程实现上也具有很大难度。较有名的 Paxos 工程实现有 Google Chubby、ZAB、 微信的 PhxPaxos 等。

Paxos 算法是用于解决什么问题的呢？ Paxos 算法要解决的问题是，在分布式系统中如何 就某个决议达成一致。

1.2 Paxos 与拜占庭将军问题

拜占庭将军问题是由 Paxos 算法作者莱斯利·兰伯特(Leslie Lamport)提出的点对点通信中的基本问题。该问题要说明的含义是，在不可靠信道上试图通过消息传递的方式达到一致性 是不可能的。所以， Paxos 算法的前提是不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传递的消息是不会被篡改的。

在实际工程实践中，可靠信道是存在的。

一般情况下，分布式系统中各个节点间采用两种通讯模型：共享内存（Shared Memory）、 消息传递（Messages Passing）。而 Paxos 是基于消息传递通讯模型的。

1.3 角色与一致性

三种角色

在 Paxos 算法中有三种角色，分别具有三种不同的行为。但很多时候，一个进程可能同 时充当着多种角色。

• Proposer： 提案（Proposal） 的提案者。在一个集群中，提案者可能存在多个，不同的提案者会提出不同的提案。
• Acceptor： 提案的表决者。即用于表决是否同步某提案。只有过半的 Acceptor 接受了某提案，该提案才会被认为是“选定了”。
• Learner： 提案的同步者。当提案被选定时，其要在本地执行该提案内容。

Paxos 算法执行前提条件

Paxos 算法执行的前提有以下几点：

• 每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、 递增的提案编号 N， 即在整个集群中是唯一的编号 N，然后将该编号赋予其要提出的提案。
• 每个表决者在 accept 某提案后，会将该提案的编号 N 记录在本地，这样每个表决者中 保存的已经被 accept 的提案中会存在一个编号最大的提案，其编号假设为 maxN。每个 表决者仅会 accept 编号大于自己本地 maxN 的提案。
• 在众多提案中最终只能有一个提案被选定。
• 一旦一个提案被选定，则其它服务器会主动同步(Learn)该提案到本地。
• 没有提案被提出则不会有提案被选定。

1.4 3PC 算法过程描述

Paxos 算法本身是不分阶段的，但在生产实现中具有 2PC 与 3PC 两种方案。

3PC 实现方案中，其执行过程划分为三个阶段：准备阶段 prepare、接受阶段 accept， 与提交阶段 commit。示意图如下：

image.png

prepare 阶段

• 提案者(Proposer)准备提交一个编号为 N 的提议，于是其首先向所有表决者(Acceptor)发送 prepare(N)请求， 用于试探集群是否支持该编号的提议。

• 每个表决者(Acceptor)中都保存着自己曾经 accept 过的提议中的最大编号 maxN。当一个表决者接收到其它主机发送来的 prepare(N)请求时，其会比较 N 与 maxN 的值。有以下几种情况：

  • 若 N 大于 maxN，则说明该提议是可以接受的，当前表决者会首先将该 N 记录下来，并将其曾经已经 accept 的编号最大的提案 Proposal(myid,maxN,value)反馈给提案者，以向提案者展示自己支持的提案意愿。其中第一个参数 myid 表示该提案的提案者标识 id，第二个参数表示其曾接受的提案的最大编号 maxN，第三个参数表示该提案的真正内容 value。当然，若当前表决者还未曾 accept 过任何提议，则会将Proposal(myid,null,null)反馈给提案者。
  • 若 N 小于等于 maxN，则说明该提议已过时，当前表决者采取不回应或回应 Error的方式来拒绝该 prepare 请求。

  注意，若 N 生成器为全局性生成器，则任何提案的编号都不可能相同，即 N 与 maxN 不可能相等。若 N 为各个参与者自行生成的，则可能会出现编号相同的提案，即 N 与 maxN 可能会相等。

accept 阶段

1. 当提案者(Proposer)发出 prepare(N)后，若收到了超过半数的表决者(Accepter)的反馈，那么该提案者就会将其真正的提案 Proposal(myid,N,value)发送给所有的表决者。
2. 当表决者(Acceptor)接收到提案者发送的 Proposal(N,value)提案后，会再次拿出自己曾经accept 过的提案中的最大编号 maxN，让 N 与它们进行比较， 若 N 大于等于 maxN，则当前表决者 accept 该提案，并反馈给提案者。若 N 小于 maxN，则表决者采取不回应或回应 Error 的方式来拒绝该提议。
3. 若提案者没有接收到超过半数的表决者的 accept 反馈，则有两种可能的结果产生。一是放弃该提案，不再提出；二是重新进入 prepare 阶段，递增提案号，重新提出 prepare请求。

commit 阶段

若提案者接收到的反馈数量超过了半数，则其会向外广播两类信息：

1. 向曾 accept 其提案的表决者发送“可执行数据同步信号”，即让它们执行其曾接收 到的提案；
2. 向未曾向其发送 accept 反馈的表决者发送“提案 + 可执行数据同步信号”，即让 它们接受到该提案后马上执行。

1.5 2PC 算法过程描述

2PC 与 3PC 的区别是，在提案者接收到超过半数的表决者对于 parepare 阶段的反馈后， 其会向所有表决者发送真正的提案 propsal。当表决者接受到 proposal 后就直接将其同步到了本地，不用再等待 commit 消息了。

那么，为什么不直接使用 2PC，而要使用 3PC 呢？是因为 2PC 中存在着较多的弊端。所 以很多 Paxos 工业实现使用的都是 3PC 提交。但 2PC 提交的效率要高于 3PC 提交，所以在保证不出问题的情况下，是可以使用 2PC 提交的。

1..6 Paxos 算法的活锁问题

前面所述的Paxos算法在实际工程应用过程中，根据不同的实际需求存在诸多不便之处， 所以也就出现了很多对于基本 Paxos 算法的优化算法，以对 Paxos 算法进行改进， 例如， Multi Paxos、 Fast Paxos、 EPaxos。

例如， Paxos 算法存在“活锁问题”， Fast Paxos 算法对 Paxos 算法进行了改进：只允许一个进程提交提案，即该进程具有对 N 的唯一操作权。该方式解决了“活锁”问题。

活锁指的是任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复“尝试—失败—尝试—失败”的过程。处于活锁的实体是在不断的改变状态，活锁有可能自行解开。

活锁与死锁的状态有着本质的区别：

• 活锁是一直在动，是活动状态。
• 死锁是系统阻塞，是不活动状态。

2. ZAB 协议

2.1 ZAB 协议简介

ZAB ， Zookeeper Atomic Broadcast， zk 原子消息广播协议，是专为 ZooKeeper 设计的一种支持崩溃恢复的原子广播协议，在 Zookeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性。

Zookeeper 使用一个单一主进程来接收并处理客户端的所有事务请求，即写请求。当服 务器数据的状态发生变更后，集群采用 ZAB 原子广播协议， 以事务提案 Proposal 的形式广播到所有的副本进程上。 ZAB 协议能够保证一个全局的变更序列，即可以为每一个事务分配一个全局的递增编号 xid。

当 Zookeeper 客户端连接到 Zookeeper 集群的一个节点后，若客户端提交的是读请求， 那么当前节点就直接根据自己保存的数据对其进行响应；如果是写请求且当前节点不是 Leader，那么节点就会将该写请求转发给 Leader， Leader 会以提案的方式广播该写操作，只要有超过半数节点同意该写操作，则该写操作请求就会被提交。然后 Leader 会再次广播给所有订阅者，即 Learner，通知它们同步数据。

image.png

2.2 ZAB 与 Paxos 的关系

ZAB 协议是 Paxos 算法的一种工业实现算法。 但两者的设计目标不太一样。 ZAB 协议主 要用于构建一个高可用的分布式数据主从系统，即 Follower 是 Leader 的从机， Leader 挂了，马上就可以选举出一个新的 Leader，但平时它们都对外提供服务。而 Fast Paxos 算法则是用于构建一个分布式一致性状态机系统，确保系统中各个节点的状态都是一致的。

2.3 三类角色

为了避免 Zookeeper 的单点问题， zk 也是以集群的形式出现的。 zk 集群中的角色主要有 以下三类：

• Leader： zk 集群事务请求的唯一处理者。当然，也可以处理读请求。
• Follower： 处理读请求，并向客户端返回结果；将事务请求转给 Leader；对 Leader 发起的决意具有表决权；同步 Leader 的事务处理结果； Leader 选举过程中的参与者（具有选举权与被选举权）。
• Observer：可以理解为在 Leader 选举过程中没有选举权与被选举权，也没有对决意的表决权的Flollower，其不属于法定人数范围，主要是为了协助 Follower 处理更多的读请求。其就相当于“临时工”，活没少干，但就是没有任何表决的权力。 增加 Observer 可以加强 zk 集群处理读操作的能力，但同时又不会增加提案表决的时长，也不会增加 Leader选举的时长。

这三类角色在不同的情况下又有一些不同的名称：

• Learner：学习者，同步者。其要从 Leader 中同步数据到本地。
  • Learner = Follower + Observer
• QuorumPeer：法定服务器。具有表决权、选举权的 Server。
  • QuorumPeer = Leader + Follower = Participant（参与者）

2.4 三个数据

在 ZAB 中有三个很重要的数据：

• zxid： 一个 64 位长度的 Long 类型，其中高 32 位表示纪元 epoch，低 32 位表示事务标识 xid。即 zxid 由两部分构成： epoch 与 xid。
• epoch：抽取自 zxid 中的高 32 位。每个 Leader 都会具有一个不同的 epoch 值，表示一个时期、时代、年号。每一次新的选举结束后都会生成一个新的 epoch，新的 Leader产生，则会更新所有 zkServer 的 zxid 中的 epoch。
• xid：抽取自 zxid 中的低 32 位。为 zk 的事务 id，每一个写操作都是一个事务，都会有一个 xid。 xid 为一个依次递增的流水号。

2.5 三种模式

ZAB 协议中对 zkServer 的状态描述有三种模式。这三种模式并没有十分明显的界线，它 们相互交织在一起。

• 恢复模式： 在集群启过程中，或在 Leader 崩溃后，系统都需要进入恢复模式，以恢复系统对外提供服务的能力。恢复模式主要包含两个阶段： Leader 选举与初始化同步。这两个阶段完成后 zk 集群恢复到了正常服务状态。
• 广播模式： 其分为两类：初始化广播与更新广播。
  • 初始化广播：leader刚选举成功，需要发广播通知其他服务器
  • 更新广播：提案通过后自己已经更新数据，然后通知其他服务器更新同步
• 同步模式： 其分为两类：初始化同步与更新同步。
  • 初始化同步：leader选举成功后初始化广播新的epoch，其他服务器接收到后可以从leader同步数据，即leader有自己没有的数据
  • 更新同步：leader提案通过后更新数据，然后发送更新广播，其他服务器接收到后更新该数据

2.6 四种状态

zk 集群中的每一台主机，在不同的阶段会处于不同的状态。每一台主机具有四种状态。

• LOOKING，选举状态(查找 Leader 的状态)。
• FOLLOWING， Follower 从 Leader 同步数据时的状态。 即 Follower 的正常工作状态。
• OBSERVING， Observer 从 Leader 同步数据时的状态。 即 Observer 的正常工作状态。
• LEADING， Leader 广播数据更新时的状态。 即 Leader 的正常工作状态。

2.7 同步模式与广播模式

初始化广播

前面我们说过，恢复模式具有两个阶段： Leader 选举与初始化同步(广播)。当完成 Leader选举后，此时的 Leader 还是一个准 Leader，其要经过初始化同步后才能变为真正的 Leader。

具体过程如下：

1. 为了保证 Leader 向 Learner 发送提案的有序， Leader 会为每一个 Learner 服务器准备一个队列
2. Leader 将那些没有被各个 Learner 同步的事务封装为 Proposal
3. Leader 将这些 Proposal 逐条发给各个 Learner，并在每一个 Proposal 后都紧跟一个COMMIT 消息，表示该事务已经被提交， Learner 可以直接接收并执行
4. Learner 接收来自于 Leader 的 Proposal，并将其更新到本地
5. 当 Learner 更新成功后，会向准 Leader 发送 ACK 信息
6. Leader 服务器在收到来自 Learner 的 ACK 后就会将该 Learner 加入到真正可用的 Follower列表或 Observer 列表。没有反馈 ACK，或反馈了但 Leader 没有收到的 Learner， Leader不会将其加入到相应列表。

更新广播

image.png

当集群中的 Learner 完成了初始化状态同步，那么整个 zk 集群就进入到了正常工作模式 了。

如果集群中的 Learner 节点收到客户端的事务请求，那么这些 Learner 会将请求转发给 Leader 服务器。然后再执行如下的具体过程：

1. Leader 接收到事务请求后， 为事务赋予一个全局唯一的 64 位自增 id，即 zxid，通过zxid 的大小比较即可实现事务的有序性管理，然后将事务封装为一个 Proposal。
2. Leader 根据 Follower 列表获取到所有 Follower，然后再将 Proposal 通过这些 Follower 的队列将提案发送给各个 Follower。
3. 当 Follower 接收到提案后，会先将提案的 zxid 与本地记录的事务日志中的最大的 zxid进行比较。若当前提案的 zxid 大于最大 zxid，则将当前提案记录到本地事务日志中，并向 Leader 返回一个 ACK。
4. 当 Leader 接收到过半的 ACKs 后， Leader 就会向所有 Follower 的队列发送 COMMIT消息，向所有 Observer 的队列发送 Proposal。
5. 当 Follower 收到 COMMIT 消息后，就会将日志中的事务正式更新到本地。当 Observer收到 Proposal 后，会直接将事务更新到本地。
6. 无论是 Follower 还是 Observer，在同步完成后都需要向 Leader 发送成功 ACK。

问题一：zookeeper更新广播，更新同步过程，是Fast-Paxos算法，只允许一个进程提交提案，所以Leader提交的提案编号肯定是最大的，不用比也知道肯定比那些learner手里的max-zxid大，那为什么第三步还需要比较？

在更新同一个数据的情况下，因为假如提案3通过了，但是只更新了一半的机器，有些机器因为网络原因还有没有收到提案3并更新，这个时候提案4通过了，并且更新了值，这个时候之前网络原因还没到的提案3来了，如果不比较，会覆盖掉最新的提案

问题二：如果两个提案修改的不是同一个数据的情况下，假如编号5提案想把一个值从1改成5，提案通过并更新了一半的机器，有些机器因为网络原因还没有收到编号5的提案，这个时候编号8的提案通过更新了另一个数据，该数据和编号5提案修改的数据不是同一个，这个时候，某个机器因为网络原因编号5的提案在编号8提案之后才到，导致编号5的提案被拒绝，值1没有变成5，数据不一致

当然上述场景是不会存在的，因为Follower 在接收到提案后，会先用提案的zxid在本地找有没有这个zxid的事务，如果有判断其内容和leader提案的内容是否相同，如果相同什么也不做，如果不同，会在本地递归找zxid-1的事务，继续和Leader里面zxid相同的事务比较，看提案的内容是否相同，就这样一直递归，直到找到相同的zxid事务，然后从Leader中将比zxid大的所有事务同步。这个就是Learner、Follower、Observer和Leader做数据同步的过程

无论是 Follower 还是 Observer，在同步完成后都需要向 Leader 发送成功 ACK，这个ACK有什么用？

Observer 的数量问题

Observer 数量一般与 Follower 数量相同。 并不是 Observer 越多越好， 因为 Observer 数量的增多虽不会增加事务操作压力，但其需要从 Leader 同步数据， Observer 同步数据的时间是小于等于 Follower 同步数据的时间的。当 Follower 同步数据完成， Leader 的 Observer列表中的 Observer 主机将结束同步。那些完成同步的 Observer 将会进入到另一个对外提供服务的列表。那么，那些没有同步了数据无法提供服务的 Observer 主机就形成了资源浪费。

所以，对于事务操作发生频繁的系统，不建议使用过多的 Observer。Observer 存在两个列表： all 与 service。

• Leader 中存在两个关于 Observer 的列表：all（包含所有 Observer）与 service（包含与Leader 同步过数据的 Observer）
• service 列表是动态变化的。对于没有进入到 service 列表中的 Observer，其会通过心跳与 Leader 进行连接，一旦连接成功，马上就会从 Leader 同步数据，同步完成后向 Leader发送 ACK。Leader 在接收到其 ACK 后会将其添加到 service 列表。
• 若客户端连接上了不在 service 列表中的 Observer，那么这个 Observer 是不能提供服务的。因为该 Observer 的状态不是 Observering。这个状态是通过 Observer 与 Leader 间的心跳来维护的。
• Leader 中对于 Follower 也同样存在两个列表：all 与 service。其功能与 Observer 的相似。但不同点是，- 若 Leader 收到的 Follower 同步完成的 ACK 数量没有过半，则认为同步失败，会重新进行广播，让 Follower 重新进行同步。

2.8 数据同步流程

在服务器启动阶段，会进行磁盘数据的恢复，完成数据恢复后就会进行Leader选举。一旦选举产生Leader服务器后，就立即开始进行集群间的数据同步，在整个过程中，Zookeeper都处于不可用状态，直到数据同步完毕，Zookeeper才可以对外提供正常服务。

2.8.1 数据初始化

在Zookeeper服务器启动期间，首先会进行数据初始化工作，用于将存储在磁盘上的数据文件加载到Zookeeper服务器内存中。完整的数据初始化流程如下：

图片

数据的初始化从磁盘中加载数据的过程，主要包括了从快照文件中加载快照数据和根据事务日志进行数据订正两个过程。

1. 初始化FileTxnSnapLog

FileTxnSnapLog是Zookeeper事务日志和快照数据访问层，用于衔接上层业务与底层数据存储，底层数据包含了事务日志和快照数据两部分，因此FileTxnSnapLog内部又分为FileTxnLog和FileSnap的初始化，分别代表事务日志管理器和快照数据管理器的初始化。

2. 初始化ZKDatabase

完成FileTxnSnapLog的初始化后，就要开始构建内存数据库ZKDatabase了，在初始化过程中，首先会构建一个初始化DataTree，同时会将步骤1中初始化的FileTxnSnapLog交给ZKDatabase，以便内存数据库能够对事务日志和快照数据进行访问。

3. 创建PlayBackListener监听器

PlayBackListener监听器主要用来接收事务应用过程中的回调，在Zookeeper数据恢复后期，会有一个事务订正的过程，在这个过程中，会回调PlayBackListener监听器来进行对应的数据订正。PlayBackListener会将这些刚刚应用到内存数据库中的事务转存到ZKDatabase.committedLog中，以便集群中服务器间进行快速的数据同步。

4. 处理快照文件

完成内存数据库的初始化后，java培训Zookeeper就可以开始从磁盘中恢复数据了，每一个快照数据文件中都保存了Zookeeper服务器几乎全量的数据，因此首先会从这些快照文件开始加载。

5. 获取最新的100个快照文件

Zookeeper会加载最新的至多100个快照文件。

6. 解析快照文件

如果正确性校验通过的话，那么通常只会解析最新的那个快照文件。只有当最新的快照文件不可用时，才会逐个解析，直到将这100个文件全部解析完。

7. 获取最新的ZXID

完成步骤6后，就已经基于快照文件构建了一个完整的DataTree实例和sessionsWithTimeouts集合汇总，此时根据这个快照文件的文件名就可以解析出一个最新的ZXID：zxid_for_snap，代表了Zookeeper开始进行数据快照的时刻。

8. 处理事务日志

经过前面7步流程的处理，此时Zookeeper服务器内存中已经有了一份近似全量的数据了，现在开始就要通过事务日志来更新增量数据了。

9. 获取所有zxid_for_snap之后提交的事务

Zookeeper中数据的快照机制决定了快照文件中并非包含了所有的事务操作，但是未被包含在快照文件中的那部分事务操作可以通过数据订正来实现，因此，我们这里只需要从事务日志中获取所有ZXID比步骤7得到的zxid_for_snap大的事务操作即可。

10. 事务应用

获取到所有ZXID大于zxid_for_snap的事务后，将其逐个应用到之前基于快照文件恢复出来的

DataTree和sessionsWithTimeouts中。

每当有一个事务被应用到内存数据库汇总，Zookeeper同时会回调PlayBackListener监听器，将这一事务操作记录转换成Proposal，并保存到ZKDatabase.committedLog中，以便Follower进行快速同步。

11. 获取最新ZXID

待所有的事务都被完整地应用到内存数据库中之后，基本上也就完成了数据的初始化过程，此时再获取一个ZXID，用来表示上次服务器正常运行时提交的最大事务ID。

12. 校验epoch

每次选举产生一个新的Leader服务器之后，就会生成一个新的epoch，在完成数据加载后，Zookeeper从步骤11中确定的ZXID中解析出事务处理的Leader周期，同时也会从磁盘文件中读取出上次记录的最新epoch值，进行校验。

接下来，我们就来看看数据同步的流程是怎样的。

2.8.2 数据同步

在集群服务器启动过程中，当整个集群完成Leader选举之后，Learner服务器会向Leader服务器进行注册，当所有服务器都注册完之后，就进入到了数据同步环节。数据同步过程就是Leader服务器将那些没有在Learner服务器上提交过的事务请求同步给Learner服务器。

大体过程如下：

图片

获取Learner状态

在注册Learner的最后阶段，Learner服务器会发送给Leader服务器一个ACKEPOCH数据包，Leader会从这个数据包中解析出该LearnerDE currentEpoch和lastZxid。

数据同步初始化

在开始数据同步之前，Leader服务器会进行数据同步初始化，首先会从Zookeeper的内存数据库中提取出事务请求对应的提议缓存队列proposals，同时完成以下三个ZXID值的初始化：

• peerLastZxid：该Learner服务器最后处理的ZXID
• minCommittedLog：Leader服务器提议缓存队列committedLog中的最小ZXID
• maxCommittedLog：Leader服务器提议缓存队列committedLog中的最大ZXID

Zookeeper集群数据同步分四类：直接差异化同步（DIFF同步）、先回滚再差异化同步（TRUNC+DIFF同步）、仅回滚同步（TRUNC同步）和全量同步（SNAP同步）。在初始化节点，Leader服务器会优先初始化以全量同步方式来同步数据，但不是最终的同步方式，最终的同步方式会根据Leader和Learner服务器之间的数据差异情况来决定。

直接差异化同步（DIFF同步）

场景：peerLastZxid介于minCommittedLog和maxCommittedLog之间。

对于这种场景，直接使用直接差异化同步方式即可。Leader服务器会首先向这个Learner发送一个DIFF指令，用于通知Learner进入差异化数据同步阶段。在实际Proposal同步过程中，针对每个Proposal，Leader服务器都会通过发送两个数据包来完成，分别是PROPOSAL内容数据包和COMMIT指令数据包。

举例说明：假如某个时刻Leader服务器的提议缓存队列对应的ZXID依次是：

0x500000001、0x500000002、0x500000003、0x500000004、0x500000005

而Learner服务器最后处理的ZXID为0x500000003，于是Leader服务器就会依次将0x500000004和0x500000005两个提议同步给Learner服务器，同步过程中的数据包发送顺序如下：

发送顺序	数据包类型	对应的ZXID
1	PROPOSAL	0x500000004
2	COMMIT	0x500000004
3	PROPOSAL	0x500000005
4	COMMIT	0x500000005

通过以上四个数据包的发送，Learner服务器就可以接收到自己和Leader服务器的所有差异数据，Leader服务器在发送完差异数据之后，就会将该Learner加入到forwardingFollowers或observingLearners队列中。随后Leader还会立即发送一个NEWLEADER指令，用于通知Learner已经将提议缓存队列中的Proposal都同步给你自己了。

接下来，我们看看Learner对Leader发送过来的数据包是如何处理的？

Learner首先会接收到一个DIFF指令，于是便确定了进入DIFF同步阶段。然后依次收到上述四个数据包，Learner会依次将其应用到内存数据库中，然后在接收到Leader的NEWLEADER指令后，Learner会反馈给Leader一个ACK消息，表明自己也完成了对提议缓存队列中Proposal的同步。

Leader在接收到来自Learner的这个ACK消息后，就认为当前Learner已经完成了数据同步，同时进入过半策略等待阶段，直到集群中有过半的Learner机器响应了Leader这个ACK消息。一旦满足过半策略后，Leader服务器就会向所有已经完成数据同步的Learner发送一个UPTODATE指令，用来通知Learner集群中已经有过半的机器完成了数据同步，集群已经具备了对外服务的能力了。

Learner在接收到这个来自Leader的UPTODATE指令后，会终止数据同步流程，然后向Leader再次反馈一个ACK消息。整个直接差异化同步过程中涉及的Leader和Learner之间的数据包通信如下图所示：

图片

先回 滚再差异化同步（TRUNC+DIFF同步）

在上述场景中有一个罕见的特殊场景：假如有A、B、C三台机器，B是Leader，此时的Leader_epoch为5，当前已经被集群中大部分机器都提交的ZXID包括：0x500000001和0x500000002。此时，Leader正要处理0x500000003，并且已经将该事务写入到了Leader本地的事务日志中，就在Leader要将该Proposal发送给其他Follower机器进行投票的时候，Leader服务器挂了，开始新一轮选举，同时Leader_epoch变更为6，之后A和C继续对外进行服务，又提交了0x600000001和0x600000002两个事务，此时B再次启动，并开始数据同步。

简单来说，上面这个场景就是Leader服务器已经将事务记录到了本地事务日志中，但是没有成功发起Proposal流程的时候就挂了，在这个特殊场景汇总，我们看到peerLastZxid和minCommittedLog和maxCommittedLog的值分别是0x500000003、0x500000001和0x600000002，显然，peerLastZxid介于minCommittedLog和maxCommittedLog之间。

对于这种特殊场景，就是用先回滚再差异化同步的方式。当Leader服务器发现某个Learner包含了一条自己没有的事务记录，那么就需要让该Learner进行事务回滚，回滚到Leader服务器上存在的，同时也是最接近于peerLastZxid的ZXID。在上述示例中，Leader需要Learner回滚到ZXID为0x500000002的事务记录。

先回滚再差异化同步的数据同步方式在具体实现上和差异化同步是一样的，都会将差异化的Proposal发送给Learner，同步过程中的数据包发送顺序如下：

发送顺序	数据包类型	对应的ZXID
1	TRUNC	0x500000002
2	PROPOSAL	0x600000001
3	COMMIT	0x600000001
4	PROPOSAL	0x600000002
5	COMMIT	0x600000002

仅回滚同步（TRUNC同步）

场景：peerLastZxid大于maxCommittedLog。

这种场景其实就是上述先回滚再差异化同步的简化模式，Leader会要求Learner回滚到ZXID值为maxCommitedLog对应的事务操作。

全量同步（SNAP同步）

场景1：peerLastZxid小于maxCommittedLog。

场景2：Leader上没有提议缓存队列，peerLastZxid不等于maxCommittedLog。

在这两种场景下，Leader服务器都无法直接使用提议缓存队列和Learner进行数据同步，因此只能进行全量同步。

全量同步就是Leader服务器将本机上的全量内存数据都同步给Learner。Leader服务器首先向Learner发送一个SNAP指令，通知Learner即将进行全量数据同步，随后，Leader会从内存数据库中获取到全量的数据节点和会话超时时间记录器，将它们序列化后传输给Learner。Learner服务器接收到该全量数据后，会对器反序列化后载入到内存数据库中。

2.9 恢复模式的三个原则

当集群正在启动过程中，或 Leader 崩溃后，集群就进入了恢复模式。对于要恢复的数 据状态需要遵循三个原则。

Leader 的主动出让原则

若集群中 Leader 收到的 Follower 心跳数量没有过半，此时 Leader 会自认为自己与集群的连接已经出现了问题，其会主动修改自己的状态为 LOOKING，去查找新的 Leader。 而其它 Server 由于已经找不到 Leader 了，所以它们会发起新的 Leader 选举，选出一个新的 Leader。

已被处理过的消息不能丢原则

当 Leader 收到超过半数 Follower 的 ACKs 后，就向各个 Follower 广播 COMMIT 消息，批准各个 Server 执行该写操作事务。当各个 Server 在接收到 Leader 的 COMMIT 消息后就会在本地执行该写操作，然后会向客户端响应写操作成功。

但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就挂了，这将导致一种后 果：部分 Server 已经执行了该事务，而部分 Server 尚未收到 COMMIT 消息，所以其并没有执行该事务。当新的 Leader 被选举出，集群经过恢复模式后需要保证所有 Server 上都执行了那些已经被部分 Server 执行过的事务。

只要保证新的 Leader 从“已经执行过最后事务的 Server”中选举出来就可以保证该原 则。而“已经执行过最后事务的 Server”的 xid 要比“没有执行过最后事务的 Server”的 xid要大。所以，只要 Leader 的选举算法是， zxid 大者当选即可。

实现：首先leader选举的时候先根据zxid比较，最大的才有可能当选，所以当选后在初始化广播和初始化同步的时候，就能够保证 已被处理过的消息不会丢，从机会先根据当前本地最大事务编号和leader比较，如果内容不同，会将当前事务-1，再次和leader比较，一直递归判断，直到相同，然后从该事务zxid开始，将leader比该zxid大的所有数据都同步到本地。

被丢弃的消息不能再现原则

当在 Leader 新事务已经通过，其已经将该事务更新到了本地，但所有 Follower 还都没 有收到 COMMIT 之前， Leader 宕机了（比刚才的挂的更早），此时，所有 Follower 根本就不知道该 Proposal 的存在。当新的 Leader 选举出来，整个集群进入正常服务状态后，之前挂了的 Leader 主机重新启动并注册成为了 Follower。若那个别人根本不知道的 Proposal 还保留在那个主机，那么其数据就会比其它主机多出了内容，导致整个系统状态的不一致。所以，该 Proposal 应该被丢弃。类似这样应该被丢弃的事务，是不能再次出现在集群中的，应该被清除。

对于这种事务的清除有两种情况： 这两种情况都可以通过数据同步过程就可以将这些应 该被丢弃的事务给覆盖:

• 新 Leader 的 xid 比 Follower(老 Leader)的大
• 新 Leader 的 xid 比 Follower(老 Leader)的小

2.10 Leader 选举

在集群启动过程中，或 Leader 宕机后，集群就进入了恢复模式。恢复模式中最重要的 阶段就是 Leader 选举。

2.10.1 Leader 选举中的基本概念

• serverId
  • 这是 zk 集群中服务器的唯一标识， 也称为 sid，其实质就是 zk 中配置的 myid。例如，有三个 zk 服务器，那么编号分别是 1,2,3。
• 逻辑时钟
  • 逻辑时钟， Logicalclock，是一个整型数。 该概念在选举时称为 logicalclock，而在选举结束后称为 epoch。即 epoch 与 logicalclock 是同一个值，在不同情况下的不同名称。

2.10.2 Leader 选举算法

在集群启动过程中的 Leader 选举过程（算法）与 Leader 断连后的 Leader 选举过程稍微有一些区别，基本相同。

集群启动中的 Leader 选举

若进行 Leader 选举，则至少需要两台主机，这里以三台主机组成的集群为例。

image.png

在集群初始化阶段，当第一台服务器 Server1 启动时，其会给自己投票，然后发布自己 的投票结果。投票包含所推荐的服务器的 myid 和本次推荐的 ZXID，使用(myid, ZXID)来表示，此时 Server1 的投票为(1, 0)。 由于其它机器还没有启动所以它收不到反馈信息， Server1 的状态一直属于 Looking，即属于非服务状态。

当第二台服务器 Server2 启动时，此时两台机器可以相互通信，每台机器都试图找到 Leader，选举过程如下：

• 每个 Server 发出一个投票。此时 Server1 的投票为(1, 0)， Server2 的投票为(2, 0)，然后各自将这个投票发给集群中其他机器。
• 接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
• 处理投票。针对每一个投票，服务器都需要将别人的投票和自己的投票进行 PK， PK规则如下：
  • 优先检查选票的 ZXID。 ZXID 比较大的服务器优先作为 Leader。
  • 如果 ZXID 相同，那么就比较选票所推荐的 server 的 myid。 myid 较大的服务器作为Leader 服务器。
    • 对于 Server1 而言，它的投票是(1, 0)，接收 Server2 的投票为(2, 0)。其首先会比较两者的 ZXID，均为 0，再比较 myid，此时 Server2 的 myid 最大，于是 Server1 更新自己的投票为(2, 0)，然后重新投票。对于 Server2 而言，其无须更新自己的投票，只是再次向集群中所有主机发出上一次投票信息即可。
• 统计投票。每次投票后，服务器都会统计投票信息， 判断是否已经有过半机器接受到 相同的投票信息。对于 Server1、 Server2 而言，都统计出集群中已经有两台主机接受了(2, 0)的投票信息，此时便认为已经选出了新的 Leader，即 Server2。
• 改变服务器状态。一旦确定了 Leader，每个服务器就会更新自己的状态，如果是Follower，那么就变更为 FOLLOWING，如果是 Leader，就变更为 LEADING。
• 添加主机。在新的 Leader 选举出来后 Server3 启动， 其想发出新一轮的选举。但由于当前集群中各个主机的状态并不是 LOOKING，而是各司其职的正常服务，所以其只能是以 Follower 的身份加入到集群中。

宕机后的 Leader 选举

在 Zookeeper 运行期间， Leader 与非 Leader 服务器各司其职，即便当有非 Leader 服务器宕机或新加入时也不会影响 Leader。但是若 Leader 服务器挂了，那么整个集群将暂停对外服务，进入新一轮的 Leader 选举，其过程和启动时期的 Leader 选举过程基本一致。

image.png

假设正在运行的有 Server1、 Server2、 Server3 三台服务器，当前 Leader 是 Server2，若某一时刻 Server2 挂了，此时便开始新一轮的 Leader 选举了。选举过程如下：

• 变更状态。 Leader 挂后，余下的非 Observer 服务器都会将自己的服务器状态由FOLLOWING 变更为 LOOKING，然后开始进入 Leader 选举过程。
• 每个 Server 会发出一个投票，仍然会首先投自己。不过，在运行期间每个服务器上的 ZXID 可能是不同，此时假定 Server1 的 ZXID 为 111， Server3 的 ZXID 为 333；在第一轮投票中， Server1 和 Server3 都会投自己，产生投票(1, 111)， (3, 333)，然后各自将投票发送给集群中所有机器。
• 接收来自各个服务器的投票。与启动时过程相同。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
• 处理投票。与启动时过程相同。针对每一个投票，服务器都需要将别人的投票和自己的投票进行 PK。对于 Server1 而言，它的投票是(1, 111)，接收 Server3 的投票为(3, 333)。其首先会比较两者的 ZXID， Server3 投票的 zxid 为 333 大于 Server1 投票的zxid 的 111，于是Server1 更新自己的投票为(3, 333)，然后重新投票。对于 Server3 言，其无须更新自己的投票，只是再次向集群中所有主机发出上一次投票信息即可。
• 统计投票。与启动时过程相同。对于 Server1、 Server2 而言，都统计出集群中已经有两台主机接受了(3, 333)的投票信息，此时便认为已经选出了新的 Leader，即Server3。
• 改变服务器的状态。与启动时过程相同。一旦确定了 Leader，每个服务器就会更新自己的状态。 Server1 变更为 FOLLOWING， Server3 变更为 LEADING。

2.11 l、Leader和Follower的主要功能

Leader功能和消息类型：

• 主要有三个功能
  • 恢复数据；
  • 维持与Learner的心跳，接收Learner请求并判断Learner的请求消息类型；
  • Learner的消息类型主要有PING消息、REQUEST消息、ACK消息、REVALIDATE消息，根据不同的消息类型，进行不同的处理。
• leader的消息类型有以下四种：
  • PING消息是指Learner的心跳信息；
  • REQUEST消息是Follower发送的提议信息，包括写请求及同步请求；
  • ACK消息是 Follower的对提议的回复，超过半数的Follower通过，则commit该提议；
  • REVALIDATE消息是用来延长SESSION有效时间。

Follower功能和消息类型：

• 主要有四个功能
  • 向Leader发送请求（PING消息、REQUEST消息、ACK消息、REVALIDATE消息）；
  • 接收Leader消息并进行处理；
  • 接收Client的请求，如果为写请求，发送给Leader进行投票；
  • 返回Client结果。
• Follower的消息类型有以下六种：
  • PING消息： 心跳消息；
  • PROPOSAL消息：Leader发起的提案，要求Follower投票；
  • COMMIT消息：服务器端最新一次提案的信息；
  • UPTODATE消息：表明同步完成；
  • REVALIDATE消息：根据Leader的REVALIDATE结果，关闭待revalidate的session还是允许其接受消息；
  • SYNC消息：返回SYNC结果到客户端，这个消息最初由客户端发起，用来强制得到最新的更新。

3. 高可用集群的容灾

3.1 服务器数量的奇数与偶数

对于 zk 集群中所包含服务器的数量存在一个误区：为了防止出现赞同票与反对票各占 一半的问题，必须要将服务器数量部署为奇数（不包含 Observer）。其实，部署奇数台服务 器从某种意义上说确实比偶数台好，但不是为了防止投票平均现象的。因为投票平均，提案 无法通过，则该提案会被重提的。

无论是写操作投票，还是 Leader 选举投票，都必须过半才能通过，也就是说若出现超过半数的主机宕机，则投票永远无法通过。基于该理论，由 5 台主机构成的集群，最多只允许 2 台宕机。而由 6 台构成的集群，其最多也只允许 2 台宕机。即， 6 台与 5 台的容灾能力是相同的。基于容灾能力的原因，建议使用奇数台主机构成集群，以避免资源浪费。

但从系统吞吐量上说， 6 台主机的性能一定是高于 5 台的。所以使用 6 台主机并不是资 源浪费。

3.2 容灾设计方案

对于一个高可用的系统，除了要设置多台主机部署为一个集群避免单点问题外，还需要考虑将集群部署在多个机房、多个楼宇。对于多个机房、楼宇中集群也是不能随意部署的，下面就多个机房的部署进行分析。

在多机房部署设计中，要充分考虑“过半原则”，也就是说，尽量要确保 zk 集群中有过 半的机器能够正常运行。

3.2.1 三机房部署

在生产环境下，三机房部署是最常见的、容灾性最好的部署方案。三机房部署中要求每 个机房中的主机数量必须少于集群总数的一半。

3.2.2 双机房部署

zk 官网没有给出较好的双机房部署的容灾方案。只能是让其中一个机房占有超过半数 的主机，使其做为主机房，而另一机房少于半数。当然，若主机房出现问题，则整个集群会 瘫痪。

3.3 zk 中的脑裂

这里说的 zk 可能会引发脑裂，是指的在多机房部署中，若出现了网络连接问题，形成 多个分区，则可能会出现脑裂问题，可能会导致数据不一致。

下面以三机房部署为例进行分析，根据机房断网情况，可以分为五种情况：

情况一

这种情况下， B 机房中的主机是感知不到 Leader 的存在的，所以 B 机房中的主机会发 起新一轮的 Leader 选举，它们的状态会变为 Looking，所以它们是不会对外提供服务的。由于 B 机房与 C 机房是相连的，所以其也会通知 C 机房中的主机进行 Leader 选举。

由于 C 机房能够感知到 A 机房中的 Leader，所以其状态为 Following。故其是不会参与 B机房发起的 Leader 选举的。由于没有 C 机房的参与，所以 B 机房中的选举不可能过半，即不可能选举出结果。

这种情况下，只有 A 与 C 机房对外提供服务。

情况二

image.png

A、 B、 C 均可以对外提供服务，不受影响。

情况三

image.png

A、 C 可以正常对外提供服务，但 B 将无法提供服务。

情况四

image.png

这种情况下 A 机房仍会对外提供服务，但只会提供短暂的读服务。

由于 B 与 C 均感知不到 Leader 的存在，且它们是相连的，所以它们会发起新一轮的选 举，此时会选举出一个新的 Leader。于是形成的两个分区出现了两个 Leader，这就是脑裂。当然，此时的 B 与 C 对外是可以提供读/写服务的。

情况五

image.png

这种情况只有 A 可能短暂的对外提供读服务，然后会由于 Leader 感知到已经失去了大 多数 Follower 而主动出让领导权，进入 LOOKING 状态。由于选举无法过半，从而无法对外 提供服务。

B 与 C 都会由于无法感知到 Leader 而使状态变为 Looking，发起新的 Leader 选举，但又都无法过半。所以最终 A、 B、 C 将都无法对外提供服务。

4. Raft 算法

Raft 算法动画演示： thesecretlivesofdata.com/raft/

4.1 基础

Nacos Discovery 集群为了保证集群中数据的一致性，其采用了 Raft 算法。 还有 Redis Sentinel 集群、 Etcd 集群的一致性也都是采用的 Raft 算法。

这是一种通过对日志进行管理来达到一致性的算法， 其是一种 AP 的一致性算法。 Raft 通过选举 Leader 并由 Leader 节点负责管理日志复制来实现各个节点间数据的一致性。

4.2 角色、任期及角色转变

在 Raft 中，节点有三种角色：

• Leader： 唯一负责处理客户端写请求的节点；也可以处理客户端读请求；同时负责日志复制工作
• Candidate： Leader 选举的候选人，其可能会成为 Leader
• Follower： 可以处理客户端读请求；负责同步来自于 Leader 的日志；当接收到其它Cadidate 的投票请求后可以进行投票；当发现 Leader 挂了，其会转变为 Candidate 发起Leader 选举 ,term， 任期， 相当于 Paxos 中的 epoch， 表示一个新的 leader 上任了。

4.3 leader 选举

我要选举

若 follower 在心跳超时范围内没有接收到来自于 leader 的心跳，则认为 leader 挂了。此时其首先会使其本地 term 增一。 然后 follower 会完成以下步骤：

• 此时若接收到了其它 candidate 的投票请求，则会将选票投给这个 candidate
• 由 follower 转变为 candidate
• 若之前尚未投票，则向自己投一票（注意， 每个节点在每个 term 内只能投一票）
• 向其它节点发出投票请求，然后等待响应

我要投票

follower 在接收到投票请求后，其会根据以下情况来判断是否投票：

• 发来投票请求的 candidate 的 term 不能小于我的 term
• 在我当前 term 内，我的选票还没有投出去
• 若接收到多个 candidate 的请求， 我将采取先来先服务 first-come-first-served 方式投票

等待响应

当一个 Candidate 发出投票请求后会等待其它节点的响应结果。这个响应结果可能有三 种情况：

• 收到过半选票，成为新的 leader。然后会将消息广播给所有其它节点，以告诉大家我是新的 Leader 了
• 接收到别的 candidate 发来的新 leader 通知，比较了新 leader 的 term 并不比我的 term 小，则自己转变为 follower
• 经过一段时间后，没有收到过半选票，也没有收到新 leader 通知，则重新发出选举

票数相同

若在选举过程中出现了各个 candidate 票数相同的情况，是无法选举出 Leader 的。当出 现了这种情况时，其采用了 randomized election timeouts 策略来解决这个问题。 其会让这些candidate 重新发起选举，只不过发起时间不同：各个 candidate 的选举发起时间是在一个给定范围内等待随机时长 timeout 之后开始的。 timeout 较小的会先开始选举，一般情况下其会优先获取到过半选票成为新的 leader。

4.4 数据同步

状态机

Raft 算法一致性的实现，是基于日志复制状态机的。状态机的最大特征是，不同 Server 中的状态机若当前状态相同，然后接受了相同的输入，则一定会得到相同的输出。

image.png

处理流程

当 leader 接收到 client 的写操作请求后，大体会经历以下流程：

• leader 将数据封装为日志
• leader 将日志并行发送给所有 follower，然后等待接收 follower 响应
• 当 leader 接收到过半响应后，将日志 commit 到自己的状态机，状态机会输出一个结果，同时日志状态变为了 committed
• 同时 leader 还会通知所有 follower 将日志 apply 到它们本地的状态机，日志状态变为了 applied
• 在 apply 通知发出的同时， leader 也会向 client 发出成功处理的响应

AP 支持

Log 由 term index、 log index 及 command 构成。为了保证可用性，各个节点中的日志可以不完全相同，但 leader 会不断给 follower 发送 log，以使各个节点的 log 最终达到相同。即 raft 算法不是强一致性的，而是最终一致的。

4.5 Leader 宕机处理

请求到达前 Leader 挂了

client 发送写操作请求到达 Leader 之前 Leader 就挂了，因为请求还没有到达集群，所以这个请求对于集群来说就没有存在过， 对集群数据的一致性没有任何影响。 Leader 挂了之 后，会选举产生新的 Leader。

由于 Stale Leader（失效的 Leader） 并未向 client 发送成功处理响应，所以 client 会重新 发送该写操作请求（若 Client 具有重试机制的话）。

未开始同步数据前 Leader 挂了

client 发送写操作请求给 Leader， 请求到达 Leader 后， Leader 还没有开始向 Followers 复制数据 Leader 就挂了。 这时集群会选举产生新的 Leader， Stale Leader 重启后会作为Follower 重新加入集群，并同步新 Leader 中的数据以保证数据一致性。 之前接收到 client 的数据被丢弃。

由于 Stale Leader 并未向 client 发送成功处理响应，所以 client 会重新发送该写操作请求（若 Client 具有重试机制的话）。

同步完部分后 Leader 挂了

client 发送写操作请求给 Leader， Leader 接收完数据后开始向 Follower 复制数据。 在部分 Follower 复制完后 Leader 挂了（可以过半也可以不过半）。 由于 Leader 挂了，就会发起新的 Leader 选举。

• 若 Leader 产生于已经复制完日志的 Follower，其会继续将前面接收到的写操作请求完成，并向 client 进行响应。
• 若 Leader 产生于尚未复制日志的 Follower，那么原来已经复制过日志的 Follower 则会将这个没有完成的日志放弃。由于 client 没有接收到响应，所以 client 会重新发送该写操作请求（若 Client 具有重试机制的话）。

apply 通知发出后 Leader 挂了

client 发送写操作请求给 Leader， Leader 接收完数据后开始向 Follower 复制数据。 Leader 成功接收到过半 Follower 复制完毕的响应后， Leader 将日志写入到状态机。此时 Leader 向 Follower 发送 apply 通知。在发送通知的同时，也会向 client 发出响应。此时 leader 挂了。

由于 Stale Leader 已经向 client 发送成功接收响应，且 apply 通知已经发出，说明这个写操作请求已经被 server 成功处理。

作者：hsfxuebao 链接：https://juejin.cn/post/7099251134333714440