Paxos算法概述：了解ZAB协议

（1）原理

Paxos 算法是莱斯利·兰伯特于1990 年提出的一种基于消息传递且具有高度容错特性的一致性算法。

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免地会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos 场景中，先不考虑可能出现消息篡改，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息的情况。Paxos 算法解决的问题：在一个可能发生上述异常的分布式系统中，如何就某个值达成一致，保证无论发生以上任何异常，都不会破坏决议一致性。

Paxos 算法使用一个希腊故事来描述，在Paxos 中存在三种角色，分别为：

①Proposer（提议者，用来发出提案Proposal）。

②Acceptor（接受者，可以接受或拒绝提案）。

③Learner（学习者，学习被选定的提案，当提案被超过半数的Acceptor 接受后为被批准）。

下面是Paxos 要解决问题的更精确的描述：

①决议（value）只有在被Proposal 提出后才能被批准。

②在一次Paxos 算法的执行实例中，只批准一个value。

③Learner 只能获得被批准的value。

ZooKeeper 的选举算法有两种：一种是基于Basic Paxos（Google Chubby 采用）实现的，另外一种是基于Fast Paxos（ZooKeeper 采用）算法实现的。系统默认的选举算法为Fast Paxos，并且ZooKeeper 在3.4.0 版本后只保留了FastLeaderElection 算法。(www.xing528.com)

ZooKeeper 的核心是原子广播，这个机制保证了各个Server 之间的同步。实现这个机制的协议称为ZAB 协议（ZooKeeper AtomicBrodCast）。ZAB 协议有两种模式，它们分别是崩溃恢复模式（选主）和原子广播模式（同步）。

①当服务启动或者在领导者崩溃后，ZAB 就进入了恢复模式，当领导者被选举出来，且大多数Server 完成与Leader 的状态同步以后，恢复模式就结束了。状态同步保证了Leader 和Follower 之间具有相同的系统状态。

②当ZooKeeper 集群选举出Leader 同步完状态退出恢复模式之后，便进入了原子广播模式。所有的写请求都被转发给Leader，再由Leader 将更新Proposal 广播给Follower，为了保证事务的顺序一致性，ZooKeeper 采用了递增的事务ID 号（zxid）来标识事务。所有的提议（Proposal）都在被提出的时候加上了Zxid。实际操作中Zxid 是一个64 位的数字，它高32 位是epoch 用来标识Leader 关系是否改变，每次一个Leader 被选出来，它都会有一个新的epoch，标识当前属于那个Leader 的统治时期。低32 位用于递增计数。

（2）Basic Paxos 流程

①选举线程由当前Server 发起选举的线程担任，其主要功能是对投票结果进行统计，并选出推荐的Server。

②选举线程首先向所有Server 发起一次询问（包括自己）。

③选举线程收到回复后，验证是否是自己发起的询问（验证zxid 是否一致），然后获取对方的Serverid（myid），并存储到当前询问对象列表中，最后获取对方提议的Leader 相关信息（Serverid，Zxid），并将这些信息存储到当次选举的投票记录表中。

④收到所有Server 回复以后，就计算出ID 最大的那个Server，并将这个Server 相关信息设置成下一次要投票的Server。

⑤线程将当前ID 最大的Server 设置为当前Server 要推荐的Leader，如果此时获胜的Server获得+1 的Server 票数，设置当前推荐的Leader 为获胜的Server，将根据获胜的Server 相关信息设置自己的状态，否则，继续这个过程，直到Leader 被选举出来。

通过流程分析可以得出：要使Leader 获得多数Server 的支持，则Server 总数必须是奇数2n+1，且存活的Server 的数目不得少于n +1。每个Server 启动后都会重复以上流程。在恢复模式下，如果是刚从崩溃状态恢复的或刚启动的Server，还会从磁盘快照中恢复数据和会话信息，zk 会记录事务日志并定期进行快照，方便在恢复时进行状态恢复。Fast Paxos 流程是在选举过程中，某Server 首先向所有Server 提议自己要成为Leader，当其他Server 收到提议以后，解决epoch 和Zxid 的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息，重复这个流程，最后一定能选举出Leader。