🌑

☀️

Hi Folks.

Home Archives Works About Links Email

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

论文来源: 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 为例，分析一个写操作需要多少时间：

时间线:
─────────────────────────────────────────────────────────────────→

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

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

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

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

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

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

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 恢复

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

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

3.3 整体架构图

                        ┌─────────────┐
                        │  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 都不同 → 可交换
否则 → 不可交换，走慢速路径

详细流程

时间线（假设 f=1，即 1 个 Witness）:
─────────────────────────────────────────────────────────────→

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

关键点：

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

为什么这样做是安全的？

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

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

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

触发条件

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

详细流程

时间线:
─────────────────────────────────────────────────────────────→

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 的可交换性检查实现

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 恢复的挑战

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

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

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

6.2 两阶段恢复流程

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 中，它们必然是可交换的。

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，跳过已执行的请求

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 的场景

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

8.2 不适合 CURP 的场景

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

9 总结

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

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

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

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

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

10 本系列文章规划

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

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

参考资料

论文：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

技术 — 2026年7月21日

View / Make Comments

Search

Made with ❤ and at Earth.