[Day 19] Consistency and Consensus (3-3) - Total Order Broadcast

续 Day 18

Total Order Broadcast

虽然 昨天 讲的 Lamport timestamp 能定义符合因果关系的全局顺序，但它们不足以解决一些分散式系统中的常见问题，例如你的系统想要让使用者名称为唯一性限制，当有 2 个使用者并发 (concurrent) 同时申请帐号时，你得决定哪个使用者能申请帐号成功，Lamport timestamp 有全局顺序，所以你可以去所有的节点汇总所有的使用者名称，然後看谁先谁後就好了对吧！？

但这个难处就是你得立即决定谁申请成功，在那个当下你并不晓得其他节点操作为何，这些操作可能穿插在全局顺序之中。

为了实现唯一性限制这种功能，只用全局顺序是不够的，你必须知道这个顺序也是 最终 顺序；就像你在建立使用者名称时，知道了没有其他节点声明要在全局顺序中使用该名称，那麽你就能安全宣告你的操作能执行成功。

这个议题称之为 全局顺序广播 (total order broadcast)。

全局顺序广播的属性 (the properties of total order broadcast)

全局顺序广播通常视为一种交换讯息用的协定，它需要满足 2 个安全属性：

可靠交付 (Reliable delivery)

​ 没有讯息遗失：如果一封讯息可被交付於某节点，那麽它也要能交付於所有节点。

完全顺序交付 (Totally ordered delivery)

​ 每一个节点的讯息顺序都相同。

使用全局顺序广播 (using total order broadcast)

共识服务像 Zookeeper 就有实现全局顺序广播，所以它跟共识算法有很强的联系关系，我们会在 Day 21 介绍。

另外全局顺序广播正是资料库做数据复制时必要的协定：如果任一讯息写入至资料库，其他副本也得用相同顺序写入，那麽副本间就能保持其一致性，该原则也称为 状态机复制 (state machine replication)。

还有它能被用在序列化隔离 (serializable isolation) 上，如同 Day 6 讨论的 连续执行 (Serial Execution) transaction，每一个 transaction 的预存程序 (stored procedures) 都能在所有节点用相同顺序执行，故资料库的每个分区跟副本也能保持一致性。

最後，全局顺序广播能用在提供 击剑令牌 (Fencing token) 的锁服务上 (Day 12)，每一个 request 获取锁时也会附加讯息在 log 里，所有讯息按顺序编号，用作击剑令牌；在 Zookeeper 中，该编号就是 zxid。

全局顺序广播最强的面向是它固定了所有已交付讯息的顺序，当後续的讯息抵达时，节点不允许往前面的位置回溯讯息，这事实也使全局顺序广播比 timestamp 排序还强。