從 Paxos 到拜占庭容錯，兼談區塊鏈的共識協議

文章來源： 數據極客

高可用架構在分佈式系統設計中是最核心的挑戰之一，拜占庭容錯則是解決高效容錯問題的通用方案。

拜占庭系統來源於拜占庭將軍問題，在古代，一些拜占庭的將軍率領他們的部隊要攻佔敵人的一個城池 , 每個將軍只能控制他們自己的部隊並且通過信使傳遞消息給其他的將軍 (這條消息只有參與的兩個將軍知道，其他的將軍可以打聽，但是不能驗證消息的正確性)。如果這些將軍中有些是來自敵方的奸細，那麼如何使忠誠的將軍仍然可以達成行動協議而不受奸細的挑撥，就是拜占庭將軍問題。分佈式系統的每一個節點可以類比成將軍，服務器之間的消息傳遞可以類比成信使，服務器可能會發生錯誤而產生錯誤的信息傳達給其他服務器。因此拜占庭容錯系統是指：在一個擁有 n 臺服務器的系統中，整個系統對於每一個請求需滿足以下兩個條件：

所有非拜占庭服務器使用相同的輸入信息，產生一致的結果；

如果輸入的信息正確，那麼所有非拜占庭服務器必須接受這個信息，並計算相應的結果。

其中，發生故障的服務器稱爲拜占庭服務器。這兩個條件被稱爲共識 Consensus，它是分佈式系統容錯處理的最基礎問題。在拜占庭系統的實際運行過程中，一般假設整個系統的拜占庭服務器不超過 f 臺，並且每個請求還需要滿足同時兩個指標：

• safety：任何已經完成的請求都不會被更改 , 它可以被之後請求看到 ;
• liveness：可以接受並且執行非拜占庭客戶端的請求，不會被任何因素影響而導致非拜占庭客戶端的請求不能執行。

在實際網絡中，拜占庭系統需要指數級的算法才能解決，隨着大規模分佈式系統尤其是雲計算的興起，通過放鬆 liveness 來提高性能的簡化拜占庭協議也不斷湧現並在具體系統中得到運用，例如 PBFT ，Paxos，Raft 等等。從目前研究現狀來看，拜占庭系統的設計主要分爲狀態機拜占庭協議和 Quorum 拜占庭協議。兩種協議在功能上的主要區別在於：前者需要給所有的請求安排序號，所有請求必須按順序執行，主要用於對於系統狀態敏感的分佈式計算系統中；後者不需要爲請求安排序號，多個請求可以同時執行，主要被應用於分佈式存儲系統中。拜占庭容錯技術的研究方向主要是降低系統開銷 , 縮小與目前實際應用中的系統之間的差距。

狀態機拜占庭系統的特點是整個系統共同維護一個狀態，所有服務器採取一致的行動，包含三種協議：一致性協議 agreement，檢查點協議 checkpoint，視圖更換協議 view change。

一致性協議的目標是使來自客戶端的請求在每個服務器上都按照一個確定的順序執行。一般有一個節點作爲主節點，負責將客戶端的請求排序，其餘是從節點，按照主節點提供的順序執行請求。所有的服務器在相同的配置信息下工作，這個配置信息稱爲 view，每更換一次主節點，view 隨之發生變化。一致性協議包含至少三個階段，發送請求 request，序號分配 pre-prepare，和返回結果 reply。根據協議設計不同，還可能會包含交互 prepare，序號確認 commit 等階段。

拜占庭系統每執行一個請求，服務器需要記錄日誌。如果日誌得不到及時的清理，就會導致系統資源被大量的日誌所佔用，影響系統性能及可用性。另一方面，由於拜占庭服務器的存在，一致性協議並不能保證每一臺服務器都執行了相同的請求，所以 , 不同服務器狀態可能不一致。週期性的檢查點協議可以定期地處理日誌，及時糾正服務器狀態。

一旦主節點自身發生錯誤，就可能導致從節點接收到具有相同序號的不同請求，或者同一個請求被分配多個序號等問題，這將直接導致請求不能被正確執行。視圖更換協議的作用就是在主節點不能繼續履行職責時，將其用一個從節點替換掉，並且保證已經被非拜占庭服務器執行的請求不會被篡改。

Castro 和 Liskov[4] 早先提出了 Practical Byzantine Fault Tolerance(PBFT)，首次將拜占庭協議的複雜度從指數級降低到多項式級別，使拜占庭協議在分佈式系統中應用成爲可能。這個算法可以在異步網絡中不保證 liveness 的情況下解決拜占庭容錯問題。 雖然不保證 Liveness，但是這個算法進入無限循環的概率非常低，在工程中是完全可用的。爲此 Barbara Liskov 獲得了 2008 年代圖靈獎。PBFT 採取兩個假設提供狀態複製：

1. 系統中只有一小部分數目可能是拜占庭服務器
2. 系統依賴佔據主導的選舉來達成共識，確保結果正確

如果系統中有 3f+1 個節點，那麼 PBFT 可以容忍拜占庭服務器不超過 f 個。簡單解釋一下原因：假設有三個將軍 , 只有一個叛徒。如果 A 是叛徒，那麼 A 可能會給 B 發出進攻，然後給 C 發出撤退的命令。當 B 和 C 互相同步信息的時候他們會發現兩個不一致的信息。但是 B 和 C 誰也無法判斷誰是叛徒，比如從 B 的角度來看，他無法判斷 A 是叛徒或者 C 是叛徒。所以三個將軍裏有一個叛徒是無法解決的。爲了確保正確，PBFT 兩兩交互確定交集後才能確定一個非叛徒：因此由-(N-f)＋(N-f)-N>=f+1 推導出 N>=3f+1。

PBFT 的一致性協議如下圖所示，每一個客戶端的請求需要 5 個階段才能完成。PBFT 通過採用兩次兩兩交互的方式在服務器達成一致之後再執行客戶端的請求，由於客戶端不能從服務器端獲得任何服務器運行狀態的信息，因此 PBFT 協議中主節點是否發生錯誤只能由服務器監測。如果服務器在一段時間內都不能完成客戶端的請求，則會觸發視圖更換協議。

PBFT 採取的設計思路是將所有的工作都放在服務器端進行，例如達成一致性，監測拜占庭主節點等。因此，它的一致性協議設計較複雜，其中有兩個階段需要服務器之間的兩兩交互，數據處理量大，計算複雜。

PBFT 在很多場景都有應用，例如 Liskov 曾經把它用於一種 NFS 的實現，最近一個熱門的應用是在 IBM 主導的區塊鏈超級賬本項目中，除了 PBFT 之外，超級賬本項目還引入了基於 PBFT 的自用共識協議 Sieve[5]，它的目的是希望在 PBFT 基礎之上能夠對節點的輸出也做好共識，這是因爲超級賬本項目的一個重要功能是提供區塊鏈之上的智能合約——就是在區塊鏈上執行的一段代碼，因此它會帶來區塊鏈賬本上最終狀態的不確定，爲此 Sieve 會在 PBFT 實現的基礎之上引入代碼執行結果簽名進行驗證。

狀態機拜占庭系統同一時刻只能執行一個請求，因此服務器之間執行請求順序要求完全一致。而在許多分佈式存儲系統中，應用通常不要求嚴格的執行順序，但對響應時間很敏感，因此人們提出 Quorum 拜占庭系統。Quorum 系統是指共享數據存儲在一組服務器上，通過訪問服務器的一個大小恆定的子集 (quorum) 來提供讀 / 寫操作。這類協議都含有一個特性：規定訪問的子集大小後，任何一個這樣的子集都包含最新的數據，並且一定可以讀出來。Quorum 拜占庭系統則是在此基礎上保證在服務器出現拜占庭錯誤時，系統的一致性語義仍然成立。這一類系統寫操作過程是：首先，客戶端 c 從某一個大小恆定的服務器子集 Q 中讀取時間戳 A，客戶端 c 從可用時間戳 t 中選取大於任何一個 A 中的時間戳並且大於所有 c 使用過的時間戳；然後，客戶端 c 發送 (v,t) 給所有服務器 (v 爲需更新數據，t 爲時間戳)，直到收到某一個大小恆定的服務器子集的反饋信息。這一類系統讀操作過程是：客戶端 c 獲得某一個恆定大小的服務器子集 Q 中所有服務器返回的最新數據信息；然後，c 按照具體協議要求從中選取需要的數值。

把拜占庭容錯系統的場景放鬆，不允許系統中出現叛徒（也就是說沒有黑客攻擊，不會出現僞造消息等情況），這樣對於數據中心分佈式系統構建是普遍情況。Paxos 是第一個適用於這種系統的共識算法，但不適用於拜占庭容錯系統（Byzanetine Paxos 除外）。Paxos 運行在稱爲副本的一組進程集合，這些進程需要在即使發生錯誤的情況下也能在某一個值上達成一致，如果半數以上的副本在足夠長的時間內沒有發生 crash，那麼所有運行中的副本將可以在某個提出的 value 上達成一致：在狀態機複製中，這意味着需要在“(多副本) 日誌中的下一條記錄是哪條”上達成一致。

借用吳鏑的圖說明下 Paxos 過程：Paxos 分爲 Prepare 和 Accept 兩個階段。協議中有兩個主要的角色，Proposer 和 Acceptor。value 被大多數接受之前，每個 Acceptor 可以 accept 多個不同的值。但是，一旦一個 value 被 majority accept(即 value 達成一致)，那麼這個 value 就不會變了。因爲 Prepare 階段會將該 value 給找出來，隨後 Accept 階段會使用這個 value，後續的所有的提案都會選擇這個 value。 需要注意的是，每個階段都是收到 majority 的響應後即開始處理。並且由於機器會宕機，Acceptor 需要對 acceptedProposalID，acceptedValue 和 minProposal 進行持久化。 從流程中可以看出 Prepare 有兩個作用 :
1. 大的 proposal id 會 block 未完成的小的 proposal id 達成一致的過程，所以爲了減少無效的 Prepare 請求，每次都選擇比自己以往見過的 proposal id 更大的 id。
2. 一旦某個 value 達成一致，那麼後續的 Prepare 都會找到這個 value 作爲 accept 階段的值可以看出，一次 Paxos 達成一致至少需要兩次網絡交互。

Paxos 並不適合於拜占庭容錯系統，例如下圖中，N2 服務器僞造數據，就會讓 Paxos 系統無法達成共識。

Zab(ZooKeeper 採用的協議) 是一個 Paxos 變種協議，它名字中的 AB 是原子多播的意思，因爲 Zab 能夠讓系統裏每個節點按照同樣順序執行同樣操作。原子多播和一致性選舉被認爲是等價問題 [3]。Raft 是近幾年出現的一致性選舉協議，在完成 Paxos 等價的正確性和性能的基礎上更加容易理解。從上圖可以看到，Zab 和 Raft 都有一個專門步驟用於選舉出一個 Primary Leader，兩者均把要解決的一致性問題分解爲一系列獨立的子問題：Leader 選舉，日誌複製，以及安全和其他活動。Leader 的變化，在 Zab 和 Raft 中分別由 epoch 和 term 表示，每次 Leader 選舉都會增加 epoch 或者 term 的值，因此所有的節點只接受 epoch 或者 term 值高的 Leader 節點，在 Leader 選舉之後，由 Leader 提議所有副本按照統一順序進行操作。

在所有 Paxos 類協議中，每個值 (就是提案) 實質上就是一條日誌記錄，記錄由兩部分標記，在 Paxos 中叫做 slot 和 ballot，在 Zab 中叫 epoch 和 counter，在 Raft 中叫 term 和 index。當 Leader 針對當前日誌廣播提案時，跟隨者依據法定多數 (Quorum) 選舉，並且在 Leader 提交後在本地應用該提案。所有的 Paxos 類協議都是保障全局順序的。

上面講述了這些 Paxos 類協議的相似之處，那麼它們在設計上也有一些差別。首先是 Leader 選舉，Zab 和 Raft 都把執行分作階段來進行 (epoch 或 term)，而 Paxos 沒有。每個 epoch 都從一次新的選舉開始，接下來是廣播，然後以 Leader 失敗作爲結束。在 Zab 和 Raft 中，任何時刻至多隻能有一個 Leader，而 Paxos 則沒有如此要求，因爲 Paxos 並沒有獨立的 Leader 選舉階段，因此 Paxos 系統會存在多個 Leader，然而它仍然可以保證正確，這是由 ballot 的數字以及 Quorum 決定的。Zab 協議中有三個階段，每個節點在任何時刻都處於這三個階段中的某一個。發現階段就是 Leader 選舉；隨後是同步階段，跟隨者按照新 Leader 自上一次 epoch 以來所有的日誌進行同步；最後是廣播階段，也就是上圖中的正常工作模式 (normal operation)，Leader 持續提交客戶決議直至它失效。在 Raft 中，沒有明顯的同步階段，Leader 在正常工作模式下跟每個跟隨者保持同步，這通過比較每條日誌的 index 和 term 來做到。因此，Raft 的狀態更爲簡單一些。

其次的差別在於副本之間的通信機制。Zab 採用消息模型，每次更新都需要至少三個消息：提議，確認，和提交，如上圖所示，而 Raft 則依賴 RPC。

Paxos 系統在構建分佈式系統有一些典型應用場景：首先最容易想到的是 Server 複製，利用狀態機複製可以同步多個 Server 之間的狀態。其次是元數據複製，由於 Paxos 系統通常不能操作大量數據，因此一些元數據複製會基於 Paxos 來進行，比如 Apache BookKeeper 系統和 Kafka。第三種是同步服務，例如各種分佈式鎖。第四種叫攔阻器編排，例如在分佈式圖處理框架中，基於 BSP 的模型需要大量攔阻器來進行同步，這通常也由 Paxos 系統進行，例如 Apache Giraph 和 Hama，以及 Google Pregel 等。

無論是 Paxos 還是 Raft 算法，理論上都可能會進入無法表決通過的死循環 (儘管這個概率其實是非常非常低的)，但是他們都是滿足 safety 的，只是放鬆了 liveness 的要求 , PBFT 也是這樣。

通常的基礎架構中，掌握 Paxos 協議就已經能夠應對所有的高可用設計挑戰，然而隨着比特幣和區塊鏈的熱門，Paxos 應用的環境就逐漸不再適合，因爲隨着去中心化網絡的引入，分佈式系統不再全是可以相信的，因此對於共識算法的需求更加多樣，共識算法可以說是區塊鏈爲數不多的核心技術之一。目前，區塊鏈應用分爲三類：

• 私有鏈：這是指在企業內部部署的區塊鏈應用，所有節點都是可以信任的；
• 聯盟鏈：半封閉生態的交易網絡，存在不對等信任的節點；
• 公有鏈：開放生態的交易網絡，爲聯盟鏈和私有鏈等提供全球交易網絡。

由於私有鏈是封閉生態的存儲系統，因此採用 Paxos 類系統可以達到最優的性能；聯盟鏈有半公開半開放特性，因此拜占庭容錯是適合選擇之一，例如 IBM 超級賬本項目；對於公有鏈來說，這種共識算法的要求已經超出了普通分佈式系統構建的範疇，再加上交易的特性，因此需要引入更多的安全考慮。

例如比特幣採用的工作量證明 PoW，就是第一種適用於公有鏈的共識算法。公有區塊鏈中，參與到系統中的每個節點都是中心，都存放一份完整的交易賬本系統。然而，每個節點卻不能同時記賬，因爲節點所處的環境不同，接收到的信息自然不同，如果同時記賬的話，必然會導致賬本的不一致，造成混亂。既然節點不能同時記賬，那就不得不選擇哪個節點擁有記賬的權力。但是，如果指定某些特殊節點擁有記賬的權力，勢必又會與去中心化的初衷相違背。比特幣區塊鏈通過競爭記賬的方式解決了去中心化的記賬系統的一致性問題。所謂競爭記賬，就是以每個節點的計算能力即“算力”來競爭記賬權的一種機制。在比特幣系統中，大約每十分鐘進行一輪算力競賽（算力大小會決定贏得一輪競爭的概率，算力高的節點贏得算力競爭的概率更大），競賽的勝利者，就獲得一次記賬的權力，這樣，一定時間內，只有競爭的勝利者才能記賬並向其他節點同步新增賬本信息，這就是工作量證明。除了工作量證明之外，還有一些其它的共識算法，主要是解決 PoW 浪費計算資源，以及吞吐量低下的缺點。例如 PoS 股權證明機制，基本概念是產生區塊的難度應該與在網絡裏所佔的股權 (所有權佔比) 成比例；去中心化股權證明機制 DPoS，每個股東可以將其投票權授予一名代表，獲票數最多的前 100 位代表按既定時間表輪流產生區塊。

因此，設計區塊鏈，需要在吞吐量，安全等方面做出適合自己的 trade off，來選擇恰當的共識算法。從區塊鏈的角度來說，Paxos 和 PoW 可以說是 trade off 的兩個極端 [6]，而着力於通用區塊鏈的超級賬本選取了 PBFT 也就不難理解了。

[1] Paxos made live: an engineering perspective, Tushar Chandra, Robert Griesemer and Joshua Redstone, ACM Symposium on Principles of Distributed Computing, 2007
[2] Consensus in the Cloud: Paxos Systems Demystified, Ailidani Ailijiang, Aleksey Charapko† and Murat Demirbas, Technical Report 2016
[3] Unreliable failure detectors for reliable distributed systems, T. Chandra and S. Toueg, Journal of the ACM, vol. 43, no. 2, 1996.
[4] Practical Byzantine fault tolerance and proactive recovery, Castro, Miguel and Liskov, Barbara, ACM Transactions on Computer Systems (TOCS), 2002
[5] Non-determinism in Byzantine Fault-Tolerant Replication, Cachin, Christian and Schubert, Simon and Vukoli\’c, Marko, arXiv preprint arXiv:1603.0735, 2016
[6] On scaling decentralized blockchains, Croman, Kyle and Decker, Christian and Eyal, Ittay and Gencer, Adem Efe and Juels, Ari and Kosba, Ahmed and Miller, Andrew and Saxena, Prateek and Shi, Elaine and G\”un, Emin, Proc. 3rd Workshop on Bitcoin and Blockchain Research, 2016

來源鏈接：0xplay.com