前言

前面我們講了各種Consistency; 講了Quorum System可以調整W/R參數決定系統如何在一堆replica servers中做讀寫; 講了Lamport Logical Clock、Vector Clock來解決Event Ordering與Versioning的問題。
可以看到大家設計系統傾向Weak Consistency來提高分散式系統的Availability。
但是有些分散式儲存我們希望所有replica servers能夠達成Strong Consistency的，有哪些方法可以達成呢?

我們先重新審視一致性問題並介紹他到底有多難？
達成共識居然是一個不可能的任務？

這邊先介紹另外一個名詞 - Consensus與我們面對的Network Model

Consensus Problem

在分散式系統中，其中一個最重要的概念就是「一致性」(Consistency)。

一致性： 每一個節點儲存相同且順序一致的資料，同時保證使用者的每次讀取操作皆返回最新的資訊。

而如合讓分散式集群中的每一個節點

1. 儲存相同的數據
2. 並且對某一個提案(proposal)達成一致認同並保存

便是分散式系統中一個重要的重要問題，而「共識演算法」便是用來達成「一致性」的方法。

一般而言，我們希望集群中的節點對以下的資訊達成共識

• 儲存的訊息與資料
• 資料儲存的順序
• 集群成員

為什麼達成共識會是一個難題呢？
第一，達成共識需要彼此傳遞訊息，當集群節點數增加時，會增加複雜度。
第二，分散式集群中Failure是必然，比方某節點失效、網路中斷導致集群分裂等，在回復後如何重新達成共識也是「共識演算法」必須處理的

Consensus Algorithm Requirements

滿足「共識演算法」，有幾個以下的條件

Termination: 保證所有參與決策且無故障的節點最終會做一個決定，執行的演算法不會無法終止。
Validity: 最終的決議一定是來自某一個參與的節點
Agreement: 當演算法完成時，所有節點都會做相同的決定

有了需求跟條件，先想想自己會怎麼設計共識演算法？

要讓所有節點做一樣的決定，似乎不難，我能不能設計這樣的演算法：
“每一次做決策，所有的節點採用所收到的所有值中最小的那個值。“

步驟： round i
1. 每一個節點在被寫入一個新資料後，廣播給所有節點
2. 而每一個節點選擇最小的的那個資料做為這一輪的結果

上述這個方法看似完美，最終也達成一致性，但是可能的問題在哪裡呢？

1. 廣播的途中網路斷線，導致斷線的節點因為沒有收到所有提議，無法做決定及終止。
2. 廣播的途中某節點失效，導致發送廣播的節點懸宕無法往下執行，也就造成剩餘的節點無法達成最終共識。
3. 節點之間傳遞資料時，資料損壞或是錯誤，導致最終的共識不一致。

等等，照上面這種說法，現實的網路環境中根本有太多種發生錯誤的可能。真的有完美無缺的共識演算法可以讓一個分散式集群中的每一個節點最終達成共識嗎?

因此在認識共識演算法前，我們需要先了解我們面對的是怎麼樣的網路環境，以及做出了什麼假設。

System Model

Network Model

首先是分散式系統中的網路模型：

1. Synchronous network:
   在一個同步網路中，所有節點滿足
   a. 時間的基本上是同步的，沒有任一個節點時間偏差是無上限的。
   b. 網路的傳輸時間有上限，在固定且已知的時間範圍內一定會收到。
   c. 所有節點計算速度一樣。
   也就是說當所有的節點運行同一個演算法時，是可以同步在一個個round中執行的。一個節點發出的訊息若是沒有在一個round中到達目的節點，那可以斷定是網路中斷造成的，該訊息會丟失而不會延遲到下一個round才到達目的。在現實中幾乎不存在這樣的網路。

2. Asynchornous network:
   在這個網路模型中，
   a. 時間基本上無法同步，時鐘飄移無上限導致各節點可能最終不同步。
   b. 訊息的傳輸延遲沒有上限。
   c. 節點計算速度不一樣。
   也就是說，當一個節點發出的訊息後一直沒有接收到對方的回覆，並無法確認是網路延遲或是該節點的計算較慢，甚至有可能該訊息已丟失。

Failure Model

而分散式系統中可能發生的錯誤也可以大致分為以下幾種：

1. Byzantine failures: 該節點不按照程式邏輯執行，惡意給予錯誤的回復，比方使用者輸入0，當提出proposal給集群時，該節點隨機傳送0或1給其餘節點。

2. Crash-recovery failures: 節點運算總是正確，但是可能因為發生Crash或是網路中斷，需要時間Recover，因此無法保證回覆時間。對於Recover方法，可以分為a)回復所有失效前的狀態，b)不完整保存失效前的狀態。

3. Omission failures: 發生Crash後，「消息」不會回覆。比方網路中斷導致訊息丟失，不再重傳。

4. Crash failure: 發生Crash，不再回復。比方某個節點發生故障，則該節點不再回復也不再跟其他系統其他節點有來往。

Summary

透過Model分類可以知道，在分散式系統中設計共識演算法，重點除了集群中節點如何達成共識本身，更重要的是該演算法可以處理哪種網路模型，以及他可以應付哪種錯誤，來做到特定程度的 Fault-tolerance。

那完美的可以應付所有情況的共識演算法存在嗎？
這邊先說結論：不存在
甚至就算條件放寬，只應付部分錯誤的「正確」共識演算法也是不存在。

在1985年這個問題已經被回答，也就是有名的 FLP Impossibility

No completely asynchronous consensus protocol can tolerate even a single unannounced process death. [Impossibility of Distributed Consensus with One Faulty Process, Journal of the Association for Computing Machinery, Vol. 32, No. 2, April 1985]

也就是說，在非同步的網路環境中即使只應付允許一个節點故障，任何共識演算法仍然都不能保證正確結束。根據該敘述，該節點的故障是其他節點無法探測且不知的，也就是說從其餘的節點來看，該故障節點可能是網路延遲或是該節點運算較慢。

此論點非常強大，證明也只用了幾頁和3個Lemma就證明完畢，但是寫在這裡會過於篇幅過長且複雜，因此這邊不做討論。
參考資料附上證明的原文與過程。

總結

Termination: 保證所有參與決策且無故障的節點最終會做一個決定，執行的演算法不會無法終止。
Agreement: 當演算法完成時，所有節點都會做相同的決定
Validity: 最終的決議一定是來自某一個參與的節點

而FLP定理則告訴我們，

在Asynchronous網路環境且允許一個節點失效的情況下，任何Consensus protocol無法確保共識在有限時間內完成。

但是這並不代表共識演算法沒有意義，從理論上也許完美的共識演算法並不存在。但是實作上我們仍然能夠實作出一個演算法，並且降低沒有達成共識的機率到合乎使用，例如接下來介紹的Paxos/Raft演算法。這些演算法有各自的缺陷，可能無法一次滿足上面三個條件，或是應付各種錯誤。

作為第一篇Consensus Problem的筆記整理，這正說明了Distributed System的本質，系統的設計本身是一種取捨，並透過假設，來實作不同功能與不同層級容錯處理的架構：

As Ken Arnold says: "You have to design distributed systems with the
expectation of failure." Avoid making assumptions that any component in the system is in a particular state.

Ref:

原文
https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

證明
https://danielw.cn/FLP-proof
https://danielw.cn/history-of-distributed-systems-2