漫談分布式共識問題
混亂的“一致性”問題
Consensus != Consistency
受翻譯影響，網(wǎng)上很多討論 paxos 或 raft 的博客使用“分布式一致性協(xié)議”或者“分布式一致性算法”這樣的字眼，雖然在漢語中“達成共識”和“達成一致”是一個意思，但是必須要說明在這里討論的是 consensus 問題，使用“共識”來表達更清晰一些。而 CAP 定理中的 C 和數(shù)據(jù)庫 ACID 的 C 才是真正的“一致性”—— consistency 問題，盡管這兩個 C 討論的也不是同一個問題，但在這里不展開。
為了規(guī)范和清晰表達，在討論 consensus 問題的時候統(tǒng)一使用“共識”一詞。
注：在早些的文獻中，共識（consensus）也叫做協(xié)商（agreement）。
共識問題
那么共識問題到底是什么呢？舉個生活中的例子，小明和小王出去聚會，小明問：“小王，我們喝點什么吧？” 小王：“喝咖啡怎么樣？” 小明：“好啊，那就來杯咖啡。”
在上面的場景中，小王提議喝一杯咖啡，小明表示同意，兩人就“喝杯咖啡”這個問題達成共識，并根據(jù)這個結果采取行動。這就是生活中的共識。
在分布式系統(tǒng)中，共識就是系統(tǒng)中的多個節(jié)點對某個值達成一致。共識問題可以用數(shù)學語言來描述：一個分布式系統(tǒng)包含 n 個進程 {0, 1, 2,..., n-1}，每個進程都有一個初值，進程之間互相通信，設計一種算法使得盡管出現(xiàn)故障，進程們仍協(xié)商出某個不可撤銷的最終決定值，且每次執(zhí)行都滿足以下三個性質：
?終止性（Termination）：所有正確的進程最終都會認同某一個值。?協(xié)定性（Agreement）：所有正確的進程認同的值都是同一個值。?完整性（Integrity），也稱作有效性（Validity）：如果正確的進程都提議同一個值，那么所有處于認同狀態(tài)的正確進程都選擇該值。
完整性可以有一些變化，例如，一種較弱的完整性是認定值等于某些正確經(jīng)常提議的值，而不必是所有進程提議的值。完整性也隱含了，最終被認同的值必定是某個節(jié)點提出過的。
為什么要達成共識？
我們首先介紹分布式系統(tǒng)達成共識的動機。
在前文中，我們已經(jīng)了解到分布式系統(tǒng)的幾個主要難題：
?網(wǎng)絡問題?時鐘問題?節(jié)點故障問題
第一篇提到共識問題的文獻[1]?來自于 lamport 的 "Time, Clocks and the Ordering of Events in a Distributed System[2]"，盡管它并沒有明確的提出共識(consensus)或者協(xié)商(agreement)的概念。論文闡述了在分布式系統(tǒng)中，你無法判斷事件 A 是否發(fā)生在事件 B 之前，除非 A 和 B 存在某種依賴關系。由此還引出了分布式狀態(tài)機的概念。
在分布式系統(tǒng)中，共識就常常應用在這種多副本狀態(tài)機（Replicated state machines），狀態(tài)機在每臺節(jié)點上都存有副本，這些狀態(tài)機都有相同的初始狀態(tài)，每次狀態(tài)轉變、下個狀態(tài)是什么都由相關進程共同決定，每一臺節(jié)點的日志的值和順序都相同。每個狀態(tài)機在“哪個狀態(tài)是下一個需要處理的狀態(tài)”這個問題上達成共識，這就是一個共識問題。
最終，這些節(jié)點看起來就像一個單獨的、高可靠的狀態(tài)機。Raft 的論文[3]提到，使用狀態(tài)機我們就能克服上述三個問題：
?滿足在所有非拜占庭條件下確保安全（不會返回錯誤結果），包括網(wǎng)絡延遲、分區(qū)、丟包、重復和重排序。?不依賴于時序。?高可用。只要集群中的大部分節(jié)點正常運行，并能夠互相通信且可以同客戶端通信，這個集群就完全可用。因此，擁有5個節(jié)點的集群可以容忍其中的2個節(jié)點失敗。假使通過停掉某些節(jié)點使其失敗，稍后它們會從持久化存儲的狀態(tài)進行恢復，并重新加入到集群中。
不僅如此，達成共識還可以解決分布式系統(tǒng)中的以下經(jīng)典問題：
?互斥（Mutual exclusion）：哪個進程進入臨界區(qū)訪問資源？?選主（Leader election）：在單主復制的數(shù)據(jù)庫，需要所有節(jié)點就哪個節(jié)點是領導者達成共識。如果一些由于網(wǎng)絡故障而無法與其他節(jié)點通信，可能會產生兩個領導者，它們都會接受寫入，數(shù)據(jù)就可能會產生分歧，從而導致數(shù)據(jù)不一致或丟失。?原子提交（Atomic commit）：跨多節(jié)點或跨多分區(qū)事務的數(shù)據(jù)庫中，一個事務可能在某些節(jié)點上失敗，但在其他節(jié)點上成功。如果我們想要維護這種事務的原子性，必須讓所有節(jié)點對事務的結果達成共識：要么全部提交，要么全部中止/回滾。
總而言之，在共識的幫助下，分布式系統(tǒng)就可以像單一節(jié)點一樣工作——所以共識問題是分布式系統(tǒng)最基本的問題。
系統(tǒng)模型
在考慮如何達成共識之前，需要考慮分布式系統(tǒng)中有哪些可供選擇的計算模型。主要有以下幾個方面：
網(wǎng)絡模型：
?同步（Synchronous）：響應時間是在一個固定且已知的有限范圍內。?異步（Asynchronous）：響應時間是無限的。
故障類型：
?Fail-stop failures：節(jié)點突然宕機并停止響應其它節(jié)點。?Byzantine failures[4]：源自“拜占庭將軍問題” ，是指節(jié)點響應的數(shù)據(jù)會產生無法預料的結果，可能會互相矛盾或完全沒有意義，這個節(jié)點甚至是在“說謊”，例如一個被黑客入侵的節(jié)點。
消息模型：
?口頭消息(oral messages)：消息被轉述的時候是可能被篡改的。?簽名消息(signed messages)：消息被發(fā)出來之后是無法偽造的，只要被篡改就會被發(fā)現(xiàn)。
作為最常見的，我們將分別討論在同步系統(tǒng)和異步系統(tǒng)中的共識。在同步通信系統(tǒng)中達成共識是可行的(下文將會談論這點)，但是，在實際的分布式系統(tǒng)中同步通信是不切實際的，我們不知道消息是故障了還是延遲了。異步與同步相比是一種更通用的情況。一個適用于異步系統(tǒng)的算法，也能被用于同步系統(tǒng)，但是反過來并不成立。
讓我們先從異步的情況開始。
異步系統(tǒng)中的共識
FLP 不可能（FLP Impossibility）
早在 1985 年，F(xiàn)ischer、Lynch 和 Paterson （FLP）在 "Impossibility of Distributed Consensus with One Faulty Process[5]" 證明了：在一個異步系統(tǒng)中，即使只有一個進程出現(xiàn)了故障，也沒有算法能保證達成共識。
簡單來說，因為在一個異步系統(tǒng)中，進程可以隨時發(fā)出響應，所以沒有辦法分辨一個進程是速度很慢還是已經(jīng)崩潰，這不滿足終止性（Termination）。詳細的證明已經(jīng)超出本文范圍，不在細述。
此時，人們意識到一個分布式共識算法需要具有的兩個屬性：安全性(safety)和活性(liveness)。安全性意味著所有正確的進程都認同同一個值，活性意味著分布式系統(tǒng)最終會認同某一個值。每個共識算法要么犧牲掉一個屬性，要么放寬對網(wǎng)絡異步的假設。
雖然 FLP 不可能定理聽著讓人望而生畏，但也給后來的人們提供了研究的思路——不再嘗試尋找異步通信系統(tǒng)中共識問題完全正確的解法。FLP 不可能是指無法確保達成共識，并不是說如果有一個進程出錯，就永遠無法達成共識。這種不可能的結果來自于算法流程中最壞的結果：
?一個完全異步的系統(tǒng)?發(fā)生了故障?最后，不可能有一個確定的共識算法。
針對這些最壞的情況，可以找到一些方法，盡可能去繞過 FLP 不可能，能滿足大部分情況下都能達成共識。《分布式系統(tǒng)：概念與設計》[6]提到一般有三種辦法：
1.故障屏蔽（Fault masking）2.使用故障檢測器（Failure detectors）3.使用隨機性算法（Non-Determinism）
1、故障屏蔽（Fault masking）
既然異步系統(tǒng)中無法證明能夠達成共識，我們可以將異步系統(tǒng)轉換為同步系統(tǒng)，故障屏蔽就是第一種方法。故障屏蔽假設故障的進程最終會恢復，并找到一種重新加入分布式系統(tǒng)的方式。如果沒有收到來自某個進程的消息，就一直等待直到收到預期的消息。
例如，兩階段提交事務使用持久存儲，能夠從崩潰中恢復。如果一個進程崩潰，它會被重啟（自動重啟或由管理員重啟）。進程在程序的關鍵點的持久存儲中保留了足夠多的信息，以便在崩潰和重啟時能夠利用這些數(shù)據(jù)繼續(xù)工作。換句話說故障程序也能夠像正確的進程一樣工作，只是它有時候需要很長時間來執(zhí)行一個恢復處理。
故障屏蔽被應用在各種系統(tǒng)設計中。
2、使用故障檢測器（Failure detectors）
將異步系統(tǒng)轉換為同步系統(tǒng)的第二個辦法就是引入故障檢測器，進程可以認為在超過一定時間沒有響應的進程已經(jīng)故障。一種很常見的故障檢測器的實現(xiàn)：超時（timeout）。
但是，這種辦法要求故障檢測器是精確的。如果故障器不精確的話，系統(tǒng)可能放棄一個正常的進程；如果超時時間設定得很長，進程就需要等待（并且不能執(zhí)行任何工作）較長的時間才能得出出錯的結論。這個方法甚至有可能導致網(wǎng)絡分區(qū)。
解決辦法是使用“不完美”的故障檢測器。Chanadra 和 Toueg 在 "The weakest failure detector for solving consensus[7]" 中分析了一個故障檢測器必須擁有的兩個屬性：
?完全性（Completeness）：每一個故障的進程都會被每一個正確的進程懷疑。?精確性（Accuracy）：正確的進程沒有被懷疑。
同時，他們還證明了，即使是使用不可靠的故障檢測器，只要通信可靠，崩潰的進程不超過 N/2，那么共識問題是可以解決的。我們不需要實現(xiàn) Strong Completeness 和 Strong Accuracy，只需要一個最終弱故障檢測器（eventually weakly failure detector），該檢測器具有如下性質：
?最終弱完全性（eventually weakly complete）：每一個錯誤進程最終常常被一些正確進程懷疑；?最終弱精確性（eventually weakly accurate）：經(jīng)過某個時刻后，至少一個正確的進程從來沒有被其它正確進程懷疑。
該論文還證明了，在異步系統(tǒng)中，我們不能只依靠消息來實現(xiàn)一個最終弱故障檢測器。但是，實際的故障檢測器能夠根據(jù)觀察到的響應時間調節(jié)它的超時值。如果一個進程或者一個到檢測器的連接很慢，那么超時值就會增加，那么錯誤地懷疑一個進程的情況將變得很少。從實用目的來看，這樣的弱故障檢測器與理想的最終弱故障檢測器十分接近。
3、使用隨機性算法(Non-Determinism)
這種解決不可能性的技術是引入一個隨機算法，隨機算法的輸出不僅取決于外部的輸入，還取決于執(zhí)行過程中的隨機概率。因此，給定兩個完全相同的輸入，該算法可能會輸出兩個不同的值。隨機性算法使得“敵人”不能有效地阻礙達成共識。
和傳統(tǒng)選出領導、節(jié)點再協(xié)作的模式不同，像區(qū)塊鏈這類共識是基于哪個節(jié)點最快計算出難題來達成的。區(qū)塊鏈中每一個新區(qū)塊都由本輪最快計算出數(shù)學難題的節(jié)點添加，整個分布式網(wǎng)絡持續(xù)不斷地建設這條有時間戳的區(qū)塊鏈，而承載了最多計算量的區(qū)塊鏈正是達成了共識的主鏈（即累積計算難度最大）。
比特幣使用了 PoW（Proof of Work）來維持共識，一些其它加密貨幣（如 DASH、NEO）使用 PoS（Proof of Stake），還有一些（如 Ripple）使用分布式賬本（ledger）。
但是，這些隨機性算法都無法嚴格滿足安全性(safety)。攻擊者可以囤積巨量算力，從而控制或影響網(wǎng)絡的大量正常節(jié)點，例如控制 50% 以上網(wǎng)絡算力即可以對 PoW 發(fā)起女巫攻擊（Sybil Attack）[8]。只不過前提是攻擊者需要付出一大筆資金來囤積算力，實際中這種風險性很低，如果有這么強的算力還不如直接挖礦賺取收益。
同步系統(tǒng)中的共識
上述的方法 1 和 2，都想辦法讓系統(tǒng)比較“同步”。我們熟知的 Paxos 在異步系統(tǒng)中，由于活鎖的存在，并沒有完全解決共識問題（liveness不滿足）。但 Paxos 被廣泛應用在各種分布式系統(tǒng)中，就是因為在達成共識之前，系統(tǒng)并沒有那么“異步”，還是有極大概率達成共識的。
Dolev 和 Strong 在論文 "Authenticated Algorithms for Byzantine Agreement[9]" 中證明了：同步系統(tǒng)中，如果 N 個進程中最多有 f 個會出現(xiàn)崩潰故障，那么經(jīng)過 f + 1 輪消息傳遞后即可達成共識。
Fischer 和 Lynch 的論文?"A lower bound for the time to assure interactive consistency[10]" 證明了，該結論同樣適用于拜占庭故障。
基于此，大多數(shù)實際應用都依賴于同步系統(tǒng)或部分同步系統(tǒng)的假設。
同步系統(tǒng)中的拜占庭將軍問題
Leslie Lamport、Robert Shostak 和 Marshall Pease 在 "拜占庭將軍問題（The Byzantine General’s Problem)[11]" 論文中討論了 3 個進程互相發(fā)送未簽名（口頭的）的消息，并證明了只要有一個進程出現(xiàn)故障，就無法滿足拜占庭將軍的條件。但如果使用簽名的消息，那么 3 個將軍中有一個出現(xiàn)故障，也能實現(xiàn)拜占庭共識。
Pease 將這種情況推廣到了 N 個進程，也就是在一個有 f 個拜占庭故障節(jié)點的系統(tǒng)中，必須總共至少有 3f + 1 個節(jié)點才能夠達成共識。即 N >= 3f + 1。
雖然同步系統(tǒng)下拜占庭將軍問題的確存在解，但是代價很高，需要 O(N^f+1 ) 的信息交換量，只有在那些安全威脅很嚴重的地方使用（例如：航天工業(yè)）。
PBFT 算法
PBFT(Practical Byzantine Fault Tolerance)[12]?算法顧名思義是一種實用的拜占庭容錯算法，由 Miguel Castro 和 Barbara Liskov 發(fā)表于 1999 年。
算法的主要細節(jié)不再展開。PBFT 也是通過使用同步假設保證活性來繞過 FLP 不可能。PBFT 算法容錯數(shù)量同樣也是 N >= 3f + 1，但只需要 O(n^2 ) 信息交換量，即每臺計算機都需要與網(wǎng)絡中其他所有計算機通訊。
雖然 PBFT 已經(jīng)有了一定的改進，但在大量參與者的場景還是不夠實用，不過在拜占庭容錯上已經(jīng)作出很重要的突破，一些重要的思想也被后面的共識算法所借鑒。
結語
本文參考了很多資料文獻，對“共識問題”的研究歷史做一些基礎概述，希望能對你帶來一點幫助。
本文提到的論文，很多直接談論結果，忽略了其中的數(shù)學證明，一是本文只是提綱挈領的討論共識問題，建立一個知識框架，后續(xù)方便往里面填充內容；二是考慮到大部分讀者對數(shù)學證明過程并不敢興趣，也不想本文變成一本書那么長。本文也遺漏許多重要算法，后續(xù)如有必要會繼續(xù)補充。
限于本人能力，懇請讀者們對本文存在的錯誤和不足之處，歡迎留言或私信告訴我。
下篇我們將會討論 Paxos 算法。
References
[1]?第一篇提到共識問題的文獻:?http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html[2]?Time, Clocks and the Ordering of Events in a Distributed System:?http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf[3]?Raft 的論文:?https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf[4]?Byzantine failures:?https://en.wikipedia.org/wiki/Byzantine_fault[5]?Impossibility of Distributed Consensus with One Faulty Process:?https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf[6]?《分布式系統(tǒng)：概念與設計》:?https://book.douban.com/subject/21624776/[7]?The weakest failure detector for solving consensus:?https://dl.acm.org/doi/10.1145/234533.234549[8]?女巫攻擊（Sybil Attack）:?https://en.wikipedia.org/wiki/Sybil_attack[9]?Authenticated Algorithms for Byzantine Agreement:?https://epubs.siam.org/doi/abs/10.1137/0212045?journalCode=smjcat[10]?A lower bound for the time to assure interactive consistency:?https://www.sciencedirect.com/science/article/abs/pii/0020019082900333[11]?拜占庭將軍問題（The Byzantine General’s Problem):?http://people.cs.uchicago.edu/~shanlu/teaching/33100_wi15/papers/byz.pdf[12]?PBFT(Practical Byzantine Fault Tolerance):?http://pmg.csail.mit.edu/papers/osdi99.pdf
推薦閱讀
站長 polarisxu
自己的原創(chuàng)文章
不限于 Go 技術
職場和創(chuàng)業(yè)經(jīng)驗
Go語言中文網(wǎng)
每天為你
分享 Go 知識
Go愛好者值得關注