分布式算法 #06：Quorum 与 NWR 模型

NWR 模型是分布式存储系统（Dynamo、Cassandra、Riak）中调节一致性与可用性的核心机制。本文深入分析 Read Repair、Hinted Handoff、Sloppy Quorum 的算法细节，并给出 W+R≤N 导致脏读的数学证明和异常场景的完整分析。

相关文章：Paxos 算法 · Raft 共识算法 · CRDT（无冲突复制数据类型） · Merkle Tree 与反熵同步

目录

NWR 模型基础

N = 总副本数（Replication Factor）
W = 写入成功所需的最小副本数（Write Quorum）
R = 读取所需的最小副本数（Read Quorum）

Quorum 条件：W + R > N

直觉：写入了 W 个副本，读取了 R 个副本
     W+R>N 保证至少有 1 个副本同时参与了写入和读取
     → 读取一定能看到最新写入（至少有 1 个重叠）

典型配置：

强 Quorum 与 Sloppy Quorum

强 Quorum（Strict Quorum）

写入操作：
  coordinator 向所有 N 个副本发送写请求
  等待至少 W 个副本确认
  如果 W 个确认 < 超时阈值：写入成功
  否则：返回写入失败

读取操作：
  coordinator 向所有 N 个副本发送读请求
  等待至少 R 个副本响应
  从 R 个响应中选择最新版本（版本号/时间戳最大）
  返回最新值

节点宕机时（强 Quorum）：
  如果宕机节点数 > N-W：写入失败（无法满足 W）
  如果宕机节点数 > N-R：读取失败（无法满足 R）
  → 可用性较低，优先保证一致性（CP 倾向）

Sloppy Quorum（宽松 Quorum）

Dynamo / Cassandra 的做法：可用性优先，分区时继续写入，但可能返回旧数据。

场景：N=3，W=2，正常副本集 {A,B,C}，A 宕机

Sloppy Quorum 写入：
  协调者发现 A 不可用
  从集群中选一个临时节点 D（不在正常副本集中）
  写入 B、D（完成 W=2 的写入）
  D 保存一个 hint：{targetNode: A, data: {...}}
  → 写入成功，但 A 没有最新数据

A 恢复后（Hinted Handoff）：
  D 将 hint 中的数据推送给 A
  A 更新数据
  D 删除 hint

Sloppy Quorum 的代价：
  写入 B、D 期间，读取 A、C（原副本集）可能读到旧数据
  因为 D 不在正常读取路径上，A 未更新

Read Repair

读取操作检测到多个副本数据不一致时，主动修复。

协调者向 R 个副本发送读请求，收到响应：
  副本A: value="v2", version=2
  副本B: value="v1", version=1  ← 落后
  副本C: value="v2", version=2

处理步骤：
  1. 选取最新版本（version=2, value="v2"）返回给客户端
  2. 异步/同步修复落后的副本：
     发送 write(value="v2", version=2) 给副本B

两种 Read Repair 模式：

  同步 Read Repair（Strong Read Repair）：
    在返回给客户端之前修复所有落后副本
    延迟增加，但后续一致性好
    适合：强一致场景

  异步 Read Repair（Background Repair）：
    先返回给客户端，后台异步修复
    延迟低，但修复前窗口内仍可能读到旧数据
    Cassandra 默认行为

Read Repair 的盲区：
  如果 key 从未被读取 → 过期副本永远不会被修复
  解决：Anti-entropy Repair（后台定期 Merkle Tree 比对，见笔记07）

Hinted Handoff

目标：在目标副本暂时不可用时，确保写入不丢失

写入流程（含 Hinted Handoff）：
  coordinator 发送写请求给副本 {A, B, C}
  A 不可达（超时）

  coordinator 发现 A 不可达：
    选取临时节点 D（preference list 中 A 的后继节点）
    发送 write to D，携带 hint metadata：
    {
      hint_for: A,      // 真正的目标副本
      data: {...},
      written_at: T
    }

  D 本地存储 hint（通常存在专用 hints 目录）：
    确认写入 coordinator（计入 W 的计数）

A 恢复后：
  D 检测到 A 可达（通过 Gossip 或主动探测）
  D 向 A 发送 hint 中的数据
  A 更新本地数据
  A 确认后，D 删除 hint 文件

异常处理：
  D 在 A 恢复前也宕机：
    hint 数据丢失！
    需要 Anti-entropy Repair（Merkle Tree 比对）来修复

  hint 积压太多（目标节点长时间宕机）：
    hint 文件占用 D 大量磁盘空间
    Cassandra 配置 max_hint_window：超过时间窗口的 hint 被丢弃
    → 长时间宕机的节点恢复后，需要手动触发 Full Repair

  hint 在传输中重复：
    目标节点已有最新数据（版本号更高）→ 忽略旧 hint ✅（幂等）

W+R≤N 脏读证明

定理：当 W+R≤N 时，存在读操作返回旧值的可能。

反例构造（N=3, W=1, R=1）：

初始：副本 {A,B,C} 都有 key=X, value="old", version=1

写入操作：coordinator1 写入 value="new", version=2
  W=1：只需 1 个副本确认
  仅写入副本 A：A.value="new", A.version=2
  B、C 未更新：B.value="old", C.value="old"

读取操作（写入后立即读）：coordinator2 读取
  R=1：只需 1 个副本响应
  coordinator2 选择副本 B（负载均衡/就近路由）
  B 返回 value="old", version=1  ← 脏读！

数学验证：
  W+R = 1+1 = 2 ≤ N=3
  写入副本集 {A}，读取副本集 {B}，交集 = ∅
  → 读取不保证看到最新写入

对比（W=2, R=2, W+R=4>N=3）：
  写入 {A,B}，读取任意 2 个副本：
  可能的读副本集：{A,B}、{A,C}、{B,C}
  无论哪种组合，都至少包含 A 或 B（写入副本）
  → 一定能读到最新写入 ✅

严格证明：

设写入副本集 W_set（|W_set|=W），读取副本集 R_set（|R_set|=R）

|W_set| + |R_set| = W + R > N = |全集|
由鸽巢原理：W_set ∩ R_set ≠ ∅
→ 至少有 1 个副本同时在写入集和读取集中
→ 该副本一定有最新写入（如果写入已持久化）
→ 读取结果中包含最新版本

异常场景分析

异常 1：写入 W 个副本后协调节点宕机

场景：W=2, N=3
  写入了 {A,B}，协调节点在通知 C 之前宕机

后续读取：
  读取 {A,C}：A 有新数据，C 没有
    选取 A 的版本（version 比较）
    Read Repair 修复 C → 最终一致 ✅

  读取 {B,C}：B 有新数据，C 没有
    选取 B 的版本，Read Repair 修复 C ✅

  读取 {A,B}：两者都有新数据，一致 ✅

问题：如果 A 和 B 都宕机，读取只能 {C}（R=1 时）
    C 没有新数据 → 读到旧值（但写入已成功确认）
    这是 NWR 模型的设计取舍，非 bug

异常 2：网络分区导致两半各自写入

场景：N=5, W=3, R=3
  分区1：{A, B, C}（3个节点）
  分区2：{D, E}（2个节点）

分区1 写入：
  向 {A,B,C} 写入 → W=3 满足 → 写入成功

分区2 写入：
  向 {D,E} 写入 → 只有 2 < W=3 → 写入失败 ✅（拒绝写入，避免脑裂）

分区恢复后：无冲突，因为分区2 无法完成写入

对比 Sloppy Quorum（W=2）：
  分区2 写入 {D,E}（用 hint 替代 A/B/C）→ 可能产生冲突
  恢复后需要向量时钟合并

异常 3：写入超时后客户端重试

场景：
  客户端写入 key=X, value="new"
  已写入副本 A，副本 B 写入超时
  客户端判定写入失败，重试

重试写入：
  写入副本 {A, B}（成功）

问题：
  副本 A 此时有两个版本：
    第一次写入：version=1（时间戳 T1）
    重试写入：version=1（同一内容，时间戳 T2>T1）

  如果用时间戳去重：T2 > T1 → 正常更新 ✅
  如果写入的是不同值（网络错误导致数据变化）：需要幂等写入机制

推荐：写入请求带唯一 request_id，服务端去重
  if request_id 已处理: 返回之前的结果（幂等）
  else: 执行写入，记录 request_id

版本冲突处理

读取多个副本时，可能获得多个不同版本：

版本比较规则（使用向量时钟）：
  v1 < v2（v2 因果上更新）→ 返回 v2，异步修复持有 v1 的副本
  v1 || v2（并发，真正冲突）→ 需要合并

合并策略：
  1. LWW（Last Write Wins）：取时间戳最大的版本
     简单，但可能丢失并发写
     
  2. 客户端合并：将所有冲突版本返回给客户端，由客户端合并
     Dynamo 购物车的做法：合并为并集
     
  3. CRDT：数据结构级别自动合并（见笔记05）
  
  4. 后台 Anti-entropy Repair（Merkle Tree）：
     定期全量比对，修复所有不一致（见笔记07）

实际参数选择

参考资料

• DeCandia, G. et al. (2007). Dynamo: Amazon's Highly Available Key-value Store
• 《Designing Data-Intensive Applications》Ch.5 — Leaderless Replication
• Vogels, W. (2009). Eventually Consistent. ACM Queue.