vlambda博客
学习文章列表

本文的目的是为了简单的了解一下这两个算法（机制）。

1、Paxos算法

Paxos算法是一种基于消息传递且具有高度容错性的一致性算法。用于解决分布式系统中各个进程如何就某个值达成一致的问题。利用大多数机制，保证2N+1的容错能力，即系统中最多允许出现N个节点故障。

1.1、Paxos算法中的角色

• 提议者（Properser） 提出议案（Proposal）,包括全局唯一且递增的Proposal ID和提议的值。
• 决策者（Accepter） 参与决策，回应提议者的提案。若提案获得多数决策者的接受，则此提案被批准。
• 最终决策学习者（Learner） 不参与决策，从提议者与决策者学习最新达成一致的提案。

多副本状态机中都有这三种角色：

1.2、Paxos算法简单流程

一个完整的Paxos算法分为三个阶段：

• Prepare阶段 提议者向各个决策者发送Prepare请求，各个决策者针对收到的Prepare请求进行Promise承诺。
• Accept阶段 提议者收到多数决策者的promise后，向决策者发出Propose请求，决策者针对收到的Propose请求进行Accept处理。
• Learn阶段 提议者在收到多数决策者的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有的学习者。

Paxos算法的例子可以参考文末的链接。

2、ZAB协议

ZAB是Zookeeper原子广播协议的简称（Zookeeper Atomic Broadcast Protocol）,在Zookeeper中依赖ZAB来实现分布式数据一致性，实现主备模式的系统架构来保持各个副本之间的数据一致性。

2.1、术语

2.1.1、大多数投票机制(quorum)

集群中超过半数的节点集合。

2.1.2、ZAB中节点的三种状态

• following 跟随者，服从leader节点命令。
• leading 领导者，协调事务。
• looking 节点处于选举状态。

2.1.3、epoch

当前集群所处的年代，每个leader上任都有年号，leader变更后，会在前一个年代的基础上+1。follower只听当前年代的leader的命令。

2.1.4、zxid

ZAB协议的事务编号，是一个64位数字，其中低32位是简单的单调递增计数器，对于客户端的每一个事务请求，计数器+1，高32位代表Leader的epoch编号，当新的Leader产生时，会从Leader的服务器上取出本地日志中最大的zxid，并取出其epoch值，然后+1作为新的epoch,并将低32位从0开始计数。

2.1.5、节点的持久状态

• history 当前节点接收到的事务提议的log。
• acceptedEpoch follower已经接受的leader更改年号的提议。
• currentEpoch 当前所处的年代。
• lastZxid history中最近接收到的提议的最大的zxid。

2.2、ZAB的四个阶段

来源：看大牛如何分析Zookeeper ZAB 协议

2.2.1、选举阶段（Leader Election）

节点在一开始都处于选举节点，只要有一个节点得到超过半数节点的投票，都可以称为准Leader。

2.2.1、发现阶段（Discovery）

在发现阶段，follower和准Leader通信，同步follower最近接收的事务提议。

2.2.1、同步阶段（Synchronization）

这一阶段主要是根据上一阶段准leader获取的最新事务提议历史，同步集群中所有的副本。只有当集群中超过半数的节点集合都同步完成，准leader才会称为真正的leader。follower只会接收zxid比自己lastZxid大的提议。

2.2.1、广播阶段（Broadcast）

在这个阶段，zookeeper才能对外提供服务，并且Leader可以进行消息广播，如果有新节点加入集群，需要对新节点进行同步。

3、Paxos与ZAB的联系

ZAB本质上就是Paxos的一种简化形式， 两者都有类似Leader角色，协调事务，都是超过半数节点反馈后，提案提交。但是他们的设计目的不一样。ZAB 协议主要用于构建一个高可用的分布式数椐主备系统， 而Paxos算法 则是用于构建一个分布式的一致性状态机。