multi-paxos、raft和zab协议的核心区别_zab multi-paxso

背景介绍

Google Chubby的作者Mike Burrows曾说：“这个世界上只有一种一致性算法，那就是Paxos，其它算法都是残次品。”由此可见，raft、zab等一致性算法都是在paxos的基础上通过增加或者调整一些限制条件演进而来的。目前Paxos算法在Google的Chubby、MegaStore、Spanner等系统中得到了应用，而raft在redis集群的leader选举中有很好地应用，zab则是雅虎工程师针对zookeeper设计的分布式一致性算法。paxos实际上又分为Basic Paxos、Fast Paxos和Multi-Paxos，而前两者只能对一个值形成决议，因此它们几乎只是用来做理论研究，并不直接应用在实际工程中。因而本文后面提到的Paxos，实际上指的都是Multi-Paxos。

本文结合自己的理解，对这些算法在演进过程中所做的取舍进行分析，最终挖掘出这些算法的核心区别。个人愚见，不一定正确，欢迎交流讨论。本文不会具体介绍每种算法，如果不熟悉的可以先阅读文末的参考资料（有耐心的同学可以阅读参考资料中的两本书，没耐心的可以阅读参考资料中的相关博客即可）。

搜索介绍zookeeper方面的博客，可以发现海量的博客基本上都是从《从Paxos到ZooKeeper分布式一致性原理与实践》这本书上摘抄来的，可见这本书的影响力之大。客观地说，这本书从宏观上介绍了两阶段提交、Paxos和ZAB协议，对于从宏观上了解分布式一致性算法是非常不错的参考资料。本文的分析，也深度基于这本书。但本人愚见，正因为这本书是从宏观上进行介绍，所以对于很多细节，是值得进一步推敲的。

《从Paxos到ZooKeeper分布式一致性原理与实践》这本书中有一段话：“ZAB协议和Paxos算法的本质区别在于，两者的设计目标不太一样。ZAB协议主要用于构建一个高可用的分布式数据主备系统，例如ZooKeeper；而Paxos算法则是用于构建一个分布式一致性状态机系统。”这段话也是被海量博客所引用。但不知道读者看完这句话，会不会有这样的疑惑：“分布式数据库主备系统” 和 “分布式一致性状态机系统”有什么本质区别呢？尤其是当我看了大量的技术博客，甚至一些分布式教学视频之后，越来越觉得这两者没有本质的区别，至少对于分布式一致性算法来说没有区别。Google的Chubby就是用Paxos实现的，而ZooKeeper可以说是Chubby的开源版本。这意味着Paxos和Zab可以实现同样的功能，所以这肯定不是本文要给出的答案。为了寻找更深层次的答案，本文需要深入ZAB协议。

ZAB协议解读

《从Paxos到ZooKeeper分布式一致性原理与实践》这本书第4章在介绍崩溃恢复时提到，ZAB协议需要保证以下两条特性：

• ZAB协议需要确保那些已经在Leader服务器上commit的事务最终被所有服务器都commit
• ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务

而为了满足这两条特性，ZAB协议设计了这样一个Leader选举算法：保证新选举出来的leader服务器拥有集群中所有机器最高编号（即ZXID最大）的事务Proposal，那么就可以保证这个新选举出来的Leader一定具有所有已经被commit的提案。更为重要的是，如果让具有最高编号事务Proposal的机器来成为Leader，就可以省去Leader服务器检查Proposal的commit和丢弃工作这一步操作了。

看完书中的这段描述，我有两个疑惑，第一个疑惑是：这里的最高编号，其范围到底是指已经收到Commit消息的Proposal呢，还是包括那些尚未收到确认消息的Proposal呢？如下图所示，ZAB的提议提交采用了类似一个二阶段提交的过程。也就是说，Follower中存储的提议有两种可能的状态：已经收到Commit消息和未收到Commit消息。如果最高编号只是已经收到Commit消息的Proposal，那很显然，新选出来的Leader肯定需要确认其自身还未收到前一任Leader的Commit消息的Proposal是否需要被丢弃。而文中明确说到可以省去Leader服务器检查Proposal的commit和丢弃工作这一步操作。由此可知，其范围应该是包括那些尚未收到确认消息的Proposal，但这又引出了第二个疑惑。