拜占庭將軍問題是分布式領(lǐng)域最復(fù)雜、最嚴(yán)格的容錯(cuò)模型。但在日常工作中使用的分布式系統(tǒng)面對(duì)的問題不會(huì)那么復(fù)雜，更多的是計(jì)算機(jī)故障掛掉了，或者網(wǎng)絡(luò)通信問題而沒法傳遞信息，這種情況不考慮計(jì)算機(jī)之間互相發(fā)送惡意信息，極大簡(jiǎn)化了系統(tǒng)對(duì)容錯(cuò)的要求，最主要的是達(dá)到一致性。

所以將拜占庭將軍問題根據(jù)常見的工作上的問題進(jìn)行簡(jiǎn)化：假設(shè)將軍中沒有叛軍，信使的信息可靠但有可能被暗殺的情況下，將軍們?nèi)绾芜_(dá)成一致性決定？

對(duì)于這個(gè)簡(jiǎn)化后的問題，有許多解決方案，第一個(gè)被證明的共識(shí)算法是 Paxos，由拜占庭將軍問題的作者 Leslie Lamport 在1990年提出，最初以論文難懂而出名，后來這哥們?cè)?001重新發(fā)了一篇簡(jiǎn)單版的論文 Paxos Made Simple，然而還是挺難懂的。

因?yàn)?Paxos 難懂，難實(shí)現(xiàn)，所以斯坦福大學(xué)的教授在2014年發(fā)表了新的分布式協(xié)議 Raft。與 Paxos 相比，Raft 有著基本相同運(yùn)行效率，但是更容易理解，也更容易被用在系統(tǒng)開發(fā)上。

針對(duì)簡(jiǎn)化版拜占庭將軍問題，Raft 解決方案類比

我們還是用拜占庭將軍的例子來幫助理解 Raft。

假設(shè)將軍中沒有叛軍，信使的信息可靠但有可能被暗殺的情況下，將軍們?nèi)绾芜_(dá)成一致性決定？

Raft 的解決方案大概可以理解成先在所有將軍中選出一個(gè)大將軍，所有的決定由大將軍來做。選舉環(huán)節(jié)：比如說現(xiàn)在一共有3個(gè)將軍 A, B, C，每個(gè)將軍都有一個(gè)隨機(jī)時(shí)間的倒計(jì)時(shí)器，倒計(jì)時(shí)一結(jié)束，這個(gè)將軍就會(huì)把自己當(dāng)成大將軍候選人，然后派信使去問其他幾個(gè)將軍，能不能選我為總將軍？假設(shè)現(xiàn)在將軍A倒計(jì)時(shí)結(jié)束了，他派信使傳遞選舉投票的信息給將軍B和C，如果將軍B和C還沒把自己當(dāng)成候選人（倒計(jì)時(shí)還沒有結(jié)束），并且沒有把選舉票投給其他，他們把票投給將軍A，信使在回到將軍A時(shí)，將軍A知道自己收到了足夠的票數(shù)，成為了大將軍。在這之后，是否要進(jìn)攻就由大將軍決定，然后派信使去通知另外兩個(gè)將軍，如果在一段時(shí)間后還沒有收到回復(fù)（可能信使被暗殺），那就再重派一個(gè)信使，直到收到回復(fù)。

故事先講到這里，希望不做技術(shù)方面的朋友可以大概能理解 Raft 的原理，下面從比較技術(shù)的角度講講 Raft 的原理。

1. Raft 節(jié)點(diǎn)狀態(tài)

從拜占庭將軍的故事映射到分布式系統(tǒng)上，每個(gè)將軍相當(dāng)于一個(gè)分布式網(wǎng)絡(luò)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有三種狀態(tài)：Follower，Candidate，Leader，狀態(tài)之間是互相轉(zhuǎn)換的，可以參考下圖，具體的后面說。

每個(gè)節(jié)點(diǎn)上都有一個(gè)倒計(jì)時(shí)器 (Election Timeout)，時(shí)間隨機(jī)在 150ms 到 300ms 之間。有幾種情況會(huì)重設(shè) Timeout：

收到選舉的請(qǐng)求
收到 Leader 的 Heartbeat (后面會(huì)講到)

在 Raft 運(yùn)行過程中，最主要進(jìn)行兩個(gè)活動(dòng)：

選主 Leader Election
復(fù)制日志 Log Replication

2. 選主 Leader Election

2.1 正常情況下選主

假設(shè)現(xiàn)在有如圖5個(gè)節(jié)點(diǎn)，5個(gè)節(jié)點(diǎn)一開始的狀態(tài)都是 Follower。

在一個(gè)節(jié)點(diǎn)倒計(jì)時(shí)結(jié)束 (Timeout) 后，這個(gè)節(jié)點(diǎn)的狀態(tài)變成 Candidate 開始選舉，它給其他幾個(gè)節(jié)點(diǎn)發(fā)送選舉請(qǐng)求 (RequestVote)

其他四個(gè)節(jié)點(diǎn)都返回成功，這個(gè)節(jié)點(diǎn)的狀態(tài)由 Candidate 變成了 Leader，并在每個(gè)一小段時(shí)間后，就給所有的 Follower 發(fā)送一個(gè) Heartbeat 以保持所有節(jié)點(diǎn)的狀態(tài)，F(xiàn)ollower 收到 Leader 的 Heartbeat 后重設(shè) Timeout。

這是最簡(jiǎn)單的選主情況，只要有超過一半的節(jié)點(diǎn)投支持票了，Candidate 才會(huì)被選舉為 Leader，5個(gè)節(jié)點(diǎn)的情況下，3個(gè)節(jié)點(diǎn) (包括 Candidate 本身) 投了支持就行。

2.2 Leader 出故障情況下的選主

一開始已經(jīng)有一個(gè) Leader，所有節(jié)點(diǎn)正常運(yùn)行。

Leader 出故障掛掉了，其他四個(gè) Follower 將進(jìn)行重新選主。

4個(gè)節(jié)點(diǎn)的選主過程和5個(gè)節(jié)點(diǎn)的類似，在選出一個(gè)新的 Leader 后，原來的 Leader 恢復(fù)了又重新加入了，這個(gè)時(shí)候怎么處理？在 Raft 里，第幾輪選舉是有記錄的，重新加入的 Leader 是第一輪選舉 (Term 1) 選出來的，而現(xiàn)在的 Leader 則是 Term 2，所有原來的 Leader 會(huì)自覺降級(jí)為 Follower

2.3 多個(gè) Candidate 情況下的選主

假設(shè)一開始有4個(gè)節(jié)點(diǎn)，都還是 Follower。

有兩個(gè) Follower 同時(shí) Timeout，都變成了 Candidate 開始選舉，分別給一個(gè) Follower 發(fā)送了投票請(qǐng)求。

兩個(gè) Follower 分別返回了ok，這時(shí)兩個(gè) Candidate 都只有2票，要3票才能被選成 Leader。

兩個(gè) Candidate 會(huì)分別給另外一個(gè)還沒有給自己投票的 Follower 發(fā)送投票請(qǐng)求。

但是因?yàn)?Follower 在這一輪選舉中，都已經(jīng)投完票了，所以都拒絕了他們的請(qǐng)求。所以在 Term 2 沒有 Leader 被選出來。

這時(shí)，兩個(gè)節(jié)點(diǎn)的狀態(tài)是 Candidate，兩個(gè)是 Follower，但是他們的倒計(jì)時(shí)器仍然在運(yùn)行，最先 Timeout 的那個(gè)節(jié)點(diǎn)會(huì)進(jìn)行發(fā)起新一輪 Term 3 的投票。

兩個(gè) Follower 在 Term 3 還沒投過票，所以返回 OK，這時(shí) Candidate 一共有三票，被選為了 Leader。

如果 Leader Heartbeat 的時(shí)間晚于另外一個(gè) Candidate timeout 的時(shí)間，另外一個(gè) Candidate 仍然會(huì)發(fā)送選舉請(qǐng)求。

兩個(gè) Follower 已經(jīng)投完票了，拒絕了這個(gè) Candidate 的投票請(qǐng)求。

Leader 進(jìn)行 Heartbeat， Candidate 收到后狀態(tài)自動(dòng)轉(zhuǎn)為 Follower，完成選主。

以上是 Raft 最重要活動(dòng)之一選主的介紹，以及在不同情況下如何進(jìn)行選主。

3. 復(fù)制日志 Log Replication

3.1 正常情況下復(fù)制日志

Raft 在實(shí)際應(yīng)用場(chǎng)景中的一致性更多的是體現(xiàn)在不同節(jié)點(diǎn)之間的數(shù)據(jù)一致性，客戶端發(fā)送請(qǐng)求到任何一個(gè)節(jié)點(diǎn)都能收到一致的返回，當(dāng)一個(gè)節(jié)點(diǎn)出故障后，其他節(jié)點(diǎn)仍然能以已有的數(shù)據(jù)正常進(jìn)行。在選主之后的復(fù)制日志就是為了達(dá)到這個(gè)目的。

一開始，Leader 和兩個(gè) Follower 都沒有任何數(shù)據(jù)。

客戶端發(fā)送請(qǐng)求給 Leader，儲(chǔ)存數(shù)據(jù) “sally”，Leader 先將數(shù)據(jù)寫在本地日志，這時(shí)候數(shù)據(jù)還是 Uncommitted (還沒最終確認(rèn)，紅色表示)

Leader 給兩個(gè) Follower 發(fā)送 AppendEntries 請(qǐng)求，數(shù)據(jù)在 Follower 上沒有沖突，則將數(shù)據(jù)暫時(shí)寫在本地日志，F(xiàn)ollower 的數(shù)據(jù)也還是 Uncommitted。

Follower 將數(shù)據(jù)寫到本地后，返回 OK。Leader 收到后成功返回，只要收到的成功的返回?cái)?shù)量超過半數(shù) (包含Leader)，Leader 將數(shù)據(jù) “sally” 的狀態(tài)改成 Committed。( 這個(gè)時(shí)候 Leader 就可以返回給客戶端了)

Leader 再次給 Follower 發(fā)送 AppendEntries 請(qǐng)求，收到請(qǐng)求后，F(xiàn)ollower 將本地日志里 Uncommitted 數(shù)據(jù)改成 Committed。這樣就完成了一整個(gè)復(fù)制日志的過程，三個(gè)節(jié)點(diǎn)的數(shù)據(jù)是一致的

3.2 Network Partition 情況下進(jìn)行復(fù)制日志

在 Network Partition 的情況下，部分節(jié)點(diǎn)之間沒辦法互相通信，Raft 也能保證在這種情況下數(shù)據(jù)的一致性。

一開始有 5 個(gè)節(jié)點(diǎn)處于同一網(wǎng)絡(luò)狀態(tài)下。

Network Partition 將節(jié)點(diǎn)分成兩邊，一邊有兩個(gè)節(jié)點(diǎn)，一邊三個(gè)節(jié)點(diǎn)。

兩個(gè)節(jié)點(diǎn)這邊已經(jīng)有 Leader 了，來自客戶端的數(shù)據(jù) “bob” 通過 Leader 同步到 Follower。

因?yàn)橹挥袃蓚€(gè)節(jié)點(diǎn)，少于3個(gè)節(jié)點(diǎn)，所以 “bob” 的狀態(tài)仍是 Uncommitted。所以在這里，服務(wù)器會(huì)返回錯(cuò)誤給客戶端

另外一個(gè) Partition 有三個(gè)節(jié)點(diǎn)，進(jìn)行重新選主。客戶端數(shù)據(jù) “tom” 發(fā)到新的 Leader，通過和上節(jié)網(wǎng)絡(luò)狀態(tài)下相似的過程，同步到另外兩個(gè) Follower。

因?yàn)檫@個(gè) Partition 有3個(gè)節(jié)點(diǎn)，超過半數(shù)，所以數(shù)據(jù) “tom” 都 Commit 了。

網(wǎng)絡(luò)狀態(tài)恢復(fù)，5個(gè)節(jié)點(diǎn)再次處于同一個(gè)網(wǎng)絡(luò)狀態(tài)下。但是這里出現(xiàn)了數(shù)據(jù)沖突 “bob" 和 “tom"

三個(gè)節(jié)點(diǎn)的 Leader 廣播 AppendEntries

兩個(gè)節(jié)點(diǎn) Partition 的 Leader 自動(dòng)降級(jí)為 Follower，因?yàn)檫@個(gè) Partition 的數(shù)據(jù) “bob” 沒有 Commit，返回給客戶端的是錯(cuò)誤，客戶端知道請(qǐng)求沒有成功，所以 Follower 在收到 AppendEntries 請(qǐng)求時(shí)，可以把 “bob“ 刪除，然后同步 ”tom”，通過這么一個(gè)過程，就完成了在 Network Partition 情況下的復(fù)制日志，保證了數(shù)據(jù)的一致性。

小總結(jié)

Raft 是能夠?qū)崿F(xiàn)分布式系統(tǒng)強(qiáng)一致性的算法，每個(gè)系統(tǒng)節(jié)點(diǎn)有三種狀態(tài) Follower，Candidate，Leader。實(shí)現(xiàn) Raft 算法兩個(gè)最重要的事是：選主和復(fù)制日志

參考鏈接：
Raft 官網(wǎng)：https://raft.github.io/

Raft 原理動(dòng)畫 (推薦看看)：http://thesecretlivesofdata.com/raft/

Raft 算法解析圖片來源：http://www.infoq.com/cn/articles/coreos-analyse-etcd