iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
Software Development

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

【Day 10】Concurrency control in apps

todos:

還在出去玩,之後補上演算法 pesudocode + comments
8.2 提到的 Google spanner 也是
two-phase locking、serializability 等等原來是在前半部 concurrent 的範圍,但之後考慮在文章內做補充

現代有很多協作工具,例如 hackmd、Google docs,
或是不同裝置之間日曆的同步,
使用這些 app 時都可能會有短暫斷線,而後才連上,
如果這時候發生了不同 replica(裝置)上的存檔有衝突,該怎麼解決呢?

8.1 Collaboration and conflict resolution

其實這種多人協作的應用程式,也可以採用第 7 章提到的 linearizable read/writes 方法,但除了很慢(讀寫都要與 quorum 個節點交流往返)還不能斷線。
為了讓使用者體驗,大部分協作軟體會採用 strong eventual consistency,等到裝置連線上了,再想辦法解決衝突。

Conflict-free Replicated Data Types(CRDTs)

CRDT 主要有兩種:

  1. Operation-based
  2. State-based

Operation-based CRDTs

  • 被廣播的是 operation,例如 broadcast (set, t1, “title”, “Lecture 1”)
  • 每個 operations 都要送達:使用 reliable broadcast
    不需要在意訊息 deliver 的順序,
    但是要保證最後每個 operations 都能被順利廣播給每個節點,
    這樣才不會出現不一致。
  • Applying an operation is commutative

{演算法place holder}

State-based CRDTs

  • 被廣播的是 replica 的 state
  • 能容忍訊息遺失、重複: 使用 best-effort broadcast
    只要節點最後能更新彼此的最新狀態,中間幾個訊息遺失也沒關係。
    至於重複的話,只要演算法設計是 idempotent 即可。

{演算法place holder}

Summary

Operation-based: 通常廣播訊息比較小。
State-based: 可以接受訊息遺失、

協作時會遇到的問題:網路斷線後的恢復

![[Screen Shot 2021-09-25 at 8.08.46 PM.png]]
userA:在 0 插入 A,而後收到 userB 在 2 插入 D 的訊息,但因為對方插入位子的計算是基於還沒 insert(0,A) 的狀態,所以直接在現在的 2 插入 D 就會出錯。

Operational Transformation(OT)

![[Screen Shot 2021-09-25 at 7.39.00 PM.png]]
把剛收到的其他節點的更新,
以目前節點最新的狀態做一些 transformation 計算(需要透過 timestamp),
而得到能夠用在現在狀態的更新。

篇幅關係,這堂課並沒有對 OT 的計算深入介紹。

Text-editing CRDT

這裡介紹了另一種解決上述協作問題的方法。
如果以 index 來作為插入的標的,那只要本地的狀態被更新,從其他節點送來的更新勢必要透過 OT 轉換過才能 apply。
而如果改成頭尾0到1之間,插入時,是把要插入的兩邊的節點的位置取中間值,不同節點之間的更新都是依據相對的位子,就不用擔心之前插入時 index 已經跑掉的問題。
但要小心小數點的精度。
![[Screen Shot 2021-09-25 at 7.59.45 PM.png]]

{演算法place holder}

8.2 Google's Spanner


上一篇
【Day 9】Replica 之間的一致性
下一篇
【Day 11】分散式系統小總結
系列文
什麼都不會還敢說你是 RD 啊?畢業後的後端入職前準備31

尚未有邦友留言

立即登入留言