并发写冲突解决：版本向量与 CRDT
本文基于模型知识整理（生成时未联网核对），关键结论建议对照经典文献复核。
一句话定义
当两个副本各自收到对同一数据的并发更新时，系统必须决定"谁是最终版本"：要么按某种策略强行取舍（LWW、人工合并），要么采用数据结构本身保证可交换合并的 CRDT，使任意顺序合并都收敛到同一结果。
为什么重要
多主与无主复制（kp-011、kp-014）把冲突从异常变成日常；协作编辑、离线优先应用、购物车合并都绕不开它。冲突解决选错策略（尤其是无脑 LWW）会静默丢数据——这是 AP 系统最常见的数据损失根因。
前置知识
kp-004（向量时钟/并发判定）。
核心概念
- 冲突的判定：两次写互不为因果（向量时钟不可比，kp-004）即为并发，需要解决策略。
- Last-Write-Wins（LWW）：按时间戳/逻辑编号保留最大者；简单，但丢失被舍弃的更新，且依赖时钟（kp-003）。
- 版本向量（version vector）：每副本对每 key 维护向量时钟，检测并发并保留多版本（Dynamo 的 sibling），交由应用合并。
- CRDT（Conflict-free Replicated Data Type）：数据结构满足交换律、结合律、幂等性，任意乱序、重复合并都收敛；分状态型（state-based，如 G-Counter）与操作型（op-based，要求消息恰好一次按因果序投递）。
- 常见 CRDT：G-Counter（只增计数）、PN-Counter（可增减）、LWW-Register/Set、OR-Set（可加可删集合，删除用 tombstone）、序列 CRDT（协作编辑，如 RGA）。
原理与机制
CRDT 为何必然收敛：状态型 CRDT 的合并操作定义为格上的 join（逐分量取 max / 并集），join 满足交换、结合、幂等 ⇒ 各副本以任意顺序、任意次序反复合并，最终状态唯一——这与消息到达顺序无关，天然适配 gossip 与 at-least-once 投递（kp-008、kp-010）。
代价：状态型需要携带完整状态或增量（网络开销与状态增长），集合类需要 tombstone（墓碑）记录删除，永不"彻底删除"导致内存增长，需要定期压缩。
LWW 的陷阱：并发更新中较旧时间戳的一方被静默丢弃。若两次更新语义正交（改了购物车的两个不同商品），LWW 丢一方——正确做法是结构分离（每个商品独立 key）或用 CRDT 合并。经验法则：LWW 只适用于"单值覆盖语义且业务可接受丢失"（如用户改昵称）。
公式或模型
- G-Counter 合并：每个副本 i 维护计数 C_i，状态为向量，值 = ΣC_i，合并 = 逐分量 max。
- OR-Set：添加带唯一 tag，删除只删已见 tags（remove(add-wins)），合并 = adds ∪ (removes 与其后见 tags 的差)。
直观类比
两个人同时编辑一份共享文档：LWW 相当于"谁最后保存就用谁的，另一个人的修改全部作废"；CRDT 相当于"改动逐条记录、可交换合并"，两人怎么同步顺序打乱，最终文档都一样。
实例或案例
- Amazon Dynamo 购物车：并发写保留多版本，客户端合并时取并集——偶尔多出一件已删商品可接受，丢商品不可接受。
- Redis Enterprise CRDB / Riak：内建 Counter/Set 等类型做跨地域合并。
- 协作编辑器（Figma/Google Docs 类）：序列 CRDT 或 OT（操作变换）保证并发编辑收敛；Yjs/Automerge 是开源 CRDT 实现。
- 离线优先应用（笔记、看板）：本地库离线写，联网后 CRDT 合并，无中心服务器裁决。
常见误区
- 误区一："LWW 简单所以先用"。它静默丢并发更新，多数业务语义下是数据损失；仅覆盖型单值场景适用。
- 误区二："CRDT 万能"。CRDT 只对特定代数结构成立；任意 JSON 合并不存在通用无冲突方案（需要专门设计或引入协调服务）。
- 误区三："CRDT 空间无限膨胀"。tombstone 与版本历史需要压缩策略（如按因果稳定点裁剪），实现时必须考虑。
与其他知识点的关系
自测题
- CRDT 收敛依赖哪三条代数性质？各自挡住什么问题？
答：交换律（消息顺序无关）、结合律（分批合并等价）、幂等性（重复投递无副作用），共同保证乱序+重复消息下最终状态唯一。
- 为什么 OR-Set 删除要靠 tombstone？
答：删除必须与"稍后到达的并发添加"可判序；只记录"删了这个值"会误删并发新增，用唯一 tag 让删除只针对已见添加，实现 add-wins 语义。
- 什么场景可以放心用 LWW？
答：单值覆盖语义（如昵称、头像）、并发写丢失业务可接受，且时钟排序偏差影响可控。
延伸阅读
- Shapiro 等, "Conflict-free Replicated Data Types"（SSS 2011）。
- Kleppmann《DDIA》第 5 章多主复制冲突节。
- Kleppmann & Beresford, "A Conflict-Free Replicated JSON Datatype"（IEEE TPDS 2017）。