摘要：只要系統滿足下面的時間要求廣播時間選舉超時時間平均故障間隔時間就可以選舉并維持一個穩定的。大多數的服務器的平均故障間隔時間都在幾個月甚至更長，很容易滿足時間的需求。

Raft是當前分布式領域最重要的一致性算法之一，今天我們就來好好研究研究這個算法的論文, 還有對應網站, 動畫, 不想看英文的也有中文的翻譯，所以我這邊就不翻譯了，主要還是記錄一下論文重點和自己的心得。

Raft算法作者的初衷是對標Paxos算法（過去十年分布式一致性的事實標準），但是要比它更易理解，主要手段有：

分解，把整個一致性問題拆分為Leader選舉、日志復制和安全機制這三大方面還有角色改變這個小方面。所以模塊化是一個軟件系統可維護、理解和擴展的不二手段。

減少狀態空間的狀態，相比于Paxos，Raft減少了非確定性和服務器之間可以處于不一致的方式。所以在復雜的問題上做減法，可以減少很多不必要的繁瑣的步驟。

Raft使用了更強的Leader，感覺這和我之前看的OceanBase是相似的，就是增強Leader（UpdateServer）或者說單點的作用，加重中心化（這也是社會的運作方式，沒有Leader就是大家一盤散沙，文明是達不到今天這個程度的），要做決策就先選擇一個Leader，然后讓他去協調所有的決議，會更加簡單快速，而Paxos就是P2P或者說弱Leader的方式。事實上，我們之所以使用分布式系統也是迫不得已，如果單臺機器能搞定還要這么多系統干嘛？所以我們也要看到單點系統的好處，那就是一致性很容易保證，所以在分布式系統中使用一個增強（能力和責任）的單點既利于一致性的保證也能獲得分布式的優勢。

Leader全權負責管理日志復制，從而實現一致性，所以有了Leader這一機制，一致性問題就可以被分解為上述三大方面了，下面分別說明。

Raft 的 Leader 是有 Term 時間限制的，類似于租約機制，這個機制能完善單純的心跳(因為節點可能太忙發不出或沒法響應心跳)。
隨機的選舉超時時間可以使得 Leader 選舉很少有選票平分的時候，按 Term number 最大和先來先服務原則可以使得每一個 Term 內最多有一個 Leader（如果沒有 Leader 就會超時進入下一個 Term 進行新的選舉）。Leader 保持身份并阻止其他節點成為 Leader 的方法是不停地向其他節點發送心跳消息（也可以包含需要復制的日志）。

Leader 為客戶端服務，處理所有客戶端請求亦即所有的系統變更，并把日志復制分發給其他節點（包含失敗重試），leader 處理日志不一致的手段是強制follower 復制自己的日志，所以 follower 中與 leader 沖突的日志會被覆蓋（比如未過半數亦即未提交的日志），leader 不刪除自己的日志（只附加原則）。

leader選舉和日志復制都需要一些安全機制來保證每個狀態機都按照相同的順序來執行相同的指令：
①. 選舉限制，除了1中的條件，還要求 candidate 具有已經提交的所有日志條目，所以 voter 會主動拒絕日志沒有自己新（通過Term Number 和 日志長度 兩個指標進行比較）的候選人的投票請求。
②. 提交之前Term內的日志條目時，Leader 會使用這個條目的原始Term Number，而不是使用當前的Term Number，這樣更容易辨別日志，而且要提交之前Term（如 2 ）的日志時必須同時提交當前Term（如 4）的日志，保證得到復制日志的 follower A 下次更有可能成為Leader而不是那些只有較舊日志但是新于A得到的舊日志（如 3 新于 2 ）的follower。換句話來說：old term 中的 log entry 需要被間接提交，即使其滿足復制數過半也必須要等到當前 term 中有 entry 被提交時才能跟著一起提交

如果 follower 或者 candidate 崩潰了，那么后續發送給他們的請求都會失敗。Raft 中處理這種失敗就是簡單的通過無限的重試，因為Raft的這種請求都是冪等的，所以這樣重試不會造成任何問題。比如，一個follower如果收到附加日志請求但是他已經包含了這一日志，那么他就會直接忽略這個新的請求。

Leader 選舉是 Raft 中對時間要求最為關鍵的方面。只要系統滿足下面的時間要求：

廣播時間（broadcastTime） << 選舉超時時間（electionTimeout） << 平均故障間隔時間（MTBF）

Raft 就可以選舉并維持一個穩定的Leader。當Leader崩潰后，整個系統會大約相當于選舉超時的時間里不可用，廣播時間和平均故障間隔時間是由系統決定的，但是選舉超時時間是我們自己選擇的， Raft的請求 要接收方將信息持久到存儲中去，所以廣播時間大約是 0.5 毫秒到 20 毫秒，取決于存儲的技術。因此，選舉超時時間可能需要在 10 毫秒到 500 毫秒之間。大多數的服務器的平均故障間隔時間都在幾個月甚至更長，很容易滿足時間的需求。

對于客戶端來說，只要得到leader的ok回復就可以認為操作成功了，未得到ok（失敗或超時）就需要重試。那么Raft是怎么保證這個語義的呢？
Leader未把日志未復制過半就掛了那么此次請求客戶端肯定會知道是失敗的，沒影響；Leader把日志復制過半但是未回復ok就掛了的話，這些日志之后可能被提交也可能被覆蓋，這就需要客戶端帶上唯一請求id重試，新的leader發現該id已經在日志中出現并且可被提交就直接回復ok，否則就重新執行一次這個請求；leader回復ok但是未提交就掛了的話，依賴于old entry的提交機制，這個請求還是能被落盤的。
通過這三個階段不同的應對機制保證了ok的語義。

Raft也是能夠應對腦裂問題的，比如ABCDE5個節點，A是leader，一開始保證正確的同步，某時刻，假設A沒發出心跳給B(比如太忙)或者B沒收到心跳（比如分區）使得B超時：

如果此時A有新的寫入，那么此時CDE至少有兩個日志比B新（多數），這是B發起選舉后是不可能得到大多數投票的

如果此時A沒有沒有新的寫入，那么B是可以選舉成功的（term自增且擁有全部已提交日志），然后B成為leader處理新的請求，如果此時AB通了，A會發現自己term落后而自動成為follower，其作為leader期間的提案都會得不到提交而回滾

所以要么是避免腦裂選主，要么是腦裂后老leader自動降級為follower。腦裂問題就可以這樣被解決了。當然最好的辦法還是在節點之前加一個專線，降低分區的概率。

集群狀態切換通過一個共同一致（新老配置的結合）的中間狀態轉換實現，這樣基于兩階段的做法可以使得集群平滑地進行狀態遷移。這一塊沒仔細看，不過 etcd 等 raft 實現都是采用了更加簡潔和安全的一次只能變更一個節點的 single Cluser MemberShip Change 算法。

閱讀原文：Mageekchiu