《极客时间教程 - 分布式协议与算法实战》笔记

拜占庭将军问题

拜占庭将军问题由莱斯利·兰波特提出，是分布式对等网络通信容错问题。核心是：不同节点通过通信达成共识，但节点可能出错、通信可能损坏，如何在存在叛徒的情况下达成一致决策。

映射关系：将军 → 节点；信使 → 通信系统；叛徒 → 故障/异常。

问题分析

口头协议的核心规则：

• 忠诚的副官遵守同一命令
• 若将军忠诚，所有忠诚副官执行其命令
• 若叛徒人数为 m，将军人数不能少于 3m + 1

示例一（3 将军 1 叛徒，不满足 3m+1）：

示例二（4 将军 1 叛徒，满足 3m+1）：

CAP 理论

CAP：在分布式系统中，一致性、可用性和分区容忍性最多同时满足两项。

• 一致性（C）：多个数据副本保持一致
• 可用性（A）：面对异常时仍可提供正常服务
• 分区容忍性（P）：网络分区故障时仍可提供服务

分布式系统中分区容忍性必不可少，实际在 C 和 A 之间权衡：

• CP：等待同步完成，期间不可用
• AP：允许读取所有节点，数据可能不一致

ACID 理论

• 原子性（A）：事务不可分割，全部成功或全部回滚
• 一致性（C）：事务前后数据库保持一致性状态
• 隔离性（I）：未提交事务的修改对其他事务不可见
• 持久性（D）：提交后修改永久保存

分布式事务实现方案：2PC、3PC、TCC、本地消息表、MQ 事务消息、Sagas。

BASE 理论

对 CAP 中一致性和可用性权衡的结果：即使无法做到强一致性，也可通过适当方式达到最终一致性。

• 基本可用（BA）：保证核心可用，允许损失部分可用性
• 软状态（S）：允许数据存在中间状态（同步延迟）
• 最终一致性（E）：经过一段时间后，所有副本最终一致

Paxos 算法

Paxos 是基于消息传递的共识算法，运行在允许宕机的异步系统中。利用 Majority 机制：2N+1 个节点最多允许 N 个节点同时故障。

Basic Paxos 算法

角色

• 提议者（Proposer）：发出提案，代表接入和协调功能
• 决策者（Acceptor）：对提案投票，代表投票协商和存储数据
• 学习者（Learner）：不参与决策，被动接受达成共识的值

算法流程

1. Prepare 阶段：Proposer 发送 Prepare 请求（仅携带 Proposal ID）
2. Promise 阶段：Acceptor 做出"两个承诺 + 一个应答"
   • 承诺不再接受更小 ID 的 Prepare/Propose 请求
   • 应答已 Accept 过的最大 ID 提案的 Value
3. Propose 阶段：Proposer 选择最大 ID 的 Value 发起提案
4. Accept 阶段：Acceptor 在不违背承诺下接受并持久化
5. Learn 阶段：决议形成，发送给所有 Learners

Multi Paxos 思想

Basic Paxos 的问题：只能对一个值形成决议；可能形成活锁。

改进：

• 为每个值运行独立 Paxos 实例（Instance），使用唯一 Instance ID
• 选举 Leader 唯一提交 Proposal，跳过 Prepare 阶段，两阶段变为一阶段

应用：Chubby、Boxwood 使用 Multi Paxos；ZooKeeper 的 Zab 是其变形。

Raft 算法

Raft 将一致性问题分解为三个子问题：选举 Leader、日志复制、安全性。

服务器角色

• Leader：处理所有客户端请求
• Follower：只响应 Leader/Candidate 的请求
• Candidate：选举时的临时角色

任期

• 时间被分割为任意长度的 Term，每段任期从一次选举开始
• 一个任期内最多只有一个 Leader
• Term 充当逻辑时钟，用于检测过期信息
• 任期号单调递增，通信时交换并更新

RPC

• RequestVote RPC：Candidate 在选举期间发起
• AppendEntries RPC：Leader 发起，复制日志 + 心跳

选举 Leader

• Leader 周期性发送心跳维持权威
• Follower 在随机竞选超时时间（150ms~300ms）内未收到心跳则发起选举
• 获得半数以上选票的 Candidate 成为 Leader

三种结果：自己成为 Leader / 其他服务器成为 Leader / 无人成为 Leader（选票瓜分）

Raft 使用随机选举超时来避免选票瓜分并快速解决。

日志复制

日志格式

日志同步保证：

• 相同日志索引 + Term → 命令相同（Leader 每个 Term 每个索引只创建一条）
• 相同日志索引 + Term → 之前所有条目完全一样（AppendEntries 一致性检查）

日志复制流程

1. Leader 将请求写入本地日志
2. 并行发送 AppendEntries RPC 给 Follower
3. 半数以上复制后，Leader 提交并返回结果

日志一致性

Leader 崩溃可能导致日志不一致：

解决：Leader 强制 Followers 复制自己的日志，不一致的日志会被覆盖。从后往前找到一致位点，向后逐条覆盖。

安全性

选举限制

拥有最新已提交日志的 Follower 才有资格成为 Leader。RequestVote RPC 包含日志信息，Follower 拒绝日志不够新的投票。

比较新旧：先比 Term（大则新），Term 相同比日志索引。

提交旧任期日志条目

Raft 永不通过计算副本数提交旧 Term 的日志。只有当前 Term 的日志可通过计数提交；一旦提交，旧日志通过日志匹配特性间接提交。

日志压缩

采用快照解决日志无限膨胀。每个副本独立生成快照（仅对已提交条目）。

快照频率要适中；可用 copy-on-write 避免影响正常日志同步。

一致性哈希算法

目标：相同的请求尽可能落到同一个服务器上。

存储节点排列在首尾相接的 Hash 环上，key 顺时针找到邻接节点存放。节点加入/退出仅影响顺时针相邻后续节点。

• 优点：增删节点影响小
• 缺点：少量节点时增减影响大；需增倍/减半节点才能均衡

改进方案：虚拟槽（如 Dynamo）。

Gossip 协议

去中心化、容错、点对点通信的最终一致性协议。

类型

• Anti-Entropy（反熵）：传播所有数据，消息无限，不适合大规模集群
• Rumor-Mongering（谣言传播）：仅传播新数据，消息有限，系统开销小

通信模式：Push（1 次通信）、Pull（2 次）、Push/Pull（3 次，效果最好）

优点

• 扩展性：节点任意增减
• 容错：节点宕机不影响传播
• 去中心化：无需中心节点
• 一致性收敛：消息传播速度 O(logN)

缺陷

• 消息延迟：不适合实时性要求高的场景
• 消息冗余：节点可能重复收到相同消息

QuorumNWR 算法

通过调整 W + R 与 N 的关系自定义一致性级别：

• N：副本数

• W：写一致性级别（成功更新 W 个副本才算完成）

• R：读一致性级别（读取 R 个副本，返回最新数据）

• W + R > N：强一致性

• W + R < N：最终一致性

PBFT 算法

略

PoW 算法

略

ZAB 协议

ZAB 是 ZooKeeper 专用的支持崩溃恢复的原子广播协议，不是 Paxos。

两个可无限循环的流程：选举 Leader（故障恢复）+ 原子广播（主从同步）。

选举 Leader

基于过半选举机制产生新 Leader。关键术语：

• myid：集群唯一 ID
• zxid：64 位事务 ID（高 32 位 epoch + 低 32 位序号），全局单调递增

服务器状态：LOOKING / FOLLOWING / LEADING / OBSERVING

投票流程：自增选举轮次 → 初始化选票 → 发送初始化选票 → 接收外部投票 → 判断选举轮次 → 选票 PK（先比 zxid，再比 myid）→ 统计选票 → 更新状态

ZooKeeper 集群节点数必须是奇数，存活节点不少于 N+1。

原子广播

所有写请求转发给 Leader，Leader 以原子广播通知 Follower。半数以上 Follower 更新持久化后，Leader 才提交更新。

InfluxDB 企业版一致性实现剖析

略

Hashicorp Raft

略

基于 Raft 的分布式 KV 系统开发实战

略

参考资料

• 分布式协议与算法实战