Zookeeper中的ZAB协议和Leader Election算法

Zxid、Myid、Epoch

Zxid ：
表示事务ID, 为了保证事务的顺序一致性，Zookeeper 采用了递增的事务ID号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了 zxid，当提议通过并提交后，会修改 zxid 的后32位进行依次递增。同时也会用来做 Leader 选举时的凭证。
Myid ：
表示当前 Zookeeper 的一个自身标志，一般用来集群初始化的时候，因为没有提交过事务，所以 zxid 都是 0 ，为了能够选出一个 Leader，这个时候就会选择 myid 最大的节点作为 Leader。
Epoch ：
表示每个 Leader 任期期间的带代号。每完成一次选举 epoch 就会 +1 ，所以一般来说集群中节点的 epoch 都是一样的，而对于选举之后添加进来的节点， epoch 会不同。

ZAB简介

ZAB 全称 Zookeeper Atomic Broadcast，是特别为 Zookeeper 设计的支持崩溃恢复的原子广播协议。用于 Zookeeper 集群中的 Leader 崩溃时，进行崩溃恢复，以及维持集群各副本数据的一致性。

ZAB协议的两个主要内容

崩溃恢复：
当 Leader 崩溃，或者集群中大多数 Follower 无法与 Leader 正常通信时，会进入崩溃恢复模式，崩溃恢复模式下回选出新的 Leader，并在完成新 Leader 和 Follower 之间的数据同步，进入消息广播状态。
消息广播：
在消息广播过程中，来自客户端的写请求都将被转发到 Leader 上，再有 Leader 通知所有 Follower 节点并落盘，多数节点完成落盘后，最终提交事务，多数提交后即完成事务提交。

ZAB协议原理

• 选举: 在 Follower 中选举中一个 Leader
• 发现: Leader 中会维护一个 Follower 列表并与之通信
• 同步: Leader 会把自己的数据同步给 Follower , 做到多副本存储
• 广播: Leader 接受 Client 的请求事务 Proposal ,然后将这个事务性的 Proposal 广播给其他 Follower

ZAB协议广播过程

1. Leader 发送 Proposal 给集群中的所有节点（包括自己）

2. 节点在接收到 Leader 发送的 Proposal 之后，将其落到磁盘上，并发送一个 ACK 给 Leader

   在实现过程中的落盘这个步骤，Follower 会向 FollowerZooKeeperServer.pendingTxns 入列 zxid（递增的事务ID号码）

3. Leader 在接收到大多数节点的 ACK 之后，发送 Commit 给集群中的所有节点

   1、Follower 在收到 Leader 的 Commit 请求之后，会从 FollowerZooKeeperServer.pendingTxns 出列 zxid，如果这个出列的 zxid 与 Commit 请求的 zxid 不一致，表明当前 Follower 有漏提交的事务，当前 Follower 就会关闭自己

   2、如果 Leader 接收到的 ACK 不到半数，Leader 就会一直处于阻塞状态，后续客户端的写请求都将无法提交。如果长时间不能收到半数以上的ACK，很可能 Leader 已经与半数以上Follower 失去连接，此时集群会进入崩溃恢复模式，重新开始选举，在选举期间整个 Zookeeper 集群不对外提供服务。

   3、当事务提交成功后，就表明当前 zxid 是完全可信的，因为第二条可以知道，当前事务提交成功，代表之前的是物业提交成功了，否则提交的时候zxid对应不上，Follower节点就会自动关闭。同时说明集群中存有 zxid 最大的节点在当前集群中的数据是最完成的。

Leader Election 算法

vote（投票信息）

vote 是 Zookeeper 选举过程中的一个重要数据，一个 vote 由 epoch ，myid 和 zxid 组成。
例如其他节点传递过来的投票信息为 （voteEpoch,voteId,voteZxid），当前节点自身的投票信息为 （myEpoch,myId,MyZxid） ,如果以下条件中有一个成立时，就认为前者比后者的新：

1. voteEpoch > myEpoch
2. voteEpoch == myEpoch && voteZxid > myZxid
3. voteEpoch == myEpoch && voteZxid == myZxid && voteId > myId

这是在短时间内选出 Leader 的重要一步，因为最新的 zxid 保证了选出来的 Leader 中的数据是当前集群中最新的。

算法过程

因为 ZAB 协议中，每次选择 Leader 之后都会进行一次数据同步，其中 Epoch，信息也会被同步，即在每一次选举之后，集群中所有可以通讯的节点中的 Epoch 都是相同的。在集群初始化的时候，所有节点的第一次 Epoch 都是 1
所以以下选举过程不考虑 Epoch 因素的影响

1. 当集群初始化或者集群中大多数节点连接不上 Leader 时，会触发 Leader 的重新选举。
2. 例如 Zookeeper 中的节点一开始向所有节点发送 vote(voteId,voteZxid)，voteId 就是 myId，voteZxid 是当前节点上最新的 zxid （事务ID）。
3. 其他节点在接收到节点一的 vote 信息之后，会和自身的 vote（myId,myZxid） 做对比，如果节点一的 vote 比自身的新，就更新自身的 vote 信息 ，myId = voteId，myZxid=voteZxid，即表示当前节点支持节点一的投票，并把 vote（voteId,voteZxid） 信息发送给所有的 Zookeeper 节点。否则的话该节点保持沉默，不做任何处理。

顺利选举

1. 在时间点①时大家都开始了投票选举动作，即投出自己。
2. 在时间点②时 node2 和 node3 完成了选举过程。因为 node2 和 node3 接收到来自 node1 的投票信息后，发现比自己的新，所以将自己的投票信息修改为 （1，8） 并发送了出去，因为本身已经收到了 node1 的投票，而又接受到自身发送的对 node1 的投票，在三个节点的集群中，满足多数原则，所以 node2 和 node3 确认 node1 为 Leader。
3. 在时间节点③ node1 接收到了来自 node2 和 node3 对自身的投票，所以确认自身为 Leader。

选举过程中出现延迟

如上，在时间节点①， node2 只接受到了自身的投票和来自 node3 的投票，并未接受到来自 node1 的 vote 信息，所以 node2 理所当然的认为 node3 应该作为 Leader 。此时 node2 可能就会向 node3 发送请求，然而 node3 直到自己不是 Leader 所以对于 node2 的请求将不做响应，node2 将在 timeout 后重试，在 timeout 过程中 node2 是不能提供任何服务的。

针对这种情况， Zookeeper引入了等待时间（finalizeWait ）的概念

在时间节点① ，node2 只接受到了自身的投票和来自 node3 的投票，但是此时他不会直接选举 node3 为 Leader，而是因为 finalizeWait 机制的原因等待一段时间，当接收到 node1 的 vote 信息时，会重新选择 node1 为 Leader。
但是如果在等待时间之内仍未接受到来自 node1 的 vote ，节点而还是会将 node3 认为是 leader 并向其发送请求，直到 node2 找到新的 Leader。这应该只是 Zookeeper 对于网络延迟的一个简单容错，finalizeWait 的时间长度为 200ms ，因为一般选举过程会在 200ms 内完成。