iT邦幫忙

2021 iThome 鐵人賽

DAY 21
0
AI & Data

資料工程師修煉之路 Part II系列 第 21

Consistency and Consensus (4-2) - Fault-Tolerant Consensus

Day 20

Fault-Tolerant Consensus

共識問題通常可以公式化成:一個或多個節點可以提議,然後共識演算法從其提議中做決定。

舉個訂飛機座位的例子,當數個客戶同時訂購該班機的最後一個位子,每一個節點都接收到客戶的 request 了,算法就要決定哪個客戶能訂到座位。

所以一個共識算法必須安全的提供以下幾個屬性:

  • 統一協議 (Uniform agreement)

    沒有任二個節點有不同決定。

  • 正當 (Integrity)

    沒有節點決定 2 次。

  • 有效 (Validity)

    如果一個節點決定為 v,那麼 v 就某個節點的提議。

  • 終止 (Termination)

    每一個最終沒故障的節點都會決定一些東西出來。

統一協議正當 屬性是共識算法中的核心;有效 屬性是為了避免做出無效的決定;而 終止 屬性則是為了系統容錯而存在,若有節點故障,其他節點必定也能做出決定,當然若所有節點故障,任何演算法都不能決定任何事情,因此,終止 屬性是假設在少於一半的節點故障或無法連接。

另外,今天講的共識演算法也是假設系統不會有 Day 12 討論的 拜占庭錯誤 (Byzantine Faults),因為它可能會破壞協定的安全屬性。

但實際上是有方法可解啦,看 李永樂老師 的說明影片就對了。

共識算法和全局順序廣播 (Consensus algorithms and total order broadcast)

已知好的容錯共識演算法有 Viewstamped Replication (VSR)PaxosRaftZab,它們之間並不完全一樣,今天我們只討論它們共通的 high-level 想法。

許多共識演算法實際上不直接用上一小節描述的定義,取而代之的是,它們決定一系列的值,使它們成為 全局順序廣播 (total order broadcast) 算法 (Day 19),全局順序廣播的訊息只被交付一次且在所有的節點順序相同,細想一下的話,這等同於執行數回合的共識,在每一回合中,節點提議它們想發送的下一條訊息,然後決定下一條要被新增至全局順序的訊息為何:

  • 由於 統一協議 屬性,所有節點決定交付相同順序的訊息。
  • 由於 正當 屬性,訊息不重複。
  • 由於 有效 屬性,訊息不會被破壞,也不會憑空捏照。
  • 由於 終止 屬性:訊息不會遺失。

Single-leader 數據複製和共識 (single-leader replication and consensus)

2020 Day 21 提過的 single-leader 類型的 replication 資料庫,leader 負責所有的寫入,然後以相同的順序發給 follower 節點,這聽起來是不是很像全局順序廣播!?

那麼,為了避免 Day 12 講的 split brain 問題,我們需要共識算法,而共識算法等於全局順序廣播,而全局順序廣播又很像 single-leader 類型的 replication 資料庫,single-leader 又可能會發生 split brain 問題.........

我們如何擺脫這個難題?

紀元號和法定人數 (Epoch numbering and quorums)

到目前為止所有討論過的共識協定都有在內部使用某種形式的 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 死亡的狀況,太常發生時對效能是個傷害。


上一篇
Consistency and Consensus (4-1) - Atomic Commit and Two-Phase Commit(2pC)
下一篇
Consistency and Consensus (4-3) - Coordination Services & Summary
系列文
資料工程師修煉之路 Part II30

尚未有邦友留言

立即登入留言