ZooKeeper原理-paxos算法，ZAB协议

我在 分布式高可用的ZooKeeper集群搭建与基本操作 提到，zk的关键字是分布式协调，其可扩展、可靠性、时序性以及快速保证了zk的高性能。

扩展性

一个zk集群有leader，follower，这个我们已经知道了，其实zk集群中还有个Observer的角色。

在zoo.cfg中这样配置：

server.1=zknode1:2888:3888
server.2=zknode2:2888:3888
server.3=zknode3:2888:3888
server.4=zknode4:2888:3888:observer

那么server.4的角色就是observer。

zk集群中leader负责写入数据，client读取数据只从follower读取，所以zk是读写分离的。这个observer也负责提供查询（读取），可以理解为它比follwer级别更低一些，当leader挂了的时候，leader参与选举投票，而observer不参与投票（和投票相关的能力均没有）。observer放大查询能力！

可靠性

想要对外提供高性能可靠的服务，zk集群内部必定有一套快速恢复leader的机制。我之前实际操作过，当leader挂了的时候，zk集群迅速就选出了新的leader。官方说200ms之内能够快速恢复leader。

一致性

在zk集群恢复leader（投票选举）的过程中，节点是不对外提供服务的！目的是保证数据最终一致性！

zk的基石：paxos

注：前方高能！读完你就理解paxos算法了！ 参考：https://www.douban.com/note/208430424/

Paxos，它是一个基于消息传递的一致性算法。Paxos只有在一个可信的计算环境中才能成立，这个环境是不会被入侵所破坏的。（不考虑网络的不稳定性、黑客攻击等因素）

Paxos描述了这样一个场景，有一个叫做Paxos的小岛(Island)上面住了一批居民，岛上面所有的事情由一些特殊的人决定，他们叫做议员(Senator)。议员的总数(Senator Count)是确定的，不能更改。岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一个编号(PID)，这个编号是一直增长的，不能倒退。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效。每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。如果议员收到小于等于当前编号的提议，他会拒绝，并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标：保证所有的议员对于提议都能达成一致的看法。

好，现在议会开始运作，所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议：将电费设定为1元/度。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1，于是他给所有议员发消息：1号提议，设定电费1元/度。其他议员收到消息以后查了一下记事本，哦，当前提议编号是0，这个提议可接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记录：当前提议编号为1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1号提议生效！收到的议员会修改他的记事本，将1好提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法令并告诉对方：1元/度。

现在看冲突的解决：假设总共有三个议员S1-S3，S1和S2同时发起了一个提议:1号提议，设定电费。S1想设为1元/度, S2想设为2元/度。结果S3先收到了S1的提议，于是他做了和前面同样的操作。紧接着他又收到了S2的提议，结果他一查记事本，咦，这个提议的编号小于等于我的当前编号1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，S1正式发布了提议: 1号提议生效。S2向S1或者S3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。

好，我觉得Paxos的精华就这么多内容。现在让我们来对号入座，看看在ZK Server里面Paxos是如何得以贯彻实施的。

小岛(Island)——ZK Server Cluster

议员(Senator)——ZK Server

提议(Proposal)——ZNode Change(Create/Delete/SetData…)

提议编号(PID)——Zxid(ZooKeeper Transaction Id)

正式法令——所有ZNode及其数据

貌似关键的概念都能一一对应上，但是等一下，Paxos岛上的议员应该是人人平等的吧，而ZK Server好像有一个Leader的概念。没错，其实Leader的概念也应该属于Paxos范畴的。如果议员人人平等，在某种情况下会由于提议的冲突而产生一个“活锁”（所谓活锁我的理解是大家都没有死，都在动，但是一直解决不了冲突问题）。Paxos的作者Lamport在他的文章”The Part-Time Parliament“中阐述了这个问题并给出了解决方案——在所有议员中设立一个总统，只有总统有权发出提议，如果议员有自己的提议，必须发给总统并由总统来提出。好，我们又多了一个角色：总统。

总统——ZK Server Leader

现在我们假设总统已经选好了，下面看看ZK Server是怎么实施的。

情况一：

屁民甲(Client)到某个议员(ZK Server)那里询问(Get)某条法令的情况(ZNode的数据)，议员毫不犹豫的拿出他的记事本(local storage)，查阅法令并告诉他结果，同时声明：我的数据不一定是最新的。你想要最新的数据？没问题，等着，等我找总统Sync一下再告诉你。

情况二：

屁民乙(Client)到某个议员(ZK Server)那里要求政府归还欠他的一万元钱，议员让他在办公室等着，自己将问题反映给了总统，总统询问所有议员的意见，多数议员表示欠屁民的钱一定要还，于是总统发表声明，从国库中拿出一万元还债，国库总资产由100万变成99万。屁民乙拿到钱回去了(Client函数返回)。

情况三：

总统突然挂了，议员接二连三的发现联系不上总统，于是各自发表声明，推选新的总统，总统大选期间政府停业，拒绝屁民的请求。

当然还有很多其他的情况，但这些情况总是能在Paxos的算法中找到原型并加以解决。这也正是我们认为Paxos是Zookeeper的灵魂的原因。当然ZK Server还有很多属于自己特性的东西：Session, Watcher，Version等。

ZAB原则

就是Zookeeper Atomic Broadcast-zookeeper原子广播协议。

原子：只有成功、失败，没有中间状态；

广播：分布式、多节点的。

消息广播

ZooKeeper消息广播

ZAB 协议的消息广播过程使用的是一个原子广播协议，类似一个 二阶段提交过程（2pc）。

对于客户端发送的写请求，全部由 Leader 接收，Leader 将请求封装成一个事务 Proposal，将其发送给所有 Follwer ，然后，根据所有 Follwer 的反馈，如果超过半数成功响应，则执行 commit 操作（先提交自己，再发送 commit 给所有 Follwer）。

这其中包含一些细节：

1、Leader 在收到客户端请求之后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一 ID，称为事务ID（ZXID），ZAB协议需要保证事务的顺序，因此必须将每一个事务按照 ZXID 进行先后排序然后处理。

2、在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，解除同步阻塞。

3、zookeeper集群中为保证任何所有进程能够有序的顺序执行，只能是 Leader 服务器接受写请求，即使是 Follower 服务器接受到客户端的请求，也会转发到 Leader 服务器进行处理。

那么问题来了，如果leader挂了呢？

Leader恢复

leader只有一个，那么就会存在单点故障问题，这时还能保证数据一致性吗？

ZAB协议规定：

1. 确保那些已经在 Leader 提交的事务最终会被所有服务器提交
2. 确保丢弃那些只在 Leader 提出/复制，但没有提交的事务

对此，如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群总所有机器编号（即 ZXID 最大）的事务，那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。

另外，如果有多台zk server的Zxid相同都是最大，那么选举myid最大的。

即：

1. 选经验最丰富的Zxid
2. myid最大的
3. 过半通过的数据才是真数据

小结

1. Paxos：一个新选举的主进程会进行两个阶段的工作，第一阶段被称为读阶段，在这个阶段中，这个新的主进程会通过和所有其他进程进行通信的方式来收集上一个主进程提出的提案，并将它们提交。第二阶段称为写阶段，在这个阶段，当前主进程开始提出自己的提案。
2. ZAB：ZAB协议在Paxos基础上，ZAB额外添加了一个同步阶段。在同步阶段之前，ZAB协议也存在一个和Paxos读阶段非常类似的过程，即发现阶段。在同步阶段，新的leader会确保存在过半的follower已经提交了之前leader周期中的所有事务proposal。一旦同步完成之后，ZAB就会执行和Paxos类似的写阶段。
3. ZK选举过程：
   • 3888端口保证两两通信
   • 只要任何人投票，都会触发那个准Leader发起自己的投票
   • 推选制：先比较zxid，如果zxid相同，再比较myid

END

推荐阅读

• 分布式高可用的ZooKeeper集群搭建与基本操作
• Elasticsearch初体验-创建Index，Document以及常见的ES查询
• 我用线程池ThreadPoolExecutor处理任务和Redis做缓存查询，将程序效率提升了5倍！
• 手撕Netty-用Java NIO完成Netty Reactor思想，助你理解Netty模型事件驱动

看完点赞，养成习惯。 举手之劳，赞有余香。