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

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

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

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

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

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

Leader全權(quán)負(fù)責(zé)管理日志復(fù)制，從而實(shí)現(xiàn)一致性，所以有了Leader這一機(jī)制，一致性問題就可以被分解為上述三大方面了，下面分別說明。

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

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

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

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

Leader 選舉是 Raft 中對時間要求最為關(guān)鍵的方面。只要系統(tǒng)滿足下面的時間要求：

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

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

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

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

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

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

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

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

閱讀原文：Mageekchiu