一致性問題可以算是分布式領域的一個圣殿級問題了耗溜，關于它的研究可以回溯到幾十年前腾它。
拜占庭將軍問題
Leslie Lamport 在三十多年前發(fā)表的論文《拜占庭將軍問題》（參考[1]）拇勃。
拜占庭位于如今的土耳其的伊斯坦布爾准给，是東羅馬帝國的首都摹迷。由于當時拜占庭羅馬帝國國土遼闊宵凌，為了防御目的供搀，因此每個軍隊都分隔很遠隅居，將軍與將軍之間只能靠信差傳消息。在戰(zhàn)爭的時候葛虐，拜占庭軍隊內(nèi)所有將軍必需達成 一致的共識胎源，決定是否有贏的機會才去攻打敵人的陣營。但是屿脐，在軍隊內(nèi)有可能存有叛徒和敵軍的間諜涕蚤，左右將軍們的決定又擾亂整體軍隊的秩序，在進行共識時的诵，結(jié)果并不代表大多數(shù)人的意見万栅。這時候，在已知有成員不可靠的情況下西疤，其余忠誠的將軍在不受叛徒或間諜的影響下如何達成一致的協(xié)議申钩，拜占庭問題就此形成。拜占庭假設是對現(xiàn)實世界的模型化瘪阁，由于硬件錯誤撒遣、網(wǎng)絡擁塞或斷開以及遭到惡意攻擊邮偎，計算機和網(wǎng)絡可能出現(xiàn)不可預料的行為。
Lamport 一直研究這類問題义黎，發(fā)表了一系列論文禾进。但綜合總結(jié)一下就是回答下面三個問題：
- 類似拜占庭將軍這樣的分布式一致性問題是否有解？
- 如果有解的話需要滿足什么樣的條件廉涕？
- 在特定前提條件的基礎上泻云，提出一種解法。
前兩個問題 Lamport 在論文《拜占庭將軍問題》已經(jīng)回答狐蜕，而第三個問題在后來的論文 《The Part-Time Parliament》中提出了一種算法并命名為 Paxos宠纯。這篇論文使用了大量的數(shù)學證明，而我基本就看不懂了（數(shù)學符號都認不全-?-;）层释，考慮到大家理解起來都比較困難婆瓜，后來 Lamport 又寫了另外一篇論文 《Paxos Made Simple》完全放棄了所有數(shù)學符號的證明，使用純英文的邏輯推導贡羔。我勉強逐字看了一遍廉白，然后感覺若有所悟，但你問我搞懂了嗎乖寒，我的標準應該還是沒懂猴蹂。對我來說理解一個算法有個明確的標準，就是真的懂了會在頭腦里能將算法映射為代碼楣嘁，而看完后面一篇論文僅僅是若有所悟還達不到能映射為代碼的清晰度磅轻。
雖然 Lamport 認為 Paxos 很 simple，但也許只是針對他的頭腦而言逐虚。事實是大家理解起來都還是很困難瓢省，所以 Raft 就是建立在希望得到一個更易于理解的 Paxos 算法的替代品。把可理解性作為算法的主要目標之一痊班，從論文題目就可看出來《In Search of an Understandable Consensus Algorithm》。
在進入正題前摹量，我想起一個舊故事可以很直觀的感受對一個問題不同的思維視角在可理解性上的差異涤伐。
不同視角的可理解性
依稀記得大約在二十年前，我還在讀初中時在一本可能大概叫《數(shù)學中的發(fā)散思維》（不能很清晰記得書名了）的書中看到這么一個有趣的問題缨称。
甲乙兩人輪流在一張圓桌上平放黑白圍棋子凝果，每次放一子，棋子不許重疊睦尽，誰先沒有地方放就輸器净。
請問怎樣放才能贏？
這個問題有兩層意思当凡，第一山害，有沒有一種放法保證必贏纠俭？第二，如果有怎么證明浪慌？這里先停頓下冤荆，思考十秒鐘。
上面的圖回答了這個問題权纤，就是先行者必勝钓简，這里使用了三種不同的思維方式。
- 假如桌子只有一個圍棋子那么大汹想。
- 假如桌子無限大外邓，先行者先占住圓心，由于圓是對稱圖形古掏，所以只要對手還能找到位置放损话，你總能在對稱的另一面找到位置放。
- 一個圓中可畫單數(shù)個直徑相等且互切的小圓冗茸。
三種不同的思維方式在可理解性難度上逐漸加深席镀。第一種是極簡化思維，但數(shù)學上是不嚴謹?shù)南氖５诙N是極限思維豪诲，和第一種結(jié)合起來就是數(shù)學歸納法了，在數(shù)學上是嚴謹?shù)墓掖隆５谌N是形象思維屎篱，使用了幾何學概念，但對于沒有幾何學基礎知識的人就很難理解了葵蒂。
Raft 協(xié)議的易理解性描述
雖然 Raft 的論文比 Paxos 簡單版論文還容易讀了交播，但論文依然發(fā)散的比較多，相對冗長践付。讀完后掩卷沉思覺得還是整理一下才會更牢靠秦士，變成真正屬于自己的。這里我就借助前面黑白棋落子里第一種極簡思維來描述和概念驗證下 Raft 協(xié)議的工作方式永高。
在一個由 Raft 協(xié)議組織的集群中有三類角色：
- Leader（領袖）
- Follower（群眾）
- Candidate（候選人）
就像一個民主社會隧土，領袖由民眾投票選出。剛開始沒有領袖命爬，所有集群中的參與者都是群眾曹傀，那么首先開啟一輪大選，在大選期間所有群眾都能參與競選饲宛，這時所有群眾的角色就變成了候選人皆愉，民主投票選出領袖后就開始了這屆領袖的任期，然后選舉結(jié)束，所有除領袖的候選人又變回群眾角色服從領袖領導幕庐。這里提到一個概念「任期」久锥，用術語 Term 表達。關于 Raft 協(xié)議的核心概念和術語就這么多而且和現(xiàn)實民主制度非常匹配翔脱，所以很容易理解奴拦。三類角色的變遷圖如下，結(jié)合后面的選舉過程來看很容易理解届吁。
Leader 選舉過程
在極簡的思維下错妖，一個最小的 Raft 民主集群需要三個參與者（如下圖：A、B疚沐、C）暂氯，這樣才可能投出多數(shù)票。初始狀態(tài) ABC 都是 Follower亮蛔，然后發(fā)起選舉這時有三種可能情形發(fā)生痴施。下圖中前二種都能選出 Leader，第三種則表明本輪投票無效（Split Votes）究流，每方都投給了自己辣吃，結(jié)果沒有任何一方獲得多數(shù)票。之后每個參與方隨機休息一陣（Election Timeout）重新發(fā)起投票直到一方獲得多數(shù)票芬探。這里的關鍵就是隨機 timeout神得，最先從 timeout 中恢復發(fā)起投票的一方向還在 timeout 中的另外兩方請求投票，這時它們就只能投給對方了偷仿，很快達成一致哩簿。
選出 Leader 后，Leader 通過定期向所有 Follower 發(fā)送心跳信息維持其統(tǒng)治酝静。若 Follower 一段時間未收到 Leader 的心跳則認為 Leader 可能已經(jīng)掛了再次發(fā)起選主過程节榜。
Leader 節(jié)點對一致性的影響
Raft 協(xié)議強依賴 Leader 節(jié)點的可用性來確保集群數(shù)據(jù)的一致性。數(shù)據(jù)的流向只能從 Leader 節(jié)點向 Follower 節(jié)點轉(zhuǎn)移别智。當 Client 向集群 Leader 節(jié)點提交數(shù)據(jù)后宗苍，Leader 節(jié)點接收到的數(shù)據(jù)處于未提交狀態(tài)（Uncommitted），接著 Leader 節(jié)點會并發(fā)向所有 Follower 節(jié)點復制數(shù)據(jù)并等待接收響應薄榛，確保至少集群中超過半數(shù)節(jié)點已接收到數(shù)據(jù)后再向 Client 確認數(shù)據(jù)已接收讳窟。一旦向 Client 發(fā)出數(shù)據(jù)接收 Ack 響應后，表明此時數(shù)據(jù)狀態(tài)進入已提交（Committed）蛇数，Leader 節(jié)點再向 Follower 節(jié)點發(fā)通知告知該數(shù)據(jù)狀態(tài)已提交。
在這個過程中是越，主節(jié)點可能在任意階段掛掉耳舅，看下 Raft 協(xié)議如何針對不同階段保障數(shù)據(jù)一致性的。
1. 數(shù)據(jù)到達 Leader 節(jié)點前
這個階段 Leader 掛掉不影響一致性，不多說浦徊。
2. 數(shù)據(jù)到達 Leader 節(jié)點馏予，但未復制到 Follower 節(jié)點
這個階段 Leader 掛掉，數(shù)據(jù)屬于未提交狀態(tài)盔性，Client 不會收到 Ack 會認為超時失敗可安全發(fā)起重試霞丧。Follower 節(jié)點上沒有該數(shù)據(jù)，重新選主后 Client 重試重新提交可成功冕香。原來的 Leader 節(jié)點恢復后作為 Follower 加入集群重新從當前任期的新 Leader 處同步數(shù)據(jù)蛹尝，強制保持和 Leader 數(shù)據(jù)一致。
3. 數(shù)據(jù)到達 Leader 節(jié)點悉尾，成功復制到 Follower 所有節(jié)點突那，但還未向 Leader 響應接收
這個階段 Leader 掛掉，雖然數(shù)據(jù)在 Follower 節(jié)點處于未提交狀態(tài)（Uncommitted）但保持一致构眯，重新選出 Leader 后可完成數(shù)據(jù)提交愕难，此時 Client 由于不知到底提交成功沒有，可重試提交惫霸。針對這種情況 Raft 要求 RPC 請求實現(xiàn)冪等性猫缭，也就是要實現(xiàn)內(nèi)部去重機制。
4. 數(shù)據(jù)到達 Leader 節(jié)點壹店，成功復制到 Follower 部分節(jié)點猜丹，但還未向 Leader 響應接收
這個階段 Leader 掛掉，數(shù)據(jù)在 Follower 節(jié)點處于未提交狀態(tài)（Uncommitted）且不一致茫打，Raft 協(xié)議要求投票只能投給擁有最新數(shù)據(jù)的節(jié)點居触。所以擁有最新數(shù)據(jù)的節(jié)點會被選為 Leader 再強制同步數(shù)據(jù)到 Follower，數(shù)據(jù)不會丟失并最終一致老赤。
5. 數(shù)據(jù)到達 Leader 節(jié)點轮洋，成功復制到 Follower 所有或多數(shù)節(jié)點，數(shù)據(jù)在 Leader 處于已提交狀態(tài)抬旺，但在 Follower 處于未提交狀態(tài)
這個階段 Leader 掛掉弊予，重新選出新 Leader 后的處理流程和階段 3 一樣。
6. 數(shù)據(jù)到達 Leader 節(jié)點开财，成功復制到 Follower 所有或多數(shù)節(jié)點汉柒，數(shù)據(jù)在所有節(jié)點都處于已提交狀態(tài)，但還未響應 Client
這個階段 Leader 掛掉责鳍，Cluster 內(nèi)部數(shù)據(jù)其實已經(jīng)是一致的碾褂，Client 重復重試基于冪等策略對一致性無影響。
7. 網(wǎng)絡分區(qū)導致的腦裂情況历葛，出現(xiàn)雙 Leader
網(wǎng)絡分區(qū)將原先的 Leader 節(jié)點和 Follower 節(jié)點分隔開正塌，F(xiàn)ollower 收不到 Leader 的心跳將發(fā)起選舉產(chǎn)生新的 Leader嘀略。這時就產(chǎn)生了雙 Leader，原先的 Leader 獨自在一個區(qū)乓诽，向它提交數(shù)據(jù)不可能復制到多數(shù)節(jié)點所以永遠提交不成功帜羊。向新的 Leader 提交數(shù)據(jù)可以提交成功，網(wǎng)絡恢復后舊的 Leader 發(fā)現(xiàn)集群中有更新任期（Term）的新 Leader 則自動降級為 Follower 并從新 Leader 處同步數(shù)據(jù)達成集群數(shù)據(jù)一致鸠天。
綜上窮舉分析了最小集群（3 節(jié)點）面臨的所有情況讼育，可以看出 Raft 協(xié)議都能很好的應對一致性問題，并且很容易理解稠集。
總結(jié)
就引用 Raft 論文最后的一節(jié)的綜述來總結(jié)本文吧奶段。
算法以正確性、高效性巍杈、簡潔性作為主要設計目標忧饭。
雖然這些都是很有價值的目標，但這些目標都不會達成直到開發(fā)者寫出一個可用的實現(xiàn)筷畦。
所以我們相信可理解性同樣重要词裤。
深以為然，想想 Paxos 算法是 Leslie Lamport 在 1990 年就公開發(fā)表在了自己的網(wǎng)站上鳖宾，想想我們是什么時候才聽說的吼砂？什么時候才有一個可用的實現(xiàn)？而 Raft 算法是 2013 年發(fā)表的鼎文，大家在參考[5]上面可以看到有多少個不同語言開源的實現(xiàn)庫了渔肩，這就是可理解性的重要性。
參考
[1]. LESLIE LAMPORT, ROBERT SHOSTAK, MARSHALL PEASE. The Byzantine General Problem. 1982
[2]. Leslie Lamport. The Part-Time Parliament. 1998
[3]. Leslie Lamport. Paxos Made Simple. 2001
[4]. Diego Ongaro and John Ousterhout. Raft Paper. 2013
[5]. Raft Website. The Raft Consensus Algorithm
[6]. Raft Demo. Raft Animate Demo
