一谍肤、角色模型

(一) Raft-node 存在三種角色：

image.png

1鳍徽、Follower：接受來(lái)自leader和Candidate 的請(qǐng)求勋陪，節(jié)點(diǎn)啟動(dòng)以后的初始化狀態(tài)一定是Follower

2皮服、Leader：處理來(lái)自客戶端的請(qǐng)求坯苹，并且承擔(dān)log復(fù)制到Follower的工作

3、Candidate：發(fā)起投票叶沛，競(jìng)選Leader（Follower 超時(shí)變成 Candidate）

(二) Raft Strong Leader

image.png

1蒲讯、Raft是限制僅有Leader節(jié)點(diǎn)可以處理寫入操作

2、Leader負(fù)責(zé)與所有的Follower節(jié)點(diǎn)進(jìn)行通信灰署，負(fù)責(zé)將log復(fù)制到Follower節(jié)點(diǎn)判帮，并收集大多數(shù)節(jié)點(diǎn)的應(yīng)答

3、Leader需要向所用的Follower節(jié)點(diǎn)發(fā)起心跳溉箕，保持和確認(rèn)Leader地位

二晦墙、選舉

(一) Terms

image.png

1. 時(shí)間被劃分為一個(gè)個(gè)任期 (term)，term id 按時(shí)間軸單調(diào)遞增肴茄；

2. 每一個(gè)任期的開始都是 Leader 選舉偎痛，選舉成功之后，Leader 在任期內(nèi)管理整個(gè)集群独郎，也就是 “選舉 + 常規(guī)操作”

3. 每個(gè)任期最多一個(gè) Leader踩麦，可能沒(méi)有 Leader (spilt-vote 導(dǎo)致)。

(二) 選舉示意圖

1. 在系統(tǒng)初始化的時(shí)候氓癌，所有節(jié)點(diǎn)都出于Follower的角色谓谦。

image.png

2. 每個(gè)節(jié)點(diǎn)隨機(jī)分配了倒計(jì)時(shí)時(shí)間。倒計(jì)時(shí)結(jié)束以后贪婉，節(jié)點(diǎn)從Follower --> Candidate反粥，并發(fā)起投票

image.png

3. B、C節(jié)點(diǎn)只收到了節(jié)點(diǎn)A的投票請(qǐng)求，于是都投票給節(jié)點(diǎn)A才顿，節(jié)點(diǎn)A成為L(zhǎng)eader角色莫湘，并與定時(shí)向所有的Follower節(jié)點(diǎn)發(fā)起Heartbeat，保持和確認(rèn)自己Leader角色郑气。

image.png

上面描述了只有一個(gè)Candidate角色時(shí)幅垮，是如何發(fā)起投票的，如果同時(shí)有多個(gè)Candidate節(jié)點(diǎn)發(fā)起投票怎么辦呢尾组？忙芒？

image.png

節(jié)點(diǎn)A和節(jié)點(diǎn)D同時(shí)成為Candidate角色發(fā)起投票，并獲取到一半的票數(shù)讳侨，都不滿足得到大多數(shù)票數(shù)的條件呵萨，因此會(huì)重新開始倒計(jì)時(shí)（時(shí)間是隨機(jī)的），最先倒計(jì)時(shí)結(jié)束的發(fā)起新一輪投票

image.png

節(jié)點(diǎn)B和節(jié)點(diǎn)C投票給節(jié)點(diǎn)A以后跨跨，就會(huì)拒絕投票給節(jié)點(diǎn)D潮峦，節(jié)點(diǎn)A晉升為L(zhǎng)eader節(jié)點(diǎn)，并且發(fā)起Hearbeat勇婴，節(jié)點(diǎn)D收到HeartBeat以后自動(dòng)轉(zhuǎn)化為Follower節(jié)點(diǎn)跑杭。

image.png

(三) 選舉限制

在任何基于領(lǐng)導(dǎo)人的一致性算法中，領(lǐng)導(dǎo)人都必須存儲(chǔ)所有已經(jīng)提交的日志條目咆耿。在某些一致性算法中，例如 Viewstamped Replication爹橱，

某個(gè)節(jié)點(diǎn)即使是一開始并沒(méi)有包含所有已經(jīng)提交的日志條目萨螺，它也能被選為領(lǐng)導(dǎo)者。

Raft 使用投票的方式來(lái)阻止一個(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)一樣新（這個(gè)新的定義會(huì)在下面討論）组砚，

那么他一定持有了所有已經(jīng)提交的日志條目吻商。請(qǐng)求投票 RPC 實(shí)現(xiàn)了這樣的限制： RPC 中包含了候選人的日志信息，然后投票人會(huì)拒絕掉那些日志沒(méi)有自己新的投票請(qǐng)求糟红。

Raft 通過(guò)比較兩份日志中最后一條日志條目的索引值和任期號(hào)定義誰(shuí)的日志比較新艾帐。如果兩份日志最后的條目的任期號(hào)不同，那么任期號(hào)大的日志更加新盆偿。

如果兩份日志最后的條目任期號(hào)相同柒爸，那么日志比較長(zhǎng)的那個(gè)就更加新。

三事扭、日志復(fù)制

(一) 日志復(fù)制原理介紹

一旦一個(gè)領(lǐng)導(dǎo)人被選舉出來(lái)捎稚，他就開始為客戶端提供服務(wù)。客戶端的每一個(gè)請(qǐng)求都包含一條被復(fù)制狀態(tài)機(jī)執(zhí)行的指令今野。領(lǐng)導(dǎo)人把這條指令作為一條新的日志條目附加到日志中去葡公，然后并行的發(fā)起附加條目 RPCs 給其他的服務(wù)器，讓他們復(fù)制這條日志條目条霜。

當(dāng)這條日志條目被安全的復(fù)制（下面會(huì)介紹）催什，領(lǐng)導(dǎo)人會(huì)應(yīng)用這條日志條目到它的狀態(tài)機(jī)中然后把執(zhí)行的結(jié)果返回給客戶端。如果跟隨者崩潰或者運(yùn)行緩慢蛔外，再或者網(wǎng)絡(luò)丟包蛆楞，領(lǐng)導(dǎo)人會(huì)不斷的重復(fù)嘗試附加日志條目 RPCs （盡管已經(jīng)回復(fù)了客戶端）直到所有的跟隨者都最終存儲(chǔ)了所有的日志條目。

image.png

日志由有序序號(hào)標(biāo)記的條目組成夹厌。每個(gè)條目都包含創(chuàng)建時(shí)的任期號(hào)（圖中框中的數(shù)字）豹爹，和一個(gè)狀態(tài)機(jī)需要執(zhí)行的指令。一個(gè)條目當(dāng)可以安全的被應(yīng)用到狀態(tài)機(jī)中去的時(shí)候矛纹，就認(rèn)為是可以提交了臂聋。

在上圖中，每一條日志條目中存儲(chǔ)了一條狀態(tài)機(jī)指令或南，和收到這條指令時(shí)的任期孩等，并且每條日志條目按index順序存儲(chǔ)。raft算法的一致性模塊采够，覺(jué)得了那些日志條目被commited肄方，并且將對(duì)應(yīng)的命令應(yīng)用到狀態(tài)機(jī)中

raft的日志系統(tǒng)存在一下特性：

• 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)，那么他們存儲(chǔ)了相同的指令蹬癌。

• 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)权她，那么他們之前的所有日志條目也全部相同

(二) 日志的一致性保證

在Raft算法中，領(lǐng)導(dǎo)人處理不一致是通過(guò)強(qiáng)制跟隨者直接復(fù)制自己的日志來(lái)解決逝薪。這意味著在跟隨者中的沖突的日志條目會(huì)被領(lǐng)導(dǎo)人的日志覆蓋

使得跟隨者的日志進(jìn)入和自己一致的狀態(tài)隅要，領(lǐng)導(dǎo)人必須找到最后兩者達(dá)成一致的地方，然后刪除從那個(gè)點(diǎn)之后的所有日志條目董济，發(fā)送自己的日志給跟隨者步清。

所有的這些操作都在進(jìn)行附加日志 RPCs 的一致性檢查時(shí)完成。領(lǐng)導(dǎo)人針對(duì)每一個(gè)跟隨者維護(hù)了一個(gè) nextIndex虏肾，這表示下一個(gè)需要發(fā)送給跟隨者的日志條目的索引地址廓啊。

當(dāng)一個(gè)領(lǐng)導(dǎo)人剛獲得權(quán)力的時(shí)候，他初始化所有的 nextIndex 值為自己的最后一條日志的index加1（圖 7 中的 11）封豪。如果一個(gè)跟隨者的日志和領(lǐng)導(dǎo)人不一致崖瞭，

那么在下一次的附加日志 RPC 時(shí)的一致性檢查就會(huì)失敗。在被跟隨者拒絕之后撑毛，領(lǐng)導(dǎo)人就會(huì)減小 nextIndex 值并進(jìn)行重試书聚。最終 nextIndex 會(huì)在某個(gè)位置使得領(lǐng)導(dǎo)人和跟隨者的日志達(dá)成一致唧领。

四、網(wǎng)絡(luò)分區(qū)

(一) Symmetric network partition tolerance（對(duì)稱網(wǎng)絡(luò)分區(qū)容忍性）

image.png

如上圖 S1 為當(dāng)前 leader雌续，網(wǎng)絡(luò)分區(qū)造成 S2 不斷增加本地 term斩个，為了避免網(wǎng)絡(luò)恢復(fù)后 S2 發(fā)起選舉導(dǎo)致正在良心 工作的 leader step-down，從而導(dǎo)致整個(gè)集群重新發(fā)起選舉驯杜，

可以增加了 pre-vote 過(guò)程來(lái)避免這個(gè)問(wèn)題的發(fā)生受啥。在 request-vote 之前會(huì)先進(jìn)行 pre-vote(currentTerm + 1, lastLogIndex, lastLogTerm)，多數(shù)派成功后才會(huì)轉(zhuǎn)換狀態(tài)為 candidate 發(fā)起真正的 request-vote鸽心，

所以分區(qū)后的節(jié)點(diǎn)滚局，pre-vote 不會(huì)成功，也就不會(huì)導(dǎo)致集群一段時(shí)間內(nèi)無(wú)法正常提供服務(wù)顽频。

(二) Asymmetric network partition tolerance(非對(duì)稱網(wǎng)絡(luò)分區(qū)容忍性)

image.png

如上圖 S1 為當(dāng)前 leader藤肢，S2 不斷超時(shí)觸發(fā)選主，S3 提升 term 打斷當(dāng)前 lease糯景，從而拒絕 leader 的更新嘁圈。

可以增加了一個(gè) tick 的檢查，每個(gè) follower 維護(hù)一個(gè)時(shí)間戳記錄下收到 leader 上數(shù)據(jù)更新的時(shí)間(也包括心跳)蟀淮，只有超過(guò) election timeout 之后才允許接受 request-vote 請(qǐng)求最住。

參考文檔

https://juejin.im/post/5c88756a6fb9a049f9136c1a

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md

http://www.reibang.com/p/8e4bbe7e276c