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

saintyyu

发布于 2021-11-22 09:56:38

1.4K2

发布于 2021-11-22 09:56:38

文章被收录于专栏：IT专栏

背景介绍

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，但这又引出了第二个疑惑。

第二个疑惑是，第二个特性说“ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务”，那是不是说只要Leader所提出的Proposal被Leader以外的至少一台Follower所收到，即使收到该Proposal的机器的数量少于集群机器数的一半（比如集群有5台机器，Leader提交的Proposal只被一台Follower收到，然后Leader就宕机了，这意味着这个事务只被两台机所确认），最终也会被新的Leader给commit呢？从这本书的前后文来看，确实是只要有一台以上的机器收到了该Proposal，最终就会被commit。但这明显违背了大多数分布式算法使用的Quorum机制（确认机器数要超过一半以上）啊！

为了让大家对这两个问题有更加深刻的认识，我们考虑由五台机器构成的集群，考虑如下两种场景：

场景一、少数机器收到Proposal

Server1(Leader): P1 C1 P2
Server2: P1 C1 P2
Server3: P1 C1
Server4: P1 C1
Server5: P1 C1

场景一中，P1代表第一个Proposal，P2代表第二个Proposal；C1代表对第一个Proposal的Commit消息。场景一描述的是作为Leader的Server1在本机执行完P2，并将P2发送到Server2之后就宕机了或者和Server3、Server4、Server5之间的网络不通了的场景。按照ZAB协议，目前Server2拥有最大值的ZXID，因而Server2会成为新的Leader。那么Server2应该继续commit还是舍弃P2呢？

场景二、多数机器收到Proposal

Server1(Leader): P1 C1 P2
Server2: P1 C1 P2
Server3: P1 C1 P2
Server4: P1 C1 P2
Server5: P1 C1

和场景一不同的是，在作为Leader的Server1宕机前，除了Server5没收到P2之外，其它机器都收到了P2消息。此时Server2～Server4拥有相同的ZXID，所以sid最大的Server4会成为新的Leader。那么对于P2，新的Leader应该是继续commit呢还是舍弃呢？

按照通常的认知，基于Quorum机制，我们认为场景一中的P2应该被舍弃，而场景二中的P2应该继续被提交并被commit。那么ZAB协议是如何选择的呢？带着这个疑惑，我阅读了《ZooKeeper Distributed Process COORDINATION》这本书。摘抄这本书的相关内容：

Most of the difficulty with implementing a broadcast protocol is related to the presence of concurrent leaders, not necessarily in a split-brain scenario. Multiple concurrent leaders could make servers commit transactions out of order or skip transactions altogether, which leaves servers with inconsistent states. Preventing the system from ever having two servers believing they are leaders concurrently is very hard. Timing issues and dropped messages might lead to such scenarios, so the broadcast protocol cannot rely on this assumption. To get around this problem, Zab guarantees that:

An elected leader has committed all transactions that will ever be committed from previous epochs before it starts broadcasting new transactions.
At no point in time will two servers have a quorum of supporters.

To implement the first requirement, a leader does not become active until it makes sure that a quorum of servers agrees on the state it should start with for the new epoch. The initial state of an epoch must encompass all transactions that have been previously committed, and possibly some other ones that had been accepted before but not committed.

这段话是说，一方面，除了“脑裂”之外，实现一个包含多个Leader的分布式一致性广播协议是非常困难的（ps：paxos就支持多Leader），因为多个Leader会导致Proposal的无序和丢失，从而导致集群的不一致；而另一方面，避免集群在任何时刻都只有一个Leader也是非常困难的。所以Zab协议为了解决这个问题，保证了以下两点要求：

一个新选举出来的Leader必须要先依次commit前一个Leader将会commit的所有Proposal，然后才能开始提交自身Proposal。
任何时刻，都不会有两台以上的服务器获得了超过半数机器支持。

为了实现第一个要求，新选出来的Leader需要确保它已经获得了超过半数的机器支持，然后它才能以Leader身份运行。而且，新的Leader的初始状态必须要保证前一任Leader提交的两类Proposal都被commit：一类是已经被commit的Proposal，还有一类就是已经被接受但还没被commit。

从这段话明确说了，新的Leader必须要保证：只要旧的Leader提交的Proposal被除了旧Leader自身以外的Follower接受（即便这些Follower还未收到commit消息，即便收到这条消息的机器数还不过半），这些Proposal都需要被新的Leader提交并最终被commit。也就是说，我们前面提到的场景一和场景二，对于Zab协议来说，最终都是会被新的Leader提交并最终被commit。

到这里，可能你还是会疑惑：说好的Quorum机制呢？其实，绝大多数的书和博客都没明确指出的是：对于ZooKeeper来说，Quorum机制只在一个Leader的广播阶段有效，对于新旧Leader的变更期间是无效的！对于发现和同步阶段，不同的算法，基于不同的考量，会选择不同的机制。由参考博客5可知，对于RAFT算法，在读阶段（相当于ZAB的发现和同步），即便前一任Leader提出的Proposal已经被半数的机器所接受，只要还没被commit，在极端情况下，都有可能被覆盖掉。因为新Leader只关注自身还没被commit的Proposal，而不关心其它机器的未commit的Proposal。

实际上，对于分布式数据的一致性问题，如果站在调用者（客户端）的角度来思考，当客户端发出的写操作请求，在集群执行该请求期间，恰巧发生了Leader更换，那么客户端最终收到的返回一定是一个不确定的结果（可能成功，也可能失败）。因而对于集群本身来讲，针对具体的业务场景，是采用消极的全部丢弃，还是采用积极地全部内部补偿，或者是介于消极和积极之间的某种策略，我认为都是合理的。但总的来说，无论这些算法采用什么样的策略，保证集群数据的一致性是必要的前提。

ZAB和RAFT以及PAXOS核心区别

由此，本文总结了这三种算法的三个核心的区别（欢迎拍砖）：

Leader候选机器的差异

ZAB是具有最大ZXID编号（包括未commit的Proposal）的机器才有资格成为新的Leader；而RAFT则是具有最大已commit编号（不包括未commit的Proposal）的机器才有资格成为新的Leader；PAXOS则是任意机器都可以成为新的Leader。由此可见，对于ZAB协议，新任Leader无需考虑自身还未被commit的Proposal是该被舍弃还是该被继续提交（因为全都需要被继续提交，积极策略）；对于RAFT协议，新的Leader只会关心自身机器上还未commit的Proposal，因而即使某一个Proposal已经被其它半数以上的机器确认，也可能会被覆盖（消极策略）；对于PAXOS，由于任意机器都可以成为新的Leader，因而新的Leader需要和其它Acceptor进行通信，以确认哪些Proposal该提交，哪些该舍弃（本质上新旧Leader相当于同时有多个Leader的场景，介于积极和消极之间）。

Quorum机制的作用范围差异

对于ZAB和RAFT，Quorum机制只在正常的Leader任期（广播阶段）内有效，对于同步/读阶段，两者都是以自身的Proposal为准，而不会关注其它机器的情况，其中ZAB是因为自身拥有了最新的Proposal，所以不需要关心；对于Paxos协议，Quorum机制在读阶段和写阶段（相当于ZAB的广播阶段）都有效，因而在读阶段需要和其它Acceptor进行沟通，以确认哪些该提交，哪些该作废。

Leader数量的差异（不考虑极端情况）

ZAB和RAFT都是单Leader，而PAXOS则支持多Leader（当然，工业应用中，绝大多数还是采用单Leader策略）。

新Leader处理旧Leader还未commit消息的差异

《ZooKeeper Distributed Process COORDINATION》这本书说到，当新的Leader在恢复阶段，会尝试将本服务器上还未同步的消息同步给所有Follower，不过同步时使用的epoch将不再是旧Leader的epoch，而是新Leader的epoch，这意味着新的Leader需要修改自身的日志记录中的epoch值；相反，RAFT论文中说到，新的Leader不会直接将本服务器上旧term的未commit消息直接同步给Follower，而是通过将本服务器上新term的新的消息同步给Follower并最终commit的机制，来间接提交旧term的未commit的消息（Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property）。当然，RAFT不用新term提交旧消息的另一个原因是用旧的term便于进行日志追踪（reason about）。

ZAB协议的考量

本质上讲，分布式一致性问题可以分为两种：分布式事务和分布式主备。其中分布式事务是指一个写操作请求，对应多个不同类型的写操作，比如跨银行转账，一定是一个银行账号存款减少，另一个银行账号存款增加。而分布式主备则是指一个写操作请求，对应多个相同类型的写操作，比如ZooKeeper集群，在Leader机器上的写操作，最终是会在集群内的所有备份机器上执行同样的操作。

以上两种一致性问题最大的差异是，在分布式事务中，一个写操作请求对应的所有写操作之间成功与失败并不相关，即一个写操作的成功，并不能保证其它写操作也能成功（一个账号存款减少，不能保证另一个账号一定能存款增加）。与之不同的是，在分布式主备系统中，一个写操作请求，如果在Leader机器上执行成功，那么理论上在备用机器上也能成功（不考虑机器不存活的场景）。

ZAB之所以采用比较积极的策略（Leader变更期间，旧Leader的提议只要被任意Follower收到，则一律提交），也正是因为其设计的初衷是服务于分布式主备系统。因为客户端的一个写请求，Zookeeper首先会在Leader上进行写入，写成功之后，才会分发给Follower。这就意味着，如果Leader不出问题的话，这些Proposal最终肯定会在所有Follower上也写成功。

最后

最后，再看看前面提到的ZAB的一个特性——ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务。实际上这个特性在极端情况下，也是做不到的。还是考虑场景一：

Server1(Leader): P1 C1 P2
Server2: P1 C1 P2
Server3: P1 C1
Server4: P1 C1
Server5: P1 C1

假设作为Leader的Server1在本地提交P2，并将P2发送到Server2之后就宕机了，而此时恰巧Sever2也宕机了。这个时候，Server3～Server5拥有相同的ZXID，所以Server5会成为新的Leader，但它却无法将P2进行提交并commit，因为它没有收到过P2。当Server5进行正常的广播的时候，Server1和Server2活了过来，这个时候，他们肯定只能回退P2。