Raft概述

Raft 是工程上使用較為廣泛的 強(qiáng)一致性、去中心化娩脾、高可用 的分布式協(xié)議赵誓，用于管理副本復(fù)制（Log Replication）。相比傳統(tǒng)的 Paxos 算法柿赊，Raft 將大量的計(jì)算問題分解成為了一些簡(jiǎn)單的相對(duì)獨(dú)立的子問題俩功，并有著和 Multi-Paxos 同樣的性能。

Raft的首要目標(biāo)就是容易理解(Understandable)碰声。

Raft相對(duì)來說易于實(shí)現(xiàn)主要?dú)w結(jié)為以下幾個(gè)原因：

• 問題分解（模塊化）：把一致性協(xié)議劃分為 Leader 選舉诡蜓、MemberShip 變更、日志復(fù)制胰挑、SnapShot 等相對(duì)比較解耦的模塊蔓罚；
• 設(shè)計(jì)簡(jiǎn)化（狀態(tài)簡(jiǎn)化）：比如不允許類似 Paxos 算法的亂序提交、使用 Randomization 算法設(shè)計(jì) Leader Election 算法以簡(jiǎn)化系統(tǒng)的狀態(tài)洽腺，只有 Leader脚粟、Follower、Candidate 等等蘸朋。

Raft相比Paxos有很多相似之處核无，但是有這么幾個(gè)新特性：

• Strong leader：使用strong leader可以簡(jiǎn)化管理。例如log entries只從leader流向其他server.
• Leader election：使用randomized timer來簡(jiǎn)化選舉過程藕坯。相比其他共識(shí)算法增加了heartbeat機(jī)制
• Membership changes：Raft變更服務(wù)器集群的使用了一種新的方法团南，保證了服務(wù)器的配置變更也能繼續(xù)運(yùn)行。

概念

角色

Raft中節(jié)點(diǎn)存在三種狀態(tài)炼彪，節(jié)點(diǎn)會(huì)根據(jù)集群的狀態(tài)轉(zhuǎn)變自己的狀態(tài)：

• Leader：Leader 會(huì)一直工作吐根，直到失敗。Leader 節(jié)點(diǎn)負(fù)責(zé)處理所有客戶端的請(qǐng)求辐马，定期向集群中的 Follower 節(jié)點(diǎn)發(fā)送心跳消息拷橘，證明自己還健在。
• Follower：Follower 只響應(yīng)來自其他服務(wù)器的請(qǐng)求。Follower 節(jié)點(diǎn)不處理 Client 的請(qǐng)求冗疮，而是將請(qǐng)求重定向給集群的 Leader 節(jié)點(diǎn)萄唇，由 Leader 節(jié)點(diǎn)進(jìn)行請(qǐng)求處理。
• Candidate：如果 Follower 長(zhǎng)時(shí)間沒有收到任何通信术幔，它將成為 Candidate 并發(fā)起選舉另萤。獲得多數(shù)選票的 Candidate 成為新的 Leader。

選舉

• Leader Election（領(lǐng)導(dǎo)人選舉）：簡(jiǎn)稱選舉诅挑，就是從候選人中選出領(lǐng)袖四敞；
• Term（任期）：它其實(shí)是個(gè)單獨(dú)遞增的連續(xù)數(shù)字，每一次任期就會(huì)重新發(fā)起一次領(lǐng)導(dǎo)人選舉拔妥；
• Election Timeout（選舉超時(shí)）：就是一個(gè)超時(shí)時(shí)間忿危，當(dāng)群眾超時(shí)未收到領(lǐng)袖的心跳時(shí)，會(huì)重新進(jìn)行選舉毒嫡。

角色變化

相比Paxos復(fù)雜的角色劃分癌蚁，Raft算法只有三種角色分類：Follower、Candidate和Leader兜畸。所有的Server都會(huì)在這三種角色中相互轉(zhuǎn)換努释，轉(zhuǎn)換流程如下：

Raft-Node

• 群眾->候選人：定時(shí)器先過期咬摇，選舉開始
• 候選人->領(lǐng)導(dǎo)者：獲得大多數(shù)投票
• 候選人->群眾：發(fā)現(xiàn)已經(jīng)有領(lǐng)導(dǎo)者或者更新的任期
• 候選人->候選人：定時(shí)器超時(shí)或者進(jìn)入一輪新的任期
• 領(lǐng)導(dǎo)者->群眾：發(fā)現(xiàn)有節(jié)點(diǎn)有更高的任期

系統(tǒng)中最多只有一個(gè)Leader伐蒂，如果在一段時(shí)間里發(fā)現(xiàn)沒有Leader，則大家通過選舉-投票選出Leader肛鹏。Leader會(huì)不停的給follower發(fā)心跳消息逸邦，表明自己的存活狀態(tài)。如果Leader故障在扰，那么follower會(huì)轉(zhuǎn)換成candidate缕减，重新選出Leader。

1. 所有節(jié)點(diǎn)啟動(dòng)時(shí)都是follower狀態(tài)芒珠；
2. 在一段時(shí)間內(nèi)如果沒有收到來自leader的心跳桥狡，從follower切換到candidate，發(fā)起選舉;
3. 如果收到過半票（含自己的一票）則切換到leader狀態(tài)皱卓；如果發(fā)現(xiàn)其他節(jié)點(diǎn)日志比自己更新裹芝，則主動(dòng)切換到follower。

工作流程

數(shù)據(jù)的流向只能從 Leader 節(jié)點(diǎn)向 Follower 節(jié)點(diǎn)轉(zhuǎn)移娜汁。當(dāng) Client 向集群 Leader 節(jié)點(diǎn)提交數(shù)據(jù)后嫂易，Leader 節(jié)點(diǎn)接收到的數(shù)據(jù)處于未提交狀態(tài)（Uncommitted），接著 Leader 節(jié)點(diǎn)會(huì)并發(fā)向所有 Follower 節(jié)點(diǎn)復(fù)制數(shù)據(jù)并等待接收響應(yīng)掐禁，確保至少集群中超過半數(shù)節(jié)點(diǎn)已接收到數(shù)據(jù)后再向 Client 確認(rèn)數(shù)據(jù)已接收怜械。一旦向 Client 發(fā)出數(shù)據(jù)接收 Ack 響應(yīng)后颅和，表明此時(shí)數(shù)據(jù)狀態(tài)進(jìn)入已提交（Committed），Leader 節(jié)點(diǎn)再向 Follower 節(jié)點(diǎn)發(fā)通知告知該數(shù)據(jù)狀態(tài)變成了已提交缕允。

從這里看出這個(gè)Leader 的作用是相當(dāng)大的融虽，事實(shí)也確實(shí)如此。Raft 協(xié)議強(qiáng)依賴 Leader 節(jié)點(diǎn)的可用性來確保集群數(shù)據(jù)的一致性灼芭。

在這個(gè)過程中，主節(jié)點(diǎn)可能在任意階段掛掉般又， Raft 協(xié)議針對(duì)不同階段也有保障數(shù)據(jù)一致性的解決方案彼绷。

1 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，但未復(fù)制到 Follower 節(jié)點(diǎn)

這個(gè)階段 Leader 掛掉茴迁，數(shù)據(jù)屬于未提交狀態(tài)寄悯，Client 不會(huì)收到 Ack 會(huì)認(rèn)為超時(shí)失敗可安全發(fā)起重試。Follower 節(jié)點(diǎn)上沒有該數(shù)據(jù)堕义，重新選出新的主謀后可再次接收客戶端的請(qǐng)求猜旬。原來的 Leader 節(jié)點(diǎn)恢復(fù)后作為 Follower 加入集群重新從當(dāng)前任期的新 Leader 處同步數(shù)據(jù)，強(qiáng)制保持和 Leader 數(shù)據(jù)一致倦卖。

2 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)洒擦，部分follower拿到復(fù)制的數(shù)據(jù)，但還未向 Leader 響應(yīng)接收

這個(gè)階段 Leader 掛掉怕膛，數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于未提交狀態(tài)（Uncommitted）且不一致熟嫩，Raft 協(xié)議要求投票只能投給擁有最新數(shù)據(jù)的節(jié)點(diǎn)。所以擁有最新數(shù)據(jù)的節(jié)點(diǎn)會(huì)被選為 Leader 再?gòu)?qiáng)制同步數(shù)據(jù)到 Follower褐捻，數(shù)據(jù)不會(huì)丟失并最終一致掸茅。

3 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，所有follower拿到復(fù)制的數(shù)據(jù)柠逞，但還未向 Leader 響應(yīng)接收

這個(gè)階段 Leader 掛掉昧狮，雖然數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于未提交狀態(tài)（Uncommitted）但保持一致，重新選出 Leader 后可完成數(shù)據(jù)提交板壮，此時(shí) Client 由于不知到底提交成功沒有逗鸣，可重試提交。針對(duì)這種情況 Raft 要求 RPC 請(qǐng)求實(shí)現(xiàn)冪等性个束，也就是要實(shí)現(xiàn)內(nèi)部去重機(jī)制慕购。

4 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 所有或多數(shù)節(jié)點(diǎn)茬底，數(shù)據(jù)在 Leader 處于已提交狀態(tài)沪悲，但在 Follower 處于未提交狀態(tài)

這個(gè)階段 Leader 掛掉，重新選出新 Leader 后的處理流程和階段 3 一樣阱表。

5 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)殿如，成功復(fù)制到 Follower 所有或多數(shù)節(jié)點(diǎn)贡珊，數(shù)據(jù)在所有節(jié)點(diǎn)都處于已提交狀態(tài)，但還未響應(yīng) Client

這個(gè)階段 Leader 掛掉涉馁，Cluster 內(nèi)部數(shù)據(jù)其實(shí)已經(jīng)是一致的门岔，Client 重復(fù)重試基于冪等策略對(duì)一致性無影響。

Raft協(xié)議關(guān)鍵點(diǎn)

選舉啟動(dòng)條件

Follower在Election timeout內(nèi)沒有收到來自leader的心跳烤送，（也許此時(shí)還沒有選出leader寒随，大家都在等；也許Leader炸了帮坚；也許只是leader與該follower之間網(wǎng)線被老鼠咬斷了）妻往，則會(huì)主動(dòng)發(fā)起選舉。

步驟

1. 增加節(jié)點(diǎn)本地的 current term 试和，切換到candidate狀態(tài)
2. 投自己一票
3. 并行給其他節(jié)點(diǎn)發(fā)送 RequestVote RPCs
4. 等待其他節(jié)點(diǎn)的回復(fù)

出現(xiàn)結(jié)果

1. 收到majority的投票（含自己的一票）讯泣，則贏得選舉，成為leader
2. 被告知?jiǎng)e人已當(dāng)選阅悍，那么自行切換到follower
3. 一段時(shí)間內(nèi)沒有收到majority投票好渠，則保持candidate狀態(tài)，重新發(fā)出選舉

投票限制

1. 在任一任期內(nèi)节视，單個(gè)節(jié)點(diǎn)最多只能投一票
2. 候選人知道的信息不能比自己的少

3. first-come-first-served 先來先得

   
   
   Raft-Node-ABC.png

若有三個(gè)節(jié)點(diǎn)A B C（上圖）拳锚。A B同時(shí)發(fā)起選舉，而A的選舉消息先到達(dá)C肴茄，C給A投了一票晌畅，當(dāng)B的消息到達(dá)C時(shí)，已經(jīng)不能滿足上面提到的第一個(gè)約束寡痰，即C不會(huì)給B投票抗楔，而A和B顯然都不會(huì)給對(duì)方投票。A勝出之后拦坠，會(huì)給B,C發(fā)心跳消息连躏，節(jié)點(diǎn)B發(fā)現(xiàn)節(jié)點(diǎn)A的term不低于自己的term，知道有已經(jīng)有Leader了贞滨，于是轉(zhuǎn)換成follower入热。

Raft-Node-ABCD.png

Log replication

共識(shí)算法基于Replicated state machines來實(shí)現(xiàn)，即相同的初識(shí)狀態(tài) + 相同的輸入 = 相同的結(jié)束狀態(tài)骄噪。

Leader將客戶端請(qǐng)求（command）封裝到一個(gè)個(gè)log entry糖赔，將這些log entries復(fù)制（replicate）到所有follower節(jié)點(diǎn)佛猛，然后大家按相同順序應(yīng)用（apply）log entry中的command，則最終狀態(tài)肯定是一致的允蜈。

請(qǐng)求完整流程

1. leader append log entry
2. leader issue AppendEntries RPC in parallel
3. leader wait for majority response
4. leader apply entry to state machine
5. leader reply to client
6. leader notify follower apply log

由于是遠(yuǎn)程請(qǐng)求宴咧，各個(gè)節(jié)點(diǎn)的操作都經(jīng)過RPC實(shí)現(xiàn)

Log matching

每個(gè)log entry不僅包含client的command還包含log entry的leader term，每個(gè)節(jié)點(diǎn)不要求完全一致，只求最終一致。未達(dá)到最終一致的時(shí)候掌实，leader會(huì)不斷嘗試給follower發(fā)log entry，直到完全一致邦马。

由于server的連接可能出現(xiàn)問題贱鼻，每個(gè)server的log entries都有可能不同，根據(jù)不同的情況可以進(jìn)行分類做log matching:

• 出現(xiàn)follower的log index比master少或者term比當(dāng)前term小滋将，則進(jìn)行額外的log commit
• log index大于當(dāng)前index或者term高于當(dāng)前l(fā)og entries的忱嘹，進(jìn)行l(wèi)og刪除
• log term小于或者不同于當(dāng)前的term的，進(jìn)行l(wèi)og覆蓋

Safety

Raft通過上面幾個(gè)屬性保障在各類異常情況下仍然正常工作（數(shù)據(jù)中心被炸不算）

Log Compaction

由于Log只執(zhí)行追加操作耕渴，而不進(jìn)行刪除和覆蓋，Raft需要定期執(zhí)行l(wèi)og compaction齿兔。snapshot可以分以下情況以提升性能橱脸。

• 定期做日志 snapshot，可使用copy-on-write技術(shù)
• 可以直接保留最新的log index和term
• Leader執(zhí)行AppendEntries RPC時(shí)分苇，節(jié)點(diǎn)log entry落后太多也可以直接發(fā)送snapshot

總結(jié)

Raft 主要包括兩個(gè)獨(dú)立的子問題添诉，Leader election和log replication。流程就是先選舉出Leader医寿，然后由Leader負(fù)責(zé)復(fù)制和提交log栏赴。
為了保證算法的safety屬性，Raft對(duì)其子問題加上了諸多約束：

Election restriction：

• 每個(gè)任期的節(jié)點(diǎn)在進(jìn)行投票都只能投一票靖秩，原則是先來先到
• 選舉人的信息必須比自己了解的多(term, log replication)

Log replication

• 一個(gè)log可以被復(fù)制到大多數(shù)節(jié)點(diǎn)（committed）须眷，且不能被回滾；
• Leader 一定包含最新的committed log,因此log只會(huì)追加而不會(huì)覆蓋刪除沟突；
• 不同節(jié)點(diǎn)花颗，某個(gè)位置上日志相同，那么這個(gè)位置之前的所有日志一定是相同的惠拭；
• Raft 不能夠提交上個(gè)任期的log entries扩劝。

參考：

1. Raft動(dòng)畫