瞭解分散式系統的工作原理對區塊鏈世界非常重要。那麼現在，就讓我們開啟分散式系統的探索之旅吧。
計算機的作用是處理資訊，我們輸入條件 A 給它，它輸出結果 B 給我們。如果處理資訊的工作是由一臺計算機完成的，這是一種中心化的結構；如果處理資訊的工作是由多臺獨立的計算機合作完成的，我們可以稱其為「分散式的系統」。
分散式系統有多種不同的架構，用以實現不同的處理資訊的方法。假設系統中有十臺計算機，一種架構是：我們把一個計算任務分成十份，讓每臺計算機獨立處理一份任務，最後彙總它們的計算結果，作為輸出。
還有另一種架構，就是讓這十臺計算機都去處理這一個計算任務，如果所有的計算機都正常工作，它們的計算結果應該是一樣的，那麼就把這個一致的計算結果作為輸出。區塊鏈就是這樣的一種分散式系統。
很容易就能發現，這是一個「自找苦吃」的系統，它相當於把同樣的工作做了十次，而且還需要額外增加不同計算機之間的溝通工作。
那為什麼還需要這種系統？因為它可以讓我們免除對中心化的那一臺計算機，以及那臺計算機背後的中心化的公司或組織的依賴。這樣一來，既能避免單點故障或作惡，也能減少權力的集中及濫用。
一、分散式系統的理想目標
區塊鏈所屬的分散式系統也被稱為「複製狀態機模型」（Replicated State Machine），它的目標很簡單：系統內全部的計算機都同意某一個輸出值，也就是指：系統內所有的節點 / 計算機都有相同的初始狀態，在執行完一個事務後，所有的節點都有相同的最終狀態 。
如果計算機都執行良好，它們之間的通訊也完全同步，實現這個目標並不困難。但現實不是如此，主要有以下兩類問題：
1. 某臺 / 某些計算機出現故障，它可能無法計算出結果，也可能連線不上系統。
2. 如果不同計算機收到事件的順序不同，對事件的處理順序就會不同，導致輸出結果也不同。比如（a+b）×c 與 a+（b×c）就是兩種不同的計算順序，會帶來不同的計算結果。
這些問題是常見且不可避免的，而一旦出現問題，就無法實現全部的計算機都同意某一個輸出結果。著名的分散式系統「FLP 不可能原理」是這樣描述的：在網路可靠，但允許節點失效的最小化非同步模型系統中，不存在一個可以解決一致性問題的確定性共識演算法。通俗而言就是：只要系統中有一臺計算機出問題，該系統就無法在輸出值上達成共識。
FLP 不可能原理告訴我們：不要浪費時間去為分散式系統設計面向所有場景的共識演算法，那是不可能實現的。
二、分散式系統的共識演算法
雖然 FLP 不可能原理很殘酷，但分散式系統能夠帶來的好處是值得我們迎難而上的。既然不存在面向所有場景的共識演算法，那麼也許可以找到一些在特定場景中有效的共識演算法。共識演算法，是指讓分散式系統達成共識的方法。
讓我們看看科學家們是如何一步一步限定場景，並實現該場景下的共識演算法的。
首先，如果系統中的每一臺計算機都可以提出自己的結果，場面無疑是複雜的，因為我們連就哪一個結果去達成共識都無法知曉。所以解決共識問題的第一步是確定共識的到底是什麼，最簡單的方法就是某一臺計算機說了算，它提出一個結果，其他的計算機來表態是否同意這個結果。
說了算的那臺計算機被稱為提案者或者領導者。雖然透過領導者來實現共識並不是唯一解決問題的方法，但絕大多數協議都是在此基礎上實現的，包括區塊鏈系統中使用的共識演算法。
所以你看，並沒有絕對的去中心化，實現共識的第一步就是要確定一箇中心。
題外話：當我們知道這一點後，就能建立起關於去中心化的更有效的討論，比如在此處就可以不泛泛而談去中心化，而是：選出這個領導者的方法是否去中心化。
回到主題。需要領導者的共識演算法的工作步驟大致是這樣的：
1. 選出一個領導者；
2. 領導者提出一個結果；
3. 追隨者確定是否同意這個結果；
4. 如果大家就結果達成了共識，系統輸出最終結果；如果大家未達成共識，回到步驟 1 重新開始。
這種思路提供了一種可以達成共識的方法，但它離真正實現共識還很遙遠。因為如果一臺計算機連線不上系統，它就無法表決自己是否同意領導者的結果；如果出現問題的計算機恰好是領導者，情況就會更糟糕，整個系統會進入停滯狀態。
三、同步性假設共識演算法
如何解決上述宕機的問題？方法說起來很簡單：如果一臺計算機連不上系統，就忽略它，不要它參與這一輪的共識。
那麼新的問題來了，我們怎麼知道它是連線不上系統，還是它正在參與共識只不過速度比別的機器慢？
因此，科學家們發展出瞭解決共識問題的最重要的一個假設：同步性假設。同步性假設引入「超時」概念，也就是說事先設定一個時間範圍，如果領導者無法在該時間範圍內發出提案，就淘汰它，選出一個新的領導者。這樣一來就可以容忍領導者節點出現問題。（注：同步性假設不等於同步假設）
Paxos 演算法和 Raft 演算法都是基於同步性假設提出來的。但這兩個演算法還需要對系統做另一種假設，即認為系統內所有的計算機都是「好人」，它們要麼正確地響應領導者的提案，要麼因為故障無法響應。
然後再製定一條規則：只要系統內過半數的計算機接受了領導者的提案，就把該提案作為系統的最終結果。這樣一來，就不用等待所有的計算機都做出響應，從而可以容忍追隨者節點出現問題。
於是，我們終於擁有了一個可以實現共識的分散式系統，雖然對它有嚴格的條件限定。
Paxos 共識演算法是由萊斯利·蘭伯特（Leslie Lamport）在 1990 年提出的一種基於訊息傳遞且具有高度容錯特性的一致性演算法，它在分散式系統應用領域有著重要的地位，包括 Google 在內的許多公司的大型分散式系統採用的都是該演算法。而我們第一階段的探索也可以在此處結束，接下來是第二階段。
四、解決掉系統中的「壞人」
Paxos 雖然能實現共識，但它的演算法是建立在所有計算機都是「好人」的基礎上的，這些計算機要麼沉默，要麼發出正確的聲音，因此整個系統中只有一種聲音，大家就這個聲音達成共識即可。而如果計算機中有「壞人」，系統裡就會出現壞人的聲音和好人的聲音，Paxos 演算法無法處理這一情況。
我們需要在有壞人的情況下也可以實現共識的演算法，有沒有可能？萊斯利·蘭伯特建立了一個模型來討論這種可能性，該模型被稱作拜占庭將軍問題，其中的拜占庭節點就是壞人節點，它們會傳遞干擾資訊阻礙整個系統達成共識。
在論文《The Byzantine Generals Problem》中，蘭伯特提出了幾種解決方案，其中一種可以在拜占庭節點不到 1/3 時實現系統的共識。也就是說，如果系統中壞人的數量少於 1/3，就可以透過演算法實現共識。
這之後出現的 DLS 演算法、PBFT 演算法（實用拜占庭容錯演算法）都是在此基礎上發展出來的。
PBFT 是具有代表性的一種拜占庭容錯演算法，其實現過程大致如下。不理解該過程也沒關係，知道透過這種溝通方式能夠達成共識就可以。
1. pre-prepare 階段：領導者傳送結果給所有追隨者。領導者在本圖中是 0 號節點，它把結果發給追隨者 1、2、3 號節點。
2. prepare 階段：如果追隨者認為結果沒有錯誤，就告訴所有其他節點自己認可這個結果。比如 1 號節點會把自己的認可訊息發給 0、2、3 號節點。
3. commit 階段：如果追隨者發現超過 2/3 的節點認可了領導者的結果，就告訴所有其他節點自己接受這個結果為最終結果。
4. reply 階段：如果領導者和追隨者發現超過 2/3 的節點接受了最終結果，就可以認為大部分節點達成了共識，就把該共識反饋給客戶端；如果客戶端收到超過 1/3 的節點的相同的共識，就可以認為全網達成了共識。
到此，我們就解決了有拜占庭節點的分散式系統的共識問題。不過如果系統中壞人的數量等於或多於 1/3，依然是無法達成共識的。我們能做的是透過系統的准入條件或激勵措施，讓壞人可以少於 1/3。
對分散式系統的第二階段的探索到這裡就結束了，接下來進入到第三階段。
五、中本聰共識演算法
不管 Paxos 還是 PBFT，都使用了同步性假設，事實上，大家對共識演算法的研究幾乎都是在該方向上的，直到中本聰共識的出現。中本聰共識使用的是非確定性機制。
這是什麼意思呢？我們可以把一個由 12 臺計算機組成的分散式系統想象成一個由 12 名陪審員組成的陪審團。我們把這 12 個人關在會議室裡，遞進去一張紙條闡述案情，然後坐在會議室門口等他們給出審理的結果。
這 12 個人對於如何判決會有不同的意見，隨著討論的深入也可能改變自己的立場，還有的人可能睡著了無法發表看法（參考《十二怒漢》）。那麼坐在門口等的人有兩種選擇。第一種選擇是你們去討論吧，讓我等多久都可以，但最後你們給我的必須是唯一確定的審理結果；第二種選擇是我等不了，你們先把最多人同意的那個結果給我，如果之後出現一個更多人同意的結果，我再改成那個結果。
顯而易見，我們只能二選一，如果要求結果確定，就不能保證一定能等到結果；如果要求拿到結果，就無法保證該結果一定是最終結果。
分散式系統就是這樣，只能二選一，第一種選擇被稱作 Finality，即「結果的確定性」或安全性；第二種選擇被稱作 Liveness，即網路的活性或可用性。
這兩種選擇決定了分散式共識兩種不同的設計思路：
1. 追求 Finality，是優先結果，就要對網路做出要求。PBFT、Tendermint 都是這一型別的演算法，它們走的是網路的同步性假設路線，使用這類演算法的系統不會出現分叉。
2. 追求 Liveness，是優先網路，就要對結果做出讓步。中本聰共識是這一型別的演算法，它走的是結果的非確定性路線，使用這類演算法的分散式網路始終可用，而且任意節點都可以隨時加入 / 離開系統。
題外話，在 Finality 和 Liveness 中二選一也是分散式系統 CAP 定理（不可能三角）的體現。該定理說的是：對於一個分散式系統來說，不可能同時滿足一致性、可用性和分割槽容錯性。因為分割槽容錯性是指該系統要能容忍網路出現分割槽，而現實網路是一定會分割槽的，所以這個條件必須滿足，那麼實際上，CAP 定理說的是一個分散式系統不可能同時滿足一致性和可用性，這其中，CAP 一致性體現的是 Finality，CAP 可用性體現的是 Liveness。
而不管是 FLP 不可能原理，還是 CAP 不可能定理，它們不是在告訴我們：這條路很難走通，你如果突破就是了不起的創新；它們告訴我們的是：這條路走不通，你要做的是根據需求來做權衡和選擇。
使用同步性假設的共識演算法在前文已經詳細地介紹過了，它們透過引入超時概念忽略出現問題的計算機，從而達成共識。
使用非確定性機制的中本聰共識描述起來也很簡單：如果你看到某提議的區塊擁有最多的工作量證明，就接受該區塊，這也被稱作最長鏈規則。它的具體實現過程大家都很熟悉，本文就不再贅述了。
現在，讓我們看看使用同步性假設的系統（Finality，PoS 中使用較多）和使用非確定性機制的系統（Liveness，PoW 中使用較多）有什麼不同。但需要提醒的是，並非所有的 PoS 都是 Finality 路線，比如 Casper FFG 就不是；而 PoW 也不是隻能走 Liveness 路線，雖然並沒有人設計 PoW 上的 Finality 共識。
PoW 和 PoS 的不同在於一個是 Work，一個是 Stake。之所以需要強調這一點，是因為在關於 PoW 和 PoS 的討論中，我們往往不是在討論 Work 機制與 Stake 機制的不同，而是在比較 Finality 系統與 Liveness 系統的不同。比如「無需許可」性，它基本是一個 Finality 系統與 Liveness 系統的話題，而不是 Work 與 Stake 的爭論點。
讓我們回到有 12 個評審員的會議室。為了追求 Finality，每個評審員都需要了解其他每一個人的想法，也需要把自己的想法告訴其他每一個人，因此通訊複雜度會隨著評審員人數的增加而迅速遞增，整個系統將因此不可用，所以必須控制陪審員的數量。
那麼對於一個分散式系統而言就是，只挑選少數節點進入會議室，由它們決定共識，而其他節點只接受共識。因此這種系統中有三種角色，領導者、追隨者和學習者，領導者和追隨者是會議室中的評審員，他們需要好好工作，不然可能導致系統無法達成共識。
中本聰共識追求的是 Liveness，節點 / 評審員不需要與其他的每一個節點溝通，它只需要與自己身邊的節點交流即可，因此通訊複雜度不會因為節點數量的增加而增加。你想成為評審員，就可以走進會議室成為評審員，無需許可，也不會增加陪審團達成共識的難度，同時你也可以不工作或隨時離開。該系統中只有領導者和追隨者兩種角色，所有人都在那間會議室裡參與共識。
這樣看來中本聰共識似乎更符合大家對分散式系統的開放性的期望，但別忘了它之所以可以如此設計，是因為犧牲了 Finality，它的輸出結果是一個概率上的最終結果。
試想，你百分百在星巴克得到一杯咖啡，但星巴克並不能百分百收到錢，這並不符合大多數人能理解的世界運轉規則。所以非確定性機制有它自己的短板，以及不適合的場景。
另一方面，Finality 系統在保證了結果的確定性後，系統設計就要反過來追求 Liveness；而 Liveness 系統在保證了網路的開放性後，系統設計就要反過來追求 Finality。中本聰共識為了提高結果的確定性或安全性，就需要做出其他讓步，比如 TPS。
以比特幣為例。比特幣可以把出塊時間從 10 分鐘提高到 1 分鐘，TPS 會大幅提升，但 1 分鐘的時間不夠把訊息傳遍全網，系統中就會出現很多分叉，導致結果的可確定性變低；比特幣也可以把區塊大小從 1MB 提高到 100MB，TPS 也會提升，但大區塊對網路和節點的要求高，會增加節點的進入門檻從而帶來中心化，導致輸出結果容易被篡改。
所以你看，設計分散式系統就像與撒旦做交易，你得到一些，必然要交出一些。沒有最好的系統，只有適合解決某類問題的系統；沒有單純的指標比較，只有是在什麼設定下實現這種指標。
如果你理解了這一點，這篇文章的目的就達到了，而我們對分散式系統的探索到此也就全部結束了。
六、更進一步
本文是受《How Does Distributed Consensus Work?》一文啟發寫成的，如果你想更進一步瞭解分散式系統，推薦這篇文章，它從專業的角度介紹了分散式共識；同時推薦《WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS》，它系統地羅列出了分散式系統的經典論文。
鏈聞注：
- How Does Distributed Consensus Work?
https://medium.com/s/story/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95
- 中文譯本《分散式共識的工作原理》，by EthFans
https://ethfans.org/posts/lets-take-a-crack-at-understanding-distributed-consensus-part-1
- WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS
http://alvaro-videla.com/2015/12/learning-about-distributed-systems.html
分散式系統的另一個關鍵問題是時序，所有的共識演算法都需要解決它，但因為是另一條線索故本文未做涉及，如果你想了解，可以從萊斯利·蘭伯特博士（how old are you）的這篇論文開始：《Time, Clocks and the Ordering of Events in a Distributed System》。
如果你對在 Finality 和 Liveness 間尋找平衡感興趣，可以去研究 Casper FFG 共識，它有 Liveness 的一部分，也有 Finality 的一部分。同時你也會發現 Casper FFG 的 PoS 與 Tendermint 的 PoS 的不同。
最後對本文做一個小結，它主要包含以下內容：
兩個定理：FLP 不可能原理；CAP 不可能定理。
兩種容錯能力：宕機容錯；拜占庭容錯。
兩種共識演算法設計思路：Finality；Liveness。
兩類共識演算法：同步性假設；非確定性機制。
三個共識演算法：Paxos、PBFT、中本聰共識。
文中會有因簡化和類比帶來的不準確以及不全面之處，還望理解，謝謝指正。
參考資料：
1.《How Does Distributed Consensus Work?》，Preethi Kasireddy；中文版本：《分散式共識的工作原理》，by EthFans，由 Ray、阿劍、IAN LIU、stormpang、安仔翻譯
2.《WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS》，Alvaro Videla
3.《Time, Clocks and the Ordering of Events in a Distributed System》，Leslie Lamport
4.《The Byzantine Generals Problem》，LESLIE LAMPORT、ROBERT SHOSTAK、MARSHALL PEASE
5.《Paxos Made Simple》，Leslie Lamport
6.《Bitcoin: A Peer-to-Peer Electronic Cash System》，Satoshi Nakamoto
