【分布式系统百科】无主复制：Dynamo 风格的读写 Quorum

本文是分布式系统百科系列 Part IV：复制 的第三篇。前两篇分别讨论了 主从复制 的同步/异步权衡和 多主复制 的冲突解决策略。主从复制有一个根本限制：Leader 是单点，挂了就得等故障转移。多主复制去掉了”单 Leader”的约束，但引入了冲突解决的深水区。本篇把 Leader 的数量从”多个”推到”零个”——看看完全去掉 Leader 之后，系统用什么机制保证你能读到正确的数据。

你的主从复制集群凌晨三点 Leader 挂了。自动故障转移需要 15 秒；这 15 秒内所有写请求全部失败。你的 SLA 承诺 99.99% 可用性——一年只允许 52 分钟停机，15 秒虽然不多，但如果每个月来一次，年底就超标了。

多主复制能缓解这个问题：每个数据中心有自己的 Leader，单个 Leader 挂了不影响其他数据中心。但多主复制的冲突解决极其复杂，上一篇已经详细讨论过。

有没有一种方案，既不依赖 Leader，又不需要处理复杂的冲突合并？

Amazon 在 2007 年给出了答案：去掉 Leader，让任何节点都能接受读写，用 Quorum（法定人数）机制保证读写的正确性。这就是 Dynamo 论文提出的无主复制（Leaderless Replication）模型。

一、为什么需要无主复制

1.1 Leader 的代价

回顾一下前两篇的核心结论：

无主复制的核心洞察：如果你不指定谁是 Leader，就不存在 Leader 故障的问题。每个节点地位平等，客户端可以向任意节点发送读写请求。只要有足够数量的节点确认操作，就认为操作成功。

1.2 Amazon Dynamo 论文

2007 年，Amazon 发表了 Dynamo: Amazon’s Highly Available Key-Value Store。这篇论文的背景是 Amazon 的购物车服务——购物车的可用性要求极高（用户加了商品到购物车，任何时候都不能丢），但对强一致性的要求相对宽松（短暂看到旧数据可以接受）。

Dynamo 论文的核心设计决策：

1. 去掉 Leader：任何节点都能处理读写请求。
2. Quorum 机制：用 R + W > N 公式保证读写集合有交集。
3. 最终一致性：允许短暂的不一致窗口，通过后台机制收敛。
4. Sloppy Quorum（宽松法定人数）：节点不可用时，临时借用其他节点，保证写入不被阻塞。
5. 向量时钟：检测并发写入冲突，交给应用层解决。

这篇论文影响深远——Cassandra、Riak、Voldemort 都直接借鉴了 Dynamo 的设计。Amazon 自己后来推出的 DynamoDB 服务在架构上已经和原始论文有很大差异，但 Quorum 的思想一脉相承。

1.3 无主复制的写入流程

在主从复制中，客户端把写请求发给 Leader，Leader 负责分发。在无主复制中，有两种常见模式：

模式一：客户端直接写多个副本。 客户端并行地把写请求发给所有持有该数据的副本节点，等待至少 W 个节点确认写入成功。Dynamo 论文描述的就是这种模式。

模式二：协调者（Coordinator）代理写入。 客户端把写请求发给一个协调者节点，由协调者转发给所有副本节点。协调者不是 Leader——它不决定写入顺序，只是一个代理。Cassandra 使用这种模式。

无论哪种模式，关键区别是：没有任何一个节点对写入有最终决定权。只要 W 个节点确认了，写入就算成功。

二、R + W > N：Quorum 公式的数学本质

2.1 基本定义

Quorum 机制的三个参数：

• N：数据的副本总数（每条数据存在多少个节点上）。
• W：写入法定人数（Write Quorum）——写入操作需要多少个节点确认才算成功。
• R：读取法定人数（Read Quorum）——读取操作需要从多少个节点获取数据才算成功。

核心公式：R + W > N。

这个公式的数学含义非常直观：如果你写入了 W 个节点，读取了 R 个节点，而 R + W > N，那么读取集合和写入集合必然有交集——至少有一个节点同时参与了最近的写入和当前的读取。这个节点持有最新的数据。

2.2 为什么交集保证正确性

用一个具体例子说明。假设 N=5，数据存储在节点 {A, B, C, D, E} 上。

写入阶段：客户端写入值 v2（版本 2），W=3，节点 {A, B, C} 确认写入成功。此时节点 D 和 E 还持有旧值 v1。

读取阶段：客户端读取，R=3，从节点 {C, D, E} 获取数据。读到的值：

客户端收到三个响应，其中节点 C 返回了最新值 v2。客户端选择版本号最高的值作为结果——这就是 Quorum 读取的核心逻辑。

R + W = 3 + 3 = 6 > 5 = N，所以交集至少有 6 - 5 = 1 个节点。在这个例子中，交集节点就是 C。

2.3 常见配置

不同的 N/W/R 配置适用于不同的工作负载：

读优化配置（N=3, W=3, R=1）：写入必须等待所有 3 个节点确认，写入延迟高且任一节点故障就会导致写入失败；但读取只需要访问 1 个节点，速度极快。适合读远多于写的缓存型场景。

写优化配置（N=3, W=1, R=3）：写入只需 1 个节点确认，速度极快；但读取需要访问全部 3 个节点。写入的持久性较弱——如果唯一确认的节点在数据复制到其他节点之前挂了，数据就丢了。

均衡配置（N=3, W=2, R=2）：这是最常用的配置。能容忍 1 个节点故障（写入还能成功：3-2=1 个节点可以挂；读取也能成功）。读写延迟都是”两个节点中较慢那个”的级别。

2.4 R + W ≤ N 时会怎样

如果 R + W ≤ N，读写集合可能没有交集。例如 N=3, W=1, R=1：

• 写入到节点 A。
• 读取从节点 B 获取——B 还是旧值。
• 客户端读到了过时的数据。

这不是”一定会读到旧数据”，而是”可能读到旧数据”。如果读取刚好命中了写入节点，仍然能读到最新值。但系统无法保证这一点。

在某些场景下，R + W ≤ N 是可以接受的——比如你只需要”尽力而为”的最终一致性，且对延迟极其敏感。DynamoDB 的 eventually consistent read 就是 R=1 的配置。

2.5 Quorum 容错能力

给定 N、W、R，系统能容忍多少节点故障？

• 写入容错：N - W 个节点可以不可用，写入仍然成功。
• 读取容错：N - R 个节点可以不可用，读取仍然成功。
• 同时容错：只要可用节点数 ≥ max(W, R)，系统就能同时处理读和写。

例如 N=5, W=3, R=3： - 写入容忍 2 个节点故障。 - 读取容忍 2 个节点故障。 - 系统在 3 个节点存活时仍然完全可用。

三、Quorum 的局限性：不等于线性一致

3.1 一个反直觉的事实

很多人看到 R + W > N 的公式后会误以为：只要满足这个条件，就能保证强一致性（线性一致性 / Linearizability）。

这是错的。

R + W > N 保证的是”读取集合和写入集合有交集”，但它不保证：

1. 客户端一定能拿到交集节点上的最新值（网络延迟可能导致读取在写入完全传播之前返回）。
2. 并发的读写操作之间有全序关系。
3. 读到最新值后不会再读到旧值。

3.2 反例：Quorum 读到过时数据的时间线

下面是一个具体的反例。N=3，W=2，R=2，节点为 {A, B, C}。

时间轴 →
t1: 客户端1 发起 write(x=1)
t2: 节点A 收到写入，本地写入 x=1，返回 ACK
t3: 节点B 收到写入，本地写入 x=1，返回 ACK
    → 客户端1 收到 2 个 ACK（W=2 满足），写入成功
t4: 客户端2 发起 read(x)
t5: 节点B 收到读取请求，返回 x=1（最新值）
t6: 节点C 收到读取请求，返回 x=0（旧值，写入还没传播到 C）
    → 客户端2 收到 2 个响应（R=2 满足）
    → 交集节点 B 返回了 x=1，客户端2 正确读到最新值 ✓

但是，考虑另一个时序：

t1: 客户端1 发起 write(x=1)
t2: 节点A 收到写入，本地写入 x=1，返回 ACK
t3: 客户端2 发起 read(x)（写入还在传播中）
t4: 节点B 收到读取请求，返回 x=0（写入尚未到达 B）
t5: 节点C 收到读取请求，返回 x=0（写入尚未到达 C）
    → 客户端2 收到 2 个响应，都是 x=0，读到了旧值 ✗
t6: 节点B 收到写入，本地写入 x=1，返回 ACK
    → 客户端1 收到 2 个 ACK（A 和 B），写入成功

在第二个时序中，客户端2 的读取在写入”正在进行”时发生。虽然写入最终成功了（满足 W=2），但读取在写入完成之前就返回了。从线性一致性的角度看，如果写入在读取之前完成，读取应该看到新值——但在这个例子中，写入和读取在时间上有重叠，Quorum 机制无法区分。

3.3 并发写入的 Last-Write-Wins 问题

当两个客户端同时对同一个键写入不同的值时，Quorum 系统面临一个根本问题：谁的写入算”最后”？

t1: 客户端1 write(x="foo")  → 到达节点 A, B
t1: 客户端2 write(x="bar")  → 到达节点 B, C

节点 B 同时收到两个写入，但因为网络延迟的微小差异，
在节点 B 上 "foo" 先到，在节点 C 上 "bar" 先到。

最终状态：
  节点 A: x="foo"
  节点 B: x="bar"（后到的覆盖了先到的）
  节点 C: x="bar"

不同节点对"最后一个写入"的判断不一致。

Cassandra 使用 LWW（Last-Write-Wins，最后写入胜出） 策略：每个写入携带一个客户端时间戳，时间戳大的覆盖时间戳小的。这在数学上保证了所有节点最终收敛到同一个值——但代价是静默丢弃了时间戳较小的写入，即使它可能包含有效的业务数据。

3.4 写入的部分失败

另一个棘手的场景：写入到达了 W 个节点中的一部分，但没有全部到达。

假设 N=3, W=2。客户端发起写入 x=1： - 节点 A 成功写入，返回 ACK。 - 节点 B 网络超时，没有返回 ACK。 - 节点 C 成功写入，返回 ACK。

客户端收到 2 个 ACK，写入成功。但节点 B 上的数据是旧的。如果后续读取命中了 B，需要 Read Repair 机制来修复——这是第五节的主题。

更糟糕的情况：节点 B 实际上收到了写入请求，也成功写入了，只是 ACK 在网络中丢失。此时数据实际上写了 3 个节点，但客户端认为只写了 2 个。这种情况不会导致正确性问题，但会触发不必要的 Read Repair。

还有一种情况：写入只到达了 1 个节点（不足 W=2），客户端判定写入失败。但那 1 个节点上已经有了新数据。后续的读取可能会读到这个”失败”的写入——这是一个很容易踩的坑。Dynamo 风格的系统不会回滚已经写入的数据，即使整体写入被判定为失败。

3.5 故障场景推演：副本失败时的读写行为

理解 Quorum 的容错能力，最好的方式是推演具体的故障场景。以下分析基于 N=3, W=2, R=2 的均衡配置，副本为 {A, B, C}。

场景一：写入期间 1 个副本故障

初始状态：A, B, C 均持有 key=X, value=v1, version=1

t1: 客户端发起 write(X=v2)
t2: 写入请求并行发给 A, B, C
t3: A 成功写入 X=v2, version=2, 返回 ACK
t4: B 宕机，请求超时，无 ACK
t5: C 成功写入 X=v2, version=2, 返回 ACK
t6: 客户端收到 2 个 ACK（A, C），满足 W=2，写入成功

结果：
  A: X=v2, version=2  (最新)
  B: X=v1, version=1  (宕机，数据过时)
  C: X=v2, version=2  (最新)

后续读取（B 仍宕机）：
  R=2 需要 2 个响应。A 和 C 都返回 v2 -> 读取成功，数据正确
  如果 B 恢复但未被修复：
    读取命中 A+B: A 返回 v2, B 返回 v1 -> 选择版本高的 v2 -> 正确
    Read Repair 将 v2 写回 B -> B 恢复一致

场景二：读取期间 1 个副本故障

初始状态：A 持有 v2（最新），B 持有 v2，C 持有 v1（过时）

t1: 客户端发起 read(X), R=2
t2: 读请求并行发给 A, B, C
t3: A 返回 X=v2, version=2
t4: B 宕机，请求超时
t5: C 返回 X=v1, version=1
t6: 客户端收到 2 个响应（A, C），满足 R=2
t7: 比较版本：v2 > v1，返回 v2（正确）
t8: Read Repair：将 v2 写回 C

结果：读取成功且正确。C 通过 Read Repair 得到修复。

场景三：写入期间 2 个副本故障（超过容错极限）

t1: 客户端发起 write(X=v3), W=2
t2: A 成功写入，返回 ACK
t3: B 宕机，超时
t4: C 宕机，超时
t5: 客户端只收到 1 个 ACK，不满足 W=2
t6: 客户端判定写入失败

注意：A 上已经写入了 v3！
后续 B 和 C 恢复后：
  read(X) 从 A+B 读取：A 返回 v3, B 返回 v1
  客户端可能读到"已失败"的写入 v3
  这是 Dynamo 风格系统的已知行为——不回滚部分写入

这三个场景揭示了 Quorum 容错的核心逻辑：在 N=3, W=2, R=2 的配置下，系统能容忍 1 个副本故障的读写操作；2 个副本同时故障则超过容错上限。 场景三还揭示了一个重要的工程陷阱：被判定为失败的写入可能已经在部分节点上生效，后续读取有可能读到这些”幽灵写入”。应用层需要对此有所准备。

3.6 收敛性保证的深入分析

Quorum 机制保证读取集合和写入集合有交集，但数据最终在所有副本上收敛到一致状态，依赖的是 Read Repair 和 Anti-Entropy 两个机制的协同工作。收敛性可以从以下三个方面理解：

时间维度的收敛：对于热数据（频繁读取），Read Repair 可以在毫秒级将过时副本修复。假设 R=2 且某个副本过时，每次读取命中该副本时都会触发 Read Repair。如果该 key 的读取 QPS 为 100，那么过时副本平均在 10ms 内就会被修复。冷数据则依赖 Anti-Entropy 的周期性修复——Cassandra 默认的修复周期建议为 gc_grace_seconds（默认 10 天）以内，超过此时间墓碑可能被清除而导致已删除数据”复活”。

版本冲突的收敛：当多个客户端并发写入同一个 key 时，LWW（Last-Write-Wins）策略通过时间戳的全序关系保证所有副本最终收敛到同一个值。收敛性的数学保证来自 LWW 合并函数的三个代数性质：交换律（A merge B = B merge A）、结合律（(A merge B) merge C = A merge (B merge C)）、幂等性（A merge A = A）。只要满足这三个性质，无论副本以什么顺序接收到写入，最终状态一定相同。

四、Sloppy Quorum 与 Hinted Handoff

4.1 标准 Quorum 的可用性困境

标准 Quorum 要求写入必须到达 W 个指定的副本节点（称为”Home 节点”）。如果 Home 节点中有太多不可用，写入就会失败。

例如 N=3, W=2，数据的 Home 节点是 {A, B, C}。如果 A 和 B 同时挂了，只剩 C 一个 Home 节点可用，写入失败——即使集群中还有 D、E、F 等健康节点。

对于 Amazon 购物车这样的场景，这是不可接受的：用户加商品到购物车的操作绝不能失败，哪怕代价是短暂的不一致。

4.2 Sloppy Quorum：借用非 Home 节点

Sloppy Quorum（宽松法定人数）的思路：如果 Home 节点不够，就借用其他节点来凑够 W 个。

继续上面的例子：A 和 B 挂了，标准 Quorum 需要在 {A, B, C} 中写入 2 个，但只有 C 可用。Sloppy Quorum 允许把写入发给 C 和 D（D 不是这条数据的 Home 节点，但临时帮忙）。

写入到 D 的数据会携带一个 Hint（提示）——标记”这条数据本来应该存在节点 A 上”。D 只是临时保管。

4.3 Hinted Handoff：数据回家

当节点 A 恢复后，D 检测到 A 已经上线，把带有 Hint 的数据推送给 A，然后删除本地的临时副本。这个过程叫 Hinted Handoff（提示移交）。

完整流程：

1. 正常状态：数据 K 的 Home 节点是 {A, B, C}
2. A 和 B 挂了
3. Sloppy Quorum：客户端写入 K=v2 到节点 C 和 D
   - C 上直接存储 K=v2（C 是 Home 节点）
   - D 上存储 K=v2 + hint="应属于 A"
4. A 恢复上线
5. D 检测到 A 恢复，推送 K=v2 给 A
6. D 删除本地的 K=v2
7. B 恢复上线后，通过 Anti-Entropy 或 Read Repair 获取 K=v2

4.4 Sloppy Quorum 的代价

Sloppy Quorum 提高了写入可用性，但进一步削弱了一致性保证。

关键问题：Sloppy Quorum 的 W 个节点中可能没有任何 Home 节点。假设 A、B、C 全部挂了（或者网络分区导致客户端无法访问它们），Sloppy Quorum 把数据写到了 D、E。此时如果另一个客户端能访问到节点 A（A 没挂，只是第一个客户端的网络分区），它用 R=2 从 A 和 B 读取——读到的全是旧值。

换句话说：Sloppy Quorum 的 R + W > N 公式中的 N 不再是固定的 Home 节点集合，而是包含了临时借用的节点。读和写可能使用了完全不同的 N，导致交集为空。

这就是为什么 Sloppy Quorum 只适用于对可用性要求极高、对一致性要求宽松的场景。Dynamo 论文把它作为购物车场景的核心设计；Riak 默认启用 Sloppy Quorum；Cassandra 同样支持但需要显式配置。

4.5 Riak 和 Dynamo 的实现细节

Riak 的 Sloppy Quorum 实现基于一致性哈希环（Consistent Hashing Ring）。每个键通过哈希映射到环上的一个位置，然后顺时针找到 N 个节点作为 Home 节点。如果某个 Home 节点不可用，就继续顺时针找到下一个可用节点作为临时替代。Riak 把这个临时节点称为 Fallback Node。Fallback Node 上的数据会定期检查 Home 节点是否恢复，一旦恢复就执行 Hinted Handoff。

Dynamo 论文中描述的实现更为激进：不仅仅是 Home 节点不可用时才使用 Sloppy Quorum，而是始终维护一个 Preference List（偏好列表）——包含 Home 节点和潜在的替代节点。写入时从 Preference List 的头部开始尝试，跳过不可用的节点。这意味着在正常情况下，写入也可能到达非 Home 节点（如果 Home 节点响应太慢）。

五、Read Repair 与 Anti-Entropy

Quorum 写入保证了至少 W 个节点有最新数据，但剩下的 N - W 个节点可能是过时的。如果不修复这些过时副本，随着时间推移，读取命中旧副本的概率会增加。两种机制负责修复过时副本：

5.1 Read Repair（读修复）

原理：客户端执行 Quorum 读取时，从 R 个节点获取数据。客户端比较这些数据的版本号，发现有些节点返回了旧版本，就把最新版本的数据写回到那些过时的节点。

客户端 read(key=K, R=2) 从节点 A 和 C 获取数据：
  节点 A 返回：K=v2, version=2
  节点 C 返回：K=v1, version=1

客户端发现 C 的版本落后。
客户端向 C 发送：write(K=v2, version=2)  // Read Repair
客户端返回 K=v2 给应用层。

优点： - 不需要额外的后台进程。 - 修复发生在正常读路径上，延迟可控。 - 热数据（频繁读取）的副本一致性收敛很快。

缺点： - 冷数据（很少读取）可能长期保持不一致。 - 增加了读取的延迟——需要额外的写回操作。 - 如果 R=1（读优化配置），只读一个节点，无法比较版本，Read Repair 不生效。

5.2 Anti-Entropy（反熵）

原理：后台进程定期比较不同副本之间的数据差异，发现不一致就修复。通常使用 Merkle Tree（默克尔树） 来高效地找出差异。

Merkle Tree 的工作方式：

假设节点 A 和节点 B 各存储了 1000 个键。

1. 每个节点对自己存储的所有键值对计算哈希，
   构建一棵二叉哈希树：
   - 叶子节点：每个键值对的哈希
   - 内部节点：子节点哈希的组合哈希
   - 根节点：整棵树的哈希

2. 节点 A 和 B 交换根节点哈希。
   - 如果相同：数据完全一致，无需进一步比较。
   - 如果不同：递归比较子树。

3. 最终定位到具体哪些键的值不一致，
   只传输这些键的数据来修复。

复杂度：O(log n) 次网络往返即可定位差异，
而不需要传输所有数据。

Cassandra 的 Anti-Entropy 实现：

Cassandra 使用 nodetool repair 命令触发 Anti-Entropy 修复。内部流程：

1. 协调者节点计算指定范围内数据的 Merkle Tree。
2. 向其他副本节点请求同一范围的 Merkle Tree。
3. 比较 Merkle Tree，找出差异键。
4. 从持有最新版本的节点拉取数据，推送到过时的节点。

# 对整个集群执行全量修复（谨慎使用，资源消耗大）
nodetool repair

# 只修复指定 keyspace
nodetool repair my_keyspace

# 增量修复（只修复上次修复之后变更的数据）
nodetool repair -inc my_keyspace

# 查看修复进度
nodetool repair_admin list

# 检查节点间数据一致性状态
nodetool describecluster

性能考量：

• 全量修复（Full Repair）会遍历所有数据构建 Merkle Tree，在大数据集上可能耗时数小时，且消耗大量 CPU、磁盘 I/O 和网络带宽。生产环境中通常在低峰期执行。
• 增量修复（Incremental Repair）只处理上次修复后的变更数据，开销小很多，但需要正确维护”已修复/未修复”的 SSTable 标记。
• Cassandra 4.0 引入了 Transient Replication（瞬态复制），进一步优化了修复的数据传输量。

5.3 两种机制的对比

最佳实践是两者结合使用：Read Repair 保证热数据的快速收敛，Anti-Entropy 周期性修复冷数据。

5.4 副本修复时间线

下面的时序图展示了一个副本故障后，Read Repair 和 Anti-Entropy 如何协同工作将数据恢复一致：

sequenceDiagram
    participant C as 客户端
    participant A as 副本A(最新)
    participant B as 副本B(过时)
    participant AE as Anti-Entropy<br/>后台进程

    Note over A,B: 初始: A=v2, B=v1(B曾宕机错过写入)

    rect rgb(232, 245, 233)
        Note over C,B: Read Repair 修复热数据
        C->>A: read(key1), R=2
        C->>B: read(key1), R=2
        A-->>C: v2, version=2
        B-->>C: v1, version=1
        Note over C: 选择 version 最高: v2
        C->>B: write(key1=v2, version=2)
        Note over B: key1 已修复
    end

    rect rgb(227, 242, 253)
        Note over AE,B: Anti-Entropy 修复冷数据
        AE->>A: 请求 Merkle Tree
        AE->>B: 请求 Merkle Tree
        A-->>AE: hash(subtree)
        B-->>AE: hash(subtree)
        Note over AE: 比较发现 key99 不一致
        AE->>A: 获取 key99 最新值
        A-->>AE: key99=v5, version=5
        AE->>B: 写入 key99=v5
        Note over B: key99 已修复(冷数据)
    end

该时序图展示了两种修复机制的互补关系：Read Repair 在正常读取路径上”搭便车”修复被访问到的过时数据（绿色区域），延迟极低但只覆盖热数据；Anti-Entropy 通过后台 Merkle Tree 比较系统性地扫描所有数据差异（蓝色区域），能修复长期未被访问的冷数据，但资源消耗较大。生产环境中应同时启用两种机制，并根据数据访问模式调整 Anti-Entropy 的执行频率。

六、Cassandra 实现深度拆解

Cassandra 是目前最广泛使用的 Dynamo 风格数据库，也是无主复制工程实现的标杆。

6.1 一致性哈希与虚拟节点

Cassandra 使用一致性哈希（Consistent Hashing）来决定数据存储在哪些节点上。

基本一致性哈希：把哈希空间组织成一个环（0 到 2^63-1），每个节点在环上占据一个位置。键通过 Murmur3 哈希映射到环上，然后顺时针找到 N 个节点作为副本。

虚拟节点（Virtual Node / vnode）：每个物理节点在环上占据多个位置（默认 256 个 Token）。这样做的好处：

1. 负载均衡：避免因节点数量少导致的哈希空间分配不均。
2. 节点增减时数据迁移更平滑：新节点加入时，从多个现有节点各迁移一小部分数据，而不是从一个节点迁移一大块。
3. 异构硬件支持：性能更强的节点可以分配更多 Token。

物理节点 3 个，每个 4 个 vnode：

哈希环：
  0 ─── A1 ─── B1 ─── C1 ─── A2 ─── B2 ─── C2 ─── A3 ─── B3 ─── C3 ─── A4 ─── B4 ─── C4 ─── 2^63

键 K 的哈希值落在 B1 和 C1 之间 → 顺时针第一个 vnode 是 C1 → 
C1 属于物理节点 C → 数据的第一个副本存在节点 C 上。
继续顺时针：A2（节点 A）、B2（节点 B）→ N=3 时副本存在 {C, A, B}。

6.2 协调者节点模式

客户端发送请求到 Cassandra 集群中的任意节点，该节点自动成为本次请求的协调者（Coordinator）。协调者的职责：

1. 根据键的哈希值和复制策略，确定 N 个副本节点。
2. 将读/写请求转发给这 N 个副本节点。
3. 等待 R 或 W 个节点响应。
4. 整合响应，返回给客户端。

协调者不是固定的——任何节点都可以充当协调者。这消除了单点瓶颈。客户端驱动（如 DataStax Java Driver）通常使用 Token-Aware 策略：直接把请求发给数据的某个副本节点，让它充当协调者，避免一次额外的网络跳转。

6.3 ConsistencyLevel 配置

Cassandra 通过 ConsistencyLevel 参数让应用在每次读写时灵活选择一致性级别。以下是常用的 ConsistencyLevel：

注意：QUORUM 写入 + QUORUM 读取满足 R + W > N，可以保证读到最新值（在没有并发写入的情况下）。ALL 写入 + ONE 读取也满足，但 ALL 的可用性很差。

6.4 CQL 实战

-- 创建 Keyspace，使用 NetworkTopologyStrategy，3 个数据中心各 3 副本
CREATE KEYSPACE shopping WITH replication = {
  'class': 'NetworkTopologyStrategy',
  'dc-beijing': 3,
  'dc-frankfurt': 3,
  'dc-virginia': 3
};

USE shopping;

-- 创建表
CREATE TABLE cart_items (
  user_id UUID,
  item_id UUID,
  quantity INT,
  added_at TIMESTAMP,
  PRIMARY KEY (user_id, item_id)
);

-- 写入：使用 LOCAL_QUORUM，保证本地数据中心多数确认
CONSISTENCY LOCAL_QUORUM;
INSERT INTO cart_items (user_id, item_id, quantity, added_at)
VALUES (
  550e8400-e29b-41d4-a716-446655440000,
  6fa459ea-ee8a-3ca4-894e-db77e160355e,
  2,
  toTimestamp(now())
);

-- 读取：使用 LOCAL_QUORUM
SELECT * FROM cart_items
WHERE user_id = 550e8400-e29b-41d4-a716-446655440000;

-- 弱一致性写入：使用 ANY，即使所有副本都挂了也能写入（Hinted Handoff）
CONSISTENCY ANY;
INSERT INTO cart_items (user_id, item_id, quantity, added_at)
VALUES (
  550e8400-e29b-41d4-a716-446655440000,
  7c9e6679-7425-40de-944b-e07fc1f90ae7,
  1,
  toTimestamp(now())
);

-- 强一致性读取：使用 ALL（需要所有副本响应，延迟高）
CONSISTENCY ALL;
SELECT * FROM cart_items
WHERE user_id = 550e8400-e29b-41d4-a716-446655440000;

6.5 轻量级事务（LWT）

标准 Quorum 不提供线性一致性。但有些场景需要——比如唯一性约束（用户名注册）。Cassandra 提供了 LWT（Lightweight Transaction，轻量级事务），基于 Paxos 协议实现线性一致性操作。

-- 只在用户名不存在时插入（Compare-And-Set）
INSERT INTO users (username, email, created_at)
VALUES ('alice', 'alice@example.com', toTimestamp(now()))
IF NOT EXISTS;

-- 条件更新：只在当前值符合预期时更新
UPDATE users
SET email = 'alice_new@example.com'
WHERE username = 'alice'
IF email = 'alice@example.com';

LWT 的代价：

1. 延迟高：LWT 需要 4 轮网络往返（Prepare → Promise → Propose → Accept），而普通写入只需 1 轮。
2. 吞吐低：同一个 Partition Key 上的 LWT 操作是串行化的。
3. 不适合高频写入：Cassandra 官方建议 LWT 的使用比例不超过总写入量的 2-5%。

LWT 本质上是在无主复制的基础上叠加了 Paxos 共识——把原本不保证线性一致性的系统，在需要的时候”升级”到线性一致。这是一种务实的折中。

6.6 集群健康监控

# 查看集群节点状态
nodetool status

# 输出示例：
# Datacenter: dc-beijing
# ===============
# Status=Up/Down
# |/ State=Normal/Leaving/Joining/Moving
# --  Address       Load       Tokens  Owns   Host ID
# UN  10.0.1.1      256.12 GiB 256     33.3%  a1b2c3d4-...
# UN  10.0.1.2      248.67 GiB 256     33.3%  e5f6g7h8-...
# DN  10.0.1.3      251.34 GiB 256     33.3%  i9j0k1l2-...

# 查看某个节点的详细信息
nodetool info

# 查看各节点的数据分布
nodetool ring

# 查看读写延迟统计
nodetool tablehistograms shopping.cart_items

# 查看 Gossip 协议状态（节点间通信）
nodetool gossipinfo

# 查看 pending 的 Hinted Handoff 数据量
nodetool tpstats | grep -i hint

# 查看 Compaction 状态
nodetool compactionstats

七、DynamoDB 实现

Amazon DynamoDB 是一个完全托管的 NoSQL 数据库服务。虽然它的名字来源于 Dynamo 论文，但现代 DynamoDB 的架构已经和原始论文有很大差异。

7.1 和 Dynamo 论文的差异

DynamoDB 最大的简化是：用户不需要关心 N、W、R 的具体数值。DynamoDB 内部使用多副本复制（通常 3 副本，跨可用区），但这些细节对用户完全透明。

7.2 分区级复制

DynamoDB 的每个表按 Partition Key 自动分区。每个分区有多个副本分布在不同的可用区（Availability Zone）中。

表: Orders
分区键: order_id

分区 P1 (order_id 范围: 0-1000)
  ├── 副本 AZ-1a（Leader）
  ├── 副本 AZ-1b
  └── 副本 AZ-1c

分区 P2 (order_id 范围: 1001-2000)
  ├── 副本 AZ-1b（Leader）
  ├── 副本 AZ-1c
  └── 副本 AZ-1a

注意：DynamoDB 的分区内部实际上使用了主从复制，而不是完全的无主复制。每个分区有一个 Leader 副本处理写入，其他副本异步复制。但在分区级别之上，DynamoDB 的行为和无主复制类似——没有全局 Leader，每个分区独立。

7.3 强一致读 vs 最终一致读

DynamoDB 提供两种读取模式：

最终一致读（Eventually Consistent Read）：从任意副本读取，可能读到旧数据。延迟低，吞吐高，费用低（读容量单位消耗减半）。

强一致读（Strongly Consistent Read）：从 Leader 副本读取，保证读到最新写入的数据。延迟略高，消耗更多读容量单位。

import boto3
from boto3.dynamodb.conditions import Key

dynamodb = boto3.resource('dynamodb', region_name='us-east-1')
table = dynamodb.Table('Orders')

# 最终一致读（默认）
response = table.get_item(
    Key={'order_id': '12345'},
    ConsistentRead=False  # 默认值，可省略
)
item = response.get('Item')
print(f"最终一致读: {item}")

# 强一致读
response = table.get_item(
    Key={'order_id': '12345'},
    ConsistentRead=True  # 强一致读
)
item = response.get('Item')
print(f"强一致读: {item}")

# 查询（Query）也支持强一致读
response = table.query(
    KeyConditionExpression=Key('user_id').eq('user-001'),
    ConsistentRead=True
)
items = response.get('Items', [])
print(f"强一致查询结果: {len(items)} 条")

7.4 条件写入作为并发原语

DynamoDB 不使用向量时钟来处理并发冲突。它提供了 条件写入（Conditional Write） 作为并发控制原语——只有当条件满足时，写入才会执行。

from botocore.exceptions import ClientError

# 乐观锁模式：使用 version 字段做 Compare-And-Swap
try:
    table.update_item(
        Key={'order_id': '12345'},
        UpdateExpression='SET quantity = :new_qty, version = :new_ver',
        ConditionExpression='version = :current_ver',
        ExpressionAttributeValues={
            ':new_qty': 5,
            ':new_ver': 3,
            ':current_ver': 2  # 期望当前版本是 2
        }
    )
    print("更新成功")
except ClientError as e:
    if e.response['Error']['Code'] == 'ConditionalCheckFailedException':
        print("版本冲突，需要重试")
    else:
        raise

# 创建（仅当不存在时）
try:
    table.put_item(
        Item={
            'order_id': '99999',
            'user_id': 'user-001',
            'status': 'pending',
            'version': 1
        },
        ConditionExpression='attribute_not_exists(order_id)'
    )
    print("创建成功")
except ClientError as e:
    if e.response['Error']['Code'] == 'ConditionalCheckFailedException':
        print("记录已存在")
    else:
        raise

条件写入的优势： - 语义清晰——应用层显式指定冲突检测条件。 - 不需要向量时钟的合并逻辑。 - 原子性由 DynamoDB 保证。

代价： - 需要应用层自行实现重试逻辑。 - 高竞争场景下重试率可能很高。

7.5 DynamoDB 全局表

DynamoDB Global Tables 提供多区域复制，类似于多主复制。每个区域都有一份完整的数据副本，支持本地读写。冲突解决使用 LWW（基于时间戳）。

# Global Tables 的使用对应用层完全透明
# 在任何区域都可以正常读写

# 东京区域
dynamodb_tokyo = boto3.resource('dynamodb', region_name='ap-northeast-1')
table_tokyo = dynamodb_tokyo.Table('GlobalOrders')

table_tokyo.put_item(Item={
    'order_id': 'tokyo-001',
    'region': 'ap-northeast-1',
    'status': 'created'
})

# 弗吉尼亚区域（最终会收到东京的写入）
dynamodb_virginia = boto3.resource('dynamodb', region_name='us-east-1')
table_virginia = dynamodb_virginia.Table('GlobalOrders')

# 最终一致读可能暂时读不到东京刚写入的数据
response = table_virginia.get_item(
    Key={'order_id': 'tokyo-001'},
    ConsistentRead=False
)

八、Quorum 模拟：用代码理解读写流程

下面用 Go 实现一个简化的 Quorum 读写模拟，帮助理解核心机制：

package main

import (
    "fmt"
    "sync"
    "time"
)

// Replica 模拟一个副本节点
type Replica struct {
    mu      sync.Mutex
    id      string
    data    map[string]VersionedValue
    alive   bool
}

type VersionedValue struct {
    Value   string
    Version int64
}

func NewReplica(id string) *Replica {
    return &Replica{
        id:    id,
        data:  make(map[string]VersionedValue),
        alive: true,
    }
}

func (r *Replica) Write(key, value string, version int64) error {
    r.mu.Lock()
    defer r.mu.Unlock()
    if !r.alive {
        return fmt.Errorf("node %s is down", r.id)
    }
    current, exists := r.data[key]
    if !exists || version > current.Version {
        r.data[key] = VersionedValue{Value: value, Version: version}
    }
    return nil
}

func (r *Replica) Read(key string) (VersionedValue, error) {
    r.mu.Lock()
    defer r.mu.Unlock()
    if !r.alive {
        return VersionedValue{}, fmt.Errorf("node %s is down", r.id)
    }
    v, ok := r.data[key]
    if !ok {
        return VersionedValue{}, fmt.Errorf("key %s not found on %s", key, r.id)
    }
    return v, nil
}

// QuorumCluster 模拟一个 Quorum 集群
type QuorumCluster struct {
    replicas []*Replica
    n, w, r  int
}

func NewQuorumCluster(n, w, r int) *QuorumCluster {
    replicas := make([]*Replica, n)
    for i := 0; i < n; i++ {
        replicas[i] = NewReplica(fmt.Sprintf("Node-%d", i))
    }
    return &QuorumCluster{replicas: replicas, n: n, w: w, r: r}
}

func (qc *QuorumCluster) QuorumWrite(key, value string) error {
    version := time.Now().UnixNano()
    acks := 0
    var mu sync.Mutex
    var wg sync.WaitGroup

    for _, rep := range qc.replicas {
        wg.Add(1)
        go func(r *Replica) {
            defer wg.Done()
            if err := r.Write(key, value, version); err == nil {
                mu.Lock()
                acks++
                mu.Unlock()
            }
        }(rep)
    }
    wg.Wait()

    if acks < qc.w {
        return fmt.Errorf("write failed: got %d ACKs, need %d", acks, qc.w)
    }
    fmt.Printf("[WRITE] key=%s value=%s version=%d acks=%d/%d\n",
        key, value, version, acks, qc.n)
    return nil
}

func (qc *QuorumCluster) QuorumRead(key string) (string, error) {
    type result struct {
        val VersionedValue
        rep *Replica
        err error
    }
    results := make([]result, 0, qc.n)
    var mu sync.Mutex
    var wg sync.WaitGroup

    for _, rep := range qc.replicas {
        wg.Add(1)
        go func(r *Replica) {
            defer wg.Done()
            v, err := r.Read(key)
            mu.Lock()
            results = append(results, result{val: v, rep: r, err: err})
            mu.Unlock()
        }(rep)
    }
    wg.Wait()

    // 收集成功响应
    var successes []result
    for _, res := range results {
        if res.err == nil {
            successes = append(successes, res)
        }
    }
    if len(successes) < qc.r {
        return "", fmt.Errorf("read failed: got %d responses, need %d",
            len(successes), qc.r)
    }

    // 选择版本号最高的值
    best := successes[0]
    for _, s := range successes[1:] {
        if s.val.Version > best.val.Version {
            best = s
        }
    }

    // Read Repair：把最新值写回过时的节点
    for _, s := range successes {
        if s.val.Version < best.val.Version {
            fmt.Printf("[READ REPAIR] %s: version %d → %d\n",
                s.rep.id, s.val.Version, best.val.Version)
            s.rep.Write(key, best.val.Value, best.val.Version)
        }
    }

    fmt.Printf("[READ] key=%s value=%s version=%d from %d nodes\n",
        key, best.val.Value, best.val.Version, len(successes))
    return best.val.Value, nil
}

func main() {
    // N=5, W=3, R=3
    cluster := NewQuorumCluster(5, 3, 3)

    // 写入
    if err := cluster.QuorumWrite("user:1001", "Alice"); err != nil {
        fmt.Printf("Error: %v\n", err)
        return
    }

    // 模拟一个节点宕机
    cluster.replicas[4].mu.Lock()
    cluster.replicas[4].alive = false
    cluster.replicas[4].mu.Unlock()
    fmt.Println("[EVENT] Node-4 is down")

    // 写入新值（4 个节点可用，W=3 仍然满足）
    if err := cluster.QuorumWrite("user:1001", "Alice-v2"); err != nil {
        fmt.Printf("Error: %v\n", err)
        return
    }

    // 读取（4 个节点可用，R=3 仍然满足）
    val, err := cluster.QuorumRead("user:1001")
    if err != nil {
        fmt.Printf("Error: %v\n", err)
        return
    }
    fmt.Printf("[RESULT] user:1001 = %s\n", val)
}

运行输出示例：

[WRITE] key=user:1001 value=Alice version=1713000000000 acks=5/5
[EVENT] Node-4 is down
[WRITE] key=user:1001 value=Alice-v2 version=1713000001000 acks=4/5
[READ REPAIR] Node-3: version 1713000000000 → 1713000001000
[READ] key=user:1001 value=Alice-v2 version=1713000001000 from 4 nodes
[RESULT] user:1001 = Alice-v2

这个模拟展示了几个关键行为：

1. 节点宕机后，只要可用节点数 ≥ max(W, R)，读写仍然正常。
2. 宕机节点上保留旧数据，其他节点已经更新。
3. Read Repair 在读取时自动修复过时的节点。

九、工程考量

9.1 监控 Quorum 健康

Quorum 系统的健康取决于可用节点数量。以下指标需要持续监控：

1. 存活节点数 vs N：如果存活节点数 < W 或 < R，系统将无法处理写入或读取。
2. 读写延迟 P99：Quorum 读写的延迟由第 R/W 快的节点决定。如果某个节点变慢（磁盘 I/O 高、GC 停顿），整体延迟会升高。
3. Hinted Handoff 队列深度：大量 Hint 堆积说明有节点长时间不可用，且 Hint 存储节点的磁盘可能撑不住。
4. Read Repair 频率：过高的 Read Repair 频率说明副本一致性差，可能需要增加 Anti-Entropy 修复的频率。

# Cassandra 监控示例

# 查看各表的读写延迟（P50 / P99 / P999）
nodetool tablestats shopping.cart_items

# 查看挂起的 Hint 数量
nodetool tpstats | grep HintedHandoff

# 查看不可用节点
nodetool status | grep "^DN"

# 查看 Read Repair 统计
nodetool tablestats shopping.cart_items | grep -i repair

# Prometheus + Grafana 监控（推荐）
# Cassandra 通过 JMX 暴露指标，可用 jmx_exporter 采集
# 关键指标：
#   - org.apache.cassandra.metrics.ClientRequest.Latency.Read
#   - org.apache.cassandra.metrics.ClientRequest.Latency.Write
#   - org.apache.cassandra.metrics.Storage.TotalHints
#   - org.apache.cassandra.metrics.ThreadPools.PendingTasks.ReadRepairStage

9.2 节点故障与替换

短期故障（节点重启、短暂网络中断）：

• Hinted Handoff 覆盖短期故障期间的写入。
• 节点恢复后自动接收 Hint 数据。
• 通常不需要人工干预。

长期故障（磁盘损坏、硬件故障、需要替换节点）：

1. 标记节点为”已退役”（nodetool decommission 或 nodetool removenode）。
2. 加入新节点（nodetool bootstrap）。
3. 执行全量修复（nodetool repair），确保新节点的数据完整。

关键注意事项：Hinted Handoff 有保留时间限制（Cassandra 默认 3 小时）。如果节点宕机超过 3 小时，Hint 会被丢弃，必须通过 Anti-Entropy 修复来恢复数据一致性。

9.3 R 和 W 的调优策略

没有”最佳”的 R/W 配置——取决于你的工作负载和一致性需求。

决策框架：

问：你能容忍读到旧数据吗？
├── 不能 → R + W > N，推荐 QUORUM/QUORUM
│   问：你能容忍偶尔的写入失败吗？
│   ├── 不能 → 考虑降低 W，提高 R
│   └── 能 → W = ⌊N/2⌋+1, R = ⌊N/2⌋+1
└── 能 → R=1, W=1 或其他宽松配置
    问：你更关心读延迟还是写延迟？
    ├── 读延迟 → R=1, W 尽量大
    └── 写延迟 → W=1, R 尽量大

实践建议：

1. 默认从 QUORUM/QUORUM 开始。这是最安全的配置。
2. 读多写少的场景：考虑 W=ALL, R=ONE。但要注意 W=ALL 时任一节点故障就会阻塞写入。
3. 写多读少的场景：考虑 W=ONE, R=ALL。写入延迟低但持久性弱。
4. 跨数据中心场景：使用 LOCAL_QUORUM 避免跨数据中心的延迟。
5. 混合配置：对同一张表的不同操作使用不同的 ConsistencyLevel。比如购物车的”添加商品”用 LOCAL_QUORUM，“结账前查询”用 ALL。

9.4 无主复制适合什么场景

适合的场景：

• 高可用要求、可以容忍短暂不一致的读密集型工作负载（用户画像、推荐数据、时序数据）。
• 多数据中心部署、需要低延迟本地读写。
• 键值存储、宽列存储等简单数据模型。
• 写入吞吐要求高、数据可以按键分区。

不适合的场景：

• 需要强一致性（线性一致）的业务逻辑（账户余额、库存扣减）——用 Raft/Paxos。
• 复杂事务（跨行/跨表事务）——用 Spanner/CockroachDB。
• 数据量不大但一致性要求高——用主从复制即可。
• 需要复杂查询（JOIN、聚合、子查询）——用关系数据库。

一句话总结：无主复制在”可用性 vs 一致性”的频谱上，站在可用性这一端。它不是万能的，但在它擅长的场景下，能提供其他复制模型难以匹敌的可用性和水平扩展能力。

十、总结

本文从 Amazon Dynamo 论文出发，系统地拆解了无主复制的核心机制：

1. R + W > N 是 Quorum 正确性的数学基础——保证读写集合有交集。
2. Quorum ≠ 线性一致——并发读写的时序交错可以导致读到旧值。
3. Sloppy Quorum 用可用性换一致性——节点不够就借用临时节点。
4. Read Repair + Anti-Entropy 是副本收敛的两条腿——一个修热数据，一个修冷数据。
5. Cassandra 和 DynamoDB 在工程实现上做了不同的权衡——Cassandra 给你完全的旋钮控制，DynamoDB 替你做了大部分决策。

下一篇我们讨论一种更特别的复制策略——链式复制（Chain Replication）。它把副本节点排成一条链，写入从头节点进入、读取从尾节点返回，用拓扑结构本身来保证强一致性。

参考资料

1. DeCandia, G., et al. “Dynamo: Amazon’s Highly Available Key-Value Store.” SOSP 2007.
2. Lakshman, A., Malik, P. “Cassandra: A Decentralized Structured Storage System.” LADIS 2009.
3. Kleppmann, M. Designing Data-Intensive Applications, Chapter 5: Replication. O’Reilly, 2017.
4. Apache Cassandra Documentation: Consistency Level.
5. Amazon DynamoDB Developer Guide: Read Consistency.
6. Vogels, W. “Eventually Consistent.” Communications of the ACM, 52(1), 2009.
7. Terry, D. “Replicated Data Consistency Explained Through Baseball.” Microsoft Research Technical Report, 2011.

Prev: 多主复制 | Next: 链式复制