分布式一致性算法Raft简介(下)

简介: 最近看了Ongaro在2014年的博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》的部分章节,对raft有了初步的理解。

最近看了Ongaro在2014年的博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》的部分章节,对raft有了初步的理解。其中论文中提到用于教学的user study,个人感觉非常不错,言简意赅,特此分享出来。本文基本与原讲解一致,又加上了笔者的一点理解。

资源来源于Ongaro和Ousterhout在youtube上的分享(http://youtu.be/YbZ3zDzDnrw),共有31个slide,因篇幅字数限制分为上下:

上:分布式一致性算法Raft简介(上)

下:分布式一致性算法Raft简介(下)


slide 15:


img_cef5dee4a6755029c6ec8fa002f7878b.jpe

这一节开始讲leader changes,即leader的变更过程中如何保证log的一致性:

1)需要明白的是,新leader上任后,各个server的log状态很可能是不一致的;因为旧leader可能只完成了部分server的log复制就挂掉了;(新君即位,一片狼藉)

2)需要特别注意的是,raft中新leader上任后,并不会立即对不一致的旧log进行clean up,而仍然是正常开始normal operation;clean up是在normal operation的过程中进行的;原因在于:新leader上任后,可能有些server仍然是宕机状态,新leader没有办法立即对其进行clean up(因为那些server宕机或网络不通,无法进行通讯),只能等到这些server恢复正常后再进行clean up;而新leader不知道这些server什么时候能恢复正常,如果傻傻地苦苦等待,很可能会导致整个系统无法运行;所以,我们设计的系统,必须要确保新leader上任后要立即开始normal operation,而在normal operation的过程中要确保最终所有log一致;

3)raft的做法是:总是认为leader的log是对的!(皇帝总是对的)

4)raft认为leader的log总是对的,总是包含所有重要的信息,因此leader的重任就是最终使得所有follower的日志与之完全相同。(皇帝总是对的,皇帝总是试图广播自己的想法,让其他所有人的想法与之最终一致)

5)但是新leader在clean up的过程中也有可能宕机,再有新的leader上任,它也可能还没完成重任就又宕机了;如此循环;长时间如此,最终会导致各个server的log混乱不堪,如图实例。

(备注:注意图中示例,只标注了某个entry的index和term,为什么不标注command了?因为前面已经说了,只要entry的index和term相同,则其command一定相同,所以没必要标注;图中展示的log混乱不堪,点评分析如下:term1时期的log都是一致的,谁是leader无从知晓;term2时期只有S4和S5两个server,但S5的entry更多,记住信息总是从leader流向follower,所以leader必定是S5;term3只有S5,无疑它就是leader,这种情况很可能是当选leader后与其他server网络隔离了;同理term4时期S4是leader,term5时期S3是leader,term6时期S1是leader,term7时期S2是leader;另外从图中场景来看,很可能在中间某段时间,S4、S5的网络,与S1、S2、S3的网络不通,即产生了网络隔离;)

需要特别注意的是,图中entry(1,1)、entry(2,1)、entry(3,5)都是已提交的(标记方法是entry(index,term),这些entry所在server数都已过半),而其余所有的entry都是未提交的;我们一定要确保的是那些已提交的entry必须保存下来且不可再变更;而那些未提交的entry,因为还未传给任何state machine执行过,client更没有收到执行结果,所以是保存还是丢弃都无关紧要;

例如图中S2成为term7时期的leader后,如果能够与其他所有server通信,那它最终要保证其他所有server的log与它的log相同,这就意味着与之有冲突的log entry必须被清除;后续会详细讲解leader如何进行clean up使得followers的log与之相同;特别强调一下correctness和safety,我们怎样才能确保系统正常运行,确保不丢失重要信息呢?如我们刚才为了保证一致性,丢弃了一些log,我们怎样做才是安全的呢?下节讲。


slide 16:


img_611955de5e94d2d54f9c8d64f8b21d89.jpe

任何实现了replicated logs的系统都必须遵守的最基本的safety requirement原则是:

Once a log entry has been applied to a state machine, no other state machine must apply a different value for that log entry;即一旦某条log entry已经被某一个state machine执行,则其他任何state machine也必须执行这同一条log entry;即所有state machine都必须按照相同的顺序,执行完全相同的entry;(执行entry指的就是执行entry中的command)

为了实现这个整体的safety要求,raft采取了更严苛的准则,即如下的safety property:

如果某个leader发现某条log entry已经被提交,则这条entry必须存在于所有后续的leader中。这意味着,一旦某个leader即位,则在它的整个term时期内,它一定含有所有的已提交的log entries;

显而易见,只要leader满足了这条safety property,则一定能满足上面的safety requirement。(因为这是一个更窄的要求,简单推理:一个leader发现某条entry已被提交,则后续所有leader中都一定要有这条entry;这意味着leader中总是有所有的已提交entry;而raft能保证follower中的log最终一定与leader中的一致;所以所有server最终都会有这些已提交entry;而entry只有被提交后才能被state machine执行;所以最终所有的state machine必将按照相同的顺序执行相同的命令)

为了实现这一点,raft能够保证的safety requirement有:

1)leaders永远不会修改自己log中的entries,只能添加;(备注:这意思就是leader中的entry是不可变的;但注意,leader只是一种角色,是动态的不是永久的;只是说某个server当leader期间,它的entry是不可变的;而一旦下台,其entry是有可能被修改的;这类似于绕口令啊;)这条性质叫AppendOnlyProperty,即leader只能添加entry,但不能修改entry;这意味着leaders中log entries永远不会被修改;

2)只有leaders中的log才能被提交;言外之意是,某条entry即使过半server都存在了,但在leader中不存在,也是不能被提交的;(有人会想,会有这种情况吗?entry不都是从leader发给follower的吗,怎么会过半followers中有而leader中没有呢?再次强调,leader和follower只是角色,是动态的;正常情况下当然不会有这种情况,但是leader变更的时候就可能会出现,后续会有这种case)

3)entries在被提交给state machine执行之前,必须已被提交;即只有已被提交的entry才能被执行;

汇总1)、2)、3),我们可以保证上面的安全性。真的如此吗?有这三个条件就够了吗?

事实上,到现在的讲述为止,raft有这三个约束,并不能保证上面的安全性;我们必须增加额外的约束条件才能保证上面所述的安全性,后面会详细讲述我们是怎么解决的。先再回头想想我们需要达到的目标:

某个entry已被提交  ->  这条entry必定在后续leader中存在

为了实现这个安全性目标,我们必须从两方面修正raft算法:

a. 对leader election增加约束条件:如果某个server的log中缺少某个已提交entry,则不允许这个server当leader;

b. 必须改变对committed的定义:前面说的已过半即是committed,这是不够的;有时候我们必须延迟committed,直到我们认为安全了才能committed;所谓的安全,就是说我们认为能够保证后续leader有这条entry;

(点评:这两个约束条件非常绕口,大家认真领悟下:约束a是排除了某些server当leader,即不含有已提交entry的server不允许当leader;显而易见,只有约束a是不够的,因为a说的只是最低安全性条件,照此条件,有可能一个leader都选不出来;而b是对committed条件的加强,意味着对committed施加更严苛的条件,也意味着给更多server成为leader的机会,即能够保证最终能选出leader;后续会有相应case)


slide 17:


img_ec2f5c6f9ce62ce7077db21a86978446.jpe

接着上个slide,先讲leader election过程的修正:

我们怎样挑选leader,才能保证这个leader有所有的已提交entries呢?

这个问题非常难,因为我们有时候根本无法判断某条entry是否已提交了!

看上图:图中有3个server,但是突然server3挂掉了,必须从server1和server2中挑选一个leader;而对于entry5而言,根本无法判断entry5是否是已提交的!因为这取决于server3,如果server3中有entry5,则是已提交的,如果server3中无entry5,则不是已提交的;而server3已宕机或网络不通,根本无法与server3通讯,所以根本不可能知道server3上到底有没有entry5,所以根本无法判断entry5是否是已提交!

既然我们根本无法判断某条entry是否是已提交,我们怎么挑选leader来确保leader中一定有所有已提交entry呢?我们只能尽我们所能,挑选最有可能含有所有已提交entry的server做leader,即挑选the best leader! 我们此处先从直觉上这样理解,下面会更精确详细地证明。

我们挑选best leader的方式就是通过对log进行比较,即comparing logs:

1)candidate发起的RequestVote RPC投票请求包含其log中最后一条entry的index和term:回忆我们前面所说,最后一条entry的index和term能唯一标记整条log,即如果last entry的index和term相同,则这两条log必定相同;(需从前面两个结论推知: a.  index和term唯一标记一条entry; b. 某个entry相同,则其之前的entries也必定相同)

2)当其他server收到投票请求时,需要将收到的(index,term)与自己的相比较,如果认为自己的log更完整,则拒绝投票;更准确的定义如下:voting server V 收到candidate C的RequestVote请求,如果出现下面两种情况之一:

a. lastTerm_v > lastTerm_c 即server v的last entry所在term,即lastTerm比candidate的大;

b.  (lastTerm_v == lastTerm_c) && (lastIndex_v > lastIndex_c) 即server v的lastTerm与candidate相同,但是lastIndex值比candidate大;

一旦出现a或b,则server V认为自己的log更complete,直接否决candidate的投票请求;

(点评:此处非常关键,务必理解;回想我们的目的是pick the best leader,即要求candidate的日志尽可能最complete!最显然直观的理解当然就是谁的log最长谁的最完整了;然而,不尽如此;还有一个更重要的要求是more informative!只最多是没用的,首先要确保的是你的信息是最权威的、最informative的;在raft中我们引入了term的概念,且总是认为更晚term的信息比更早term的信息权威,所以挑选leader的首要条件就是看,谁的term更晚更大,即a;第二才是比较谁的log更长,即b)

3)结合1)、2)最终确保选举出来的leader将会是大多数server中log“最完整”的(most complete);

听懂没?不要担心,下面上实例。


slide 18:


img_ba292552191e1171c2287ff22fd1c26a.jpe

考虑最有趣的一种场景:leader刚刚确定某条entry被committed了(即刚收到来自大多数server的AppendEntries响应),就挂了。这种场景可以再分成两种独立case:1)这条entry属于current term;2)这条entry属于prior term;

先说case1,如图:

S1是term2时期的leader,刚把entry4复制到S2、S3成功,立马宣布entry4已安全(即在大多数server中都有,已被committed),立即在state machine上执行entry4;这意味着entry4是已提交的,后续的leader中必须包含这条entry,我们怎么确保呢?就是通过上一个slide中的leader election中的pick the best leader;设想,此时S1突然网络不通,需要重新选举leader,我们逐个分析:

a. S5绝不可能成为leader,因为其他server都处于term2,它还在term1,即其他server的lastTerm更大,会直接拒绝给它投票;

b. S4处于term2,但它若想成为leader,还需要至少2台server给它投票,而它最多只能得到S5的投票;因为其他server也都处于term2,但是log更长,即lastIndex更大,所以都会拒绝投票;因此S4加上自身最多得2票,也不可能成为leader;

c. S2和S3都可能成为leader,例如收到来自S4、S5的投票;显然,S1也可能成为leader;

综合abc发现,可能成为leader的server都含有entry4,即新的term3时期的leader必定含有entry4;换言之,最终新leader必定含有已committed的entry;


slide 19:


img_4ac813e59fb70b5626b48de80b2f08ac.jpe

现在考虑case 2:leader尽力使得一条entry被提交,而这条entry来自上一个term时期。

如图:

1)S1是term2时期的leader,S1刚将entry3复制到S2,就挂掉了,即此时entry3只在S1、S2两个server上有;

2)接着S5发起leader竞选,收到来自S3、S4的投票(此时S3、S4、S5都只有term1时期的entry1、entry2,所以不会拒绝投票),成功当选成为term3时期的leader;接着S5收到client请求,在本地log中产生了3条entry,但由于种种原因(如与其他server网络忽然不通),并未复制到其他server上就挂掉了;

3)接着S1再次竞选,成功当选为term4时期的leader;S1成为leader后,会尽力使得其他server的log与之相同,所以会将entry3、entry4复制到其他server上;一旦将entry3复制到server3上,则此时entry3已经形成大多数,即是已被committed了;entry3上的command就会被state machines执行,client就会收到entry3的执行结果。

最危险的情况出现了!注意,这种场景下entry3并不能认为是safely committed!因为它仍可能被覆盖,仍可能丢失!

考虑接下来可能发生的情况,就会明白为什么了:

4)S1成为term4时期的leader后,刚在本地产生entry4就挂掉了;而此时,S5可以再次当选,成为term5时期的leader(考虑下可能性,是完全有可能的,虽然entry3是committed了,但是S5很可能并不知道;因为可能网络分割,S1无法与其他server通信,只有S2、S3、S4、S5可以互相通信,此时S5不可能知道entry3是否已committed,S5完全可以当选leader)

5)S5当选leader之后,就会尽力使得其他server的log与之相同,就会term3时期的entry3、entry4、entry5复制到其他server;

很显然,之前的term2时期的entry3虽然已被认为是committed了,但仍会被覆盖导致丢失!显然,这与我们要求的safety原则相悖,无法容忍!必须加上新的限制条件,避免这种情况发生。


slide 20:


img_2767e919abace55d5d49dabcaf44f141.jpe

接前文;目前为止,new leader election rules并不足以保证安全性,我们必须还要修改已有的commitment rules!

回想一下,到目前为止,我们的commitment rules是:

1)只要leader看到某条entry存在majority of servers上(过半即可),则认为这条entry是committed;

为了保证安全性,我们必须添加一个额外的rule:

2)leader必须看到至少一条来自leader term(即leader的current term)的entry也存在于大多数的server上;

同时,rule 1)之前是充要条件,现在变成了必要非充分条件,新的commitment ruels是:

1)leader必须看到某条entry存在于大多数server上;

2)另外,leader必须看到至少一条来自其current term的entry也存在于大多数server上;

只有同时满足1)2)才能认为某条entry是committed的。

很明显,新加的rule 2)主要是针对上面说的case2场景的,即当新leader看到某条来自之前term的entry已经存在于大多数server上时,它不能再认为这条entry是committed了,必须等到来自其自身term的第一条entry也存在于大多数server上,才能认为之前term的那条entry是committed的;这其实相当于一种leader change场景下的延迟commitment吧,或者换种思路,相当于将上一个term时期的entry的commitment与当前term时期的commitment绑定在了一起。

回到前面的case2,接着看新commitment rules是如何保证安全性的:

1)当S5成为term4时期的leader后,它将entry3复制到S3,此时entry3已经存在于过半server上,但是并不能认为entry3是committed的,即并不会将entry3传给state machines执行;

2)必须等到entry4也复制到过半机器上,此时才能认为entry3、entry4是committed了(相当于延迟与绑定)。

那这样就是安全的了吗?是的。设想一下:

1)如果S1复制完成entry3、entry4到大多数server上,即entry3、entry4都已被committed了,此时S1挂掉了;那么显然,S4、S5不可能成为新的leader(因为term太低会被拒绝投票),只有S1、S2、S3有可能成为新leader,而这些server上都有entry3、entry4,所以entry3、entry4是安全的;

2)那么如果S1还没将entry3、entry4复制到大多数server上就挂了呢?那S5有可能成为新leader,即意味着entry3、entry4可能会被覆盖。这有什么关系呢?这种情况下entry3、entry4并没被认为是committed的,其命令被没有被state machine执行,client更没有收到其执行结果;这种情况下,entry3、entry4被覆盖而丢失是无关紧要的;

我们只保证已committed的entries的safety,并不对未committed的entries的安全性做任何保证。

因此,据上分析可知,new commitment rules是能够保证committed entries的safety的。

综上可知,new election rules和new commitment rules结合起来,能够保证raft的safety特性总是成立;即,一旦leader认为某条entry已被committed,则这条entry必然存在于后续所有leader的log中(就是说已committe的entries永不丢失);虽然我们这里只证明了已committed的entry必然存在于紧接着它的后续一个leader中,但很显然容易证明,这条entry在后续所有leader中都会有;

而一旦raft的safety特性成立,根据我们之前所说,所有的replicated logs都是安全的。

(点评:raft的safety property是整个raft系统的基石,是整个系统运行可靠性的最基本要求;需要认真理解领悟,结合实例认真体会raft是如何面对这些问题的,如何一步步修正完善rules来保证安全性的)


slide 21:


img_bca33f582f616229d36b92b47c0931de.jpe

现在,我们保证了raft的safety,并且知道leader的log永远是对的,那么我们怎么使得followers的log与leader的log相同呢?

首先让我们看下,followers的log有哪些与leader可能不同的情况呢:

1)missing entries:即follower的log与leader相比缺少某些entries,如图中的a/b/e follower;

2)extraneous entries:即follower的log与leader相比多出某些entries,如图中的c/d/f follower;

我们需要做的是:删除所有follower log中的多余entries,并用leader log中的entries填充follower中缺失的entries。


slide 22:


img_2cb8bd64b7893c45ac138eade0737916.jpe

接上文继续讲述,leader到底如何修复follower的logs使其与之相同呢?

上个slide已说了,leader为了保证follower的log与之相同,必须:

1)删除follower中的多余entries;

2)用自己的entries填充follower中的缺失entries;

那leader具体是如何做的呢?

为了恢复log一致性,leader为集群中所有follower都保存一个状态变量,即nextIndex:

1)nextIndex是leader准备向某个follower发送的下一个log entry的index;

2)当leader刚刚即位后,nextIndex的初始值是(1+leader's last index);

如图举例:

某个server成为term7时期的新leader,其log中的最后一条是entry10,所以这个leader会将所有follower的nextIndex都设为11;

leader可以通过AppendEntries RPC请求发现log之间的一致性问题;回想前面说过的,follower收到AppendEntries RPC请求的时候,会进行log一致性检查,所以一旦有不一致情况就会被检查出来;

因此,当leader试图与集群中的follower通讯时候,会带上nextIndex前面的一个entry的index和term(回想下,这是之前说过的,AppendEntries RPC请求会带上前一个entry的index和term用于进行一致性检查,这里的前一个entry就是entry10,对应的index和term分别是10和6);

顺便说下,新leader即位后,立即发出的请求很可能是heartbeat(心跳请求)!回忆之前说的,心跳请求跟普通的AppendEntries RPC是一样的,只是不带新values而已,但心跳请求仍然可以进行一致性检查;

因此,当这个请求(可能是心跳也可能是普通的AppendEntries )到达follower a时,follower会拿这个index和term(这里就是(10,6))与自己的log相比较;很显然,follower a中没有与之相匹配的;所以follower a会直接拒绝这个请求!

当leader看到请求被拒绝时,其动作非常简单:只需将nextIndex-1,再次尝试。

如此往复,再失败,nextIndex再减1,再重试;直到nextIndex=5,此时leader会带上(4,4)这个entry,follower a发现能与之匹配,所以接收;一旦follower a接受,则最终后续所有的missing entry都会被添加上;

follower b的情况也类似,当nextIndex=11时,一致性检查会失败;每次失败leader都会将nextIndex-1,然后重试;直到nextIndex=4,才会成功;最终follower b中的log也会被重新填充上;


slide 23:


img_708705f41cb9b3ac7e77b191d674a7cf.jpe

接上文,修复log的过程中,需要注意的一点是:

一旦follower收到某个log entry,且这条entry会覆盖掉follower 自身的与之不一致的entry,则follower会删掉自己所有后续的entries;

如图举例:当leader将entry4发送给follower,则follower的对应位置的entry与之冲突(仍处于term2而不是term4),因此entry4会覆盖follower的entry,且会将follower中entry4后面的所有entries都删除掉(即图中的before变成after);因为我们知道,某条多余的entry后面的所有entry也都是多余的。

这里简要总结下leader change这部分的关键点:

有两个overall problems我们需要处理:一是确保系统的safety,即怎么挑选leader、何时认为某条entry是committed的;二是当新leader上任后,会尽力使所有followers的log与之相匹配,而AppendEntries一致性检查提供了所有我们需要的信息。


slide 24:


img_9c611043912139ec949b74f6b8ef3eda.jpe

raft协议的第4部分也是关于leader change的,即old leader可能并没有真的死掉。如:

1)可能存在网络隔离或不稳定,导致leader暂时性地断网,即无法与其他servers通信;

2)其余servers等待到election timeout,然后选举出新的leader;

3)这时,如果旧leader的网络恢复了,它并不知道已经进行了选举,并不知道已有新的leader了;所以它仍认为自己是leader,并像leader一样行动,如尝试复制log entries;

事实上,确实还可能有client请求旧leader:旧leader接收到请求,记录到自己的log里,并尝试复制到集群中的其他servers中;我们必须阻止这种情况发生,方法就是使用term。

terms被用来识别过期的leader和candidate:

1)所有RPC请求都会带上sender(发送者)的term信息;当receiver收到RPC请求时,会将sender的term与其自身的term相比较,一旦不匹配,过期的一方必须更新term;

2)如果sender的term更低(更老),意味着sender是过期的;此时receiver会立即拒绝该请求,即不会执行该请求;并再给sender的response中带上receiver的term信息;当sender收到response之后,会意识到它的term已经过时,因此会主动下台,再次回到follower状态,同时更新自己的term;此时其term状态与其他servers是一致的;

3)相反,如果receiver的term更旧,则:如果此时receiver不是follower的状态,它也会主动下台,再次回到follower状态,同时更新自己的term(如果本来就是follower只需更新term即可);接着正常处理该RPC请求;这种情况下receiver不会拒绝RPC请求,因为它没有必要这样做;它只需主动下台且更新term即可;

有趣的是,leader election过程会使得集群中大多数server都更新term,因为当candidate请求投票时,它必须与集群中大多数server通信;而RequestVote RPC会带上candidate的term信息;而所有的接收者都会更新自身的term信息使之与candidate的相同;因此,当新leader上任后,集群中的大多数server都会反映出新的term信息;这意味着,一旦新的leader election完成,旧leader就不可能再接受请求并复制log entries到其他server了。因为为了复制log entries,旧leader必须与具有新term的server中的至少一台通讯,而一旦这样做,就会被发现term不匹配,而导致旧leader下台。(此处较为拗口,道理很显然,新的leader当选必然意味着过半server的term都是最新的;而旧leader复制log也必须与过半server通讯;而过半与过半之间,必然有至少一个公共server;而这个server的term检查就会使得旧leader暴露,从而下台)

因此,综上所述,可以用term检查识别过期信息。

(点评:分布式系统中的时期、任期的概念非常关键,如raft中的term、zab中的epoch等,道理都是类似的;其核心用意只有一个,即识别过期信息)


slide 25:


img_39dfb231e485f7c6a4d23929d54d28b2.jpe

现在讲raft的第5部分,即client如何与raft系统交互。

大部分情况下,这都很简单,即:client将command请求发送给leader,然后接收leader的response。

但是,如果client不知道谁是leader呢?没关系,client可以请求集群中的任意server;如果那个server不是leader,它会告诉client谁是leader;然后client可以重新请求leader。

之前说过,leader并不会立即响应client,直到:command被记录到log中,并复制到大多数server上,即被committed,接着leader的state machine执行该command。此时,leader才会向client返回请求结果。

唯一需要注意的地方是,如果此时请求超时了(如leader突然挂掉导致),会怎么样?答案是:

1)client会请求集群中任意一个server,不断重试;

2)最终,client会发现集群中的新leader;

3)client会向新leader重试请求;

新leader会执行client的command,并发送请求结果。因此这能保证,command总是能够被执行。


slide 26:


img_407c23c2777d4be69d135e5917ef7416.jpe

然而,上一个slide中说的,总能保证command最终被执行,会带来command被重复执行的风险。

问题的关键是:leader可能在执行完某个command,但是还未向client发送结果时挂掉。而一旦出现这种情况,client不可能知道这个command到底是否被执行了,所以它会不断重试,并最终请求到新leader上,而这会导致该command被执行两次。

显然,这是无法接受的!我们要求command必须最终被执行,且只能执行一次(once and exactly once)。

raft的解决思路是:client为每个command生成一个唯一id,并在发送command时候带上该id。

1)当leader记录command时,会将command的id也记录到log entry中;

2)在leader接受command之前,会先检查log中是否有带该id的entry;

3)leader一旦发现log中已有该id的entry,则会忽略这个new command,并将old command的结果返回给client(如果此时old command还没执行完,会等待其完成再返回);

因此,只要client不crash,我们就能实现exactly-once语义,即每个command只会被执行一次。这也是我们希望系统具有的,被叫做linearize ability。

(点评:类似于幂等性,即client重试不会导致重复执行。系统本身要支持这种重入、重试,保证有且仅有一次执行。)


slide 27:


img_3f4024f95d569f9b4db9ea7451f98520.jpe

这是raft协议的第6部分:系统配置的变更机制。

系统配置指的是组成集群的各个server的信息。如每个server的id、用于通讯的网络地址等。这些信息非常重要,因为这些决定了集群中“大多数”(majority)的组成,而选举leader、commit log entry等都取决于majority vote。

我们必须要支持系统配置变更,因为机器可能宕机,我们需要用新机器替代老机器;或集群管理员想更改集群的degree of replication(复制因子、副本系数)。我们想让系统自动而安全(automatic and safe)地完成这些,而不至于变更配置导致系统崩溃。


slide 28:


img_271729179e34e454c139e43539626f61.jpe

重要的是,我们必须意识到:我们不能直接地将旧配置切换成新配置。为什么呢?看图中例子:

设想系统正在运行,系统配置中有3台机器,即server1/server2/server3;而我们现在想添加2台机器,即添加后应该有5台机器组成新的集群。

如果我们要求每个server直接更改配置,从旧配置改为新配置,就会产生问题。问题就是我们没办法做到所有server同时更改配置,变更过程总要花点时间,而这会导致conflicting majoritys(大多数冲突)。

例如图中某个时刻,server1、server2仍是旧配置;而server3、server4、server5已经是新配置。这样server1、server2能够形成旧集群中的大多数,它们可以基于此进行leader election、commit log entry等;而与此同时,另外3台机器,即server3、server4、server5已经是新配置了,它们也可以形成新配置集群中的大多数,也可能commit与前2台server相同位置的log entry,而这很可能会产生冲突。

这意味着,我们必须用two-phase protocol(两阶段协议),我们没办法在one-phase中完成。当然,所有的分布式系统中的decision-making都会采取这种典型办法;如果有人告诉你,他能在one-phase中完成分布式系统的decision-making,你需要提出严重质疑!要么是他错了,要么是他发现了这个世界上从来没人知道的新东西!

(点评:two-phase protocol即两阶段协议,是所有分布式系统中做decision-making的套路。问题的核心与关键就在于“分布式”,意味着系统中不是一个单一的个体,而是众多个体组成的整体;而遗憾的是这个整体不可能像单一个体那样行为,例如众多个体不可能同时完成某项动作,也即不可能完全地把一个整体等价于一个个体;而client又需要整体像一个体一样地运行。)


slide 29:


img_f8fdc7f1964023843c719c49c81ebef2.jpe

raft采用2-phase的方式进行配置变更:

raft先立即进入一个中间状态,叫joint-consensus;这个状态包含旧配置和新配置的所有机器;但是decision-making,如leader election和log commitment,需要同时满足旧配置的大多数和新配置的大多数(need majority of both old and new configurations for election and commitment);

如图中举例说明:

集群最初的已有配置是Cold,而在某个时刻,由client发起集群配置变更,即client向leader发送配置变更请求(类似普通的operation请求);当leader接收到配置变更请求时,就向自己的log中插入一条entry(跟普通的log entry是一样的),用于描述配置变更,如Cold+new;然后leader通过AppendEntries RPC请求将该配置变更log entry复制到其他server上(跟普通的AppendEntries RPC复制log entry一样);需要特别注意的是,配置变更立即生效!即一旦server将新配置的log entry写入自己的log,它就立即生存在新的配置之下;它不需要等待大多数server都有这条entry,即不需要等待这条entry提交,一旦写入自己的log中就立即生效(这点与普通entry不同,普通的entry必须等到已提交才能被执行而生效);

回到图中的时间线,leader将新配置的log entry写入自己的log,并立即生效;之后leader所做的所有decisions,都必须基于old+new的配置,如后续某条普通的entry要想被提交,必须同时存在于大多数的旧配置的server上,和大多数的新配置的server上;

过一小段时间,Cold+new这条log entry总会复制到大多数的server上而变成被提交状态;而在此之前,decision-making有可能是基于Cold,也有可能是基于Cold+new;如leader刚收到Cold+new的配置变更,还没来得及复制到更多server上就宕机了,此时处于Cold配置的server有可能当选并掌控集群;

但是,总有一个时间点,最终Cold+new这条entry能够复制到大多数server上而成为committed状态;一旦Cold+new被提交,则意味着任何server都不能再仅仅基于Cold来make decision了。简单解释:如果一个server想成为leader,它必须具有所有的已committed的log entries,而Cold+new一旦被committed,就保证了后续任何leader都一定有Cold+new这条entry,这意味着那个leader必定在Cold+new的配置下生存(living by it),即leader选举过程必须获得old配置中的大多数和new配置中的大多数同时投票,某条entry提交也必须要求这条entry存在于old配置中的大多数servers和new配置中的大多数servers上;因此,集群中不可能再有任何server仅仅基于old配置中的大多数来做决定。

所以在Cold+new已被committed的之后,集群就会在joint-consensus(联合一致性)下运行;而一旦joint-consensus被committed,leader就会传播Cnew这条log entry,即将配置变更为Cnew这条entry写入自己的log,并复制到其他servers上;

同样,在其后一段时间内,集群有可能在joint-consensus下运行(即Cold+new下),有可能在Cnew下运行;但最终,Cnew这条entry总能被committed;而一旦Cnew被committed,后续的所有decision-making都必须基于Cnew了;

因此,这里的关键点在于:决不允许Cold和Cnew都能make decision,而不互相consult(参考、询问)!最初的一段时间,仅仅依靠Cold就可以make decison;最终的一段时间,仅仅依靠Cnew就可以make decison;但是我们能确保这两个时间段没有重叠。而在这两段时间之间,两个配置必须互相consult,这就确保了集群在任何时候都不可能同时形成两个独立的consensus。

另外说明下,这种2-phase特性是非常基本的,任何一致性算法都会采用某种形式的2-phase来变更配置。事实上,任何形式的distributed agreement都要求two phases;如果有人发明了新的distributed agreement algorithm,并声称可以在single phase内完成,你需要严重质疑他:要么他们错了,要么他们发现了我们都不知道的新东西。

(点评:joint-consensus的核心关键点在于:如何避免新旧配置同时存在而产生majority conflict,进而导致decision conflict,从而产生不一致。这里采用了过渡方法,认真思考,其实单独地只有2种形式的decison-making依据:a.获取Cold中的majority的支持  b.获得Cnew中的majority的支持;但是如果简单粗暴地从a切换到b,其实是做不到的,因为不可能是一个原子操作,中间必然有一段时间,会存在a和b都生效,那么就可能会产生冲突。这里采用了一种渐进的思路:

a -> a || (a&b) -> a&b -> (a&b) || b -> b

实质上,将整个集群可能的decison-making依赖的majority状态空间分成了5个阶段,分别是:

old中大多数做决定 -> (old中的大多数做决定) 或者 (old和new中的大多数同时做决定) ->

(old和new中的大多数同时做决定)-> (old和new中的大多数同时做决定) 或者 (new中的大多数做决定) -> new中的大多数做决定

这种状态变迁的核心与关键在于:这种变迁是渐进的,每一个阶段都不会产生decison-conflict,从而保证变更过程的平稳。如果不这样做,直接变更 a ->b,显然这种粗暴的做法会导致decison-conflict。)


slide 30:


img_0fa34307377722ffbd02fbaf941d69a4.jpe

Joint-consensus这部分还有一些细节:

1)在变更的过程中,来自新旧配置的server都有可能成为leader;

2)如果当前leader不在Cnew配置里面,则一旦Cnew提交,它必须step down(下台);

这意味着,旧leader不再是新配置的成员之后,还有可能继续服务一小段时间;即旧leader可能在Cnew配置下继续当leader(虽然实质上并不是leader,但仍发挥leader的作用),直到Cnew的entry能够复制到足够多的server上而被committed;


slide 31:


img_c9be282420d63cc2448c0dab48c50c98.jpe

Congratulations!终于介绍完了raft。这里简要回顾下raft的6个部分:

1)leader election:我们确保任何时间,一个term内至多只有一个leader;

2)normal operation:leader接收client的请求,写log并复制到集群中其他机器;注意AppendEntries时非常重要的consistency check,用于确保log的一致性,并在log不一致时用来恢复一致性;

3)safety and consistency:主要讲leader changeovers,涉及两个重大问题。一是保证系统safety,我们展示了如何保证某条entry一旦被committed就永久存在;二是确保一致性,即leader如何确保最终所有followers的log都与其完全相同;

4)neutralize old leaders:一旦有新leader,旧leader就不能再发号施令。

5)client protocol:简要介绍了client与raft的交互,特别是raft中server crash之后,client需要怎么做;

6)configuration changes:讲了raft如何自动并安全地进行配置变更。

最后,对整个raft算法进行整体评论:这个算法的核心是系统必须完美运行,即使只有majority的servers在线。这意味着,永远不能依赖全部server的信息,因为总可能会有server宕机,这完全是未知的,算法必须考虑到这点并完美处理。

(点评:raft的核心思想跟其他一致性算法是相同的,即你不能要求系统中所有个体都运行良好,你必须要做出让步,即不要求系统中所有个体良好,只要系统中大部分个体良好,系统就要能良好地运行下去。而如何保证系统中大多数行为一致,就能达到最终系统所有个体作为一个整体行为一致呢?这其实就是分布式一致性算法需要解决的问题,其实是提出了更高的要求。其中最核心的要求就是两点:一是safety,即无论如何都要保证系统不出问题;二是liveness,即系统要前进、要运行、要为client服务,不能只是不出问题,还要保证能及时地干活、能良好地运转下去。)

目录
相关文章
|
4天前
|
存储 算法 安全
分布式系统架构1:共识算法Paxos
本文介绍了分布式系统中实现数据一致性的重要算法——Paxos及其改进版Multi Paxos。Paxos算法由Leslie Lamport提出,旨在解决分布式环境下的共识问题,通过提案节点、决策节点和记录节点的协作,确保数据在多台机器间的一致性和可用性。Multi Paxos通过引入主节点选举机制,优化了基本Paxos的效率,减少了网络通信次数,提高了系统的性能和可靠性。文中还简要讨论了数据复制的安全性和一致性保障措施。
18 1
|
25天前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
33 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
1月前
|
存储 缓存 算法
分布式缓存有哪些常用的数据分片算法?
【10月更文挑战第25天】在实际应用中,需要根据具体的业务需求、数据特征以及系统的可扩展性要求等因素综合考虑,选择合适的数据分片算法,以实现分布式缓存的高效运行和数据的合理分布。
|
1月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
2月前
|
算法
基于粒子群算法的分布式电源配电网重构优化matlab仿真
本研究利用粒子群算法(PSO)优化分布式电源配电网重构,通过Matlab仿真验证优化效果,对比重构前后的节点电压、网损、负荷均衡度、电压偏离及线路传输功率,并记录开关状态变化。PSO算法通过迭代更新粒子位置寻找最优解,旨在最小化网络损耗并提升供电可靠性。仿真结果显示优化后各项指标均有显著改善。
|
2月前
|
SQL 关系型数据库 分布式数据库
Citus 简介,将 Postgres 转换为分布式数据库
【10月更文挑战第4天】Citus 简介,将 Postgres 转换为分布式数据库
95 4
|
2月前
|
存储 缓存 NoSQL
大数据-38 Redis 高并发下的分布式缓存 Redis简介 缓存场景 读写模式 旁路模式 穿透模式 缓存模式 基本概念等
大数据-38 Redis 高并发下的分布式缓存 Redis简介 缓存场景 读写模式 旁路模式 穿透模式 缓存模式 基本概念等
71 4
|
2月前
|
算法
raft算法的自我理解
本文介绍了Raft算法的基本概念和工作原理,包括它如何通过日志复制和领导选举来实现分布式系统中不同机器的强一致性。
31 2
|
2月前
|
消息中间件 缓存 算法
分布式系列第一弹:分布式一致性!
分布式系列第一弹:分布式一致性!
|
2月前
|
算法 Java 关系型数据库
漫谈分布式数据复制和一致性!
漫谈分布式数据复制和一致性!

热门文章

最新文章