字数
780 字
阅读时间
4 分钟
在分布式系统中，由于有多个机器（进程）在一起协调工作，于是如何定义分布式系统中事件的先后顺序就成了难题。
这里就需要我们了解两个数学上的概念：全序（total ordering）和偏序（partial ordering）关系。
全序（Total Order） 全序关系满足以下性质：
- 反对称性：若 ( a <= b ) 且 ( b <= a )，则 ( a = b )。
- 传递性：若 ( a <= b ) 且 ( b <= c )，则 ( a <= c )。
- 完全性：对于任意 ( a ) 和 ( b )，要么 ( a <= b )，要么 ( b <= a )。
特点：
- 集合中的任意两个元素都可以比较大小。
- 不存在无法比较的元素。
举例：
- 整数集合：任意两个整数都可以比较大小（如 ( 3 <= 5 ) 或 ( 5 <= 3 )）。
- 时间戳：如果所有事件都分配了唯一的时间戳，则事件顺序是全序的。
- 物理时钟：从物理时钟到NTP与PTP协议
全序的应用
- 分布式共识算法：
- Paxos 或 Raft 等算法为所有操作分配一个全局唯一的顺序，从而实现全序。
- 例如，在 Raft 中，Leader 为每个日志条目分配一个唯一的索引，确保所有副本按相同的顺序执行操作。
- 状态机复制：
- 在状态机复制中，全序用于确保所有副本按相同的顺序执行操作，从而保持一致状态。
偏序（Partial Order） 偏序关系满足以下性质：
- 自反性：对于任意 ( a )，有 ( a <= a )。
- 反对称性：若 ( a <= b ) 且 ( b <= a )，则 ( a = b )。
- 传递性：若 ( a <= b ) 且 ( b <= c )，则 ( a <= c )。
特点：
- 集合中的部分元素可以比较大小，但并非所有元素都可以比较。
- 可能存在无法比较的元素（即并发事件）。
举例：
- 树形结构：同一层级的节点之间无法比较大小，只有父子节点之间可以比较。
- 家庭关系：你和你堂兄弟姐妹之间没有直接的父子关系，因此无法比较“大小”。
- 逻辑时钟：Lamport 逻辑时钟
- 向量时钟：Vector 向量时钟
偏序的应用
- 因果一致性：
- 在分布式系统中，偏序用于描述事件的因果关系。
- 例如，如果事件 A 导致事件 B 发生，则 ( A <= B )。
- 冲突检测：
- 在 AP 系统中，偏序用于检测并发写操作的冲突。
- 例如，使用向量时钟识别并发事件。
YJ