iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
Software Development

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

【Day 9】Replica 之間的一致性

7.3 eventual consistency 還沒寫QQ

這章會來聊聊 consistency
ACID 中的 consistency 跟 CAP 理論中的 consistency 是不同的,
可以看看這篇鐵人賽文章:Day 2 - 我的C是你的C嗎,介紹CAP Theorem與ACID/BASE

這裏我們在講 replica 之間的 consistency,
該怎麼定義兩個 replica 是一致的?
什麼時候一致?

7-1 Two phase commit

這堂課的上半學期有講到 ACID 的 atomicity,
如果 transaction 會發生在多個節點上,
我們仍希望維持 atomicity:
要馬全部的節點 commit 這個 transaction,
要馬全部的節點放棄這個 transaction 並 rollback。

因此,需要全部的節點有某種 agreement:決定要 abort 或 commit。
而且只要有一個節點掛掉,全部都會 abort。

Consensus vs Atomic commit

講到節點要達成某種協議,跟第六章的 consensus 好像,
所以這邊比較一下。
![[Screen Shot 2021-09-24 at 11.02.21 PM.png]]

Two phase commit

Two phase commit 是一個確保多個節點上的 atomic commitment 的協定

一開始 client 發送 transaction 給每個 replica,這些 replica 就執行這個 transaction。

而當 client 要 commit 時:

  1. 傳送 commit request 給 commit coordinator
  2. coordinator 傳送 "prepare"訊息 給其他 replicas,問問他們可不可以 commit?如果 replica 們都確認自己的狀態是可以 commit 的,才會傳 yes
    replicas 們只要跟 coordinator 保證他們是可以 commit 的狀態,
    就不能出爾反爾,
    因此這時候不能任意的 commit 或 abort 任何東西,
    以免之後跟 coordinator 的決定不一致。
  3. 若有任何一個節點說不,全部節點就會 abort、rollback。反之,全部說好,則 coordinator 會再告訴大家可以 commit 了。

Coordinator 掛掉怎麼辦?

經過前幾章的洗禮,大家都很怕某個節點掛了會影響整個系統的運行(SPOF)。
以上面的演算法來說,coordinator 佔有很重要的地位,如果掛掉了會有什麼樣的影響?
一般來說,coordinator 作出決定後會馬上寫入硬碟,才開始廣播,
這樣的話如果不幸掛了,開機恢復後還可以讀回剛剛做的決定,再廣播出去。

然而送出 prepare 訊息,並已經做決定,還沒廣播給節點們就掛了的話,
其他節點會動彈不得。(畢竟他們已經給 coordinator 承諾了,不能隨意改變狀態以免違約)

Fault-tolerant two-phase commit

這裡將介紹一個能夠容錯的 two-phase commit,基於 Paxos Commit。
使用 total order broadcast!(或是 consensus,畢竟兩者可以互換)
這個想法就是,
commit 時每個節點都會廣播自己的投票給其他節點,
而其他節點就會開始算,只要收到所有其他節點的 yes,他就可以 commit 這個 transaction;如果收到一個 no,就可以馬上 abort。

而既然是 total order,每個節點 deliver 訊息的順序是相同的,
因此不需要擔心 race condition,只要已經收到某個節點投票,接下來又收到同個節點的投票都直接丟掉不算。

如果是其中一個 replica 掛了,
該怎麼處理呢?
如果 A 懷疑 B 掛掉了(timeout),A 會幫 B 投 no。
就算 B 其實只是反應慢,而後投 yes,
但就像前面說的,感謝 total order broadcast,又每個 replica 只會接受第一票,所以不會造成 replica 之間不一致的狀況。

7-2 Linearizability

linearizability 確保永遠只讀到最新的數值,
又稱為 strong consistency。

這聽起來跟第 5 章提到的 read-after write 很相似。
read-after write consistency 只保證同個節點寫完後能讀到至少是自己寫的之後的資料,
而 linearizability 則更嚴格,要能確保不同的節點都能讀取到最新的資料。

![[Screen Shot 2021-09-24 at 11.16.19 PM.png]]
這裡只專注於從 client 的角度出發。
當 client 1 set(x, v1),client2 也希望能讀到 v1。
不是 happens-before 關係,happens-before 是基於發送和收訊息而訂出的順序關係,而這裡就算 client 1 與 client 2 沒有任何訊息往來,單就時間來說,仍希望能讀到最新的數值。

所以要看系統是否 linearizable,我們需要考慮 client 間 operation 的時間重疊下,是否還能得到最新的結果。

使用 quorum reads/writes 難道不能保證每個節點都能讀到最新數值嗎?

![[Screen Shot 2021-09-24 at 11.17.38 PM.png]]
以此圖來看,第一個 client1 發出 set,而 client2 get 的當下只有 只有 A 成功被更新,他也剛好得到 A、B 回應,並由 timestamp 知道 v1 是最新的數值。
但 client3 get 時,回應的剛好只有兩個還沒更新到數值的節點,所以這不符合 linearizability。

linearizable ABD 演算法

當 client 發現 get 到不同的數值,會幫忙再發送 set 新數值給過時的節點或沒有回應的節點,這也是前面提過的 read repair。
這個 get 的過程只有等到 quorum 個節點都有成功 read repair 或是一開始就是最新數值,才會結束。

這方法又叫 ABD 演算法,確保 linearizable reads and writes,每次的 get 或 set 都讓至少 quorum 個節點擁有最新的數值。

7-3 Eventual consistency


上一篇
【Day 8】節點間的共識(Consensus)
下一篇
【Day 10】Concurrency control in apps
系列文
什麼都不會還敢說你是 RD 啊?畢業後的後端入職前準備31

尚未有邦友留言

立即登入留言