CURP共识算法详解-00-CURP理论

项目 › tiny-distributed-kv
, ,

论文来源: Exploiting Commutativity For Practical Fast Replication
作者: Seo Jin Park, John Ousterhout (Stanford University)
会议: NSDI ‘19

本系列文章记录我基于现有 Raft 实现扩展为 CURP 共识协议的过程。这一节先介绍 CURP 的核心理论，帮助读者理解为什么 CURP 能够实现 1 RTT 的写操作延迟。

1 为什么需要 CURP？

在深入 CURP 的细节之前，我们先思考一个问题：为什么传统复制协议的写延迟至少是 2 RTT？

1.1 分布式系统的 CAP 权衡

分布式系统设计中最著名的原则之一是 CAP 定理：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）中的两项。

对于需要强一致性的系统（如金融交易、配置管理等），我们通常选择 CP 架构，牺牲部分可用性来保证一致性。Raft、Paxos、ZAB 等共识协议就是这类系统的代表。

但强一致性的代价是什么？是延迟。

1.2 传统复制的延迟瓶颈

让我们以 Raft 为例，分析一个写操作需要多少时间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间线:
─────────────────────────────────────────────────────────────────→

Client                Leader                Follower
  │                     │                      │
  │─── 写请求 ─────────→│                      │
  │                     │                      │
  │                     │─── AppendEntries ───→│
  │                     │                      │
  │                     │←─── ACK ────────────│  (等待多数派确认)
  │                     │                      │
  │                     │─── 提交并执行 ──────→│
  │                     │                      │
  │←─── 响应客户端 ─────│                      │

总延迟 = Client→Leader (1 RTT) + Leader→Follower (1 RTT) = 2 RTT

这里的瓶颈在于：必须先确定操作的顺序（排序），才能执行并响应客户端。

为什么必须先排序？因为：

  1. 多个客户端可能并发发起写操作
  2. 这些操作可能作用于相同的数据
  3. 不同的执行顺序可能导致不同的最终状态
  4. 为了保证所有副本最终状态一致，必须先达成顺序共识

这就是传统复制协议的核心约束：排序和持久化是耦合的。

1.3 2 RTT 能接受吗？

这取决于应用场景：

场景 RTT 要求 传统复制是否满足
跨数据中心（100ms RTT） 写延迟 200ms+ ❌ 用户可感知延迟
同数据中心（1ms RTT） 写延迟 2ms+ ✅ 可接受
内存数据库（µs 级） 写延迟受限于 RTT ❌ 性能瓶颈

对于需要跨数据中心部署或对延迟敏感的应用，2 RTT 的代价是昂贵的。这正是 CURP 试图解决的问题。

2 CURP 的核心洞察

CURP（Consistent Unordered Replication Protocol）的名字本身就揭示了其核心思想：Consistent（一致） + Unordered（无序）。

2.1 一个关键问题：顺序真的那么重要吗？

让我们重新审视排序的必要性。考虑以下两个操作：

1
2
操作 A: SET key1 = value1
操作 B: SET key2 = value2

问题：A 和 B 哪个先执行，结果有区别吗？

答案：没有区别。因为 A 和 B 操作的是不同的 key，它们是可交换的（commutative）。

再考虑：

1
2
操作 A: SET key1 = value1
操作 B: SET key1 = value2

问题：A 和 B 哪个先执行，结果有区别吗？

答案：有区别。最终值取决于执行顺序。它们是不可交换的。

CURP 的核心洞察：

如果操作是可交换的，那么执行顺序就不重要。如果顺序不重要，我们就不需要等待排序完成。

2.2 分离持久性与排序

传统复制协议中，持久化依赖于排序：

1
传统流程：客户端请求 → 排序 → 复制（持久化）→ 执行 → 响应

CURP 将持久化和排序解耦：

1
2
3
CURP 流程：客户端请求 → 持久化（Witness） + 执行（Master）→ 响应
                              ↓
                        异步排序和复制到 Backup

关键点：持久化可以在排序之前完成！

这样一来，客户端只需要等待 1 RTT（请求到达 Master 和 Witness），就可以收到响应。

3 CURP 架构详解

CURP 在传统 primary-backup 架构基础上引入了一个新角色：Witness（见证者）。

3.1 为什么需要 Witness？

问题：如果 Master 在执行操作后、同步到 Backup 前崩溃，数据会丢失吗？

传统复制：会丢失。所以必须先同步到 Backup 再响应。

CURP 的解决方案：让 Witness 记录操作。Witness 是一个轻量级的存储节点：

  • 只存储操作的元数据和请求数据
  • 不执行操作
  • 不需要维护完整的数据副本

Witness 的成本远低于 Backup，但提供了等价的持久性保证。

3.2 节点角色与职责

角色 数量 存储内容 职责
Master 1 完整数据 接收请求、执行操作、协调复制
Backup f 完整数据 存储有序数据，用于恢复和服务读请求
Witness f 请求记录 临时存储未同步请求，保证持久性

为什么需要 f 个 Witness？

容错能力的要求：系统需要容忍 f 个任意节点故障。

  • 如果只有 f 个 Backup（无 Witness），Master 崩溃后可以从 Backup 恢复，但如果某个 Backup 也同时故障，可能丢失数据
  • 增加 f 个 Witness 后，即使 Master 和部分 Backup 同时故障，仍然可以从剩余 Backup + Witness 恢复
1
2
3
4
5
6
7
8
9
容错配置示例（f=1）:
─────────────────────────────────────
Master (1) + Backup (1) + Witness (1)
可容忍任意 1 个节点故障

容错配置示例（f=2）:
─────────────────────────────────────
Master (1) + Backup (2) + Witness (2)
可容忍任意 2 个节点故障

3.3 整体架构图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
                        ┌─────────────┐
                        │  Witness 1  │
                        └─────────────┘
                              ↑
                        ┌─────────────┐
                        │  Witness f  │  ← 轻量级，只存请求
                        └─────────────┘
                              ↑
┌──────────────────────────────────────────────────────────┐
│                        Client                            │
└──────────────────────────────────────────────────────────┘
          │                               │
          ↓                               ↓
    ┌──────────┐              ┌──────────────┐
    │  Master  │──────────────│   Backup 1   │
    │ (执行)   │   异步同步    └──────────────┘
    └──────────┘              ┌──────────────┐
                              │   Backup f   │  ← 完整数据副本
                              └──────────────┘

快速路径：Client → Master + Witness（并行，1 RTT）
异步路径：Master → Backup（后台进行，不影响客户端）

4 写操作流程

4.1 快速路径（Fast Path）- 1 RTT

快速路径是 CURP 的核心优化，实现了 1 RTT 的写操作。

前置条件

操作必须与所有未同步的操作可交换。对于 KV 存储：

  • 新操作的 key 与所有未同步操作的 key 都不同 → 可交换
  • 否则 → 不可交换，走慢速路径

详细流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
时间线（假设 f=1，即 1 个 Witness）:
─────────────────────────────────────────────────────────────→

Client                    Master                   Witness
  │                         │                         │
  │──── 1. 写请求 ─────────→│                         │
  │     (SET key1=val1)     │                         │
  │                         │                         │
  │──── 2. 记录请求 ─────────────────────────────────→│
  │     (并行发送)           │                         │
  │                         │                         │
  │                         │── 3. 检查可交换性 ─────→│
  │                         │   (key1 不在记录中)      │
  │                         │                         │
  │                         │←── ACCEPTED ────────────│
  │                         │                         │
  │                         │── 4. 推测执行 ──────────→│ (本地执行)
  │                         │   key1 = val1           │
  │                         │                         │
  │←──── 5. 响应 ───────────│                         │
  │     "写入成功"           │                         │
  │                         │                         │
  │  ✓ 客户端收到响应        │                         │
  │                         │                         │
  │                         │── 6. 异步同步 ─────────→│ Backup
  │                         │   (后台进行)             │

关键点：

  1. 并行发送：客户端同时向 Master 和所有 Witness 发送请求
  2. Witness 检查：Witness 检查新请求是否与已存储的请求可交换
  3. 推测执行：Master 不等待 Backup 同步，直接执行并响应
  4. 条件完成：客户端收到 Master 响应 + 所有 Witness ACCEPTED = 操作完成

为什么这样做是安全的？

  1. 持久性保证：请求已记录在 f 个 Witness 中，即使 Master 崩溃也能恢复
  2. 一致性保证：可交换操作的执行顺序不影响最终结果
  3. 容错保证：f 个 Witness + f 个 Backup 可以恢复任意 f 个节点的故障

4.2 慢速路径（Slow Path）- 2 RTT

当操作不可交换时，CURP 退回到类似传统复制的 2 RTT 流程。

触发条件

  1. Witness 拒绝：新请求与已存储请求冲突（操作相同 key）
  2. 空间不足：Witness 存储空间已满
  3. Master 检测到冲突：新请求与 Master 本地未同步的操作冲突

详细流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
时间线:
─────────────────────────────────────────────────────────────→

Client                    Master                   Backup
  │                         │                         │
  │──── 1. 写请求 ─────────→│                         │
  │     (SET key1=val2)     │                         │
  │                         │                         │
  │                         │── 检测到 key1 未同步 ───│
  │                         │                         │
  │←──── 2. NEED_SYNC ──────│                         │
  │     (触发慢路径)         │                         │
  │                         │                         │
  │──── 3. Sync 请求 ───────→│                         │
  │                         │                         │
  │                         │── 4. 同步到 Backup ────→│
  │                         │                         │
  │                         │←── 5. ACK ─────────────│
  │                         │                         │
  │                         │── 6. 执行操作 ─────────→│
  │                         │                         │
  │←──── 7. 响应 ───────────│                         │
  │                         │                         │

慢路径的性能影响

慢路径虽然需要 2 RTT，但在实际系统中：

  • 如果应用具有良好的访问局部性（热点 key 少），大部分操作走快速路径
  • 论文数据显示，快速路径成功率可达 90%+

5 可交换性深入分析

可交换性是 CURP 的核心概念，理解它对于实现和优化都至关重要。

5.1 什么是可交换性？

两个操作 A 和 B 是可交换的，当且仅当：无论先执行 A 还是先执行 B，最终状态都相同。

KV 存储中的可交换性

对于简单的 KV 存储（只支持 GET/SET）：

操作 A 操作 B 可交换？ 原因
SET k1=v1 SET k2=v2 ✅ 是 不同 key
SET k1=v1 GET k2 ✅ 是 不同 key
SET k1=v1 SET k1=v2 ❌ 否 相同 key，结果取决于顺序
SET k1=v1 GET k1 ❌ 否 相同 key，GET 返回值取决于顺序
GET k1 GET k1 ✅ 是 只读操作总是可交换

更复杂的场景

对于支持更多操作的 KV 存储：

操作类型 可交换条件
INCR key 与任何同 key 操作都不可交换
LPUSH key value 与任何同 key 操作都不可交换
SADD key member 与同 key 的 SADD 可交换（集合幂等）

实现提示： 简单起见，教学版实现可以采用最保守的策略——只有操作不同 key 才认为可交换。

5.2 Witness 的可交换性检查实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Witness {
private:
    // 存储已接受请求的 key 集合
    std::unordered_set<std::string> recorded_keys_;
    
    // 存储完整的请求记录
    std::unordered_map<std::string, WitnessRecord> records_;
    
public:
    RecordResult record(const std::string& key, 
                        uint64_t rpc_id,
                        const std::vector<uint8_t>& request_data) {
        std::lock_guard<std::mutex> lock(mtx_);
        
        // 可交换性检查：key 是否已被记录？
        if (recorded_keys_.count(key) > 0) {
            // 存在冲突，走慢路径
            return RecordResult::REJECTED_NOT_COMMUTATIVE;
        }
        
        // 接受请求
        recorded_keys_.insert(key);
        records_[key] = WitnessRecord{rpc_id, key, request_data, now()};
        return RecordResult::ACCEPTED;
    }
};

注意： 这是一个简化实现。论文中的完整实现使用 hash 分桶来提高并发性能。

6 恢复机制

当 Master 崩溃后，需要从 Backup 和 Witness 恢复数据。CURP 的恢复过程保证了不丢失任何已确认的写操作。

6.1 恢复的挑战

恢复面临的核心问题是：数据分散在多个地方

  1. Backup：存储有序的、已同步的数据
  2. Witness：存储无序的、未同步的请求
  3. Master 本地：已执行但未同步的数据（崩溃后丢失）

问题： 如何确保恢复后的数据包含所有已确认的操作？

6.2 两阶段恢复流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Phase 1: 从 Backup 恢复有序数据
───────────────────────────────────
New Master ← Backup (复制最新的有序数据)

这步复用传统 primary-backup 的恢复机制。


Phase 2: 从 Witness 重放无序请求
───────────────────────────────────
1. 选择一个可用的 Witness
2. 停止该 Witness 接收新请求
3. 获取所有存储的请求
4. 重放请求（顺序不重要，因为可交换）
5. 同步到 Backup
6. 重置 Witness

6.3 为什么重放顺序不重要？

因为 Witness 只接受可交换的操作。如果两个操作记录在同一个 Witness 中，它们必然是可交换的。

1
2
3
4
5
6
Witness 中记录的请求：
- SET key1 = v1
- SET key2 = v2
- SET key3 = v3

重放顺序可以是任意排列，最终结果相同。

6.4 防止重复执行

问题： 某个请求可能已经同步到 Backup，但 Witness 中还有记录。如果重放会导致重复执行。

解决方案： RIFL（Reusable Infrastructure for Linearizability）

每个请求分配唯一的 RPC ID：

  • 客户端生成递增的 RPC ID
  • Master 记录已执行的 RPC ID
  • 恢复时检查 RPC ID，跳过已执行的请求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool CurpMaster::alreadyExecuted(uint64_t rpc_id) {
    return executed_rpc_ids_.count(rpc_id) > 0;
}

void CurpMaster::replayFromWitness(Witness* witness) {
    auto records = witness->getRecoveryData();
    
    for (const auto& record : records) {
        if (!alreadyExecuted(record.rpc_id)) {
            execute(record.request);
            executed_rpc_ids_.insert(record.rpc_id);
        }
    }
}

7 与 Raft 的对比

CURP 和 Raft 都提供线性一致性，但设计理念不同。

7.1 设计理念对比

方面 Raft CURP
核心思想 先排序，再执行 先执行，排序延迟
延迟优化 优化故障恢复时间 优化正常操作延迟
适用场景 通用 操作可判断可交换性

7.2 性能对比

指标 Raft CURP
写延迟（正常） 2 RTT 1 RTT（90%+ 情况）
写延迟（冲突） 2 RTT 2 RTT
读延迟 1 RTT（从 Leader） 1 RTT（从 Master）或更低（从 Backup）
节点数量 2f+1 2f+1（f Backups + f Witnesses）

7.3 实现复杂度

CURP 相比 Raft 增加了：

  • Witness 组件
  • 可交换性检查逻辑
  • 推测执行管理
  • 更复杂的恢复流程

但对于 KV 存储这类天然支持可交换性检查的系统，这些额外复杂度是值得的。

8 适用场景分析

CURP 不是银弹，它有特定的适用场景。

8.1 适合 CURP 的场景

  1. KV 存储：天然支持 key 级别的可交换性检查
  2. 高并发写：大量写操作可以并行进行
  3. 跨数据中心部署：RTT 较大时收益明显
  4. 内存数据库：性能瓶颈在 RTT 而非磁盘 I/O

8.2 不适合 CURP 的场景

  1. 热点 key 频繁更新：大量操作冲突，走慢路径
  2. 复杂事务：难以判断可交换性
  3. 读多写少：优化写延迟收益有限
  4. 磁盘数据库：磁盘延迟主导，RTT 优化收益有限

9 总结

CURP 的核心贡献是发现了一个被忽视的机会：

传统复制协议假设所有操作都需要排序，但实际上很多操作是可交换的，不需要等待排序。

通过引入 Witness 节点和推测执行机制，CURP 实现了：

  • 1 RTT 的写延迟（对于可交换操作）
  • 线性一致性（不牺牲正确性）
  • 容错能力（支持 f 个节点故障）

对于 KV 存储这类系统，CURP 是一个值得考虑的优化方案。

10 本系列文章规划

接下来的文章将介绍 CURP 的具体实现：

  1. 实现计划：基于现有 Raft 代码扩展为 CURP
  2. 测试框架：如何验证 CURP 的正确性和性能
  3. Witness 实现：详细讲解 Witness 的设计和实现
  4. CurpMaster 实现：推测执行和异步同步
  5. 恢复机制实现：崩溃恢复的正确性保证

参考资料

  • 论文：Exploiting Commutativity For Practical Fast Replication, NSDI ‘19
  • 论文 PDF：doc/curp-nsdi19.pdf
  • 论文文本：doc/curp-nsdi19.txt
  • NSDI ‘19 视频：https://www.usenix.org/conference/nsdi19/presentation/park
  • Raft 论文：In Search of an Understandable Consensus Algorithm, ATC ‘14