pengtao-tech

CRDT 向量时钟的适用性判断

8分钟阅读

CRDT / 向量时钟的适用性判断

一句话速记

向量时钟（Vector Clock）：每个节点维护所有节点的逻辑时钟向量，用于判断事件先后顺序和检测并发冲突——“我写的时候对方的版本是多少”；CRDT（Conflict-free Replicated Data Type）：特殊设计的数据结构，所有合并操作（merge）满足交换律、结合律、幂等律，无论什么顺序合并，最终结果都相同——彻底避免冲突。工程中 CRDT 适合协同编辑、分布式计数器、在线状态等场景；向量时钟适合检测冲突，冲突解决还需业务逻辑。

关键细节

1）向量时钟

每个节点 i 维护一个向量 V[i] = [v1, v2, v3, ..., vn]
  vj 表示节点 i 见到的节点 j 的最新时钟值

节点 A 发送消息：附上自己的向量时钟 V[A]
接收方 B：V[B] = component-wise max(V[B], V[A])，然后 V[B][B]++

并发判断：
  A 发生在 B 之前：V[A] ≤ V[B]（各分量都 ≤）
  A 发生在 B 之后：V[A] ≥ V[B]（各分量都 ≥）
  A 和 B 并发：V[A] 和 V[B] 既不 ≤ 也不 ≥（某些分量大、某些分量小）

示例：
  节点 A 发送 msg1，V[A]=[1,0,0]
  节点 B 收到并处理，V[B]=[1,1,0]
  节点 C 也收到 msg1（同时收到），V[C]=[1,0,1]
  → V[B] 和 V[C] 并发（B[1]=1>0 但 B[2]=0<1）→ 检测到冲突，需要解决

适用场景：

✅ 分布式 KV 存储（DynamoDB 用向量时钟检测写冲突）
✅ 版本控制系统（Git 的 merge 底层思想类似）
✅ 需要检测因果关系的分布式系统

❌ 不适用：
  节点数量很多（向量大小 = 节点数，开销大）
  只需要全序（向量时钟是偏序）
  需要自动解决冲突（向量时钟只检测，不解决）

2）CRDT（Conflict-free Replicated Data Type）

核心思想：

设计数据结构，使得 merge 操作满足：
  交换律：merge(A, B) = merge(B, A)（顺序无关）
  结合律：merge(A, merge(B, C)) = merge(merge(A, B), C)（分组无关）
  幂等律：merge(A, A) = A（重复合并无害）

→ 多副本最终收敛到同一状态（无论同步顺序如何）

常见 CRDT 类型：

G-Counter（只增计数器）：
  每个节点维护自己的计数器 counter[node_id]++
  合并：counter = max(counter[i], other[i]) for each i
  读取：sum(counter)
  → 分布式 DAU、点赞数、播放次数

PN-Counter（可增减计数器）：
  P（增）+ N（减）两个 G-Counter
  合并各自 max，值 = sum(P) - sum(N)
  → 库存（可以减少但不能为负数需额外校验）

LWW-Register（Last Write Wins）：
  每个写操作带时间戳，合并时取最新时间戳的值
  → 最简单，但可能丢失并发写
  → 适合：最后一次更新胜出的场景（用户状态）

OR-Set（Observed-Remove Set，可观察删除集合）：
  每个元素添加时带唯一标签
  删除：标记该标签为删除
  合并：存在 add 标签且未被删除 → 元素存在
  → 协同编辑的标签/成员列表

RGA（Replicated Growable Array）：
  支持插入和删除的序列（文本编辑）
  每个插入操作有唯一 ID，用于保证最终顺序
  → Google Docs、Notion 等协同编辑的底层

3）适用场景对比

技术          适用场景                                   代表产品
────────────────────────────────────────────────────────────────────
向量时钟      检测并发冲突（再由业务/用户解决）          DynamoDB, Riak, Git
CRDT（G/PN）  分布式计数（DAU、点赞、库存）              Redis（Streams/HLL），Riak
CRDT（LWW）   最后写赢的简单状态（在线状态、配置）       Redis（一般 SET 操作）
CRDT（OR-Set）协作共享标签、成员列表                     Figma, Notion
CRDT（RGA）   实时协同文本编辑                            Google Docs, VS Code Live Share
操作变换（OT）协同编辑（CRDT 的前辈方案，更复杂）        Google Wave（已废弃）

4）工程中的选型建议

绝大多数互联网业务场景：
  用"乐观锁 + 版本号"足够（简单、够用）
  
需要多节点并发写入、容忍网络分区时：
  计数类：CRDT G/PN Counter
  状态类：LWW Register（带时间戳的最后写赢）
  
需要高精度冲突检测（不想丢数据）：
  向量时钟（检测冲突）+ 展示给用户选择（类似 Git conflict）
  
实时协作编辑产品：
  使用 CRDT（Yjs, Automerge 等成熟库）
  不要自己实现 RGA（极其复杂）

延伸追问

  • Q：CRDT 的 LWW 策略有什么问题？ → 依赖时钟同步（NTP）。如果节点时钟不同步，可能导致”更旧的写操作”时间戳更大，覆盖”更新的写操作”。解决方案：用逻辑时钟（HLC，混合逻辑时钟）替代物理时钟，或接受 LWW 的语义（业务上最后一次 click 胜出是合理的）。
  • Q：Redis 是 CRDT 吗？ → Redis 本身不是 CRDT（单节点主从复制，不是无中心多主）。但 Redis Enterprise 有 Active-Active（CRDT-based）模式，多地域多主写，用 CRDT 保证冲突自动合并。开源 Redis 的 INCRBY 操作在并发下通过单线程保证原子性，不需要 CRDT。
  • Q：向量时钟和逻辑时钟（Lamport Clock）的区别？ → Lamport Clock（标量逻辑时钟）：只能判断”A 一定发生在 B 之前”，无法判断并发（不能判断”A 和 B 是并发的”）。向量时钟（偏序）：可以精确判断”A 先于 B”、“B 先于 A”、“A 和 B 并发”。向量时钟是 Lamport Clock 的多维扩展。

我的记法

  • 向量时钟 = 每节点维护向量，判断先后/并发，不解决冲突
  • CRDT = 特殊设计数据结构，合并满足交换+结合+幂等，自动无冲突
  • G-Counter = 分布式计数；LWW = 最后写赢；OR-Set = 协作列表；RGA = 协作文本
  • 日常业务：乐观锁够用；协作产品 / 多主写：考虑 CRDT
  • 一句话：「向量时钟检测冲突，CRDT 从设计上消灭冲突」

状态

  • 已背速记
  • 能解释 G-Counter 的合并规则
  • 能判断什么场景用 CRDT vs 向量时钟

关系图谱