Consistency and Consensus (3-1) - Ordering Guarantees

顺序这件事在 Design Data Intensive Applications 这本书中重复到提到了很多次，代表了它是重要的基础知识，2020 年写到现在，我们总共讨论过：

• 2020 Day 21 - Leaders and Followers：single-leader 类型的数据复制资料库用 replaction log 记录操作，让 follower 节点能以同样顺序做副本。
• 2021 Day 6 - 序列化隔离 (serializable isolation)：在单一执行绪按照顺序执行 transactions。
• 2021 Day 11 - 顺序性事件的时间戳记

现在就让我们深入探讨、连结顺序、线性一致性和共识的相关知识吧！

排序和因果关系 (Ordering and Causality)

排序这件事带给我们最重要的启发就是因果关系，其实我们已经展示了多个有关因果关系很重要的例子了：

• 2020 Day 22 - 图 5-5：答案比问题还早出现。
• 2020 Day 23 - 图 5-9：insert 比 update 还晚出现。
• 2020 Day 26 - Happend before 关系：若 A 比 B 早发生，则 B 应该要知道 A；若是并发发生，则 A B 互相不知道对方。
• 2021 Day 4 - Snapshot Isolation：transaction 的资料来自有一致性快照中，而快照就等於 因果关系 (causality) 。
• 2021 Day 7 - Serializable Snapshot Isolation：序列化快照隔离能依不同 transaction 的因果关系检测 write skew。

因导致果，而因果来自事件顺序，如果系统之顺序来自遵守因果关系，我们称它为 因果一致性 (causally consistent)，就像快照隔离那样，你看到的资料必定先於其他 transaction 操作而来。

因果顺序不是全局顺序 (the causal order is not a total order)

全局顺序允许你比较任何 2 个元素的大小，像给它数字 5 跟 13，你能知道 13 比 5 大；然而若要你比较 2 个数学集合 {a, b} 和 {b, c} 哪个大呢？我们并不知道哪个大，因为 2 个集合彼此不是对方的子集合，视为 不可比 (incomparable)，这 2 个集合也是 部分顺序 (partially ordered)。

全局顺序和部分顺序若反映在一致性模型里就是以下这 2 个：

线性一致性 (Linearizability)

线性化系统是全局顺序，因为资料只有一份且操作都是原子操作，所以我们可以很轻松知道 2 个操作谁先谁後，视觉化时序图可参考 Day 15 的图 9-4。

因果一致性 (Causality)

2 个事件能排序代表他们有因果关系（一个发生在另一个之前），但如果他们是并发发生的话，则就是不可比，所以因果关系也等於是部分顺序，非全局顺序。

并发事件意味者时序会分支，然後在合并，不同分支的操作是不可比，我们可以来看一下 2020 Day 26 图 5-14， 它并不是一条直线干到底，而是并发的发生多个操作，然後合并，箭头的指向关系也代表了 因果依赖 (causal dependencies)。

另一个大家更有感的例子就是 Git 啦！版本历史就很像因果关系，一个 commit 必定发生在某 commit 之後，合并时会组合多个并发分支的 commit。

未完，明日继续。