【分布式系统百科】链式复制与 CRAQ：不走寻常路的高吞吐方案

一、引言：为什么需要链式复制

在分布式系统的复制协议中，我们通常会第一时间想到 Raft 或 Paxos。这些基于共识（Consensus）的复制方案已经成为工业界的主流选择，从 etcd 到 CockroachDB，从 Consul 到 TiKV，几乎所有需要强一致性保证的系统都在使用它们。但在 2004 年，Cornell 大学的 Robbert van Renesse 和 Fred Schneider 提出了一个完全不同的思路：链式复制（Chain Replication）。

链式复制的核心思想简单却优雅：将所有副本按线性顺序排列成一条链，写操作从链头（Head）开始，沿着链顺序传播到链尾（Tail），而读操作只在链尾进行。这种看似简单的设计，却带来了几个令人惊讶的特性：

1. 强一致性自然保证：由于所有读操作都在链尾进行，而链尾保存了所有已提交的写入，系统天然满足线性一致性（Linearizability）。
2. 写入吞吐量高：链式传播允许多个写操作同时在链的不同位置进行流水线处理（Pipeline），充分利用带宽。
3. 读取路径简化：读操作只需要访问链尾一个节点，无需任何共识协议或多数派确认。

然而，链式复制也有明显的局限：所有读操作集中在链尾，形成读取瓶颈。2009 年，Jeff Terrace 和 Michael J. Freedman 在 USENIX ATC 发表了 CRAQ（Chain Replication with Apportioned Queries），通过巧妙的版本控制机制，允许链上任意节点提供读服务，同时保持强一致性。

本文将深入探讨链式复制和 CRAQ 的设计原理、性能特征、故障恢复机制，以及它们在工业界的实际应用。

二、Chain Replication 核心协议

2.1 基础模型与角色定义

链式复制假设有 N 个副本节点，按固定顺序排列为链：S₁ → S₂ → S₃ → … → Sₙ。其中：

• Head（链头）：S₁，负责接收所有客户端的写请求
• Tail（链尾）：Sₙ，负责处理所有客户端的读请求
• Middle（中间节点）：S₂ 到 Sₙ₋₁，只负责转发写操作

每个节点维护两个关键数据结构：

type ChainNode struct {
    nodeID      int
    isHead      bool
    isTail      bool
    successor   *ChainNode  // 后继节点
    predecessor *ChainNode  // 前驱节点
    
    // 数据存储
    store       map[string]string
    
    // 待确认的写入队列
    pendingWrites []WriteOp
    
    // 已提交的最新序列号
    committedSeq  int64
}

type WriteOp struct {
    key       string
    value     string
    sequence  int64
    clientID  string
}

2.2 写入协议详解

写入协议的核心是沿链传播。整个流程分为三个阶段：

阶段一：客户端发起写入

客户端将写请求发送到 Head 节点。Head 节点做两件事： 1. 将写操作追加到本地的 pendingWrites 队列 2. 立即将写操作转发给后继节点

def handle_write_at_head(key, value, client_id):
    # 分配全局递增序列号
    seq = allocate_sequence_number()
    
    # 记录到本地待确认队列
    op = WriteOp(key, value, seq, client_id)
    pending_writes.append(op)
    
    # 转发给后继节点
    send_to_successor(op)
    
    # 注意：Head 不会立即回复客户端

这里有一个关键设计：Head 接收到写入后，不会立即回复客户端，也不会更新本地的已提交状态。Head 只是一个”入口”角色。

阶段二：链中传播

中间节点收到写操作后，执行相同的流程： 1. 追加到本地 pendingWrites 队列 2. 转发给后继节点

def handle_write_at_middle(op):
    # 记录到本地待确认队列
    pending_writes.append(op)
    
    # 继续转发
    send_to_successor(op)

这种链式传播允许多个写操作形成流水线（Pipeline）。假设链上有 5 个节点，当写操作 W₁ 到达节点 3 时，W₂ 可能已经到达节点 2，W₃ 刚到达 Head。这种并行性是链式复制高吞吐的关键。

阶段三：Tail 确认并应用

当写操作到达 Tail 时，情况发生变化：

def handle_write_at_tail(op):
    # 应用到状态机
    store[op.key] = op.value
    
    # 更新已提交序列号
    committed_seq = op.sequence
    
    # 回复客户端：写入成功
    send_ack_to_client(op.client_id, op.sequence)
    
    # 向前传播 ACK，告知前驱节点可以提交
    send_commit_ack_to_predecessor(op.sequence)

Tail 的职责是： 1. 将写操作真正应用到状态机 2. 向客户端发送成功响应 3. 向链上游发送确认消息（ACK），通知前驱节点可以安全提交

阶段四：ACK 逆向传播

中间节点收到 ACK 后：

def handle_commit_ack(seq):
    # 提交所有序列号 <= seq 的操作
    for op in pending_writes:
        if op.sequence <= seq:
            store[op.key] = op.value
            pending_writes.remove(op)
    
    committed_seq = seq
    
    # 继续向前传播 ACK
    if not is_head:
        send_commit_ack_to_predecessor(seq)

ACK 沿链反向传播，每个节点在收到 ACK 后，将对应的写操作从 pendingWrites 移到已提交状态。最终 ACK 到达 Head，整条链完成提交。

2.3 读取协议

读取协议极其简单：

def handle_read(key):
    if not is_tail:
        # 非 Tail 节点拒绝读请求
        return Error("Read must go to tail")
    
    # Tail 直接返回本地值
    return store.get(key, None)

所有读请求必须发送到 Tail。由于 Tail 只返回已提交的数据，且写入必须经过完整链式传播才能提交，因此读取到的数据必然是所有已确认写入的最新值。这自然满足线性一致性。

2.4 为什么能保证强一致性？

链式复制的强一致性保证源于以下不变式（Invariant）：

不变式 1：对于任意已提交的写操作 W，链上所有节点要么已应用 W（存储在 store 中），要么 W 在其 pendingWrites 队列中。

不变式 2：对于任意两个写操作 W₁ 和 W₂，如果 W₁ 在链头的序列号小于 W₂，则 W₁ 在链的任意节点上的序列号都小于 W₂。也就是说，写操作的全局顺序在链上保持一致。

不变式 3：Tail 节点的 store 包含了所有已提交的写入，且不包含任何未提交的写入。

基于这些不变式，我们可以证明： - 读操作总是返回最新提交的值（线性一致性） - 任意两个并发操作有全局确定的顺序（Total Order）

假设客户端 C₁ 写入 W₁，客户端 C₂ 读取 R₂。如果 R₂ 开始于 W₁ 的 ACK 之后，则 R₂ 必然看到 W₁ 的效果，因为： 1. W₁ 的 ACK 表示 Tail 已应用 W₁ 2. R₂ 读取 Tail 的 store 3. 根据不变式 3，Tail 的 store 包含 W₁

这正是线性一致性的定义。

三、性能分析与优缺点

3.1 吞吐量分析

链式复制的写入吞吐量受益于流水线并行。假设： - 链长度为 N - 节点间网络延迟为 d - 单个节点处理一次写入的时间为 p（包括序列化、磁盘写入等）

在串行模型下，完成一次写入的延迟为：

L_serial = N × (d + p)

但在流水线模型下，当第一个写入完成后，后续写入可以持续进入流水线。稳态吞吐量为：

Throughput = 1 / max(d + p)

这意味着： - 如果网络是瓶颈（d > p），吞吐量约为 1/d - 如果处理是瓶颈（p > d），吞吐量约为 1/p

关键观察：吞吐量与链长度 N 无关！ 这是因为流水线允许 N 个写入同时在链的不同位置处理。

举个具体例子： - d = 1ms（数据中心内网络延迟） - p = 0.5ms（SSD 写入延迟） - N = 5

串行延迟：5 × (1 + 0.5) = 7.5ms 流水线吞吐量：1 / 1ms = 1000 ops/s（每个节点）

如果有 100 个并发客户端持续写入，总吞吐量可达 100,000 ops/s。

3.2 读取性能与瓶颈

链式复制的读取性能有明显的瓶颈：所有读请求集中在 Tail 节点。假设 Tail 的处理能力为 C_tail，则系统的读取吞吐量上限为：

Read_throughput ≤ C_tail

这在读密集型工作负载下成为严重问题。假设： - 系统需要处理 100,000 reads/s - Tail 的单机能力为 50,000 reads/s

此时系统无法满足需求，即使增加链长度也无济于事，因为读取不会分散到其他节点。

对比 Raft/Paxos 的 Follower Read 优化： - Raft 允许从 Follower 读取（需要 ReadIndex 或 Lease 机制） - 读取可以分散到多个节点，总吞吐量为 N × C_node

这是链式复制最大的劣势。

3.3 延迟特性

链式复制的端到端延迟（从客户端写入到收到 ACK）为：

L = N × (d + p) + d_return

其中 d_return 是 Tail 到客户端的返回延迟。对于 N=5, d=1ms, p=0.5ms：

L = 5 × 1.5 + 1 = 8.5ms

这比 Raft/Paxos 的多数派延迟要高。Raft 只需等待 ⌈N/2⌉ 个节点确认：

L_raft = ⌈N/2⌉ × (d + p)
      = 3 × 1.5 = 4.5ms

但延迟劣势在高吞吐场景下会被流水线效应抵消。当有大量并发写入时，链式复制的平均延迟和 Raft 类似，而吞吐量可能更高。

3.4 优势总结

1. 实现简单：没有复杂的选主（Leader Election）逻辑，没有日志匹配算法，代码量远小于 Raft
2. 确定性顺序：所有写入有全局确定的顺序，无需 Raft 的 Log Compaction 复杂性
3. 高写入吞吐：流水线并行允许充分利用网络和磁盘带宽
4. 强一致性简单：线性一致性通过架构自然保证，无需额外机制

3.5 劣势总结

1. 读取瓶颈：Tail 成为单点瓶颈，无法水平扩展读取
2. 延迟较高：需要遍历整条链，不如多数派延迟
3. 故障恢复复杂：不同位置的节点故障需要不同的恢复策略（详见第七节）
4. 链配置变更困难：增减节点需要小心处理 pending 写入

四、CRAQ：突破读取瓶颈

4.1 问题与动机

链式复制的读取瓶颈在实际系统中非常明显。以一个实际场景为例：

假设我们有一个元数据存储系统，存储了 1 亿个对象的元数据（key-value 对）。工作负载为： - 95% 读操作，5% 写操作 - 总 QPS: 1,000,000

则读取 QPS = 950,000，写入 QPS = 50,000。

如果使用 5 节点的链式复制： - 写入吞吐：充分利用流水线，假设每节点处理 50,000 writes/s，可以满足 - 读取吞吐：全部落在 Tail，假设 Tail 只能处理 200,000 reads/s，无法满足

CRAQ 的目标就是解决这个问题：允许链上任意节点提供读服务，同时保持强一致性。

4.2 核心思想：版本链与 Clean/Dirty 标记

CRAQ 的关键洞察是：中间节点虽然可能有 pending 的写入，但它知道这些写入是否已经提交。如果能区分”已提交”和”未提交”的版本，就可以安全地提供读服务。

CRAQ 为每个 key 维护一个版本链：

type VersionedValue struct {
    value     string
    version   int64
    isClean   bool  // Clean: 已提交; Dirty: 未提交
}

type CRAQNode struct {
    nodeID      int
    successor   *CRAQNode
    predecessor *CRAQNode
    
    // 每个 key 映射到版本列表
    store       map[string][]VersionedValue
    
    // 已知的最新提交版本（从 Tail 同步）
    committedVersion map[string]int64
}

版本状态定义： - Clean 版本：已经被 Tail 确认提交，所有节点都可以安全返回 - Dirty 版本：仍在传播过程中，尚未被 Tail 确认

4.3 CRAQ 写入协议

CRAQ 的写入协议在链式复制基础上增加版本管理：

Step 1: Head 收到写入，创建新版本并标记为 Dirty

def craq_write_at_head(key, value, seq):
    # 创建新版本，标记为 Dirty
    new_version = VersionedValue(value, seq, is_clean=False)
    
    # 追加到版本链
    if key not in store:
        store[key] = []
    store[key].append(new_version)
    
    # 转发给后继
    send_to_successor(key, value, seq)

Step 2: 中间节点收到写入，同样标记为 Dirty

def craq_write_at_middle(key, value, seq):
    new_version = VersionedValue(value, seq, is_clean=False)
    store[key].append(new_version)
    send_to_successor(key, value, seq)

Step 3: Tail 收到写入，标记为 Clean 并发送 ACK

def craq_write_at_tail(key, value, seq):
    # Tail 直接标记为 Clean
    new_version = VersionedValue(value, seq, is_clean=True)
    store[key] = [new_version]  # Tail 只保留最新 Clean 版本
    
    # 回复客户端
    send_ack_to_client(seq)
    
    # 向前传播 Clean ACK
    send_clean_ack_to_predecessor(key, seq)

Step 4: ACK 逆向传播，将对应版本标记为 Clean

def handle_clean_ack(key, seq):
    # 找到对应版本，标记为 Clean
    for v in store[key]:
        if v.version == seq:
            v.is_clean = True
            committed_version[key] = seq
            break
    
    # 清理旧版本（小于 seq 的所有版本）
    store[key] = [v for v in store[key] if v.version >= seq]
    
    # 继续向前传播
    if not is_head:
        send_clean_ack_to_predecessor(key, seq)

4.4 CRAQ 读取协议：版本查询

CRAQ 的读取协议允许客户端从任意节点读取。节点根据版本状态决定如何响应：

情况 1：所有版本都是 Clean

如果节点的版本链中所有版本都是 Clean，说明没有 pending 写入，直接返回最新版本：

def craq_read(key):
    if key not in store:
        return None
    
    versions = store[key]
    
    # 检查是否所有版本都是 Clean
    all_clean = all(v.is_clean for v in versions)
    
    if all_clean:
        # 直接返回最新版本
        return versions[-1].value
    else:
        # 有 Dirty 版本，需要查询 Tail
        return query_tail_for_version(key)

情况 2：存在 Dirty 版本

如果存在 Dirty 版本，节点不能直接返回（可能返回未提交的值），需要向 Tail 查询当前已提交的版本号：

def query_tail_for_version(key):
    # 向 Tail 查询当前已提交版本
    committed_ver = ask_tail_committed_version(key)
    
    # 在本地版本链中找到对应版本
    for v in store[key]:
        if v.version == committed_ver:
            return v.value
    
    # 理论上不应该到这里
    raise Exception("Committed version not found locally")

Tail 的版本查询处理：

def tail_handle_version_query(key):
    if key not in store:
        return None, 0
    
    # Tail 只有 Clean 版本，直接返回
    latest = store[key][-1]
    return latest.value, latest.version

4.5 正确性分析

CRAQ 的关键问题是：为什么允许中间节点读取仍然保持线性一致性？

考虑以下场景： 1. 客户端 C1 向 Head 写入 W1: x = 1 2. W1 传播到中间节点 N2，标记为 Dirty 3. 客户端 C2 向 N2 读取 x

此时 N2 有两个版本： - x = 0 (Clean, version 0) - x = 1 (Dirty, version 1)

如果 N2 直接返回 x = 1，而 W1 最终因为 Tail 故障而未提交，就违反了一致性。

CRAQ 的解决方法：N2 检测到 Dirty 版本，向 Tail 查询。假设 Tail 的提交版本为 0，则 N2 返回 x = 0。这保证了：

定理：CRAQ 满足线性一致性。

证明思路： - 如果读取时 key 的所有版本都是 Clean，则 Tail 已提交这些版本，读取返回最新提交值。 - 如果读取时存在 Dirty 版本，节点查询 Tail 的提交版本，返回 Tail 认可的值。 - Tail 的提交版本是全局真相（Source of Truth），所有读取最终与 Tail 一致。

4.6 性能提升

CRAQ 的读取吞吐量理论上可以达到：

Read_throughput = N × C_node

假设每个节点处理 200,000 reads/s，5 节点链可以提供 1,000,000 reads/s。

但实际性能取决于版本查询（Query Tail）的频率。假设： - 写入 QPS: 50,000 - 平均写入延迟: 10ms - 读取 QPS: 950,000

在稳态下，任意时刻大约有 50,000 × 0.01 = 500 个 Dirty 版本在链中传播。如果这些 Dirty 版本均匀分布在所有 key 上，且总 key 数为 100M，则 Dirty 比例为 500/100M = 0.0005%。

这意味着 99.9995% 的读取可以直接从本地返回，只有 0.0005% 需要查询 Tail。实际吞吐量接近理论上限。

但在写密集场景下，情况会恶化。假设写入 QPS = 500,000： - Dirty 版本数: 500,000 × 0.01 = 5,000 - Dirty 比例: 5,000 / 100M = 0.005%

仍然很低，但如果 key 空间很小（比如只有 1M 个 key），Dirty 比例会上升到 0.5%，此时较多读取需要查询 Tail，性能提升有限。

4.7 CRAQ 读扩展的局限与优化

CRAQ 通过允许任意节点提供读服务来实现读扩展，但这一机制并非在所有场景下都能发挥最大效能。理解其局限性并掌握对应的优化手段，对于正确选型和系统调优至关重要。

退化场景分析

CRAQ 读性能退化的根本原因在于：当节点上存在 Dirty 版本时，读请求必须向 Tail 发起版本查询（Version Query），这一额外的网络往返会显著增加延迟并消耗 Tail 的处理能力。退化程度取决于两个关键因素：

1. 高写入速率：写入 QPS 越高，链中同时存在的 Dirty 版本数量越多。假设写入 QPS 为 W，平均写入延迟（从 Head 传播到 Tail）为 L，则任意时刻的 Dirty 版本数约为 W * L。当 W 和 L 都较大时，Dirty 版本数会急剧增加。

2. 小 Key 空间：Dirty 比例 = Dirty 版本数 / 总 Key 数。即使 Dirty 版本绝对数不大，如果 Key 空间很小，单个 Key 处于 Dirty 状态的概率也会很高。例如：

场景A（大 Key 空间）：W=100K, L=10ms, Keys=100M → Dirty比例 = 1000/100M = 0.001%
场景B（小 Key 空间）：W=100K, L=10ms, Keys=10K  → Dirty比例 = 1000/10K  = 10%

在场景 B 中，约 10% 的读请求需要查询 Tail，CRAQ 退化为接近普通 Chain Replication 的行为，读扩展优势大幅减弱。

优化策略

针对上述退化场景，可以采用以下优化手段：

1. 批量版本查询（Batch Version Query）：当节点需要查询 Tail 时，不是每个 Dirty Key 单独发起请求，而是将一段时间窗口内的多个查询聚合为一次批量请求。这可以显著减少网络往返次数，降低 Tail 的请求处理压力。典型实现是设置一个微秒级的聚合窗口（如 100us），窗口内的所有版本查询合并发送。

2. 投机读取（Speculative Read）：当节点检测到某个 Key 的 Dirty 版本只有一个、且该版本的前一个 Clean 版本与 Dirty 版本的值相同时，可以直接返回该值而无需查询 Tail。这种优化适用于”覆盖写”（写入值未改变）的场景。更激进的做法是：如果应用能容忍短暂的过期读取（Stale Read），可以直接返回最新的 Clean 版本，将一致性级别从线性一致性降级为最终一致性。

3. 写入合并（Write Coalescing）：对同一 Key 的连续多次写入，在 Head 节点进行合并，只传播最后一个值。这可以减少链中的 Dirty 版本数量，但会改变写入的语义（中间值被跳过），仅适用于”最终状态”重要而”中间过程”不重要的场景。

与 Raft Follower Read 的对比

Raft 也支持从 Follower 读取数据以实现读扩展，其典型实现方式是 ReadIndex 协议：Follower 收到读请求后，向 Leader 确认当前的 Commit Index，等待本地日志应用到该 Index 后返回结果。

                    CRAQ 读扩展                    Raft Follower Read (ReadIndex)
一致性保证          线性一致性                       线性一致性
额外网络开销        仅 Dirty Key 需查询 Tail         每次读都需确认 ReadIndex
读放大系数          Dirty比例 × 1 RTT               100% × 1 RTT（可通过 Lease Read 优化）
Tail/Leader 压力    仅处理版本查询                   处理 ReadIndex 确认 + 写入
最佳场景            大 Key 空间、读远多于写           任意场景（开销固定且可预测）

总体而言，CRAQ 在大 Key 空间、低写入率场景下的读扩展效率优于 Raft Follower Read，因为绝大多数读请求无需任何额外网络通信。但 Raft Follower Read 的优势在于性能表现更加可预测和稳定，不会因写入模式变化而出现性能波动。

五、实际应用场景

5.1 HDFS Pipeline Replication

HDFS（Hadoop Distributed File System）使用了链式复制的变体来复制数据块。虽然 HDFS 论文没有明确提到 Chain Replication，但其复制流程与链式复制高度相似。

HDFS 写入流程： 1. 客户端向 NameNode 申请写入，NameNode 返回一组 DataNode（DN1, DN2, DN3） 2. 客户端将数据块写入 DN1，DN1 同时转发给 DN2，DN2 转发给 DN3（Pipeline） 3. DN3 发送 ACK 给 DN2，DN2 发送 ACK 给 DN1，DN1 发送 ACK 给客户端 4. 所有 ACK 收到后，客户端确认写入成功

这正是链式复制的写入流程。HDFS 选择链式复制的原因： - 带宽效率：每个 DataNode 只需要发送一份数据，总带宽消耗为 N（节点数）而不是 N² - 高吞吐：Pipeline 允许多个数据块同时复制

HDFS 与标准 Chain Replication 的差异： - HDFS 不要求读取从 Tail 进行（HDFS 的一致性语义较弱） - HDFS 允许客户端指定复制链的顺序（考虑机架感知）

5.2 Corfu Shared Log

Corfu（Clusters of Raw Flash Units）是微软研究院开发的共享日志（Shared Log）系统，用于构建分布式数据库和事务处理系统。Corfu 使用 Chain Replication 来复制日志条目。

Corfu 架构： - 日志被分割成固定大小的 Segment（比如 1GB） - 每个 Segment 复制到一条 Chain（通常 3-5 个节点） - 客户端向 Sequencer 申请日志位置，然后直接写入对应 Chain

为什么 Corfu 选择 Chain Replication： - 确定性顺序：日志的全局顺序至关重要，Chain Replication 自然保证全局顺序 - 高吞吐写入：流水线复制允许快速追加日志 - 简单性：Corfu 的故障恢复由外部 Sequencer 协调，Chain 本身逻辑简单

5.3 FawnKV

FAWN（Fast Array of Wimpy Nodes）是 CMU 开发的低功耗键值存储系统。FawnKV 使用 CRAQ 作为其复制协议。

FawnKV 特点： - 节点为低功耗嵌入式设备（比如 Intel Atom） - 每个节点有 SSD 存储 - 读密集型工作负载（95% 读取）

为什么选择 CRAQ： - 读取分散：CRAQ 允许从任意节点读取，充分利用所有节点的计算资源 - 低延迟：本地读取延迟远低于跨节点 RPC - 适合弱处理器：CRAQ 的协议简单，适合低功耗 CPU

FawnKV 的实测数据（2009 年论文）： - 单节点读取：15,000 ops/s - 3 节点 CRAQ：45,000 ops/s（线性扩展） - 3 节点标准 Chain Replication：15,000 ops/s（受限于 Tail）

5.4 Microsoft Azure Storage

Azure Storage 是微软云存储服务的基础，处理全球数万亿对象的存储。Azure Storage 的复制层使用了 Chain Replication 的变体。

Azure Storage 架构： - 数据分区（Partition）映射到一个或多个 Extent（存储单元） - 每个 Extent 复制到 3 个 Extent Node，组成一条 Chain - Primary Extent Node 充当 Head，Secondary 和 Tertiary 充当 Middle 和 Tail

Azure 的优化： 1. 本地读取优化：允许从 Primary 读取（牺牲强一致性，换取低延迟） 2. Seal 机制：Extent 在达到大小上限后被 Seal（密封），之后变为只读，可以从任意副本读取 3. 快速恢复：使用 Extent 级别的复制，故障恢复粒度小

Azure Storage 处理的规模（根据公开资料）： - 每天处理数十万亿次请求 - 存储数百 EB 数据 - 写入吞吐达到 TB/s 级别

Chain Replication 在如此大规模下的成功应用，证明了其设计的有效性。

六、与 Raft/Paxos 的对比

6.1 一致性模型

Chain Replication： - 天然提供线性一致性（Linearizability） - 所有操作有全局确定顺序（Total Order） - 不需要额外机制（如 ReadIndex、Lease）来保证一致性读取

Raft/Paxos： - 基础协议提供日志一致性（Log Consistency） - 需要额外机制来提供线性一致性读取： - ReadIndex：向多数派确认当前 commit index - Lease Read：Leader 在租约期内直接读取 - 操作顺序由 Leader 的日志序列决定

6.2 吞吐量对比

假设 N = 5，每节点处理能力 C，网络延迟 d，处理延迟 p。

Chain Replication： - 写入吞吐：C / (d + p) × 并发数 - 读取吞吐：C（所有读取集中在 Tail）

Raft： - 写入吞吐：C / (⌈N/2⌉ × (d + p)) × 并发数 - 读取吞吐（Follower Read）：N × C

具体数值（d=1ms, p=0.5ms, C=100,000 ops/s）：

关键观察： 1. 写入吞吐类似：在高并发下，两者都能充分利用流水线 2. 读取吞吐差异大：Raft 的 Follower Read 可以水平扩展，Chain Replication 受限于 Tail

6.3 延迟对比

端到端延迟（单个操作）：

Chain Replication 的写入延迟更高，但读取延迟更低（直接本地访问 Tail，无需网络 RPC）。

在批量操作场景下（比如连续写入 1000 条记录），流水线效应使得平均延迟趋同。

6.4 故障检测与恢复

Chain Replication： - 需要外部配置管理器（Configuration Manager）检测故障 - 不同位置的节点故障有不同的恢复策略（见第七节） - 恢复过程可能需要重新排序或转移 pending 数据

Raft： - 内置故障检测（心跳超时） - Leader 故障触发选举，Follower 故障不影响可用性 - 恢复过程统一：新 Leader 发送日志条目，Follower 复制到本地

可用性对比： - Chain Replication：任意节点故障都会暂时中断服务（直到配置管理器介入） - Raft：只要多数派存活，服务持续可用

这是 Chain Replication 的主要劣势：故障恢复不是协议内置的，需要外部协调。

6.5 适用场景

优先选择 Chain Replication 的场景： - 写密集型工作负载，读取量较少 - 需要确定性全局顺序（比如日志复制） - 系统由外部配置管理（比如 Kubernetes Operator） - 追求实现简单性

优先选择 Raft/Paxos 的场景： - 读密集型工作负载 - 需要自主故障恢复（无外部协调） - 要求低延迟（多数派确认即可） - 需要动态成员变更

6.6 深入对比：吞吐量模型与延迟模型

为了更精确地理解 Chain Replication 与 Raft/Paxos 在性能上的差异，我们建立形式化的吞吐量模型和延迟模型进行定量分析。假设链/集群包含 N 个节点，每个节点的单向网络带宽容量为 C，节点间单次网络往返延迟为 d。

吞吐量模型

写入吞吐量方面，两者的瓶颈来源不同：

Chain Replication 写入吞吐量：T_write = C

在链式复制中，写入以 Pipeline 方式沿链传播。每个节点只需要向下一个节点转发数据，因此每个节点的出站带宽负载为 C。虽然总网络流量为 N * C（每个节点转发一次），但由于是流水线并行，单个节点不会成为带宽瓶颈，整体吞吐量等于单节点带宽 C。

Raft 写入吞吐量：T_write = C / ceil(N/2)

在 Raft 中，Leader 需要将日志条目并行发送给所有 Follower，并等待多数派（ceil(N/2) 个节点）确认。Leader 的出站带宽负载为 (N-1) * C（向所有 Follower 发送），因此 Leader 的带宽成为瓶颈。假设 Leader 的出站带宽为 B，则写入吞吐量为 B / (N-1)。在节点带宽相同的情况下，Raft 的写入吞吐量随节点数增加而下降。

读取吞吐量方面：

CRAQ 读取吞吐量：T_read = N * C （所有节点均可提供读服务）
Raft Follower Read 吞吐量：T_read = N * C （所有节点均可提供读服务，但存在 ReadIndex 开销）

CRAQ 和 Raft Follower Read 都能实现读取的水平扩展，理论上限相似。但 CRAQ 在大 Key 空间场景下的实际吞吐量更接近理论上限，因为大部分读取无需额外网络通信；而 Raft ReadIndex 每次读都需要一次与 Leader 的往返确认，实际吞吐量会打折扣。Raft 的 Lease Read 优化可以消除这一开销，但引入了对时钟精度的依赖。

延迟模型

写入延迟的差异是两种方案最显著的区别之一：

Chain Replication 写入延迟：L_write = N * d （顺序经过链上所有节点）
Raft 写入延迟：          L_write = d     （并行发送到所有 Follower，延迟取决于最慢的多数派成员）

Chain Replication 的写入延迟与链长度成正比，因为数据必须按顺序经过每个节点。在 5 节点链中，写入延迟为 5d；而 Raft 的写入延迟仅为 1 个 RTT（Leader 并行向所有 Follower 发送，只需等待最快的多数派响应）。这意味着在延迟敏感的场景下，Raft 具有明显优势。

读取延迟方面：

Chain Replication 读取延迟：L_read = d   （单次访问 Tail）
Raft ReadIndex 读取延迟：  L_read = 2d  （Follower → Leader 确认 + 本地读取）

Chain Replication 的读取延迟仅为一次网络往返（客户端直接访问 Tail），而 Raft ReadIndex 需要先向 Leader 确认当前 Commit Index，再在本地读取，延迟为两次网络往返。Raft Lease Read 可以将读取延迟降低到 d，但需要依赖时钟同步。

故障处理差异对比

从故障处理角度看，Raft/Paxos 的核心优势在于自治性：协议内部完成故障检测和 Leader 选举，无需外部组件参与。而 Chain Replication 依赖外部配置管理器，虽然恢复动作本身更简单（无需选举），但引入了对外部系统可用性的依赖，CM 本身的故障也需要额外处理（通常使用 Paxos/Raft 来实现高可用的 CM）。

七、故障恢复机制

7.1 故障检测

Chain Replication 依赖外部配置管理器（Configuration Manager, CM）进行故障检测。CM 的职责包括： 1. 维护链的当前配置（节点列表、顺序、Head/Tail 标识） 2. 通过心跳或租约（Lease）检测节点故障 3. 在检测到故障后，生成新的链配置 4. 通知所有节点和客户端新配置

CM 通常使用 Paxos 或 Raft 实现高可用（是的，Chain Replication 本身不解决配置一致性问题，需要借助共识协议）。

7.2 Head 节点故障

故障影响： - 无法接收新的写入 - 已进入 pipeline 的写入不受影响（继续传播到 Tail）

恢复步骤： 1. CM 检测到 Head 故障 2. 将 Head 的后继节点（原来的第二个节点）提升为新 Head 3. 更新客户端配置，将写请求发送到新 Head

代码示例：

func (cm *ConfigManager) handleHeadFailure(chain *Chain) {
    failedHead := chain.head
    newHead := failedHead.successor
    
    // 更新链配置
    chain.head = newHead
    newHead.predecessor = nil
    newHead.isHead = true
    
    // 通知所有客户端
    cm.broadcastNewConfig(chain)
    
    // 从成员列表中移除故障节点
    cm.removeNode(failedHead)
}

关键问题：已发送到故障 Head 但未转发的写入会丢失吗？

答：会丢失，但这符合语义。因为故障 Head 尚未将写入转发给后继，客户端也未收到 ACK，从客户端视角看，这次写入失败（超时），客户端会重试。

7.3 Tail 节点故障

故障影响： - 无法提供读服务 - 无法确认新的写入（无法发送 ACK） - 已在 pipeline 中的写入无法完成提交

恢复步骤： 1. CM 检测到 Tail 故障 2. 将 Tail 的前驱节点提升为新 Tail 3. 新 Tail 需要提交所有 pending 写入

代码示例：

func (cm *ConfigManager) handleTailFailure(chain *Chain) {
    failedTail := chain.tail
    newTail := failedTail.predecessor
    
    // 更新链配置
    chain.tail = newTail
    newTail.successor = nil
    newTail.isTail = true
    
    // 通知新 Tail 提交所有 pending 写入
    cm.sendCommitAll(newTail)
    
    // 更新客户端配置
    cm.broadcastNewConfig(chain)
    
    cm.removeNode(failedTail)
}

func (node *ChainNode) commitAllPending() {
    for _, op := range node.pendingWrites {
        // 将 pending 写入应用到 store
        node.store[op.key] = op.value
        
        // 回复客户端
        sendAckToClient(op.clientID, op.sequence)
        
        // 向前传播 ACK
        if node.predecessor != nil {
            sendCommitAck(node.predecessor, op.sequence)
        }
    }
    
    node.pendingWrites = nil
}

关键问题：新 Tail 如何知道哪些写入需要提交？

答：新 Tail 的 pendingWrites 队列包含了所有已传播到它的写入。由于链的顺序性，如果写入 W 到达了新 Tail，则 W 必然已经到达了链上所有前驱节点，可以安全提交。

7.4 中间节点故障

故障影响： - 打断 pipeline，阻止写入传播

恢复步骤： 1. CM 检测到中间节点 M 故障 2. 将 M 的前驱和后继直接连接，跳过 M 3. M 的前驱需要将 pending 写入重新发送给新后继

代码示例：

func (cm *ConfigManager) handleMiddleFailure(chain *Chain, failedNode *ChainNode) {
    pred := failedNode.predecessor
    succ := failedNode.successor
    
    // 重新连接链
    pred.successor = succ
    succ.predecessor = pred
    
    // 通知前驱：将 pending 写入重新发送给新后继
    cm.sendResync(pred, succ)
    
    cm.removeNode(failedNode)
}

func (node *ChainNode) resyncWithSuccessor(newSuccessor *ChainNode) {
    // 将所有 pending 写入重新发送
    for _, op := range node.pendingWrites {
        sendToNode(newSuccessor, op)
    }
}

关键问题：是否会重复发送写入？

答：可能会。假设写入 W 已经从 M 传播到后继，但 M 故障前未收到 ACK。M 的前驱会重新发送 W。后继节点需要去重（通过序列号）。

7.5 CRAQ 的故障恢复

CRAQ 的故障恢复与标准 Chain Replication 类似，但需要额外处理版本链：

Tail 故障： - 新 Tail 将所有 Dirty 版本标记为 Clean - 这可能导致短暂的一致性窗口问题：客户端可能读到旧版本（如果在 Clean 传播前查询）

中间节点故障： - 清理故障节点的版本链 - 后继节点可能缺少某些版本（需要从前驱补齐）

7.6 性能影响

故障恢复期间的性能影响：

对比 Raft： - Raft Leader 故障：写入中断，读取可能中断（取决于 Follower Read 配置），恢复时间 ~200-500ms（选举超时） - Raft Follower 故障：无影响（多数派仍然可用）

Chain Replication 的故障恢复时间通常更短（无需选举），但任意节点故障都会中断服务。

7.7 故障场景完整推演

为了更直观地理解 Chain Replication 的故障恢复过程，我们对三种典型故障场景进行详细的时间线推演。假设链的结构为 H → M1 → M2 → T，配置管理器（CM）通过心跳检测故障，心跳超时为 Δt。

场景一：Head 节点故障

时间线：
t0        客户端发送写入请求 W1 到 Head（H）
t1        H 接收 W1，写入本地存储，准备转发给 M1
t2        H 崩溃（W1 尚未转发给 M1）
t3        客户端等待 ACK 超时（客户端侧超时，通常 1-5s）
t4=t2+Δt  CM 检测到 H 心跳超时，确认 H 故障
t5        CM 将 M1 提升为新 Head，更新链配置为 M1 → M2 → T
t6        CM 通知客户端新的 Head 地址（或客户端从配置中心获取）
t7        客户端向新 Head（M1）重试写入 W1
t8        M1 接收 W1，开始正常的链式传播：M1 → M2 → T
t9        T 提交 W1，沿链回送 ACK
t10       客户端收到 W1 的 ACK，写入成功

关键要点：H 崩溃时尚未转发的写入 W1 不会丢失，因为客户端在超时后会重试。已经被 H 转发但尚未到达 T 的写入会继续沿链传播，不受影响。恢复的关键延迟在于 CM 的故障检测时间 Δt。

场景二：中间节点故障

时间线：
t0        H 接收写入 W1，转发给 M1
t1        M1 接收 W1，写入本地，转发给 M2
t2        M2 崩溃（W1 卡在 M1 的发送队列中）
t3        M1 检测到与 M2 的连接断开
t4=t2+Δt  CM 检测到 M2 心跳超时，确认 M2 故障
t5        CM 更新链配置为 H → M1 → T
t6        CM 通知 M1：你的新后继是 T
t7        CM 通知 T：你的新前驱是 M1
t8        M1 与 T 建立连接
t9        M1 将所有 pending 写入（包括 W1）重发给 T
t10       T 接收 W1，检查序列号，确认是新写入，执行提交
t11       T 沿链回送 ACK（现在直接回送给 M1）
t12       链恢复正常运行

关键要点：中间节点故障的恢复核心是”前驱直连后继”。M1 重发 pending 写入时，T 通过序列号进行去重，避免重复提交。如果 M2 在故障前已经将部分写入转发给了 T，T 会根据序列号识别并跳过这些重复写入。

场景三：Tail 节点故障

时间线：
t0        H 接收写入 W1、W2、W3（Pipeline 中有多个写入）
t1        W1 已到达 T 并提交，W2 在 M2 处，W3 在 M1 处
t2        T 崩溃（W1 的 ACK 尚未发送，W2、W3 在 Pipeline 中）
t3        M2 检测到与 T 的连接断开
t4=t2+Δt  CM 检测到 T 心跳超时，确认 T 故障
t5        CM 将 M2 提升为新 Tail，更新链配置为 H → M1 → M2
t6        M2 将自身所有 pending 写入标记为已提交
          （M2 上有 W2，标记为 committed）
t7        M2 向客户端发送 W2 的 ACK
t8        W3 从 M1 到达 M2（新 Tail），M2 提交 W3 并发送 ACK
t9        对于 W1：客户端可能已超时重试，新写入会被 M2 以序列号去重
t10       链恢复正常运行，M2 同时承担 Tail 的读取职责

关键要点：Tail 故障的恢复较为复杂，因为 Tail 同时承担读取和提交职责。新 Tail（M2）提升后必须立即提交所有本地 pending 的写入，因为这些写入已经被前驱节点持久化，只是尚未被旧 Tail 确认。恢复期间读取服务会短暂中断，直到新 Tail 就位。

故障恢复决策树

下面的流程图展示了配置管理器在检测到节点故障后的决策和恢复流程：

flowchart TD
    A[节点故障检测] --> B{故障节点位置?}
    B -->|Head| C[提升后继为新 Head]
    B -->|Middle| D[前驱直连后继]
    B -->|Tail| E[提升前驱为新 Tail]
    C --> F[客户端重定向到新 Head]
    C --> G[未转发的写入由客户端重试]
    D --> H[前驱重发 pending 写入]
    D --> I[后继按序列号去重]
    E --> J[新 Tail 提交所有 pending]
    E --> K[向客户端发送 ACK]
    F --> L[恢复写入服务]
    G --> L
    H --> M[恢复 Pipeline]
    I --> M
    J --> N[恢复读写服务]
    K --> N

该决策树清晰展示了三类故障的处理路径。无论故障发生在链的哪个位置，配置管理器都遵循”摘除故障节点、重新连接链、恢复未完成操作”的统一策略。三条路径最终都收敛到”恢复服务”这一目标，但各自的恢复动作和关注点不同：Head 故障关注客户端重定向，Middle 故障关注写入去重，Tail 故障关注 pending 提交。

中间节点故障的链重配置时序

以下时序图详细展示了中间节点故障时，配置管理器、前驱节点和后继节点之间的交互过程：

sequenceDiagram
    participant CM as 配置管理器
    participant P as 前驱节点
    participant M as 故障节点 M
    participant S as 后继节点
    
    Note over M: 节点 M 崩溃
    CM->>M: 心跳超时
    CM->>CM: 检测到 M 故障
    CM->>P: 更新后继为 S
    CM->>S: 更新前驱为 P
    P->>S: 重发 pending 写入
    S->>S: 按序列号去重
    Note over P,S: 链恢复正常
    P->>S: 新写入继续传播

该时序图揭示了中间节点故障恢复的核心交互流程。配置管理器在检测到故障后，分别通知前驱和后继节点更新各自的连接信息，使链绕过故障节点重新连通。前驱节点在获得新的后继地址后，会将所有尚未被确认的 pending 写入重发给后继节点，后继节点通过序列号机制确保幂等性，避免重复处理。

八、总结与展望

链式复制和 CRAQ 代表了分布式复制协议的另一条路径。与主流的 Raft/Paxos 相比，它们通过简单的链式结构，在特定场景下实现了更高的吞吐量和更简单的实现。

8.1 核心要点回顾

1. 链式复制的强一致性：通过 Head 写入、Tail 读取的架构，自然满足线性一致性，无需复杂的共识协议。

2. 流水线并行：链式传播允许多个写操作同时在链的不同位置处理，写入吞吐量与链长度无关。

3. CRAQ 的创新：通过 Clean/Dirty 版本标记和向 Tail 查询的机制，允许任意节点提供读服务，突破了原始链式复制的读取瓶颈。

4. 工业界应用：HDFS、Azure Storage、Corfu 等系统的成功应用，证明了链式复制在大规模生产环境中的价值。

5. 权衡取舍：链式复制牺牲了故障恢复的自主性和读取的水平扩展性（标准版本），换取了实现简单性和写入高吞吐。

8.2 选型建议

选择链式复制/CRAQ 的条件： - 工作负载为写密集或读写均衡 - 系统已有外部配置管理组件（如 ZooKeeper、etcd） - 追求实现简单，代码库较小 - 需要确定性的全局操作顺序

选择 Raft/Paxos 的条件： - 工作负载为读密集 - 需要自主故障恢复，无外部依赖 - 要求低延迟（多数派延迟优于全链延迟） - 需要频繁的成员变更

8.3 未来方向

链式复制的研究仍在继续，一些有趣的方向包括：

1. 混合架构：结合链式复制的写入路径和 Raft 的读取路径，充分利用两者优势。

2. 自适应链长度：根据负载动态调整链长度，在延迟和吞吐之间取得平衡。

3. 跨数据中心链式复制：在地理分布式环境中，如何优化链的拓扑结构以减少跨区域延迟。

4. CRAQ 的进一步优化：减少版本查询频率，比如通过 Bloom Filter 或版本预测机制。

5. 与新硬件结合：利用 RDMA、持久内存（Persistent Memory）等新硬件，进一步提升链式复制的性能。

链式复制提醒我们，分布式系统设计没有银弹。不同的架构选择带来不同的权衡，深入理解各种复制协议的内在机制，才能在实际系统中做出最优决策。

参考文献

1. Robbert van Renesse and Fred B. Schneider. 2004. Chain Replication for Supporting High Throughput and Availability. In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’04).

2. Jeff Terrace and Michael J. Freedman. 2009. Object Storage on CRAQ: High-throughput chain replication for read-mostly workloads. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC ’09).

3. Konstantin Shvachko, Hairong Kuang, Sanjay Radia, and Robert Chansler. 2010. The Hadoop Distributed File System. In Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies (MSST ’10).

4. Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobber, Michael Wei, and John D. Davis. 2013. CORFU: A Shared Log Design for Flash Clusters. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’13).

5. David G. Andersen, Jason Franklin, Michael Kaminsky, Amar Phanishayee, Lawrence Tan, and Vijay Vasudevan. 2009. FAWN: A Fast Array of Wimpy Nodes. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (SOSP ’09).

6. Brad Calder et al. 2011. Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency. In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP ’11).

7. Diego Ongaro and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC ’14).

上一篇：无主复制 | 下一篇：线性一致性的实现