冲突解决

多 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 → 结果正确

应用选择

参考

• 论文⁠: "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