【Day 7】Replica 的 Quorum 、State machine replication

5.2 Quorum

read-after-write（read-your-write） consistency

例如一个使用者 po 文，通常使用者会希望能看到自己的文章，
不然他可能以为自己眼睛业障重。

如果今天 client 送出 po 文请求给两个 replicas，
但只有 A 成功收到，
而发出读取请求时却只有 B 收到，
就违背了 read-after-write consistency。

如何达到 read-after-write consistency？

若能保证两个 replicas 都有收到 po 文请求才真正写入，
那读取时两个 replicas 都是最新的，就没问题了吧？

然而这样却失去了 fault tolerance：
当其中一个 replica 出事，无论是 写入 还是 读取 都不能做了。

Read and write quorum

quorum 是指一个动作要有几个节点回应才有效。

如果今天有 n 个 replicas，
write quorum： w 个 replicas 回 ack
read quorum: r 个 replicas 回 ack
只要能保证 w + r > n，
就会保证读取时至少有 1 个节点是之前写过的。（鸽笼原理）

通常： r = w = (n + 1)// 2 for n = 3, 5, 7...

但 Replicas 不一致？

透过 Read and write quorum，
client 端开心了，
但是 replicas 这边可能有一些不一致。
有两种解法：

1. anti-entropy
   replicas 自己发现并透过前面谈到的 anti-entropy 过程去 sync
2. read repair
   因为 client 在读时很容易发现哪些 replicas 回的是旧资料，
   可以帮忙把最新的更新推回去给这些过时的 replicas。

5.3 State machine replication

虽然没特别提，但前面的 Quorum 是在 best-effort 的基础上讨论的：client 广播读写请求到每个 replicas，封包可能遗失、也没有保证特定的讯息顺序。

如果用之前说的最严格的 FIFO total order broadcast 呢？

State machine replication (SMR)

可以把 replicas 变成 state machine!
我们假设 state machine 是 deterministic 的，
复习一下ＸＤ
deterministic: 一个 state 被 apply 更新後，只会转换成下一个 state，不会有两个或三个其他可能。
有了这个前提，replicas 们的 initial state 相同，会经过相同顺序的 transitions（FIFO total order给的保证） 而最终变成同样的 state。

SMR 优缺点

优点：从一个 state 转到另一个 state，之间的逻辑要多复杂就可以多复杂，不用想太多，唯一的条件就是 deterministic。

区块链、智能合约等等都是基於 state machine replication

缺点：total order broadcast 本身的限制。

第 4 章有提到，一个节点要确定前面的讯息都来了才能 deliver 自己的广播讯息，也就是一个 replica 不能马上更新自己的 state。

用其他的广播模型做 replication

前面提到 best-effort，
而後提到 FIFO total order，
那其他的广播模型例如 causal order 也能拿来作 replication 吗？

以 causal order 来说，只有 concurrent 的广播事件顺序可能会不一致，那只要确保这些事件在 apply 时，是 commutative 就好。
f(g(x)) = g(f(x)) 也就是就算中途不一样，最後会一致就好。这些在第 8 章会提到。