raft 學(xué)習(xí)筆記
最近在學(xué)習(xí) 6.824 的分布式課程.
學(xué)習(xí)到 Raft 算法. 寫篇文章作為記錄.
什么是 Raft
Raft 是一個用于管理分布式副本一致性的算法, 設(shè)計的目的是為了使分布式一致性更加容易理解和實現(xiàn).
算法細(xì)節(jié)
目前實現(xiàn)的 Raft 算法主要包含兩個部分, 一個是領(lǐng)導(dǎo)者選舉, 另外一個是日志復(fù)制.
領(lǐng)導(dǎo)者選舉
在 Raft 算法中存在三種角色, 領(lǐng)導(dǎo)者/候選人/跟隨者. 有兩個時間的概念, 心跳時間(固定時間)/選舉超時時間(隨機時間).
在初始狀態(tài)下, 所有的角色都是候選人, 等到選舉超時時間到的時候發(fā)起選舉投票, 如果得到半數(shù)以上的選票則變?yōu)轭I(lǐng)導(dǎo)者.
當(dāng)角色變成領(lǐng)導(dǎo)者之后要立即對所有的成員發(fā)起心跳請求, 以鞏固領(lǐng)導(dǎo)者的地位(阻止其他成員繼續(xù)發(fā)起投票請求). 如果一個
成員收到了心跳請求, 則變成跟隨者角色, 并作出響應(yīng).
日志復(fù)制
日志復(fù)制的的請求使伴隨在心跳請求中的, 也就是說如果存在沒有同步給其他成員的日志, 則在心跳的時候附帶上這些日志.
對于客戶端的請求, 只有復(fù)制到大多數(shù)成員的時候才認(rèn)為這個請求使可提交的狀態(tài), 領(lǐng)導(dǎo)者提交之后也要通知其他成員提交.
Raft 算法實現(xiàn)
在 6.824 的課程當(dāng)中提供了一個骨架以及一些測試用例, 目標(biāo)是實現(xiàn)提供的接口, 最終通過所有的測試. 下面是論文中的實現(xiàn)方式.
所有服務(wù)器都需要存儲的狀態(tài)
在回復(fù) RPCs 的響應(yīng)之前保存到磁盤
- currentTerm 服務(wù)器所經(jīng)歷的最后一屆領(lǐng)導(dǎo)人 (初始化為 0, 單調(diào)遞增)
- votedFor 當(dāng)前任期(上面的currentTerm)獲取投票的候選人ID
- log[] log隊列, 每個log實體包含一個給狀態(tài)機的命令和領(lǐng)導(dǎo)人收到時的任期號(第一個索引號為1)
所有服務(wù)器變化的狀態(tài)
- commitIndex 服務(wù)器知道的最高的應(yīng)該提交的log實體編號(初始化為 0, 單調(diào)遞增).
- lastApplied 服務(wù)器應(yīng)用到狀態(tài)機的log實體最高編號(初始化為0, 單調(diào)遞增)
領(lǐng)導(dǎo)人經(jīng)常變化的狀態(tài)
贏得選舉之后需要重新初始化.
- nextIndex[] 維護每個服務(wù)器下一個需要發(fā)送的log實體的編號(初始化為領(lǐng)導(dǎo)人最新的log實體編號 加 1).
- matchIndex[] 維護每個服務(wù)器得到確認(rèn)的最大log實體編號.
所有成員需要實現(xiàn)的接口(RPC)
請求選舉的 RPC
用于候選人調(diào)用獲得選票
參數(shù)列表
- term 候選人的任期號
- candidateId 候選人ID
- lastLogIndex 候選人的最新log實體的編號.
- lastLogTerm 候選人的最新log實體的任期號
返回值
- term 當(dāng)前任期號(currentTerm), 用于候選人更新自己
- voteGranted true 表示投票給該候選人
接受者的實現(xiàn)
- 如果 term < currentTerm 返回 false.
- 如果 votedFor 狀態(tài)為空, 或者為請求中的 candidateId, 并且候選人的 log 至少跟接受者的日志一樣新, 則投出選票 true, 否則 false.
復(fù)制 log 的 RPC
用于領(lǐng)導(dǎo)人調(diào)用來復(fù)制log實體. 也用于維持心跳.
參數(shù)列表
- term 領(lǐng)導(dǎo)人的任期號
- leaderId 領(lǐng)導(dǎo)人 ID, 用于跟隨者可以轉(zhuǎn)發(fā)請求
- prevLogIndex 上一個 log 的索引號.
- prevLogTerm 上一個 log 的任期號.
- entries[] 需要存儲的 log (心跳的這個字段為空; 為了提高效率可能會發(fā)送多個)
- leaderCommit 領(lǐng)導(dǎo)人的 commitIndex
返回值
- term 當(dāng)前任期(currentTerm), 用于領(lǐng)導(dǎo)人更新自己
- success 如果接受者存在與 prevLogIndex 和 prevLogTerm 匹配的日志則返回 true
接收者實現(xiàn)
- 如果 term < currentTerm 返回 false.
- 如果接收者的log隊列中不包含與 prevLogIndex 和 prevLogTerm 匹配的日志, 返回 false.
- 如果接收者存在一個 log 與發(fā)來的 log prevLogIndex 匹配但是 prevLogTerm 不匹配, 則刪掉這個 log 及之后所有的 log.
- 把所有不存在于 log 隊列中的 log, 添加到隊列中
- 如果 leaderCommit > commitIndex, 則 commitIndex = min(leaderCommit, 新發(fā)來的 log 的 index)
所有服務(wù)器都應(yīng)該遵守的規(guī)則
所有服務(wù)器
- 如果 commitIndex > lastApplied, 增加 lastApplid, 應(yīng)用 log[lastapplied] 到狀態(tài)機中
- 如果 RPC 請求或者響應(yīng)當(dāng)中包含的任期 T > currentTerm, 則 currentTerm = T, 并且自己轉(zhuǎn)換到跟隨者狀態(tài).
跟隨者
- 響應(yīng)來自候選人和領(lǐng)導(dǎo)人的 RPC.
- 如果選舉時間超時, 并且沒有收到附加日志(或者心跳)的 RPC, 也沒用收到選舉請求, 則自己轉(zhuǎn)變?yōu)楹蜻x人
候選人
- 當(dāng)轉(zhuǎn)變?yōu)楹蜻x人的時候, 開始選舉:
- 增加currentTerm
- 給自己投票
- 重置選舉超時計時器
- 發(fā)送 RequestVote RPC 給所有服務(wù)器
- 如果收到大多數(shù)服務(wù)器的支持選票則變?yōu)轭I(lǐng)導(dǎo)人
- 如果收到了一個新的領(lǐng)導(dǎo)人的附加日志的RPC 或者 心跳, 則轉(zhuǎn)變?yōu)楦S者
- 如果選舉超時, 開始一輪新的選舉(跳轉(zhuǎn)到步驟 1)
領(lǐng)導(dǎo)人
- 贏得選舉之后不斷發(fā)送心跳給所有的服務(wù)器, 防止超時
- 如果收到客戶端命令: 首先添加到本地的日志隊列, 在應(yīng)用到狀態(tài)機之后應(yīng)答客戶端.
- 如果最新的log編號>= 跟隨者的 nextIndex 編號: 從 nextIndex 索引號開始發(fā)送附加log的 RPC.
- 如果成功: 更新跟隨者的 nextIndex 和 matchIndex
- 如果因為 log 不匹配而失敗: 減小 nextIndex 的值并且重試.
- 如果存在一個 N, 這個 N 滿足: N > commitIndex, 并且 大多數(shù)跟隨者的 matchIndex[i] >= N, 并且 log[N].term == currentTerm, 那么就讓 commitIndex = N.
現(xiàn)在只實現(xiàn)了選舉和日志復(fù)制兩部分內(nèi)容, 關(guān)于集群的變更等內(nèi)容后續(xù)會繼續(xù)實現(xiàn), 課程中后續(xù)還會基于這個實現(xiàn)的基礎(chǔ)上
來實現(xiàn)一個分布式的 KV存儲.
最后附上代碼地址: https://gist.github.com/icodinglife/910869da89a2e62a1b4deae994fb8d0b
由于剛剛接觸 golang, 對于一些用法還不是太熟悉, 代碼中有一些比較丑陋或者錯誤的設(shè)計和用法, 后續(xù)隨著不斷熟悉和深入
會慢慢重構(gòu)掉. 歡迎大家討論拍磚提意見 : )
歡迎打賞, 鼓勵我堅持下去~~~ : )
