raft是一個用于管理復(fù)制日志的協(xié)議苗胀，raft首先先選舉出一個leader含潘，然后由leader完全管理復(fù)制日志淀歇，以實現(xiàn)一致性。

使用raft簡化了復(fù)制日志的管理姚糊，如leader在接受了客戶端發(fā)送的日志條目之后贿衍，在不需要詢問其他服務(wù)器的情況下決定把日志條目放在哪里；且數(shù)據(jù)流向只能從leader到其他服務(wù)器救恨，leader將日志復(fù)制到其他服務(wù)器贸辈，并告訴它們什么時候可以安全的把日志之條目應(yīng)用到他們的狀態(tài)機上。如果leader和其他服務(wù)器斷開連接肠槽，這種情況下擎淤，新的leader被選舉出來。

使用leader方案秸仙，Raft把一致性問題分解為三個相關(guān)的子問題：

leader選舉：當前l(fā)eader故障時必須選舉出一個新的leader揉燃。

日志復(fù)制：leader必須從客戶端接收日志條目并復(fù)制到集群中其他服務(wù)器上，強制其他日志和它的保持一致筋栋。

正確性：Raft的關(guān)鍵屬性是圖3中描述的狀態(tài)機正確屬性：如果一個服務(wù)器把一條日志條目應(yīng)用到了它的狀態(tài)機上，那么不會有其他服務(wù)器在相同的日志偏移處應(yīng)用一條不同的指令正驻。5.4節(jié)描述了Raft如何保證這一點弊攘；解決方案包括了5.2節(jié)中描述的對選舉機制額外的一些限制抢腐。

Focus：

一個Raft集群包含了多個服務(wù)器；典型的數(shù)字是5個襟交，這樣的系統(tǒng)可以容忍兩臺服務(wù)器的故障迈倍。在任意給定的時刻，每個server都處于三種狀態(tài)的一種：leader,follower, 或者candidate捣域。在一般情況下啼染，只有一個leader，其他server都是follower焕梅。Followers是被動的：他們不會自己發(fā)起請求迹鹅，只會響應(yīng)來自leader和candidate的請求。leader處理所有的客戶端請求(如果客戶端請求到一個follower贞言，follower會把請求重定向到leader)斜棚。第三種狀態(tài)，candidate该窗，是用于選舉新leader的缀拭。

Raft的leader是任期制的不同，Raft把時間分為任意長度的terms，如圖5所示。Terms用連續(xù)的數(shù)據(jù)來標志层宫。每個term都以一個選舉開始，其中一個或多個candidate嘗試著成為leader镊折。如果一個candidate在選舉中勝出鹦筹，它會成為leader，并在這個term的后續(xù)時間中一直保持是leader奏纪。在某些情況下鉴嗤，選舉可能會導致投票結(jié)果分裂開來。這種情況下這個term會以沒有l(wèi)eader的狀態(tài)結(jié)束序调；新的term(新的選舉)會接著開始醉锅。Raft保證在一個term中只會有一個leader。

不同的服務(wù)器可能會在不同時間段看到terms的轉(zhuǎn)移发绢，某種情況下服務(wù)器可能在整個term周期內(nèi)都不會觀察到選舉硬耍。Terms在Raft中扮演著邏輯時鐘的角色，它們使得服務(wù)器可以檢測到過時的信息边酒，比如一個陳舊的leader经柴。每個服務(wù)器都存儲著一個當前term數(shù)字，這個數(shù)字會隨著時間單調(diào)增加墩朦。當前terms會在服務(wù)器之間通信時進行交換坯认；如果一個服務(wù)器的當前term比其他服務(wù)器的小，它會更新自己的當前term為大的值。如果一個candidate或者leader發(fā)現(xiàn)它的term過時了牛哺，它會立即轉(zhuǎn)移到follower狀態(tài)陋气。如果一個服務(wù)器收到了一個過期的term值，它會拒絕這個請求引润。

接下來主要介紹下raft算法的主要的三個問題：

1.leader選舉

Raft使用一種心跳機制來觸發(fā)leader選舉巩趁。服務(wù)器啟動時，以follower狀態(tài)開始淳附。只要它受到來自leader或者candidatea的有效RPC請求议慰，它會保持follower狀態(tài)。leader會持續(xù)周期的發(fā)送心跳(沒有數(shù)據(jù)的AppendEntries RPC)給所有的followers奴曙，以此維持它的權(quán)威别凹。如果一個服務(wù)器在一個選舉超時的時間內(nèi)沒有收到心跳請求，它會認為沒有可用的leader缆毁，然后一次選舉以選擇新的leader番川。

開始一次選舉的方式是：follower增加它的當前term值，并轉(zhuǎn)移到candidate狀態(tài)脊框。然后它為自己投票颁督，并發(fā)起并行的RequestVote RPC給集群中的每一個其他服務(wù)器。candidate會持續(xù)在這個狀態(tài)直到以下三種情況之一發(fā)生：(a)它贏得了選舉浇雹，(b)其他服務(wù)器贏得了選舉沉御，(c)一段時間過去了沒有勝出者。下面的段落會分別討論這幾種情況昭灵。

如果一個candidate在同一個term中收到了集群中大部分服務(wù)器的響應(yīng)吠裆，那么它就在選舉中勝出。在指定的term中烂完，每個server只能為一個candidate投票试疙，以先到先得的規(guī)則來實現(xiàn)。大部分保證了在一個term中最多一個candidate會在選舉中勝出抠蚣。一旦一個candidate贏得了選舉祝旷，它便成為leader。接下來它會發(fā)送心跳消息給所有其他服務(wù)器以建立權(quán)威并阻止新的選舉嘶窄。

在等待投票結(jié)果的時候怀跛，candidate可能會收到其他服務(wù)器的AppendEntries RPC，聲稱它自己以及成為了leader柄冲。如果這個leader的term值(在RPC中攜帶)不小于candidate的term值吻谋，那么candidate就會承認此leader是合法的并將自己返回到follower狀態(tài)。如果RPC中的term值比candidate的當前term要小现横，那么candidate會拒絕RPC并繼續(xù)保持candidate狀態(tài)漓拾。

第三個可能的結(jié)果是一個candidate既沒有在選舉中勝出也沒有失敻笞睢：如果多個followers同時成為candidate，投票可能會分裂骇两，以至于沒有任何candidate能獲得大多數(shù)的認可闽撤。當發(fā)生這種情況時，每個candidate都會投票超時脯颜，它們會增加自己的term值并發(fā)起新一輪的RequestVote RPC。如果不采取額外的措施贩据，投票可能會無限的分裂下去栋操。

Raft使用隨機的選舉超時值來保證投票分裂很少發(fā)生，并能夠快速得到解決饱亮。為了從源頭方式投票分裂的發(fā)生矾芙，選舉超時值會隨機的從一段固定范圍內(nèi)選取(比如150-300ms)。這些不同的值分散在服務(wù)器中近上，因此大多數(shù)情況下只會有一個服務(wù)器會超時剔宪；超時的服務(wù)器會在其他服務(wù)器超時之前贏得選舉并發(fā)送心跳給其他服務(wù)器。這種機制也用來處理投票分裂壹无。每個candidate在一次選舉開始的時候會選擇一個超時值葱绒，等待這個時間過去，然后開始下一次選舉斗锭；這減少了下次選舉出現(xiàn)投票分裂的可能性地淀。

2.日志復(fù)制

一旦leader被選舉出來，它開始接收客戶端請求岖是。每個客戶端請求都包含著一個可被狀態(tài)機執(zhí)行的指令帮毁。leader將指令添加到日志后面作為一個新條目，然后并行的給其他服務(wù)器發(fā)起AppendEntries RPC豺撑，讓它們復(fù)制這個條目烈疚。當此條目被正確的復(fù)制后，leader把這個條目應(yīng)用到它的狀態(tài)機上聪轿，并將結(jié)果返回給客戶端爷肝。如果follower宕機或者運行緩慢，或者出現(xiàn)消息丟失屹电，leader會無限的嘗試發(fā)送AppendEntries RPC直到所有的follower最終存儲了全部的日志條目阶剑。

日志被組織為如圖6所示的形式。每一條日志條目都保存著一個狀態(tài)機指令以及一個term值危号。term值用來檢測日志之間的不一致牧愁。每條日志條目都有一個整數(shù)索引值來識別它在日志中的位置。

leader決定何時才能安全的把一條日志條目應(yīng)用到狀態(tài)機上外莲；這樣的條目被稱作已提交猪半。Raft保證已提交的條目會持久化兔朦，并最終被所有可用的狀態(tài)機執(zhí)行。一旦leader把某個條目復(fù)制到了大多數(shù)戶服務(wù)器中(比如圖6中的條目7)磨确，這個條目就提交了沽甥。同時被提交的還有l(wèi)eader日志中之前的所有的條目，包括由之前l(fā)eader創(chuàng)建的條目乏奥。leader保持追蹤它所知道的最高已提交條目的索引摆舟，它會在后續(xù)的AppendEntries RPC(包括心跳)中帶上這個索引值，這樣其他的服務(wù)器最終也會知道這個值邓了。當follower發(fā)現(xiàn)某個條目已經(jīng)提交了恨诱，它會應(yīng)用這個條目到它自己的狀態(tài)機上(按照日志的順序)。

我們設(shè)計Raft日志機制骗炉，讓不同服務(wù)器上日志保持高度一致照宝。這套機制不僅簡化了系統(tǒng)行為，使系統(tǒng)更加可預(yù)測句葵，也是保證正確性的重要組件厕鹃。Raft維持以下屬性，它們共同構(gòu)成了日志匹配屬性(Log Matching Property):

如果不同日志中的兩個條目有相同的索引值和term值乍丈，那么他們保存著相同的指令

如果不同日志中的兩個條目有相同的索引值和term值剂碴，那么他們之前的日志條目全部是相同的

第一個屬性可以從如下事實中推演：在指定的term中，leader在日志的某個索引位置只會創(chuàng)建最多一條日志诗赌，而且日志條目絕不會改變它們在日志中的位置汗茄。第二個屬性由AppendEntries RPC所執(zhí)行的一致性檢查來保證。當發(fā)送AppendEntries RPC時铭若，leader會帶上當前最新添加條目之前的那一條日志條目的term值和index值洪碳。如果follower在它的日志的相同位置沒有找到相同的條目，它就會拒絕新的條目叼屠。這個一致性檢查以歸納法的形式運作：最初的空日志符合Log Matching Property瞳腌，而一致性檢查則保證后續(xù)的日志仍然滿足Log Matching Property。作為結(jié)果镜雨，任何時候只要AppendEntries返回成功嫂侍，leader就能知道，這個follower的日志在和自己的日志荚坞，直到最新添加的條目這里挑宠，全部是相同的。

在常見操作中颓影，leader和followers的日志保持一致各淀，因此AppendEntries一致性檢查不會失敗。然而诡挂，leader宕機會導致日志不一致(老的leader可能沒有把它的日志全部復(fù)制完成)碎浇。這種不一致可能會在一系列l(wèi)eader和followers的宕機過程中疊加临谱。圖7展示了followers日志和新leader不一致的幾種可能。follower可能缺少leader的部分日志奴璃，也可能有一些leader上面沒有的日志悉默，或者同時發(fā)生這兩種情況。確實和多余的日志條目可能跨域多個term苟穆。

在Raft中抄课，leader通過強制follower復(fù)制自己的日志來達到一致。這就是說follower中的沖突日志條目會被leader的日志內(nèi)容覆蓋雳旅。加上適當?shù)募s束剖膳，這樣做是安全的。

為了讓follower的日志和自己的一致岭辣，leader必須找到兩個日志中相同的最近的那條日志條目，從這個點開始甸饱，刪除follower日志后面的內(nèi)容沦童，并把leader自這里開始的日志都發(fā)送給follower。這些動作都在AppendEntries RPC的一致性檢查中進行叹话。leader對每個follower維護著一個nextIndex值偷遗，這個值標志著下一條發(fā)送給follower的日志索引。當leader開始工作時驼壶，它會把所有的nextIndex初始化為它日志的最后一條后面的位置(圖7中的11)氏豌。如果某個follower的日志和leader不一致，那么后續(xù)的AppendEntries RPC的一致性檢查就會失敗热凹。在RPC被拒絕之后泵喘，leader減小nextIndex的值，然后再次嘗試發(fā)送AppendEntries RPC般妙。最終會得到一個leader和follower的日志內(nèi)容匹配的nextIndex纪铺。當找到這個點后，AppendEntries會成功碟渺，它會刪除follower中所有沖突的日志鲜锚，然后添加上leader的日志內(nèi)容。一旦AppendEntries成功苫拍，follower的日志就和leader一致了芜繁，并且會在當前term中保持一致。

如果需要的話绒极，可以優(yōu)化協(xié)議以減少AppendEntries RPC被拒絕的次數(shù)骏令。比如，在拒絕AppendEntries時集峦， follower可以在回復(fù)中帶上沖突的條目以及它所保存的當前term的第一個條目的索引伏社。有了這些信息抠刺，leader可以確定一個能夠繞過沖突條目的nextIndex；解決沖突條目只需要一次AppendEntries RPC摘昌，而不是每個條目一個RPC速妖。在實際中，我們懷疑這個優(yōu)化的必要性聪黎，因為故障不會頻繁的發(fā)生罕容，不太可能出現(xiàn)很多不一致的條目。

使用這種機制稿饰，leader在上任后不需要采取額外的措施來恢復(fù)一致性锦秒。它僅僅開始常規(guī)操作，日志就會在AppendEntries一致性檢查中自動的匯合喉镰。leader絕不會覆蓋或者刪除自己的日志(leaderAppend-Only屬性)旅择。

日志復(fù)制機制展示了第2章中描述的一致性屬性：在大多數(shù)服務(wù)器正常的情況下，Raft可以接收侣姆，復(fù)制生真，應(yīng)用新的日志條目；在普通情形下捺宗，復(fù)制一條新條目只需要一輪RPC柱蟀；單個慢服務(wù)器不會影響性能。

3? 正確性

前面的章節(jié)描述了Raft是如何選舉leader和復(fù)制日志的蚜厉。然而到目前為止长已，上述的機制并不能保證每個狀態(tài)機都按照相同的順序執(zhí)行完全一樣的指令。比如說昼牛，某個follower可能在leader復(fù)制日志的時候不可用术瓮，然后又被選舉為leader并用新的日志條目覆蓋了之前l(fā)eader復(fù)制的那些條目；這種情況下贰健，不同狀態(tài)機就可能會執(zhí)行不同的指令斤斧。

這一小節(jié)描述了哪些服務(wù)器能被選舉為leader的限制，從而完善了Raft算法霎烙。這個限制保證了任意term中的leader都包含了在之前term中提交的所有日志條目(Leader完整屬性)撬讽。通過這個限制，我們把提交規(guī)則變得更精確悬垃。最后游昼，我們給出對Leader完整屬性的一個概要證明，并展示了它是如何使復(fù)制狀態(tài)機都正確工作尝蠕。

1） 選舉限制

在任何基于leader的一致性算法中烘豌，leader最終都必須存儲著所有提交的日志條目。在一些算法中看彼，如Viewstamped Replication[^]廊佩，一個leader即使在開始沒有包含所有提交的條目也能夠被選為leader囚聚。這些算法包括了額外的機制，用來發(fā)現(xiàn)丟失的條目并將它們傳輸?shù)叫耹eader上标锄，要么在選舉過程中顽铸，要么在選舉后進行。不幸的是料皇，這導致了大量的額外機制和復(fù)雜性谓松。Raft使用了一個簡單的方案，它保證在選舉開始時践剂，所有在之前term中提交的條目都在新leader上鬼譬，不需要傳輸這些條目到leader。這意味著日志條目只會在一個方向上流動逊脯，從leader到followers优质，而且leader絕不會覆蓋他自己日志中已有的條目。

Raft在投票過程中會防止某個candidate贏得選舉军洼，除非它的日志包括了所有提交的條目盆赤。為了贏得選舉，candidate必須和集群中的大多數(shù)服務(wù)器進行通信歉眷，這意味著每一條提交的條目至少存在這些服務(wù)器中的一臺上。如果candidate的日志至少和大多數(shù)服務(wù)器中的日志都是一樣新(up-to-date颤枪，后面會精確定義)的汗捡，那么它就包括了所有提交的條目。RequestVote RPC實現(xiàn)了這個限制：RPC中包含了candidate的日志信息畏纲，如果投票者發(fā)現(xiàn)它自己的日志比candidate的更新扇住，它會拒絕此次投票。

Raft通過比較日志中最后一個條目的index和term來決定哪個日志更新一些盗胀。如果兩個日志最后一個條目的term不同艘蹋，那么term大的更新。如果兩個日志最后條目的term相同票灰，那么更長的那個日志更新女阀。

2） 提交之前term的條目

當一個當前term的條目被存儲在集群中大多數(shù)服務(wù)器上時，leader則認為此條目是已提交了屑迂。如果leader在提交某個條目之前崩潰了浸策，新的leader會嘗試完成這個條目的復(fù)制。然而惹盼，leader不能立即斷定一個之前term的條目已經(jīng)提交庸汗，即使這個條目存儲在大多數(shù)服務(wù)器上。圖8展示了一個情形手报，其中一個舊的條目存儲在大多數(shù)服務(wù)器上蚯舱，但仍然可能會被新的leader覆蓋改化。

為了消除圖8中的問題，Raft絕不會通過計數(shù)副本的數(shù)目來提交之前term的日志條目枉昏。只有當前term的條目會通過計數(shù)來提交陈肛；一旦當前term的某個條目通過這種方式提交了，那么之前的所有條目也都提交了凶掰，基于Log匹配屬性燥爷。某些情況下，leader可以安全的斷定一個舊的條目以及被提交(比如懦窘，每個server上都保存著這個條目)前翎，但是處于簡化的考慮，Raft仍然采用一個保守的方式來處理畅涂。

Raft在提交規(guī)則中引入了這樣額外的復(fù)雜性港华，從而使得在leader復(fù)制之前的條目時，這些日志條目仍然可以保留他們原始的term值午衰。在其他一致性算法中立宜，當一個新leader復(fù)制之前term的條目時，它必須使用一個新的term值臊岸。Raft的方案使得理解日志條目更加簡單橙数，因為它們總是保持著最初的term值，不管是在不同時間還是不同的日志中帅戒。除此之外灯帮，相比于其他算法，在Raft中新leader會發(fā)送更少的舊條目(其他算法中必須發(fā)送冗余的日志條目逻住，并在提交之前進行重新編號)钟哥。

3）正確性討論

給出了完整Raft算法后，我們可以更加精細的證明Leader完整屬性是成立的(證明基于正確性證據(jù)瞎访，查看9.2節(jié))腻贰。我們假設(shè)Leader完整性不成立，然后得出一個沖突扒秸。假設(shè)term T的leaderT提交了一個日志條目播演，但是這個條目不在未來的某個leader中。設(shè)定最小的不包含這個條目的leader的term是U伴奥，即leaderU中沒有這個條目宾巍。

在選舉的時候，leaderU的日志中就沒有這個條目(leader不會刪除或者覆蓋日志條目)渔伯。

leaderT將這個條目復(fù)制到大多數(shù)服務(wù)器上顶霞，leaderU收到大多數(shù)服務(wù)器的投票。因此，至少有一個服務(wù)器(投票者)即接收了leaderT的日志條目选浑，又給leaderU投票了蓝厌。如圖9所示，這個投票者是證明沖突的關(guān)鍵所在古徒。

投票者必須是在給leaderU投票之前接受了leaderT的日志條目拓提；否則它會拒絕leaderT的AppendEntries請求(它的當前term比T要大)。

當投票者給leaderU投票時隧膘，它仍然存儲著這個條目代态，這是因為中間所有的leader都存儲著這個條目(基于假設(shè))，而leader不會刪除條目疹吃，同時follower只會刪除它們和leader沖突的條目蹦疑。

投票者給leaderU投票了，這樣的話leaderU的日志必須是和投票者一樣新的萨驶。這導致了兩個沖突歉摧。

第一，如果投票者和leaderU的日志term是相同的腔呜，那么leaderU的日志至少是和投票者的日志一樣長的叁温，因此它會包含投票者日志中的所有條目。這是一個沖突核畴，投票者包括這個條目膝但，而leaderU中沒有(基于假設(shè))。

如果他們的term不同谤草，那么leaderU的最后一個日志條目的term必須是比投票者的term大跟束。進一步的，它的term是比T大的咖刃，因為投票者的最后一個日志條目的term至少是T(已提交的這個條目是term T的)。創(chuàng)建leaderU的最后一個日志條目的之前l(fā)eader是包含了這個提交的條目的(基于假設(shè))憾筏。根據(jù)Log匹配屬性嚎杨，leaderU的日志中必須包含所有的提交條目，這是一個沖突氧腰。

這樣就完整了整個沖突證明枫浙。因此，所有term比T大的leader的日志中古拴，必須包含了term T中提交的所有日志條目箩帚。

日志匹配屬性保證了后續(xù)的leader也會包括被間接提交的日志條目，如同圖8(d)中的第2條黄痪。

給出了Leader完整屬性紧帕，我們可以證明圖3中的狀態(tài)機正確性，即如果一個服務(wù)器應(yīng)用了某個index的指令到它的狀態(tài)機，那么在這個index位置是嗜，不會有其他服務(wù)器應(yīng)用不同的指令愈案。當一個服務(wù)器應(yīng)用某個日志條目到狀態(tài)機時，它的日志和leader的日志直到這個條目為止應(yīng)該都是相同的鹅搪，并且這個條目肯定是已提交的≌拘鳎現(xiàn)在考慮一下任意服務(wù)器應(yīng)用的某個index的日志條目中最低的term。leader完整屬性保證所有更高term的leader會存儲相同的條目丽柿，因此應(yīng)用這個條目的所有服務(wù)器都會應(yīng)用相同的條目恢准。因此，狀態(tài)機正確性成立甫题。

最后馁筐，Raft要求服務(wù)器按照日志順序來應(yīng)用條目。和狀態(tài)機正確性結(jié)合起來幔睬，這意味著所有服務(wù)器都會應(yīng)用完全相同的日志條目到它們的狀態(tài)機眯漩，按照相同的順序。

原文地址：http://www.reibang.com/p/0b2ef4f37ae3