向量时钟如何帮助解决并发版本冲突?
简化版
向量时钟为每个参与副本维护计数器,可判断版本 A 发生在 B 之前、B 在 A 之前,或两者并发。 若 A 的每个分量都不大于 B 且至少一个更小,则 A 因果早于 B;双方各有更大分量则并发,需要业务合并或保留 siblings。 它能检测冲突,不能自动决定哪个业务值正确。
详细版
节点本地写时递增自己的分量,接收版本时逐分量取最大,再为新事件递增本地分量。 例如 A={A:2,B:1},B={A:2,B:3},前者先于后者;C={A:3,B:1} 与 B 则并发。
向量大小随参与者增长,动态集群常用版本向量、dotted version vector 或截断策略。 截断会丢因果信息,可能把并发误判为覆盖。 冲突合并后产生一个支配两个父版本的新向量,并保留合并审计。
完整版教学
一、为何标量版本不足
单个递增版本需要中心分配者。 物理时间受漂移影响,不能可靠表示因果。 向量时钟把各参与者的已知进度保存在版本中。
向量时钟回答“是否有因果先后”,不回答“业务上谁赢”。
二、更新规则
local event at node A:
V[A] = V[A] + 1
receive W then create event:
V = componentWiseMax(V, W)
V[A] = V[A] + 1
合并知识后再递增,表示新事件因果依赖已接收版本。
三、比较规则
| A 与 B | 判断 |
|---|---|
| 所有 A[i] <= B[i] 且至少一项小于 | A happens-before B |
| 所有 B[i] <= A[i] 且至少一项小于 | B happens-before A |
| 相等 | 同一因果版本 |
| 双方各有更大分量 | 并发 |
比较必须覆盖缺失分量,缺失通常按 0 处理。
四、并发示例
副本 X 从 {X:1,Y:1} 写成 {X:2,Y:1}。 网络分区中 Y 写成 {X:1,Y:2}。 两个向量互不支配,因此不能把任一当作旧版本直接丢弃。 系统保留 siblings,交给购物车集合合并或人工规则。
五、冲突合并
若业务合并两个购物车版本,新向量先逐分量取最大,再由执行合并的节点递增。 合并结果支配两个父版本,后续可安全淘汰父 siblings。 余额等不可交换数据不能简单求和或取最大。 合并函数最好满足确定性、交换性和幂等性。
六、元数据膨胀
每个客户端都作为分量会无限增长。 实际系统常按固定副本、区域或版本向量 actor 建模。 Dotted Version Vector 将一次事件与上下文分开,改善并发表达。 截断旧分量是工程权衡,必须评估丢因果带来的误覆盖风险。
七、存储和观测
版本与值一起原子存储,不能内容更新后丢失向量。 监控 siblings 数量、并发冲突率、向量大小和自动合并失败。 对版本编码进行跨语言兼容测试。 离线修复也要生成新因果版本,不能直接篡改值。
八、常见误区与追问
- 误区:向量最大的版本就是最新。 并发向量不存在全序最大者。
- 误区:它能自动选正确值。 它只检测因果与并发。
- 误区:物理时间可完全替代。 时钟漂移和并发会丢因果。
- 误区:随意删向量分量无影响。 可能误判覆盖关系。
- 追问:并发后怎么办? 保存 siblings,并按业务合并或人工裁决。
- 追问:合并版本如何生成? 取父向量逐分量最大,再递增合并者分量。
- 追问:为什么不适合无限客户端? 元数据随 actor 数增长。
九、加强记忆
- 每个 actor 维护自己的计数分量。
- 逐分量偏序判断因果先后。
- 互不支配就是并发冲突。
- 检测与业务合并是两件事。
- 合并结果支配父版本,元数据膨胀需受控。