4.2　共識算法

共識（consensus）這個術語很多時候會與一致性放在一起討論。嚴謹地講，兩者的含義并不完全相同。

一致性的含義比共識寬泛，在不同場景（基于事務的數據庫、分布式系統等）下意義不同。具體到分布式系統場景下，一致性指的是多個副本對外呈現的狀態。如前面提到的順序一致性、線性一致性，描述了多節點對數據狀態的共同維護能力。而共識，則特指在分布式系統中多個節點之間對某個事情（例如多個事務請求，先執行誰？）達成一致看法的過程。因此，達成某種共識并不意味著就保障了一致性。

實踐中，要保障系統滿足不同程度的一致性，往往需要通過共識算法來達成。

共識算法解決的是，分布式系統中大部分節點對于某個提案（proposal）達成一致意見的過程。提案的含義在分布式系統中十分寬泛，如多個事件發生的順序、某個鍵對應的值、誰是主節點等等。可以認為任何可以達成一致的信息都是一個提案。

對于分布式系統來講，各個節點通常都是相同的確定性狀態機模型（又稱為狀態機復制問題，state-machine replication），從相同初始狀態開始接收相同順序的指令，則可以保證相同的結果狀態。因此，系統中多個節點最關鍵的是對多個事件的順序進行共識，即排序。

1.問題與挑戰

無論是在現實生活中，還是在計算機世界里，達成共識都要解決兩個基本問題：

●如何提出一個待共識的提案？如通過令牌傳遞、隨機選取、權重比較、求解難題等。

●如何讓多個節點對該提案達成共識（同意或拒絕），如通過投票、規則驗證等。

理論上，如果分布式系統中各節點都能以十分“理想”的性能（瞬間響應、超高吞吐）穩定運行，節點之間通信瞬時送達（如量子糾纏），則實現共識過程并不十分困難，簡單地通過廣播進行瞬時投票和應答即可。

可惜的是，現實中這樣的“理想”系統并不存在。不同節點之間通信存在延遲（光速物理限制、通信處理延遲），并且任意環節都可能存在故障（系統規模越大，發生故障可能性越高）。如通信網絡會發生中斷、節點會發生故障、甚至存在被入侵的節點故意偽造消息，破壞正常的共識過程。

通常，把出現故障（crash或fail-stop，即不響應）但不會偽造信息的情況稱為“非拜占庭錯誤（non-byzantine fault）”或“故障錯誤（crash fault）”；偽造信息惡意響應的情況稱為“拜占庭錯誤（byzantine fault）”，對應節點為拜占庭節點。顯然，后者場景中因為存在“搗亂者”更難達成共識。

此外，任何處理都需要成本，共識也是如此。當存在一定信任前提（如接入節點都經過驗證、節點性能穩定、安全保障很高）時，達成共識相對容易，共識性能也較高；反之，在不可信的場景下達成共識很難，需要付出較大成本（如時間、經濟、安全等），而且性能往往較差（如工作量證明算法）。

注意

非拜占庭場景的典型例子是通過報數來統計人數，即便偶有沖突（如兩人同時報一個數）也能很快解決；拜占庭場景的一個常見例子是“殺人游戲”，當參與者眾多時很難快速達成共識。

2.常見算法

根據解決的場景是否允許拜占庭錯誤情況，共識算法可以分為Crash Fault Tolerance（CFT）和Byzantine Fault Tolerance（BFT）兩類。

對于非拜占庭錯誤的情況，已經存在不少經典的算法，包括Paxos（1990年）、Raft（2014年）及其變種等。這類容錯算法往往性能比較好，處理較快，容忍不超過一半的故障節點。

對于拜占庭錯誤的情況，包括以PBFT（Practical Byzantine Fault Tolerance，1999年）為代表的確定性系列算法、以PoW（1997年）為代表的概率算法等。確定性算法一旦達成共識就不可逆轉，即共識是最終結果；而概率類算法的共識結果則是臨時的，隨著時間推移或某種強化，共識結果被推翻的概率越來越小，最終成為事實上結果。拜占庭類容錯算法往往性能較差，容忍不超過1/3的故障節點。

此外，XFT（Cross Fault Tolerance，2015年）等最近提出的改進算法可以提供類似于CFT的處理響應速度，并能在大多數節點正常工作時提供BFT保障。

Algorand算法（2017年）基于PBFT進行改進，通過引入可驗證隨機函數解決了提案選擇的問題，理論上可以在容忍拜占庭錯誤的前提下實現更好的性能（1000tps以上）。

注意

實踐中，對客戶端來說，要拿到共識結果需要自行驗證，典型地，可訪問足夠多的服務節點來比對結果，確保獲取結果的準確性。

3.理論界限

科學家都喜歡探尋問題最壞情況的理論界限。那么，共識問題的最壞界限在哪里呢？很不幸，在推廣到任意情況時，分布式系統的共識問題無通用解。

這似乎很容易理解，在多個節點之間的通信網絡自身不可靠情況下，很顯然，無法確保實現共識（例如，所有涉及共識的消息都丟失）。那么，對于一個設計得當、可以大概率保證消息正確送達的網絡，是不是一定能獲得共識呢？

理論證明告訴我們，即便在網絡通信可靠情況下，一個可擴展的分布式系統的共識問題通用解法的下限是——沒有下限（無解）。

這個結論稱為“FLP不可能原理”。該原理極其重要，可以作為分布式領域里的“測不準原理”。

注意

不光分布式系統領域，實際上很多領域都存在類似“測不準原理”的約束，這或許說明世界本源就存在限制。