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