KV存储笔记：版本、并发写与冲突解决（LWW / vector clock）

复制 + quorum 的系统一旦允许在故障/分区下继续接受写，就必须回答：当同一 key 出现并发写时，系统如何定义“最终值”？

这里的“并发”不是多线程意义，而是分布式因果意义：两个写互相不可比较（没有 happens-before）。

本文聚焦三种常见策略：

• LWW（Last-Write-Wins）：用时间戳强行线性化
• vector clock + siblings：保留多个并发版本，把合并交给上层
• 单主/租约：通过领导者把写线性化（本质是避免并发）

1. 为什么会出现并发写：分区 + 可用性选择

以 N=3 为例，若系统选择 W=1（更可用）：

• 分区时两侧都可能分别写入不同副本集合
• 当分区恢复，这些写会在修复中“相遇”，形成并发版本

即使 W=2，也可能出现：

• coordinator 超时重试导致重复写
• 不同 coordinator 在配置切换时对同一 key 接受写（epoch 设计不严谨）

工程结论：只要系统不是严格单主线性化，并发版本就是常态风险。

2. 版本的基本要求：可比较、可判定并发

一个版本系统至少要支持：

• 比较新旧（A 是否更新于 B）
• 判定并发（A 与 B 是否并发）

常见版本类型：

• 单调序列号（需要单主或全局序列源）
• 时间戳（需要时钟假设）
• 逻辑时钟（Lamport：可比较但无法判定并发）
• 向量时钟（vector clock：可判定并发）

3. LWW：简单，但把风险转移到时钟与重试

3.1 LWW 的定义

为每次写附带一个 timestamp，取 timestamp 最大的版本作为 winner：

winner = argmax(version.timestamp)

3.2 LWW 的工程陷阱

• 时钟漂移：不同节点时间不同，会导致“较旧写被认为较新”
• 回拨：NTP 校时造成时间跳变
• 客户端时间戳：风险更大，且与客户端重试耦合

若仍要用 LWW，至少要明确：

• timestamp 由谁生成（服务端更常见）
• 单调性如何保证（逻辑时钟 + 物理时钟混合）
• 时钟异常时的降级策略（拒写/强制走单主）

3.3 LWW 适用边界

适用于：

• value 本身可被覆盖，业务只关心“最新写”
• 能容忍小概率错误覆盖（或有上层补偿）

不适用于：

• 计数器、集合更新等需要“合并语义”的场景

4. Vector Clock：保留并发版本，明确冲突存在

4.1 向量时钟的直觉

每个 key 的版本携带一个向量：

vc = { nodeA: 5, nodeB: 2, nodeC: 7 }

当某节点写入时，递增自己的分量并携带整个向量。

两个版本 vc1 与 vc2 的关系：

• 若对所有节点 (vc1[i] <= vc2[i])，且至少一个严格小于，则 vc2 “更新于” vc1
• 若既不满足 vc1<=vc2 也不满足 vc2<=vc1，则并发

4.2 siblings：并发版本集合

当系统检测到并发，会把多个版本都保留：

key -> [ (value1, vc1), (value2, vc2), ... ]

读可能返回多个值（siblings），由上层合并并写回“合并后的新版本”。

4.3 代价与工程问题

• 元数据膨胀：向量长度随节点数增长；工程上常做裁剪/只保留相关节点
• 并发版本爆炸：若上层不及时合并，siblings 会持续累积
• 读写路径复杂：读要合并、修复要传播多个版本

因此常见工程约束：

• siblings 上限（超过则强制 LWW 或拒写）
• 自动合并策略（对可自动合并的数据类型）
• 只在“需要并发语义”的表启用 vector clock

5. 另一条路：避免并发（单主/租约/共识）

如果系统目标是更强的一致性与更简单的读写语义，通常会选择：

• 单主复制（primary-backup）
• leader lease（租约）限制并发 leader
• Raft/Paxos 把写线性化

代价是：

• 可用性在分区下下降（写需要 leader/quorum）
• 时延与实现复杂度上升

工程上常见分层：

• 强一致关键路径：走共识/单主
• 大吞吐弱一致路径：走多主 + 修复

6. 冲突解决策略（上层视角）

当读到 siblings，需要一个 merge 函数：

• 集合：取并集（加 tombstone 处理删除）
• 计数器：用 CRDT（PN-Counter 等）
• 最后写：回到 LWW（但明确语义）
• 业务合并：例如购物车、点赞等

关键是：merge 必须是幂等的，且在重试/重复执行下不会扩大错误。

7. 小结

冲突解决没有银弹，只有明确的语义选择：

• LWW 简单但依赖时钟与容错假设
• vector clock 能表达并发，但需要控制元数据与 siblings 增长
• 单主/共识能避免并发，但牺牲分区下写可用性与实现复杂度

下一篇笔记会把“删除语义”补齐：tombstone、TTL 与 compaction/修复的交互，避免“删了又回来”。