分布式一致性算法Raft简介(下)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

分布式一致性算法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服务,不能只是不出问题,还要保证能及时地干活、能良好地运转下去。)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: