【Day 6】Replication

决定要拆章节了，
这篇只有 5.1，
5.2 5.3 放明天，因为我好累。

这章会提到 replication，
也就是把资料复制到多个节点（称为 replica）上，
这使得分散式系统能够容错，
当一个节点出事了，
还有其他节点能帮忙。
另外，也能做 load balancing，
例如很多人要读某笔资料，可以不用都向同个服务器要，
而可以分流到这些 replica 上。

5.1 Replication

资料如果不会更动，做 replication 很简单，
就只是复制过去，happy ending。
所以 replication 主要的困难点在於资料会异动。

更新远端资讯可能发生的问题

通常使用者端会与系统做一些互动，
而对系统的资料有所异动。

例如考虑按赞这件事：
![[Screen Shot 2021-09-21 at 4.45.49 PM.png]]
当使用者对贴文点赞，
远端资料库收到了，但回覆的 ack 封包遗失，
使用者端因此认为对方没收到，重传封包。

而远端服务器，每收到一个点赞封包，
就把 counter++，
才不管到底是不是同一个使用者重传的封包，
这样会导致重复计算很多次赞。

如何避免这样的情况呢？
除了想办法辨识重复的封包（deduplicate），
还可以把程序逻辑设计为 idempotence。

Idempotence

如果 f(x) = f(f(x))，我们说这个 function 是 idempotence。

也就是无论按几次赞，效果都跟按一次一样。
这样就不需要额外做 deduplicate。

以同样的例子来说，
原来设计 counter +=1 并不是 idempotence。
但如果改成当封包一来，把 userid 加入 likeset，
按赞数再透过这个 set 计算数量，就是 idempotence。

choices of retry behavior

对於重传的行为，有下列三种含义（semantics），
可以帮助我们厘清需求、思考怎麽设计程序。

• at-most-one
  就传一次，有可能因为封包遗失而没更新到。
• at-least-one
  一直重传直到收到 ack 包。可能重复更新。
• exactly-one
  重传 + idempotence or dedup

adding then removing again 1

一个程序是 idempotence，还会有其他问题吗？

如果今天某个数值能够被不同的使用者更动，
可能会有下面这个状况：
![[Screen Shot 2021-09-21 at 5.07.44 PM.png]]
2 个 client 对 1 个 server，
按赞和取消赞可以被不同使用者操作，
client 1 想要按赞，
client 2 想取消按赞，
以结果来说，最後应该要是取消赞的情况。
然而 client 1 却因为 ack 封包遗失而重传，
那麽即使这个程序被设计为 idempotence，也会因此再把赞加回来。

adding and removing again 2

如果考虑 1 个 client 对 2 个 replicas 同时做更新，
![[Screen Shot 2021-09-21 at 5.23.16 PM.png]]
情况一，client 先增加 x，而後希望移除 x。却因为其中一个移除 x 的封包遗失导致 A、B 服务器不一致。
情况二，client 只想增加 x。而因为其中一个增加 x 的封包遗失，导致 A、B 服务器不一致。

这两个情况最後的结果是相同的，
都会造成 A 上面有 x，B 没有。
然而这并不是 client 想要的结果。

今天 replica 之间的状态不一致时，
肯定是哪里出了问题，
但如果没办法分辨到底是哪种情况，
那就不可能恢复。

Timestamp 与 tombstone

为了解决上述问题，要做两件事：

1. 每个动作都附上 logical timestamp
2. 删除资料时不真的删掉东西，而是写入一个特别的资料（tombstone）

当两个 replicas 发现冲突，
要让状态变回正确且一致时 （anti-entropy），
有 tombstone，才能够分辨这笔资料到底是还没产生、还是被删除了？
有 timestamp，才能够分辨到底那个纪录是最新的。
使得 anti-entropy 过程顺利。

前面提到 2 个 client 对 1 个 server 同时做更新的问题，
也刚好得以解决：
因为重传的讯息拥有与原讯息相同的 timestamp，
所以当後来的更新到达并影响了服务器状态後，
重传的讯息的 timestamp 较小，而被舍弃。

当多个 client 对同一笔资料做更新

当多个 client 对同一笔资料做更新，
到底要听谁的呢？

1. Last writer wins (LWW)

• 使用 total order 的 timestamp，eg. lamport clock
  有了 total order，
  若 t1 > t2，就留下 t1 的讯息，舍弃 t2 的。
• data lose
  如果有多个 concurrent 的更新，
  只有最大 timestamp 的更新会影响这个系统。

2. Multi-value register

• 使用 partial order 的 timestamp，eg. vector clock
  可以知道哪些是确实要被覆盖掉的旧数值，
  而哪些更新是 concurrent 的。
  这些 concurrent 的事件称为 conflicts 或 siblings，
  透过後续的处理（第 8 章）去做合并。