Raft协议和ZAB协议

   分布式系统设计中，在极大提高可用性、容错性的同时，带来了一致性问题（CAP理论），Raft协议和ZAB协议就是用于解决分布式中的一致性问题的方案。

   一、Raft协议

   1. Raft协议是什么？

   Raft协议是一种分布式一致性算法（共识算法），它是为了替代复杂难懂的 Paxos 算法而生的。共识就是多个节点对某一个事件达成一致的算法，即使出现部分节点故障，网络延时等情况，也不影响各节点，进而提高系统的整体可用性。Raft是使用较为广泛的分布式协议，我们熟悉的etcd注册中心就采用了这个算法；
   Raft算法将分布式一致性分解为多个子问题，包括Leader选举（Leader election）、日志复制（Log replication）、安全性（Safety）、日志压缩（Log compaction）等。

   2. 系统中的角色

   Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选者（Candidate）。

• Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后高速Follower提交日志。
• Follower：接受并持久化Leader同步的日志，在Leader告知日志可以提交后，提交日志。当Leader出现故障时，主动推荐自己为候选人。
• Candidate：Leader选举过程中的临时角色。向其他节点发送请求投票信息，如果获得大多数选票，则晋升为Leader。

   Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Follower，Raft算法将时间划分为任意不同长度的任期(Term)，每一任期的开始都是一次选举，一个或多个候选人会试图称为Leader，在成功选举Leader后，Leader会在整个任期内管理整个集群，如果Leader选举失败，该任期就会因为没有Leader而结束，开始下一任期，并立刻开始下一次选举。

   3. Leader选举

   Raft使用心跳机制来触发领导者选举，当服务器启动时，初始化都是Follower身份，由于没有Leader，Followers无法与Leader保持心跳，因此，Followers会认为Leader已经下线，进而转为Candidate状态，然后Candidate向集群其他节点请求投票，同意自己成为Leader，如果Candidate收到超过半数节点的投票(N/2 +1)，它将获胜成为Leader。

   如下图：

    1）选举触发时机

    Leader向所有Follower周期性发送heartbeat，如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

    2）唯一投票

   在Raft协议中，一个节点在一次任期（term）内只能投一次票。这是为了防止同一候选者在一轮选举中获得多次投票，或者多个候选者在同一轮选举中都获得同一节点的投票，从而确保选举的公正性。

   在进入选举投票时，每个节点都会先给自己投票，那会不会出现所有的节点都给自己投票呢？注意上述中 Candidate 和 Follower 的区别。

   Follower 在一段时间内（超时时间）没有接收到 Leader 的心跳，它就会把自己标记为 Candidate，成为 Candidate 后才会给自己投票，并给其他节点发起请求投票。但每个节点的超时时间都是随机的，所以所有 Follower 节点进入 Candidate 状态的时间是不一样的。当第一个 Candidate 发送请求投票给其他节点时，其他节点基本还是 Follower 状态，还没有把票投给自己。

   同样如果第一轮选举失败，要发起下一轮选举。每个节点还是经过随机的不同超时时间后，再进入 Candidate 状态。

   3）任期

   在Raft协议中，任期被用作逻辑时钟，并用于解决冲突。每当选举开始时，候选者都会增加它们的任期。这样可以确保每一轮选举都有一个唯一的标识，同时也能防止过期的选举结果影响新的选举。

   如果第一轮选举失败了，第二轮选举开始时，候选者依然会首先增加它们的任期。例如，假设一个节点在第一轮选举中没有获得足够的投票，然后开始第二轮选举。此时，如果它没有增加其任期，那么就可能出现一个问题：这个节点可能同时在第一轮和第二轮选举中都是候选者。这将导致混乱，因为其他节点可能不知道他们应该对哪一轮选举进行投票。

   4. 日志同步

   Raft算法实现日志同步的具体过程如下：

   1）Leader收到来自客户端的请求，将之封装成log entry并追加到自己的日志中；

   2）Leader并行地向系统中所有节点发送日志复制消息；

   3）接收到消息的节点确认消息没有问题，则将log entry追加到自己的日志中，并向Leader返回ACK表示接收成功；

   4）Leader若在随机超时时间内收到大多数节点的ACK，则将该log entry应用到状态机并向客户端返回成功。

   如下图：

  二、ZAB协议

  1.  ZAB协议是什么？

  ZAB 协议主要是用在 ZooKeeper 集群中。同 Raft协议一样，都是为了替代复杂难懂的 Paxos 算法，二者的相似度很高。

  2. ZAB 协议核心

  在 Zookeeper 中只有一个 Leader，并且只有 Leader 可以处理外部客户端的事务请求，并将其转换成一个事务 Proposal（写操作），然后 Leader 服务器再将事务 Proposal 操作的数据同步到所有 Follower（数据广播/数据复制）。

  Zookeeper 采用 Zab 协议的核心就是只要有一台服务器提交了 Proposal，就要确保所有服务器最终都能正确提交 Proposal，这也是 CAP/BASE 最终实现一致性的体现。

  2.  ZAB 两种模式

  ZAB 协议有两种模式：一种是消息广播模式，另一种是崩溃恢复模式。

  1）消息广播模式

  在系统正常运行时，所有的数据更新操作都由一个领导者节点（Leader）发起，然后通过原子广播方式传递到所有的追随者节点（Follower）。

  在 Zookeeper 集群中数据副本的传递策略就是采用消息广播模式，Zookeeper 中的数据副本同步方式与2PC方式相似但却不同，2PC是要求协调者必须等待所有参与者全部反馈ACK确认消息后，再发送 commit 消息，要求所有参与者要么全成功要么全失败，2PC方式会产生严重的阻塞问题。
而 Zookeeper 中 Leader 等待 Follower 的 ACK 反馈是指：只要半数以上的 Follower 成功反馈即可，不需要收到全部的 Follower 反馈。

  2）崩溃恢复模式

  一旦 Leader 服务器出现崩溃或者由于网络原因导致 Leader 服务器失去了与过半 Follower 的联系，那么就会进入崩溃恢复模式。
Zookeeper 集群中为保证任何进程能够顺序执行，只能是 Leader 服务器接收写请求，其他服务器接收到客户端的写请求，也会转发至 Leader 服务器进行处理。

  Zab 协议崩溃恢复需满足以下2个请求：

确保已经被 Leader 提交的 proposal 必须最终被所有的 Follower 服务器提交

确保丢弃已经被 Leader 提出的但没有被提交的 Proposal

也就是新选举出来的 Leader 不能包含未提交的 Proposal，必须都是已经提交了的 Proposal 的 Follower 服务器节点，新选举出来的 Leader 节点中含有最高的 ZXID，所以，在 Leader 选举时，将 ZXID 作为每个 Follower 投票时的信息依据。这样做的好处是避免了 Leader 服务器检查 Proposal 的提交和丢弃工作。

   3. Leader 选举

   ZAB协议的选举过程主要发生在恢复模式中，一般在系统启动或者领导者节点故障时触发，主要分以下几步：

   1）开始选举

   每个节点首先投给自己一票，并将自己的编号和最后一条已经提交的事务的ZXID（Zookeeper Transaction ID，包含了事务的epoch和计数器）发送给其他所有节点，表示它推举自己成为领导者。

   2）收集选票：接收到其他节点的投票信息后，每个节点会比较其他节点的ZXID和自己的ZXID。如果其他节点的ZXID更高（epoch或者计数器更大），或者ZXID相同但是节点编号更大，那么就会将票投给这个节点。
   3）计票：每个节点收集到超过半数的投票（包括自己的）后，就会认为选举完成，选出的领导者就是得票最多的节点。如果有多个节点的票数相同，就选择ZXID最大的节点，如果还是相同，就选择节点编号最大的。

   4）领导者确认

   选举完成后，新的领导者会向所有节点发送领导者确认消息，其他节点收到确认消息后，会向领导者发送已经接受领导者的消息。

   5）新领导者工作

   当领导者收到大多数节点的确认消息时，就可以开始提供服务，处理客户端的请求，从而结束了选举过程。

   总结：ZAB协议的选举过程是为了在领导者节点故障时快速选出新的领导者，恢复系统的正常运行，同时还确保了系统的一致性。

   三、Raft协议和ZAB协议的区别

   通过选举流程来看，二者差别不大，它们在领导者选举的过程中主要区别在于：

   1. 选举条件

   在Raft中，如果 Follower 在一段时间内没有收到 Leader 的心跳信息，就会主动进入候选人状态并启动新一轮选举，原因可能只是 Leader 节点繁忙而无法及时响应等情况。而在ZAB除了系统启动时，只有等到 Leader 故障，无法提供服务时才会进行选举。Raft更偏向于积极选举，只要有可能就尝试选举新的领导者，而ZAB更倾向于保持现状，只有在确定领导者无法提供服务时才触发选举。

   2. 投票规则

   Raft 中，每个节点只能投票一次，并且投票给第一个请求投票的候选人。而在 ZAB 协议中，节点可能会改变自己的投票，投给 ZXID 更大的节点。所以 ZAB 不存在随机超时时间，虽然第一票都会投给自己，但后续如果决定其他节点的 ZXID 更大，就修改自己的选票。

   3. 票数要求：在Raft 中，候选人在获得超过半数的投票后成为 Leader。在 ZAB 中，新的领导者被选出后，还需要得到超过半数的节点的确认才能开始工作。

   4. 决定因素

   在Raft中，选举过程严格按照轮次进行，每轮选举只能选出一位Leader，选出 Leader 很大程度取决于随机的超时时间和日志最新。而在 ZAB 中，选举的结果主要取决于节点的 ZXID 以及节点编号。ZXID最大的节点通常是最近处理过事务，数据最新的节点。

   参考链接：

   https://juejin.cn/post/7143541597165060109

   https://juejin.cn/post/7001070049200963621