raft算法与paxos算法相比有什么优势,使用场景有什么差异? - 知乎

标签: | 发表时间:2018-03-26 15:13 | 作者:
出处:https://www.zhihu.com

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协议构建一个复制状态机。我表示智商正常的大学生,都能看懂。我相信在未来一致性现在被提起来,肯定不是现在这样,大部分人觉得好难啊,实现更难。。。。应该会成为一种常用技术。

相关 [raft 算法 paxos] 推荐:

raft算法与paxos算法相比有什么优势,使用场景有什么差异? - 知乎

- -
Raft协议比paxos的优点是 容易理解,容易实现. 它强化了leader的地位,把整个协议可以清楚的分割成两个部分,并利用日志的连续性做了一些简化: (1)Leader在时. 由Leader向Follower同步日志 (2)Leader挂掉了,选一个新Leader,Leader选举算法. 但是本质上来说,它容易的地方在于流程清晰,描述更清晰,关键之处都给出了伪代码级别的描述,可以直接用于实现,而paxos最初的描述是针对非常理论的一致性问题,真正能应用于工程实现的mulit-paxos,Lamport老爷爷就提了个大概,之后也有人尝试对multi-paxos做出更为完整详细的描述,但是每个人描述的都不大一样.

Paxos算法分析

- chuang - Schooner中国技术团队
Paxos 算法要解决的问题是在一个分布式系统中如何就某个值(提案)达成一致. 是一个非常基础而且经典的算法,也是目前最有效的一个算法. 【来自Schooner中国团队,转载请申明】. prepare 阶段: proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派;.

raft算法与实现

- - 掘金架构
强一致性、高可用的存储组件是构建现代分布式系统的必要条件,广泛应用于注册中心、配置中心等平台设施中,分布式锁、协调器等等各类场景需求也有相关需求,在该领域有众多知名的开源组件,如etcd、zookeeper、Tikv等等. 共识算法是实现这类组件的关键算法. 简单的说共识算法是协调多个节点达成共识的算法,这是构建高可用系统的基石.

分布式选举算法Paxos

- - 互联网 - ITeye博客
Paxos算法是分布式计算领域中一个非常重要的算法,主要解决分布式系统如何就某个值(决议)达成一致的问题. 一个典型的场景是分布式数据库的一致问题:如果分布式数据库的各个节点初始状态一致,又能执行相同的操作序列,那么最后能达到一个一致的状态. 但是如何保证在每个节点上执行相同的命令序列呢. 这就需要在每条指令上执行一个“一致性算法”以保证每个节点看到的指令一致.

Paxos与zookeeper

- - 互联网 - ITeye博客
1,什么是Paxos算法. Paxos算法是分布式计算领域中一个非常重要的算法,主要解决分布式系统如何就某个值(决议)达成一致的问题. 一个典型的场景是分布式数据库的一致问题:如果分布式数据库的各个节点初始状态一致,又能执行相同的操作序列,那么最后能达到一个一致的状态. 但是如何保证在每个节点上执行相同的命令序列呢.

Raft 共识

- - 瀚海星空
Raft是一种共识算法,用于多个分布式的系统,如zookeeper,谷歌chubby. 其核心思想是由一个leader作为入口,由他来对数据进行接受和分发处理. 该唯一leader必须得到多数节点的选票. 所以即使集群分裂,最终还是会有多数节点会达成一致. 适用于彼此可信的节点环境. candidate 临时角色,没有leader时由follower转成.

短文: Block Chain 与 Paxos

- comain - fcicq's blog-beta
作为 P2P 系统, Bitcoin 的一致性实现方法是值得专门写出来的.. 下面一一列举 Paxos 的专有名词, 并指出 Bitcoin 中的对应方法/实现.. –最长链中所有的 Block 均为决议. (但链末尾并不稳定, 所以最近 120 个 Block 里产生的钱不能花.. 经历 120 block 之后, block 是彻底不可逆转的, 严格意义上最近 120 block 不能算通过的决议).

Raft对比ZAB协议

- - zzm
ZooKeeper的一致性算法赏析. 本篇文章想总结下Raft和ZAB在处理一些一致性问题上的做法,详见之前对这2个算法的描述. ZooKeeper的一致性算法赏析. 上述分别是针对如下算法实现的讨论:. copycat,由于Raft算法本身已经介绍的相当清晰,copycat基本上和Raft算法保持一致.

分布式架构之 Paxos 协议

- - IT瘾-dev
这周一下了个决定"裸辞",逼自己一把. 当你在一个复杂的环境下,对所负责的项目失去激情时、不开心时你会选择怎样. 已经进入到分布式架构系列的尾声了,倒数第三篇文章. Paxos、Raft、以及变种/类似的协议都是用于在分布式里面解决选举的问题. 2pc、3pc、Waro是保证数据的强一致性,它们之间的强一致性在层次上是不同的概念、解决的问题不同,需要注意区分.

分布式系统基石:Paxos

- - DockOne.io
这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品. ——Mike Burrows(Google Chubby 的作者). Paxos是学习分布式系统无法绕开的一环,从理论上看Paxos是非常优雅的,但是实现起来就没有那么简单了. 《 The Part-Time Parliament》又看不懂,只能看《 Paxos Made Simple》和 视频教程这种东西才能维持的了生活这样子.