很久之前研究過raft協(xié)議烟零，最近項目中一直沒有使用幕袱，有些生疏了暴备，這次重溫了一下raft，花了兩天的時間们豌，就順便做下筆記涯捻。

一致性問題

在分布式系統(tǒng)中,一致性問題(consensus problem)是指對于一組服務器，給定一組操作望迎，我們需要一個協(xié)議使得最后它們的結果達成一致障癌。

由于CAP理論告訴我們對于分布式系統(tǒng)，如果不想犧牲一致性辩尊，我們就只能放棄可用性涛浙，所以，數(shù)據(jù)一致性模型主要有以下幾種：強一致性摄欲、弱一致性和最終一致性等轿亮，在本篇章中，我們主要討論的算法Raft胸墙，是一種分布式系統(tǒng)中的強一致性的實現(xiàn)算法我注。

強一致性的一般實現(xiàn)的原理：當其中某個服務器收到客戶端的一組指令時,它必須與其它服務器交流以保證所有的服務器都是以同樣的順序收到同樣的指令,這樣的話所有的服務器會產(chǎn)生一致的結果,看起來就像是一臺機器一樣.

Raft算法描述

在Raft被提出來之前，Paxos協(xié)議是第一個被證明的一致性算法劳秋，但是Paxos的論文非常難懂仓手，導致基于Paxos的工程實踐和教學都十分頭疼胖齐，于是Raft在設計的過程中，就從可理解性出發(fā)嗽冒，使用算法分解和減少狀態(tài)等手段呀伙，目前已經(jīng)應用非常廣泛。

在Raft中添坊，問題分解為：領導選取剿另、日志復制、安全和成員變化贬蛙。

基本概念

復制狀態(tài)機（Replicated State Machine）

1.png

• 復制狀態(tài)機通過復制日志來實現(xiàn)：

  • 日志：每臺機器保存一份日志雨女，日志來自于客戶端的請求，包含一系列的命令
  • 狀態(tài)機：狀態(tài)機會按順序執(zhí)行這些命令
  • 一致性模型：分布式環(huán)境下阳准，保證多機的日志是一致的氛堕，這樣回放到狀態(tài)機中的狀態(tài)是一致的

• 一致性算法作用于一致性模型，一般有以下特性：

  • safety：在非拜占庭問題下（網(wǎng)絡延時野蝇，網(wǎng)絡分區(qū)讼稚，丟包，重復發(fā)包以及包亂序等）绕沈，結果是正確的
  • availability：在半數(shù)以上機器能正常工作時锐想，則系統(tǒng)可用
  • timing-unindependent：不依賴于時鐘來保證日志一致性，錯誤的時鐘以及極端的消息時延最多會造成可用性問題

注意：
真實的實現(xiàn)中乍狐，建議狀態(tài)機的每個命令操作都采用冪等的赠摇，這樣一致性的保證會更容易。

服務器狀態(tài)

每臺服務器一定會處于三種狀態(tài)：

1. 領導者
2. 候選人
3. 追隨者

2.png

追隨者只響應其他服務器的請求浅蚪。如果追隨者沒有收到任何消息藕帜，它會成為一個候選人并且開始一次選舉。收到大多數(shù)服務器投票的候選人會成為新的領導人掘鄙。領導人在它們宕機之前會一直保持領導人的狀態(tài)耘戚。

任期(Term)

Raft 算法將時間劃分成為任意不同長度的任期（term）嗡髓。任期用連續(xù)的數(shù)字進行表示操漠。每一個任期的開始都是一次選舉（election），一個或多個候選人會試圖成為領導人饿这。如果一個候選人贏得了選舉浊伙，它就會在該任期的剩余時間擔任領導人。在某些情況下长捧，選票會被瓜分嚣鄙，有可能沒有選出領導人，那么串结，將會開始另一個任期哑子，并且立刻開始下一次選舉舅列。Raft 算法保證在給定的一個任期最多只有一個領導人。

3.png

RPC

Raft 算法中服務器節(jié)點之間通信使用遠程過程調(diào)用（RPCs）卧蜓，并且基本的一致性算法只需要兩種類型的 RPCs帐要。請求投票（RequestVote） RPCs 由候選人在選舉期間發(fā)起，然后附加條目（AppendEntries）RPCs 由領導人發(fā)起弥奸，用來復制日志和提供一種心跳機制榨惠。為了在服務器之間傳輸快照增加了第三種 RPC。當服務器沒有及時的收到 RPC 的響應時盛霎，會進行重試赠橙， 并且他們能夠并行的發(fā)起 RPCs 來獲得最佳的性能。
RPC有三種：

1. RequestVote RPC：候選人在選舉期間發(fā)起
2. AppendEntries RPC：領導人發(fā)起的一種心跳機制愤炸，復制日志也在該命令中完成
3. InstallSnapshot RPC: 領導者使用該RPC來發(fā)送快照給太落后的追隨者期揪。

超時設置：

1. BroadcastTime : 領導者的心跳超時時間
2. Election Timeout: 追隨者設置的候選超時時間
3. MTBT :指的是單個服務器發(fā)生故障的間隔時間的平均數(shù)

BroadcastTime << ElectionTimeout << MTBF
兩個原則：

1. BroadcastTime應該比ElectionTimeout小一個數(shù)量級，為的是使領導人能夠持續(xù)發(fā)送心跳信息（heartbeat）來阻止追隨者們開始選舉规个；
2. ElectionTimeout也要比MTBF小幾個數(shù)量級横侦，為的是使得系統(tǒng)穩(wěn)定運行。

一般BroadcastTime大約為0.5毫秒到20毫秒绰姻，ElectionTimeout一般在10ms到500ms之間枉侧。大多數(shù)服務器的MTBF都在幾個月甚至更長。

領導人選取

• 觸發(fā)條件：

  1. 一般情況下狂芋，追隨者接到領導者的心跳時榨馁，把ElectionTimeout清零，不會觸發(fā)帜矾；
  2. 領導者故障翼虫，追隨者的ElectionTimeout超時發(fā)生時，會變成候選者屡萤，觸發(fā)領導人選日浣！；

• 候選操作過程：

追隨者自增當前任期死陆，轉換為Candidate招拙，對自己投票，并發(fā)起RequestVote RPC措译，等待下面三種情形發(fā)生别凤；

1. 獲得超過半數(shù)服務器的投票，贏得選舉领虹，成為領導者规哪；
2. 另一臺服務器贏得選舉，并接收到對應的心跳塌衰，成為追隨者诉稍；
3. 選舉超時蝠嘉，沒有任何一臺服務器贏得選舉，自增當前任期杯巨，重新發(fā)起選舉是晨；

• 注意事項：

  1. 服務器在一個任期內(nèi)，最多能給一個候選人投票舔箭，采用先到先服務原則罩缴；
  2. 候選者等待投票時，可能會接收到來自其它聲明為領導人的的AppendEntries RPC层扶。如果該領導人的任期（RPC中有）比當前候選人的當前任期要大箫章，則候選人認為該領導人合法，并轉換成追隨者镜会；如果RPC中的任期小于候選人的當前任期檬寂，則候選人拒絕此次RPC，繼續(xù)保持候選人狀態(tài)戳表；
  3. 候選人既沒有贏得選舉也沒有輸?shù)暨x舉：如果許多追隨者在同一時刻都成為了候選人桶至，選票會被分散，可能沒有候選人能獲得大多數(shù)的選票匾旭。當這種情形發(fā)生時镣屹，每一個候選人都會超時，并且通過自增任期號和發(fā)起另一輪 RequestVote RPC 來開始新的選舉价涝。然而女蜈，如果沒有其它手段來分配選票的話，這種情形可能會無限的重復下去色瘩。所以Raft使用的隨機的選舉超時時間（150~300ms之間）伪窖，來避免這種情況發(fā)生。

• 問題探討：為什么這里沒有談收到其他候選者的RequestVote RPC請求居兆？
  可能的解釋：

  1. 候選者已經(jīng)給自己投票了覆山，一個候選者在一個任期只會給一個人投票，不會給其他人再投票了泥栖；
  2. 也有可能算法本身設定候選者就拒絕所有的其他服務器的請求簇宽。

日志復制

4.png

接受命令的過程：

1. 領導者接受客戶端請求；
2. 領導者把指令追加到日志聊倔；
3. 發(fā)送AppendEntries RPC到追隨者晦毙；
4. 領導者收到大多數(shù)追隨者的確認后，領導者Commit該日志耙蔑，把日志在狀態(tài)機中回放，并返回結果給客戶端孤荣；

提交過程：

1. 在下一個心跳階段甸陌，領導者再次發(fā)送AppendEntries RPC給追隨者须揣，日志已經(jīng)commited；
2. 追隨者收到Commited日志后钱豁，將日志在狀態(tài)機中回放耻卡。

安全性

到目前為止描述的機制并不能充分的保證每一個狀態(tài)機會按照相同的順序執(zhí)行相同的指令，例如：一個跟隨者可能會進入不可用狀態(tài)同時領導人已經(jīng)提交了若干的日志條目牲尺，然后這個跟隨者可能會被選舉為領導人并且覆蓋這些日志條目卵酪；因此，不同的狀態(tài)機可能會執(zhí)行不同的指令序列谤碳。

1. 領導者追加日志（Append-Only)

領導者永遠不會覆蓋已經(jīng)存在的日志條目溃卡；
日志永遠只有一個流向：從領導者到追隨者；

2. 選舉限制：投票阻止沒有全部日志條目的服務器贏得選舉

如果投票者的日志比候選人的新蜒简，拒絕投票請求瘸羡；
這意味著要贏得選舉，候選者的日志至少和大多數(shù)服務器的日志一樣新搓茬，那么它一定包含全部的已經(jīng)提交的日志條目犹赖。

3. 永遠不提交任期之前的日志條目（只提交任期內(nèi)的日志條目）

在Raft算法中，當一個日志被安全的復制到絕大多數(shù)的機器上面卷仑，即AppendEntries RPC在絕大多數(shù)服務器正確返回了峻村，那么這個日志就是被提交了，然后領導者會更新commit index锡凝。

5.png

如果允許提交任期之前的日志條目雀哨，那么在步驟c中，我們就會把之前任期為2的日志提交到其他服務器中去私爷，并造成了大多數(shù)機器存在了日志為2的情況雾棺。所以造成了d中S5中任期為3的日志條目會覆蓋掉已經(jīng)提交的日志的情況。

Raft 從來不會通過計算復制的數(shù)目來提交之前人氣的日志條目衬浑。只有領導人當前任期的日志條目才能通過計算數(shù)目來進行提交捌浩。一旦當前任期的日志條目以這種方式被提交，那么由于日志匹配原則（Log Matching Property）工秩，之前的日志條目也都會被間接的提交尸饺。

論文中的這段話比較難理解，更加直觀的說：由于Raft不會提交任期之前的日志條目助币，那么就不會從b過渡到c的情況浪听，只能從b發(fā)生S5down機的情況下直接過渡到e，這樣就產(chǎn)生的更新的任期眉菱，這樣S5就沒有機會被選為領導者了迹栓。

4. 候選者和追隨者崩潰

候選者和追隨者崩潰的情況處理要簡單的多。如果這類角色崩潰了俭缓，那么后續(xù)發(fā)送給他們的 RequestVote和AppendEntries的所有RCP都會失敗克伊，Raft算法中處理這類失敗就是簡單的無限重試的方式酥郭。
　　如果這些服務器重新可用，那么這些RPC就會成功返回愿吹。如果一個服務器完成了一個RPC不从，但是在響應Leader前崩潰了，那么當他再次可用的時候還會收到相同的RPC請求犁跪，此時接收服務器負責檢查椿息，比如如果收到了已經(jīng)包含該條日志的RPC請求，可以直接忽略這個請求坷衍，確保對系統(tǒng)是無害的寝优。

集群成員變更

集群成員的變更和成員的宕機與重啟不同，因為前者會修改成員個數(shù)進而影響到領導者的選取和決議過程惫叛，因為在分布式系統(tǒng)這對于majority這個集群中成員大多數(shù)的概念是極為重要的倡勇。

簡單的做法是，運維人員將系統(tǒng)臨時下線嘉涌，修改配置妻熊，重新上線。但是這種做法存在兩個缺點：

1. 更改時集群不可用
2. 人為操作失誤風險

直接從一種配置轉到新的配置是十分不安全的

如下圖所示：

6.png

因為各個機器可能在任何的時候進行轉換仑最。在這個例子中扔役，集群配額從 3 臺機器變成了 5 臺。不幸的是警医，存在這樣的一個時間點亿胸，兩個不同的領導人在同一個任期里都可以被選舉成功。一個是通過舊的配置预皇，一個通過新的配置侈玄。

兩階段方法保證安全性：

為了保證安全性，配置更改必須使用兩階段方法吟温。在 Raft 中序仙，集群先切換到一個過渡的配置，我們稱之為共同一致鲁豪；一旦共同一致已經(jīng)被提交了潘悼，那么系統(tǒng)就切換到新的配置上。共同一致是老配置和新配置的結合爬橡。

共同一致允許獨立的服務器在不影響安全性的前提下治唤，在不同的時間進行配置轉換過程。此外糙申，共同一致可以讓集群在配置轉換的過程人依然響應服務器請求宾添。

一個領導人接收到一個改變配置從 C-old 到 C-new 的請求，他會為了共同一致存儲配置（圖中的 C-old,new），以前面描述的日志條目和副本的形式辞槐。一旦一個服務器將新的配置日志條目增加到它的日志中掷漱，他就會用這個配置來做出未來所有的決定粘室。領導人完全特性保證了只有擁有 C-old,new 日志條目的服務器才有可能被選舉為領導人榄檬。當C-old,new日志條目被提交以后，領導人在使用相同的策略提交C-new衔统，如下圖所示鹿榜，C-old 和 C-new 沒有任何機會同時做出單方面的決定，這就保證了安全性锦爵。

7.png

一個配置切換的時間線舱殿。虛線表示已經(jīng)被創(chuàng)建但是還沒有被提交的條目，實線表示最后被提交的日志條目险掀。領導人首先創(chuàng)建了 C-old,new 的配置條目在自己的日志中沪袭，并提交到 C-old,new 中（C-old,new 的大多數(shù)和 C-new 的大多數(shù)）。然后他創(chuàng)建 C-new 條目并提交到 C-new 中的大多數(shù)樟氢。這樣就不存在 C-new 和 C-old 可以同時做出決定的時間點冈绊。

日志壓縮

日志會隨著系統(tǒng)的不斷運行會無限制的增長，這會給存儲帶來壓力埠啃，幾乎所有的分布式系統(tǒng)(Chubby死宣、ZooKeeper)都采用快照的方式進行日志壓縮，做完快照之后快照會在穩(wěn)定持久存儲中保存碴开，而快照之前的日志和快照就可以丟棄掉毅该。

Raft的具體做法如下圖所示：

8.png

與Raft其它操作Leader-Based不同，snapshot是由各個節(jié)點獨立生成的潦牛。除了日志壓縮這一個作用之外眶掌，snapshot還可以用于同步狀態(tài)：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成該過程巴碗，不再贅述朴爬。

Client交互

1. Client只向領導者發(fā)送請求；
2. Client開始會向追隨者發(fā)送請求良价，追隨者拒絕Client的請求寝殴，并重定向到領導者；
3. Client請求失敗明垢，會超時重新發(fā)送請求蚣常；

Raft算法要求Client的請求線性化，防止請求被多次執(zhí)行痊银。有兩個解決方案：

1. Raft算法提出要求每個請求有個唯一標識抵蚊；
2. Raft的請求保持冪等性；