知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 共识基础与 Paxos ## 什么是共识问题 在分布式系统中,**共识(Consensus)** 是指多个节点就某个值达成一致的过程。 ### 为什么需要共识?  *图:没有共识协议时三个节点都自称主节点,出现脑裂* ``` 场景:分布式数据库的主节点选举 ┌─────────┐ ┌─────────┐ ┌─────────┐ │ Node A │ │ Node B │ │ Node C │ │ "我是主" │ │ "我是主" │ │ "我是主" │ └─────────┘ └─────────┘ └─────────┘ 问题:如果没有共识协议 - 多个节点都认为自己是主节点(脑裂) - 数据写入冲突 - 系统不一致 共识协议解决: - 所有节点就"谁是主节点"达成一致 - 即使部分节点故障也能正常工作 ``` ### 共识问题的定义 一个正确的共识算法必须满足以下条件:  *图:共识算法三大属性:协定性、有效性、终止性* ``` ┌─────────────────────────────────────────────────────────────┐ │ 共识算法三大属性 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 1. 协定性(Agreement) │ │ 所有正确的节点必须就同一个值达成一致 │ │ │ │ 2. 有效性(Validity) │ │ 达成共识的值必须是某个节点提议的值 │ │ │ │ 3. 终止性(Termination) │ │ 所有正确的节点最终都会做出决定 │ │ │ └─────────────────────────────────────────────────────────────┘ ``` ## FLP 不可能定理 ### 定理内容 > 在一个**异步**系统中,即使只有**一个节点**可能发生故障(崩溃故障),也**不存在**一个能保证终止的确定性共识算法。 — Fischer, Lynch, and Paterson, 1985 ### 理解 FLP  *图:异步系统无法区分节点崩溃与网络延迟* ``` 异步系统的特点: ┌─────────────────────────────────────────────────────────────┐ │ 1. 消息延迟没有上界 │ │ 2. 进程执行速度没有下界 │ │ 3. 无法区分"节点崩溃"和"网络延迟" │ └─────────────────────────────────────────────────────────────┘ 困境示例: Node A 发送消息给 Node B,长时间没有收到回复 可能情况: 1. Node B 已经崩溃 2. 消息在网络中延迟 3. Node B 处理很慢 4. 回复消息在网络中延迟 Node A 无法区分这些情况! ``` ### FLP 的意义 FLP 告诉我们:**理论上完美的共识算法不存在**。 但实践中,我们通过以下方式绕过: | 方法 | 说明 | |------|------| | 随机化 | 引入随机性打破对称(如 Raft 的随机超时) | | 超时机制 | 假设部分同步(大部分时间消息延迟有界) | | 故障检测器 | 使用不完美的故障检测器 | 共识问题的工程实践:  *图:FLP 说纯异步不保证终止,工程用随机超时与多数派* ``` 理论 vs 工程的分界线: FLP (1985): ┌────────────────────────────────────────────┐ │ "在纯异步系统中,确定性共识算法无法保证终止" │ └────────────────────────────────────────────┘ 理论结论:完美的共识算法不存在 │ ↓ 工程实践(Paxos / Raft): ┌────────────────────────────────────────────┐ │ 引入随机超时 → 打破活锁(Raft 的核心创新) │ │ 假设部分同步 → 实际网络大多时候有界 │ │ 多数派投票 → 容忍 f 个节点故障 │ └────────────────────────────────────────────┘ 工程结论:99.9% 的请求能在几 ms~几 s 达成共识 两者不矛盾: FLP 说"不能保证"在任意网络延迟下都终止 Raft/Paxos 说"实际上"网络延迟有95分位上限,在此范围内能保证终止 极端情况(网络无限延迟)才活锁,概率极低 ```  ## 拜占庭容错(BFT) ### 拜占庭将军问题  *图:叛徒将军对 A、C 发送矛盾消息,忠诚将军如何一致* ``` 背景:多个拜占庭将军围攻一座城市,需要通过信使通信 问题:部分将军可能是叛徒,会发送虚假信息 ┌─────────┐ ┌─────────┐ │将军 A │ │将军 B │ │(忠诚) │←───→│(叛徒) │ └────┬────┘ └────┬────┘ │ │ │ ┌───────┐ │ └───→│将军 C │←─┘ │(忠诚) │ └───────┘ 叛徒将军 B 可能: - 对 A 说"进攻" - 对 C 说"撤退" 忠诚将军如何达成一致? ``` ### 拜占庭容错 vs 崩溃容错 | 类型 | 故障模式 | 代表算法 | 容错能力 | |------|----------|----------|----------| | **CFT** (Crash Fault Tolerant) | 节点停止工作 | Paxos, Raft | n ≥ 2f + 1 | | **BFT** (Byzantine Fault Tolerant) | 节点可能恶意行为 | PBFT | n ≥ 3f + 1 | ``` CFT: 需要 2f + 1 个节点容忍 f 个崩溃故障 例:5 个节点可以容忍 2 个崩溃 BFT: 需要 3f + 1 个节点容忍 f 个拜占庭故障 例:4 个节点可以容忍 1 个恶意节点 ``` ## Paxos 算法 ### 算法背景 Paxos 由 Leslie Lamport 在 1990 年提出,是分布式共识算法的奠基之作。 > "Paxos 算法可能是世界上最难理解的共识算法" > — 业界普遍看法 ### 角色定义  *图:Paxos 三种角色:提议者、接受者、学习者* ``` ┌─────────────────────────────────────────────────────────────┐ │ Paxos 三种角色 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ Proposer(提议者) │ │ - 发起提议 │ │ - 可以有多个 Proposer │ │ │ │ Acceptor(接受者) │ │ - 接受或拒绝提议 │ │ - 形成多数派决定结果 │ │ │ │ Learner(学习者) │ │ - 学习已经达成共识的值 │ │ - 不参与投票过程 │ │ │ └─────────────────────────────────────────────────────────────┘ 注:同一个节点可以同时扮演多种角色 ``` ### Basic Paxos 流程  *图:Paxos 两阶段四步:准备、承诺、接受、确认* ``` Phase 1a: Prepare(准备阶段) ──────────────────────────────────────── Proposer 选择一个提案编号 n,发送 Prepare(n) 给所有 Acceptor Proposer Acceptors │ ┌─────┬─────┬─────┐ │───Prepare(n=1)───→ │A1 │A2 │A3 │ │ └─────┴─────┴─────┘ Phase 1b: Promise(承诺阶段) ──────────────────────────────────────── Acceptor 收到 Prepare(n): - 如果 n > 之前见过的最大编号,承诺不再接受编号小于 n 的提案 - 返回之前接受过的最大编号提案(如果有) Proposer Acceptors │ ┌─────┬─────┬─────┐ │←──Promise(n=1)─────│A1 │A2 │A3 │ │ [无历史提案] └─────┴─────┴─────┘ Phase 2a: Accept(接受阶段) ──────────────────────────────────────── Proposer 收到多数派的 Promise 后,发送 Accept(n, value) - 如果收到的 Promise 中有已接受的提案,选择编号最大的提案值 - 否则使用自己的提案值 Proposer Acceptors │ ┌─────┬─────┬─────┐ │──Accept(n=1,v="X")→│A1 │A2 │A3 │ │ └─────┴─────┴─────┘ Phase 2b: Accepted(确认阶段) ──────────────────────────────────────── Acceptor 收到 Accept(n, value): - 如果 n >= 之前承诺的编号,接受提案 - 返回确认消息 Proposer Acceptors │ ┌─────┬─────┬─────┐ │←──Accepted(n=1)────│A1 │A2 │A3 │ │ └─────┴─────┴─────┘ 收到多数派的 Accepted,共识达成! ```  ### Paxos 示例代码 ```java public class PaxosNode { private long promisedId = 0; // 承诺的最小提案 ID private long acceptedId = 0; // 已接受的提案 ID private String acceptedValue; // 已接受的值 // Phase 1b: 处理 Prepare 请求 public Promise handlePrepare(long proposalId) { if (proposalId > promisedId) { promisedId = proposalId; return new Promise(true, acceptedId, acceptedValue); } return new Promise(false, 0, null); } // Phase 2b: 处理 Accept 请求 public boolean handleAccept(long proposalId, String value) { if (proposalId >= promisedId) { promisedId = proposalId; acceptedId = proposalId; acceptedValue = value; return true; } return false; } } public class Proposer { private List<PaxosNode> acceptors; private long proposalId; public String propose(String value) { proposalId = generateProposalId(); // Phase 1: Prepare List<Promise> promises = new ArrayList<>(); for (PaxosNode acceptor : acceptors) { Promise p = acceptor.handlePrepare(proposalId); if (p.isAccepted()) { promises.add(p); } } // 检查是否获得多数派 if (promises.size() <= acceptors.size() / 2) { throw new ConsensusException("Cannot get majority"); } // 选择值:使用已接受的最大编号的值 String finalValue = value; long maxAcceptedId = 0; for (Promise p : promises) { if (p.getAcceptedId() > maxAcceptedId) { maxAcceptedId = p.getAcceptedId(); finalValue = p.getAcceptedValue(); } } // Phase 2: Accept int acceptCount = 0; for (PaxosNode acceptor : acceptors) { if (acceptor.handleAccept(proposalId, finalValue)) { acceptCount++; } } if (acceptCount > acceptors.size() / 2) { return finalValue; // 达成共识 } throw new ConsensusException("Accept phase failed"); } } ```  ### 多 Proposer 冲突场景  *图:并发提议时编号更大的 Proposer 胜出,值 Y 被选定* ``` 时间线 → Proposer A: ──Prepare(1)──┐ │ Acceptors: ←──Promise──┤ │ Proposer B: ──Prepare(2)──┐ │ Acceptors: ←──Promise───┤ (B的编号更大) │ Proposer A: ──Accept(1,X)──╳ (被拒绝,因为已承诺2) │ Proposer B: ──Accept(2,Y)──→ (成功) 结果:值 Y 被选定 ``` ### 活锁问题 ``` Proposer A: Prepare(1) → Promise Proposer B: Prepare(2) → Promise (A的Accept(1)被拒绝) Proposer A: Prepare(3) → Promise (B的Accept(2)被拒绝) Proposer B: Prepare(4) → Promise (A的Accept(3)被拒绝) ... 无限循环 ... 解决方案: 1. 随机延迟重试 2. 选出单一 Leader(Multi-Paxos) 3. 使用指数退避 ``` ## Multi-Paxos ### 优化思路  *图:Multi-Paxos 选 Leader 后每个值只需一轮 Accept* ``` Basic Paxos 问题:每次提议都需要两轮通信(Prepare + Accept) Multi-Paxos 优化: 1. 选出稳定的 Leader 2. Leader 对连续的日志条目只需一轮 Accept 3. 大大减少网络通信 ┌─────────────────────────────────────────────────────────────┐ │ Basic Paxos: 每个值需要 2 轮 │ │ 值1: Prepare → Accept │ │ 值2: Prepare → Accept │ │ 值3: Prepare → Accept │ ├─────────────────────────────────────────────────────────────┤ │ Multi-Paxos: Leader 确定后只需 1 轮 │ │ 选 Leader: Prepare │ │ 值1: Accept │ │ 值2: Accept │ │ 值3: Accept │ └─────────────────────────────────────────────────────────────┘ ``` ### Multi-Paxos 流程  *图:选举阶段一次 Prepare,正常阶段只发 Accept* ``` Leader Followers │ ┌───┬───┬───┐ 选举阶段: │ │F1 │F2 │F3 │ │──Prepare(epoch)─→ │ │ │ │ │←───Promise────────│ │ │ │ │ └───┴───┴───┘ │ 正常阶段(只需Accept): │ │──Accept(1, "cmd1")→│ │ │ │ │←──Accepted─────────│ │ │ │ │──Accept(2, "cmd2")→│ │ │ │ │←──Accepted─────────│ │ │ │ ... ``` ## Paxos 变体 | 变体 | 特点 | |------|------| | **Multi-Paxos** | 引入 Leader,减少通信轮次 | | **Fast Paxos** | 无冲突时只需一轮 | | **EPaxos** | 无 Leader,并行提交 | | **Flexible Paxos** | 允许不同的 Quorum 大小 | ## 本章小结 - **共识问题**:多节点就某个值达成一致 - **FLP 不可能**:异步系统无法保证终止的确定性共识 - **拜占庭容错**:处理恶意节点,需要更多节点(3f+1) - **Paxos**:两阶段协议(Prepare-Accept),保证一致性和安全性 - **Multi-Paxos**:引入 Leader 优化性能 ## 思考题 1. 为什么 Paxos 需要多数派(Quorum)?少数派为什么不行? 2. 在 Paxos 中,Proposer 为什么必须使用 Promise 阶段返回的最大编号对应的值? 3. 如果网络永远分区,Paxos 能达成共识吗?这与 FLP 有什么关系? ## QA ### Q1:为什么 Paxos 需要多数派(Quorum)?少数派为什么不行? 因为多数派之间一定有交集,这个交集节点能把“已经接受过的值”传递给后续提案,从而保证不会同时选出两个不同的值。如果只要求少数派同意,不同少数集合之间可能完全没有重叠,就无法继承历史状态,安全性会被破坏。 ### Q2:为什么 Proposer 必须使用 Promise 阶段返回的最大编号对应的值? 这是为了保证已经“最接近被选定”的旧值不会被新值覆盖。某个提案编号越大,代表它越新;而 Promise 返回的最大已接受提案值,是当前系统里最应该被继承的候选值。如果 Proposer 随意换成别的值,就可能让不同轮次分别推进出不同结果,破坏 Paxos 的一致性。 ### Q3:如果网络永远分区,Paxos 能达成共识吗?这与 FLP 有什么关系? 如果分区后某一侧仍然拥有多数节点,那么这一侧还能继续推进共识,少数侧不能。若所有分区都拿不到多数派,系统就无法继续达成新共识。FLP 告诉我们,在纯异步网络且允许节点故障的模型中,不存在一个既总能终止又绝对正确的确定性共识算法,所以 Paxos 选择优先保证安全性,在必要时接受“暂时不能继续提交”。 --- 下一篇:[05 - Raft 算法详解](./05-raft.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入