研讀 分散式系統 時，遇到兩個常出現的議題：

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

這兩個問題也是分散式系統很重要的核心議題，底下整理相關研讀的資料。

議題一：一致性問題 (Distributed Consistency Problems)

分散式系統中，只要是資料 (Data) 相關的服務在多集群運作，就會面對 資料的同步問題、主從問題，而這就是所謂的 一致性 (Consistency) 問題。順著這問題往下找就會找到著名的問題：拜占庭將軍問題

資料相關包含 RDBMS、NoSQL、Cache … 等，像是 MySQL Cluster、Redis、etcd、Zookeeper … etc.

一致性的種類

資料的一致性分成三種特性：

1. 強一致性：保證寫完之後，任何讀取都是取得更新後的值。
2. 弱一致性：寫完之後，系統不能保證存取到更新後的值。
3. 最終一致性： 保證寫完之後，最後一定可以存取到更新後的值。

拜占庭將軍問題

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

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

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

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

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

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

這個問題稱為 拜占庭容錯 (Byzantine Fault Tolerance, BFT)。拜占庭容錯演算法 (PBFT) 是 1999 年 由 Miguel Castro 和 Barbara Liskov 提出的演算法，實現只要叛徒不超過三分之一，忠誠的將軍們就能達成一致結果。PBFT 處理的第一個前提是：

假設系統中存在不被信任的節點

基於這樣的前提，如何解決一致性問題。

相對於 PBFT 的是 非拜占庭容錯，又稱為 故障容錯 (Crash Fault Tolerance, CFT)，解決的是分散式系統中，沒有不受信任的節點，但是有故障機會的節點。

議題二：共識演算法 (Consensus Algorithm)

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

Paxos 演算法

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

Raft 演算法

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

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

• 從動畫中了解 Raft 演算法。
• Hashicorp Consul 的 Raft 實踐
  • Hashicorp Raft in Go

共識演算法

底下整理自 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

共識演算法的應用

• Service Discovery:
  • etcd
  • Hashicorp Consul
  • ZooKeeper
  • Google Chubby Lock
• Consensus and Replication in Elasticsearch
• 區塊鏈
  • 比特幣: PoW (Proof of Work)
  • 以太幣: PoS (Proof of Stake)
  • 維基鏈（WICC）: DPoS (Delegated Proof of Stake)

共識與一致性

共識 的英文是 Consensus，意思如下：

a general agreement.

就是大家取得共同的想法。

一致性 的英文是 Consistency，英文解釋如下：

conformity in the application of something, typically that which is necessary for the sake of logic, accuracy, or fairness.

在分散式系統中，兩者的差異：

1. 共識：指的是各個節點 (node) 就指定得值達成共識，而且之後就不能改變了。
   • 但是沒有包含寫入的時間保證，而 一致性 則定義了取得資料的特徵現象，像是強一致性、弱一致性、最終一致性等特徵。
2. 一致性：寫入資料後，Client 能否從各個節點取得最新寫入的資料，如果可以立即讀到，那麼就是強一致性，如果最終能讀到，就是最終一致性。

人類的群體協作中，經常需要尋找共識，達到群體行動的一致性。

企業組織裡，找到共識的方法很多種，會議 最常見的尋找共識方式，一群人在一間房間裡，共同討論議題，找到交集點，最終對對於議題結論有了共識。之後各個個題依照共識的結果，有了一致性的行動，產生一致性的結果。

例如針對技術的選擇，要用 MySQL 還是 PostgreSQL？在技術決策會議裡，經過討論、發想、辯論，找到共識，出了會議室，所有人的行動依照共識的結論，有了一致性的動作。

先有共識，再來把資訊同步，對外有一致的行動。

同步共識的過程，就會造成強一致性、弱一致、最終一致性的現象。

共識的訊息，在組織裡的傳遞，可能是透過 Email、Slack … 等內部的通訊系統，這種方法大家很快就知道了，也就是達到 強一致性 的資訊同步。通常是內部重要的人事命令，重要的公司方向、重要的組織調整 … 等。

如果有些事情是 聽說的，訊息是透過八卦散出去的，像是誰誰誰升官了、誰誰誰調部門了、誰誰誰要離職了、那個部門要被裁撤了 … ，這種透過非正式的管道傳布，但最終資訊還是會一致。

如果有些事情沒有達到共識之前，在非正式的場合有很多訊息來源，像是某個新任務的時程、目標、客戶的期待，在還沒有共識之前，訊息就已經在流串，那麼最後整個資訊就會變成 弱一致性，也就是大家知道的都不太一樣。

整理一張圖，用我自己的說法描述共識與一致性的差異：

1. 綠色：X 的值目前是 9
2. 橘色：開會找共識，透過一些 方法 討論。
   • 經過會議後找到共識，共識就是大家口徑一致：X = 5，不是 X = 9。
   • 方法的種類很多，總之就是 共識演算法。
3. 紅色：開會結束了，但是還沒正式對外公布。
   • Client A 被預先告知了
4. 第二段橘色：
   • Client W, Z, Y 都是靠聽說的 …. 得到兩種分別是 X = 5、X = 9 的答案
5. 藍色：透過最終一致性的方法布達，經過一段時間之後，大家都知道 X = 5。
   • 有人是透過主管告知
   • 有人是高層直接約 1 on 1 告知

圖中的顏色分別代表以下意義：

1. 第一段橘色：共識演算法
2. 一致性：
   • 紅色：強一致性
   • 藍色：最終一致性
   • 第二段橘色：弱一致性

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

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

延伸閱讀

分散式系統系列文章

• 聊聊分散式系統
• 分散式一致性問題與共識演算法
• CAP Theorem
• Distributed Message Systems
• Eventually Consistent 與 Dynamo NWR 模型
• 淺談分散式交易
• Design Patterns for Distributed Systems
• 分散式系統設計 - 正體中文版翻譯記事

Dapr 系列文章

• 摘要 Dapr 的設計與概念
• Experience Dapr - Hello World
• Experience Dapr - Run on K8s
• Experience Dapr - Secret Store

參考資料

• 左耳朵耗子：分散式系統架構經典資料
• Fallacies of distributed computing

論文

• Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
• CAP Confusion: Problems with Partition Tolerance
• In Search of an Understandable Consensus Algorithm
• The Byzantine Generals Problem
• SRE Chapter 23: Managing Critical State: Distributed Consensus for Reliability
• Distributed programming in Argus by Dr. Barbara Liskov (Turing Award)

演算法

• ConsensusPedia: An Encyclopedia of 30 Consensus Algorithms
• 區塊鏈 Blockchain – 共識機制之實用拜占庭容錯 PBFT
• 區塊鏈 Blockchain – 共識機制之 Raft
• The Raft Consensus Algorithm

更新紀錄

• 2020/07/25: 更新一致性、共識的差異說明