前言
Raft算法是解決分布式系統(tǒng)共識(shí)的問(wèn)題的算法，Raft是基于Multi-Paxos的基礎(chǔ)上做了簡(jiǎn)化和限制衫画。不同于Paxos的難以理解，Raft設(shè)計(jì)的首要目的就是可理解性皮壁，一個(gè)易于理解笼沥、實(shí)現(xiàn)簡(jiǎn)單的分布式一致性協(xié)議。
Raft 將一致性算法分解成了幾個(gè)關(guān)鍵模塊窜骄，例如領(lǐng)導(dǎo)人選舉锦募、日志復(fù)制和安全性，本文將主要基于raft論文簡(jiǎn)單分析raft算法邻遏。
領(lǐng)導(dǎo)選舉
Raft是強(qiáng)領(lǐng)導(dǎo)(Strong leader)模型糠亩，一切以leader為主，比如日志只能由leader復(fù)制到其他服務(wù)器准验。所以leader的選舉是非常重要的一部分赎线。
首先介紹raft算法的三個(gè)服務(wù)狀態(tài)：
- Leader：處理客戶端請(qǐng)求、向集群其他服務(wù)發(fā)送心跳糊饱、日志復(fù)制管理垂寥。
- Follower：接受leader的信息，當(dāng)于leader心跳超時(shí)另锋，轉(zhuǎn)換為候選者(candidate)滞项。
- Candidate：候選人將向其他節(jié)點(diǎn)發(fā)送請(qǐng)求投票消息，通知其他節(jié)點(diǎn)來(lái)投票夭坪，如果贏得了大多數(shù)選票文判，就晉升當(dāng)領(lǐng)導(dǎo)者。
任意時(shí)間集群中只能由一個(gè)leader存在室梅。
Raft使用心跳機(jī)制實(shí)現(xiàn)leader選舉律杠。在服務(wù)啟動(dòng)的時(shí)候，處于follower角色竞惋，需要注意的是每個(gè)服務(wù)于leader的心跳超時(shí)的時(shí)間是隨機(jī)的(150-300 毫秒)柜去。
如上圖，集群中有三個(gè)幾點(diǎn)A拆宛、B嗓奢、C，超時(shí)時(shí)間分別為150ms浑厚、200ms股耽、300ms剛啟動(dòng)時(shí)任期編號(hào)都是0根盒，都處于follower角色。節(jié)點(diǎn)A與leader的心跳超時(shí)時(shí)間最短物蝙，最先從follower狀態(tài)轉(zhuǎn)為candidate炎滞，并增加自己的任期編號(hào)，先給自己投上一張選票诬乞，并向集群中其他節(jié)點(diǎn)發(fā)送投票信息册赛，當(dāng)B、C節(jié)點(diǎn)接受到A的投票請(qǐng)求之后震嫉，在任期為1的這個(gè)階段沒(méi)有給其他節(jié)點(diǎn)投過(guò)票森瘪，便接受A的投票請(qǐng)求。此時(shí)節(jié)點(diǎn)A接受到了集群中超過(guò)一半的節(jié)點(diǎn)的投票票堵，便成為任期為1的leader扼睬。
上訴是最簡(jiǎn)單的選舉流程，里面有很多概念都需要解釋悴势，比如為什么超時(shí)時(shí)間不一樣窗宇？任期編號(hào)是什么？投票比較的規(guī)則又是什么特纤？
1. 任期編號(hào)
每個(gè)leader在當(dāng)選期間都有一個(gè)自己的任期編號(hào)军俊，它是全局單調(diào)遞增的數(shù)字。每個(gè)節(jié)點(diǎn)都存儲(chǔ)這當(dāng)前的leader的任期編號(hào)叫潦，當(dāng)處于candidate階段的時(shí)候蝇完，發(fā)起投票的時(shí)候會(huì)把當(dāng)前任期編號(hào)加一。
而且當(dāng)一個(gè)節(jié)點(diǎn)接受到比自己任期高的請(qǐng)求時(shí)矗蕊，會(huì)將自己的任期編號(hào)更新為高的任期編號(hào)短蜕，如果當(dāng)前角色是leader，會(huì)從leader轉(zhuǎn)換為follower角色傻咖。當(dāng)接受到任期編號(hào)比自己小的請(qǐng)求時(shí)朋魔，節(jié)點(diǎn)會(huì)直接拒絕這個(gè)請(qǐng)求。
2. 投票比較規(guī)則
a. 先到先服務(wù)：一個(gè)節(jié)點(diǎn)在一個(gè)任期只能投一票卿操，如果A警检、B節(jié)點(diǎn)都請(qǐng)求C節(jié)點(diǎn)投票，C節(jié)點(diǎn)如果先投給A之后害淤、就會(huì)拒絕B的投票請(qǐng)求扇雕。
b.日志完整性：一個(gè)節(jié)點(diǎn)接受的投票信息如果它的日志比自身小，將會(huì)拒絕該投票請(qǐng)求窥摄。
c.過(guò)半策略：當(dāng)某節(jié)點(diǎn)接受到了集群中超過(guò)一半的節(jié)點(diǎn)投票之后镶奉，成為該次任期的leader，向其他節(jié)點(diǎn)發(fā)送leader心跳。
d. 在等待投票期間哨苛，candidate 可能會(huì)收到另一個(gè)聲稱自己是 leader 的服務(wù)器節(jié)點(diǎn)發(fā)來(lái)的 AppendEntries RPC 鸽凶。如果這個(gè) leader 的任期號(hào)（包含在RPC中）不小于 candidate 當(dāng)前的任期號(hào)，那么 candidate 會(huì)承認(rèn)該 leader 的合法地位并回到 follower 狀態(tài)建峭。
3.隨機(jī)超時(shí)
前面提高過(guò)玻侥，每個(gè)幾點(diǎn)與leader的心跳超時(shí)時(shí)間是不同的，這樣的好處在于避免瓜分票數(shù)的情況存在亿蒸，能快速的進(jìn)行l(wèi)eader選舉凑兰。如果各個(gè)節(jié)點(diǎn)的超時(shí)時(shí)間都是一樣的，就容易出現(xiàn)瓜分票數(shù)的情況存在祝懂，每個(gè)節(jié)點(diǎn)都沒(méi)有獲得超過(guò)一半的投票票摇，就會(huì)開啟下一輪的選舉拘鞋，選舉時(shí)間就會(huì)很長(zhǎng)砚蓬。使用隨機(jī)超時(shí)機(jī)制，正常情況下盆色，一個(gè)時(shí)間段里只有一個(gè)節(jié)點(diǎn)發(fā)起投票請(qǐng)求灰蛙。
下圖是整個(gè)集群中服務(wù)角色變化的流程圖。
日志復(fù)制
Leader選舉出來(lái)之后為客戶端提供服務(wù)隔躲，將接受到的指令作為一個(gè)新的日志項(xiàng)追加到日志中去摩梧，然后并行的發(fā)起 AppendEntries RPC 給其他的服務(wù)器，讓它們復(fù)制該日志項(xiàng)宣旱。當(dāng)該日志項(xiàng)被安全地復(fù)制（過(guò)半的節(jié)點(diǎn)已復(fù)制完成）仅父，leader 會(huì)應(yīng)用該日志項(xiàng)到它的狀態(tài)機(jī)中（狀態(tài)機(jī)執(zhí)行該指令）然后把執(zhí)行的結(jié)果返回給客戶端。如果 follower 崩潰或者運(yùn)行緩慢浑吟，或者網(wǎng)絡(luò)丟包笙纤，領(lǐng)導(dǎo)人會(huì)不斷地重試 AppendEntries RPC（即使已經(jīng)回復(fù)了客戶端）直到所有的 follower 最終都存儲(chǔ)了所有的日志。
什么是日志
上圖展示了日志的格式组力，一個(gè)日志項(xiàng)包含三部分
- 索引(index)：日志項(xiàng)對(duì)應(yīng)的整數(shù)索引值省容。它其實(shí)就是用來(lái)標(biāo)識(shí)日志項(xiàng)的，是一個(gè)連續(xù)的燎字、單調(diào)遞增的整數(shù)號(hào)碼腥椒。
- 指令：一條由客戶端請(qǐng)求指定的、狀態(tài)機(jī)需要執(zhí)行的指令候衍。
- 任期編號(hào)：創(chuàng)建這條日志項(xiàng)的領(lǐng)導(dǎo)者的任期編號(hào)笼蛛。
復(fù)制
Leader通過(guò) AppendEntries RPC 將日志復(fù)制到其他節(jié)點(diǎn)。
AppendEntries RPC：
| 參數(shù) | 解釋 |
|---|---|
| term | 領(lǐng)導(dǎo)人的任期號(hào) |
| leaderId | 領(lǐng)導(dǎo)人的 Id蛉鹿，以便于跟隨者重定向請(qǐng)求 |
| prevLogIndex | 新的日志條目緊隨之前的索引值 |
| prevLogTerm | prevLogIndex 條目的任期號(hào) |
| entries[] | 準(zhǔn)備存儲(chǔ)的日志條目（表示心跳時(shí)為空滨砍；一次性發(fā)送多個(gè)是為了提高效率） |
| leaderCommit | 領(lǐng)導(dǎo)人已經(jīng)提交的日志的索引值 |
| 返回值 | 解釋 |
|---|---|
| term | 前的任期號(hào)，用于領(lǐng)導(dǎo)人去更新自己 |
| success | 跟隨者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志時(shí)為真 |
接收者實(shí)現(xiàn)：
- 如果 term < currentTerm 就返回 false
- 如果日志在 prevLogIndex 位置處的日志條目的任期號(hào)和 prevLogTerm 不匹配，則返回 false
- 如果已經(jīng)存在的日志條目和新的產(chǎn)生沖突（索引值相同但是任期號(hào)不同）惨好，刪除這一條和之后所有的
- 附加日志中尚未存在的任何新條目
- 如果 leaderCommit > commitIndex煌茴，令 commitIndex 等于 leaderCommit 和 新日志條目索引值中較小的一個(gè)
上訴是AppendEntries RPC的參數(shù)的接受流程。term與leaderId不用介紹很簡(jiǎn)單日川，而prevLogIndex蔓腐、prevLogTerm的作用是日志的一致性檢測(cè)，如果 follower 在它的日志中找不到包含相同索引位置和任期號(hào)的條目龄句，那么他就會(huì)拒絕該新的日志條目回论。一致性檢查就像一個(gè)歸納步驟：一開始空的日志狀態(tài)肯定是滿足 Log Matching Property（日志匹配特性） 的，然后一致性檢查保證了日志擴(kuò)展時(shí)的日志匹配特性分歇。因此傀蓉，每當(dāng) AppendEntries RPC 返回成功時(shí)，leader 就知道 follower 的日志一定和自己相同（從第一個(gè)日志條目到最新條目）职抡。
正常操作期間葬燎，leader 和 follower 的日志保持一致，所以 AppendEntries RPC 的一致性檢查從來(lái)不會(huì)失敗缚甩。然而谱净，leader 崩潰的情況會(huì)使日志處于不一致的狀態(tài)（老的 leader 可能還沒(méi)有完全復(fù)制它日志里的所有條目）。如下情況：
在 Raft 算法中擅威，leader 通過(guò)強(qiáng)制 follower 復(fù)制它的日志來(lái)解決不一致的問(wèn)題壕探。這意味著 follower 中跟 leader 沖突的日志條目會(huì)被 leader 的日志條目覆蓋。
Leader 針對(duì)每一個(gè) follower 都維護(hù)了一個(gè) nextIndex 郊丛，表示 leader 要發(fā)送給 follower 的下一個(gè)日志條目的索引李请。當(dāng)選出一個(gè)新 leader 時(shí)，該 leader 將所有 nextIndex 的值都初始化為自己最后一個(gè)日志條目的 index 加1厉熟。如果 follower 的日志和 leader 的不一致导盅，那么下一次 AppendEntries RPC 中的一致性檢查就會(huì)失敗。在被 follower 拒絕之后庆猫，leaer 就會(huì)減小 nextIndex 值并重試 AppendEntries RPC 认轨。最終 nextIndex 會(huì)在某個(gè)位置使得 leader 和 follower 的日志達(dá)成一致。此時(shí)月培，AppendEntries RPC 就會(huì)成功嘁字，將 follower 中跟 leader 沖突的日志條目全部刪除然后追加 leader 中的日志條目（如果有需要追加的日志條目的話）。一旦 AppendEntries RPC 成功杉畜，follower 的日志就和 leader 一致纪蜒，并且在該任期接下來(lái)的時(shí)間里保持一致。
總結(jié)
本機(jī)簡(jiǎn)單介紹了raft 的leader選舉和日志復(fù)制此叠，當(dāng)然raft還有其他的特性本文并沒(méi)有介紹纯续，推薦去看raft的論文，完整的了解raft。
我之前ZAB協(xié)議的文章分析了zookeeper的zab協(xié)議猬错，這里對(duì)比一下兩者的異同窗看。
- 兩者都是強(qiáng)領(lǐng)導(dǎo)模型，由領(lǐng)導(dǎo)接受處理請(qǐng)求倦炒、復(fù)制日志显沈。
- leader選舉，兩者都需要獲取過(guò)半節(jié)點(diǎn)的投票才能選舉出leader逢唤，raft采用隨機(jī)超時(shí)和先到先服務(wù)的策略拉讯，相比zab協(xié)議會(huì)盡快選舉出leader。
- 日志復(fù)制鳖藕，在服務(wù)正常運(yùn)行期間兩者的日志復(fù)制沒(méi)什么區(qū)別魔慷，都是由leader復(fù)制和過(guò)半節(jié)點(diǎn)確認(rèn)提交日志。但是從leader崩潰到選舉出新的leader著恩，zab需要經(jīng)過(guò)DISCOVERY和SYNCHRONIZATION兩個(gè)階段院尔，來(lái)確認(rèn)自己的leader地位和保持其他節(jié)點(diǎn)與leader的日志一致，才能對(duì)外提供服務(wù)页滚。而raft選舉完成之后就能對(duì)外提供服務(wù)召边，通過(guò)心跳和日志復(fù)制來(lái)完成leader的確認(rèn)和日志的一致性铺呵。
最后https://raft.github.io這個(gè)網(wǎng)址詳細(xì)介紹了raft協(xié)議裹驰。
參考
https://time.geekbang.org/column/intro/279
https://raft.github.io/
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
