它是什么
在多个副本都接受写入的存储里，有三个问题环环相扣。读和写必须各访问多少个副本，才能彼此看见（quorum）？当两次写入在互不知情的情况下发生时，怎么发现（版本控制）？发现之后，怎么合并（冲突解决）？这些就是 Dynamo、Cassandra 这类”始终可写”系统背后的机制，也是协同编辑器背后的机制。
Important
核心要点： 在 leaderless 存储里，冲突不是 bug，而是”始终可写”这份契约的购买价格。设计上的问题是你要诚实地发现它们（vector clock、sibling），还是悄悄地抹掉它们（last-writer-wins）。墙上时钟的时间戳分不清”更晚”和”并发”。
何时需要它
“在分区期间，两个用户写同一个 key 会怎样？“是任何复制存储的标准追问，而资深的回答会说出时间戳为什么失效、取代它的机制是什么，以及由谁负责合并。
Note
面试信号：
在同一个回答里说”R + W > N 并不能做到 linearizable”和”LWW 会悄悄丢写”，说明你读得比标题更深。再补一句：合并函数是一个产品决策，因为存储本身不知道语义。
Quorum
每个 key 有 N 个副本，一次写入在 W 个确认后成功，一次读取咨询 R 个副本。如果 R + W > N，读集合和写集合必然相交，所以每次读中至少有一个副本拥有最新的已确认写入。
| N | W | R | R + W > N？ | 表现 |
|---|---|---|---|---|
| 3 | 2 | 2 | 是 | 保证相交；两侧都能容忍一个慢或死的副本 |
| 3 | 1 | 1 | 否 | 最快且始终可用；读可能错过最近的写 |
| 3 | 3 | 1 | 是 | 读很快；一个死副本会阻塞所有写 |
| 3 | 1 | 3 | 是 | 写很快；读侧承担协调成本 |
这种相交让过期读成为例外，而不是常态。它并不能让系统 linearizable：并发写入和 sloppy quorum 仍然会产生异常。一个合理的默认值是 N=3, W=2, R=2，并允许按请求覆盖。
Sloppy quorum 与 hinted handoff。 如果某个 key 的 N 个副本中有一个宕机，严格的 quorum 会让写失败，或者副本数不足。Sloppy quorum 会把缺失的那份副本写到环上下一个健康的节点，并附上一个 hint（“这份属于节点 C；等它回来时交给它”）。这次写入用一个替身满足了 W，所以只要任意 W 个节点在线，集群就接受写入，而不是任意 W 个特定节点。代价：在 hint 被重放之前，读 quorum 可能与写 quorum 不相交。
为什么时间戳会失效
朴素的合并方式是 last-write-wins（LWW）：保留墙上时钟时间戳更晚的版本。
算例。 一个购物车 key 在分区两侧的版本相同。左侧的客户端在 14:00:00.003 加入商品 X；右侧的客户端在 14:00:00.007 加入商品 Y。LWW 保留右侧的版本，悄悄丢掉了 X。没有任何日志，顾客只会看到少了一件商品。它失败有两个原因：
- 时钟偏差是真实存在的。 NTP 能把时钟保持在大约 1 到 100 ms 以内，而不是微秒，所以”更晚”可能只是”那个节点的时钟走快了”。
- 因果性是看不见的。 时间戳分不清”这次写入取代了另一次”和”这两次写入是并发的、都应该保留”。
LWW 只适用于真正属于覆盖型的数据（session token、设备心跳），这类数据里最新的物理值正是你想要的。
Vector clock
Vector clock 是一个从节点 id 到计数器的映射，随每个值一起存储。它记录的是因果历史，不是时间。
- 在 coordinator X 上写入时，把 X 的条目加一。新版本在因果上取代它所继承的任何版本。
- 如果 V1 中每个条目都不小于 V2 的对应条目（并且有一个严格更大），就说 V1 继承自 V2。此时 V1 更新，V2 可以丢弃。
- 如果两个版本互不继承，它们就是并发的。都不是更新的，所以两者都必须作为 sibling 保留下来。
算例。 购物车起初在各处都是 [(A,3)]。分区期间，左侧通过 A 写入，得到 [(A,4)]；右侧通过 C 写入，得到 [(A,3),(C,1)]。比较它们：A 的条目是 4 对 3（左侧在 A 上领先）；C 的条目是 0 对 1（右侧在 C 上领先）。谁也不继承谁，所以它们是并发的，coordinator 会把两个 sibling 连同一个合并后的 context token 一起返回给客户端。
解决 sibling
客户端（或应用）合并 sibling，并带着合并后的 context 写回：
Sibling 1: { items: [X, Y] } <- [(A,4)]
Sibling 2: { items: [Y, Z] } <- [(A,3),(C,1)]
Merged: { items: [X, Y, Z] } 用 context [(A,5),(C,1)] 写回合并后的版本继承自两个 sibling，所以冲突就此关闭。由谁来解决是一个产品决策： 购物车用集合并集，计数器用求和，文档可以选其一。存储没法知道，这就是 Riak 把 sibling 暴露出来并支持可插拔的解决器，而 Cassandra 默认用 LWW、用正确性换简单的原因。
Vector clock 会增长。 每个处理过这个 key 的 coordinator 都有一个条目，所以一个被 50 个 coordinator 写过的 key 会有 50 项的向量。两种缓解办法：截断（Dynamo 把向量限制在约 10 个条目，接受偶尔出现的假 sibling，它带来对账工作，但不会丢数据），或者使用服务端管理的 dotted version vector（Riak），防止客户端重试让时钟膨胀。
Warning
生产实践： 知道向量必须被管理，而不只是被使用，是 staff 级别的细节。“一个被每个节点都写过的 key，它的 vector clock 会怎样？“只有一个正确答案：带着可接受的假并发风险做截断，而不是无限增长。
从构造上合并：CRDT
与其发现冲突再合并，无冲突复制数据类型（CRDT） 的设计让每个操作都可交换：以任意顺序、在任意副本上应用这些操作，最终状态都相同。例子：
| CRDT | 如何合并 |
|---|---|
| 只增计数器 | 每个副本保存自己的计数；值是它们之和，合并时取每个副本的最大值 |
| 带添加和删除的集合 | 每个元素带唯一标签；删除只删除它见过的标签，所以并发的添加得以保留 |
| 序列（文本） | 每个插入的字符有唯一 id，并锚定在它的邻居上，所以并发的插入落在同样的稳定邻居之间；删除是针对原插入 id 的 tombstone |
协同编辑器要在**操作转换（OT）**和 CRDT 之间选择：OT 由中央服务器把每个传入的操作与并发的操作做转换（紧凑、久经考验，但需要全局顺序）；CRDT 去中心化，天然离线合并，但每个字符的元数据更多。离线编辑是决定性因素：OT 需要服务器对一个离开了几个小时的客户端做线性化，而 CRDT 在本地合并、无论顺序如何都能收敛。
Caution
常见错误： 因为 LWW 是默认值就用它，然后把丢失的写入描述成”最终一致性”。最终一致性承诺的是收敛，而不是没有任何人的写入被扔掉。如果丢写很要紧，就去发现它（vector clock），或者让数据类型从构造上就能合并（CRDT）。
如何选择
| 数据 | 做法 | 原因 |
|---|---|---|
| Session token、心跳、最后已知位置 | LWW | 最新的物理值正是你想要的 |
| 购物车、物品集合 | Vector clock 加并集合并 | 并发的添加必须都保留 |
| 计数器、点赞 | 计数器 CRDT，或在流里聚合 | 自增可交换 |
| 协同文本 | CRDT 或 OT | 对同一文档的并发编辑 |
| 金钱、库存、唯一性 | 不要用 leaderless 存储 | 需要一个单一的串行化点 |
相关
- 演练：设计分布式 KV 存储 — 在一个设计里同时用到 quorum、vector clock 和 hinted handoff。
- 演练：设计协同编辑器 — OT 与 CRDT 之争，离线编辑决定了合并策略。
- 参考：反熵与故障检测 — 错过了写入的副本如何重新收敛。