分布式系统中的 partial ordering 和 global ordering 的理解

Scroll Down

原文地址:https://www.inlighting.org/archives/understand-partial-ordering-and-global-ordering

在分布式系统中,我们在阅读关于事务一致性的论文中,经常会看到 partial ordering 和 global ordering。这里简单的说明下。

Partial ordering

部分有序。指在一系列的事件中,只保证部分的事件按照一定的顺序进行处理。

Global ordering / Total ordering

全局有序。很简单,就是所有的事件均按照一定的顺序处理。例如在一个单核系统中,所有的事件都是逐一发生的,发生了 A 事件才会发生 B 事件再发生 C 事件。

例子

假设我有三个事件 ${ A,B,C}$ ,假设事件的执行顺序是 $A>B>C$,那么该系统属于 Global ordering 。另一种情况,如果我们假设 $A>C$,执行 $C$ 事件需要先执行 $A$ 事件,而 $B$ 事件为独立事件,不受 $A$ 和 $C$ 的影响,那么这种情况称为 partial ordering。

所以我们能知道,基于 Lamport Timestamp 的系统一定是 partial ordering 的。因为 Lamport Timestamp 只保证同一个 key 的数据处理有序,而不保证整个系统的所有事件处理有序。

不清楚什么是 Lamport Timestamp 的可以阅读之前的文章:https://www.inlighting.org/archives/lamport-timestamp-vector-clock

参考资料

https://stackoverflow.com/questions/4620779/partial-ordering-of-events-in-a-distributed-system