分布式一致性算法Paxos、Raft 及 Zookeeper ZAB_raft算法和zookeeper

国科大学习生活（期末复习资料、课程大作业解析、学习文档等）: 文章专栏（点击跳转）
大数据开发学习文档（分布式文件系统的实现，大数据生态圈学习文档等）: 文章专栏（点击跳转）

分布式一致性算法Paxos、Raft 及 Zookeeper ZAB

1. 什么是分布式一致性算法？

分布式一致性算法是用于在分布式系统中确保数据一致性的一类算法。在分布式计算环境中，数据通常会分布在多个节点或副本中，并且这些节点可能由于网络延迟、故障或其他原因而导致数据的不一致。因此，分布式一致性算法的目标是确保分布式系统中的所有节点最终都能达到一致的状态。
分布式一致性算法可以分为两种主要类型：强一致性和弱一致性。

1. 强一致性算法（Strong Consistency）：强一致性算法保证在任何时刻，系统中的任意节点都可以看到相同的数据副本，并且对数据的任何操作都会立即反映在系统的其他部分。常见的强一致性算法包括Paxos和Raft。
2. 弱一致性算法（Weak Consistency）：弱一致性算法允许在分布式系统中的不同节点之间存在一定时间上的数据不一致，以提高系统的可用性和性能。弱一致性算法通常以最终一致性为目标，即系统最终会达到一致的状态。常见的弱一致性算法包括Gossip协议和CRDTs（Conflict-free Replicated Data Types）。

分布式一致性算法的选择取决于系统的需求和特定的应用场景。强一致性算法提供了严格的一致性保证，但可能会对性能产生较大的影响。而弱一致性算法可以在某些场景下提供更高的性能，但对数据的一致性要求较低。
因此，在设计分布式系统时，需要根据实际需求综合考虑一致性和性能之间的权衡。

1.1 Paxos一致性协议

Paxos是一种分布式系统中的一致性算法，用于解决分布式系统中节点之间的数据一致性问题。它是由Leslie Lamport于1990年提出的。在 Paxos 算法中，把数据修改用提案标识：Proposal:提案，即分布式系统的修改请求，可以表示为[提案编号N，提案内容value]

在 Paxos 算法中有三种角色：Proposer，Acceptor，Learners（注意，每个节点都可以身兼数职）

• Proposer ：发起提案，只要 Proposer 发的提案被半数以上 Acceptor 接受，Proposer 就认为该提案里的 value 被选定了。
• Acceptor : 只要 Acceptor 接受了某个提案，Acceptor 就认为该提案里的 value 被选定了。不同意比自己以前接收过的提案编号要小的提案，例如A以前给N号提案表决过，那么再收到小于等于N号的提案时就直接拒绝了
• Learners : Acceptor 告诉 Learner 哪个 value 被选定，Learner 就认为那个 value 被选定。类似记录被通过提案的记录员，负责记录提案

Paxos算法的核心思想是通过多个轮次的消息传递和投票来达成共识。算法的主要流程可以概括如下：

1. 准备阶段（Prepare）：提议者（Proposer）向接受者（Acceptor）发送Prepare请求，在接受者中选择一个提案编号（Proposal Number）作为准备的回应。
2. 承诺阶段（Promise）：如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应Propose反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。
3. 学习阶段（Learner）：如果提议者（Proposer）收到了大多数接受者（Acceptor）的承诺（Promise），那么它会向所有节点发送确定的请求（Accept请求），要求它们接受提案。接受者在接收到大多数的接受请求后，就可以接受该提案。
   

通过多个轮次的消息传递，Paxos算法最终可以使得所有节点达成一致，并选择一个确定的提案作为共识结果。

Paxos示例1：

Paxos示例2：

Paxos算法是一种高度复杂的算法，尤其是在实现细节和各种优化策略方面。它是分布式系统中的重要工具，用于确保数据的一致性和可靠性。

1.2 Paxos算法缺陷

在网络复杂的情况下，一个应用Paxos算法的分布式系统，可能很久无法收敛，甚至陷入活锁的情况：

为解决这种问题的出现，下面我们来介绍另一种一致性算法：Raft。

1.3 Raft一致性协议

Raft 是一种分布式一致性算法，用于在分布式系统中实现数据的一致性和高可用性。它由 Diego Ongaro 和 John Ousterhout 在 2013 年提出，并于 2014 年发表的论文中详细描述了算法的设计原则和机制。

根据Paxos的改进：整个系统只有一个Proposer，称之为Leader。
若集群中没有Leader，则在集群中选出一个节点并声明它为第M任Leader。集群的Acceptor只表决最新的Leader发出的最新的提案，其他步骤和Paxos相同。Raft 和 Paxos 一样只要保证 n/2+1 节点正常就能够提供服务；Raft 把算法流程分为三个子问题：

• 选举（Leader election）
• 日志复制（Log replication）
• 安全性（Safety）
  

Raft 算法的领导者选举机制具有以下过程：

1. 初始状态：当一个 Raft 集群启动时，所有节点都处于 Follower 状态。每个节点都等待接收来自 Leader 的心跳消息。
2. Follower 成为 Candidate：如果一个 Follower 在一段时间内未收到来自 Leader 的心跳消息，它将成为 Candidate，并开始发起选举。
3. 发起选举：一旦成为 Candidate，节点将增加自己的当前任期号（term），然后发送包含该任期号和候选人 ID 的请求给其他节点。每个节点只能投一次票，因此在一次选举中只会有一个 Candidate 获胜。
4. 投票过程：每个节点在收到来自 Candidate 的选举请求后，会根据以下条件进行投票决策：
   • 如果该节点已经投过票给了其他 Candidate，并且该 Candidate 的任期号更大，则拒绝投票。
   • 如果该节点的日志更新较新，没有落后于 Candidate 的日志，则支持该 Candidate 并重置自己的选举超时计时器。
5. 选举胜出条件：一个 Candidate 可以成为新的 Leader，需要满足以下条件之一：
   • 收到了大多数节点的选票，并且得票数超过了一半。
   • 在选举过程中，其他节点成为了 Leader（新的 Leader 后来者居上）。
6. 成为 Leader：当一个 Candidate 赢得选举后，它将成为新的 Leader。它会发送心跳消息给所有节点来维持自己的领导地位，并准备接收客户端的操作请求。

通过这样的领导者选举机制，Raft 算法保证了集群中只存在一个 Leader，使得整个系统能够稳定运行。而选举过程中使用的随机化和选举超时机制，确保了快速选出新的 Leader，从而减少系统的不可用时间。

相对于其他一致性算法，如 Paxos，Raft 更加易于理解和实现。它的设计模块化，便于扩展和维护。它的目标是提供一个可靠的分布式一致性算法，以简化构建分布式系统的难度。
Raft动态图片演示链接
一定要看！
一定要看！
一定要看！重要的事情说三遍，演示超级详细！！！

2. 什么是Zookeeper？

Zookeeper是一个用于构建分布式应用的开源协调服务。它提供高度可靠的分布式协调功能，使得分布式应用可以在大规模集群中进行协作和同步。

Zookeeper可以被广泛应用于分布式系统中的各种场景，如分布式锁、领导选举、配置管理、命名服务等。它被许多分布式系统和框架使用，比如Hadoop、Kafka等。Zookeeper的简单和可靠性使得它成为构建可扩展和弹性的分布式系统的重要工具之一。

2.1 ZAB一致性协议

ZAB（ZooKeeper Atomic Broadcast）是 Apache ZooKeeper 分布式协调服务中使用的一种原子广播协议。它旨在实现分布式系统中的一致性和可靠性。
ZAB 协议将 ZooKeeper 服务集群中的节点分为两个角色：Leader 和 Follower。Leader 负责接收并处理客户端请求，然后将请求广播给集群中的所有节点（包括自己）。Follower 则对 Leader 发送的消息进行复制和追随，以保持整个集群的数据一致性。

选举参数
在介绍选举流程之前，需要介绍几个参数，

• myid: 服务器ID，这个是在安装Zookeeper时配置的，myid越大，该服务器在选举中被选为Leader的优先级会越大。ZAB算法中通过myid来规避了多个节点可能有相同zxid问题，（注意可以对比之前的Raft算法，Raft算法中通过随机的timeout来规避多个节点可能同时成为Leader的问题）。
• zxid: 事务ID，这个是由Zookeeper集群中的Leader节点进行Proposal时生成的全局唯一的事务ID，由于只有Leader才能进行Proposal，所以这个zxid很容易做到全局唯一且自增。因为Follower没有生成zxid的权限。zxid越大，表示当前节点上提交成功了最新的事务，这也是为什么在崩溃恢复的时候，需要优先考虑zxid的原因。
• epoch: 投票轮次，每完成一次Leader选举的投票，当前Leader节点的epoch会增加一次。在没有Leader时，本轮此的epoch会保持不变。

另外在选举的过程中，每个节点的当前状态会在以下几种状态之中进行转变。

LOOKING: 竞选状态。
FOLLOWING: 随从状态，同步Leader 状态，参与Leader选举的投票过程。
OBSERVING: 观察状态，同步Leader 状态，不参与Leader选举的投票过程。
LEADING: 领导者状态。
1
2
3
4

ZAB 协议的核心机制包括两个阶段：崩溃恢复阶段（Leader 选举）和消息广播阶段。

1. 崩溃恢复阶段（Leader 选举）：

   • 选举算法：在初始启动或 Leader 崩溃的情况下，ZAB 协议会启动选举算法来选举新的 Leader。节点将发送选举请求（包含自己的 ID 和选举轮次）给所有节点，并等待其他节点的投票。某个节点收到投票请求后，会比较选举轮次和节点 ID 来决定是否投票。最终，根据投票数量和选举规则，选举出新的 Leader 节点。

   • 同步数据：新选出的 Leader 需要将自己的数据状态同步给其他节点，以确保整个集群达到一致性。Leader 会将自己的数据变更记录（事务日志）发送给所有的 Follower 节点，然后等待大多数节点确认接收。

2. 消息广播阶段：

   • Leader 的操作：一旦选举成功，Leader 负责接收客户端的操作请求，并将这些请求转换为事务日志，然后将日志广播给所有的 Follower 节点。
   • Follower 的复制：Follower 节点接收到 Leader 发送的事务日志后，会将其复制到本地的存储中，并发送确认消息给 Leader。当 Leader 收到大多数节点的确认消息后，可以确认该日志已经被复制成功。
   • 提交和应用：在大多数节点确认接收到某个事务日志后，Leader 可以将该事务日志提交，并将结果应用到自己的状态中。然后 Leader 会通知所有的节点该事务的提交结果，以保持整个集群状态的一致性。

Zookeeper选举机制示例：
注：示例中的服务器ID即为上文中的myid、事务ID即为上文zxid中的count、逻辑时钟即为上文中的epoch

ZAB一致性协议讲解视频B站链接

强烈建议观看，毕竟纯文字的形式对于知识的理解不如演示动画的形式来的快

ZAB 协议通过 Leader 选举和日志复制的方式实现了数据的一致性和可靠性。它确保了在集群中只有一个 Leader，避免了数据冲突。同时，ZAB 协议提供了恢复机制，以应对 Leader 崩溃或网络分区等异常情况。这使得 ZooKeeper 可以作为高性能、高可用性的分布式协调服务在实际应用中被广泛使用。

参考文献：
文章名：一文彻底搞懂ZAB算法，看这篇就够了！！！
文章名：Zookeeper核心知识及分布式一致性算法

---

21点19分 2023年12月15日
近期课程压力变小，于是重新开始学习大数据开发框架知识
书写学习文档一方面是为了督促自己更好的学习，另一方面也是给自己的学习之路留下个痕迹。

---

身为初学者，难免有表述不准确的地方，欢迎大家积极讨论交流。
不积跬步 无以至千里！