共识问题概述
分布式共识是指在分布式系统中，多个节点就某个值或决策达成一致的过程。由于网络延迟、节点故障等原因，达成共识是一个核心挑战。
📐 FLP 不可能定理
在异步网络环境中，即使只有一个节点可能失效，也无法保证在有限时间内达成确定性共识。
共识算法发展时间线
1989
Paxos
Leslie Lamport 提出
1999
PBFT
Castro & Liskov
2008
PoW
比特币区块链
2013
Raft
Ousterhout & Ong
2014
PoS
以太坊 2.0
故障类型
💥 崩溃故障
节点停止响应，不再发送消息
Crash Failure
🎭 拜占庭故障
节点可能发送错误或恶意消息
Byzantine Failure
📭 遗漏故障
消息丢失或延迟到达
Omission Failure
Paxos 算法
Paxos 是由 Leslie Lamport 在 1989 年提出的分布式共识算法，被譽为最经典的共识算法。它允许在存在节点故障的分布式系统中达成一致。
sequenceDiagram
participant P as Proposer
participant A as Acceptor
participant L as Learner
P->>A: Phase 1a: Prepare(n)
A->>P: Phase 1b: Promise(n, acceptedValue)
P->>A: Phase 2a: Accept(n, value)
A->>P: Phase 2b: Accepted(n, value)
A->>L: Learn(value)
Note over P,L: 两阶段提交
阶段 1: 准备阶段
- Proposer 提出编号为 n 的提案
- 向多数派 Acceptor 发送 Prepare 请求
- Acceptor 回复 Promise，承诺不接受编号小于 n 的提案
阶段 2: 接受阶段
- Proposer 收到多数派的 Promise 后
- 发送 Accept 请求，包含提案值
- Acceptor 接受后，提案被批准
Paxos 安全性保证
1. 只有被提出的值才能被批准
2. 只有一个值能被批准
3. 一个值被批准后，Learner 才能学习到
2. 只有一个值能被批准
3. 一个值被批准后，Learner 才能学习到
Raft 算法
Raft 是一种易于理解的分布式共识算法，由 Stanford 大学于 2013 年提出。它将共识问题分解为三个子问题：领导者选举、日志复制和安全性。
Raft 节点状态转换
Follower
被动响应
⇄
Candidate
请求投票
→
Leader
管理日志
所有节点从 Follower 开始，超时后成为 Candidate，获得多数票后成为 Leader
sequenceDiagram
participant L as Leader
participant F1 as Follower1
participant F2 as Follower2
participant F3 as Follower3
L->>F1: AppendEntries(log, term)
L->>F2: AppendEntries(log, term)
L->>F3: AppendEntries(log, term)
F1-->>L: Success
F2-->>L: Success
Note over L,F3: 多数派确认
L->>L: Commit entry
L->>F1: Commit index
L->>F2: Commit index
L->>F3: Commit index
Note over L,F3: 日志复制完成
Raft 核心机制
| 机制 | 说明 | 关键参数 |
|---|---|---|
| 领导者选举 | 超时后成为 Candidate，请求投票 | 选举超时：150-300ms |
| 日志复制 | Leader 向 Follower 复制日志 | 心跳间隔：50ms |
| 安全性保证 | Leader 包含所有已提交日志 | Leader 完整性 |
PBFT 算法
实用拜占庭容错 (Practical Byzantine Fault Tolerance) 算法由 Castro 和 Liskov 于 1999 年提出，能够容忍最多 f 个拜占庭节点 (总节点数 n ≥ 3f + 1)。
sequenceDiagram
participant C as Client
participant P as Primary
participant R1 as Replica1
participant R2 as Replica2
participant R3 as Replica3
C->>P: Request(m)
P->>R1: Pre-Prepare(m, n, d)
P->>R2: Pre-Prepare(m, n, d)
P->>R3: Pre-Prepare(m, n, d)
R1->>R2: Prepare(n, d, i)
R1->>R3: Prepare(n, d, i)
R2->>R1: Prepare(n, d, i)
R2->>R3: Prepare(n, d, i)
R3->>R1: Prepare(n, d, i)
R3->>R2: Prepare(n, d, i)
Note over R1,R3: 2f+1 个 Prepare
R1->>R2: Commit(n, d, i)
R1->>R3: Commit(n, d, i)
R2->>R1: Commit(n, d, i)
R2->>R3: Commit(n, d, i)
R3->>R1: Commit(n, d, i)
R3->>R2: Commit(n, d, i)
Note over R1,R3: 2f+1 个 Commit
R1-->>C: Reply(r)
Note over C,R3: 三阶段提交
阶段 1: Pre-Prepare
- Client 发送请求到 Primary
- Primary 分配序列号 n
- 广播 Pre-Prepare 消息给所有 Replica
阶段 2: Prepare
- Replica 验证 Pre-Prepare
- 广播 Prepare 消息
- 收到 2f+1 个 Prepare 后进入下一阶段
阶段 3: Commit
- 广播 Commit 消息
- 收到 2f+1 个 Commit 后执行
- 返回结果给 Client
PoW 工作量证明
PoW (Proof of Work) 是比特币使用的共识机制，要求节点通过计算密集型任务来竞争记账权，防止恶意攻击。
⚠️ 优缺点分析
优点: 安全性高，抗攻击能力强
缺点: 能源消耗大，交易确认慢，存在算力集中风险
缺点: 能源消耗大，交易确认慢，存在算力集中风险
PoW 难度目标
SHA256(SHA256(block_header)) < target
难度调整：每 2016 个区块调整一次，目标出块时间 10 分钟
难度调整：每 2016 个区块调整一次，目标出块时间 10 分钟
PoS 权益证明
PoS (Proof of Stake) 通过持有代币的数量和时间来选择验证者，相比 PoW 更节能高效。
| 特性 | PoW | PoS |
|---|---|---|
| 选择机制 | 算力竞争 | 持币质押 |
| 能源消耗 | 高 | 低 |
| 交易速度 | 慢 (比特币 7 TPS) | 快 (以太坊 2.0 100000+ TPS) |
| 安全性 | 51% 算力攻击 | 51% 持币攻击 |
| 代表项目 | 比特币、莱特币 | 以太坊 2.0、Cardano |
算法对比与选择
| 算法 | 故障容忍 | 通信复杂度 | 确认延迟 | 应用场景 |
|---|---|---|---|---|
| Paxos | 崩溃故障 | O(n) | 低 | Chubby, ZooKeeper |
| Raft | 崩溃故障 | O(n) | 低 | etcd, Consul, TiKV |
| PBFT | 拜占庭故障 | O(n²) | 中 | 联盟链，Hyperledger |
| PoW | 拜占庭故障 | O(1) | 高 (10 分钟) | 比特币，公有链 |
| PoS | 拜占庭故障 | O(1) | 中 (12 秒) | 以太坊 2.0 |
| DPoS | 拜占庭故障 | O(n) | 低 (3 秒) | EOS, TRON |
✅ 算法选择指南
- 许可链/内部系统: 选择 Raft 或 PBFT，性能好，延迟低
- 公有链: 选择 PoW 或 PoS，抗攻击，去中心化
- 高吞吐场景: 考虑 DPoS 或 PoS 变体
- 强一致性要求: 选择 Paxos/Raft 系列
- 弱一致性可接受: 考虑 Gossip 协议