柚子快報邀請碼778899分享：【分布式協(xié)議與算法】Raft

http://yzkb.51969.com/

協(xié)議和算法篇

Raft算法

如何選舉領(lǐng)導(dǎo)者？

有哪些成員身份

領(lǐng)導(dǎo)者：處理寫請求，管理日志復(fù)制，不斷發(fā)送心跳信息跟隨者：接受和處理來自領(lǐng)導(dǎo)者的消息，領(lǐng)導(dǎo)者心跳超時，會主動推薦自己當(dāng)候選人候選人：向其他節(jié)點發(fā)送請求投票RPC消息，通知其他節(jié)點來投票，如果贏得大多數(shù)選票，晉升為領(lǐng)導(dǎo)者

選舉領(lǐng)導(dǎo)者的過程

1.初始狀態(tài)，所有節(jié)點都是跟隨者狀態(tài)。Raft算法實現(xiàn)了隨機超時時間的特性，每個節(jié)點等待領(lǐng)導(dǎo)者節(jié)點心跳信息的超時時間間隔是隨機的。

2.上圖的A因為超時時間最短，會最先變成候選人，發(fā)起投票（先給自己投票，再給其他節(jié)點發(fā)送投票消息）

3.如果其他節(jié)點接收到A的請求投票消息，在編號為1的任期中，還沒有進行過投票，它將把投票給節(jié)點A，并增加自己的任期編號

4.如果候選人在選舉超時時間內(nèi)贏得了大多數(shù)選票，就會成為本屆任期內(nèi)新的領(lǐng)導(dǎo)者

5.A當(dāng)選領(lǐng)導(dǎo)者后，將周期性地發(fā)送心跳消息，通知其他服務(wù)器我是領(lǐng)導(dǎo)者，阻止跟隨者發(fā)起新的選舉

選舉過程四連問

節(jié)點間如何通訊

領(lǐng)導(dǎo)者選舉中，通常需要用到兩類RPC： 1.請求投票RPC，是由候選人在選舉期間發(fā)起，通知各節(jié)點進行投票 2.日志復(fù)制RPC，是由領(lǐng)導(dǎo)者發(fā)起，用于復(fù)制日志和提供心跳信息

什么是任期

1.跟隨者在等待領(lǐng)導(dǎo)者心跳信息超時后，推舉自己成為候選人時，會增加自己的任期號 2.如果一個服務(wù)器節(jié)點，發(fā)現(xiàn)自己的任期編號比其他節(jié)點小，那么他會更新自己的編號到較大的編號值 3.如果一個候選者或者領(lǐng)導(dǎo)者，發(fā)現(xiàn)自己的任期編號比其他節(jié)點小，那么他會立即恢復(fù)成跟隨者狀態(tài) 4.如果一個節(jié)點接收到一個包含較小任期編號的請求，那么他會直接拒絕這個請求

選舉有哪些規(guī)則

1.領(lǐng)導(dǎo)者周期性地向所有跟隨者發(fā)送心跳消息，通知大家我是領(lǐng)導(dǎo)者 2.如果在指定時間內(nèi)，跟隨者沒有接收到來自領(lǐng)導(dǎo)者的消息，那么他會認為當(dāng)前沒有領(lǐng)導(dǎo)者，推舉自己為候選人，發(fā)起領(lǐng)導(dǎo)者選舉 3.在一次選舉中，贏得大多數(shù)選票的候選人，將晉升為領(lǐng)導(dǎo)者 4.在一個任期內(nèi)，領(lǐng)導(dǎo)者一直都會是領(lǐng)導(dǎo)者，直到他自身出現(xiàn)問題（宕機），或者因為網(wǎng)絡(luò)延遲，其他節(jié)點發(fā)起一輪新的選舉 5.在一次選舉中，每一個服務(wù)器節(jié)點最多會對一個任期編號透出一張選票，并按照“先來先服務(wù)”的原則進行投票 6.當(dāng)任期編號相同時，日志完整性高的跟隨者，拒絕投票給日志完整性低的候選人

隨機超時時間又是什么

Raft算法巧妙地使用隨機選舉超時時間，將超時時間都分散開來，在大多數(shù)情況下只有一個服務(wù)器節(jié)點先發(fā)起選舉 1.跟隨者等待領(lǐng)導(dǎo)者心跳信息超時的時間間隔是隨機的 2.當(dāng)沒有候選人贏得過半票數(shù)，選舉無效了，這時需要等待一個隨機時間間隔，也即等待選舉超時的時間間隔是隨機的

內(nèi)容小結(jié)

1.Raft中，只有日志最完整的節(jié)點才能當(dāng)領(lǐng)導(dǎo)者，并且日志必須是連續(xù)的 2.通過任期，領(lǐng)導(dǎo)者心跳信息，隨機選舉超時時間，大多數(shù)選票原則等，保證了一個任期只有一位領(lǐng)導(dǎo)

日志復(fù)制

如何理解日志

日志是一種數(shù)據(jù)格式，包含：指令，任期編號，索引值

指令：一條由客戶端指定的，狀態(tài)機需要執(zhí)行的指令索引值：日志項對應(yīng)的整數(shù)索引值，是一個連續(xù)的，單調(diào)遞增的整數(shù)號碼任期編號：創(chuàng)建這條日志項的領(lǐng)導(dǎo)者的任期編號

如何復(fù)制日志

1.接收到客戶端請求后，領(lǐng)導(dǎo)者基于客戶端請求中的指令，創(chuàng)建一個新日志項，并附加到本地日志 2.領(lǐng)導(dǎo)者通過日志復(fù)制RPC ，將新的日志項復(fù)制到其他的服務(wù)器 3.當(dāng)領(lǐng)導(dǎo)者將日志項成功復(fù)制到大多數(shù)的服務(wù)器上的時候，領(lǐng)導(dǎo)者會將這條日志項提交給它的狀態(tài)機中 4.領(lǐng)導(dǎo)者將執(zhí)行的結(jié)果返回給客戶端 5.當(dāng)跟隨者接收到心跳信息，或者新的日志復(fù)制RPC 消息后，如果跟隨者發(fā)現(xiàn)領(lǐng)導(dǎo)者已經(jīng)提交了某條日志項，而他還沒有提交，那么跟隨者就將這條日志項提交到本地的狀態(tài)機中

如何實現(xiàn)日志的一致

領(lǐng)導(dǎo)者通過日志復(fù)制RPC 的一致性檢查，找到跟隨者節(jié)點上，與自己相同日志項的最大索引值。此時，這個索引值之前的日志，領(lǐng)導(dǎo)者和跟隨者是一致的，之后的日志是不一致的。 然后，領(lǐng)導(dǎo)者強制跟隨者更新覆蓋的不一致日志項，實現(xiàn)日志的一致。 如下圖，當(dāng)前是要復(fù)制索引為8的日志，但是找不到索引為7，任期為4的日志，繼續(xù)往前面找。找到了索引為6，任期為3的日志。那么這個日志項之前的日志是和領(lǐng)導(dǎo)者一致的，直接用領(lǐng)導(dǎo)者的日志覆蓋后面的7，8

內(nèi)容小結(jié)

1.副本數(shù)據(jù)以日志的形式存在，日志項中的指令表示用戶指定的數(shù)據(jù) 2.multi-paxos不要求日志是連續(xù)的，但在Raft 中日志必須是連續(xù)的。日志的完整性最高的節(jié)點才能當(dāng)選領(lǐng)導(dǎo)者 3.值的共識和日志的一致都是由領(lǐng)導(dǎo)者決定的

成員變更

成員變更的問題

問題：可能會出現(xiàn)兩個領(lǐng)導(dǎo)者 解決方法：單節(jié)點變更 異常情況：在領(lǐng)導(dǎo)者啟動時，創(chuàng)建一個NO_OP日志項，只有當(dāng)領(lǐng)導(dǎo)者將NO_OP日志項提交后，再執(zhí)行成員變更請求。

內(nèi)容小結(jié)

1.成員變更的問題，主要在于進行成員變更時，可能存在新舊配置的2個“大多數(shù)”，導(dǎo)致集群中同時出現(xiàn)兩個領(lǐng)導(dǎo)者，破壞了Raft的領(lǐng)導(dǎo)者的唯一性原則，影響了集群的穩(wěn)定運行 2.單節(jié)點變更是利用“一次變更一個節(jié)點，不會同時存在舊配置和新配置2個‘大多數(shù)’”的特性，實現(xiàn)成員變更（etcd，hashicorp raft） 3.一般需要根據(jù)場景特點，在一致性強度和實現(xiàn)復(fù)雜度之間進行權(quán)衡

柚子快報邀請碼778899分享：【分布式協(xié)議與算法】Raft

http://yzkb.51969.com/

推薦文章