前言
建議先對raft論文有一些基本的瀏覽撕蔼，然后再看下面的內(nèi)容』蛄矗可以結(jié)合后面引用的鏈接去進(jìn)行更深入的學(xué)習(xí)惫恼。下文提到的章節(jié)，指論文的章節(jié)
正文
通過領(lǐng)導(dǎo)人的方式澳盐，Raft 將一致性問題分解成了三個(gè)相對獨(dú)立的子問題：
- 領(lǐng)導(dǎo)選舉：一個(gè)新的領(lǐng)導(dǎo)人需要被選舉出來祈纯，當(dāng)現(xiàn)存的領(lǐng)導(dǎo)人宕機(jī)的時(shí)候會(huì)重新選出一個(gè)新的領(lǐng)導(dǎo)（章節(jié) 5.2）
- 日志復(fù)制：領(lǐng)導(dǎo)人必須從客戶端接收日志然后復(fù)制到集群中的其他節(jié)點(diǎn)，并且強(qiáng)制要求其他節(jié)點(diǎn)的日志保持和自己相同叼耙。
- 安全性：在 Raft 中安全性的關(guān)鍵是在圖 3 中展示的狀態(tài)機(jī)安全：如果有任何的服務(wù)器節(jié)點(diǎn)已經(jīng)應(yīng)用了一個(gè)確定的日志條目到它的狀態(tài)機(jī)中腕窥，那么其他服務(wù)器節(jié)點(diǎn)不能在同一個(gè)日志索引位置應(yīng)用一個(gè)不同的指令。章節(jié) 5.4 闡述了 Raft 算法是如何保證這個(gè)特性的筛婉；這個(gè)解決方案涉及到一個(gè)額外的選舉機(jī)制（5.2 節(jié)）上的限制簇爆。
除此以外，還有：
日志壓縮
成員關(guān)系變化
與客戶端交互
領(lǐng)導(dǎo)選舉
重點(diǎn)閱讀論文的 5.1 以及 5.2，結(jié)合 Figure 2 食用入蛆。
只需要兩個(gè)rpc和兩個(gè)周期性檢查的timer（heartbeat timer和election timer）即可描述領(lǐng)導(dǎo)選舉：
requestVote
appendEntity（作為心跳包）
election timer作為選舉超時(shí)（隨機(jī)超時(shí)時(shí)間150ms~300ms）响蓉，使得follwer轉(zhuǎn)變?yōu)閏andidate以及candidate處于分票狀態(tài)時(shí)的重新選舉。
heartbeat timer作為心跳超時(shí)（定時(shí)哨毁，50ms）枫甲，使用appendEntity重置各follower的election timer。（日志復(fù)制那里還要維護(hù)nextIndex扼褪，matchIndex和commitIndex）
對于每一個(gè)不同狀態(tài)的 Raft 節(jié)點(diǎn)言秸，他們可能有如下并發(fā)的事件：（即復(fù)制狀態(tài)機(jī)的行為）
-
Follower
- 處理
AppendEntries（重置electionTimer，維護(hù)3個(gè)index迎捺，同步日志） - 處理
RequestVote（是否給發(fā)送請求的candidate投票举畸，需要candidate數(shù)據(jù)是up to date且獲得絕大多數(shù)節(jié)點(diǎn)的投票才能稱為leader） -
electionTimer超時(shí)（follower轉(zhuǎn)變?yōu)閏andidate）
- 處理
-
Candidate
- 處理
AppendEntries（判斷term是否轉(zhuǎn)變?yōu)閒ollower） - 處理
RequestVote（根據(jù)term是否需要轉(zhuǎn)變?yōu)閒ollower，判斷是否成為leader） -
electionTimer超時(shí)（分票后的重新選舉） - 發(fā)起投票
sendRequestVote（給集群其他節(jié)點(diǎn)發(fā)送requestVote凳枝，請求投票）
- 處理
-
Leader
- 處理
AppendEntries（判斷term是否轉(zhuǎn)變?yōu)閒ollower抄沮，維護(hù)各follower的nextIndex和matchIndex，維護(hù)leader的commitIndex） - 處理
RequestVote（判斷term是否轉(zhuǎn)變?yōu)閒ollower） -
heartbeatTimer超時(shí)(給各節(jié)點(diǎn)發(fā)送appendEntity) - 停掉
electionTimer計(jì)時(shí)器 - 發(fā)送心跳包
sendAppendEntries（根據(jù)leader的nextIndex數(shù)組打包請求參數(shù)岖瑰，發(fā)送appendEntries）
- 處理
日志復(fù)制
圖示：
黑點(diǎn)：表示matchIndex
箭頭：表示nextIndex
虛線（虛線圍起來的叛买，紫色底的2。表示日志項(xiàng)）：表示該日志還沒提交蹋订。
實(shí)線（實(shí)線圍起來的）：日志已提交
步驟：
當(dāng)前l(fā)eader通過心跳（appendEntities）維護(hù)不同節(jié)點(diǎn)的nextIndex和matchIndex率挣。
follower節(jié)點(diǎn)接收到appendEntity請求時(shí)，對比自己的和leader發(fā)過來的term和nextIndex露戒。如果自己的小椒功，就返回false，讓leader降低nextIndex智什。直到leader發(fā)過來的日志就是自己缺失的那部分动漾，直接刪掉follower節(jié)點(diǎn)的matchIndex之后的數(shù)據(jù)，添加leader發(fā)過來的自己缺失的數(shù)據(jù)荠锭。
leader節(jié)點(diǎn)接受到appendEntity的返回后：
如果是成功的返回：維護(hù)該follower的matchIndex和nextIndex旱眯，查看當(dāng)前是否絕大多數(shù)follower節(jié)點(diǎn)已復(fù)制（通過查看leader維護(hù)的matchIndex數(shù)組來判斷），如果大多數(shù)已復(fù)制证九，即表示該日志項(xiàng)已提交删豺，下一次心跳的AppendEntity會(huì)使得各follower的commitIndex也得到更新，即各follower節(jié)點(diǎn)的該日志項(xiàng)也處于已提交狀態(tài)愧怜。呀页；
如果是失敗的返回，降低對應(yīng)follower的nextIndex叫搁，然后直接對該follower重新發(fā)送appendEntity
此時(shí)該復(fù)制狀態(tài)機(jī)的狀態(tài)就保持了一致（獲得共識(shí)）赔桌。
安全性
詳見論文第五節(jié)
描述了 Raft 算法是如何選舉和復(fù)制日志的。然而渴逻，到目前為止描述的機(jī)制并不能充分的保證每一個(gè)狀態(tài)機(jī)會(huì)按照相同的順序執(zhí)行相同的指令疾党。
-
選舉限制
Raft 使用投票的方式來阻止一個(gè)候選人贏得選舉除非這個(gè)候選人包含了所有已經(jīng)提交的日志條目。候選人為了贏得選舉必須聯(lián)系集群中的大部分節(jié)點(diǎn)惨奕，這意味著每一個(gè)已經(jīng)提交的日志條目在這些服務(wù)器節(jié)點(diǎn)中肯定存在于至少一個(gè)節(jié)點(diǎn)上雪位。如果候選人的日志至少和大多數(shù)的服務(wù)器節(jié)點(diǎn)一樣新（up to date，Raft 通過比較兩份日志中最后一條日志條目的索引值和任期號定義誰的日志比較新）梨撞，那么他一定持有了所有已經(jīng)提交的日志條目雹洗。
-
提交之前任期內(nèi)的日志條目
Raft 永遠(yuǎn)不會(huì)通過計(jì)算副本數(shù)目的方式去提交一個(gè)之前任期內(nèi)的日志條目。只有領(lǐng)導(dǎo)人當(dāng)前任期里的日志條目通過計(jì)算副本數(shù)目可以被提交卧波；一旦當(dāng)前任期的日志條目以這種方式被提交时肿，那么由于日志匹配特性，之前的日志條目也都會(huì)被間接的提交港粱。
成員關(guān)系變化
詳見論文第6小節(jié)螃成。
兩階段變更的方式：
第一階段：共同一致（過渡階段）
領(lǐng)導(dǎo)者收到從舊配置到新配置的變更請求時(shí)，創(chuàng)建共同一致的日志并復(fù)制給其他節(jié)點(diǎn)
follower以最新的配置做決定查坪，領(lǐng)導(dǎo)者需要以已經(jīng)提交的配置來做決定
新舊配置中所有機(jī)器都可能成為領(lǐng)導(dǎo)者
達(dá)成一致要在新舊配置上均獲得大多數(shù)支持
第二階段：切換到新配置
- 提交新配置的日志到所有節(jié)點(diǎn)寸宏，一旦新配置的日志被提交，即完成變更
日志壓縮
詳見論文第7小節(jié)
在實(shí)際的系統(tǒng)中偿曙，Raft 產(chǎn)生的日志在持續(xù)的正常操作中不斷增長氮凝，但不可以無限的增長下去。
快照（snapshot）是最簡單的壓縮方式望忆。在快照中罩阵，全部的當(dāng)前系統(tǒng)狀態(tài)都被寫入到快照中，存儲(chǔ)到持久化的存儲(chǔ)中启摄，然后在那個(gè)時(shí)刻之前的全部日志都可以被丟棄永脓。
Raft快照基本思想：
每個(gè)服務(wù)器獨(dú)立創(chuàng)建快照，只包括已經(jīng)被提交的日志
快照值存儲(chǔ)了當(dāng)前的狀態(tài)鞋仍、最后的索引位置和任期號
快照完成后常摧，刪除最后索引位置之前的所有日志和快照
領(lǐng)導(dǎo)人必須偶爾的發(fā)送快照給一些落后的follower
異常情況分析
上圖的任意一步，任意一個(gè)節(jié)點(diǎn)都可以宕機(jī)威创。也可以保證數(shù)據(jù)一致性落午。。
follower或者candidate節(jié)點(diǎn)崩潰
如果不是一半節(jié)點(diǎn)崩潰肚豺，服務(wù)還是可用溃斋，leader還是可以通過appendEntity給正常follower節(jié)點(diǎn)復(fù)制數(shù)據(jù)，確認(rèn)接收后吸申，leader保證該日志項(xiàng)是提交狀態(tài)梗劫，向客戶端返回操作成功享甸，等到心跳（appendEntity）使得follower對于該日志項(xiàng)也提交成功；
如果超過一半節(jié)點(diǎn)崩潰梳侨，服務(wù)不可用蛉威，等待節(jié)點(diǎn)重啟，通過appendEntity掃描節(jié)點(diǎn)需要同步的數(shù)據(jù)（維護(hù)nextIndex走哺，matchIndex）蚯嫌，使用leader的數(shù)據(jù)覆蓋當(dāng)前follower數(shù)據(jù)，即該節(jié)點(diǎn)已同步完成數(shù)據(jù)丙躏，等待多數(shù)節(jié)點(diǎn)恢復(fù)择示，服務(wù)即可用。
客戶端請求的數(shù)據(jù)到達(dá)leader前晒旅，leader崩潰
等待集群重新選舉栅盲。且客戶端重新請求。
客戶端數(shù)據(jù)已到達(dá)leader废恋，但未復(fù)制到絕大多數(shù)follower（即處于uncommited）剪菱，leader崩潰
uncommited數(shù)據(jù)無意義。等待集群重新選舉拴签。且客戶端重新請求孝常。
客戶端數(shù)據(jù)已到達(dá)leader，已復(fù)制到絕大多數(shù)follower（處于commited）蚓哩，leader崩潰
等待集群重新選舉构灸。且客戶端重新請求。但是該不應(yīng)該繼續(xù)保存在復(fù)制狀態(tài)機(jī)上岸梨。（不然就造成重復(fù)提交）喜颁。因此需要raft服務(wù)能內(nèi)部去重（具備冪等性，實(shí)現(xiàn)線性化語義）曹阔，論文上是第八節(jié)（client interaction）中提到一個(gè)解決方案就是：
客戶端對于每一條指令都賦予一個(gè)唯一的序列號半开。然后，狀態(tài)機(jī)跟蹤每條指令最新的序列號和相應(yīng)的響應(yīng)赃份。如果接收到一條指令寂拆，它的序列號已經(jīng)被執(zhí)行了，那么就立即返回結(jié)果抓韩，而不重新執(zhí)行指令纠永。
網(wǎng)絡(luò)分區(qū)，導(dǎo)致雙leader
客戶端向那個(gè)不具備絕大多數(shù)節(jié)點(diǎn)的leader請求谒拴，肯定是超時(shí)的尝江。
客戶端只有向具備絕大多數(shù)節(jié)點(diǎn)的leader請求才能正常返回。
多說一下英上，分區(qū)后的數(shù)據(jù)恢復(fù)：
不正常的leader網(wǎng)絡(luò)恢復(fù)炭序，接收到正常leader的appendEntity后降級為follower啤覆，進(jìn)行日志復(fù)制過程。
代碼實(shí)現(xiàn)raft
自己實(shí)現(xiàn)過一個(gè)簡單的raft惭聂，包含領(lǐng)導(dǎo)選舉窗声，日志復(fù)制和安全性，未實(shí)現(xiàn)日志壓縮彼妻，成員關(guān)系變化嫌佑。
思路：
一個(gè)節(jié)點(diǎn)使用了一個(gè)go routine模擬一個(gè)狀態(tài)機(jī)豆茫，兩個(gè)timer侨歉，兩個(gè)rpc（使用go的net/rpc內(nèi)置包）。
但是發(fā)現(xiàn)測試特別困難揩魂。僅僅根據(jù)論文描述寫了代碼幽邓，也簡單的打印測試，基本是可用的火脉，可以選舉出來leader牵舵，同步數(shù)據(jù)，但是異常邊界情況很難模擬出來然后測試倦挂。
代碼如下畸颅，實(shí)現(xiàn)不完整：
https://github.com/theoneLee/go-raft-demo
todo
后面發(fā)現(xiàn)raft.github.io上有一個(gè)mit分布式系統(tǒng)的課程，里面包含了raft的一個(gè)實(shí)現(xiàn)方援，且附帶完善的測試用例没炒，準(zhǔn)備好好看課程,然后實(shí)現(xiàn)這塊內(nèi)容。
參考
- 論文
https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
- 可視化raft
http://thesecretlivesofdata.com/raft/
- mit 6.824
http://nil.csail.mit.edu/6.824/2020/index.html
- 《云原生分布式存儲(chǔ)基石 etcd深入解析》第一章
