iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
Software Development

什麼都不會還敢說你是 RD 啊?畢業後的後端入職前準備系列 第 8

【Day 8】節點間的共識(Consensus)

準備出遊,6.2 的 Raft 之後再補

5.3 提到 state machine replication(SMR)需要 total order broadcast。
而前面也提到,達到 total order broadcast 的其中一種方法,
可以透過 leader 決定訊息順序,並使用 FIFO broadcast 給其他節點。
問題在於 leader 掛掉時,要怎麼辦?

  • manual failover:leader 掛掉的話,把負責的人摳爆,叫他重啟或是重選一個 leader。

如果轉換 leader 的工作靠手動,
除了員工不爽,還可能會導致服務不能用一陣子,
那有沒有自動的方法呢?
就是接下來介紹的 Consensus 共識演算法。

6.1 Intro to consensus

分散式系統中的節點要達到共識(Consensus),也就是都同意某個值。
一個或多個節點會 提議(propose) 一個數值,
然後透過共識演算法決定要採用哪個,
最後每個節點都達到一致,
而且決定好之後就不會改變心意~

Consensus 與 total order broadcast

consensus 跟 total order broadcast 可以互相轉換。

  • total order broadcast -> consensus: 想要提議數值的節點就廣播,而 total order 決定 deliver 的第一個訊息當作大家同意的值。
  • consensus -> total: 使用不同輪的 consensus 決定第一、二、三個要 deliver 的數值,想要廣播的節點就在這幾輪 consensus 中提議新數值,共識演算法會確保每個節點都同意這個 deliver 的訊息序列。(講得有點複雜QQ 就是用 consensus 來做 total order,如果每次大家都同意一個數值,那每個節點 deliver 訊息的順序也就一樣)

目前有名的共識演算法:
Paxos、Multi-paxos
Raft

Consensus system models

共識演算法基於 partially sync, crash recovery system model

為什麼不用 async model?

  • FLP result
    這個理論證明,如果假設 async model,沒有 deterministic 的共識演算法能保證會停下來。

  • Paxos、Raft 等演算法只有在 timeout/failure detector 上用到 clock(確保 progress),在 correctness(safety) 上並不依賴時間。

Leader election

共識演算法的核心基本上就是發現舊的 leader 掛掉時,
能自動選上新的 leader。
而且要避免 split-brain:同時間有不只一個 leader,各說各話。

leader election 過程會根據不同演算法有所差異,
基本上是當節點有一陣子沒收到 leader 的訊息,
會發起選舉,成為 candidate,並問其他節點是否投票,
當有足夠 quorum 數量的節點投票,他就成為新的 leader。

Raft 演算法中,一個 term 只會有一個 leader,
但不同 term 可以有不同 leader,
之後會說明。

能保證同時間只有一個 leader?

我們需要避免 split-brain,
但基於一開始的假設:partially syncronus,
會因為 timeout 就判定舊的 leader 掛了、選出新 leader。
但或許只是網路真的很爛而已,
舊 leader 活著、甚至不知道自己被奪權了。

雖然不可能保證同時間有好幾個 leader,
但可以保證 每個 term 只有一個 leader。
Raft 中的 term 代表這是第幾次選舉 的 leader,
就是為了能夠做出區別。

每次決定下一個訊息的順序,leader 都要先問

這是一個很重視團隊意見的 leader XD
每次 leader 要決定下一個訊息,
就要獲得 quorum ,也就是大部分節點要同意。
以避免實際上有好幾個 leader(例如因為暫時的網路斷掉,已經有較大 term 的 leader 被選出)造成了節點間訊息順序不一致。

  1. leader 詢問大家:can i deliver message m in term t?
  2. 因為其他 follower 還沒有認識別的擁有更大 term 的 leader,就說好哇好哇聽你的,leader 獲得 quorum 投票
  3. leader 叫大家 deliver m

6.2 Raft

Raft 演算法的部分會在我出去玩回來,也就是下禮拜之後補上


上一篇
【Day 7】Replica 的 Quorum 、State machine replication
下一篇
【Day 9】Replica 之間的一致性
系列文
什麼都不會還敢說你是 RD 啊?畢業後的後端入職前準備30

尚未有邦友留言

立即登入留言