一致性問題可以算是分布式領(lǐng)域的一個(gè)圣殿級(jí)問題了，關(guān)于它的研究可以回溯到幾十年前。
拜占庭將軍問題
Leslie Lamport 在三十多年前發(fā)表的論文《拜占庭將軍問題》（參考[1]）。
拜占庭位于如今的土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當(dāng)時(shí)拜占庭羅馬帝國國土遼闊，為了防御目的，因此每個(gè)軍隊(duì)都分隔很遠(yuǎn)，將軍與將軍之間只能靠信差傳消息。在戰(zhàn)爭的時(shí)候，拜占庭軍隊(duì)內(nèi)所有將軍必需達(dá)成 一致的共識(shí)，決定是否有贏的機(jī)會(huì)才去攻打敵人的陣營。但是，在軍隊(duì)內(nèi)有可能存有叛徒和敵軍的間諜，左右將軍們的決定又?jǐn)_亂整體軍隊(duì)的秩序，在進(jìn)行共識(shí)時(shí)，結(jié)果并不代表大多數(shù)人的意見。這時(shí)候，在已知有成員不可靠的情況下，其余忠誠的將軍在不受叛徒或間諜的影響下如何達(dá)成一致的協(xié)議，拜占庭問題就此形成。拜占庭假設(shè)是對(duì)現(xiàn)實(shí)世界的模型化，由于硬件錯(cuò)誤、網(wǎng)絡(luò)擁塞或斷開以及遭到惡意攻擊，計(jì)算機(jī)和網(wǎng)絡(luò)可能出現(xiàn)不可預(yù)料的行為。
Lamport 一直研究這類問題，發(fā)表了一系列論文。但綜合總結(jié)一下就是回答下面三個(gè)問題：
- 類似拜占庭將軍這樣的分布式一致性問題是否有解？
- 如果有解的話需要滿足什么樣的條件？
- 在特定前提條件的基礎(chǔ)上，提出一種解法。
前兩個(gè)問題 Lamport 在論文《拜占庭將軍問題》已經(jīng)回答，而第三個(gè)問題在后來的論文 《The Part-Time Parliament》中提出了一種算法并命名為 Paxos。這篇論文使用了大量的數(shù)學(xué)證明，而我基本就看不懂了（數(shù)學(xué)符號(hào)都認(rèn)不全-?-;），考慮到大家理解起來都比較困難，后來 Lamport 又寫了另外一篇論文 《Paxos Made Simple》完全放棄了所有數(shù)學(xué)符號(hào)的證明，使用純英文的邏輯推導(dǎo)。我勉強(qiáng)逐字看了一遍，然后感覺若有所悟，但你問我搞懂了嗎，我的標(biāo)準(zhǔn)應(yīng)該還是沒懂。對(duì)我來說理解一個(gè)算法有個(gè)明確的標(biāo)準(zhǔn)，就是真的懂了會(huì)在頭腦里能將算法映射為代碼，而看完后面一篇論文僅僅是若有所悟還達(dá)不到能映射為代碼的清晰度。
雖然 Lamport 認(rèn)為 Paxos 很 simple，但也許只是針對(duì)他的頭腦而言。事實(shí)是大家理解起來都還是很困難，所以 Raft 就是建立在希望得到一個(gè)更易于理解的 Paxos 算法的替代品。把可理解性作為算法的主要目標(biāo)之一，從論文題目就可看出來《In Search of an Understandable Consensus Algorithm》。
在進(jìn)入正題前，我想起一個(gè)舊故事可以很直觀的感受對(duì)一個(gè)問題不同的思維視角在可理解性上的差異。
不同視角的可理解性
依稀記得大約在二十年前，我還在讀初中時(shí)在一本可能大概叫《數(shù)學(xué)中的發(fā)散思維》（不能很清晰記得書名了）的書中看到這么一個(gè)有趣的問題。
甲乙兩人輪流在一張圓桌上平放黑白圍棋子，每次放一子，棋子不許重疊，誰先沒有地方放就輸。
請(qǐng)問怎樣放才能贏？
這個(gè)問題有兩層意思，第一，有沒有一種放法保證必贏？第二，如果有怎么證明？這里先停頓下，思考十秒鐘。
上面的圖回答了這個(gè)問題，就是先行者必勝，這里使用了三種不同的思維方式。
- 假如桌子只有一個(gè)圍棋子那么大。
- 假如桌子無限大，先行者先占住圓心，由于圓是對(duì)稱圖形，所以只要對(duì)手還能找到位置放，你總能在對(duì)稱的另一面找到位置放。
- 一個(gè)圓中可畫單數(shù)個(gè)直徑相等且互切的小圓。
三種不同的思維方式在可理解性難度上逐漸加深。第一種是極簡化思維，但數(shù)學(xué)上是不嚴(yán)謹(jǐn)?shù)摹５诙N是極限思維，和第一種結(jié)合起來就是數(shù)學(xué)歸納法了，在數(shù)學(xué)上是嚴(yán)謹(jǐn)?shù)?。第三種是形象思維，使用了幾何學(xué)概念，但對(duì)于沒有幾何學(xué)基礎(chǔ)知識(shí)的人就很難理解了。
Raft 協(xié)議的易理解性描述
雖然 Raft 的論文比 Paxos 簡單版論文還容易讀了，但論文依然發(fā)散的比較多，相對(duì)冗長。讀完后掩卷沉思覺得還是整理一下才會(huì)更牢靠，變成真正屬于自己的。這里我就借助前面黑白棋落子里第一種極簡思維來描述和概念驗(yàn)證下 Raft 協(xié)議的工作方式。
在一個(gè)由 Raft 協(xié)議組織的集群中有三類角色：
- Leader（領(lǐng)袖）
- Follower（群眾）
- Candidate（候選人）
就像一個(gè)民主社會(huì)，領(lǐng)袖由民眾投票選出。剛開始沒有領(lǐng)袖，所有集群中的參與者都是群眾，那么首先開啟一輪大選，在大選期間所有群眾都能參與競(jìng)選，這時(shí)所有群眾的角色就變成了候選人，民主投票選出領(lǐng)袖后就開始了這屆領(lǐng)袖的任期，然后選舉結(jié)束，所有除領(lǐng)袖的候選人又變回群眾角色服從領(lǐng)袖領(lǐng)導(dǎo)。這里提到一個(gè)概念「任期」，用術(shù)語 Term 表達(dá)。關(guān)于 Raft 協(xié)議的核心概念和術(shù)語就這么多而且和現(xiàn)實(shí)民主制度非常匹配，所以很容易理解。三類角色的變遷圖如下，結(jié)合后面的選舉過程來看很容易理解。
Leader 選舉過程
在極簡的思維下，一個(gè)最小的 Raft 民主集群需要三個(gè)參與者（如下圖：A、B、C），這樣才可能投出多數(shù)票。初始狀態(tài) ABC 都是 Follower，然后發(fā)起選舉這時(shí)有三種可能情形發(fā)生。下圖中前二種都能選出 Leader，第三種則表明本輪投票無效（Split Votes），每方都投給了自己，結(jié)果沒有任何一方獲得多數(shù)票。之后每個(gè)參與方隨機(jī)休息一陣（Election Timeout）重新發(fā)起投票直到一方獲得多數(shù)票。這里的關(guān)鍵就是隨機(jī) timeout，最先從 timeout 中恢復(fù)發(fā)起投票的一方向還在 timeout 中的另外兩方請(qǐng)求投票，這時(shí)它們就只能投給對(duì)方了，很快達(dá)成一致。
選出 Leader 后，Leader 通過定期向所有 Follower 發(fā)送心跳信息維持其統(tǒng)治。若 Follower 一段時(shí)間未收到 Leader 的心跳則認(rèn)為 Leader 可能已經(jīng)掛了再次發(fā)起選主過程。
Leader 節(jié)點(diǎn)對(duì)一致性的影響
Raft 協(xié)議強(qiáng)依賴 Leader 節(jié)點(diǎn)的可用性來確保集群數(shù)據(jù)的一致性。數(shù)據(jù)的流向只能從 Leader 節(jié)點(diǎn)向 Follower 節(jié)點(diǎn)轉(zhuǎn)移。當(dāng) Client 向集群 Leader 節(jié)點(diǎn)提交數(shù)據(jù)后，Leader 節(jié)點(diǎn)接收到的數(shù)據(jù)處于未提交狀態(tài)（Uncommitted），接著 Leader 節(jié)點(diǎn)會(huì)并發(fā)向所有 Follower 節(jié)點(diǎn)復(fù)制數(shù)據(jù)并等待接收響應(yīng)，確保至少集群中超過半數(shù)節(jié)點(diǎn)已接收到數(shù)據(jù)后再向 Client 確認(rèn)數(shù)據(jù)已接收。一旦向 Client 發(fā)出數(shù)據(jù)接收 Ack 響應(yīng)后，表明此時(shí)數(shù)據(jù)狀態(tài)進(jìn)入已提交（Committed），Leader 節(jié)點(diǎn)再向 Follower 節(jié)點(diǎn)發(fā)通知告知該數(shù)據(jù)狀態(tài)已提交。
在這個(gè)過程中，主節(jié)點(diǎn)可能在任意階段掛掉，看下 Raft 協(xié)議如何針對(duì)不同階段保障數(shù)據(jù)一致性的。
1. 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)前
這個(gè)階段 Leader 掛掉不影響一致性，不多說。
2. 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，但未復(fù)制到 Follower 節(jié)點(diǎn)
這個(gè)階段 Leader 掛掉，數(shù)據(jù)屬于未提交狀態(tài)，Client 不會(huì)收到 Ack 會(huì)認(rèn)為超時(shí)失敗可安全發(fā)起重試。Follower 節(jié)點(diǎn)上沒有該數(shù)據(jù)，重新選主后 Client 重試重新提交可成功。原來的 Leader 節(jié)點(diǎn)恢復(fù)后作為 Follower 加入集群重新從當(dāng)前任期的新 Leader 處同步數(shù)據(jù)，強(qiáng)制保持和 Leader 數(shù)據(jù)一致。
3. 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 所有節(jié)點(diǎn)，但還未向 Leader 響應(yīng)接收
這個(gè)階段 Leader 掛掉，雖然數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于未提交狀態(tài)（Uncommitted）但保持一致，重新選出 Leader 后可完成數(shù)據(jù)提交，此時(shí) Client 由于不知到底提交成功沒有，可重試提交。針對(duì)這種情況 Raft 要求 RPC 請(qǐng)求實(shí)現(xiàn)冪等性，也就是要實(shí)現(xiàn)內(nèi)部去重機(jī)制。
4. 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 部分節(jié)點(diǎn)，但還未向 Leader 響應(yīng)接收
這個(gè)階段 Leader 掛掉，數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于未提交狀態(tài)（Uncommitted）且不一致，Raft 協(xié)議要求投票只能投給擁有最新數(shù)據(jù)的節(jié)點(diǎn)。所以擁有最新數(shù)據(jù)的節(jié)點(diǎn)會(huì)被選為 Leader 再強(qiáng)制同步數(shù)據(jù)到 Follower，數(shù)據(jù)不會(huì)丟失并最終一致。
5. 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 所有或多數(shù)節(jié)點(diǎn)，數(shù)據(jù)在 Leader 處于已提交狀態(tài)，但在 Follower 處于未提交狀態(tài)
這個(gè)階段 Leader 掛掉，重新選出新 Leader 后的處理流程和階段 3 一樣。
6. 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 所有或多數(shù)節(jié)點(diǎn)，數(shù)據(jù)在所有節(jié)點(diǎn)都處于已提交狀態(tài)，但還未響應(yīng) Client
這個(gè)階段 Leader 掛掉，Cluster 內(nèi)部數(shù)據(jù)其實(shí)已經(jīng)是一致的，Client 重復(fù)重試基于冪等策略對(duì)一致性無影響。
7. 網(wǎng)絡(luò)分區(qū)導(dǎo)致的腦裂情況，出現(xiàn)雙 Leader
網(wǎng)絡(luò)分區(qū)將原先的 Leader 節(jié)點(diǎn)和 Follower 節(jié)點(diǎn)分隔開，F(xiàn)ollower 收不到 Leader 的心跳將發(fā)起選舉產(chǎn)生新的 Leader。這時(shí)就產(chǎn)生了雙 Leader，原先的 Leader 獨(dú)自在一個(gè)區(qū)，向它提交數(shù)據(jù)不可能復(fù)制到多數(shù)節(jié)點(diǎn)所以永遠(yuǎn)提交不成功。向新的 Leader 提交數(shù)據(jù)可以提交成功，網(wǎng)絡(luò)恢復(fù)后舊的 Leader 發(fā)現(xiàn)集群中有更新任期（Term）的新 Leader 則自動(dòng)降級(jí)為 Follower 并從新 Leader 處同步數(shù)據(jù)達(dá)成集群數(shù)據(jù)一致。
綜上窮舉分析了最小集群（3 節(jié)點(diǎn)）面臨的所有情況，可以看出 Raft 協(xié)議都能很好的應(yīng)對(duì)一致性問題，并且很容易理解。
總結(jié)
就引用 Raft 論文最后的一節(jié)的綜述來總結(jié)本文吧。
算法以正確性、高效性、簡潔性作為主要設(shè)計(jì)目標(biāo)。
雖然這些都是很有價(jià)值的目標(biāo)，但這些目標(biāo)都不會(huì)達(dá)成直到開發(fā)者寫出一個(gè)可用的實(shí)現(xiàn)。
所以我們相信可理解性同樣重要。
深以為然，想想 Paxos 算法是 Leslie Lamport 在 1990 年就公開發(fā)表在了自己的網(wǎng)站上，想想我們是什么時(shí)候才聽說的？什么時(shí)候才有一個(gè)可用的實(shí)現(xiàn)？而 Raft 算法是 2013 年發(fā)表的，大家在參考[5]上面可以看到有多少個(gè)不同語言開源的實(shí)現(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
