什么是Raft

Raft是由Diego Ongaro與John Ousterhout的一篇論文中所提出的分布式存儲一致性算法。在分布式系統(tǒng)中，為了防止服務(wù)器數(shù)據(jù)由于只存一份而導(dǎo)致在服務(wù)時由于一個存儲節(jié)點故障就產(chǎn)生服務(wù)完全不可用或數(shù)據(jù)丟失的嚴(yán)重后果，數(shù)據(jù)的存儲會有多個備份副本胁住，分別存儲于不同的存儲服務(wù)器上沦寂，都可以提供服務(wù)。這樣一來爽航，如果有合適的算法能保障各服務(wù)器對同一份數(shù)據(jù)存儲的內(nèi)容一致，并且在一臺服務(wù)的存儲服務(wù)器故障時乾忱，這個集群能以適當(dāng)?shù)倪壿嬊袚Q到其他正常服務(wù)器提供服務(wù)讥珍，那么就可以實實在在地保障分布式存儲服務(wù)的質(zhì)量。Raft就是為這樣的系統(tǒng)服務(wù)的窄瘟。

Raft的特點

• 簡單易學(xué)衷佃。Paxos算法由Leslie Lamport通過論文發(fā)表于1990年，是當(dāng)時最實用的分布式存儲一致性算法蹄葱。有許多上了年頭的分布式系統(tǒng)底層采用的是Paxos氏义。而Raft是由Paxos簡化得來锄列。Diego Ongaro與John Ousterhout在自己的論文中指出：經(jīng)過對比，學(xué)生學(xué)習(xí)Paxos所需時間明顯長于學(xué)習(xí)Raft所需時間惯悠。
• 最終一致性邻邮。存儲一致性根據(jù)對于各個服務(wù)器的同一份數(shù)據(jù)之間允許差異的嚴(yán)格程度不同，可以分為強一致性克婶、最終一致性筒严、弱一致性。根據(jù)CAP定理情萤，一個分布式系統(tǒng)不能同時保障一致性（Consistency）鸭蛙、可用性（Availability）與分區(qū)容錯性（Partition tolerence）。但是經(jīng)過權(quán)衡紫岩，系統(tǒng)可以達(dá)到“BASE”效果：基本可用（Basically available）规惰、軟狀態(tài)（Soft state）、最終一致性（Eventually consistent）泉蝌。Raft所達(dá)到的最終一致性歇万，是指各節(jié)點上的數(shù)據(jù)在經(jīng)過足夠的時間之后，最終會達(dá)到一致的狀態(tài)勋陪。

Raft基本思想

• 選舉與邏輯主從管理贪磺。一個典型的Raft集群由3臺或5臺服務(wù)器組成，各節(jié)點最終都會保存相同的數(shù)據(jù)诅愚。在運行開始時寒锚，集群會通過自動選舉產(chǎn)生一個主節(jié)點（Raft中稱為leader），其他節(jié)點為從節(jié)點（稱為follower）违孝。所有來自客戶端的讀寫請求都要由leader處理刹前；follower若收到了客戶端請求，則要回復(fù)leader的地址雌桑，從而使請求重定向到leader喇喉。當(dāng)探測到leader失效（leader通過心跳機制通知follower自己的存活，超時則認(rèn)為leader故障）校坑，其他節(jié)點將會出發(fā)重新選舉拣技，得到新的leader。
• 用日志存儲寫操作耍目。顯然膏斤，只讀操作不影響存儲一致。所以邪驮，如果能保證所有節(jié)點對于所有寫操作都能按照相同的順序沒有遺漏也沒有多余地保存下來莫辨，那么自然能夠保證最終存儲一致。Raft使用日志（log）存儲寫操作。Leader收到寫操作請求后衔掸，在自己的日志條目存儲中生成對應(yīng)的日志條目（log entry烫幕，簡稱entry）俺抽。之后就只需要把自己的日志記錄復(fù)制（replicate）到各follower即可敞映。

從上面可以看出，Raft的核心問題就是保障：可靠的選舉與日志復(fù)制操作磷斧。實際上這兩點在許多分布式系統(tǒng)中都有應(yīng)用振愿。

Raft的選舉

Raft集群各機之間的RPC報文可分為兩種：添加條目RPC（AppendEntries RPC，以下簡稱AE）與請求投票RPC（RequestVote RPC弛饭，以下簡稱RV）冕末。AE是leader用來向follower加entry使用的。RV是“候選人"（candidate侣颂，是除了leader档桃、follower以外的第三種狀態(tài)，只出現(xiàn)于選舉時）用來向其他follower要求給自己投票的憔晒。

如果超過一定時間藻肄，follower檢測不到來自leader的周期性心跳消息（leader將不含實際entry的AE作為心跳使用），就會變?yōu)閏andidate狀態(tài)拒担。此時嘹屯，Raft集群就會開始選舉leader。在Raft中从撼，時間上有著term的概念州弟，表示一個leader的統(tǒng)治期；每個term有著獨特的遞增的序號低零，稱為term ID婆翔。leader會在自己發(fā)送的AE中都附上自己的term ID。當(dāng)新的candidate產(chǎn)生掏婶，它會在上一個leader的term ID基礎(chǔ)上加1啃奴，作為自己的term ID，并在廣播給所有其他機的RV中也附上新的term ID气堕。任何非candidate的節(jié)點收到了帶有比自己已經(jīng)見過的任何ID更大的term ID的RV時纺腊，就會回復(fù)這個RV，并更新“自己已經(jīng)見過的最大ID”茎芭。如果同時這個RV中說明的candidate含有的日志足夠新（詳細(xì)說明見后文）揖膜，follower就會為這個candidate投票。這樣一來梅桩，任何節(jié)點就都不會為同一個term ID投兩票壹粟。如果一個candidate收到了足夠的票數(shù)（票數(shù)加上自己的一票能夠占集群的多數(shù)），就會開始發(fā)送心跳，宣告自己在這個term內(nèi)的leader地位趁仙，開始服務(wù)洪添。

由于在一個leader失效時，可能有多個follower超時的時刻相同雀费，發(fā)出RV廣播的時刻也大致相同干奢，結(jié)果在新term都得不到足夠的票數(shù)，所以candidate存在等票超時與隨機等待機制盏袄，避免一致沖突忿峻，選不出leader。candidate在等足夠的票時當(dāng)然也會看有沒有其他candidate宣布勝利辕羽。如果都沒有發(fā)生的話逛尚，在一段超時后，candidate們會再開啟新term ID刁愿，但會隨機等待一段時間绰寞，然后才廣播RV請求投票（廣播RV前相當(dāng)于follower，可以投票）铣口。由于隨機等待的時間有長有短滤钱，最終一定會由率先結(jié)束等待的candidate獲勝。

Raft的日志復(fù)制

前面提到枷踏，Raft集群由leader統(tǒng)一處理所有客戶端請求菩暗，會將寫請求轉(zhuǎn)換為log entry，然后用AE向follower發(fā)送來復(fù)制log旭蠕。Leader創(chuàng)建日志條目時停团，會給它附上兩個屬性：term ID與log index。term ID即為自己統(tǒng)治期的ID掏熬，在當(dāng)前term的日志條目都用這個ID佑稠；而log index也是一種遞增序號，但它是在集群的整個運行期間連續(xù)的旗芬∩嘟海跨term時，log index會在前面的的基礎(chǔ)上遞增1疮丛，而非歸零重計幔嫂。如此一來，考慮到選舉機制保證了一個term ID一定對應(yīng)確定的一個leader節(jié)點誊薄，我們由term ID+log index這個組合就一定可以確定唯一的一條日志履恩。

Leader生成了寫操作的日志之后，就通過AE將日志條目發(fā)送到各個follower處呢蔫，讓它們把日志按早晚順序加入自己的日志存儲中切心。如果有集群多數(shù)的節(jié)點（包含leader自己）都成功存儲了一條日志（follower會回復(fù)自己的存儲情況），那么leader就認(rèn)為這條日志及更早的日志的存儲都是安全的，會回復(fù)客戶端寫操作成功绽昏，并會告知集群已經(jīng)可以將到此條的所有日志中的寫操作實際進(jìn)行协屡，修改自己的存儲數(shù)據(jù)。

當(dāng)leader上臺時全谤，會以自己自己的日志存儲為準(zhǔn)肤晓，使其他節(jié)點與自己對齊。如果比自己快啼县，就截掉多的材原；比自己慢沸久，就用自己的日志存儲給它慢慢補足季眷。但是在復(fù)制日志的過程中，各個follower可能因各種原因速度差異較大卷胯。那么如果leader突然故障子刮，而一個復(fù)制的特別慢的follower選舉為leader，那么不就會導(dǎo)致大量寫操作失效嗎窑睁？之所以要保證日志已經(jīng)復(fù)制到了多數(shù)機上挺峡，才可認(rèn)為寫操作成功，就是為了避免這種情況担钮。之前在講解選舉機制時提到：RV要包含candidate的日志存儲版本消息橱赠，也就就是最后一條日志的term ID+log index。如果投票的follower發(fā)現(xiàn)這candidate的版本消息比自己的還要舊箫津，就會拒絕給它投票狭姨。由于只有復(fù)制到了多數(shù)節(jié)點的日志的寫操作才被回報為“成功”，而選舉時必須要獲得多數(shù)票才能當(dāng)選苏遥，所以最終當(dāng)選的leader一定擁有上一個leader所回報為成功的操作的所有日志饼拍，不會缺失。

后記

由于在實際運行中田炭，不論服務(wù)器還是網(wǎng)絡(luò)信道师抄，都是可能發(fā)生故障的。所以Raft其實還有一些額外的措施來保障數(shù)據(jù)的最終一致性教硫。限于篇幅叨吮，本文不再詳述。如有興趣瞬矩，請研讀Raft原論文茶鉴。相關(guān)學(xué)習(xí)資源，包括系統(tǒng)可視化模擬丧鸯、視頻講解蛤铜、比論文更詳細(xì)的講解Raft的書籍，都可以在專題網(wǎng)站上面找到。