罗罗编程学习记录
本页内容 展开查看

09.9.2 Quorum 与多数派读写

所属:全栈开发面试题库 / 09 高阶架构:高并发与分布式 / 09.9 分布式基础算法

覆盖范围

  • NWR 模型与相交条件
  • 读写 quorum 配置与一致性取舍
  • 慢副本处理与超时
  • Quorum 与共识协议的关系
  • 工程实现:Dynamo、Cassandra、etcd

高频题速览

编号 题目 难度 频率
09.9.2-001 Quorum NWR 怎么算 进阶 ★★★★★
09.9.2-002 R + W > N 意味着什么 进阶 ★★★★☆
09.9.2-003 怎么根据场景调 W 和 R 进阶 ★★★★☆
09.9.2-004 慢副本怎么处理 进阶 ★★★☆☆
09.9.2-005 Quorum 和多数派共识的区别 高级 ★★★★☆
09.9.2-006 W=N 时写性能怎么样 进阶 ★★★☆☆
09.9.2-007 R=N 时读性能怎么样 进阶 ★★★☆☆
09.9.2-008 版本号与读修复 进阶 ★★★☆☆
09.9.2-009 Hinted Handoff 是什么 进阶 ★★★☆☆
09.9.2-010 Quorum 下的一致性窗口 高级 ★★★☆☆

09.9.2-001 Quorum NWR 怎么算?

一句话结论

N 是副本总数,W 是写成功需要确认的副本数,R 是读时需要返回并比对的副本数;当 R + W > N 时,读 quorum 和写 quorum 的集合必然相交,读到的副本中至少有一个包含最新写,配合版本号比对就能读到最新值。

概念解释

  • N:数据副本份数,通常 3 或 5。
  • W:写请求需要 W 个副本确认才算成功。
  • R:读请求需要 R 个副本返回结果,比对版本取最新。
  • 相交:R + W > N 保证读写集合有交集。

原理流程

N=3, W=2, R=2
  R+W=4 > 3 → 读写 quorum 相交
  写:至少 2 副本确认
  读:至少 2 副本返回,比对版本取新

代码或图示

N=3, W=2, R=1:
  R+W=3 = N,不严格大于
  → 可能读到旧副本(W 的 2 个副本和 R 的 1 个副本不相交)
N=3, W=2, R=2:
  R+W=4 > 3 → 必然读到至少一个最新副本

常见误区

  • 误区:N=3, W=2, R=2 就是强一致。相交只保证读到最新版本,仍需要版本号比对,且失败副本处理要考虑。
  • 误区:Quorum 配置所有副本都要在线。超时未响应的副本不计入 quorum,详见 09.9.2-004。

追问

  • 问:和 09.5.1.1 一致性模型什么关系?答:09.5.1.1 讲一致性模型定义,这里讲 NWR 工程配置。
  • 问:典型配置?答:Dynamo/Cassandra 常用 N=3, W=2, R=2(fast quorum)。

09.9.2-002 R + W > N 意味着什么?

一句话结论

R + W > N 意味着读 quorum 集合和写 quorum 集合必有交集,因此读请求返回的 R 个副本中至少有一个是最近一次写 quorum 成功的副本,读到最新版本的概率有集合论保证;这是 Quorum 一致性的核心不等式。

概念解释

  • 集合相交:|R_set ∩ W_set| >= R + W - N > 0。
  • 版本比对:从相交副本取版本最高的值返回。
  • 不相交:R + W <= N 时,读写集合可能不相交,读到旧值。

原理流程

写 W=2 个副本确认成功(A、B)
读 R=2 个副本返回(C、D)
  如果 R+W <= N:C、D 可能都不是 A、B → 读到旧值
  如果 R+W > N:R 个副本中至少有一个在 W 集合里 → 读到最新

代码或图示

N=5, W=3, R=3:
  R+W=6 > 5 → 读写集合必相交至少 1 个副本
N=5, W=2, R=2:
  R+W=4 < 5 → 可能不相交,读到旧值

常见误区

  • 误区:R+W>N 就自动强一致。还要版本号比对、处理失败副本、读修复。
  • 误区:R+W>N 时读一定最快。要等 R 个副本返回,慢副本拖累读延迟。

追问

  • 问:R+W=N 行不行?答:临界情况,集合相交为空,不保证读到最新,不推荐。
  • 问:怎么选 W 和 R?答:写多读少调大 W、调小 R;读多写少调大 R、调小 W,详见 09.9.2-003。

09.9.2-003 怎么根据场景调 W 和 R?

一句话结论

写多读少的场景调大 W、调小 R(保证写可靠,读容忍少量旧值);读多写少的场景调大 R、调小 W(读性能优先,写异步确认);强一致场景 W+R>N;极端可用场景 W=1, R=1(最终一致,最高性能)。

概念解释

  • 写多读少:W 大保证数据可靠,R 小读快。
  • 读多写少:R 大保证读到最新,W 小写快。
  • 一致性要求:W+R>N 保证读到最新。

原理流程

场景 → W, R 配置:
  强一致:W+R>N(例如 N=3, W=2, R=2)
  写多读少:W=2, R=1(N=3,W+R=3=N,临界)
  读多写少:W=1, R=2(N=3,W+R=3=N,临界)
  高性能最终一致:W=1, R=1

代码或图示

电商商品详情(读多写少):
  N=3, W=1(写快),R=2(读到最新概率高)
库存扣减(强一致):
  N=3, W=2, R=2(或直接走共识)

常见误区

  • 误区:所有场景 W+R>N。读多写少的展示数据,W=1, R=2 已经够用,不必 W=2, R=2。
  • 误区:W=1 一定丢数据。W=1 时写一个副本成功就返回,其他副本异步复制,故障时可能丢未复制的数据。

追问

  • 问:Cassandra 怎么配?答:ONE/QUORUM/ALL,业务按字段一致性要求选择。
  • 问:etcd 用 Quorum 吗?答:etcd 用 Raft 共识,写必须多数派确认,R 通常读 leader 或 quorum。

09.9.2-004 慢副本怎么处理?

一句话结论

读请求等 R 个副本返回,如果某个副本超时未响应,不等待它,用已返回的副本比对版本;写请求等 W 个副本确认,超时未确认的副本不影响 quorum 成功,但要记录该副本落后,后续通过读修复或反熵补齐。

概念解释

  • 超时:副本响应超过阈值,不计入成功 quorum。
  • 读修复:读时发现某副本版本旧,异步把最新值写回该副本。
  • 反熵:后台定期比对副本数据,修复不一致。

原理流程

读:等 R 个副本返回
  - 副本 A 快,副本 B 慢(超时)
  - 用 A + 其他快副本比对版本
  - 发现 B 版本旧 → 异步读修复 B
写:等 W 个副本确认
  - W 个确认成功就返回
  - 超时的副本下次反熵补齐

代码或图示

读超时阈值:例如 200ms
  200ms 内 R 个副本返回 → 比对版本
  否则用已返回副本,标记慢副本

常见误区

  • 误区:quorum 要求所有副本在线。超时副本不计入,只要 W/R 个响应就成功。
  • 误区:慢副本被排除就不管了。要通过读修复和反熵补齐,否则数据长期不一致。

追问

  • 问:读修复怎么触发?答:读请求返回时比对各副本版本,发现旧版本就异步写回。
  • 问:反熵多久跑一次?答:按数据量和一致性要求,小时级或天级。

09.9.2-005 Quorum 和多数派共识(Raft/Paxos)有什么区别?

一句话结论

Quorum 是读写 quorum 配置(NWR),保证读写集合相交读到最新;多数派共识(Raft/Paxos)是保证所有节点对日志顺序达成一致,写必须多数派确认且日志顺序一致;Quorum 是最终一致模型(版本比对),共识是线性一致模型(日志顺序保证)。

概念解释

  • Quorum:读时从多个副本比对版本,不保证日志顺序。
  • 共识:写必须多数派确认,日志顺序一致,保证线性一致。
  • 区别:Quorum 允许副本暂时不一致,靠版本比对;共识不允许未提交的日志分叉。

原理流程

Quorum(Dynamo/Cassandra):
  写 W 个副本,读 R 个副本,版本比对
  → 最终一致,允许版本分叉
共识(Raft/etcd):
  写必须多数派确认,日志顺序一致
  → 线性一致,无版本分叉

代码或图示

Quorum:
  副本间日志顺序可能不同
  读时版本号/时间戳比对取最新
共识:
  所有已提交日志在所有节点顺序一致
  读无需版本比对

常见误区

  • 误区:Quorum 就是共识。Quorum 是读时比对,共识是写时达成顺序一致,模型不同。
  • 误区:Quorum 配置 W+R>N 等于线性一致。它只保证读到最新版本,不保证日志顺序与线性时间。

追问

  • 问:什么时候用 Quorum?答:高可用、最终一致的存储,例如 Cassandra、Dynamo。
  • 问:什么时候用共识?答:需要线性一致的配置中心、元数据存储,例如 etcd、ZooKeeper。

09.9.2-006 W=N 时写性能怎么样?

一句话结论

W=N 意味着写必须所有副本确认才算成功,写延迟等于最慢副本的延迟(尾巴延迟),写吞吐受限于最慢副本;但数据可靠性最高(所有副本都有最新写),适合数据不能丢、写 QPS 不高的元数据场景。

概念解释

  • W=N:所有副本确认才返回。
  • 尾巴延迟:写 RT = max(各副本 RT),慢副本拖累整体。
  • 可靠性:最高,所有副本都有最新数据。

原理流程

写请求 → N 个副本并行写
  → 等所有副本确认
  → 返回成功
  RT = max(各副本 RT)

代码或图示

N=3, W=3:
  副本 A RT=5ms, B RT=10ms, C RT=50ms(GC 停顿)
  → 写 RT=50ms,受最慢副本拖累

常见误区

  • 误区:W=N 性能最好。W=N 写延迟最高,因为要等最慢副本。
  • 误区:W=N 不需要读修复。所有副本都写了,但读仍可能因时间差读到旧值,版本比对仍需要。

追问

  • 问:什么场景 W=N?答:元数据、配置中心,写 QPS 低但不能丢。
  • 问:W=N 故障怎么办?答:一个副本宕机,写请求无法满足 W=N,集群不可写。

09.9.2-007 R=N 时读性能怎么样?

一句话结论

R=N 意味着读必须等所有副本返回,读延迟等于最慢副本延迟,读吞吐受慢副本拖累;但能比对所有副本版本,读到最新版本概率最高;适合读 QPS 低、一致性要求高的场景。

概念解释

  • R=N:读所有副本,比对版本。
  • 慢副本拖累:读 RT = max(各副本 RT)。
  • 版本最全:所有副本都比对,取最新。

原理流程

读请求 → N 个副本并行读
  → 等所有返回
  → 比对版本取最新
  RT = max(各副本 RT)

代码或图示

N=3, R=3:
  副本 A 5ms, B 8ms, C 100ms(慢)
  → 读 RT=100ms

常见误区

  • 误区:R=N 一定读到最新。R=N 比对所有副本,版本最全,但仍要处理版本比对与冲突。
  • 误区:R=N 读性能好。R=N 读延迟最高,慢副本拖累。

追问

  • 问:什么场景 R=N?答:强一致读、元数据读,QPS 低。
  • 问:怎么避免慢副本拖累?答:读超时,不等慢副本,用已返回副本,详见 09.9.2-004。

09.9.2-008 版本号与读修复怎么做?

一句话结论

每个数据副本带版本号(单调递增计数器或向量时钟),读请求从 R 个副本拿到值和版本,取版本最高的值返回;如果发现某副本版本低,异步把最新值写回该副本(读修复);版本号是 Quorum 一致性的基础。

概念解释

  • 版本号:单调递增,每次写版本 +1。
  • 版本比对:取版本最高的值。
  • 读修复:发现旧副本,异步写回最新值。

原理流程

读 → R 个副本返回 (value, version)
  → 取 version 最高的 value 返回
  → 如果某副本版本低 → 异步写回最新值

代码或图示

副本 A: (value=10, v=5)
副本 B: (value=10, v=5)
副本 C: (value=8, v=3)
  → 返回 value=10
  → 异步读修复 C:写回 (10, 5)

常见误区

  • 误区:版本号用时间戳。各节点时钟可能漂移,时间戳不能做跨副本版本裁决,用单调计数器。
  • 误区:读修复是同步的。读修复异步做,不阻塞读请求。

追问

  • 问:版本号怎么生成?答:每个写节点单调递增,或用向量时钟记录多节点并发写。
  • 问:并发写同一 key 怎么办?答:版本号相同(并发),进入冲突合并,详见 09.9.5 向量时钟。

09.9.2-009 Hinted Handoff 是什么?

一句话结论

Hinted Handoff(暗示交接)是 Dynamo/Cassandra 的机制:写请求时如果某个副本暂时不可用,协调节点先把写入的值存在本地(hint),等副本恢复后再把 hint 重放给该副本,保证副本不丢失数据。

概念解释

  • 暗示:写不可用副本时,协调节点暂存数据。
  • 重放:副本恢复后,协调节点把暂存数据发给它。
  • 目的:避免副本故障期间数据永久丢失。

原理流程

写请求 → 副本 A、B 可用,副本 C 不可用
  → 协调节点写 A、B,把 C 的数据暂存为 hint
  → C 恢复后 → 协调节点把 hint 发给 C

代码或图示

Hint 存储:
  协调节点本地磁盘,记录目标副本、数据、过期时间
  副本恢复 → 重放 hint → 清理

常见误区

  • 误区:Hinted Handoff 替代 Quorum。它是副本故障期间的数据暂存机制,仍需配合 W/R 配置。
  • 误区:hint 永久存储。hint 有过期时间,副本长期不可用时要触发反熵。

追问

  • 问:hint 存多久?答:通常数小时到数天,超过则触发反熵。
  • 问:协调节点故障怎么办?答:hint 复制到其他协调节点,避免丢失。

09.9.2-010 Quorum 下的一致性窗口有多大?

一句话结论

Quorum 下一致性窗口是从写请求到所有副本收敛的时间:写成功 W 个副本后,其他副本异步复制,窗口内读可能读到旧值;窗口大小取决于异步复制延迟、读修复频率、反熵周期,通常秒级到分钟级。

概念解释

  • 写成功:W 个副本确认就返回。
  • 异步复制:其他副本后续追赶。
  • 窗口:写成功到所有副本一致的时间。

原理流程

写 W=2 副本成功 → 返回
  副本 C 异步复制,1 秒后追上
  → 窗口内读 C 可能旧值
  → 读修复或反熵收敛

代码或图示

窗口来源:
  - 异步复制延迟
  - 慢副本未及时更新
  - 读修复未触发

常见误区

  • 误区:W+R>N 没有一致性窗口。W+R>N 保证读到最新版本,但其他副本仍有窗口,窗口内读 quorum 集合可能不含最新写。
  • 误区:窗口内读一定旧值。读 quorum 集合相交时仍能读到最新,窗口影响的是未被读 quorum 覆盖的副本。

追问

  • 问:怎么缩短窗口?答:提高 W(更多副本同步写)、频繁读修复、反熵周期缩短。
  • 问:关键读怎么避免窗口?答:读 quorum 设为 R=W=N,或读 leader(共识协议)。

待整理清单

  • [ ] Cassandra 一致性级别配置示例
  • [ ] etcd Raft 读一致性(Linearizable Read)
  • [ ] 读修复与反熵工程实现