iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
Software Development

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

【Day 7】Replica 的 Quorum 、State machine replication

5.2 Quorum

read-after-write(read-your-write) consistency

例如一個使用者 po 文,通常使用者會希望能看到自己的文章,
不然他可能以為自己眼睛業障重。

如果今天 client 送出 po 文請求給兩個 replicas,
但只有 A 成功收到,
而發出讀取請求時卻只有 B 收到,
就違背了 read-after-write consistency。

如何達到 read-after-write consistency?

若能保證兩個 replicas 都有收到 po 文請求才真正寫入,
那讀取時兩個 replicas 都是最新的,就沒問題了吧?

然而這樣卻失去了 fault tolerance:
當其中一個 replica 出事,無論是 寫入 還是 讀取 都不能做了。

Read and write quorum

quorum 是指一個動作要有幾個節點回應才有效。

如果今天有 n 個 replicas,
write quorum: w 個 replicas 回 ack
read quorum: r 個 replicas 回 ack
只要能保證 w + r > n
就會保證讀取時至少有 1 個節點是之前寫過的。(鴿籠原理)

通常: r = w = (n + 1)// 2 for n = 3, 5, 7...

但 Replicas 不一致?

透過 Read and write quorum,
client 端開心了,
但是 replicas 這邊可能有一些不一致。
有兩種解法:

  1. anti-entropy
    replicas 自己發現並透過前面談到的 anti-entropy 過程去 sync
  2. read repair
    因為 client 在讀時很容易發現哪些 replicas 回的是舊資料,
    可以幫忙把最新的更新推回去給這些過時的 replicas。

5.3 State machine replication

雖然沒特別提,但前面的 Quorum 是在 best-effort 的基礎上討論的:client 廣播讀寫請求到每個 replicas,封包可能遺失、也沒有保證特定的訊息順序。

如果用之前說的最嚴格的 FIFO total order broadcast 呢?

State machine replication (SMR)

可以把 replicas 變成 state machine!
我們假設 state machine 是 deterministic 的,
複習一下XD
deterministic: 一個 state 被 apply 更新後,只會轉換成下一個 state,不會有兩個或三個其他可能。
有了這個前提,replicas 們的 initial state 相同,會經過相同順序的 transitions(FIFO total order給的保證) 而最終變成同樣的 state。

SMR 優缺點

優點:從一個 state 轉到另一個 state,之間的邏輯要多複雜就可以多複雜,不用想太多,唯一的條件就是 deterministic。

區塊鏈、智能合約等等都是基於 state machine replication

缺點:total order broadcast 本身的限制。

第 4 章有提到,一個節點要確定前面的訊息都來了才能 deliver 自己的廣播訊息,也就是一個 replica 不能馬上更新自己的 state。

用其他的廣播模型做 replication

前面提到 best-effort,
而後提到 FIFO total order,
那其他的廣播模型例如 causal order 也能拿來作 replication 嗎?

以 causal order 來說,只有 concurrent 的廣播事件順序可能會不一致,那只要確保這些事件在 apply 時,是 commutative 就好。
f(g(x)) = g(f(x)) 也就是就算中途不一樣,最後會一致就好。這些在第 8 章會提到。


上一篇
【Day 6】Replication
下一篇
【Day 8】節點間的共識(Consensus)
系列文
什麼都不會還敢說你是 RD 啊?畢業後的後端入職前準備31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言