咨詢電話：023-6276-4481
咨詢電話：023-6276-4481
熱門文章
電 話：023-6276-4481
郵箱：broiling@qq.com
地址：重慶市南岸區(qū)亞太商谷6幢25-2
分布式系統(tǒng)中主要的問題就是如何保持節(jié)點(diǎn)狀態(tài)的一致性，不論發(fā)生任何failure，只要集群中大部分的節(jié)點(diǎn)可以正常工作，則這些節(jié)點(diǎn)具有相同的狀態(tài)，保持一致，在client看來相當(dāng)于一臺(tái)機(jī)器。
一致性問題本質(zhì)就是replicated state machines，即所有結(jié)點(diǎn)都從同一個(gè)state出發(fā)，都經(jīng)過同樣的一些操作序列（log），最后到達(dá)同樣的state。其中保證各個(gè)節(jié)點(diǎn)執(zhí)行相同的操作序列就是raft算法所要實(shí)現(xiàn)的。在raft算法中有一個(gè)Leader的角色，client與之進(jìn)行交互，并且Leader協(xié)調(diào)Follower，保障所有的Follower具有相同的操作序列，最后提交這些操作，使?fàn)顟B(tài)機(jī)達(dá)成一個(gè)新的一致的stat。
整個(gè)raft算法分為L(zhǎng)eader選舉，日志分發(fā)，日志壓縮（快照），集群成員變更。其中的Leader選舉是算法的核心部分。算法保證任何時(shí)候最多只有一個(gè)Leader，但是可能沒有Leader（比如正在選舉過程中或者集群成員多數(shù)不可用時(shí)）。在Leader確立之后，就可以進(jìn)行日志分發(fā)，算法保證日志會(huì)被安全的分發(fā)到集群中并且應(yīng)用到狀態(tài)機(jī)的日志和自己相同?？煺帐菫榱藴p少日志量，去除中間過程。集群成員變更是為了在不停服務(wù)的情況下安全使用新的集群配置。
Raft在非拜占庭錯(cuò)誤情況下，包括網(wǎng)絡(luò)延遲、分區(qū)、丟包、冗余和亂序等錯(cuò)誤都可以保證正確，不會(huì)返回錯(cuò)誤結(jié)果，這就是安全性保證。實(shí)際上就是保證所有成員狀態(tài)機(jī)都以同樣的順序，執(zhí)行同樣的命令。下面分析幾種典型的場(chǎng)景下，raft是如何保證安全性的。
1. Leader選舉之后，如果Follower與Leader日志有沖突該如何處理？
Raft規(guī)定Follower中的沖突日志會(huì)被Leader中的日志覆蓋，使得Follower中的日志總是與Leader的日志保持一致。Leader必須找到Follower日志中最后兩者達(dá)成一致的地方，然后刪除從那個(gè)點(diǎn)之后的所有日志條目，發(fā)送自己的日志給Follower。所有的這些操作都在進(jìn)行日志復(fù)制RPC的一致性檢查時(shí)完成： Leader針對(duì)每一個(gè)Follower維護(hù)了一個(gè) nextIndex，表示下一個(gè)需要發(fā)送給Follower的日志條目的index。當(dāng)一個(gè)Leader剛獲得權(quán)力的時(shí)候，他初始化所有的 nextIndex 值為自己的最后一條日志的index加1。Leader每次發(fā)送日志復(fù)制RPC的時(shí)候會(huì)包含兩個(gè)值：prevLogIndex和prevLogTerm，分別對(duì)應(yīng)緊隨新日志條目之前日志的索引值(index)和任期號(hào)(term)，即prevLogIndex = newIndex - 1，如果Follower在它的日志中找不到包含Leader發(fā)送過來的index和term的條目，那么他就會(huì)拒絕接收新的日志條目。也就是此時(shí)Follower的日志和Leader不一致，日志復(fù)制RPC 時(shí)的一致性檢查就會(huì)失敗。在被Follower拒絕之后，Leader就會(huì)減小 nextIndex 值并進(jìn)行重試。最終 nextIndex 會(huì)在某個(gè)位置使得Leader和Follower的日志達(dá)成一致。當(dāng)這種情況發(fā)生，日志復(fù)制 RPC 就會(huì)成功，這時(shí)就會(huì)把Follower沖突的日志條目全部刪除并且加上Leader的日志。一旦日志復(fù)制 RPC 成功，那么Follower的日志就會(huì)和Leader保持一致，并且在接下來的任期里一直繼續(xù)保持。通過上述步驟，Raft算法保證了日志是順序復(fù)制的。就是說，假如有一條舊的日志還未復(fù)制給FollowerA，那么更新的日志就不能復(fù)制。日志的順序復(fù)制，很大程度上簡(jiǎn)化了Raft算法。比如查看各成員日志的新舊，只要比較最后一條日志即可。
2. 如果在一個(gè)Follower宕機(jī)的時(shí)候Leader提交了若干的日志條目，然后這個(gè)Follower上線后可能會(huì)被選舉為L(zhǎng)eader并且覆蓋這些日志條目，如此就會(huì)產(chǎn)生不一致。
Raft通過對(duì)Leader的選舉進(jìn)行限制，來保證所新選出的任何Leader對(duì)于給定的任期號(hào)，都擁有了之前任期的所有被提交的日志條目，限制規(guī)則為：candidate發(fā)送出去的投票請(qǐng)求消息必須帶上其最后一條日志條目的Index與Term；接收者需要判斷該Index與Term至少與本地日志的最后一條日志條目一樣新，否則不給投票。因?yàn)?nbsp;前一個(gè)Leader提交日志條目的條件是日志復(fù)制給集群中的多數(shù)成員，Candidate選舉為L(zhǎng)eader的條件也是需要多數(shù)成員的投票。那么這兩個(gè)大多數(shù)中成員必定有一個(gè)交叉，即有一個(gè)成員具有該日志，并且投票給了新Leader，也就意味著新Leader的日志至少不比該成員舊，那么新Leader也具有該日志。這樣就得到證明了，后續(xù)的Leader一定具有前面Leader提交的日志。
3. 即使保證上述選舉規(guī)則，也不能保證一致性，也就是說會(huì)出現(xiàn)Leader提交了前面任期的日志條目之后，該條目還有可能被后來的Leader覆蓋而產(chǎn)生不一致。如下圖所示：
(a) S1是Leader，并且部分地復(fù)制了index-2；
(b) S1宕機(jī)，S5得到S3、S4、S5的投票當(dāng)選為新的Leader（S2不會(huì)選擇S5，因?yàn)镾2的日志較S5新），并且在index-2寫入到一個(gè)新的條目，此時(shí)是term=3（注：之所以是term=3，是因?yàn)樵趖erm-2的選舉中，S3、S4、S5至少有一個(gè)參與投票，也就是至少有一個(gè)知道term-2，雖然他們沒有term-2的日志）；
(c) S5宕機(jī)，S1恢復(fù)并被選舉為L(zhǎng)eader，并且開始繼續(xù)復(fù)制日志（也就是將來自term-2的index-2復(fù)制給了S3），此時(shí)term-2，index-2已經(jīng)復(fù)制給了多數(shù)的服務(wù)器，但是還沒有提交；
(d) S1再次宕機(jī)，并且S5恢復(fù)又被選舉為L(zhǎng)eader（通過S2、S3、S4投票，因?yàn)镾2、S3、S4的term=4<5，且日志條目(為term=2,index=2)并沒有S5的日志條目新，所以可以選舉成功），然后覆蓋Follower中的index-2為來自term-3的index-2；（注：此時(shí)出現(xiàn)了，term-2中的index-2已經(jīng)復(fù)制到三臺(tái)服務(wù)器，還是被覆蓋掉）；
(e) 然而，如果S1在宕機(jī)之前已經(jīng)將其當(dāng)前任期（term-4）的條目都復(fù)制出去，然后該條目被提交（那么S5將不能贏得選舉，因?yàn)镾1、S2、S3的日志term=4比S5都新）。此時(shí)所有在前的條目都會(huì)被很好地提交。
如果上述情況(c)中,term=2,index=2的日志條目被復(fù)制到大多數(shù)后，如果此時(shí)當(dāng)選的S1提交了該日志條目，則后續(xù)產(chǎn)生的term=3，index=2會(huì)覆蓋它，此時(shí)就可能會(huì)在同一個(gè)index位置先后提交一個(gè)不同的日志，這就違反了狀態(tài)機(jī)安全性，產(chǎn)生不一致。也就是說當(dāng)一個(gè)新Leader當(dāng)選時(shí)，由于所有成員的日志進(jìn)度不同，很可能需要繼續(xù)復(fù)制前面term的日志條目，就算復(fù)制到多數(shù)服務(wù)器并且提交，還是可能被覆蓋，因?yàn)榍懊鎡erm對(duì)應(yīng)的日志條目較舊，容易使的沒有這些條目的其他服務(wù)器當(dāng)選Leader，此時(shí)就會(huì)覆蓋這些日志條目。
為了消除上述場(chǎng)景就規(guī)定Leader可以復(fù)制前面任期的日志，但是不會(huì)主動(dòng)提交前面任期的日志。而是通過提交當(dāng)前任期的日志，而間接地提交前面任期的日志。
4.配置變更的時(shí)候，需要保證任何時(shí)候只能有一個(gè)Leader，直接從舊的配置轉(zhuǎn)化到新配置的方案是不安全的，如下圖所示：
轉(zhuǎn)換過程中，server1,server2通過舊配置選出一個(gè)Leader(三臺(tái)中的兩臺(tái)支持)，server3,server4,server5通過新配置選出一個(gè)Leader(五臺(tái)中的三臺(tái)支持)，這樣在同一個(gè)term中就有兩臺(tái)Leader，造成不一致，為了保證安全性，配置更改必須使用兩階段方法。在 Raft 中，集群先切換到一個(gè)過渡配置，我們稱之為共同一致；一旦共同一致已經(jīng)被提交了，那么系統(tǒng)就切換到新的配置上。
過渡配置保證不會(huì)在old與new兩個(gè)配置上同時(shí)產(chǎn)生Leader :
過渡配置是指由 old配置和 new復(fù)合成的一個(gè)新配置（old+new）。
Leader會(huì)將該過渡配置日志先應(yīng)用到本地，然后復(fù)制給集群中的所有成員。所有收到配置的成員，會(huì)直接將配置應(yīng)用到本地。
處于過渡配置的成員，在Leader選舉與提交日志時(shí)規(guī)則發(fā)生了變化，要求分別得到old與new兩個(gè)配置下的多數(shù)成員同意才行。比如：
old：1、2、3
new：2、3、4、5、6 （刪除機(jī)器1，增加機(jī)器4、5、6）
old+new：1、2、3、4、5、6（機(jī)器是old+new所有機(jī)器）
那么處于過渡配置的成員在Leader選舉與提交日志時(shí)，需要得到 old（1、2、3）三個(gè)成員中的多數(shù)支持，以及new（2、3、4、5、6）五個(gè)成員中的多數(shù)支持（而不是old+new中六個(gè)成員的多數(shù)）。
那么上述過度配置如何保證不同時(shí)間段只產(chǎn)生一個(gè)Leader:
1）從old -> old+new配置提交之前
此時(shí)還未產(chǎn)生new配置，因此不可能在new配置下產(chǎn)生Leader。
那么是否可能在old與old+new下分別產(chǎn)生Leader哪？ old下要產(chǎn)生Leader需要old中的多數(shù)投票，old+new下要產(chǎn)生Leader也需要old中的多數(shù)投票，而要在old與old+new下分別產(chǎn)生Leader，則old中至少有一個(gè)成員同時(shí)投票給old與old+new中的Leader。根據(jù)投票規(guī)則，在一個(gè)term下只能投票一次，因此就不可能在old與old+new配置下在同一個(gè)term上分別產(chǎn)生Leader。
而在不同term下產(chǎn)生則不違反規(guī)則，因?yàn)樾碌膖erm下產(chǎn)生的Leader，發(fā)送心跳給舊Leader，舊Leader就會(huì)馬上變成Follower。
2）old+new提交之后
只要old+new這個(gè)配置提交，則意味著該配置已經(jīng)復(fù)制給了old中的多數(shù)成員，那么在old配置中就不可能再產(chǎn)生一個(gè)Leader出來了。只能在old+new與new配置下產(chǎn)生。而在old+new與new中也不可能在同一個(gè)term下分別選舉出Leader，這個(gè)證明與old與old+new配置是一樣的。
若每次增加或者刪除一個(gè)成員不需要過渡配置：
就是說，每次配置變更只能增加或者刪除一個(gè)成員。若滿足則可以直接從old配置轉(zhuǎn)換到new配置。
證明：舊配置有N個(gè)成員，新配置有N+1個(gè)成員，在切換過程中不會(huì)在舊配置與新配置下分別產(chǎn)生Leader。
1）若舊配置下選舉出Leader，那么需要N/2+1個(gè)成員投票。
2）新配置下，從成員數(shù)是N+1去掉以及投票的N/2+1個(gè)成員只剩下N/2個(gè)成員。
3）而新配置下要選舉出Leader需要(N+1)/2+1=N/2+3/2個(gè)成員投票，但是只剩下N/2個(gè)成員可以投票，因此新配置下不可能再選舉出Leader。
4）反過來也一樣。
參考: http://www.blogjava.net/jinfeng_wang/archive/2017/02/03/432287.html
http://blog.csdn.net/hfty290/article/details/75331948
