【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