【Day 9】Replica 之间的一致性

7.3 eventual consistency 还没写ＱＱ

这章会来聊聊 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