Fidge 1988 — 给每个进程一份"账本向量"，让因果关系变成可判定

待复核

是什么

Fidge 1988 是一篇 11 页论文，它告诉我们：每个进程不要只记一个整数时钟，而是记一个长度为 N 的整数向量——这样不仅能判断”谁先谁后”，还能精确判断”两件事是不是真的并发”。日常类比：lamport-1978 那篇里每个人手上只有一本自己的账本，记得我的事。Fidge 让每个人手上多了一份全员账本表——我的那一格记自己事件数，别人那 N-1 格则记”我从他们那里听说过的最新进度”。每次收到来信就把对方表里的进度合并进自己的表，两份表一比就能精确说出”你比我多走了几步” vs “我们各走各的，谁也没影响过谁”。

更具体地说：lamport-1978 只能给出 a→b ⇒ C(a)<C(b) 的必要条件，无法检测并发。Fidge 给进程 i 维护 N 维向量 V_i：本地事件 V_i[i]+=1；发消息时 piggyback 整个 V_i；收消息时逐格 max 再把自己那格 +1。于是 a→b ⟺ V(a) < V(b)；a‖b ⟺ 两向量不可比。

40 年过去，Dynamo version vector、CRDT 的 dot、Riak causal context 都是直系后代；Jaeger 一类 tracing 的 parent/child span 只是「保留因果边」的远亲，并不带 version vector。

为什么重要

不理解这篇，下面这些事都没法解释：

为什么 Dynamo 论文里购物车冲突合并用的是 “version vector”，而不是单一时间戳
为什么 crdt-shapiro-2011 里 OR-Set 删除元素要带一个 “dot”——dot 就是向量时钟的一格
为什么 chandy-lamport-1985 拍快照后还要靠向量判断”哪些消息算 in-flight”
为什么 Riak 给客户端返回多版本（sibling）时附带 “causal context”，让客户端下次写入时合并

核心要点

Fidge 的协议出奇地简洁，就三条规则（每个进程 i 维护向量 V_i，长度 = 进程数 N）：

本地事件：V_i[i] += 1。类比：每个人在自己账本表的”我”那一行画一笔。
发消息：先 V_i[i] += 1，然后把整个向量 V_i 当 piggyback 塞进消息。类比：寄信前在我自己的格子记一笔，再把整张账本表复印一份附进去。
收消息：对每个 k 取 V_i[k] = max(V_i[k], V_msg[k])，再 V_i[i] += 1。类比：把对方的账本表和我的逐格取大值（“他们已经知道的，我也知道了”），最后在我的格子再画一笔表示”我读完信了”。

比较两个向量 V(a) 和 V(b)：

逐分量 V(a)[k] ≤ V(b)[k] 且至少一处严格 < ⟹ a → b（a 因果先于 b）
完全相等 ⟹ 同一事件
双向都有严格大于 ⟹ a ‖ b（真正并发）

这套规则保证 a → b ⟺ V(a) < V(b) 双向成立——这是 Lamport 时间戳做不到的。

实践案例

案例 1：Dynamo 购物车合并的 version vector

Dynamo 论文里购物车被两个 region 同时修改，version vector 让客户端能区分”同步版”和”分叉版”：

# 简化伪码
class Cart:
    def __init__(self, items, vv):
        self.items = items
        self.vv = vv  # {node_id: counter}

def write(cart, node_id, new_items):
    vv = dict(cart.vv)
    vv[node_id] = vv.get(node_id, 0) + 1
    return Cart(new_items, vv)

def dominates(va, vb):
    # V(a) < V(b)：逐分量 ≤ 且至少一处严格 <
    keys = set(va) | set(vb)
    less_or_eq = all(va.get(k, 0) <= vb.get(k, 0) for k in keys)
    strict = any(va.get(k, 0) < vb.get(k, 0) for k in keys)
    return less_or_eq and strict

def merge(a, b):
    if dominates(a.vv, b.vv):
        return [b]          # a 更旧，只留 b
    if dominates(b.vv, a.vv):
        return [a]
    # 并发分叉：逐节点取 max 合成 vv，并保留两份 sibling 给客户端 resolve
    keys = set(a.vv) | set(b.vv)
    vv = {k: max(a.vv.get(k, 0), b.vv.get(k, 0)) for k in keys}
    return [Cart(a.items, vv), Cart(b.items, vv)]

逐部分解释：

vv 是稀疏向量（只记真正写过的节点），等价于 Fidge 的 V_i
dominates 就是论文里的 V(a) < V(b)，用来识别 stale 写入
双向都不 dominate 就是并发分叉，Dynamo 把两份 sibling 都返回让客户端 resolve

案例 2：CRDT OR-Set 用 dot 标识每次添加

crdt-shapiro-2011 里 OR-Set（Observed-Remove Set）添加元素 x 时，给这次操作打一个 dot = (node_id, counter)：

class ORSet:
    def __init__(self, node_id):
        self.node_id = node_id
        self.counter = 0
        self.adds = {}  # element -> set of dots
        self.removes = set()  # set of dots

    def add(self, x):
        self.counter += 1
        dot = (self.node_id, self.counter)
        self.adds.setdefault(x, set()).add(dot)

    def remove(self, x):
        for dot in self.adds.get(x, set()):
            self.removes.add(dot)

逐部分解释：

dot (node_id, counter) 是 vector clock 的一格——每个 add 操作都有唯一向量坐标
remove 只删”我看到过的那些 dot”，并发的 add 不会被误删
合并时把两侧 adds 和 removes 取并集，这就是论文里的 V_i 与 V_msg 取 max

案例 3：用向量比较检测真正并发

def compare(va, vb):
    less = any(va[k] < vb[k] for k in keys)
    more = any(va[k] > vb[k] for k in keys)
    if less and not more: return "a -> b"
    if more and not less: return "b -> a"
    if not less and not more: return "a == b"
    return "a || b"  # concurrent

逐部分解释：

向量比较是 partial order——可能两个都 less、两个都 more、或者两边互不包含
“互不包含” 就是 Lamport 时间戳永远做不到的判定
这正是因为 vector 在每一格里保留了”我从对方那里听到的最新进度”

踩过的坑

把 ≤ 当成 <：V(a) ≤ V(b)（每分量都 ≤）允许 a == b 同事件，必须额外要求”至少一处严格 <“才表示 a → b 真因果先。混淆会让”自己”被判成”自己的祖先”。
N 必须固定：进程动态加入/退出时，向量长度变化，老向量没有新进程那一格，比较会失败。工业上要么配死 N（Dynamo 节点数固定），要么用 ITC（Interval Tree Clock）/ Dotted Version Vector 解决。
每条消息都带 O(N) 字节：1000 节点集群每条消息要 8KB（uint64 × 1000）只为带向量。大集群用 sparse vector（只记非零项）+ 周期 GC（pruning 策略见 Almeida-Baquero 2014）。
进程 ID 必须稳定：节点重启后复用 ID，新事件会”接着用”老的 V[i] 计数，但实际语义是新进程，会污染所有人的判断。要用 epoch（重启计数）+ id 组合，或永久 UUID。
Mattern 1988 是同一时期独立工作：社区常把 Fidge 1988 和 Mattern 1988/1989 一起引用，统称 vector clock。两者算法等价，论文角度不同——Fidge 偏可视化和 partial order，Mattern 偏 virtual time 抽象。

适用 vs 不适用场景

适用：

进程数已知且不大的集群（< 几百节点）
需要精确检测并发的场景（multi-master 写冲突、协同编辑）
CRDT 数据结构（OR-Set, RGA, MV-Register 都内置 version vector）
Causal consistency 数据库的 dependency tracking

不适用：

进程数动态变化（用 ITC / Dotted Version Vector / Bloom Clock）
超大规模集群（O(N) 太贵，可降级成 lamport-1978 时间戳 + 牺牲并发检测）
需要绑定真实物理时间（用 spanner TrueTime 或 HLC）
跨数据中心强一致事务（共识协议如 raft 才够）

历史小故事（可跳过）

1978：Lamport 逻辑时钟只能判 a→b 不能判 a‖b
1988：Fidge 在 ACSC 发表本文；同年 Mattern 独立提出 Virtual Time，思想几乎一致
1989：Mattern 长文被社区更频繁引用
2007 / 2011：Dynamo 把 version vector 推到工业；crdt-shapiro-2011 嵌进 OR-Set / RGA
2010s：Yjs / Automerge / Riak DT 让协同编辑大规模用上变种

学到什么

partial order 真正可判定：向量时钟把 Lamport 的必要条件升级为充要条件
空间换信息：用 O(N) 空间换「是否真并发」的判定能力
同时期独立发现：Fidge 与 Mattern 几乎同时给出同一思想
不是全序：不是所有事件都可比——这是分布式系统诚实的时间观

关联

lamport-1978 —— 前置工作，Fidge 在它的基础上把单整数升级成向量
chandy-lamport-1985 —— 全局快照，向量时钟可用来判定 marker 之间消息归属
crdt-shapiro-2011 —— OR-Set / MV-Register 直接以 dot（向量一格）标识每次操作
paxos —— 不依赖 vector clock，但共识协议的 round 编号本质是退化版 Lamport 时钟
raft —— term + log index 同样是退化版 Lamport，向量在多 leader 系统才用
spanner —— 反命题：用物理 TrueTime 替代逻辑时钟，避开 O(N) 成本

反向链接

hlc-2014 —— HLC 2014 — 把逻辑时钟和物理时钟合一，让普通服务器也能拍一致快照
linearizability-1990 —— Linearizability 1990 — 让并发对象看起来像一次只执行一个操作
mattern-1989 —— Mattern 1989 — 虚拟时间与全局状态：把分布式时钟变成 N 维笛卡尔积
mills-ntp-1991 —— NTP 1991 — 用四个时间戳和一棵服务器树，让全互联网的钟差几毫秒
sequential-consistency-1979 —— Sequential Consistency 1979 — 多处理器内存模型的第一个正确性标准

Fidge 1988 — 给每个进程一份"账本向量"，让因果关系变成可判定

是什么

为什么重要

核心要点

实践案例

案例 1：Dynamo 购物车合并的 version vector

案例 2：CRDT OR-Set 用 dot 标识每次添加

案例 3：用向量比较检测真正并发

踩过的坑

适用 vs 不适用场景

历史小故事（可跳过）

学到什么

延伸阅读

关联

反向链接