Paxos 与 Raft 区别

Raft 协议比 paxos 的优点是 容易理解，容易实现。它强化了 leader 的地位，把整个协议可以清楚的分割成两个部分，并利用日志的连续性做了一些简化： （1）Leader 在时。由 Leader 向 Follower 同步日志 （2）Leader 挂掉了，选一个新 Leader，Leader 选举算法。

但是本质上来说，它容易的地方在于流程清晰，描述更清晰，关键之处都给出了伪代码级别的描述，可以直接用于实现，而 paxos 最初的描述是针对非常理论的一致性问题，真正能应用于工程实现的 mulit-paxos，Lamport 老爷爷就提了个大概，之后也有人尝试对 multi-paxos 做出更为完整详细的描述，但是每个人描述的都不大一样。

Zookeeper 的 ZAB，Viewstamped Replication（VR），raft，multi-paxos，这些都可以被称之为 Leader-based一致性协议。不同的是，multi-paxos leader 是作为对经典 paxos 的优化而提出，通过选择一个 proposer 作为 leader 降低多个 proposer 引起冲突的频率，合并阶段一从而将一次决议的平均消息代价缩小到最优的两次，实际上就算有多个 leader 存在，算法还是安全的，只是退化为经典的paxos算法。而经典的 paxos，从一个提案被提出到被接受分为两个阶段，第一个阶段去询问值，第二阶段根据询问的结果提出值。这两个阶段是无法分割的，两个阶段的每个细节都是精心设计的，相互关联，共同保障了协议的一致性。而 VR,ZAB,Raft 这些强调合法 leader 的唯一性协议，它们直接从 leader 的角度描述协议的流程，也从 leader 的角度出发论证正确性。但是实际上它们使用了和 Paxos 完全一样的原理来保证协议的安全性，当同时存在多个节点同时尝试成为 leader 或者不知一个节点认为自己时 leader 时，本质上它们和经典 Paxos 中多个 proposer 并存的情形没什么不同。

Paxos 和 raft 都是一旦一个 entries（raft 协议叫日志，paxos 叫提案，叫法而已）得到多数派的赞成，这个 entries 就会定下来，不丢失，值不更改，最终所有节点都会赞成它。Paxos 中称为提案被决定，Raft,ZAB,VR 称为日志被提交，这只是说法问题。一个日志一旦被提交(或者决定），就不会丢失，也不可能更改，这一点这 4 个协议都是一致的。Multi-paxos和 Raft 都用一个数字来标识 leader 的合法性，multi-paxos 中叫 proposer-id，Raft 叫 term，意义是一样的，multi-paxos proposer-id 最大的 Leader 提出的决议才是有效的，raft协议中 term 最大的 leader 才是合法的。实际上 raft 协议在 leader 选举阶段，由于老 leader 可能也还存活，也会存在不只一个 leader 的情形，只是不存在 term 一样的两个 leader，因为选举算法要求 leader 得到同一个 term 的多数派的同意，同时赞同的成员会承诺不接受 term 更小的任何消息。这样可以根据 term 大小来区分谁是合法的 leader。Multi-paxos 的区分 leader 的合法性策略其实是一样的，谁的proproser-id大谁合法，而 proposer-id 是唯一的。因此它们其实在同一个时刻，都只会存在一个合法的 leader。同时 raft 协议的 Leader 选举算法，新选举出的 Leader 已经拥有全部的可以被提交的日志，而 multi-paxos 择不需要保证这一点，这也意味 multi-paxos 需要额外的流程从其它节点获取已经被提交的日志。因此 raft 协议日志可以简单的只从 leader 流向 follower 在 raft 协议中，而 multi-paxos 则需要额外的流程补全已提交的日志。需要注意的是日志可以被提交和日志已经被提交是两个概念，它们的区别就像是我前方有块石头和我得知我前方有块石头。但是实际上，Raft 和multi-Paxos一旦日志可以被提交，就能会保证不丢失，multi-paxos 天然保证了这一点，这也是为什么新 leader 对于尚未被确认已经提交的日志需要重新执行经典 paxos 的阶段一，来补全可能缺失的已经被提交的日志，Raft 协议通过强制新 Leader 首先提交一个本 term 的 no-op 日志，配合前面提到的 Leader 选举算法所保证的性质，确保了这一点。一条日志一旦被多数派的节点写入本地日志文件中，就可以被提交，但是 leader 只有得知这一点后，才会真正 commit 这条日志，此时日志才是已经被提交的。

Raft 协议强调日志的连续性，multi-paxos 则允许日志有空洞。日志的连续性蕴含了这样一条性质：如果两个不同节点上相同序号的日志，只要 term 相同，那么这两条日志必然相同，且这和这之前的日志必然也相同的，这使得 leader 想 follower 同步日志时，比对日志非常的快速和方便；同时 Raft 协议中日志的 commit（提交）也是连续的，一条日志被提交，代表这条日志之前所有的日志都已被提交，一条日志可以被提交，代表之前所有的日志都可以被提交。日志的连续性使得 Raft 协议中，知道一个节点的日志情况非常简单，只需要获取它最后一条日志的序号和 term。可以举个列子，A,B,C 三台机器，C 是 Leader，term 是 3，A 告诉 C 它们最后一个日志的序列号都是 4，term 都是 3，那么 C 就知道 A 肯定有序列号为 1,2,3,4 的日志，而且和 C 中的序列号为 1,2,3,4 的日志一样，这是 raft 协议日志的连续性所强调的，好了那么 Leader 知道日志 1，2，3，4 已经被多数派（A,C)拥有了，可以提交了。同时，这也保证 raft 协议在 leader 选举的时候，一个多数派里必然存在一个节点拥有全部的已提交的日志，这是由于最后一条被 commit 的日志，至少被多数派记录，而由于日志的连续性，拥有最后一条 commit 的日志也就意味着拥有全部的 commit 日志，即至少有一个多数派拥有所有已 commit 的日志。并且只需要从一个多数集中选择最后出最后一条日志 term 最大且序号最大的节点作为 leader，新 leader 必定是拥有全部已 commit 的日志(关于这一点的论证，可以通过反证法思考一下，多数集中节点 A 拥有最后一条已 commit 的日志，但是 B 没有，而 B 当选 leader。根据选主的法则只能有两种可能(1)当选而 A 最后一条日志的 term 小于 B；(2)A 最后一条日志的 term 等于 B，但是 A 的日志少于 B。1,2 可能嘛？）而对于 multi-paxos 来说，日志是有空洞的，每个日志需要单独被确认是否可以 commit，也可以单独 commit。因此当新 leader 产生后，它只好重新对每个未提交的日志进行确认，已确定它们是否可以被 commit，甚至于新 leader 可能缺失可以被提交的日志，需要通过 Paxos 阶段一向其它节点学习到缺失的可以被提交的日志，当然这都可以通过向一个多数派询问完成（这个流程存在着很大的优化空间，例如可以将这个流程合并到 leader 选举阶段，可以将所有日志的确认和学习合并到一轮消息中，减少消息数目等）。但是无论是 Raft 还是 multi-paxos，新 leader 对于那些未提交的日志，都需要重新提交，不能随意覆写，因为两者都无法判定这些未提交的日志是否已经被之前的 leader 提交了。所以本质上，两者是一样的。一个日志被多数派拥有，那么它就可以被提交，但是 Leader 需要通过某种方式得知这一点，同时为了已经被提交的日志不被新 leader 覆写，新 leader 需要拥有所有已经被提交的日志（或者说可以被提交，因为有时候并没有办法得知一条可以被提交的日志是否已经被提交，例如当只有老 leader 提交了该日志，并返回客户端成功，然而老 leader 挂了），之后才能正常工作，并且需要重新提交所有未 commit 的日志。两者的区别在于 Leader 确认提交和获取所有可以被提交日志的方式上，而方式上的区别又是由于是日志是否连续造成的，Raft 协议利用日志连续性，简化了这个过程。

在 Raft 和 multi-paxos 协议确保安全性的原理上，更进一步的说，所有的凡是 满足 集群中存活的节点数还能构成一个多数派，一致性就能满足的算法，raft 协议，paxos，zab，viewstamp 都是利用了同一个性质：两个多数派集合之间存在一个公共成员。对于一致性协议来说，一旦一个变量的值被确定，那么这个变量的值应该是唯一的，不再更改的。Raft,paoxos 等协议，对于一个变量 v 来说，一个由节点 n1 提出的值 a 只有被一个多数集 q1 认可并记录后，才会正式令 v=a，如果另一个节点 n2 想要修改变量 v 的值为 b，也需要一个多数集 q2 的认可，而 q1 和 q2 必然至少有一个共同的成员 p,节点 p 已经记录了 v=a。因此只需要通过增加一些约束，让 p 能够告诉节点 n2 这个事实：v=a，使得 n2 放弃自己的提议，或者让节点 p 拒绝节点 n2 想要赋予 v 的值为 b 这个行为，都可以确保变量 v 的一致性不被破坏。这个思想对于这个四个协议来说都是一样的，4 个协议都使用一个唯一的整数作为标识符来标明 leader 的合法性，paxos 叫做 proposer-id，ZAB 叫 epoch，VR 叫 view，raft 叫 term。把 leader 看做是想要赋予变量 v 某个值的节点 n1,n2，上面提到的情形中，如果 n2 是目前的合法 leader，那么 n2 需要知道 v=a 这个事实，对于 raft 来说就是选择 n2 是已经记录了 v=a 的节点，对于 multi-paxos 来说，就是重新确认下 v 的值。如果 n1 是目前的合法 leader，n2 是老的 leader，p 就会根据 leader 的标识符拒绝掉 n2 的提案，n2 的提案会由于得不到一个多数派的接受而失效。最直接的从理论上阐明这个原理的是经典的 paxos 算法，关于这个原理更具体的阐述可以看看我在如何浅显易懂地解说 Paxos 的算法？下的回答。所以确实在一定程度上可以视 raft,ZAB,VR 都是 paxos 算法的一种改进，一种简化，一种优化，一种具象化。Lamport 老人家还是叼叼叼。。。。。。。不过值得一提的是，ZAB 和 raft 作者确实是受了 paxos 很多启发，VR 是几乎同时独立于 paxos 提出的。

Raft 容易实现在于它的描述是非常规范的，包括了所有的实现细节。如上面的人说的有如伪代码。而 paxos 的描述侧重于理论，工程实现按照谷歌 chubby 论文中的说话，大家从 paxos 出现，写着写着，处理了 n 多实际中的细节之后，已经变成另外一个算法了，这时候正确性已经无法得到理论的保证。所以它的实现非常难，因为一致性协议实非常精妙的。小细节上没考虑好，整个协议的一致性就崩溃了，而发现并更正细节上的错误在没有详尽的现成的参考的情况下是困难的，这需要对协议很深的理解。而且在 Raft 协议的博士论文 CONSENSUS: BRIDGING THEORY AND PRACTICE，两位作者手把手事无巨细的教你如何用 raft 协议构建一个复制状态机。我表示智商正常的大学生，都能看懂。我相信在未来一致性现在被提起来，肯定不是现在这样，大部分人觉得好难啊，实现更难。。。。应该会成为一种常用技术