共識算法

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

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

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

共識算法解決的是分佈式系統對某個提案（Proposal），大部分節點達成一致意見的過程。提案的含義在分佈式系統中十分寬泛，如多個事件發生的順序、某個鍵對應的值、誰是主節點……等等。可以認為任何可以達成一致的信息都是一個提案。對於分佈式系統來講，各個節點通常都是相同的確定性狀態機模型（又稱為狀態機複製問題，State-Machine Replication），從相同初始狀態開始接收相同順序的指令，則可以保證相同的結果狀態。因此，系統中多個節點最關鍵地是對多個事件的順序進行共識，即排序。

問題與挑戰

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

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

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

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

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

一般地，把出現故障（Crash 或 Fail-stop，即不響應）但不會偽造信息的情況稱為“非拜占庭錯誤（Non-Byzantine Fault）”或“故障錯誤（Crash Fault）”；偽造信息惡意響應的情況稱為“拜占庭錯誤”（Byzantine Fault），對應節點為拜占庭節點。顯然，後者場景中因為存在“搗亂者”更難達成共識。

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

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

常見算法

根據解決的場景是否允許拜占庭錯誤情況，共識算法可以分為 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 進行改進，通過引入可驗證隨機函數解決了提案選擇的問題，理論上可以在容忍拜占庭錯誤的前提下實現更好的性能（1000+ TPS）。

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

理論界限

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

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

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

這個結論，被稱為“FLP 不可能原理”。該原理極其重要，可以看做是分佈式領域裡的“測不準原理”。

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