分散式一致性與共識演算法


最近研讀 分散式系統 時,遇到兩個常出現的議題:

  1. 分散式一致性問題 (Distributed Consistency Problems)
  2. 共識演算法 (Consensus Algorithm)

整理最近瀏覽的資料。


核心議題:分散式一致性問題 (Distributed Consistency Problems)

分散式系統中,只要是資料,就一定會跟 一致性 (consistency) 的問題有關係。

CAP Theorem

由 加州柏克萊分校教授 Eric Brewer 在 1999 年的論文中發表:Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services。論文中第一次提到 CAP 三者的關係,描述如下:

  • 一致性 (Consistency):每次讀取有兩個結果,一種是取得最近寫入的資料,另一種則是得到錯誤
  • 可用性 (Availability):每次請求都能獲得一個 (非錯誤)回應,但不保證返回的是最新寫入的資料
  • 分區容忍 (Partition tolerance):任意數量的訊息被節點間的網路丟失 (或延遲),系統仍繼續運行。

論文的結論是:分散式系統裡,CAP 三者無法同時被滿足,只能擇其二。下圖則是 w3resource 在其文件中描述 NoSQL 時提到的 CAP 的關係,與其他實作的概念:


Source: https://www.w3resource.com/mongodb/nosql.php

CAP 常見的排列組合:

  • CA (consistency + availability)
    • RDBMS
    • 2PC (2 Phase Commit, 二階段提交)
  • CP (consistency + partition tolerance)
    • Paxos 演算法
  • AP (availability + partition tolerance)
    • 關注的是 可用性分區容錯
    • Dynamo

Google I/O 2009 Transactions Across Datacenters 整理一了張很有意思的結論,如下圖:

相關議題、名詞 (待整理)

  • BASE: Basically Available、Soft state、Eventual consistency
  • ACID
  • Two-phase Commit (2PC): 二階段提交協議,這是種 distributed algorithm
  • Three-phase Commit (3PC): 三階段提交協議,distributed algorithm
  • Partition、Sharding (分區、分片)
  • Replication (副本)

拜占庭將軍問題

拜占庭將軍問題 是由 Leslie Lamport 在他最有名的論文中提出來的:The Byzantine Generals Problem

主要描述在分散式系統中,不同的節點透過網路交換資料,達成共識,然後按照此共識進行策略行動。但有時候系統中的節點,可能因為傳送過程中的錯誤,造成全員資訊不一致,導致協作策略得到不一樣的結論,最後破壞了系統的一致性。拜占庭將軍問題被認為是容錯性問題中最難的問題類型之一。

拜占庭將軍問題大概如下:

在中世紀,拜占庭帝國的幾位將軍帶兵共同為攻一座城市。他們必須一起進攻,或者一起撤退,否則就是災難性後果。但是每個將軍四散在各處,無法一起討論,只能透過通訊方式投票,描述自己是進攻、還是撤退。所有將軍收到其他將軍的投票後,再決定自己是進攻、還是撤退。

假設所有將軍都不會叛變,那就依照投票結果就好。但問題是,將軍中可能有叛徒。九個將軍投票,四個人進攻、四個人投撤退,一個人選擇背叛,分別告訴告訴四個人進攻、四個人撤退,結果就是同時四個進攻、四個撤退。

拜占庭容錯演算法 (PBFT) 是 1999 年 由 Miguel Castro 和 Barbara Liskov 提出的,實現只要叛徒不超過三分之一,忠誠的將軍們就能達成一致結果。

相關技術:

  • 拜占庭容錯架構:FTMP、MMFCS、SIFT
  • 拜占庭容錯演算法:PBFT
  • 拜占庭容錯通訊 (BFT):Q/U, HQ, …

核心議題:共識演算法 (Consensus Algorithm)

共識演算法是分散式系統中重要的通訊機制,像是 Service Discovery 的實作都會基於這樣的核心理論,同時他也是現今流行的區塊鏈技術的基礎。

Paxos 演算法

同樣的是由 Leslie Lamport 提出來的 Paxos 演算法,主要目的是基於消息傳遞且具有高度容錯特性的一致性演算法。Google 在分散式所服務 (Chubby lock) 使用 Paxos 演算法。Chubby lock 這個架構應用在 Bigtable 展品中。

Raft 演算法

Stanford 大學的教授 Diego Ongaro and John Ousterhout 發表一篇論文:In Search of an Understandable Consensus Algorithm,演算法的方法和 Paxos 效能與功能一樣,但是卻是更容易實踐的演算法。他的核心概念:

如果在分散式系統中多個數據庫的初始狀態一致,只要之後進行的操作順序一致,就能保證之後的執行結果一致。

從動畫中了解 Raft 演算法

共識演算法

底下整理自 ConsensusPedia: An Encyclopedia of 30 Consensus Algorithms (中文),如果對區塊鏈有興趣,這些看是很有關係的。

  • 工作量證明 (PoW,Proof of Work): 比特幣, 跟 PBFT 相比,有一半的容錯率,換句話說,有 50% 以上的叛徒才行,或者破壞一半以上的網路才行。缺點是需要很大的電力成本。
  • 權益證明 (PoS,Proof of Stake): 以太幣, 相比於 PoW 節約了大量的資源,但他會造成富者越富,窮者越窮,然後用戶會流失,新用戶也不願意加入。
  • 延遲工作量證明 (dPoW,Delayed Proof-of-Work)
  • 授權 PoS (DPoS,Delegated Proof-of-Stake): 維基鏈(WICC)
  • 權威證明 (PoA,Proof-of-Authority)
  • 權重證明 (PoWeight,Proof-of-Weight)
  • 聲譽證明 (PoR,Proof of Reputation)
  • 所用時間證明 (PoET,Proof of Elapsed Time)
  • 容量證明 (PoC,Proof of Capacity),也稱為空間證明 (PoSpace,Proof of Space)
  • 歷史證明 (PoHistory,Proof of History)
  • 權益流通證明 (PoSV,Proof of Stake Velocity)
  • 重要性證明 (PoImportance,Proof of Importance)
  • 身份證明 (PoI,Proof of Identity)
  • 活動證明 (PoActivity,Proof Of Activity)
  • 時間證明 (PoTime,Proof of Time)
  • 存在證明 (PoExistence,Proof of Existence)
  • Ouroboros
  • 可收回證明 (PoR,Proof of Retrievability)
  • 拜占庭容錯 (Byzantine Fault Tolerance)
  • 授權拜占庭容錯演算法 (dBFT,Delegated Byzantine Fault Tolerance)
  • RAFT
  • 恆星共識 (Stellar Consensus)
  • 置信度證明 (PoB,Proof of Believability)
  • 有向無環圖 (DAG,Directed Acyclic Graphs)
    • Tangle (IOTA)
    • Hashgraph
    • Holochain
    • Block-Lattice (Nano)
    • SPECTRE
    • ByteBall

共識演算法的應用


結論:生活中訊息的一致性問題

古代戰爭時,四處的資訊,除了用快馬,透過驛站交接傳遞,烽火台是更快的方式。透過視覺傳遞,快速的讓各地的烽火台、決策者,知道該怎麼決策,這可以說是一致性問題最古早的方式之一了。烽火台的例子是集中式的訊息一致性問題,拜占庭問題則是反過來,他是分散式一致性問題。


參考資料

Conference

論文

演算法


Comments