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


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

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

整理最近瀏覽的資料。


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

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

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

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

拜占庭將軍問題

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

Leslie Lamport 是美國計算機科學家,2013 年獲得圖靈獎,他也是著名排版系統 LaTeX 的開發者。

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

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

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

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

拜占庭容錯演算法 (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

共識演算法的應用


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

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


參考資料

論文

演算法


Comments