Paxos，Raft，ZAB的差异对比

原 作者 李兆龙 | 发表于 | 分类于 2018级

在这里插入图片描述本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
在这里插入图片描述本作品 (李兆龙 博文, 由 李兆龙 创作)，由 李兆龙 确认，转载请注明版权。

文章目录

引言

对于ZAB与Paxos协议并不了解的我写这篇文章属实有点误导人的感觉，所以把这篇文章看成一篇消遣娱乐的爽文即可。

虽然平时Raft协议我们听的比较多，但是确实是ZAB诞生的更早，ZAB在2008年就被提出了[1]，而Raft在2014年才被提出[2]。因为是先读的[2]，所以在读[1]的时候在协议部分真的是非常类似，我一度以为ZAB抄Raft，后来才知道年轻了。当然它们的老大哥都是multi-Paxos，基本都是在Paxos的光芒照耀下对multi-Paxos进行算法结构上的修改，最终演化成另外一个不同的算法。

还有就是为什么在读[1]的时候会有相似的感觉呢，现在看来是因为[1]中对于选举部分并没有描述（一句话带过）。 对于ZAB描述最清楚的应该就是[3]了，[3]基本阐述清楚了ZAB，而[1]就显得太为简略了，不想看paper可以看[4]中的描述，相当于是一个[3]简略了很多的版本，但是看清楚流程问题不大。

这Raft与ZAB因为都是基于multi-Paxos算法进行设计，所以三者们之间的区别很大一部分就在选举上，而日志同步的过程基本类似，就是leader（proposer）接收一个来自客户端的请求，然后广播到Follower（Accepter），接收到过半Ack时回复客户端。所以讨论它们之间的差别时选举以及涉及到的信息是一个很重要的问题。

文首已经说到，我对于ZAB与Paxos协议并不了解，因为没有看过开源的实现或者尝试自己实现一个，得到的信息基本是来自于论文和博客，所以很多地方可能会出现与实现不符的问题；而Raft我在ChubbyGo中有实现过，所以准确性会高一些。

背景概述

首先Paxos作为此领域的祖师爷，必然是最为闪亮的一个，但是这个算法有一个问题，就是不但难以理解，而且难以实现；因为Lamport开始时提出的是Base-Paxos，其确实解决了分布式中的一致性问题，但是却很难无法被应用于实际生活中。因为Base-Paxos是一个只能针对于单提案生效的算法，所以基本上所有Paxos的实现都是基于multi-Paxos的，同时也抽象出了Leader这个概念。

而Raft和ZAB在此基础上做出了一定算法结构上的改变，最终演化为另一种一致性算法；前者为了可理解性，而后者为了zk的高性能。虽然是这样，但是还是有很多人愿意称Raft和ZAB为特殊的multi-Paxos。

本篇文章不描述介绍算法相关的的内容，对三种算法不了解的朋友建议先参考如下资料，再看后面的内容，了解的话就不用浪费时间啦：

  1. Paxos：[18][19]
  2. Raft：[2]
  3. ZAB：[1][3][4][7]

差异对比

目前计划分为如下问题进行讨论：

    1. Leader选举
      • 如何选举
      • 选举的信息
      • 选举的触发
    1. 上一轮次的数据
      • 如何处理上一轮未提交的日志
      • 脑裂问题
    1. 请求处理过程
      • 一般流程
      • 日志的连续性
      • 请求的顺序性（异常时的安全性保证）

Leader选举

如何选举

三个算法的差异还是比较大的。

我们知道Raft是一个强领导人的一致性协议，领导人拥有最大的话语权，因为算法保证Leader一定拥有最新最全的日志，这也让Raft的选举非常的简单，也就是在每个Term中只有一票，只会投票给Term与LogIndex大于自己的结点，收到选票大于一半时选举成功，后面的心跳包中会宣布自己的身份。当然这种方法可能会在大多数结点存活的时候仍出现选举失败的情况，因为可能出现瓜分选票的情况，解决的方法也很简单，就是在ElectionTimeOut上下功夫，让每一个结点的超时时间加上随机数，这就让出现瓜分选票的情况大大减少了。对于随机数区间的选择可以参考[2]9.3。

相比之下，ZAB和Paxos的选举就复杂的多，ZAB的选举可以参考[22]。

至于Paxos的选举，一般来说有两种方法，一种是简单方法，估计是Lamport提出的，不过好像生产中很少用；另一种是基于租约的选举。

下面的leader选举算法来自standford的课程ppt：
在这里插入图片描述
显然这种方法很好理解，且用于选举的开销较小，就是很容易造成多Leader的情况，但是在Paxos中不影响正确性，在[19]中我们可以看到Base-Paxos保证了多Leader的情况下仍保持一致。

还有一种方法是基于租约的，这种算法保证只有一个Leader的存在。
在这里插入图片描述
其实就是把成为Leader的消息看做是一条日志，让Paxos保证一致，这也可以看出这种选举方法其实和Paxos是完全解耦合的。

具体的过程就是：

  1. 把BeMaster看做是一个Peoposer操作，其中携带自己的节点信息。
  2. 状态机中的callback做两件事情，第一：发现Value的节点非自己，则等待timeout时间再发起BeMaster。第二：发现Value的节点是自己，那么将自己提升为Master，并在T(BeMaster) + timeout后过期。

通过以上我们可以看出显然基于租约的选举同一时刻最多只能有一个结点为Leader，但是不保证这个Leader拥有最新日志，

具体可以参考[21]。

选举信息

Fast Leader Election选举请求信息为 （ P . v o t e , P . i d , P . s t a t e , P . r o u n d ） ， P . v o t e ← （ P . l a s t Z x i d , P . i d ） ； （P.vote,P.id,P.state,P.round），P.vote←（P.lastZxid,P.id）； （P.vote,P.id,P.state,P.round），P.vote←（P.lastZxid,P.id）；

而Raft为 （ t e r m , c a n d i d a t e I d , l a s t L o g I n d e x , l a s t L o g T e r m ） （term,candidateId,lastLogIndex ,lastLogTerm） （term,candidateId,lastLogIndex,lastLogTerm）

Paxos为 a c c e p t ( n , v , i n d e x , f i r s t U n c h o o s e n I n d e x ) accept(n, v, index, firstUnchoosenIndex) accept(n,v,index,firstUnchoosenIndex)

其他两个我在[22]中解释过了。Paxos中的index是为了区分不同的Paxos实例，firstUnchoosenIndex是为了同步结点间已提交的数据。可参考[17]。

选举的触发

对于Raft和ZAB来说，其实就是超时后触发超时事件，进行新一轮选举，但是Raft只有Follower可以发起选举；ZAB则是Leader和Follower都可以发起选举。
在这里插入图片描述
显然我们可以看到Raft算法中Leader无法成为Candidate。

leader和follower都有各自的检测超时方式，leader是检测是否过半follower心跳回复了，follower检测leader是否发送心跳了。

一旦leader检测失败，则leader进入LOOKING状态，其他follower过一段时间因收不到leader心跳也会进入LOOKING状态，从而出发新的leader选举。

一旦follower检测失败了，则该follower进入LOOKING状态，此时如果leader和其他follower仍然保持良好，则该follower仍然是去学习上述leader的投票，而不是触发新一轮的leader选举；反之则是触发新一轮选举。

至于Paxos，则是与选举算法有关，本文呈现的两种方法对应了两种不同的选举触发条件，一个是检测到自己的ID最大的时候；基于租约的选举则是在超时之后进行选举，其实就是去进行一轮Base-Paxos。

上一轮次的数据

如何处理上一轮未提交的日志

这是一个非常有意思的问题，话说的再清楚一点就是如何处理上一轮未达成一致的日志，其实这个问题与协议本身无关，而与应用有关，因为无论怎么处理，其实从协议的角度来说都是可以达成一致的。但是对应用就不一样了，处理的策略不妥可能会出现一种称为“幽灵复现”的问题。

问题的本质就是分布式系统中复杂的根源所在，即“第三态”问题，分布式系统中RPC请求存在三种情况，成功，失败与超时。在超时时要求后面每一次读取可以看到上一次读取结果。这其实很不好搞。拿Raft举个例子：

假设存在如下日志：
在这里插入图片描述

  1. A节点为leader，Log entry 5，6内容还没有commit，A节点发生宕机。这个时候client 无法查询到 Log entry 5，6里面的内容。
  2. B成为Leader, B中Log entry 3, 4内容复制到C中（心跳包）， 并且在B为主的期间内没有写入任何内容。
  3. A 恢复并且B、C发生重启，A又重新选为leader, 那么Log entry 5, 6内容又被复制到B和C中，这个时候client再查询就查询到Log entry 5, 6 里面的内容了。

这就是一个幽灵复现的场景，比如客户刚刚买了个手机，返回超时，然后查一下购买记录发现购买没有成功，客户大概率会重新购买一次，这样在后面的Term中就会存在两条购买记录，客户一定不希望看到这种情况。

对于Raft来说只需要在Leader选举成功后写入一条空日志（需要被Commit）就好了，这样的话就不会出现上述问题了。

一般过程中Raft如何对待上一Term的日志呢？

在这里插入图片描述
其实就是不提交，就算已经拷贝到了大多数结点上也不会提交，除非在Term内也提交了一条日志，上一条日志才会被顺带提交，也就是上图中的（e）。

具体可以参考[2]5.4.2。

ZAB协议的解决思路不太一样。我们还是拿上面的图：

在这里插入图片描述

首先A的Log entry 5，6没有被提交，A宕机。假设B晋升，但是没有写入任何一条Log entry，意味着B的最后一条日志zxid依然小于A的最后一条日志的zxid，如果A恢复，就会重新称为Leader，此时会在Recovery同步数据，从而出现幽灵复现的问题，解决的思路就是持久化CurrentEpoch，在请求选举时带上CurrentEpoch，这样就没有这个问题了。

ZAB如何对待上一Term的日志呢？采取激进的策略，对于所有过半还是未过半的日志都判定为提交，都将其应用到状态机中。

至于Paxos如何避免，这个牵扯到日志，所以我们先不谈。

脑裂问题

脑裂（split-brain）问题其实就是说集群中可能会出现两个主结点，事实上Raft和ZAB在正常情况下不会出现这个问题，因为只有在获得大于二分之一结点数量的同意时操作才有效，虽然分区可能使得出现多个主，但是其中最多有一个可以工作。

Paxos允许多主，且在多主情况下仍保证正确性，这主要是由Base-Paxos来实现的，多主可以并发写入，不过可能会出现活锁问题。具体可参考[19]。

Paxos的这个特性让我觉得整个Multi-paxos就类似于一个P2P网络！

所有节点互相双向同步，对所有unchoose的日志进行不断确认的过程（反熵的过程）！！这个网络中，可以出现多个leader，可能出现多个leader来回切换，这都不影响正确性。

请求处理过程

一般流程

三者在确定了Leader以后可以认为基本过程相同，但是如何把日志已经提交这个信息传播出去的过程有一点区别。

  1. client连接follower或者leader，如果连接的是follower则，follower会把client的请求(写请求，读请求则自身就可以直接处理)转发到leader
  2. leader接收到client的请求，将该请求转换成entry，写入到自己的日志中，得到在日志中的index，会将该entry发送给所有的follower(实际上是批量的entries)
  3. follower接收到leader的AppendEntries RPC请求之后，会将leader传过来的批量entries写入到文件中（通常并没有立即刷新到磁盘），然后向leader回复OK

以上为Raft的过程，其他两个算法与其基本相同，差别就是名词。

Raft和Paxos 选择在各种交互的包中放入最后一条被提交日志的下标，以此同步日志。而ZAB则会向所有的follower发送一个提交日志的请求，同时leader自己也会提交该议案，应用到自己的状态机中，完毕后回复客户端。

日志的连续性

显然Raft的日志是连续的（日志匹配原则），这使得Leader在拥有最新的日志时也拥有了最全的日志，也就是在Raft中数据的流向是单向的，即从Leader到Follower，这使得整个过程非常简单，且易于理解。

而Paxos的日志是不连续的，因为因为当前leader再上一任leader的任期内可能错过了一些日志的同步，而这些日志在其他机器上形成多了多数派。由于logID连续递增，被错过的日志就成了连续logID连续递增序列中的“空洞”，需要通过重确认来补全这些“空洞”位置的日志。而每一次重确认其实都需要一轮完整的Paxos过程。

可能有些日志在恢复前确实未形成多数派备份，需要通过重新执行Paxos来把这些日志重新持久化才能回放。这种不管日志是否曾经形成多数派备份，都重新尝试持久化的原则，这被称为“最大commit原则”，这是因为在持有日志的结点宕机是我们没办法区分某个日志是否已经被提交。可以参考[24]。

当然这也可能造成幽灵复现问题，可以使用epochID，提交日志时如果上一条Log entry epochID大于本条（为了防止两个leader，选主成功时会执行一条StartWorking日志，所以本epoch必定有新日志，以此拒绝幽灵日志），证明本条是幽灵日志[11]。

而ZAB的日志到底是不是连续的就比较让人疑惑了，我找了一些博客，有些说是有些说不是。文档中也没找到，所以在知乎上提了问题，看后面有没有人解答吧。Zookeeper的ZAB协议到底允许日志空洞吗？

从[25]的讨论中我们可以看出日志的不连续在提交的事务较多时对稳定性和性能有帮助。

请求的连续性

即正常情况下先到达leader的请求，先被应用到状态机。那么在异常出现时如何来保证顺序呢？这其实类似于协议如何保证正确性。

首先是Raft，因为日志连续，所以过程比较简单，我们来看看[2]5.3中的一幅图：
在这里插入图片描述

当一个 leader 成功当选时（最上面那条日志），follower 可能是（a-f）中的任何情况。每一个盒子表示一个日志条目；里面的数字表示任期号。Follower 可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。例如，场景 f 可能这样发生，f 对应的服务器在任期 2 的时候是 leader ，追加了一些日志条目到自己的日志中，一条都还没提交（commit）就崩溃了；该服务器很快重启，在任期 3 重新被选为 leader，又追加了一些日志条目到自己的日志中；在这些任期 2 和任期 3 中的日志都还没被提交之前，该服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

同步的过程其实比较简单，就是Leader在心跳包中附带最后一条Commit日志的index与Term，然后Follower在同一index处比较Term，一直比较到Leader发来的Term的日志被比较完了，回复index，最差的情况下几个（相差日志的Term总数）来回就能找到不一致的位置。

而对于ZAB来说，因为在Leader成功以后会有一个Recovery， 所以绝对不会出现像上图那样乱的日志，所以只有一种情况需要同步日志，就是Follower宕机，重启后恢复日志。

[9]中的描述如下：

ZooKeeper：重启之后，需要和当前leader数据之间进行差异的确定，同时期间又有新的请求到来，所以需要暂时获取leader数据的读锁，禁止此期间的数据更改，先将差异的数据先放入队列，差异确定完毕之后，还需要将leader中已提交的议案和未提交的议案也全部放入队列，即ZooKeeper的如下2个集合数据
ConcurrentMap<Long, Proposal> outstandingProposals
Leader拥有的属性，每当提出一个议案，都会将该议案存放至outstandingProposals，一旦议案被过半认同了，就要提交该议案，则从outstandingProposals中删除该议案
ConcurrentLinkedQueue toBeApplied
Leader拥有的属性，每当准备提交一个议案，就会将该议案存放至该列表中，一旦议案应用到ZooKeeper的内存树中了，然后就可以将该议案从toBeApplied中删除
然后再释放读锁，允许leader进行处理写数据的请求，该请求自然就添加在了上述队列的后面，从而保证了队列中的数据是有序的，从而保证发给follower的数据是有序的，follower也是一个个进行确认的，所以对于leader的回复也是有序的

而Paxos的日志是不连续的，Leade也不一定拥有最新的，所以需要进行日志同步，首先需要确认同步的结束位置，所以需要向集群内其他server发送请求，查询每个server本地的最大logID，并从多数派的应答中选择最大的logID作为重确认的结束位置，就像上面说的，每一次重确认都是一次一轮完整的Paxos过程。当然有时收到的多数派也不存在此位置日志，就填充为空。

一点想法

首先需要阐明的是Raft不过是Paxos的一个变种，且一般情况下性能基本与Paxos持平。但是相比之下对于冲突的解决Raft更像是一个悲观版本，因为只有Leader可以写入；而multi-Paxos则是一个乐观版本，因为多个Proposer可以并发的执行写操作（虽然有活锁的风险），有Master只是为了提高性能。这也是我上面说Paxos像是一个P2P结构的原因。

[25]中的描述也很有意思，允许空洞的日志在处理事务时有得天独厚的优势，而像Raft这样强制日志有序在极端条件下是一个无法忽视的潜在性能和稳定性风险。

ZAB在被应用时Raft还没出现，其本身也可以看做一个特殊的multi-Paxos，其在算法上比Paxos好懂，比Raft难懂，那么为什么有了Paxos还要开发一个ZAB呢，在[1]中我们可以找到一些线索，ZooKeeper需要保证客户端角度的FIFO语义，但是基础的multi-Paxos却并不做这样的保证。multi-Paxos只保证了所有节点的日志顺序一模一样，但对于每个节点自身来说，可以认为它的日志并没有所谓的“顺序”。

按照[17]中的话来描述就是这样：

1）假如1个客户端，连续发送了2条日志a, b(a没有收到回复，就发出了b)。那对于服务器来讲，存储顺序可能是a,b；也可能是b，a；也可能a, b之间还插入了其他客户端发来的日志！

2）假如1个客户端，连续发送了2条日志a, b(a收到回复之后，再发出的b)。那对于服务器来讲，存储顺序可能是a, b；也可能是a, xxx, b。但不会出现b在a的前面。

出现这个问题的原因就是允许并发写入，显然上面提到的并发优势到了这里成了一个绊脚石。

我想是因为这个原因所以开发了ZAB。

简单总结下各个算法的优缺点：

Raft优点：

  1. 比其他两者算法更容易理解，⽽且更容易工程化实现。论文中就给出了伪码。
  2. Raft与Paxos一样高效，效率上Raft等价于(multi-)Paxos。
  3. Raft的日志设计使得整个算法非常的简洁，分成了几个功能独立的子版块。

Raft缺点：

  1. 无法容忍拜占庭将军问题，当然其他两者也不能容忍，后面就不提了。
  2. 总的来说Raft只是Paxos实现的一种，但是Raft身上的限制比较多，而Paxos在算法层面上更通用，所以相比于Raft，在Paxos的基础上进行优化，上限应该会更高，比如上面提到了两点。
  3. 因为日志的设计只能串行写入，并发场景下效率有损失；且在多事务的情况下有可能损害性能和稳定性。

Paxos优点：

  1. 高效。
  2. Paxos算法有严格的数学证明，系统设计精妙。

Paxos缺点：

  1. 难以理解。
  2. 难以实现，达到工业级性能需要进行不同程度的工程优化，而有时工程设计的偏差会造成整个系统的崩溃。
  3. Base-Paxos可能出现活锁问题。
  4. 对于客户端来说无法满足操作的全序关系。

ZAB优点：

  1. 保证了客户端FIFO的语义。
  2. 比Paxos简单。

很遗憾，对ZAB了解太少，不知道ZAB有什么缺点。

总结

Paxos水太深。

为了解决活锁问题，出现了multi-paxos；

为了解决通信次数较多的问题，出现了fast-paxos；

为了尽量减少冲突，出现了epaxos。

你可能会说这么多变种该怎么学呢，光看着就已经让人头疼了。[16]中有如下文字：

这几种主流的consensus协议其实都是在做细微部分的tradeoff，如你提到的无论multipaxos（如Megastore，几乎是唯一的可以找到的业界multipaxos的公开细节，paper复杂晦涩）还是Raft其实都是应用驱动做tradeoff，前者注重write的latency后者注重recovery的简单性和速度（Megastore recover的复杂性可参考其catchup的流程），决定了leader candidate的条件不同；书中还提到其他的tradoff：consistent read的tradeoff (quorum lease)；disk access和message rounds的tradeoff (multipaxos的explicit Accept variation)

可以看到实际上工业中一致性协议的使用还是应用驱动的，根据需求在不同的地方做权衡。不过头还是有点疼。

这篇文章只是起点，后面如果可以深入到源码的话还会回来完善这篇文章的。

参考：

  1. 论文《Zab: A simple totally ordered broadcast protocol 》
  2. 论文《In Search of an Understandable Consensus Algorithm(Extended Version)》
  3. 论文《ZooKeeper’s atomic broadcast protocol: Theory and practice》
  4. gitee《百度开源/braft ZAB协议简介》
  5. 知乎《raft协议和zab协议有啥区别？》
  6. https://time.geekbang.org/column/article/143329
  7. 博客《深入浅出Zookeeper（一） Zookeeper架构及FastLeaderElection机制》
  8. 博客《简单对比 Raft 及 ZAB 协议》
  9. 博客《Raft对比ZAB协议》
  10. 博客《Zab vs. Paxos》
  11. 博客《如何解决分布式系统中的“幽灵复现”？》
  12. 博客《Raft Vs Zab》
  13. 博客《Vive La Différence: Paxos vs Viewstamped Replication vs Zab》
  14. 博客《state machine replication vs primary backup system》
  15. 博客《理解分布式一致性:Paxos协议之Multi-Paxos》
  16. 知乎《raft算法与paxos算法相比有什么优势，使用场景有什么差异？》
  17. 博客《Multi-Paxos》
  18. 论文《Paxos Made Simple》
  19. 博客《Paxos算法概述与推导》
  20. 博客《ZooKeeper在分布式环境中的假死脑裂》
  21. 博客《Paxos理论介绍(3): Master选举》
  22. 博客《对于 Fast Leader Election 机制的探究》
  23. 博客《Database · 原理介绍 · 关于Paxos 幽灵复现问题》
  24. 博客《使用Multi-Paxos协议的日志同步与恢复》
  25. 知乎《OceanBase的一致性协议为什么选择 paxos而不是raft?》
  26. 博客《共识算法系列：Raft算法关键点综述、优缺点总结》
  27. 博客《为什么选择zab协议》
  28. 论文《Paxos Made live》