raft利用日志连续性对Paxos做了大量很好的简化,但是其中有一点有很强的误导性,就是新任leader对于旧日志的处理,他的原文描述是“Raft uses a simpler approach where it guarantees that all the committed entries from previous terms are present on each new leader from the moment of its election, without the need to transfer those entries to the leader.”
raft利用日志连续确认的特性,只要选举termID最大的做leader,就可以保证leader当选以后,不需要对本地旧日志重新投票,而是请follower过来直接抓就行了。即使对哪些尚未形成多数派的entry,也是一样的处理方式,并未进行重新投票,在他的协议里这个做法是没有问题的。
但是multi-paxos原本的意思是,即使形成了多数派,仍然需要使用新的proposalID走一遍prepare-accept过程,工程上做了优化之后,对于明确标记了已形成多数派的entry可以不重新投票,但是未确认是否形成多数派的entry,则要求新任leader使用新的proposalID重新投票。
因为multi-paxos并不假设日志间有连续确认的关系,每条日志之间相互独立,没有关系,1号日志尚未确认时,2号日志就可以确认形成多数派备份。附一张之前分享ppt里的图,大家自己琢磨吧。
<noscript><img src="https://pic1.zhimg.com/54726a042b0c4e353ff93dc8b629af48_b.png" data-rawwidth="2000" data-rawheight="662" class="origin_image zh-lightbox-thumb" width="2000" data-original="https://pic1.zhimg.com/54726a042b0c4e353ff93dc8b629af48_r.png"></noscript>
raft利用日志连续确认的特性,只要选举termID最大的做leader,就可以保证leader当选以后,不需要对本地旧日志重新投票,而是请follower过来直接抓就行了。即使对哪些尚未形成多数派的entry,也是一样的处理方式,并未进行重新投票,在他的协议里这个做法是没有问题的。
但是multi-paxos原本的意思是,即使形成了多数派,仍然需要使用新的proposalID走一遍prepare-accept过程,工程上做了优化之后,对于明确标记了已形成多数派的entry可以不重新投票,但是未确认是否形成多数派的entry,则要求新任leader使用新的proposalID重新投票。
因为multi-paxos并不假设日志间有连续确认的关系,每条日志之间相互独立,没有关系,1号日志尚未确认时,2号日志就可以确认形成多数派备份。附一张之前分享ppt里的图,大家自己琢磨吧。
<noscript><img src="https://pic1.zhimg.com/54726a042b0c4e353ff93dc8b629af48_b.png" data-rawwidth="2000" data-rawheight="662" class="origin_image zh-lightbox-thumb" width="2000" data-original="https://pic1.zhimg.com/54726a042b0c4e353ff93dc8b629af48_r.png"></noscript>
• 作者保留权利
raft集成了成员管理,这个地方是唯一比paxos精妙的地方。里面的正确性的保证很有趣。raft增加了committed状态,如同@郁白 所说,这个在paxos里没有具体说。raft可以看成multiple paxos的一个实现。raft给你的基本是伪代码的描述了,方便实现。学理论的话还… 显示全部
raft集成了成员管理,这个地方是唯一比paxos精妙的地方。里面的正确性的保证很有趣。
raft增加了committed状态,如同@郁白 所说,这个在paxos里没有具体说。raft可以看成multiple paxos的一个实现。
raft给你的基本是伪代码的描述了,方便实现。学理论的话还是paxos好。
大部分场景都可以用raft实现,paxos应该没什么能直接使用的场景,太理论了……
raft增加了committed状态,如同@郁白 所说,这个在paxos里没有具体说。raft可以看成multiple paxos的一个实现。
raft给你的基本是伪代码的描述了,方便实现。学理论的话还是paxos好。
大部分场景都可以用raft实现,paxos应该没什么能直接使用的场景,太理论了……
本质上来讲,raft协议比paxos的优点是 容易理解,容易实现。容易理解在于它强化了leader的地位。整个协议可以清楚的分割成两个部分:(1)Leader在时。由Leader向Follower同步日志(2)Leader挂掉了,选一个新Leader,Leader选举算法。Zookeeper的ZAB和Viewst… 显示全部
本质上来讲,raft协议比paxos的优点是 容易理解,容易实现。容易理解在于它强化了leader的地位。整个协议可以清楚的分割成两个部分:
(1)Leader在时。由Leader向Follower同步日志
(2)Leader挂掉了,选一个新Leader,Leader选举算法。
Zookeeper的ZAB和Viewstamped Replication也类似,这些都可以被称之为Leader-based一致性协议。paxos Leader只是一种优化,为了提升性能,实际上就算有多个leader存在,算法还是安全的。paxos原版协议,从一个提案被提出到被接受分为两个阶段。这两个阶段是无法分割的,因为两个阶段的每个细节都是精心设计的,相互关联,共同保障了协议的一致性。
paxos和raft都是一旦一个entries(raft协议叫日志,paxos叫提案,叫法而已)得到多数派的赞成,这个entries就会定下来,不丢失,不更改,最终所有节点都会赞成它。paoxos中称为提案被决定,raft和zab称为日志被提交,这只是说法问题。Raft和ZAB就是一个日志一旦被提交,就不会丢失,Multi-paxos也是如此。实际上Multi-paxos和Raft都有一个Leader,multi-paxos的proposer-id和Raft的term概念是类似的,都是用来标识leader的合法性,multi-paxos proposer-id最大的Leader提出的决议才是有效的,raft协议中term最大的Leader才是合法的。实际上raft协议也会存在两个Leader的情形,只是不可能存在term一样的两个leader,因为选举算法要求leader得到同一个term的多数派的同意,这样可以根据term来区分谁还是合法的leader。multi-paxos的区分leader的合法性策略其实是一样的,谁大谁合法。同时raft协议的Leader选举算法,新选举出的Leader一定拥有全部的可以被提交的日志,而multi-paxos择不需要保证这一点。这样raft协议日志可以简单的只从leader流向follower在raft协议中,而multi-paxos则需要补全已提交的日志。需要注意的是日志可以被提交和日志已经被提交是两个概念。它们的区别就像是我前方有块石头和我得知我前方有块石头。日志只有已经被提交,才会保证不丢失。
raft协议强调日志的连续性,如果两个日志相同的序列号位置,term相同,那么这和这之前的日志必然是相同的。multi-paxos则允许日志有空洞。raft协议利用日志的连续性,Leader可以很方便的得知自己的哪些日志是已经commit的。Follower只要告诉Leader自己的日志本文件的最后一个日志的序号和term就可以了。而multi-paxos则不行,所以需要每个日志重新用proposer-id重走一遍所有的日志。可以举个列子,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)拥有了,可以提交了。同样的情形,multi-paxos就不行。Leader只好重新对日志进行投票。当然这是可以优化的,只要是Follower告诉Leader它拥有的所有所有日志的情况。Leader收集统计一下还是可以知道哪些日志已经被多数派接受了。所以本质上,两者是一样的。一个日志被多数派拥有,那么它就可以被提交,但是Leader需要通过某种方式得知这一点。两者的区别在于Leader得知的手段上,手段上的区别又是由于日志的连续性造成的。
更进一步的说,所有的凡是 满足 集群中存活的节点数还能构成一个多数派,一致性就能满足的算法,raft协议,paxos,zab都是利用了两个多数派集合之间存在一个公共集合这个特性,两个决定分别被两个多数派接受,必然有一个节点同时接受了两个决定。从这一个基本点出发,在协议的运转中增加了约束来使得协议的一致性任何时候都不会被破坏。从这些协议的共同点来说,确实可以认为它们都是paxos算法的一种改进,一种简化,一种优化。Lamport老爷爷还是叼叼的。。。。。。。
Raft容易实现在于它的描述是非常规范的,包括了所有的实现细节。如上面的人说的有如伪代码。而paxos的描述侧重于理论,工程实现按照谷歌chubby论文中的说话,大家从paxos出现,写着写着,处理了n多实际中的细节之后,已经变成另外一个算法了,这时候正确性已经无法得到理论的保证。所以它的实现非常难,因为一致性协议实非常精妙的。小细节上没考虑好,整个协议的一致性就崩溃了。而且在Raft协议的博士论文CONSENSUS: BRIDGING THEORY AND PRACTICE,两位作者手把手事无巨细的教你如何用raft协议构建一个复制状态机。我表示智商正常的大学生,都能看懂。我相信在未来一致性现在被提起来,肯定不是现在这样,好难啊,实现更难。。。。会成为一种常用技术。
(1)Leader在时。由Leader向Follower同步日志
(2)Leader挂掉了,选一个新Leader,Leader选举算法。
Zookeeper的ZAB和Viewstamped Replication也类似,这些都可以被称之为Leader-based一致性协议。paxos Leader只是一种优化,为了提升性能,实际上就算有多个leader存在,算法还是安全的。paxos原版协议,从一个提案被提出到被接受分为两个阶段。这两个阶段是无法分割的,因为两个阶段的每个细节都是精心设计的,相互关联,共同保障了协议的一致性。
paxos和raft都是一旦一个entries(raft协议叫日志,paxos叫提案,叫法而已)得到多数派的赞成,这个entries就会定下来,不丢失,不更改,最终所有节点都会赞成它。paoxos中称为提案被决定,raft和zab称为日志被提交,这只是说法问题。Raft和ZAB就是一个日志一旦被提交,就不会丢失,Multi-paxos也是如此。实际上Multi-paxos和Raft都有一个Leader,multi-paxos的proposer-id和Raft的term概念是类似的,都是用来标识leader的合法性,multi-paxos proposer-id最大的Leader提出的决议才是有效的,raft协议中term最大的Leader才是合法的。实际上raft协议也会存在两个Leader的情形,只是不可能存在term一样的两个leader,因为选举算法要求leader得到同一个term的多数派的同意,这样可以根据term来区分谁还是合法的leader。multi-paxos的区分leader的合法性策略其实是一样的,谁大谁合法。同时raft协议的Leader选举算法,新选举出的Leader一定拥有全部的可以被提交的日志,而multi-paxos择不需要保证这一点。这样raft协议日志可以简单的只从leader流向follower在raft协议中,而multi-paxos则需要补全已提交的日志。需要注意的是日志可以被提交和日志已经被提交是两个概念。它们的区别就像是我前方有块石头和我得知我前方有块石头。日志只有已经被提交,才会保证不丢失。
raft协议强调日志的连续性,如果两个日志相同的序列号位置,term相同,那么这和这之前的日志必然是相同的。multi-paxos则允许日志有空洞。raft协议利用日志的连续性,Leader可以很方便的得知自己的哪些日志是已经commit的。Follower只要告诉Leader自己的日志本文件的最后一个日志的序号和term就可以了。而multi-paxos则不行,所以需要每个日志重新用proposer-id重走一遍所有的日志。可以举个列子,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)拥有了,可以提交了。同样的情形,multi-paxos就不行。Leader只好重新对日志进行投票。当然这是可以优化的,只要是Follower告诉Leader它拥有的所有所有日志的情况。Leader收集统计一下还是可以知道哪些日志已经被多数派接受了。所以本质上,两者是一样的。一个日志被多数派拥有,那么它就可以被提交,但是Leader需要通过某种方式得知这一点。两者的区别在于Leader得知的手段上,手段上的区别又是由于日志的连续性造成的。
更进一步的说,所有的凡是 满足 集群中存活的节点数还能构成一个多数派,一致性就能满足的算法,raft协议,paxos,zab都是利用了两个多数派集合之间存在一个公共集合这个特性,两个决定分别被两个多数派接受,必然有一个节点同时接受了两个决定。从这一个基本点出发,在协议的运转中增加了约束来使得协议的一致性任何时候都不会被破坏。从这些协议的共同点来说,确实可以认为它们都是paxos算法的一种改进,一种简化,一种优化。Lamport老爷爷还是叼叼的。。。。。。。
Raft容易实现在于它的描述是非常规范的,包括了所有的实现细节。如上面的人说的有如伪代码。而paxos的描述侧重于理论,工程实现按照谷歌chubby论文中的说话,大家从paxos出现,写着写着,处理了n多实际中的细节之后,已经变成另外一个算法了,这时候正确性已经无法得到理论的保证。所以它的实现非常难,因为一致性协议实非常精妙的。小细节上没考虑好,整个协议的一致性就崩溃了。而且在Raft协议的博士论文CONSENSUS: BRIDGING THEORY AND PRACTICE,两位作者手把手事无巨细的教你如何用raft协议构建一个复制状态机。我表示智商正常的大学生,都能看懂。我相信在未来一致性现在被提起来,肯定不是现在这样,好难啊,实现更难。。。。会成为一种常用技术。
raft优势:简单,好懂,易实现。场景没什么太大区别.------------------------------------------------------------ RAFT的简单有好几个方面,比如:1)协议上的简化(最后主要RPC只有两个,其他协议的二阶段、三阶段也都变成 /看起来像是一阶段); 2)TE… 显示全部
raft优势:简单,好懂,易实现。
场景没什么太大区别.
------------------------------------------------------------
RAFT的简单有好几个方面,比如:
1)协议上的简化(最后主要RPC只有两个,其他协议的二阶段、三阶段也都变成 /看起来像是一阶段);
2)TERM概念的强化(看起来似乎PAXOS也有重选LEADER的机制,但是强化概念,并增加一个TERM内有一个一个LEADER、ENTRY与TERM相关的属性等都大大简化了流程);
3)LOG只会从LEADER到FOLLOWER单向同步(实现一下你会发现这真的减少好多问题,代码量都少了好多);
4)……TODO(先挖坑,回头再填)
但是本质上,又可以把RAFT和PAXOS对应起来(看有没精力后边再填坑……TODO)
场景没什么太大区别.
------------------------------------------------------------
RAFT的简单有好几个方面,比如:
1)协议上的简化(最后主要RPC只有两个,其他协议的二阶段、三阶段也都变成 /看起来像是一阶段);
2)TERM概念的强化(看起来似乎PAXOS也有重选LEADER的机制,但是强化概念,并增加一个TERM内有一个一个LEADER、ENTRY与TERM相关的属性等都大大简化了流程);
3)LOG只会从LEADER到FOLLOWER单向同步(实现一下你会发现这真的减少好多问题,代码量都少了好多);
4)……TODO(先挖坑,回头再填)
但是本质上,又可以把RAFT和PAXOS对应起来(看有没精力后边再填坑……TODO)
http://www.zhihu.com/question/36648084
http://www.tuicool.com/articles/Yfmu6n2
相关推荐
raft算法,原版论文,英文版 摘要 Raft 是一种用来管理日志复制的一致性算法。它和 Paxos 的性能和功能是一样的,但是它和 Paxos 的结构不一样;这使得 Raft 更容易理解并且更易于建立实际的系统。为了提高理解性,...
raft 是一种类似于 paoxs 的分布式算法,相对于 paxos 算法, raft 更容易于理解以及实现,这也是一种典型的 半数协议算法 。这里不详细介绍 raft 算法
对Paxos和Raft算法进行了综合介绍
磁盘阵列,CAP原则,数据的一致性,Paxos算法,Raft算法
为了提高理解性,Raft 将一致性算法分为了几个部分,例如领导选取(leader selection),日志复制(log replication)和安全性(safety),同时它使用了更强的一致性来减少了必须需要考虑的状态。从用户学习的结果来...
一、Paxos算法 世界上只有一种一致性算法,就是 Paxos,其它的算法都是残次品,但Paxos非常复杂难懂。 算法原理参考:Paxos的通俗解释 Paxos共识算法详解 算法例子参考:如何浅显易懂地解说 Paxos 的算法? Paxos...
Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。...Raft算法中文动画演示文件
Raft 是用来管理复制日志(replicated log)的一致性协议。它跟 multi-Paxos 作用相同,效率也相当,但是它的... Raft 还包括一个用于变更集群成员的新机制,它使用重叠的大多数(overlapping majorities)来保证安全性
服务发现工具的主要目标是用来服务查找和相互对话,为此该工具需要知道每个服务,这不是一个新概念,在Docker之前就已经存在很多类似的工具了,然而,容器带给了这些工具一个全新水平的需求。
raft是一种类似于paoxs的分布式算法,相对于paxos算法,raft更容易于理解以及实现,这也是一种典型的半数协议算法。
它与RBFT算法名称有点像,然而Raft算法里不能存在拜占庭节点,而RBFT则能容忍BFT节点的存在。Raft非常类似于paxos协议(参见我的这篇文章《paxos算法如何容错的–讲述五虎将的实践》),然而它比paxos协议好理解许多...
raft 声称简洁明了,可以取代非常复杂的 PAXOS 算法。然而翻看 raft 的论文后,会发现即便声称简洁明了,自己完整地实现 raft 还是很麻烦的。 etcd是一个分布式的 key-value 存储组件,它通过 raft 算法保证多台机器...
Raft算法的开源实现众多,在Go、C++、Java以及 Scala中都有完整的代码实现。Raft这一名字来源于"Reliable, Replicated, Redundant, And Fault-Tolerant"(“可靠、可复制、可冗余、可容错”)的首字母缩写。
介绍分布式系统概述、高可用等内容; 就业界常用的一致性协议,如Bully算法、Raft算法、Paxos算法作了详细的描述; 对于Raft的应用,以ETCD为例,讲解了其读写流程。
相比Paxos,Raft算法理解起来更加直观。 Raft算法将Server划分为3种状态,或者也可以称作角色: Leader 负责Client交互和log复制,同一时刻系统中最多存在1个。 Follower 被动响应请求RPC,从不主动发起请求RP
Raft一致性算法与Paxos不同,号称简单易学,且已经广泛应用在生产中。例如k8s和CoreOS中使用的etcd;tikv中使用Raft完成分布式同步;RedisCluster中使用类似Raft的选主机制等等。今天我们来一探究竟吧。复制状态机的...
与paxos相比,它更易理解和工程化。我们完整实现了该算法并将其应用在自研的高可靠消息中间件CMQ中,同时沉淀出对外通用的Raft算法库。本文主要介绍Raft算法的原理、工程化时遇到的问题与解决方案、以及改进性能的...
Raft是一种共识算法,旨在替代Paxos。 它通过逻辑分离比Paxos更容易理解,但它也被正式证明是安全的,并提供了一些额外的功能。 是用java开发的例子demo
前言 我计划写raft的一系列文章,包含从...1、leader:raft中会有一个领导者具有超级权限,可以把自己的log 复制到其他节点中。 2、leader election: raft每隔一段随机的时间就会进行leader的选举 3、raft允许集群配置