看動(dòng)畫(huà)學(xué)會(huì) Raft 算法
作者：HDT3213
分布式和一致性
分布式系統(tǒng)中數(shù)據(jù)必然會(huì)存在于多臺(tái)機(jī)器，一致性簡(jiǎn)單地說(shuō)就是分布式系統(tǒng)中的各個(gè)部分保持?jǐn)?shù)據(jù)一致
但讓數(shù)據(jù)保持一致往往并不像看上去那么簡(jiǎn)單，假設(shè)我們有兩臺(tái)機(jī)器 A 與 B，這時(shí) A 更新了數(shù)據(jù)，A 需要將更新的指令同步到 B，如果 A 到 B 網(wǎng)絡(luò)傳輸?shù)?B 數(shù)據(jù)落地的總時(shí)間為 500ms，那么這個(gè) 500ms 就是可能造成數(shù)據(jù)不一致的時(shí)間窗口，假如兩臺(tái)機(jī)器分屬不同機(jī)房，甚至分屬不同國(guó)家的機(jī)房，其時(shí)間窗口會(huì)更大，具體會(huì)造成什么影響呢？
在談分布式一致性之前，我們首先了解一個(gè)定理，那就是 CAP 定理，請(qǐng)注意，CAP 是定理而非理論，CAP 定理證明了一個(gè)分布式系統(tǒng)只能同時(shí)滿足一致性（Consistency）、可用性（Availability）和分區(qū)容錯(cuò)性（Partition tolerance）這三項(xiàng)中的兩項(xiàng)。
一致性（Consistency）：指的就是整個(gè)集群的所有節(jié)點(diǎn)數(shù)據(jù)保持一致
可用性（Availability）：在數(shù)據(jù)同步過(guò)程中，集群是否是可用狀態(tài)
分區(qū)容忍性（Partition tolerance）：是否能夠容忍網(wǎng)絡(luò)分區(qū)的發(fā)生
C 和 A相對(duì)好理解，這里著重說(shuō)一下 P（Partition tolerance）分區(qū)容忍性，聽(tīng)著比較拗口，說(shuō)實(shí)話，剛開(kāi)始看到他的時(shí)候也是一臉茫然，分區(qū)？什么是分區(qū)？其實(shí)分區(qū)（Partition）簡(jiǎn)單的說(shuō)就是服務(wù)器之間的網(wǎng)絡(luò)通信斷了，兩邊的服務(wù)器變成兩個(gè)獨(dú)立的集群，這就是所謂的分區(qū)，斷了的原因有很多比如交換機(jī)故障，路由器故障，掃地阿姨把網(wǎng)線拔了等等，然后什么是容忍性（tolerance），這個(gè)就很好理解了，是不是發(fā)生分區(qū)了我的服務(wù)就不再提供服務(wù)了呢，當(dāng)然不是，否則也就沒(méi)有高可用一說(shuō)了，那么我們能否說(shuō)不做網(wǎng)絡(luò)故障可能發(fā)生的假設(shè)呢，答案必然是不能的，首先網(wǎng)絡(luò)延遲是必然的，網(wǎng)絡(luò)延遲的過(guò)程中也可以將其當(dāng)做發(fā)生分區(qū)，另外網(wǎng)絡(luò)故障也可以說(shuō)是必然的。
在所有分布式系統(tǒng)中 P 幾乎都是不可拋棄的，所以說(shuō)我們的選擇也就只剩兩個(gè)了 AP 和 CP。（兩項(xiàng)）
如何理解 CP 與 AP
舉個(gè)簡(jiǎn)單例子，若我們集群有兩臺(tái)機(jī)器，而兩臺(tái)機(jī)器網(wǎng)絡(luò)發(fā)生中斷而導(dǎo)致出現(xiàn)分區(qū):
如果我們?cè)陔p發(fā)無(wú)法通信的情況下繼續(xù)允許兩邊進(jìn)行寫入，則必然造成數(shù)據(jù)的不一致，這時(shí)我們實(shí)現(xiàn)了 AP 而拋棄了C。
但如果我們禁止其中一方進(jìn)行寫入，這樣就可以保證系統(tǒng)的一致性了，但我們卻因?yàn)閷⒁恢幸粋€(gè)副本置為不可用而導(dǎo)致了A屬性的喪失，也是說(shuō)實(shí)現(xiàn)了 CP。
至此分布式和一致性的背景知識(shí)就介紹完畢（摘抄自網(wǎng)絡(luò)），篇幅問(wèn)題就不展開(kāi)聊了，下面進(jìn)入正題。
Raft 算法
分布式一致性是分布式系統(tǒng)中最基本的問(wèn)題,用來(lái)保證分布式系統(tǒng)的高可靠。解決分布式環(huán)境下一致性的問(wèn)題不得不提 Paxos 算法，但由于 Paxos 算法過(guò)于晦澀難懂且難以實(shí)現(xiàn)，Diego Ongaro 提出了一種更易于理解和實(shí)現(xiàn)并能等價(jià)于 Paxos 算法的共識(shí)算法 —— Raft 算法。
因?yàn)?Raft 算法清晰易懂越來(lái)越多的開(kāi)源項(xiàng)目嘗試引入 Raft 算法來(lái)解決分布式一致性問(wèn)題。在分布式存儲(chǔ)領(lǐng)域基于 Raft 算法構(gòu)建的項(xiàng)目百花齊放，欣欣向榮。
所以學(xué)會(huì) Raft 算法對(duì)于理解很多支持分布式的開(kāi)源項(xiàng)目有很大的幫助，分布式協(xié)議和算法這塊也是后端程序員進(jìn)階必須掌握的知識(shí)，所以一起變強(qiáng)吧！
介紹 Raft 算法的文章早已是汗牛充棟，本文先介紹兩個(gè)非常優(yōu)秀的網(wǎng)站：
The Secret Lives of Data-CN 以圖文方式介紹 Raft 算法，是非常好的入門材料。將其閱讀完后您大概率已經(jīng)了解了 Raft 算法，如果您仍有疑問(wèn)可以回來(lái)繼續(xù)閱讀本文。
https://acehi.github.io/thesecretlivesofdata-cn/raft/
Raft Scope 是 Raft 官方提供的互動(dòng)式演示程序，它展示了 Raft 集群的工作狀態(tài)。您可以用它模擬節(jié)點(diǎn)宕機(jī)、心跳超時(shí)等各種情況。有了 Raft Scope 我們可以親自“動(dòng)手” 觀察 Raft 集群是如何工作、如何處理各種故障的。
https://raft.github.io/raftscope/index.html
遺憾的是這個(gè)程序幾乎沒(méi)有任何說(shuō)明非常難以上手。本文接下來(lái)將先介紹如何使用 Raft Scope 然后用它模擬幾種 Raft 集群工作中會(huì)遭遇的典型狀況。
下面就一起通過(guò) Raft Scope 的動(dòng)畫(huà)來(lái)學(xué)習(xí) Raft 算法吧！
Raft Scope 說(shuō)明
可以看到 Raft Scope 界面由三部分組成。
最下方有兩個(gè)滑塊：上面的是進(jìn)度條您可以拖動(dòng)它回看剛剛發(fā)生過(guò)事件，下面的是變速器滑塊越靠左系統(tǒng)運(yùn)行越慢。
左上角部分是一個(gè)由 5 個(gè)節(jié)點(diǎn)組成的 Raft 集群，每個(gè)圓圈代表集群中的一個(gè)節(jié)點(diǎn)。點(diǎn)擊節(jié)點(diǎn)可以看到它的狀態(tài)。對(duì)話框的右下角有一些按鈕，我們可以點(diǎn)擊按鈕模擬各種狀況。我們直接右鍵點(diǎn)擊節(jié)點(diǎn)也可以看到這些按鈕
這些按鈕的功能是:
stop: 節(jié)點(diǎn)停機(jī) resume: 啟動(dòng)停機(jī)的節(jié)點(diǎn) restart: 將節(jié)點(diǎn)立即重啟 time out: 模擬心跳超時(shí)，點(diǎn)擊按鈕后相應(yīng)節(jié)點(diǎn)會(huì)認(rèn)為 Leader 發(fā)生了心跳超時(shí)。 request: 向集群提交新的數(shù)據(jù)
節(jié)點(diǎn)中間的數(shù)字是節(jié)點(diǎn)當(dāng)前的任期號(hào)(Term), 節(jié)點(diǎn)的顏色似乎同樣是用來(lái)表示任期的。節(jié)點(diǎn)可能處于 Follower、Candidate 或者 Leader 狀態(tài)。
S2 處于 Candidate 狀態(tài)，實(shí)心原點(diǎn)表示它現(xiàn)在收到的投票。圖中的兩個(gè)原點(diǎn)表示收到了 S2 和 S4 的投票，這 5 個(gè)小圓點(diǎn)和集群中節(jié)點(diǎn)的位置是對(duì)應(yīng)的，左下角的小圓點(diǎn)表示 S4, 最上面的小圓點(diǎn)表示 S1。在集群選舉過(guò)程中節(jié)點(diǎn)外的動(dòng)態(tài)邊框表示 Election Timeout。
黑色實(shí)心邊框表示 S5 是 Leader。Follower 外面的邊框表示 HeartBeat 超時(shí)倒計(jì)時(shí)。
右上角的表格表示各節(jié)點(diǎn)的日志，每行表示一個(gè)節(jié)點(diǎn)。
表格最上面的數(shù)字是日志的序號(hào)(Log Index)。Log Index 是一個(gè)自增且連續(xù)的 ID，它可以作為一條日志唯一標(biāo)識(shí)。節(jié)點(diǎn)中最大的 Log Index 也反映了這個(gè)節(jié)點(diǎn)的狀態(tài)機(jī)是否與集群一致。
表格里的單元格表示日志項(xiàng)(Entry)，其中的數(shù)字表示提交日志的任期(Term)。虛線框表示日志尚未提交，實(shí)線框表示日志已經(jīng)提交。
我們可以點(diǎn)擊 leader 節(jié)點(diǎn)的 request 按鈕來(lái)查看向 Raft 集群提交數(shù)據(jù)的過(guò)程。
Leader 選舉
Raft Scope 啟動(dòng)后會(huì)立即進(jìn)行第一次 Leader 選舉，在集群運(yùn)行過(guò)程任何一個(gè) Follower 出現(xiàn)心跳超時(shí)都會(huì)引發(fā)新一輪選舉。
我們可以點(diǎn)擊任意一個(gè) Follower 的 time out 按鈕模擬心跳超時(shí)，隨后此 Follower 會(huì)發(fā)起新一輪選舉。
或者我們可以點(diǎn)擊 Leader 的 stop、restart 來(lái)模擬 Leader 宕機(jī)或者重啟，并觀察隨后的集群選舉過(guò)程。
比較奇怪的是，Raft Scope 中的 Leader 節(jié)點(diǎn)也可以通過(guò)點(diǎn)擊 time out 來(lái)模擬心跳超時(shí)，在實(shí)際的 Raft 集群中 Leader 節(jié)點(diǎn)通常不會(huì)對(duì)自己進(jìn)行心跳檢測(cè)。
Leader 選舉的更多介紹可以查看：Leader選舉。不過(guò) The Secret Lives of Data 有兩處說(shuō)的可能不太清楚：
這里的選舉超時(shí)是指新一輪選舉開(kāi)始時(shí)，每個(gè)節(jié)點(diǎn)隨機(jī)思考要不要競(jìng)選 Leader 的時(shí)間，這個(gè)時(shí)間一般100-到200ms，非常短。
Candidate 發(fā)起選舉時(shí)會(huì)將自身任期(Term)+1并向其它所有節(jié)點(diǎn)發(fā)出 RequestVote 消息，這條消息中包含新任期和 Candidate 節(jié)點(diǎn)的最新 Log Index
收到 RequestVote 的節(jié)點(diǎn)會(huì)進(jìn)行判斷:
def onRequestVote(self, request_vote)
if request_vote.term <= self.term:
# 若 RequestVote 中的任期小于或等于(<=)當(dāng)前任期
# 則繼續(xù) Follow 當(dāng)前 Leader 并拒絕給 RequestVote投票
return False
if request_vote.log_index < self.log_index:
# 若 request_vote 發(fā)送者的 log_index 不如自己新，節(jié)點(diǎn)也會(huì)拒絕給發(fā)送者投票
# 這種機(jī)制確保了已經(jīng)提交到集群中的日志不會(huì)丟失，即保證 Raft 算法的安全性
return False
if self.voted_for is None:
# 若在本 term 中當(dāng)前節(jié)點(diǎn)還未投票，則給 request_vote 的發(fā)送者投票
self.voted_for = request_vote.sender
return True
else:
return False
Follower 超時(shí)
現(xiàn)在我們研究一下 The Secret Lives of Data 沒(méi)有詳細(xì)說(shuō)明的 Follower 超時(shí)處理過(guò)程。
我們可以點(diǎn)擊任意一個(gè) Follower 的 time out 按鈕模擬心跳超時(shí)，隨后此 Follower 會(huì)發(fā)起新一輪選舉。
根據(jù)上文中的 onRequestVote 邏輯，超時(shí)的 Follower 的 Log Index 是否與集群中的大多數(shù)節(jié)點(diǎn)相同決定了這次選舉的不同結(jié)果。
首先來(lái)看超時(shí) Follower 的 Log Index 與集群中大多數(shù)相同的情況：
現(xiàn)在我們點(diǎn)擊 S5 的 time out 按鈕，隨后我們看到 S5 發(fā)起了一輪投票。因?yàn)?5 個(gè)節(jié)點(diǎn)的 Log Index 是一致的, 所以包含原 Leader 在內(nèi)的大多數(shù)節(jié)點(diǎn)都投票給了 S5。
現(xiàn)在 S5 成為了新一任 Leader.
接下來(lái)我們看另外一種情況。S5 由于網(wǎng)絡(luò)問(wèn)題沒(méi)有收到帶有 Log Entry 1 的心跳包并導(dǎo)致心跳超時(shí)，S5 隨后會(huì)發(fā)起一次投票:
由于 S5 的 Log Index 比較小其它節(jié)點(diǎn)拒絕投票給他，集群 Leader 和任期不變：
日志復(fù)制
日志復(fù)制的介紹您可以查看：日志復(fù)制
現(xiàn)在我們進(jìn)一步探究日志復(fù)制的過(guò)程:
客戶端將更改提交給 Leader, Leader 會(huì)在自己的日志中寫入一條未提交的記錄(Entry) 在下一次心跳時(shí) Leader 會(huì)將更改發(fā)送給所有 Follower 一旦收到過(guò)半節(jié)點(diǎn)的確認(rèn) Leader 就會(huì)提交自己日志中的記錄4 并向客戶端返回寫入成功 Leader 會(huì)在下一次心跳時(shí)通知所有節(jié)點(diǎn)提交日志
這里比較復(fù)雜的情況是在第 4 步完成之后 Leader 崩潰。由于此時(shí)客戶端已經(jīng)收到了寫入成功的回復(fù)，所以在選出新的 Leader 之后要繼續(xù)完成提交。
在 Leader 提交了自己的日志后我們立即關(guān)掉 Leader:
隨后集群發(fā)起了一次選舉，S3 成為新任 Leader:
可能是因?yàn)?Raft Scope 存在 Bug, S3 本應(yīng)該當(dāng)選后立即完成提交工作。但是實(shí)際上需要我們?cè)僖淮?Request 之后，日志1 和日志 2 才會(huì)被一起提交。
腦裂問(wèn)題
在 Leader 崩潰時(shí)可能會(huì)有多個(gè)節(jié)點(diǎn)近乎同時(shí)發(fā)現(xiàn)心跳超時(shí)并轉(zhuǎn)變?yōu)?Candidate 開(kāi)始選舉：
其它節(jié)點(diǎn)投票情況多種多樣，但只要保證獲只有得到過(guò)半投票的候選人才能成為 Leader。那么選舉結(jié)果只有兩種可能：
有且只有一個(gè)候選人獲得過(guò)半投票成為 Leader 并開(kāi)始新的任期 沒(méi)有一個(gè)候選人獲得過(guò)半投票，沒(méi)有選出 Leader 進(jìn)入下一輪投票
絕對(duì)不會(huì)選出多個(gè) Leader
網(wǎng)絡(luò)分區(qū)問(wèn)題
Raft 甚至可以在網(wǎng)絡(luò)分區(qū)的情況下正常工作：
在發(fā)生網(wǎng)絡(luò)分區(qū)后可能存在 3 種情況:
任意分區(qū)中的節(jié)點(diǎn)數(shù)都不超過(guò)一半：這種情況只有集群被分成 3 個(gè)或更多分區(qū)時(shí)才會(huì)出現(xiàn)，十分罕見(jiàn)。因?yàn)?Leader 選舉和 Commit Log 都需要超過(guò)一半節(jié)點(diǎn)確認(rèn)才可以進(jìn)行，在這種情況下 Raft 集群不能正常工作。
leader 所在的分區(qū)有超過(guò)一半的節(jié)點(diǎn)：這種情況視作其它分區(qū)中的 Follower 宕機(jī)，系統(tǒng)仍然可以繼續(xù)工作。在分區(qū)修復(fù)后，F(xiàn)ollower 節(jié)點(diǎn)會(huì)重新與 Leader 同步。
leader 所在分區(qū)中節(jié)點(diǎn)數(shù)不超過(guò)一半，但存在節(jié)點(diǎn)數(shù)超過(guò)一半的分區(qū)。這種情況最為復(fù)雜:
C、D、E 所在的分區(qū)節(jié)點(diǎn)數(shù)超過(guò)一半且與原來(lái)的 Leader 無(wú)法通信，隨后 C、D、E 在心跳超時(shí)后會(huì)發(fā)起新一輪投票選出新的 Leader 并恢復(fù)工作。
原領(lǐng)導(dǎo)者 Node B 仍然會(huì)認(rèn)為自己是集群的 Leader，但是由于只能與兩個(gè)節(jié)點(diǎn)通信(包括自己)無(wú)法得到過(guò)半節(jié)點(diǎn)同意，所以無(wú)法完成日志提交。
在分區(qū)修復(fù)后 Node B 會(huì)收到 Node C 的心跳并發(fā)現(xiàn)對(duì)方的任期（Term）比自己高，Node B 會(huì)放棄 Leader 身份轉(zhuǎn)為 Node C 的 Follower 與它保持同步。
總結(jié)
經(jīng)過(guò)本文探討我們可以總結(jié)一下 Raft 的一些特性:
只要集群中有超過(guò)一半的節(jié)點(diǎn)可以正常工作，集群就可以工作 只要寫入成功的數(shù)據(jù)就不會(huì)再丟失 任意節(jié)點(diǎn)上保存的狀態(tài)可能會(huì)落后于集群共識(shí)但是永遠(yuǎn)不會(huì)出現(xiàn)錯(cuò)誤的提交。只要系統(tǒng)仍然在正常工作，節(jié)點(diǎn)上的狀態(tài)一定會(huì)在某個(gè)時(shí)間后與系統(tǒng)共識(shí)達(dá)成同步，即保證最終一致性 只要在某個(gè)節(jié)點(diǎn)上讀到了某個(gè)變更, 在此之后這個(gè)節(jié)點(diǎn)上永遠(yuǎn)可以讀到該變更，即保證單調(diào)一致性
興趣是最好的老師，HelloGitHub 發(fā)現(xiàn)編程的樂(lè)趣