分布式一致性算法Raft简介(下)
slide 15：
?
這一節開始講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：
?
任何實現了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：
?
接著上個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：
?
考慮最有趣的一種場景：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：
?
現在考慮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：
?
接前文；目前為止，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：
?
現在，我們保證了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：
?
接上文繼續講述，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：
?
接上文，修復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：
?
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：
?
現在講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：
?
然而，上一個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：
?
這是raft協議的第6部分：系統配置的變更機制。
系統配置指的是組成集群的各個server的信息。如每個server的id、用于通訊的網絡地址等。這些信息非常重要，因為這些決定了集群中“大多數”（majority）的組成，而選舉leader、commit log entry等都取決于majority vote。
我們必須要支持系統配置變更，因為機器可能宕機，我們需要用新機器替代老機器；或集群管理員想更改集群的degree of replication（復制因子、副本系數）。我們想讓系統自動而安全（automatic and safe）地完成這些，而不至于變更配置導致系統崩潰。
slide 28：
?
重要的是，我們必須意識到：我們不能直接地將舊配置切換成新配置。為什么呢？看圖中例子：
設想系統正在運行，系統配置中有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：
?
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：
?
Joint-consensus這部分還有一些細節：
1）在變更的過程中，來自新舊配置的server都有可能成為leader；
2）如果當前leader不在Cnew配置里面，則一旦Cnew提交，它必須step down（下臺）；
這意味著，舊leader不再是新配置的成員之后，還有可能繼續服務一小段時間；即舊leader可能在Cnew配置下繼續當leader（雖然實質上并不是leader，但仍發揮leader的作用），直到Cnew的entry能夠復制到足夠多的server上而被committed；
slide 31：
?
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服務，不能只是不出問題，還要保證能及時地干活、能良好地運轉下去。）
?
總結
以上是生活随笔為你收集整理的分布式一致性算法Raft简介(下)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 分布式一致性算法Raft简介(上)
- 下一篇： kubernetes(二)k8s组件