跳转到内容
Jason's Study

CRAQ — 让链复制每个节点都能读，吞吐线性扩展

是什么

CRAQ（Chain Replication with Apportioned Queries）是给原版链复制（OSDI 2004）打的一个补丁——让链上任意节点都能服务读请求，但仍保持强一致。日常类比：原版 chain 像工厂流水线，只允许末端工人对外发货；CRAQ 像每个工位都允许客户来取，但每个货箱上贴一张标签写着”已封箱（clean）“或”加工中（dirty）“——前者直接拿走，后者得问末端工位”现在的合格版本是哪个”。

技术语言：

  • 每个对象在每个节点维护版本列表，每条版本带 clean | dirty 标记
  • 写传播时，链上每节点收到先存 dirty 版本；tail 收到后从尾向头回传 commit 通知，被通知到的节点把对应版本翻成 clean，丢弃更早版本
  • 读 clean 直接返回；读 dirty 跳一次 tail 询问当前已提交版本号，再从本地多版本中挑那个返回

这样读吞吐随节点数线性扩展，写路径与原版一致。

为什么重要

不理解 CRAQ，下面这些事都没法解释：

  • 为什么”强一致 + 读吞吐扩展”两件事可以同时拿——很多人误以为必须靠 quorum read 才能扩展
  • 为什么 HyperDex、CorfuDB、ChainReaction 等系统在 chain replication 之上还要再选 CRAQ 风格
  • 为什么”多版本 + dirty/clean 标记”是把强一致挪出 tail 单点的标准模板
  • 为什么 dirty 读”只多查一次 tail”就能保住线性化——这背后是个非常巧的论证

核心要点

CRAQ 的关键可以拆成 三件事：

  1. 多版本对象：每个节点对每个 key 存一个版本列表。新写来 → 追加一个 dirty 版本；commit 通知到 → 把对应版本翻 clean，删除所有更早版本。类比：每个工位的货架上同时放”已封箱”和”加工中”两种箱子。

  2. 读 clean 直返：节点读到对象最新版本是 clean，直接返回本地副本。这就是吞吐扩展的来源——任意节点都能直接服务读请求，不用经过 tail。

  3. 读 dirty 转 tail 询问：节点最新版本是 dirty，意味着有个写还在传播没到 tail。节点向 tail 发一个轻量 query：“你那的当前 commit 版本号是啥？“，tail 返回 v_k，节点从自己的版本列表里挑 v_k 那条返回给客户端。这一步保证返回值已被 tail 见过 = 线性化。

实践案例

案例 1：一次写穿过 5 节点链

5 副本链 A → B → C → D → E（A=head，E=tail）。client 发 set x = 5：

A: 收到 → 存 dirty(x=5,v=7) → 转发给 B
B: 收到 → 存 dirty(x=5,v=7) → 转发给 C
... C, D 同理
E: 收到 → 存 clean(x=5,v=7) → ACK 反向回传
D: 收到 ACK → dirty(v=7) 翻 clean，删除 v<7
... C, B, A 同理

任意时刻 client read 都能打到任意节点：v=7 已 clean 的节点直返；还没翻的节点跳一次 E 问”当前 commit 版本”，E 答 7（或更新），节点从本地拿 v=7 返回。

案例 2：dirty 读为什么仍是线性化

A 上 x 当前是 dirty(v=7)（写还在飞），并且 A 上还有 clean(v=6)。client 来读：

A 看到最新是 dirty → 向 E 询问 "x 当前 commit 版本？"
E 回 "v=6（v=7 还没传到我这）"
A 从本地取 clean(v=6) 返回

如果 E 那边正好传到了，E 回 “v=7”，A 从本地 dirty 列表里取 v=7 返回。这条 v=7 此刻已被 tail commit，因此对外可见的就是已提交值——线性化成立。

案例 3：和原版 chain 的吞吐对比

3 节点链，读多写少（95% read）：

原版 chain replication：所有 read 都打 tail
  → tail CPU 100%，head/middle 闲置，吞吐 = 1 节点上限


CRAQ：read 分摊到 3 个节点
  → 3 个节点都 ~33% CPU 服务读，吞吐 ≈ 3 节点上限

论文实测：5 节点链上 CRAQ 读吞吐相比 chain 提升约 4-5 倍；写吞吐基本持平（写路径没变）。读越多、节点越多、增益越大。

CRAQ 还提供两种弱一致变体：eventual consistency（dirty 直接返回，不查 tail）和 eventual with max-bounded staleness（dirty 但只要本地版本不太旧就直返）。客户端可按 key 选择强 / 弱模式，工业场景里冷数据走强、热数据走弱。

踩过的坑

  1. 以为 dirty 读不安全：错。dirty 读会同步查 tail 拿当前 commit 版本号，返回的永远是 tail 已见过的版本。dirty 不是”脏数据”，是”本节点不确定哪个是 commit 的”——一次 RPC 解决。

  2. 多版本会无限堆积：不会。每次 commit 通知到达，节点把对应版本翻 clean 后会丢弃所有更早版本。只有正在飞的写才会让版本列表暂时变长，链稳态下每节点每 key 只存 1 个 clean 版本。

  3. 以为 CRAQ 也降低了写延迟：错。写仍要从 head 走到 tail，再 commit ACK 回传——延迟与原版 chain 一致，O(链长)。CRAQ 只优化读。

  4. 跨 key/跨链事务无能为力：CRAQ 单链内强一致，多 key 跨多链的事务仍需 2PC 或外部协调。论文里专门说 CRAQ 不解决多键事务。

  5. dirty 读还是要一次额外 RPC：客户端如果对延迟敏感、读到 dirty 比例又高（写非常密集），平均读延迟反而高于原版 chain。CRAQ 的甜区在写少、读密、链长。

适用 vs 不适用场景

适用：

  • 读多写少的强一致 KV / 对象存储——典型 95% read，CRAQ 能把读吞吐线性扩展
  • 想保留 chain 工程简单度的同时绕开 tail 读瓶颈
  • 跨数据中心部署链时，地理近的节点读延迟也低（无需跨洲打 tail）

不适用：

  • 写密集场景——写路径未优化，吞吐瓶颈仍在链上 commit
  • 需要多 key 跨链事务——必须搭 2PC 或上层事务管理器
  • 链长很短（2-3 节点）的小集群——原版 chain 的 tail 瓶颈不严重，CRAQ 增益有限
  • Byzantine 故障模型——和原版一样假设 fail-stop

历史小故事（可跳过）

  • 2004：van Renesse + Schneider 在 OSDI 提出 chain replication，强一致简单工程化，但读必经 tail。
  • 2009：Princeton 的 Jeff Terrace 与 Mike Freedman 在 USENIX ATC 提出 CRAQ。论文标题强调 “Read-Mostly Workloads”——明确针对读多写少场景。
  • 2010s：HyperDex（2012）、CorfuDB、ChainReaction 等系统采用 CRAQ 风格的多版本 + dirty/clean 设计。
  • 2020：Hermes 协议把 chain 思想再往前推一步——任意节点既可读也可写，invalidation-based 协议替代纯链式转发。

CRAQ 是”教科书级别的协议小改动产生工程级别大收益”的典型案例——加一个 dirty/clean 标记，吞吐扩展 N 倍。

学到什么

  1. 多版本 + 标记 = 读扩展的标准模板——把”是否已 commit”显式化成版本标记，读者就能本地判断 + 必要时一次 RPC 兜底
  2. 强一致不一定要走单点读——只要能用某种方式让任意节点的返回值”等价于 tail 见过的某个版本”，线性化就能保住
  3. 协议改动要看清优化哪个维度——CRAQ 只优化读，写延迟没变；这是有意识的取舍而非疏漏
  4. 读多写少是分布式存储最常见的工业负载——绝大部分系统读写比 9:1 到 99:1，CRAQ 这类专门优化读的协议价值远大于看起来

延伸阅读

关联

  • chain-replication-2004 —— CRAQ 是它的读优化版，写路径完全沿用
  • paxos-1998 —— CRAQ 的成员管理 master 通常用 Paxos 实现
  • smr-1990 —— 链复制 + CRAQ 都是 SMR 框架的一种实现
  • azure-storage-2011 —— Azure Storage 流层用 chain 变种，思路与 CRAQ 同源
  • brewer-cap-2000 —— CRAQ 仍选 CP，网络分区下停服等 reconfig
  • bigtable-2006 —— 行级强一致 + 读多写少的工业场景，与 CRAQ 目标接近
  • raft —— Raft 同样要解决”扩展读”问题，常用 lease + read-index 路线，与 CRAQ 思路对照
  • spanner-2012 —— 跨 Paxos 组事务，CRAQ 单链强一致是它在更小尺度上的近亲

反向链接

  • azure-storage-2011 —— Windows Azure Storage 2011 — 云对象存储第一次在工业界做到强一致
  • bigtable-2006 —— Bigtable 2006 — Google 把行级随机读写做到 PB 级的存储系统
  • brewer-cap-2000 —— Brewer CAP — 网络一断电，一致性和可用性只能留一个
  • chain-replication-2004 —— Chain Replication — 把多副本排成流水线，简单且强一致
  • paxos-1998 —— Paxos 1998 — 古希腊议会寓言里藏的共识协议
  • raft —— Raft — 易理解的共识算法
  • smr-1990 —— SMR 1990 — 把”容错服务”还原成”多副本一起跑同一台状态机”
  • spanner-2012 —— Spanner 2012 — 用原子钟和 GPS 给全球数据库发时间戳