全序、偏序

标签

分布式/时钟

字数

2547 字

阅读时间

11 分钟

在分布式系统中，由于有多个机器（进程）在一起协调工作，于是如何定义分布式系统中事件的先后顺序就成了难题。

这里就需要我们了解两个数学上的概念：全序（total ordering）和偏序（partial ordering）关系。

全序（Total Order）

全序关系满足以下性质：

1. 反对称性：若 ( a <= b ) 且 ( b <= a )，则 ( a = b )。
2. 传递性：若 ( a <= b ) 且 ( b <= c )，则 ( a <= c )。
3. 完全性：对于任意 ( a ) 和 ( b )，要么 ( a <= b )，要么 ( b <= a )。

特点：

• 集合中的任意两个元素都可以比较大小。
• 不存在无法比较的元素。

举例：

• 整数集合：任意两个整数都可以比较大小（如 ( 3 <= 5 ) 或 ( 5 <= 3 )）。
• 时间戳：如果所有事件都分配了唯一的时间戳，则事件顺序是全序的。
• 物理时钟：从物理时钟到NTP与PTP协议

全序的应用

• 分布式共识算法：
  • Paxos 或 Raft 等算法为所有操作分配一个全局唯一的顺序，从而实现全序。
  • 例如，在 Raft 中，Leader 为每个日志条目分配一个唯一的索引，确保所有副本按相同的顺序执行操作。
• 状态机复制：
  • 在状态机复制中，全序用于确保所有副本按相同的顺序执行操作，从而保持一致状态。

两种结构的形状差别（箭头朝上表示"更大"，连线表示可比）：

全序（链）：任意两点可比                 偏序（菱形）：中间两点互不可比

        c                                      c
        │                                    ╱   ╲
        b                                   b     d
        │                                    ╲   ╱
        a                                      a

  完全性成立：任意 a、b 都有先后            b 与 d 之间没有边 ⇒ 不可比
  例：整数；带唯一时间戳的事件               例：因果序下的并发事件

偏序（Partial Order）

偏序关系满足以下性质：

1. 自反性：对于任意 ( a )，有 ( a <= a )。
2. 反对称性：若 ( a <= b ) 且 ( b <= a )，则 ( a = b )。
3. 传递性：若 ( a <= b ) 且 ( b <= c )，则 ( a <= c )。

特点：

• 集合中的部分元素可以比较大小，但并非所有元素都可以比较。
• 可能存在无法比较的元素（即并发事件）。

举例：

• 树形结构：同一层级的节点之间无法比较大小，只有父子节点之间可以比较。
• 家庭关系：你和你堂兄弟姐妹之间没有直接的父子关系，因此无法比较“大小”。
• 逻辑时钟：Lamport 逻辑时钟
• 向量时钟：Vector 向量时钟

偏序的应用

• 因果一致性：
  • 在分布式系统中，偏序用于描述事件的因果关系。
  • 例如，如果事件 A 导致事件 B 发生，则 ( A <= B )。
• 冲突检测：
  • 在 AP 系统中，偏序用于检测并发写操作的冲突。
  • 例如，使用向量时钟识别并发事件。

全序是偏序的特例

上面两条定义并列写，容易看漏它们的关系：全序 = 偏序 + 完全性。

性质	偏序	全序
自反性 $a\le a$	要	（由完全性推出）
反对称性 $a\le b\wedge b\le a\Rightarrow a=b$	要	要
传递性 $a\le b\wedge b\le c\Rightarrow a\le c$	要	要
完全性：任意 $a$、$b$ 可比	不要	要

所以每个全序都是偏序，反过来不成立。这条关系在分布式系统里有一个直接的后果：你手里的事件集天然只有偏序，把它变成全序必须额外加东西 —— 加进去的那个东西（Lamport 的进程编号、Raft 的任期号、或任何打破平局的规则）不是事件集自带的，见 03-逻辑时钟：Lamport 与向量 的「全序不唯一」一节。

偏序为什么不够

分布式系统对"顺序"实际有三个需求，其中有两个在偏序上没有答案：

需求	偏序够用吗
判断 $a$ 是否因果先于 $b$	够（$a<b$）
判断 $a$ 与 $b$ 是否并发	够（两个方向都不成立）
合并两份状态（取"至少知道这么多"）	不够 —— 需要一个"最小的共同上界"
求两份状态的共同过去	不够 —— 需要一个"最大的共同下界"

后两项要的就是下面两个概念。

上确界、下确界与格

设 $(P,\le )$ 是一个偏序集，取 $a,b\in P$。

• 上界：$u$ 是 $a$ 与 $b$ 的上界，当且仅当 $a\le u$ 且 $b\le u$。
• 上确界（least upper bound，记 $\bigsqcup$，也叫 join）：所有上界中最小的那个。
• 下确界（greatest lower bound，记 $\sqcap$，也叫 meet）：所有下界中最大的那个。

注意上界可能不止一个，而上确界要求唯一且最小。于是：

格（lattice）：如果 $(P,\le )$ 里任意两个元素都有上确界与下确界，就称它是一个格。

四个例子

偏序集	$\bigsqcup$（join）	$\sqcap$（meet）	是格吗
整数上的 $\le$	$max(a,b)$	$min(a,b)$	是（而且因为任意两元素可比，它是全序格）
集合上的 $\subseteq$	$A\cup B$	$A\cap B$	是
时钟向量上的逐分量序	逐分量 $max$	逐分量 $min$	是
同一偏序事件集的所有割	$C_1\cup C_2$	$C_1\cap C_2$	是（Mattern 定理 1）

第四行是 04-全局快照与虚拟时间 里的定理 1：割集合在 $\cup$ 与 $\cap$ 下构成格，$inf=C_1\cap C_2$、$sup=C_1\cup C_2$。紧接着的定理 2 把结论收紧到一致割上：一致割的集合是全体割集合的子格（sublattice）。

一个不是格的例子

「任意两元素都有上确界」不是自动成立的。 取四个元素 $a,b,c,d$，令 $a<c$、$b<c$、$a<d$、$b<d$，且 $c$ 与 $d$ 互不可比。那么：

• $a$ 与 $b$ 的上界有 $c$ 和 $d$ 两个；
• $c$ 与 $d$ 不可比，所以没有一个"最小的上界"；
• $\{a,b\}$ 没有上确界 → 这个偏序集不是格。

这个反例说明了格的定义为什么要求"最小"而不只是"存在上界"：上界不唯一的时候就无法定义合并的结果。

反例的形状：$a$、$b$ 在下，$c$、$d$ 在上，四条边 $a\to c$、$a\to d$、$b\to c$、$b\to d$。

        c       d          ← c 与 d 之间没有边，互不可比

        ↑╲   ╱↑
        │ ╲ ╱ │             a 与 b 的上界集合 = {c, d}
        │  ╳  │             其中没有「最小者」
        │ ╱ ╲ │             ⇒ a 与 b 没有上确界 ⇒ 不是格
        │╱   ╲│
        a       b

「有上界」与「有上确界」是两回事 —— 上界不唯一时就没有一个唯一的合并结果，这正是不加「最小」这个要求就不行的原因。

子格

如果 $Q\subseteq P$ 且 $Q$ 在继承来的 $\le$ 下本身也是格，就称 $Q$ 是 $P$ 的子格。判断子格不用重新验证三条偏序性质，只需验证一件事：$Q$ 对 $\bigsqcup$ 与 $\sqcap$ 封闭（$\mathrm{\forall }a,b\in Q:a\bigsqcup b\in Q\wedge a\sqcap b\in Q$）。Mattern 定理 2 的证明就是"验证一致割对 $\cup$ 与 $\cap$ 封闭"，这一步是留给读者的。

为什么分布式系统恰好需要格

上面两个代数运算对应两个工程动作：

• $\bigsqcup$（join）就是"合并"：接收一条消息后取本地状态与对方状态的并 —— 向量时钟的接收规则 $T_{jk}=max(T_{jk},M{T}_k)$ 就是逐分量 join。副本反熵（anti-entropy）合并两个副本状态时做的也是 join。
• $\sqcap$（meet）就是"求共同过去"：两份状态共同已知的那部分，用来确定一个可以回退的共同基准点。

格保证的是这两件事永远有唯一答案。 如果偏序结构不是格（像上面那个反例），合并结果就会出现多个"最小上界"互不可比的情况 —— 系统必须再挑一条规则来打破平局，而那已经越出了偏序本身能提供的保证。

Mattern 另外用格说明了一件更直观的事：任意两个一致割之间必定还存在更晚的和更早的一致割（格的封闭性）。这条性质是全局快照算法能"从任意时刻发起、得到一个合法的全局状态"的结构前提。

相关

• 03-逻辑时钟：Lamport 与向量 —— 本篇定义的偏序是全序化与逻辑时钟要解决的问题的出发点
• 04-全局快照与虚拟时间 —— 一致割集合构成的格，正是本篇「上确界 / 下确界」的直接应用
• 05-Interval Tree Clocks —— 另一条在动态系统里维护偏序的路线

参考

• Friedemann Mattern. Virtual Time and Global States of Distributed Systems. International Workshop on Parallel and Distributed Algorithms（Chateau de Bonas, France, October 1988），M. Cosnard et al. (ed.)，Elsevier Science Publishers B.V. (North-Holland), 1989.

贡献者

YJ

文件历史

最后编辑于 大约 23 小时前查看完整历史

e7758-累累累，我的token qaq

ae1ee-docs：内容完善

5f958-docs：不知道

04687-docs：笔记