Raft一致性共識演演算法論文學習
論文地址：https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
看完raft共識演演算法，腦袋非常懵，所以寫一篇學習筆記，記錄一下。
raft演演算法主要解決三個模組的問題：領導人選舉、紀錄檔複製和安全性。當然除了這三個方面，論文對於raft的安全機制，叢整合員變更和紀錄檔壓縮都做了比較詳細的描述。
一、複製狀態機
複製狀態機（Replicated state machine）的概念就是，相同的初始狀態 + 相同的輸入 = 相同的結束狀態。也就意味在多節點叢集中，從相同的初始狀態開始，執行相同的一串命令，產生相同的最終狀態。
在 raft 中，leader將使用者端請求封裝成一個一個 log entry 中，將這些 log 傳送到 follow 節點，然後大多數的節點按照同樣的順序應用 log entry 中的 command，依據複製狀態機的理論，大家最後的狀態是會一致的。在分散式場景中，各個節點就是依靠共識演演算法，保證命令序列的一致，從而始終保持它們的狀態一致，從而實現高可用性。
論文提及raft演演算法的特性有以下幾點：
- 安全性保證(絕對不會返回一個錯誤的結果):在非拜占庭錯誤情況下，包括網路延遲、分割區、丟 包、冗餘和亂序等錯誤都可以保證正確。（這裡的拜占庭錯誤指的是節點的本身就不可靠，變成叢集中的惡意節點，它為了阻撓真實資訊的傳遞以及有效一致的達成，會向各個節點傳送前後不一致的資訊）
- 可用性:叢集中只要有大多數的機器可執行並且能夠相互通訊、和使用者端通訊，就可以保證可用。 因此，一個典型的包含 5 個節點的叢集可以容忍兩個節點的失敗。伺服器被停止就認為是失敗。他們當有穩定的儲存的時候可以從狀態中恢復回來並重新加入叢集。
- 不依賴時序來保證一致性:物理時鐘錯誤或者極端的訊息延遲只有在最壞情況下才會導致可用性問題。
- 通常情況下，一條指令可以儘可能快的在叢集中大多數節點響應一輪遠端過程呼叫時完成。小部分 比較慢的節點不會影響系統整體的效能。
二、狀態變化
在任意時刻，每個伺服器節點都只處於 leader，follower或candidate這三個狀態之一。
- leader：領導者，在通常情況下，系統中只有一個領導人並且其他的節點全部都是跟隨者。
- follow：跟隨者，他們不會傳送任何請求，只是簡單的響應來自領導者或者候選人的請求。
- candidate：選舉者，當叢集沒有領導者時，跟隨者會轉變成 candidate
starts up：叢集啟動時
time out, start election：follow 在沒有收到 leader 心跳後開始選舉變成選舉者 candidate；
time out，new election：在當前選舉中沒有出現 leader，此輪次超時後進行下一輪選舉
dicocers current leader or new term：當發現已經選出新的 leader，也就是收到 leader 的心跳資訊，或者發現已經開始新的 term 任期，選舉者狀態 candidate 將會轉化成 follow。
dicover serer with higher term：當前的 leader 可能因為網路分割區的問題和叢集中的其他 follow 失去心跳聯絡，這時候叢集選舉出了新的 leader，這時候 leader 就要變成 follow 狀態。
receives votes from mahority servers：當 candidate 收到叢集中大多數的投票時，會被選舉成新的 leader，進入 leader 狀態
這圖展示了 raft 中幾個狀態的轉化。
在論文中解釋了 term 任期
raft將時間劃分成一個一個的任期，每個任期開始都是一個選舉， 選舉成功後 leader 會管理叢集到任期結束，如果任期中沒有選舉成功，那麼這個任期會因為沒有領導人而結束，這時候 candidate 因為選舉超時（也就是沒有選出 leader 的超時時間）而自動開啟下一個任期 term。
他們通過 rpc 請求來進行伺服器之間的遠端呼叫和通訊，並且基本的一致性演演算法只需要兩種型別的 RPCs。請求投票(RequestVote) RPCs 由候選人在選舉期間發起，然後附加條目 (AppendEntries)RPCs 由領導人發起，用來複制紀錄檔和提供一種心跳機制。除此之外在伺服器之間傳輸快照增加了第三種 RPC。
- RequestVote RPC（請求投票）：由 candidate 在選舉期間發起。
- AppendEntries RPC（追加條目）：由 leader 發起，用來複制紀錄檔和提供一種心跳機制。
在論文中對於 raft 的 rpc 實現有一個演演算法濃縮總結：還有一個 rpc 是 state 的狀態查詢 rpc 就不列舉了
| rpc介面 | 引數 |
返回值 |
||||||||||||
| RequestVote RPC |
|
|
||||||||||||
| 接受者實現 |
1. 如果 term < currentTerm 返回 false。如果候選人的任期 term 比接收的 follow 跟隨者的當前任期還小，那就拒絕投票。 2. 如果 votedFor 為空或者為 candidateId，並且候選人的紀錄檔至少和自己一樣新，那麼就投票給他（votedFor指的是這個follow節點把票投給的候選者） |
|||||||||||||
| rpc介面 | 引數 | 返回值 | ||||||||||||||||
| AppendEntries RPC |
|
|
||||||||||||||||
| 接受者實現 |
1. 返回 false 如果領導者的任期小於接收者的當前任期 2. 返回 false 如果接收者紀錄檔中沒有包含這樣一個條目，即該條目的任期在prevLogIndex上不能和 prevLogTerm匹配上 3. 如果一個已經存在的條目和新條目發生了衝突(因為索引相同，任期不同)，那麼就刪除這個已經存在的條目以及它之後的所有條目 4. 追加紀錄檔中尚未存在的任何新條目 5. 如果領導者的已知已經提交的最高的紀錄檔條目的索引 leaderCommit 大於接收者的已知已經提交的，最高的紀錄檔條目的索引 commitIndex 則把接收者的已知已經提交的最高的紀錄檔條目的索引 commitIndex 重置為領導者的已知已經提交的最高的紀錄檔條目的索引leaderCommit，或者是上一個新條目的索引取兩者的最小值（就是會把follow節點的commitindex之前的都提交了） |
|||||||||||||||||
除此之外所有的節點需要遵循的演演算法規則為：
| 角色 | 遵循規則 |
| 所有服務者 |
1. 如果 term < currentTerm 返回 false 2. 如果 votedFor 為空或者為 candidateId，並且候選人的紀錄檔至少和自己一樣新，那麼就投票給他 |
| follower（5.2） |
1. 如果 currentIndex > lastApplied，那麼就 lastApplied 加一，並把 log[lastApplied] 應用到狀態機中（commitIndex - 已知已提交的最高的紀錄檔條目的索引，初始值為0，單調遞增。lastApplied - 已經被應用到狀態機的最高的紀錄檔條目的索引，初始值為0，單調遞增） |
|
candidate （5.2） |
1. 在轉變成候選人後就立即開始選舉過程 |
| leader |
1. 一旦成為領導人:傳送空的附加紀錄檔 RPC(心跳) 給其他所有的伺服器，這裡就是 no-op 機制;在一定的空餘時間之後不停的重複傳送，以阻止跟隨者超時（5.2） |
英文版本
三、領導者選舉
raft 內部有一種心跳機制，如果存在 leader，那麼它就會週期性的向所有 follower 傳送心跳，來維持自己的地位。如果 follower 在一段時間滅有收到心跳，那麼它會認為沒有 leader，開始進行下一輪選舉。
開啟下一個選舉後，follow 會轉先增加自己的當前任期，並且轉變成 candidate 狀態，然後投票給自己，向其他節點傳送 RequestVote RPC。這裡因為有超時控制，follower 會根據超時時間陸續進入下一輪選舉 term，所以不存在同時都變成 candidate 投票給自己的情況。
對於沒有成為 canditate 的 follower 節點，按照先來先得的原則進行投票。
當 s2 宕機後
開始投票選舉
確認後提交後正式進入term=3的任期
這裡的狀態機演示可以在網頁上自行偵錯：https://raft.github.io/raftscope/index.html
當 candidate 在等待其他節點投票給自己的時候，此時會有三種結果，上圖是成功當選的結果：
- 它獲得超過半數投票贏得了選舉 -> 成為主 leader 後傳送心跳
- 其他節點贏得選舉（這裡就是上面的 S4 節點），收到新 leader 心跳後，如果新 leader 的任期號不小於自己當前的任期號，那麼就從 candidate 變成 follower 狀態
- 一段時間後如果沒有任何獲勝者，每個candidate 都在一個自己的隨機選舉超時時間後增加任期號開始新一輪的投票，論文中給的隨機選舉超時時間為 150~300ms。
四、紀錄檔複製
叢集中 leader 是肯定有最新的紀錄檔的，但是其他節點不清楚，基本都是處於一直追趕 leader 紀錄檔進度的情況。
在使用者端提供服務中，使用者端的每一個請求都包含一條被複制狀態機執行的指令。領導人把這條指令作為一條新的紀錄檔條目附加到紀錄檔中去，然後並行的發起附加條目 RPC 給其他的伺服器，讓他們複製這條紀錄檔條目。當這條紀錄檔條目被安全的複製
領導人會應用這條紀錄檔條目到它的狀態機中然後把執行的結果返回給使用者端。如果跟隨者崩潰或者執行緩慢，再或者網路丟包，領導人會不斷的重複嘗試附加紀錄檔條目 RPCs (儘管已經回覆了使用者端)直到所有的跟隨者都最終儲存了所有的紀錄檔條目。
也就說寫請求會在 leader 進行紀錄檔複製給大多數 follower 節點成功後返回結果。
一條紀錄檔中需要三個資訊：
- 狀態機指令（就是儲存的資料比如下圖的 x->3）
- leader 的任期號（term）
- 紀錄檔號（紀錄檔索引）
圖中紀錄檔由有序序號標記的條目組成。每個條目都包含建立時的任期號(圖中框中的數位)，和一個狀態機需要執行的指令。
一個條目當可以安全的被應用到狀態機中去的時候，就認為是可以提交了。 是的，紀錄檔還有兩個狀態，就是 未提交 和 已提交
未提交指的是，當 leader 傳送 AppendEntriesRPC 請求給其他節點後，讓他們複製該紀錄檔條目，這時候紀錄檔的狀態就是未提交的。一但超過半數的節點 follower 響應成功，也就意味著這個紀錄檔已經成功複製到大多數節點上了，那麼此時leader就會把結果返回給使用者端，並且在本地也執行復制儲存該紀錄檔的操作，在leader中此時紀錄檔條目是已提交狀態。但是注意的是，此時大多數節點中的紀錄檔條目還沒有提交。是的，raft 是使用的累計確認的機制，通過下一個心跳才讓大多數提交當前紀錄檔條目的，因為 follower 在下一個心跳來臨之前並不知道該紀錄檔是否需要改成已提交的。
當收到S5領導者節點傳送的append請求後
當S5節點收到大多數節點的回覆後會把紀錄檔條目設定為已提交
傳送下一個心跳確認會帶上最後一個確認的紀錄檔條目
最後
下面這裡討論一下當紀錄檔複製過程中如果 leader 和 follow 出現崩潰和緩慢超時的情況，raft 演演算法是怎麼保證繼續紀錄檔複製並且保證每個副本順序一致
1. 如果有 follower 因為某些原因沒有給 leader 響應，那麼 leader 會不斷的重新傳送追加條目請求 appendRPC，哪怕 leader 已經回覆了使用者端
2. 如果有 follower 崩潰後恢復，此時 raft 追加條目的一致性檢查生效，保證 follower 能按照順序回覆崩潰後缺失的進度
raft的一致性檢查，leader 在每一個發往 follower 的追加條目 appendRPC 中，會放入前一個紀錄檔條目的索引prelogIndex 和 任期號term。 如果 follower 找不到這個前一個紀錄檔，那麼它就會拒絕紀錄檔，leader 收到拒絕後，會傳送前一個紀錄檔條目，從而逐漸定位到 follower 第一個缺失的紀錄檔。這裡其實對於不同的 raft 實現演演算法，會有一定的優化，leader 收到拒絕後可以不是傳送前一個紀錄檔條目，可以通過二分查詢啊，或者下一個傳送當前term任期的第一個紀錄檔，加快查詢的程序。
下圖，S3落後 leader 的紀錄檔條目非常多，所以在紀錄檔複製時：
第一次，S5傳送給S3 appendRPC 時，S3 因為 preIndexIndex（等於8） 和它自己當前的 logCurrentindex（等於6） 不符合，所以第一次的時候 S5 並不能將自己的 index=9 的紀錄檔條目複製給 s3
第二次，S5傳送給S3 appendRPC 時，preIndexIndex=7，還是和S3的 logCurrentindex（等於6） 不符合，所以還是不能將 index=8 的紀錄檔條目複製給 s3
第三次，成功複製，將 index=7 的紀錄檔條目複製給 s3
3. 如果 leader 崩潰，那麼崩潰的 leader 可能已經複製到部分 follower ，但是資料還沒有提交 ，而被選出的新leader又可能不具備這些紀錄檔，這樣就有部分 follow 中的紀錄檔和新 leader 的紀錄檔不相同。
raft 在這種情況下，leader 會通過強制 follower 複製它的紀錄檔來解決不一致的問題，這意味著 follower 中跟 leader 中衝突的紀錄檔條目會被新 leader 的紀錄檔條目覆蓋（注意這裡說是未提交的，也就是虛線的資料，意味著這些資料並沒有提交，所以不違反外部一致性原則）
例如論文中提出的例子
當一個領導人成功當選時，跟隨者可能是任何情況(a-f)。每一個盒子表示是一個紀錄檔條 目;裡面的數位表示任期號。跟隨者可能會缺少一些紀錄檔條目(a-b)，可能會有一些未被提交的 紀錄檔條目(c-d)，或者兩種情況都存在(e-f)。例如，場景 f 可能會這樣發生，某伺服器在任期 2 的時候是領導人，已附加了一些紀錄檔條目到自己的紀錄檔中，但在提交之前就崩潰了。很快這個機器就被重啟了，在任期 3 重新被選為領導人，並且又增加了一些紀錄檔條目到自己的紀錄檔中;在任 期 2 和任期 3 的紀錄檔被提交之前，這個伺服器又宕機了，並且在接下來的幾個任期裡一直處於宕機狀態。
當a-e的任意一個節點當選為 leader 時，都會強制將 f 節點變成和 leader 一致的資料。
總結：
ralf 通過這樣的紀錄檔複製機制，leader 不需要任何特殊的操作來使得紀錄檔恢復到一致狀態，leader 只需要進行正常的操作，然後紀錄檔就能在 appendRPC 回覆中通過一致性檢查失敗的時候自動趨於一致。
leader 從來不會覆蓋或者刪除自己的條目，只會讓 follower 強制和 leader 保持一致，這樣可以保證：
- 只要過半的伺服器鄭航執行，raft 就能接收，複製並應用新的紀錄檔條目
- 在正常情況下，新的紀錄檔條目可以在一個 rpc 來回中杯複製給叢集中過半的機器
- 單個執行慢的follow（如果不是超過叢集的大多數）並不會影響整體的效能，也不會影響資料的一致性
五、安全性
上面紀錄檔複製實際上是解決資料一致性的問題，那麼安全性的問題是什麼？論文舉例說，一個跟隨者可能會進入不可用狀態同時領導人已經提交了若干的紀錄檔條目，然後這個跟隨者可能會被選舉為領導人並且覆蓋這些紀錄檔條目;因此， 不同的狀態機可能會執行不同的指令序列。 也就是叢集中可能選擇一個紀錄檔條目落後很多的節點當選成為 leader，並且強制覆蓋其他節點的資料。以下規則可以保證在各類宕機問題下都不會出錯：
- Leader 宕機：選舉限制
- Leader 宕機：新 leader 是否提交之前任期內的紀錄檔條目
- Follower 和 Candidate 宕機處理
- 時間和可用性限制
下面進行逐條的解釋：
- Leader 宕機：選舉限制
如果一個 follower 落後了 leader 若干條紀錄檔（但是沒有漏一整個任期），那麼下次選舉時，它依然可能當選為 leader。當它當選為 leader 時，它因為缺失最新的那部分紀錄檔，從而導致狀態機和其他節點的不一致，並且永遠無法達成一致。所以此規則對候選人增加了一個限制，也就是被選出來的 leader 必須保證為一定包含了之前各個任期所有被提交的紀錄檔條目。
在 RequestVoteRPC 中，引數有 lastLogIndex（候選者自己最後一個紀錄檔號） 和 lastLogTerm（候選者自己最後一個紀錄檔任期）
raft 中收到投票選舉請求的節點，會對比自己紀錄檔中最後一條紀錄檔的條目索引值，和自己當前的任期號比較新來判斷是否要投票給這個候選者。如果沒有自己的新，它就拒絕投票。
當時這裡會出現如下圖的情況：(c)中原本已經複製到大多數節點的index=2紀錄檔，在(d)中由於S5節點當選為 leader ，則被強制覆蓋，導致index=2的資料無了
在 (a) 中， S1 是領導者，部分的複製了索引位置 2 的紀錄檔條目。在 (b) 中，S1 崩潰了，然後 S5 在任期 3 裡 通過 S3、S4 和自己的選票贏得選舉，然後從使用者端接收了一條不一樣的紀錄檔條目放在了索引 2 處。然後到 (c)，S5 又崩潰了;S1 重新啟動，選舉成功，開始複製紀錄檔。在這時，來自任期 2 的 那條紀錄檔已經被複制到了叢集中的大多數機器上，但是還沒有被提交。如果 S1 在 (d) 中又崩潰 了，S5 可以重新被選舉成功(通過來自 S2，S3 和 S4 的選票)，然後覆蓋了他們在索引 2 處的紀錄檔。
- Leader 宕機：新 leader 是否提交之前任期內的紀錄檔條目
領導人知道一條當前任期內的紀錄檔記錄是可以被提交的，只要它被儲存到了大多數的伺服器上。如果一個領導人在提交紀錄檔條目之前崩潰了，未來後續的領導人會繼續嘗試複製這條紀錄檔記錄。然而，一個領導人不能斷定一個之前任期裡的紀錄檔條目被儲存到大多數伺服器上的時候就一定已經提交了。 這裡說的情況就是上面所說的情況，有可能已經在大多數節點中提交的資料被新 leader 給覆蓋了。
在論文裡這一段我看了很久，確實比較難以理解這裡想表達的意思，Raft 永遠不會通過計算副本數目的方式去提交一個之前任期內的紀錄檔條目。只有領導人當前任期裡的紀錄檔條目通過計算副本數目可以被提交，一旦當前任期的紀錄檔條目以這種 方式被提交，那麼由於紀錄檔匹配特性，之前的紀錄檔條目也都會被間接的提交。
如果上面所說的這一段規則，那麼必然會出現新leader被選擇出來後立馬就把舊 term 的資料給覆蓋提交的情況。如下圖
在 (c) 中，當前的 leader 為 s1，此時的 term=4，此時s1宕機了。然後 s5 當選為最新的 leader ，term=5。此時 s5 順利的把當前的 index=2 term=3 的紀錄檔複製給了全部叢集，主要看這個紀錄檔條目是虛線框，意味著沒有提交的。此時如果再請求新增一個 term=5 index=3 的紀錄檔條目，這個時候吧這個紀錄檔條目複製傳送給其他節點後，藍色的紀錄檔部分才會從虛線變成實現，變成提交狀態。
這以規則的目的是保證，新選舉出來的 leader 不會在當前 term 內的第一條紀錄檔條目請求提交前宕機，也就保證了資料肯定是最新的最可靠的，因為宕機的 leader 它們的資料都不可信，也就是 term=2 和 term=4 任期中提交的資料。雖然複製給了大多數，但是並沒有在此任期提交 term=4 的紀錄檔資料，所以被認為是髒資料。
- Follower 和 Candidate 宕機處理
這裡的崩潰宕機比leader宕機要簡單，因為宕機後傳送給他們的 requestVote 和 appendEntries 請求都會失敗。raft 通過無線重試的方法來處理這種失敗，如果崩潰的機器重啟了，那麼這些rpc就會成功的完成。如果一個伺服器接收了一個rpc，但是還沒有響應的時候宕機了，那麼重啟之後會再次收到相同的請求。這裡重複的請求是 leader 快取了這個 follower 節點相關的資訊，大多數是 stateRPC 中的引數。這裡插個題外話，如果 follower 節點過多的話，會不會導致 leader 的負擔非常大，因為每個節點都要傳送心跳，然後還要記住每個節點的狀態資訊？
- 時間和可用性限制
raft 只要滿足以下的時間要求，整個系統就能選舉出並維持一個穩定的 leader。
廣播時間(broadcastTime) << 選舉超時時間(electionTimeout) << 平均故障間隔時間 (MTBF)
廣播時間指的是從一個伺服器並行的傳送 RPCs 給叢集中的其他伺服器並接收響應的平均時間。選舉超時時間就是在 candidate 的選舉的超時時間限制。然後平均故障間隔時間就是對於 一臺伺服器而言，兩次故障之間的平均時間。
六、叢整合員變更
在叢整合員變更，或者需要改變叢集設定的時候（比如增刪節點、替換宕機的機器或者改變複製的程度），raft可以進行設定變更自動化。因為這個時候其實是最容易出現錯誤的，比如宕機出現，可能會造成叢集腦裂的問題。raft 使用的是類似於兩階段提交的方法，來保證轉換過程中不會出現同一任期的兩個 leader，不會出現叢集變成兩個獨立的大多數的問題。
比如論文中這裡，從三臺節點增加到五臺節點過程中，S4S5是新加入節點，設定變更的時候會出現 two dishoint majorities ，也就是叢集可能會出現兩個 leader 。
如下圖就是發生上面問題的過程：
階段a. 叢集存在 S1 ~ S3 三個節點，我們將該成員設定表示為 C-old，綠色表示該節點當前檢視(成員設定)為 C-old，其中紅邊的 S3 為 leader。
階段b. 叢集新增了 S4、S5 兩個節點，該變更從 leader 例如，我們將 S1 ~ S5 的五節點新成員設定表示為 C-new，藍色表示該節點當前檢視為 C-new。
階段c. 假設 S3 短暫宕機觸發了 S1 與 S5 的超時選主。
階段d. S1 向 S2、S3 拉票，S5 向其它全部四個節點拉票。由於 S2 的紀錄檔並沒有比 S1 更新，因此 S2 可能會將選票投給 S1，S1 兩票當選(因為 S1 認為叢集只有三個節點)。而 S5 肯定會得到 S3、S4 的選票，因為 S1 感知不到 S4，沒有向它傳送 RequestVote RPC，並且 S1 的紀錄檔落後於 S3，S3 也一定不會投給 S1，結果 S5 三票當選。最終叢集出現了多個主節點的致命錯誤，也就是所謂的腦裂。
在 raft 中為了避免出現這樣的問題，所以用了兩階段的方法。叢集在發起變更的時候會切換到一個過渡的設定，也就是（b）中 leader 為 s3 時，收到叢整合員新增的命令，此時會變成聯合一致的狀態（joint consensus）
- 第一階段，leader 發起 C(old-new) 讓叢集進入聯合一致狀態，這時候所有 rpc 都要在新舊兩個設定中都達到大多數才算成功
- 第二階段，leader 發起 C(new) 讓叢集進入新設定狀態，這時候 rpc 只要在新設定叢集下能達到大多數就算成功。
在聯合一致（joint consensus）中，論文說明此階段 raft 需要遵循一下幾點
- 紀錄檔條目被複制給叢集中新、老設定的所有伺服器。
- 新、舊設定的伺服器都可以成為領導人。
- 達成一致(針對選舉和提交)需要分別在兩種設定上獲得大多數的支援。特別是這一條，非常重要
來看看在變更階段的設定切換示意圖
虛線表示已經被建立但是還沒有被提交的設定紀錄檔條目，實線表 示最後被提交的設定紀錄檔條目。領導人首先建立了 C(old-new) 的設定條目在自己的紀錄檔中，並提 交到 C(old-new) 中(C-old 的大多數和 C-new 的大多數)。然後他建立 C-new 條目並提交到 C- new 中的大多數。這樣就不存在 C-new 和 C-old 可以同時做出決定的時間點。
估計大多人看到這裡還是會比較懵逼，下面我們分別討論下如果 leader 在上圖不同時段宕機，叢集會發生什麼變化，就知道 raft 是怎麼避免腦裂問題的發生了。
1. leader 在 C(old-new) 聯合一致未提交的時候宕機
S1S2S3是舊叢集，S4S5是新加入叢集，當s3領導者開始提交 C(old-new) 發起聯合一致時，注意此時還沒提交 C(old-new) 。這個時候 S3 宕機，S1S2選舉超時開始下一輪term，然後S1S2會產生一個老設定的 leader，因為可以投票給自己並且獲取到對方一票，所以 S1S2 都有可能變成舊叢集的 leader，而不需要宕機的 S3。
然後 S3S4S5 叢集中的任何一個想要成為 leader 的話，需要在老設定叢集 S1S2S3 ，和新叢集 S1S2S3S4S5 中都拿到超過半數選票才能當選。S4 和 S5 是不可能成為新 leader 的，因為在舊設定 S1S2 中根本不知道有新叢集的節點 S4S5，所以舊叢集肯定是不能拿到選票的，也就不可能成為舊叢集的 leader。唯一有機會成為 leader 的S3，如果在 S1S2 之中成為 leader 後，也是不可能成為舊叢集的 leader 的，所以叢集就回退到聯合一致的狀態之前了，也就是叢集變更失敗，但是不會出現兩個 leader。
如果在 S1S2 超時之前，S3就從宕機恢復，並且成為舊叢集的leader，並且在新叢集也硬的了大多數，也就是 S4S5 的選票，那麼 S3 從宕機中恢復，繼續開始叢整合員變更。
在S3中將 C(oid-new) 設定都複製到了新舊叢集中的大多數的時候，比如下面
舊叢集：S2S3，新叢集：S2S3S4。這時候就可以提交 C(old-new) 了
2. leader 如果在 C(old-new) 已提交但 C-new 未發起的時候宕機
這個時候選舉限制安全性規則決定了選出的新 leader 肯定是具有 C(old-new) 設定的，所以也就不存在腦裂的可能。C(old-new) 提交後，leader 就會發起 C-new，這時候 leader 只需要滿足新設定的條件就可以提交紀錄檔。
3. leader 在 C-new 已發起複製時候宕機
對於這種情況，已經複製了 C-new 的節點會只按新設定選舉，沒有複製 C-new 的節點會按照新老設定選擇，然後新 leader 會再次再次提交 C-new，所以宕機也無所謂了。
如果此時 leader S3 宕機了，C-new 會不會覆蓋呢？不會的，因為處於聯合一致狀態的節點，也就是說只複製 C(old-new) 但是沒有複製 C-new 的節點，必須要在兩個新舊叢集中獲得大多數選票才能選舉成功，而 S2S3 不會投票給 S1S4S5 中的一個，因為它紀錄檔是領先的，所以只有 S2 才能當選，已提交的 C-new 是不會覆蓋的。
叢整合員變更還有三個補充規則需要說明一下：
- 新增節點時，需要新增的節點一定會先完成紀錄檔同步，然後再開始叢整合員的變更，這個時候新增的節點不對外提供服務，就只是紀錄檔複製追上 leader
- 縮減節點時，leader 本身可能就是要縮減的節點，這時它會在完成 C-new 提交後自動退位
- 為了避免下線的節點超時選舉影響叢集執行，伺服器會在它確信叢集中有 leader 存在時拒絕 requestVoteRPC。因為 C-new 的新 leader 不會再傳送心跳給要退出的節點，如果這些節點沒有及時下線，那麼它們超時後會發起選舉，導致叢集進入選舉階段，影響叢集正常執行。所以一個節點如果在最小超時時間之內，收到了 requestVoteRPC 請求，那麼它會拒絕此 RPC。
七、紀錄檔壓縮
raft 的紀錄檔在正常操作中不斷的增長，但是在實際的系統中，紀錄檔不能無限制的增長。隨著紀錄檔不斷增長，他會佔用越來越多的空間，花費越來越多的時間來重置。如果沒有一定的機制去清除紀錄檔裡積累的陳舊的資訊，那麼會帶來可用性問題。
快照是最簡單的壓縮方法。在快照系統中，整個系統的狀態都以快照的形式寫入到穩定的持久化儲存中，然後到那個時間點之前的紀錄檔全部丟棄。快照技術被使用在 Chubby 和 ZooKeeper 中，接下來的會介紹 raft 中的快照技術。
圖中展示了 raft 中快照的基礎思想。每個伺服器獨立的建立快照，只包括已經被提交的紀錄檔。主要的工作包括將狀態機的狀態寫入到快照中。raft 也包含一些少量的後設資料到快照中: 最後被包含索引指的是被快照取代的最後的條目在紀錄檔中的索引值(狀態機最後應用的紀錄檔)，最後被包含的任期指的是該條目的任期號。保留這些資料是為了支援快照後緊接著的第一個條目的附加紀錄檔請求時的一致性檢查， 因為這個條目需要前一紀錄檔條目的索引值和任期號。為了支援叢整合員更新，快照中也將最後的一次設定作為最後一個條目存下來。一旦伺服器完成一次快照，他就可以刪除最後索引位置之前的所有紀錄檔和快照了。