---
title: 冲突解决
url: https://doc.liz6.com/distributed-systems/03-replication-and-consistency/02-conflict-resolution
locale: zh
area: distributed-systems
tags:
- distributed-systems
- 复制与一致性
date: 2026-06-30
modified: 2026-06-30
description: 多 leader 和 leaderless 复制下冲突不可避免——两个节点同时对同一 key 写入。从粗暴的"最后写入胜出"到版本向量追踪因果,再到 CRDT 用数学性质(结合律/交换律/幂等律)保证自动合并,冲突解决的方案越强、代价越大。
---

# 冲突解决

> 多 leader 和 leaderless 复制下冲突不可避免——两个节点同时对同一 key 写入。从粗暴的"最后写入胜出"到版本向量追踪因果,再到 CRDT 用数学性质(结合律/交换律/幂等律)保证自动合并,冲突解决的方案越强、代价越大。

多 leader 和 leaderless 复制的代价是**冲突不可避免**——两个节点同时收到对同一 key 的不同写入，且无法通过 happens-before 关系判定先后。

## Last-Write-Wins (LWW)

按时间戳决定：最新的时间戳获胜，旧的值被丢弃。简单、高效，但可能丢数据：

```
Node A: write(x="Alice")  ts=1000
Node B: write(x="Bob")    ts=1001
→ "Bob" wins, "Alice" 被覆盖
如果这两个写是并发的（没有因果依赖），LWW 丢弃了"Alice"——数据丢失
```

LWW 在 Cassandra 中是默认策略，Riak 可选。代价是"数据可能丢失"——对于计数器（如点赞数），这是不可接受的。

## 版本向量 (Version Vectors)

不依赖物理时间，而是用各节点的逻辑时钟来判定 happens-before 关系（见 01-02）。当版本向量不可比较时，标记为**并发冲突**，交给应用层或自动合并。

Dynamo 的做法：读操作返回所有不可比较的版本（siblings），客户端必须自己合并（如购物车合并：用户同时在不同设备加了不同商品 → client 显示两者的 union）。如果 client 不合并而直接写入，server 也会存储多个 siblings。

## CRDT (Conflict-free Replicated Data Types)

数学上保证并发操作可交换——自动收敛，无需应用层处理冲突。

### G-Counter (Grow-only Counter)

```
每节点维护独立的 counter[N]:
  node_i 的 Increment(): counter[i] += 1
  Value = sum(counter[0..N])   ← 永远正确的总值 (因为只增不减, 无冲突)

merge(self, other): 对每个 i: counter[i] = max(self[i], other[i])
→ 合并时取每个节点各自的最大值 (因为 increment 是本地的, 其他节点可能没收到最近的值)
```

### PN-Counter (Positive-Negative Counter)

支持递增和递减：

```
每个节点维护两个 G-Counter: P[i] (正) 和 N[i] (负)
  Increment(): P[i] += 1
  Decrement(): N[i] += 1
  Value = sum(P[0..N]) - sum(N[0..N])
```

### OR-Set (Observed-Remove Set)

支持 add 和 remove 的集合：

```
每个元素 add 时分配 unique tag (如 UUID)
  add(e): 生成 tag t; S = S ∪ {(e, t)}
  remove(e): 对 S 中所有 e 的 tags, 记录在 tombstones 中
  Value = {e | (e,t) in S 且 t 不在 tombstones 中}

merge(self, other): S = self.S ∪ other.S (集合并), tombstones = self.T ∪ other.T
→ 只要 tag 没有被标记为 "removed", 元素就存在
→ 并发 add(e) 和 remove(e): add 有 tag t, remove 记录 tombstones 含 t → 结果正确
```

## 应用选择

| 场景 | 推荐 |
|------|------|
| 简单键值, 容忍数据丢失 | LWW (Cassandra default) |
| 并发修改需要语义保留 | 版本向量 (Dynamo, Riak) |
| 计数器 | PN-Counter |
| 集合/列表 | OR-Set, RGA (Replicated Growable Array) |
| 富文本协作 | CRDT (Yjs/Automerge for collaborative editing) |

## 参考

- **论文**: "A Comprehensive Study of Convergent and Commutative Replicated Data Types" (Shapiro et al, 2011)
- **实际实现**: github.com/automerge/automerge, docs.yjs.dev

*Keywords: LWW, version vector, CRDT, G-Counter, PN-Counter, OR-Set, causal consistency, concurrent writes*