續 Day 20
共識問題通常可以公式化成：一個或多個節點可以提議，然後共識演算法從其提議中做決定。
舉個訂飛機座位的例子，當數個客戶同時訂購該班機的最後一個位子，每一個節點都接收到客戶的 request 了，算法就要決定哪個客戶能訂到座位。
所以一個共識算法必須安全的提供以下幾個屬性：
統一協議 (Uniform agreement)
沒有任二個節點有不同決定。
正當 (Integrity)
沒有節點決定 2 次。
有效 (Validity)
如果一個節點決定為 v，那麼 v 就某個節點的提議。
終止 (Termination)
每一個最終沒故障的節點都會決定一些東西出來。
統一協議 和 正當 屬性是共識算法中的核心；有效 屬性是為了避免做出無效的決定；而 終止 屬性則是為了系統容錯而存在，若有節點故障，其他節點必定也能做出決定，當然若所有節點故障，任何演算法都不能決定任何事情，因此，終止 屬性是假設在少於一半的節點故障或無法連接。
另外，今天講的共識演算法也是假設系統不會有 Day 12 討論的 拜占庭錯誤 (Byzantine Faults)，因為它可能會破壞協定的安全屬性。
但實際上是有方法可解啦，看 李永樂老師 的說明影片就對了。
已知好的容錯共識演算法有 Viewstamped Replication (VSR)、Paxos、Raft 和 Zab，它們之間並不完全一樣，今天我們只討論它們共通的 high-level 想法。
許多共識演算法實際上不直接用上一小節描述的定義，取而代之的是，它們決定一系列的值，使它們成為 全局順序廣播 (total order broadcast) 算法 (Day 19)，全局順序廣播的訊息只被交付一次且在所有的節點順序相同，細想一下的話，這等同於執行數回合的共識，在每一回合中，節點提議它們想發送的下一條訊息，然後決定下一條要被新增至全局順序的訊息為何：
2020 Day 21 提過的 single-leader 類型的 replication 資料庫，leader 負責所有的寫入，然後以相同的順序發給 follower 節點，這聽起來是不是很像全局順序廣播！？
那麼，為了避免 Day 12 講的 split brain 問題，我們需要共識算法，而共識算法等於全局順序廣播，而全局順序廣播又很像 single-leader 類型的 replication 資料庫，single-leader 又可能會發生 split brain 問題.........
我們如何擺脫這個難題？
到目前為止所有討論過的共識協定都有在內部使用某種形式的 leader，但它們並不保證 leader 是唯一，相反地，它們提供一個較弱的保證：它定義了 紀元號 (epoch number)。
Paxos 稱為 ballot number，Viewstamped Replication 稱為 view number ，Raft 稱為 term number。
每次只要認為 leader 死亡時，演算法就會開始在節點中選出新的 leader，選出 leader 時會一起給一個逐步增加的紀元號，若有 2 個不同的 leader 衝突發生，則由有較大的紀元號的 leader 勝出。
在 leader 決定任何事情之前，它必須檢查有沒有其他 leader 有更大的紀元號，那麼領導者該怎麼知道它有沒有被趕走呢？它必須從 quorum (法定人數) (2020 Day 24) 節點們收集投票，當 leader 要決定事情時，它需要發送它的提議給其他節點，然後看 quorum 節點們是否同意該提議，只有當節點 不知道 有更高紀元號的 leader 時，節點才會投票贊成提議。
所以這裡會有 2 回合的投票，一次是選 leader，第二次是投 leader 的提議，這裡有個重點是這 2 次的投票的 quorum 節點必須重疊：如果一個提議成功，則最少其中之一節點也必須參與在最近一次的 leader 選舉之中。
因此，如果提議的投票沒有透露出任一更高紀元號的 leader 時，當前的 leader 可以做出沒有更高紀元號的選舉行為發生，它就可以知道自己擁有領導權，能安全地做決定。
首先是每次的提議都要投票，這樣就跟 同步化數據複製 (synchronous replication) 一樣，但現在資料庫為了效能通常都會選擇 異步化數據複製 (asynchronous replication)。
再者共識算法需要嚴格的多數才能進行，意味者起碼要 3 個節點。
最後就是共識算法通常是依靠 timeout 去檢測故障節點，在高網路延遲的環境下，尤其是不同地區的分散式系統，有可能會發生誤會 leader 死亡的狀況，太常發生時對效能是個傷害。
iThome鐵人賽
看影片追技術