昨天我們介紹了拜占庭將軍問題和FLP Impossibility, 我們知道了在異步網(wǎng)絡(luò)中的total correct的consensus算法是不存在的, 但是如果我們放松

liveness的要求, 我們在工程和實際應(yīng)用當(dāng)中, 我們是否可以解決一致性問題呢? 今天我們會給大家介紹一個工程中最常用的一個consensus算法 – Paxos算法.

大名鼎鼎的Paxos算法

Consensus主要目的是屏蔽掉故障節(jié)點的噪音讓整個系統(tǒng)正常運行下去, 比如選舉過程和狀態(tài)機復(fù)制. 所以Consensus問題對于agreement條件做了放松, 它接受不一致是常態(tài)的事實, 既然我無法知道某些節(jié)點是掛了還是暫時聯(lián)系不到, 那我只要關(guān)心正確響應(yīng)的節(jié)點, 只要表決能過半即可, 過半表決意味著雖然沒有完全一致, 但是”投票結(jié)果”被過半成員繼承下來了, 這是因為任何兩個quorum一定會存在交集(想象一下有A/B/C三個節(jié)點, 兩個quorum比如AB和AC一定會有A是交集), 所以不管有多少個quorum存在, 我們能確保他們一定會有交集, 所以他們一定能信息互通而最終達(dá)成一致, 其他沒有達(dá)成一致的成員將來在網(wǎng)絡(luò)恢復(fù)后也可以和這部分交集內(nèi)的節(jié)點傳播出去的”真理”達(dá)成一致.

大名鼎鼎的Paxos算法誕生了， Paxos是第一個正確實現(xiàn)適用于分布式系統(tǒng)的Consensus算法。1990年Lamport提出了這個算法, 但有趣的是ACM TOCS的評審委員們沒看懂他的論文, 主編建議他不要拿古希臘神話什么長老被砸健忘了的故事寫論文, 要他用數(shù)學(xué)語言寫簡潔點, Lamport也是個人才, 他拒絕修改論文, 并在一次會議上公開質(zhì)疑”為什么搞基礎(chǔ)理論的人一點幽默感都沒有呢?”

6年光陰過去, 另外一個超級牛人, 圖靈獎獲得者Butler Lampson看到這篇論文, 而且…… 他看懂了! Lampson覺得這個算法很重要并呼吁大家重新審視這篇重要論文, 后來提出FLP理論的三人組其中的Nacy Lynch重寫了篇文章闡述這篇論文, 后來終于大家都看懂了, 最終1998年ACM TOCS終于發(fā)表了這篇論文 [The Part-Time Parliament. ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169], 至此將近9年了. 最爆笑得是1998發(fā)表的時候, 負(fù)責(zé)編輯的Keith配合Lamport的幽默寫的注解, 這里我給八卦一下省的你去翻論文了:

本文最近剛被從一個文件柜里發(fā)現(xiàn), 盡管這篇論文是很久之前提交的但是主編認(rèn)為還是值得發(fā)表的(不是我們ACM TOCS過去沒看懂, 是忘記發(fā)表了). 但是由于作者目前在希臘小島上考古, ACM TOCS聯(lián)系不上這位考古學(xué)家, 所以任命我來發(fā)表這篇論文(其實是Lamport拒絕修改論文, 不鳥ACM TOCS了). 作者貌似是個對計算機科學(xué)稍微有點興趣的考古學(xué)家(赤裸裸的吐槽), 盡管他描述的Paxon島上民主制度的故事對計算機科學(xué)家沒啥興趣, 但是但是這套制度對于在異步網(wǎng)絡(luò)中實現(xiàn)分布式系統(tǒng)到時很好的模型(這句總算客觀了). 建議閱讀的時候直接看第四節(jié)(跳過前三節(jié)神話故事), 或者最好先別看(你可能會看不懂), 最好先去看看Lampson或者De Prisco對這篇論文的解釋.

看到這你笑噴了沒?

我們的”考古學(xué)家” Lamport在Paxos算法定義了三個角色, 其中proposer是提出建議值的進(jìn)程, acceptor是決定是否接受建議的進(jìn)程, learner是不會提議但是也要了解結(jié)果的進(jìn)程, 在一個系統(tǒng)中一個進(jìn)程經(jīng)常同時扮演這三個角色. 算法分兩個階段 (以下是最基礎(chǔ)的算法, 其中沒有l(wèi)earners):

第一階段: 一個proposer選擇一個全局唯一的序號n發(fā)給至少過半的acceptors. 如果一個acceptor收到的請求中的序號n大于之前收到的建議, 那么這個acceptor返回proposer一個確認(rèn)消息表示它不會再接受任何小于這個n的建議.

第二階段: 如果proposer收到過半的acceptor的確認(rèn)消息表示他們不會接受n以下的建議, 那么這個proposer給這些acceptor返回附帶他的建議值v的確認(rèn)消息. 如果一個acceptor收到這樣的確認(rèn)消息{n, v}, acceptor就會接受它. 除非在此期間acceptor又收到了一個更高的n的建議.

對證明有興趣的讀者可以去看看Paxos Made Simple. 簡單來講, 算法的正確性有兩個方面促煮。

提議的safety是由sequence number N決定的, 如果N是全序集, 唯一而且一定有先后, 并且在每個proposer上都單調(diào)遞增, 那么acceptor選擇的結(jié)果就是安全的. 實際應(yīng)用中, 這個N經(jīng)常是timestamp, 進(jìn)程id, 還有進(jìn)程的本體counter的組合, 比如: timestamp + node id + counter, 或者像twitter的snowflake基于timestamp和網(wǎng)卡mac地址的算法. 這樣可以保證事件順序盡量接近物理時間的順序, 同時保證事件number的唯一性.

過半表決可以保證網(wǎng)絡(luò)出現(xiàn)多個分區(qū)的時候, 任何兩個能夠過半的分區(qū)必然存在交集, 而交集內(nèi)的進(jìn)程就可以保證正確性被繼承, 以后被傳播出去.

Paxos是一個非陈穑基礎(chǔ)的算法, 更多的時候你需要在Paxos的基礎(chǔ)之上實現(xiàn)你的算法.

Paxos的過半表決有一定局限性. 這牽扯到分區(qū)可用性. 如果網(wǎng)絡(luò)分區(qū)的時候, 沒有形成多數(shù)派, 比如一個網(wǎng)絡(luò)內(nèi)被均勻的分成了三個小區(qū), 那么整個系統(tǒng)都不能正常工作了. 如果分成一個大區(qū), 一個小區(qū), 那么小區(qū)是無法工作的, 如果大區(qū)和小區(qū)非常接近, 比如是501 vs 499, 這意味著系統(tǒng)的處理能力可能會下降一半. 所有這些都影響到了Paxos的可用性. 舉個例子, Zookeeper的ZAB協(xié)議的選舉和廣播部分很類似Paxos, Zookeeper允許讀取過期數(shù)據(jù)來獲得更好的性能, 所以一般情況下是Sequential Consistency. 但是他有一個Sync命令, 當(dāng)你每次都Sync+Read的時候, 雖然性能大打折扣, 但是Zookeeper就是和Paxos一樣能保證Linearizability了. 當(dāng)zookeeper在發(fā)生網(wǎng)絡(luò)分區(qū)的時候, 如果leader在quorum side (大區(qū)), 那么quorum side的讀寫都正常, 但是non-quorum side因為無法從小區(qū)選出leader, 所有連接到non-quorum side的客戶端的所有的讀寫都會失敗! (也可以不發(fā)Sync命令降低到SC級別, 通過過期的緩存讓讀操作能繼續(xù)下去) 如果把client也考慮在內(nèi), 假設(shè)如下圖所示, 99%的節(jié)點連同1%的客戶端處于一個分區(qū), 那么會導(dǎo)致99%的客戶端都無法正常工作, 盡管這個時候集群是99%的節(jié)點都是好的. (通常我們的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不會發(fā)生這么極端不平衡的情況).

有人會覺得網(wǎng)絡(luò)分區(qū)在同一個數(shù)據(jù)中心內(nèi)發(fā)生的概率非常低吧?

其實不然, 舉一個例子, github在2012年有一次升級一對聚合交換機的時候, 發(fā)現(xiàn)了一些問題決定降級, 降級過程中其中要關(guān)閉一臺交換機的agent來收集故障信息, 導(dǎo)致90秒鐘的網(wǎng)絡(luò)分區(qū), 精彩的開始了. 首先, github的文件服務(wù)器是基于DRBD的, 因為每一對文件服務(wù)器只能有一個活動節(jié)點, 另外一個作為熱備, 當(dāng)主節(jié)點出現(xiàn)故障后, 熱備節(jié)點在接替故障的活動節(jié)點之前會發(fā)一個指令去關(guān)閉活動節(jié)點. 如果網(wǎng)絡(luò)沒有分區(qū), 活動節(jié)點的硬件發(fā)生了故障導(dǎo)致響應(yīng)超時, 那么這樣可以避免brain-split. 但是在網(wǎng)絡(luò)分區(qū)的情況下, 活動節(jié)點沒有收到關(guān)閉指令, 熱備節(jié)點就把自己作為新的活動節(jié)點了, 當(dāng)網(wǎng)絡(luò)恢復(fù)之后, 就有了兩個活動節(jié)點同時服務(wù), 導(dǎo)致了數(shù)據(jù)不一致不說, 還會發(fā)生互相嘗試殺死對方的情況, 因為兩邊都認(rèn)為對方是有故障的, 需要殺死對方, 結(jié)果有些文件服務(wù)器真的把對方都?xì)⑺懒?

網(wǎng)絡(luò)分區(qū)是真實存在的, 而且在跨多個數(shù)據(jù)中心的情況下, 網(wǎng)絡(luò)分區(qū)發(fā)生的概率更高. 所以使用zookeeper的時候你一定要理解他的一致性模型在處理網(wǎng)絡(luò)分區(qū)的情況時的局限性. 對于map reduce來講, 結(jié)果是correct or nothing, 寧可犧牲可用性也要保證一致性, safety更重要. 但是一個分布式系統(tǒng)的服務(wù)發(fā)現(xiàn)組件就不同了, 對于發(fā)現(xiàn)服務(wù)而言, having something wrong is better than having nothing, liveness更重要. 所以Netflix的黑幫們才自己造了個輪子Eureka, 因為如果你的微服務(wù)都是無狀態(tài)的, 大多數(shù)情況下發(fā)現(xiàn)服務(wù)只要能達(dá)到Eventual Consistency就可以了, 而高可用性是必須的. 后面介紹CAP定理和Eventual Consistency的時候會介紹一下側(cè)重可用性的算法.

除了網(wǎng)絡(luò)分區(qū), Paxos的另外一個缺點是延遲比較高. 因為Paxos放松了liveness, 它有時候可能會多個回合才能決定結(jié)果, 錯誤的實現(xiàn)甚至?xí)?dǎo)致live lock. 比如proposer A提出n1, proposer B提出n2, 如果n1 > n2, acceptor先接受了n1, B收到拒絕之后重新發(fā)起n3, 如果n3先于A的確認(rèn)消息到達(dá)acceptor, 而且n3 > n1, 那么acceptor會拒絕A, 接受B, A可能會重復(fù)B的行為, 然后無限循環(huán)下去.

FLP理論描述了Consensus可能會進(jìn)入無限循環(huán)的情況, 但是實際應(yīng)用中這個概率非常低, 大家都知道計算機科學(xué)是應(yīng)用科學(xué), 不是離散數(shù)學(xué)那樣非正即誤, 如果錯誤或者偏離的概率非常低, 工程中就會采用. 比如費馬小定理(Fermat’s Little Theorem) 由于Carmichael Number的存在并不能用來嚴(yán)格判斷大素數(shù), 但是由于Carmichael Number實在是太少, 1024 bit的范圍里概率為10^-88, 所以RSA算法還是會用費馬小定理. 同樣, 根據(jù)FLP理論, 異步網(wǎng)絡(luò)中Paxos可能會進(jìn)入無限循環(huán). 真實世界中Paxos的如果兩個節(jié)點不斷的互相否定, 那么就會出現(xiàn)無限循環(huán), 但是要永遠(yuǎn)持續(xù)下去的概率非常非常低, 實際中我們經(jīng)常讓某個Proposer獲取一定期限的lease, 在此期限之內(nèi)只有一個proposer接受客戶端請求并提出 proposal. 或者隨機改變n的增長節(jié)奏和proposer的發(fā)送節(jié)奏等, 來降低livelock的概率. 當(dāng)然, 單從純粹FLP理論來看, 超過一個proposer的時候Paxos是不保證liveness的.

Paxos在實現(xiàn)中, 每個進(jìn)程其實一般都是身兼三職, 然后成功提議的那個proposer所在的進(jìn)程就是 distinguished proposer, 也是 distinguished learner, 我們稱之為 leader.

上面提到的Paxos算法是最原始的形式, 這個過程中有很多可以優(yōu)化的地方, 比如如果accetpr拒絕了可以順便返回當(dāng)前最高的n, 減少算法重試的回合, 但這不影響這個算法的正確性. 比如Multi-Paxos可以假設(shè)leader沒有掛掉或者過期之前不用每次都發(fā)出prepare請求, 直接發(fā)accept請求, 再比如Fast Paxos等等.

Paxos設(shè)計的時候把異步網(wǎng)絡(luò)的不確定性考慮在內(nèi), 放松了liveness的要求, 算法按照crash-recovery的思想設(shè)計, 所以Paxos才可以成為這樣實際廣泛應(yīng)用而且成功的算法. 但是Paxos也不能容忍拜占庭式故障節(jié)點, 要容忍拜占庭式故障實在是太困難了 (比如, Paxos中兩個quorum中的交集如果都是叛徒怎么辦?).

盡管Paxos有很多缺點, 但是Paxos仍然是分布式系統(tǒng)中最重要的一個算法, 比如它的一個重要用途就是 State Machine Replication. 一個Deterministic State Machine對于固定的輸入序列一定會產(chǎn)生固定的結(jié)果, 不論重復(fù)執(zhí)行多少次, 或者再另外一臺一樣的機器上執(zhí)行, 結(jié)果都是一樣的. 分布式系統(tǒng)中最常見的一個需求就是通過某種路由算法讓客戶端請求去一組狀態(tài)一致的服務(wù)器, 數(shù)據(jù)在服務(wù)器上的分布要有replica來保證高可用性, 但是replica之間要一致. 狀態(tài)復(fù)制就成為了分布式系統(tǒng)的一個核心問題. Paxos的狀態(tài)復(fù)制可以保證整個系統(tǒng)的所有狀態(tài)機接受同樣的輸入序列 (Atomic Broadcast), 如果查詢也使用過半表決, 那么你一定會得到正確的結(jié)果.

這種做法相對于Master-Slave的的狀態(tài)復(fù)制一致性好很多. 比如一旦Master節(jié)點掛了, 還沒來得及復(fù)制的結(jié)果會導(dǎo)致Slave之間的狀態(tài)有可能是不一致的, 如果客戶端能夠訪問到延遲的Slave節(jié)點, 那么用戶展現(xiàn)的數(shù)據(jù)將會不一致. 如果你可以犧牲性能來換得更高的一致性, 那么你可以通過Paxos表決查詢來屏蔽掉延遲或者有故障的節(jié)點. 只要系統(tǒng)中存在一個quorum, 那么狀態(tài)的一致性就可以保留下去. 比如google的chubby, 只要故障節(jié)點不超過一半, 網(wǎng)絡(luò)沒有發(fā)生分區(qū), chubby就可以通過Paxos狀態(tài)機為其他服務(wù)器提供分布式鎖. 因為chubby分別部署在每個數(shù)據(jù)中心, 他們沒有跨數(shù)據(jù)中心的通信, 所以網(wǎng)絡(luò)分區(qū)的故障頻率不像跨數(shù)據(jù)中心的情況那么多高, chubby犧牲部分性能和網(wǎng)絡(luò)分區(qū)下的可用性, 換來了一致性.

因為Paxos家族的算法寫性能都不是很好但是一致性又很重要, 所以實現(xiàn)中我們經(jīng)常做一些取舍, 讓Paxos只處理最關(guān)鍵的信息. 比如Kafaka的每個Partition都有多個replicas, 日志的復(fù)制本身沒有經(jīng)過Paxos這樣高延遲的算法, 但是為了保證負(fù)責(zé)接受producer請求和跟蹤ISR的leader只有一個, Kafaka依賴于Zookeeper的ZAB算法來選舉leader. 在實際應(yīng)用中, 狀態(tài)機復(fù)制不太適合很高的吞吐量, 一般都是用于不太頻繁寫入的重要信息. Zookeeper不能被當(dāng)做一個OLTP級的數(shù)據(jù)庫用, 它不是分布式系統(tǒng)協(xié)同的萬能鑰匙。

Uniform Consensus

對于Consensus問題, 我們只關(guān)注非故障節(jié)點的一致性和整體系統(tǒng)的正常, 而Uniform Consensus中要求無論是非故障節(jié)點還是故障節(jié)點, 他們都要一致, 比如在分布式事務(wù)的前后, 各個節(jié)點必須一致, 故障節(jié)點恢復(fù)后也要一致, 任何時刻都不應(yīng)該有兩個參與者一個決定提交, 一個決定回滾.杀捻。

很長一段時間內(nèi)大多數(shù)人沒有把Uniform Consensus單獨分類, 直到2001年才有人提出Uniform Consensus更難. [Uniform Consensus is Harder Than Consensus, Charron-Bost, Schiper, Journal of Algorithms 51 2004 15-37]

一般的Consensus問題通常用來解決狀態(tài)機復(fù)制時容錯處理的問題, 比如Paxos, 而Uniform Consensus所處理的是分布式事務(wù)這樣的問題, 在Uniform Consensus中我們要求所有節(jié)點在故障恢復(fù)后都要達(dá)成一致. 所以Uniform Consensus的定義在agreement上更加嚴(yán)格:

termination: 所有進(jìn)程最終會在有限步數(shù)中結(jié)束并選取一個值, 算法不會無盡執(zhí)行下去.

agreement: 所有進(jìn)程(包含故障節(jié)點恢復(fù)后)必須同意同一個值. (假設(shè)系統(tǒng)沒有拜占庭故障)

validity: 最終達(dá)成一致的值必須是V1到Vn其中一個, 如果所有初始值都是vx, 那么最終結(jié)果也必須是vx.

總結(jié)

至此, 通過對Concensus問題的介紹, 我們對Linearizability和Sequential Consistency的應(yīng)用應(yīng)該有了更深入的理解, 在本系列下一篇文章中我們將會介紹性能更好但是一致性要求更低的Causal Consistency, PRAM以及不需要硬件自動同步的一致性模型, 比如Weak Consistency墓拜。

本文作者：Daniel吳強（點融黑幫），現(xiàn)任點融網(wǎng)首席社交平臺架構(gòu)師请契，前盛大架構(gòu)師, 專注分布式系統(tǒng)和移動應(yīng)用, 有十三年的開發(fā)經(jīng)驗, 目前在點融做最愛的兩件事情: 寫代碼和重構(gòu)代碼咳榜。