分布式中的一致性paxos算法以及其实现zab协议

分布式最重要的问题就是如何解决，不同节点中数据的一致性。paxos算法就是最重要的解决这个问题的理论。

paxos基础

Quorum机制

Quorum机制是表示在分布式系统中，只要大于总数-被修改数时，就能读到修改值

Quorum是分布式系统中的一种机制，用来保证数据冗余和最终一致性的投票算法。Quorum机制不是一个强一致性的，无法保证每个节点都能读取到最新的数据，需要一个类似于版本号的服务来确定获取到的数据是最新的。

paxos算法中定义的参与者角色

• proposer 提案者
• acceptor 批准者
• learner 学习者

paxos算法的流程

1. 准备阶段
   proposer提案者向acceptor批准者发送一个当前提案者最大的ProposallID,acceptor批准者收到ProposallID后，将与自己的maxId进行比较，这样会产生三种结果

   1. 回复数量中大于一半的节点返回的都是空，提案者直接向批准者发送更改
   2. 回复数量中大于一半的节点返回的不是空，提案者直接向批准者发送自己最大的proposallID和更改
   3. 回复数量中小于一半的节点，提案者重新进入准备阶段

2. 选举阶段

proposer提案者向acceptor批准者发送一个(proposallId,变更)，acceptor接受到之后会比较maxId是否进行更新操作，并将结果返回给提案者。这样又产生了三种结果：
1. 大于一半的节点返回更新成功，进行全局广播写入成功,学习者进行更改
2. 小于一半的节点时时，重新进入准备阶段
3. 当收到一条提交失败时，说明有其他的提交者进行了提交，因此重新进入准备阶段

paxos算法的常见问题

1. proposalId有什么作用？

通过类似于版本号的proposalId,将当前更改和版本进行关联，版本号大的可以替代版本号小的更改

Zab算法

Zab协议是zk用来保证分布式事务最终一致性的的paxos算法的工程实践，其支持崩溃恢复

zab协议的具体实现可以分为以下两个部分：
pk

• 消息广播阶段

Leader节点接受更改，再通知从节点，最后进行commit

• 崩溃恢复阶段

当Leader节点宕机，会进入崩溃恢复阶段，重新进行Leader选举

Zxid

Zxid是zab协议中的一个事务编号，由64位数字组成，其中低32位是一个简单的单调递增计数器，高32位表示leader节点的唯一任职周期。

zab的具体流程

消息广播阶段

消息广播阶段主要是分为

1. leader节点将操作分配一个zid，封装成一个事务，放到对应的follower节点对应的队列中
2. 发送队列中的消息到对应的follower节点，返回相应的ACK消息到leader节点
3. leader节点根据follower节点返回的消息进行操作，过半进行广播事务的提交

崩溃恢复阶段

可能导致进入崩溃恢复阶段的情况有：

1. 初始化集群
2. leader崩溃
3. leader失去半数以上的机器

zk中的节点一共有三种状态

状态	说明
following	从属节点
leading	leader节点，负责协调
election/looking	处于候选状态

• 选举的规则
  候选节点首先在第一次投票中先将自己投为leander，然后将消息广播出去。其他的候选节点接受到消息后进行选举处理。
  选举处理就是：

1. 首先选举 epoch 最大的
2. 如果 epoch 相等，则选 zxid 最大的
3. 若 epoch 和 zxid 都相等，则选择 server id 最大的，就是配置 zoo.cfg 中的 myid
4. 最后得出最终结果，改变各个节点的状态。选举结束。