一、Raft 概述

??Raft 算法???是分布式系統(tǒng)開發(fā)首選的??共識(shí)算法??。比如現(xiàn)在流行 Etcd、Consul。

如果??掌握???了這個(gè)算法，就可以較容易地處理絕大部分場景的??容錯(cuò)???和??一致性??需求。比如分布式配置系統(tǒng)、分布式 NoSQL 存儲(chǔ)等等，輕松突破系統(tǒng)的單機(jī)限制。

Raft 算法是通過一切以領(lǐng)導(dǎo)者為準(zhǔn)的方式，實(shí)現(xiàn)一系列值的共識(shí)和各節(jié)點(diǎn)日志的一致。

二、Raft 角色

2.1 角色

跟隨者（Follower）：??普通群眾??，默默接收和來自領(lǐng)導(dǎo)者的消息，當(dāng)領(lǐng)導(dǎo)者心跳信息超時(shí)的時(shí)候，就主動(dòng)站出來，推薦自己當(dāng)候選人。

候選人（Candidate）：??候選人??將向其他節(jié)點(diǎn)請(qǐng)求投票 RPC 消息，通知其他節(jié)點(diǎn)來投票，如果贏得了大多數(shù)投票選票，就晉升當(dāng)領(lǐng)導(dǎo)者。

領(lǐng)導(dǎo)者（Leader）：??霸道總裁??，一切以我為準(zhǔn)。處理寫請(qǐng)求、管理日志復(fù)制和不斷地發(fā)送心跳信息，通知其他節(jié)點(diǎn)“我是領(lǐng)導(dǎo)者，我還活著，你們不要”發(fā)起新的選舉，不用找新領(lǐng)導(dǎo)來替代我。

如下圖所示，分別用三種圖代表跟隨者、候選人和領(lǐng)導(dǎo)者。

角色

三、單節(jié)點(diǎn)系統(tǒng)

3.1 數(shù)據(jù)庫服務(wù)器

現(xiàn)在我們想象一下，有一個(gè)單節(jié)點(diǎn)系統(tǒng)，這個(gè)節(jié)點(diǎn)作為數(shù)據(jù)庫服務(wù)器，且存儲(chǔ)了一個(gè)值為 X。

數(shù)據(jù)庫服務(wù)器

3.2 客戶端

左邊綠色的實(shí)心圈就是客戶端，右邊的藍(lán)色實(shí)心圈就是節(jié)點(diǎn) a（Node a）。Term 代表任期，后面會(huì)講到。

客戶端

3.3 客戶端向服務(wù)器發(fā)送數(shù)據(jù)

客戶端向單節(jié)點(diǎn)服務(wù)器發(fā)送了一條更新操作，設(shè)置數(shù)據(jù)庫中存的值為 8。單機(jī)環(huán)境下（單個(gè)服務(wù)器節(jié)點(diǎn)），客戶端從服務(wù)器拿到的值也是 8。一致性非常容易保證。

客戶端向服務(wù)器發(fā)送數(shù)據(jù)

3.4 多節(jié)點(diǎn)如何保證一致性？

但如果有多個(gè)服務(wù)器節(jié)點(diǎn)，怎么保證一致性呢？比如有三個(gè)節(jié)點(diǎn)：a，b，c。如下圖所示。這三個(gè)節(jié)點(diǎn)組成一個(gè)數(shù)據(jù)庫集群。客戶端對(duì)這三個(gè)節(jié)點(diǎn)進(jìn)行更新操作，如何保證三個(gè)節(jié)點(diǎn)中存的值一致？這個(gè)就是分布式一致性問題。Raft 算法就是來解決這個(gè)問題的。當(dāng)然還有其他協(xié)議也可以保證，本篇只針對(duì) Raft 算法。

在多節(jié)點(diǎn)集群中，在節(jié)點(diǎn)故障、分區(qū)錯(cuò)誤等異常情況下，Raft 算法如何保證在同一個(gè)時(shí)間，集群中只有一個(gè)領(lǐng)導(dǎo)者呢？下面就開始講解 Raft 算法選舉領(lǐng)導(dǎo)者的過程。

四、選舉領(lǐng)導(dǎo)過程

4.1 初始狀態(tài)

初始狀態(tài)下，集群中所有節(jié)點(diǎn)都是跟隨者的狀態(tài)。

如下圖所示，有三個(gè)節(jié)點(diǎn)(Node) a、b、c，任期（Term）都為 0。

初始狀態(tài)

4.2 成為候選者

Raft 算法實(shí)現(xiàn)了隨機(jī)超時(shí)時(shí)間的特性，每個(gè)節(jié)點(diǎn)等待領(lǐng)導(dǎo)者節(jié)點(diǎn)心跳信息的超時(shí)時(shí)間間隔是隨機(jī)的。比如 A 節(jié)點(diǎn)等待超時(shí)的時(shí)間間隔 150 ms，B 節(jié)點(diǎn) 200 ms，C 節(jié)點(diǎn) 300 ms。那么 a 先超時(shí)，最先因?yàn)闆]有等到領(lǐng)導(dǎo)者的心跳信息，發(fā)生超時(shí)。如下圖所示，三個(gè)節(jié)點(diǎn)的超時(shí)計(jì)時(shí)器開始運(yùn)行。

超時(shí)時(shí)間

當(dāng) A 節(jié)點(diǎn)的超時(shí)時(shí)間到了后，A 節(jié)點(diǎn)成為候選者，并增加自己的任期編號(hào)，Term 值從 0 更新為 1，并給自己投了一票。

• Node A：Term = 1, Vote Count = 1。
• Node B：Term = 0。
• Node C：Term = 0。

成為候選者

4.3 投票

我們來看下候選者如何成為領(lǐng)導(dǎo)者的。

Leader 選舉

• 第一步：節(jié)點(diǎn) A 成為候選者后，向其他節(jié)點(diǎn)發(fā)送請(qǐng)求投票 RPC 信息，請(qǐng)它們選舉自己為領(lǐng)導(dǎo)者。
• 第二步：節(jié)點(diǎn) B 和 節(jié)點(diǎn) C 接收到節(jié)點(diǎn) A 發(fā)送的請(qǐng)求投票信息后，在編號(hào)為 1 的這屆任期內(nèi)，還沒有進(jìn)行過投票，就把選票投給節(jié)點(diǎn) A，并增加自己的任期編號(hào)。
• 第三步：節(jié)點(diǎn) A 收到 3 次投票，得到了大多數(shù)節(jié)點(diǎn)的投票，從候選者成為本屆任期內(nèi)的新的領(lǐng)導(dǎo)者。
• 第四步：節(jié)點(diǎn) A 作為領(lǐng)導(dǎo)者，固定的時(shí)間間隔給 節(jié)點(diǎn) B 和節(jié)點(diǎn) C 發(fā)送心跳信息，告訴節(jié)點(diǎn) B 和 C，我是領(lǐng)導(dǎo)者，組織其他跟隨者發(fā)起新的選舉。
• 第五步：節(jié)點(diǎn) B 和節(jié)點(diǎn) C 發(fā)送響應(yīng)信息給節(jié)點(diǎn) A，告訴節(jié)點(diǎn) A 我是正常的。

4.4 任期

英文單詞是 term，領(lǐng)導(dǎo)者是有任期的。

• 自動(dòng)增加：跟隨者在等待領(lǐng)導(dǎo)者心跳信息超時(shí)后，推薦自己為候選人，會(huì)增加自己的任期號(hào)，如上圖所示，節(jié)點(diǎn) A 任期為 0，推舉自己為候選人時(shí)，任期編號(hào)增加為 1。
• 更新為較大值：當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)自己的任期編號(hào)比其他節(jié)點(diǎn)小時(shí)，會(huì)更新到較大的編號(hào)值。比如節(jié)點(diǎn) A 的任期為 1，請(qǐng)求投票，投票消息中包含了節(jié)點(diǎn) A 的任期編號(hào)，且編號(hào)為 1，節(jié)點(diǎn) B 收到消息后，會(huì)將自己的任期編號(hào)更新為 1。
• 恢復(fù)為跟隨者：如果一個(gè)候選人或者領(lǐng)導(dǎo)者，發(fā)現(xiàn)自己的任期編號(hào)比其他節(jié)點(diǎn)小，那么它會(huì)立即恢復(fù)成跟隨者狀態(tài)。這種場景出現(xiàn)在分區(qū)錯(cuò)誤恢復(fù)后，任期為 3 的領(lǐng)導(dǎo)者受到任期編號(hào)為 4 的心跳消息，那么前者將立即恢復(fù)成跟隨者狀態(tài)。
• 拒絕消息：如果一個(gè)節(jié)點(diǎn)接收到較小的任期編號(hào)值的請(qǐng)求，那么它會(huì)直接拒絕這個(gè)請(qǐng)求，比如任期編號(hào)為 6 的節(jié)點(diǎn) A，收到任期編號(hào)為 5 的節(jié)點(diǎn) B 的請(qǐng)求投票 RPC 消息，那么節(jié)點(diǎn) A 會(huì)拒絕這個(gè)消息。

4.5 選舉規(guī)則

• 一個(gè)任期內(nèi)，領(lǐng)導(dǎo)者一直都會(huì)領(lǐng)導(dǎo)者，直到自身出現(xiàn)問題（如宕機(jī)），或者網(wǎng)絡(luò)問題（延遲），其他節(jié)點(diǎn)發(fā)起一輪新的選舉。
• 在一次選舉中，每一個(gè)服務(wù)器節(jié)點(diǎn)最多會(huì)對(duì)一個(gè)任期編號(hào)投出一張選票，投完了就沒了。

4.6 大多數(shù)

假設(shè)一個(gè)集群由 N 個(gè)節(jié)點(diǎn)組成，那么大多數(shù)就是至少 N/2+1。例如：3 個(gè)節(jié)點(diǎn)的集群，大多數(shù)就是 2。

4.7 心跳超時(shí)

為了防止多個(gè)節(jié)點(diǎn)同時(shí)發(fā)起投票，會(huì)給每個(gè)節(jié)點(diǎn)分配一個(gè)隨機(jī)的選舉超時(shí)時(shí)間。這個(gè)時(shí)間內(nèi)，節(jié)點(diǎn)不能成為候選者，只能等到超時(shí)。比如上述例子，節(jié)點(diǎn) A 先超時(shí)，先成為了候選者。這種巧妙的設(shè)計(jì)，在大多數(shù)情況下只有一個(gè)服務(wù)器節(jié)點(diǎn)先發(fā)起選舉，而不是同時(shí)發(fā)起選舉，減少了因選票瓜分導(dǎo)致選舉失敗的情況。

成為候選者

五、領(lǐng)導(dǎo)者故障

如果領(lǐng)導(dǎo)者節(jié)點(diǎn)出現(xiàn)故障，則會(huì)觸發(fā)新的一輪選舉。如下圖所示，領(lǐng)導(dǎo)者節(jié)點(diǎn) A 發(fā)生故障，節(jié)點(diǎn) B 和 節(jié)點(diǎn) C 就會(huì)重新選舉 Leader。

領(lǐng)導(dǎo)者故障

• 第一步 ：節(jié)點(diǎn) A 發(fā)生故障，節(jié)點(diǎn) B 和節(jié)點(diǎn) C 沒有收到領(lǐng)導(dǎo)者節(jié)點(diǎn) A 的心跳信息，等待超時(shí)。
• 第二步：節(jié)點(diǎn) C 先發(fā)生超時(shí)，節(jié)點(diǎn) C 成為候選人。
• 第三步：節(jié)點(diǎn) C 向節(jié)點(diǎn) A 和節(jié)點(diǎn) B 發(fā)起請(qǐng)求投票信息。
• 第四步：節(jié)點(diǎn) C 響應(yīng)投票，將票投給了 C，而節(jié)點(diǎn) A 因?yàn)榘l(fā)生故障了，無法響應(yīng) C 的投票請(qǐng)求。
• 第五步：節(jié)點(diǎn) C 收到兩票（大多數(shù)票數(shù)），成為領(lǐng)導(dǎo)者。
• 第六步：節(jié)點(diǎn) C 向節(jié)點(diǎn) A 和 B 發(fā)送心跳信息，節(jié)點(diǎn) B 響應(yīng)心跳信息，節(jié)點(diǎn) A 不響應(yīng)心跳信息，因?yàn)?A 故障了。

總結(jié)

Raft 算法通過以下幾種方式來進(jìn)行領(lǐng)導(dǎo)選舉，保證了一個(gè)任期只有一位領(lǐng)導(dǎo)，極大減少了選舉失敗的情況。

• 任期
• 領(lǐng)導(dǎo)者心跳信息
• 隨機(jī)選舉超時(shí)時(shí)間
• 先來先服務(wù)的投票原則
• 大多數(shù)選票原則

本篇通過動(dòng)圖的方式來講解 Raft 算法如何選舉領(lǐng)導(dǎo)者，更容易理解和消化。