一、Raft 概述
Raft 算法是分布式系統開發首選的共識算法。比如現在流行 Etcd、Consul。
如果掌握了這個算法，就可以較容易地處理絕大部分場景的容錯和一緻性需求。比如分布式配置系統、分布式 NoSQL 存儲等等，輕松突破系統的單機限制。
Raft 算法是通過一切以上司者為準的方式，實作一系列值的共識和各節點日志的一緻。
二、Raft 角色
2.1 角色
跟随者（Follower）：普通群衆，默默接收和來自上司者的消息，當上司者心跳資訊逾時的時候，就主動站出來，推薦自己當候選人。
候選人（Candidate）：候選人将向其他節點請求投票 RPC 消息，通知其他節點來投票，如果赢得了大多數投票選票，就晉升當上司者。
上司者（Leader）：霸道總裁，一切以我為準。處理寫請求、管理日志複制和不斷地發送心跳資訊，通知其他節點“我是上司者，我還活着，你們不要”發起新的選舉，不用找新上司來替代我。
如下圖所示，分别用三種圖代表跟随者、候選人和上司者。
角色
三、單節點系統
3.1 資料庫伺服器
現在我們想象一下，有一個單節點系統，這個節點作為資料庫伺服器，且存儲了一個值為 X。
資料庫伺服器
3.2 用戶端
左邊綠色的實心圈就是用戶端，右邊的藍色實心圈就是節點 a（Node a）。Term 代表任期，後面會講到。
用戶端
3.3 用戶端向伺服器發送資料
用戶端向單節點伺服器發送了一條更新操作，設定資料庫中存的值為 8。單機環境下（單個伺服器節點），用戶端從伺服器拿到的值也是 8。一緻性非常容易保證。
用戶端向伺服器發送資料
3.4 多節點如何保證一緻性？
但如果有多個伺服器節點，怎麼保證一緻性呢？比如有三個節點：a，b，c。如下圖所示。這三個節點組成一個資料庫叢集。用戶端對這三個節點進行更新操作，如何保證三個節點中存的值一緻？這個就是分布式一緻性問題。Raft 算法就是來解決這個問題的。當然還有其他協定也可以保證，本篇隻針對 Raft 算法。
在多節點叢集中，在節點故障、分區錯誤等異常情況下，Raft 算法如何保證在同一個時間，叢集中隻有一個上司者呢？下面就開始講解 Raft 算法選舉上司者的過程。
四、選舉上司過程
4.1 初始狀态
初始狀态下，叢集中所有節點都是跟随者的狀态。
如下圖所示，有三個節點(Node) a、b、c，任期（Term）都為 0。
初始狀态
4.2 成為候選者
Raft 算法實作了随機逾時時間的特性，每個節點等待上司者節點心跳資訊的逾時時間間隔是随機的。比如 A 節點等待逾時的時間間隔 150 ms，B 節點 200 ms，C 節點 300 ms。那麼 a 先逾時，最先因為沒有等到上司者的心跳資訊，發生逾時。如下圖所示，三個節點的逾時計時器開始運作。
逾時時間
當 A 節點的逾時時間到了後，A 節點成為候選者，并增加自己的任期編号，Term 值從 0 更新為 1，并給自己投了一票。
- Node A：Term = 1, Vote Count = 1。
- Node B：Term = 0。
- Node C：Term = 0。
成為候選者
4.3 投票
我們來看下候選者如何成為上司者的。
Leader 選舉
- 第一步：節點 A 成為候選者後，向其他節點發送請求投票 RPC 資訊，請它們選舉自己為上司者。
- 第二步：節點 B 和 節點 C 接收到節點 A 發送的請求投票資訊後，在編号為 1 的這屆任期内，還沒有進行過投票，就把選票投給節點 A，并增加自己的任期編号。
- 第三步：節點 A 收到 3 次投票，得到了大多數節點的投票，從候選者成為本屆任期内的新的上司者。
- 第四步：節點 A 作為上司者，固定的時間間隔給 節點 B 和節點 C 發送心跳資訊，告訴節點 B 和 C，我是上司者，組織其他跟随者發起新的選舉。
- 第五步：節點 B 和節點 C 發送響應資訊給節點 A，告訴節點 A 我是正常的。
4.4 任期
英文單詞是 term，上司者是有任期的。
- 自動增加：跟随者在等待上司者心跳資訊逾時後，推薦自己為候選人，會增加自己的任期号，如上圖所示，節點 A 任期為 0，推舉自己為候選人時，任期編号增加為 1。
- 更新為較大值：當節點發現自己的任期編号比其他節點小時，會更新到較大的編号值。比如節點 A 的任期為 1，請求投票，投票消息中包含了節點 A 的任期編号，且編号為 1，節點 B 收到消息後，會将自己的任期編号更新為 1。
- 恢複為跟随者：如果一個候選人或者上司者，發現自己的任期編号比其他節點小，那麼它會立即恢複成跟随者狀态。這種場景出現在分區錯誤恢複後，任期為 3 的上司者受到任期編号為 4 的心跳消息，那麼前者将立即恢複成跟随者狀态。
- 拒絕消息：如果一個節點接收到較小的任期編号值的請求，那麼它會直接拒絕這個請求，比如任期編号為 6 的節點 A，收到任期編号為 5 的節點 B 的請求投票 RPC 消息，那麼節點 A 會拒絕這個消息。
4.5 選舉規則
- 一個任期内，上司者一直都會上司者，直到自身出現問題（如當機），或者網絡問題（延遲），其他節點發起一輪新的選舉。
- 在一次選舉中，每一個伺服器節點最多會對一個任期編号投出一張選票，投完了就沒了。
4.6 大多數
假設一個叢集由 N 個節點組成，那麼大多數就是至少 N/2+1。例如：3 個節點的叢集，大多數就是 2。
4.7 心跳逾時
為了防止多個節點同時發起投票，會給每個節點配置設定一個随機的選舉逾時時間。這個時間内，節點不能成為候選者，隻能等到逾時。比如上述例子，節點 A 先逾時，先成為了候選者。這種巧妙的設計，在大多數情況下隻有一個伺服器節點先發起選舉，而不是同時發起選舉，減少了因選票瓜分導緻選舉失敗的情況。
成為候選者
五、上司者故障
如果上司者節點出現故障，則會觸發新的一輪選舉。如下圖所示，上司者節點 A 發生故障，節點 B 和 節點 C 就會重新選舉 Leader。
上司者故障
- 第一步 ：節點 A 發生故障，節點 B 和節點 C 沒有收到上司者節點 A 的心跳資訊，等待逾時。
- 第二步：節點 C 先發生逾時，節點 C 成為候選人。
- 第三步：節點 C 向節點 A 和節點 B 發起請求投票資訊。
- 第四步：節點 C 響應投票，将票投給了 C，而節點 A 因為發生故障了，無法響應 C 的投票請求。
- 第五步：節點 C 收到兩票（大多數票數），成為上司者。
- 第六步：節點 C 向節點 A 和 B 發送心跳資訊，節點 B 響應心跳資訊，節點 A 不響應心跳資訊，因為 A 故障了。
總結
Raft 算法通過以下幾種方式來進行上司選舉，保證了一個任期隻有一位上司，極大減少了選舉失敗的情況。
- 任期
- 上司者心跳資訊
- 随機選舉逾時時間
- 先來先服務的投票原則
- 大多數選票原則
本篇通過動圖的方式來講解 Raft 算法如何選舉上司者，更容易了解和消化。
原文連結：https://mp.weixin.qq.com/s/HMS4VWqApi3n8J5Kddqv4g