分布式系统中的 Partial ordering 和 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

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇