Paxos 与分布式一致性协议详解 ⭐⭐⭐
分布式一致性是分布式系统的核心问题，面试高频考点
🎯 面试题：什么是 Paxos？分布式系统为什么需要一致性协议？
Paxos 是 Leslie Lamport 提出的分布式一致性算法，用于在可能发生故障的分布式系统中，让多个节点对某个值达成一致。它是分布式共识算法的理论基础，Raft、ZAB 等都是其简化或变体。
一、为什么需要分布式一致性协议
1.1 分布式系统的挑战
┌─────────────────────────────────────────────────────────────┐
│ 分布式系统的核心问题 │
│ │
│ 单机系统： │
│ ┌─────────┐ │
│ │ Server │ ← 所有操作在一台机器上完成，天然一致 │
│ └─────────┘ │
│ │
│ 分布式系统： │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Node A │◄───►│ Node B │◄───►│ Node C │ │
│ └─────────┘ └─────────┘ └─────────┘ │
│ ▲ ▲ │
│ └────────── 网络分区 ──────────┘ │
│ │
│ 问题： │
│ 1. 网络延迟/丢包 → 消息可能丢失或乱序 │
│ 2. 节点故障 → 部分节点可能崩溃 │
│ 3. 网络分区 → 节点间无法通信 │
│ 4. 拜占庭故障 → 节点可能发送错误信息（恶意或故障） │
└─────────────────────────────────────────────────────────────┘
1.2 一致性问题场景
/**
* 场景1：数据库主从复制
*
* 主库写入数据后，从库同步
* 如果主库宕机，从库提升为主库
* 如何保证数据不丢失、不冲突？
*/
public class ReplicationConsistency {
// 主库写入: set key = value
// 从库1同步: set key = value ✓
// 从库2同步: 网络延迟，未收到
// 主库宕机，从库2成为新主库
// 问题：从库2缺少数据，读取到旧值
}
/**
* 场景2：分布式锁
*
* 多个服务竞争同一把锁
* 如何保证只有一个服务获得锁？
*/
public class DistributedLock {
// Service A: 申请锁成功
// Service B: 同时申请锁
// 如果没有一致性协议，可能两者都成功！
}
/**
* 场景3：配置中心
*
* 配置更新需要所有节点达成一致
* 部分节点看到新配置，部分看到旧配置会导致混乱
*/
public class ConfigConsistency {
// 更新配置: timeout = 30s
// Node A 看到: timeout = 30s
// Node B 看到: timeout = 10s (旧值)
// 结果：系统行为不一致
}
1.3 一致性的核心目标
┌─────────────────────────────────────────────────────────────┐
│ 一致性协议的目标 │
│ │
│ 1. 安全性 (Safety) │
│ - 所有正确的节点最终达成一致 │
│ - 一旦达成一致，值不会再改变 │
│ - 达成的值一定是某个节点提议的 │
│ │
│ 2. 活性 (Liveness) │
│ - 系统最终能达成一致（在有限时间内） │
│ - 不会因为某些节点故障而永久阻塞 │
│ │
│ 3. 容错性 (Fault Tolerance) │
│ - 容忍部分节点故障 │
│ - 容忍网络分区 │
│ - 容忍消息丢失/延迟 │
└─────────────────────────────────────────────────────────────┘
二、理论基础：FLP 不可能定理与 CAP 定理
2.1 FLP 不可能定理
/**
* FLP 不可能定理 (Fischer, Lynch, Paterson, 1985)
*
* 定理内容：
* 在一个异步的分布式系统中，如果至少有一个节点可能故障，
* 那么不存在一个确定性的共识算法能够保证所有非故障节点达成一致。
*
* 关键条件：
* 1. 异步系统：消息延迟没有上界
* 2. 至少一个节点可能故障（即使是崩溃故障）
* 3. 确定性算法：给定相同输入，总是产生相同输出
*/
public class FLPImpossibility {
/*
* 含义解读：
*
* FLP 不是说共识不可能实现，而是说：
* - 在异步系统中，没有算法能保证"一定"在有限时间内达成共识
* - 实际系统中，我们通过超时机制打破异步假设
* - 或者使用随机化算法（非确定性）
*
* 实际影响：
* - 所有实用的共识算法都依赖超时或随机化
* - Paxos、Raft 通过超时机制绕过 FLP 限制
*/
}
2.2 CAP 定理回顾
┌─────────────────────────────────────────────────────────────┐
│ CAP 定理 │
│ │
│ ┌─────────┐ │
│ │ C │ Consistency (一致性) │
│ │ A │ Availability (可用性) │
│ │ P │ Partition Tolerance (分区容错性) │
│ └─────────┘ │
│ │
│ 定理：分布式系统最多同时满足其中两个 │
│ │
│ 实际意义： │
│ - P 是必须的（网络分区必然发生） │
│ - 发生分区时，只能在 C 和 A 之间选择 │
│ │
│ CP 系统：Zookeeper、etcd、HBase │
│ AP 系统：Cassandra、Eureka、DynamoDB │
└─────────────────────────────────────────────────────────────┘
/**
* CAP 在一致性协议中的体现
*/
public class CAPInConsensus {
/*
* Paxos/Raft 的选择：CP
*
* 在网络分区时：
* - 为了保证一致性，可能拒绝部分请求（牺牲可用性）
* - 或者只能由多数派节点处理请求
*
* 例如 Raft：
* - Leader 选举需要多数票
* - 少数派分区无法选出 Leader，不可用
* - 但保证了不会脑裂
*/
}
三、Paxos 算法详解
3.1 Paxos 核心角色
┌─────────────────────────────────────────────────────────────┐
│ Paxos 角色定义 │
│ │
│ ┌─────────────┐ │
│ │ Proposer │ 提议者：提出提案 (Proposal) │
│ │ (提议者) │ - 向 Acceptor 发送 Prepare 请求 │
│ └──────┬──────┘ - 向 Acceptor 发送 Accept 请求 │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ │ Acceptor │ 接受者：决定是否接受提案 │
│ │ (接受者) │ - 对 Prepare 做出 Promise 响应 │
│ └──────┬──────┘ - 对 Accept 做出 Accepted 响应 │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ │ Learner │ 学习者：学习已确定的值 │
│ │ (学习者) │ - 不参与决策过程 │
│ └─────────────┘ - 从 Acceptor 获取最终结果 │
│ │
│ 注意：一个节点可以同时担任多个角色 │
└─────────────────────────────────────────────────────────────┘
3.2 提案编号机制
/**
* 提案编号 (Proposal Number)
*
* 格式：[RoundNumber, ServerId]
*
* 比较规则：
* - 先比较 RoundNumber，大的更大
* - RoundNumber 相同，比较 ServerId，大的更大
*
* 示例：
* - (1, A) < (2, B) → RoundNumber 2 > 1
* - (1, A) < (1, B) → RoundNumber 相同，B > A
*/
public class ProposalNumber implements Comparable<ProposalNumber> {
private final long roundNumber; // 轮次号，单调递增
private final String serverId; // 服务器标识
@Override
public int compareTo(ProposalNumber other) {
if (this.roundNumber != other.roundNumber) {
return Long.compare(this.roundNumber, other.roundNumber);
}
return this.serverId.compareTo(other.serverId);
}
/*
* 作用：
* 1. 保证提案的全序关系
* 2. 防止旧提案覆盖新提案
* 3. 实现"后者优先"的语义
*/
}
3.3 Promise 承诺机制
┌─────────────────────────────────────────────────────────────┐
│ Acceptor 的承诺机制 (Promise) │
│ │
│ Acceptor 维护两个状态： │
│ - promisedId: 已承诺的最高提案编号 │
│ - acceptedId: 已接受的最高提案编号 │
│ - acceptedValue: 已接受的值 │
│ │
│ Promise 规则： │
│ 1. 收到 Prepare(n) 时： │
│ - 如果 n > promisedId： │
│ → 更新 promisedId = n │
│ → 返回 Promise，附带已接受的 (acceptedId, acceptedValue)│
│ - 如果 n ≤ promisedId： │
│ → 拒绝（已有更高编号的承诺） │
│ │
│ 2. 收到 Accept(n, v) 时： │
│ - 如果 n ≥ promisedId： │
│ → 接受该提案 │
│ → 更新 acceptedId = n, acceptedValue = v │
│ → 返回 Accepted │
│ - 如果 n < promisedId： │
│ → 拒绝（已承诺更高编号的提案） │
└─────────────────────────────────────────────────────────────┘
3.4 Paxos 两阶段流程详解
┌─────────────────────────────────────────────────────────────────────────┐
│ Paxos 两阶段流程 │
│ │
│ Phase 1: Prepare 阶段（准备阶段） │
│ ═══════════════════════════════════ │
│ │
│ Proposer Acceptor (多数派) │
│ │ │ │
│ │ 1. Prepare(n) │ │
│ │ ─────────────────────────────────►│ │
│ │ │ │
│ │ 2. Promise(n, acceptedId, acceptedValue) │
│ │ ◄─────────────────────────────────│ │
│ │ (或 Reject，如果 n 不够大) │ │
│ │ │ │
│ ▼ ▼ │
│ │
│ 目的： │
│ 1. 阻止旧的提案被接受 │
│ 2. 了解 Acceptor 已接受的值（如果有） │
│ 3. 获得"提议权" │
│ │
│ ───────────────────────────────────────────────────────────────────── │
│ │
│ Phase 2: Accept 阶段（接受阶段） │
│ ═══════════════════════════════════ │
│ │
│ Proposer Acceptor (多数派) │
│ │ │ │
│ │ 3. Accept(n, v) │ │
│ │ ─────────────────────────────────►│ │
│ │ (v 的选择规则见下文) │ │
│ │ │ │
│ │ 4. Accepted(n, v) │ │
│ │ ◄─────────────────────────────────│ │
│ │ (或 Reject，如果 promisedId 变了) │
│ │ │ │
│ ▼ ▼ │
│ │
│ 目的：确定最终的值 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.5 值的选择规则
/**
* Proposer 如何选择要提议的值 v？
*/
public class ValueSelection {
/*
* 规则：
*
* 如果收到的 Promise 响应中，有 Acceptor 已经接受了某个值：
* → 必须选择 acceptedValue 最大的那个值
*
* 如果所有 Promise 响应都没有已接受的值：
* → 可以选择任意值（通常是客户端请求的值）
*
* 示例：
*
* 情况1：没有已接受的值
* Promise1: (null, null)
* Promise2: (null, null)
* Promise3: (null, null)
* → 选择客户端请求的值 v
*
* 情况2：有已接受的值
* Promise1: (10, "X") ← acceptedId=10, acceptedValue="X"
* Promise2: (8, "Y")
* Promise3: (null, null)
* → 必须选择 "X"（acceptedId 最大的值）
*/
public String selectValue(List<PromiseResponse> responses, String clientValue) {
// 找出所有已接受的值中，acceptedId 最大的
PromiseResponse maxAccepted = responses.stream()
.filter(r -> r.getAcceptedId() != null)
.max(Comparator.comparing(PromiseResponse::getAcceptedId))
.orElse(null);
if (maxAccepted != null) {
// 必须使用已接受的值
return maxAccepted.getAcceptedValue();
} else {
// 可以使用客户端的值
return clientValue;
}
}
}
3.6 完整流程图解
┌─────────────────────────────────────────────────────────────────────────┐
│ Paxos 完整执行流程示例 │
│ │
│ 场景：3 个 Acceptor (A1, A2, A3)，1 个 Proposer (P1) │
│ 目标：让多数派接受值 "Hello" │
│ │
│ Step 1: Prepare 阶段 │
│ ───────────────── │
│ │
│ P1(proposal=5) │
│ │ │
│ ├──► A1: Prepare(5) ──► Promise(null, null) │
│ │ │
│ ├──► A2: Prepare(5) ──► Promise(null, null) │
│ │ │
│ └──► A3: Prepare(5) ──► Promise(null, null) │
│ (只需要多数派响应即可) │
│ │
│ P1 收到 A1, A2 的 Promise，形成多数派 ✓ │
│ │
│ Step 2: Accept 阶段 │
│ ───────────────── │
│ │
│ P1(选择值 "Hello") │
│ │ │
│ ├──► A1: Accept(5, "Hello") ──► Accepted(5, "Hello") │
│ │ │
│ ├──► A2: Accept(5, "Hello") ──► Accepted(5, "Hello") │
│ │ │
│ └──► A3: Accept(5, "Hello") ──► Accepted(5, "Hello") │
│ (只需要多数派确认即可) │
│ │
│ 结果："Hello" 被多数派接受，共识达成！ │
│ │
│ ───────────────────────────────────────────────────────────────────── │
│ │
│ 冲突场景：两个 Proposer 同时提议 │
│ │
│ P1(proposal=5) P2(proposal=6) │
│ │ │ │
│ ├──► A1: Prepare(5) ├──► A2: Prepare(6) │
│ │ │ │
│ A1 promised=5 A2 promised=6 │
│ │ │ │
│ ├──► A2: Prepare(5) ──► Reject!(promised=6) │
│ │ │ │
│ │ ├──► A1: Prepare(6) ──► Promise(5, null) │
│ │ │ │
│ │ A1 promised=6 │
│ │ │ │
│ │ ├──► A3: Prepare(6) ──► Promise(null, null) │
│ │ │ │
│ ▼ ▼ │
│ P1 失败，需要重试 P2 获得多数派，继续 Accept 阶段 │
│ │
│ 最终 P2 的值会被接受，P1 重试时会采用 P2 已接受的值 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.7 Paxos 的 Java 实现简版
/**
* Paxos 算法简版实现
*/
public class PaxosNode {
// 提案编号
private long proposalNumber = 0;
private final String nodeId;
// Acceptor 状态
private long promisedId = -1; // 已承诺的最高提案编号
private long acceptedId = -1; // 已接受的最高提案编号
private Object acceptedValue = null; // 已接受的值
// Proposer 状态
private long currentProposal = -1;
private Object currentValue = null;
public PaxosResult propose(Object value, List<PaxosNode> acceptors) {
// ==================== Phase 1: Prepare ====================
currentProposal = ++proposalNumber;
currentValue = value;
List<PromiseResponse> promises = new ArrayList<>();
int promisesNeeded = acceptors.size() / 2 + 1;
// 向所有 Acceptor 发送 Prepare
for (PaxosNode acceptor : acceptors) {
PromiseResponse response = acceptor.handlePrepare(currentProposal);
if (response != null) {
promises.add(response);
}
}
// 没拿到多数派，提案失败
if (promises.size() < promisesNeeded) {
return new PaxosResult(false, null);
}
// ==================== Phase 2: Accept ====================
// 选择值：必须用 acceptedId 最大的那个值
Object chosenValue = selectValue(promises, currentValue);
List<AcceptedResponse> accepts = new ArrayList<>();
// 向所有 Acceptor 发送 Accept
for (PaxosNode acceptor : acceptors) {
AcceptedResponse response = acceptor.handleAccept(currentProposal, chosenValue);
if (response != null) {
accepts.add(response);
}
}
// 拿到多数派 Accept，提案成功
if (accepts.size() >= promisesNeeded) {
return new PaxosResult(true, chosenValue);
}
// 失败，需要重新提案（proposalNumber 增大）
return new PaxosResult(false, null);
}
// 处理 Prepare 请求（Acceptor 端）
public synchronized PromiseResponse handlePrepare(long n) {
if (n > promisedId) {
promisedId = n;
// 返回已接受的值（如果有）
if (acceptedId != -1) {
return new PromiseResponse(acceptedId, acceptedValue);
}
return new PromiseResponse(null, null);
}
return null; // 拒绝
}
// 处理 Accept 请求（Acceptor 端）
public synchronized AcceptedResponse handleAccept(long n, Object v) {
if (n >= promisedId) {
promisedId = n;
acceptedId = n;
acceptedValue = v;
return new AcceptedResponse(n, v);
}
return null; // 拒绝
}
private Object selectValue(List<PromiseResponse> promises, Object fallback) {
// 找出 acceptedId 最大的 Promise
PromiseResponse max = promises.stream()
.filter(p -> p.getAcceptedId() != null)
.max(Comparator.comparing(PromiseResponse::getAcceptedId))
.orElse(null);
return max != null ? max.getAcceptedValue() : fallback;
}
}
四、Paxos 活锁问题与 Multi-Paxos
4.1 活锁问题（Livelock）
┌─────────────────────────────────────────────────────────────────────────┐
│ Paxos 活锁问题 │
│ │
│ 场景：两个 Proposer 竞争，导致无限循环 │
│ │
│ 时间点 P1(proposal=1) P2(proposal=2) │
│ ───────────────────────────────────────────────────────────────── │
│ t1 Prepare(1) ──► A1,A2 (等待) │
│ t2 ◄─── Promise Prepare(2) ──► A1,A2 │
│ t3 (准备 Accept) ◄─── Promise │
│ t4 Accept(1,v) ──► A1 (准备 Accept) │
│ t5 ◄─── Reject!(promised=2) Accept(2,v') ──► A2 │
│ t6 (失败，proposal=3) ◄─── Reject!(promised=3) │
│ t7 Prepare(3) ──► A1,A2 (失败，proposal=4) │
│ t8 ◄─── Promise Prepare(4) ──► A1,A2 │
│ t9 ... ... │
│ │
│ 结果：两个 Proposer 不断用更高的编号抢占，但都无法完成 Accept 阶段 │
│ 系统一直在运行，但无法达成共识（活锁） │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4.2 活锁解决方案
/**
* 解决活锁的方法
*/
public class LivelockSolution {
/*
* 方案1：随机退避（Random Backoff）
*
* 当 Proposer 失败时，等待随机时间再重试
* 降低多个 Proposer 同时竞争的概率
*/
public void retryWithBackoff() {
int backoffMs = random.nextInt(100) + 50; // 50-150ms 随机
Thread.sleep(backoffMs);
retry();
}
/*
* 方案2：Leader 选举（Multi-Paxos 核心思想）
*
* 选举一个 Leader 作为唯一的 Proposer
* 其他节点只作为 Acceptor
* 避免多个 Proposer 竞争
*/
/*
* 方案3：提案编号分配策略
*
* 让每个 Proposer 使用不同的编号空间
* 例如：P1 用 1, 4, 7...，P2 用 2, 5, 8...，P3 用 3, 6, 9...
* 这样不会频繁冲突
*/
}
4.3 Multi-Paxos 优化
┌─────────────────────────────────────────────────────────────────────────┐
│ Multi-Paxos 优化 │
│ │
│ 核心思想：选举 Leader，跳过 Prepare 阶段 │
│ │
│ 标准 Paxos（每条日志都走两阶段）： │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │Prepare │────►│ Accept │────►│Prepare │────► ... │
│ │(日志1) │ │(日志1) │ │(日志2) │ │
│ └─────────┘ └─────────┘ └─────────┘ │
│ 2 RTT 2 RTT 2 RTT │
│ │
│ Multi-Paxos（Leader 跳过 Prepare）： │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │Prepare │────►│ Accept │────►│ Accept │────► ... │
│ │(仅一次) │ │(日志1) │ │(日志2) │ │
│ └─────────┘ └─────────┘ └─────────┘ │
│ 2 RTT 1 RTT 1 RTT │
│ │
│ 优化效果： │
│ - 第一条日志：2 RTT（需要 Prepare） │
│ - 后续日志：1 RTT（直接 Accept） │
│ - 吞吐量提升约 1 倍 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
五、Raft vs Paxos 对比
5.1 设计哲学对比
┌─────────────────────────────────────────────────────────────────────────┐
│ Raft vs Paxos 设计哲学 │
│ │
│ Paxos： │
│ - 从理论出发，先证明正确性 │
│ - 论文极其简洁（只有 8 页），但难以理解 │
│ - 没有明确区分角色，实现复杂 │
│ - Lamport："Paxos 很简单" │
│ - 工程师："Paxos 难以理解" │
│ │
│ Raft： │
│ - 从可理解性出发，设计目标就是"易于理解" │
│ - 将问题分解为三个子问题：领导选举、日志复制、安全性 │
│ - 明确区分 Leader/Follower/Candidate │
│ - 强 Leader 设计，简化日志复制 │
│ - 有详细的论文和开源实现参考 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
5.2 详细对比表
| 维度 | Paxos | Raft |
|---|---|---|
| 核心思想 | 两阶段提交，允许多个 Proposer | 强 Leader，所有写操作经过 Leader |
| 角色划分 | Proposer/Acceptor/Learner，角色可重叠 | Leader/Follower/Candidate，角色明确 |
| Leader | 无固定 Leader，允许多个 Proposer 竞争 | 有且仅有一个 Leader，简化设计 |
| 日志复制 | 每个日志位置独立运行 Paxos | Leader 统一协调日志复制 |
| 理解难度 | 难（Chubby 作者：实现 Paxos 很难） | 易（设计目标就是可理解） |
| 工程实现 | 复杂，容易出错 | 简单，有成熟开源实现 |
| 性能 | 多 Proposer 竞争时性能下降 | Leader 成为瓶颈，但可预测 |
| 成员变更 | 理论完善但复杂 | 两阶段 Joint Consensus，相对简单 |
| 典型应用 | Chubby、ZooKeeper（ZAB 类似） | etcd、Kubernetes、RocketMQ、TiKV |
| 论文可读性 | 简洁但晦涩 | 详细且清晰 |
5.3 算法流程对比
┌─────────────────────────────────────────────────────────────────────────┐
│ 日志复制流程对比 │
│ │
│ Paxos/Multi-Paxos： │
│ ───────────────── │
│ │
│ Client │
│ │ │
│ │ 写请求 │
│ ▼ │
│ Proposer ──► 选择日志位置 i │
│ │ │
│ ├──► Prepare(i) ──► Acceptor 多数派 │
│ │ │
│ ├──► Accept(i, v) ──► Acceptor 多数派 │
│ │ │
│ └──► 通知 Learner │
│ │
│ 特点：每个日志位置独立，可以乱序提交 │
│ │
│ ───────────────────────────────────────────────────────────────────── │
│ │
│ Raft： │
│ ───── │
│ │
│ Client │
│ │ │
│ │ 写请求 │
│ ▼ │
│ Leader ──► 追加本地日志 │
│ │ │
│ ├──► AppendEntries ──► Follower │
│ │ │
│ ├──► 收到多数确认后提交 │
│ │ │
│ └──► 通知 Follower 提交 │
│ │
│ 特点：Leader 统一协调，日志顺序复制 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
六、ZAB 协议（ZooKeeper 原子广播）
6.1 ZAB 概述
┌─────────────────────────────────────────────────────────────┐
│ ZAB 协议简介 │
│ │
│ ZAB (ZooKeeper Atomic Broadcast) │
│ - ZooKeeper 的核心一致性协议 │
│ - 类似 Multi-Paxos，专为 ZooKeeper 设计 │
│ - 保证： │
│ 1. 顺序一致性：客户端的更新按发送顺序执行 │
│ 2. 原子性：更新要么全部成功，要么全部失败 │
│ 3. 单一系统镜像：客户端看到一致的视图 │
│ 4. 可靠性：更新一旦生效就会持久化 │
│ 5. 及时性：客户端在一定时间内看到更新 │
│ │
│ 与 Raft 的主要区别： │
│ - ZAB 保证事务的全局顺序（zxid 单调递增） │
│ - 崩溃恢复时，需要保证已提交的事务不丢失 │
│ - Leader 选举时会比较 zxid，选择数据最新的节点 │
│ │
└─────────────────────────────────────────────────────────────┘
6.2 ZAB 协议状态
┌─────────────────────────────────────────────────────────────┐
│ ZAB 节点状态机 │
│ │
│ ┌───────────┐ │
│ │ LOOKING │ 选举状态，寻找 Leader │
│ └─────┬─────┘ │
│ │ │
│ ▼ 选举出 Leader │
│ ┌───────────┐ │
│ │ LEADING │ Leader 状态，Leader 向 Follower 发提案 │
│ └─────┬─────┘ │
│ │ │
│ ▼ 检测到 Leader 失效 │
│ ┌───────────┐ │
│ │ FOLLOWING │ Follower 状态，接收 Leader 的提案 │
│ └───────────┘ │
│ │
│ 注意：没有 Candidate 状态，Leader 选举直接│ 从 LOOKING 状态进入 LEADING 或 FOLLOWING │
│ │
└─────────────────────────────────────────────────────────────┘
6.3 Leader 选举机制
/**
* ZAB Leader 选举（Fast Leader Election）
*
* 关键点：
* 1. 使用 (zxid, serverId) 作为选举权重
* 2. zxid 大的优先（数据更完整）
* 3. serverId 大的作为 tiebreaker
*/
public class ZabLeaderElection {
/**
* 投票信息
*/
public static class Vote {
private final long zxid; // 事务 ID，越大数据越新
private final long serverId; // 服务器 ID
private final long epoch; // 选举轮次
// 比较规则：epoch > zxid > serverId
public int compareTo(Vote other) {
if (this.epoch != other.epoch) {
return Long.compare(this.epoch, other.epoch);
}
if (this.zxid != other.zxid) {
return Long.compare(this.zxid, other.zxid);
}
return Long.compare(this.serverId, other.serverId);
}
}
/*
* 选举流程：
*
* 1. 每个节点投票给自己 (zxid, serverId)
* 2. 向所有节点广播投票
* 3. 收到其他节点的投票后：
* - 如果对方的票比自己的好（zxid 更大），更新自己的票
* - 否则保持不变
* 4. 如果某节点收到相同票达到半数，该节点成为 Leader
*
* 与 Raft 选举的区别：
* - Raft 比较日志完整度（lastLogTerm + lastLogIndex）
* - ZAB 比较 zxid（事务 ID，更直接）
*/
}
/**
* ZAB 的崩溃恢复（Recovery）
*
* 当 Leader 崩溃后，新的 Leader 需要保证：
* 1. 已提交的事务不能丢失
* 2. 未提交的事务不能应用（回滚或继续）
*
* 恢复过程：
* 1. 新 Leader 收集所有 Follower 的 zxid
* 2. 找出最大的 zxid 作为自己的起点
* 3. 同步缺失的事务给 Follower
* 4. 确保已提交的事务在所有节点上一致
*/
6.4 ZAB 写入流程
┌─────────────────────────────────────────────────────────────────────────┐
│ ZAB 写入流程 │
│ │
│ Client │
│ │ │
│ │ 写请求 "set /config value" │
│ ▼ │
│ ┌──────────────┐ │
│ │ Leader │ │
│ │ (收到请求) │ │
│ └──────┬───────┘ │
│ │ │
│ │ 生成 zxid，写入本地日志 │
│ ▼ │
│ ┌──────────────┐ │
│ │ PROPOSAL │ 向所有 Follower 广播提案 │
│ │ (提议阶段) │ │
│ └──────┬───────┘ │
│ │ │
│ ├──► Follower1: PROPOSAL ──► 写入本地日志 │
│ │ ◄── ACK │
│ ├──► Follower2: PROPOSAL ──► 写入本地日志 │
│ │ ◄── ACK │
│ └──► Follower3: PROPOSAL ──► 写入本地日志 │
│ ◄── ACK │
│ │ │
│ ▼ 收到多数 ACK │
│ ┌──────────────┐ │
│ │ COMMIT │ 向所有节点发送 COMMIT │
│ │ (提交阶段) │ │
│ └──────┬───────┘ │
│ │ │
│ ├──► Follower1: COMMIT ──► 应用到状态机 │
│ ├──► Follower2: COMMIT ──► 应用到状态机 │
│ └──► Follower3: COMMIT ──► 应用到状态机 │
│ │
│ ◄── 响应 Client │
│ │
│ zxid 格式： │
│ ┌────────────────────────┬───────────┐ │
│ │ epoch (高 32 位) │ counter │ │
│ │ (选举轮次) │ (低 32 位) │ │
│ └────────────────────────┴───────────┘ │
│ │
│ - epoch 每次 Leader 选举递增 │
│ - counter 在每个事务时递增 │
│ - 保证了 zxid 的全局唯一性和递增性 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
七、一致性级别详解
7.1 一致性级别总览
┌─────────────────────────────────────────────────────────────────────────┐
│ 一致性级别金字塔 │
│ │
│ 强一致性 │
│ ╱ ╲ │
│ 线性一致 顺序一致 │
│ ╱ ╲ │
│ 因果一致 读己之所写 │
│ ╱ ╲ │
│ 会话一致 单调读 │
│ ╱ ╲ │
│ 单调写 最终一致 │
│ │
│ 从上到下：一致性强度递减，性能/可用性递增 │
│ │
│ 各一致性级别定义： │
│ 1. 强一致性：任何时刻，所有节点看到相同数据 │
│ 2. 线性一致：操作按真实时间排序，所有节点同时看到 │
│ 3. 顺序一致：所有节点看到相同的操作顺序（不一定按真实时间） │
│ 4. 因果一致：有因果关系的操作顺序一致，无因果关系的可重排 │
│ 5. 读己之所写：总能读到自己最新写入的值 │
│ 6. 会话一致：同一会话内保证单调读/单调写 │
│ 7. 单调读：不会读到比之前更旧的数据 │
│ 8. 单调写：自己的写操作按顺序执行 │
│ 9. 最终一致：系统在没有新更新时，最终达到一致 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
7.2 线性一致性（Linearizability）
/**
* 线性一致性（最强的一致性级别）
*
* 定义：每个操作看起来在调用和响应之间的某个时间点
* 原子地执行，所有节点看到相同的操作顺序
*
* 特点：
* 1. 操作按真实时间排序
* 2. 读操作总是返回最新的写结果
* 3. 任何读操作都能"看见"之前所有完成的写操作
*/
public class Linearizability {
/*
* 示例：分布式锁服务
*
* 时间线：
* T1: Client A 获取锁（成功）
* T2: Client B 获取锁（失败，应该被阻塞）
* T3: Client A 释放锁
* T4: Client B 获取锁（成功）
*
* 线性一致保证：
* - T1 < T2 < T3 < T4（按真实时间排序）
* - B 在 T4 之前无法获取锁
* - 不会出现两个客户端同时持有锁的情况
*/
/*
* 验证方法：
* - 使用读写寄存器模型验证
* - 记录所有操作的调用时间和返回时间
* - 检查是否存在合法的线性化排序
*/
}
/**
* 线性一致 vs 顺序一致
*
* 线性一致：操作按真实时间（物理时钟）排序
*
* 时间 ─────────────────────────────────►
* P1: W(x=1) -----------
* P2: R(x=1) --------
* P3: R(x=1) --------
* ✓ 线性一致（读到了之前的写）
*
* 顺序一致：不保证真实时间顺序，只保证所有进程看到相同的顺序
*
* P1: W(x=1) -----------
* P2: R(x=0) -------- (读到旧值，但这是允许的)
* P3: R(x=1) --------
* ✓ 顺序一致（所有进程看到的写顺序都是 x=1）
* ✗ 线性一致（因为 P2 在 P1 写之后读到了旧值）
*/
7.3 因果一致性（Causal Consistency）
/**
* 因果一致性
*
* 定义：只有有因果关系的操作需要按顺序执行
* 没有因果关系的操作可以并行执行或重排
*
* 因果关系的例子：
* - "发布微博" → "收到评论"（有因果）
* - "发朋友圈 A" → "发朋友圈 B"（无因果）
*
* 因果一致的实现：
* - 使用向量时钟（Vector Clock）跟踪因果关系
* - 每个节点维护一个向量，记录每个节点的"逻辑时间"
*/
public class CausalConsistency {
/**
* 向量时钟
*/
public class VectorClock {
private final Map<String, Long> clock = new HashMap<>();
// 更新本地逻辑时间
public void increment(String nodeId) {
clock.merge(nodeId, 1L, Long::sum);
}
// 合并两个向量时钟（取最大值）
public void merge(VectorClock other) {
for (String nodeId : other.clock.keySet()) {
clock.merge(nodeId, other.clock.get(nodeId), Math::max);
}
}
// 判断是否存在因果关系
public boolean happenedBefore(VectorClock other) {
boolean lessThan = false;
for (String nodeId : clock.keySet()) {
long thisTime = clock.getOrDefault(nodeId, 0L);
long otherTime = other.clock.getOrDefault(nodeId, 0L);
if (thisTime > otherTime) return false;
if (thisTime < otherTime) lessThan = true;
}
return lessThan;
}
}
/*
* 示例：
*
* Node A: 发消息 "你好" (VC_A = {A:1})
* Node B: 收到 "你好"，回复 "收到" (VC_B = {A:1, B:1})
* Node C: 收到 "收到"，知道与 "你好" 有因果关系
*
* Node A 和 Node D 同时发消息（无因果）
* 可以以任意顺序应用，不需要等待对方
*/
}
/**
* 因果一致 vs 顺序一致
*
* 顺序一致：
* - 所有节点看到相同的操作全局顺序
* - 不关心真实时间
*
* 因果一致：
* - 只保证有因果关系的操作顺序一致
* - 无因果关系的操作可以乱序
* - 更宽松，性能更好
*/
7.4 读己之所写（Read Your Writes）
/**
* 读己之所写（Read Your Writes Consistency）
*
* 定义：一个进程写入的值，后续该进程的读操作一定能读到
*
* 示例：用户更新头像后，立即刷新页面
* - 必须看到新头像（自己刚更新的）
* - 不能看到旧头像
*
* 实现方式：
*/
public class ReadYourWrites {
/*
* 方式1：会话亲和性（Session Affinity）
* - 同一个客户端的读写路由到同一个节点
* - 简单但不通用
*
* 方式2：版本号/时间戳跟踪
* - 客户端记录自己写的版本号
* - 读请求携带版本号
* - 服务器返回 >= 版本号的数据
*
* 方式3：管道持久化（Pipeline RMDA）
* - 写操作同步到 quorum 后才返回
* - 后续读操作一定能在 quorum 中读到新值
*/
// 客户端实现示例
public class Client {
private String lastWriteVersion;
public void write(String key, String value) {
// 写入并获取版本号
lastWriteVersion = storage.write(key, value);
}
public String read(String key) {
// 读请求携带版本号
return storage.read(key, lastWriteVersion);
}
}
}
/**
* 单调读（Monotonic Reads）
*
* 定义：不会读到比之前更旧的数据
*
* 示例：
* - 第一次读到 v2
* - 第二次不能读到 v1（比 v2 更旧）
* - 可以读到 v2、v3 等
*
* 实现：
* - 使用向量时钟跟踪每个键的版本
* - 节点记录客户端已读过的最新版本
*/
7.5 最终一致性（Eventual Consistency）
/**
* 最终一致性
*
* 定义：在没有新更新的情况下，系统最终会达到一致状态
* - 不保证何时达到一致
* - 不保证每次读到的值都相同
* - 但最终会收敛
*
* 典型场景：
* - DNS 域名解析（TTL 过期后更新）
* - 社交媒体点赞数（允许短暂不一致）
* - 商品库存（需要补偿机制）
*/
public class EventualConsistency {
/*
* Dynamo/Cassandra 的最终一致实现：
*
* 1. 写操作写入多个副本（W 副本确认）
* 2. 读操作从多个副本读取（R 副本取最新）
* 3. 使用向量时钟或时间戳解决冲突
* 4. 后台同步修复不一致的数据
*
* 配置：W + R > N 保证强读
* 例如：N=3, W=2, R=2
* - 写需要 2 个副本确认
* - 读需要 2 个副本取最新
* - W 和 R 有重叠，保证读到最新
*/
// Cassandra 一致性级别
public enum ConsistencyLevel {
ANY, // 写入任一节点即可
ONE, // 1 个节点确认
QUORUM, // 多数派确认 (N/2 + 1)
ALL, // 所有节点确认
LOCAL_QUORUM, // 本地 DC 多数派
EACH_QUORUM // 每个 DC 都多数派
}
}
/**
* 一致性级别的选择
*
* 强一致 (Linearizable/Sequential):
* - 银行转账、库存扣减、分布式锁
* - 需要强一致性保证
*
* 因果一致:
* - 社交评论（回复必须在原评论之后）
* - 协同编辑（因果关系重要）
*
* 读己之所写:
* - 用户更新个人资料后查看
* - 修改密码后继续操作
*
* 最终一致:
* - 点赞数、阅读量
* - 缓存更新
* - 日志同步
*/
八、Gossip 协议详解
8.1 Gossip 协议概述
┌─────────────────────────────────────────────────────────────────────────┐
│ Gossip 协议简介 │
│ │
│ Gossip 协议：模拟病毒在人群中传播的 gossip 闲聊 │
│ │
│ 核心思想： │
│ - 每个节点随机选择其他节点交换信息 │
│ - 信息像病毒一样在集群中扩散 │
│ - 最终所有节点都拥有完整信息 │
│ │
│ 特点： │
│ ✓ 去中心化：无需协调者 │
│ ✓ 高可用：节点可以随时加入/离开 │
│ ✓ 容错：部分节点故障不影响整体 │
│ ✓ 可扩展：信息传播时间 O(log N) │
│ ✗ 最终一致：不是强一致 │
│ ✗ 带宽占用：定期通信 │
│ ✗ 收敛时间：有延迟 │
│ │
│ 经典应用： │
│ - Amazon DynamoDB │
│ - Redis Cluster │
│ - Cassandra │
│ - Consul 服务发现 │
│ - SWIM 集群成员协议 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
8.2 Gossip 传播机制
┌─────────────────────────────────────────────────────────────────────────┐
│ Gossip 传播流程（Anti-Entropy） │
│ │
│ 场景：5 个节点，节点 A 更新了值 x=1，需要同步到所有节点 │
│ │
│ Round 1: │
│ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │ A:x=1│───►│ B │ │ C │ │ D │ │ E │ │
│ │ (新) │ │(收到)│ │ │ │ │ │ │ │
│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ │
│ │
│ Round 2: │
│ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │ A:x=1│ │ B:x=1│───►│ C │ │ D:x=1│ │ E │ │
│ │ │◄───│ │ │(收到)│ │ │◄───│(收到)│ │
│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ │
│ │
│ Round 3: │
│ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │ A:x=1│ │ B:x=1│ │ C:x=1│◄───►│ D:x=1│ │ E:x=1│ │
│ │ │ │ │◄───│ │ │ │◄───│ │ │
│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ │
│ 完成同步！所有节点 x=1 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
8.3 Gossip 变种
/**
* Gossip 协议的两种主要传播方式
*/
public class GossipVariants {
/**
* 方式1：Anti-Entropy（反熵）
*
* - 交换完整数据
* - 发现并修复不一致
* - 带宽消耗大，但准确性高
* - 通常定期执行
*/
public void antiEntropy(Node self, Node peer) {
// 交换完整数据集
Map<String, Version> selfData = self.getAllData();
Map<String, Version> peerData = peer.getAllData();
// 计算差异并修复
for (String key : union(selfData.keySet(), peerData.keySet())) {
Version selfVer = selfData.get(key);
Version peerVer = peerData.get(key);
if (selfVer == null) {
self.setData(key, peerVer); // 获取缺失数据
} else if (peerVer == null) {
peer.setData(key, selfVer); // 推送缺失数据
} else if (selfVer.timestamp < peerVer.timestamp) {
self.setData(key, peerVer); // 更新旧数据
} else if (selfVer.timestamp > peerVer.timestamp) {
peer.setData(key, selfVer); // 推送新数据
}
}
}
/**
* 方式2：Rumor Mongering（谣言传播）
*
* - 只传播新数据（ rumors / gossip）
* - 旧数据不再传播
* - 带宽消耗小
* - 可能遗漏更新（通过定期"重新传播"解决）
*/
public void rumorMongering(Node self, Node peer) {
// 只交换"新鲜"的数据
List<Rumor> rumors = self.getRecentRumors();
for (Rumor rumor : rumors) {
peer.receiveRumor(rumor);
}
}
}
/**
* Gossip 配置参数
*/
public class GossipConfig {
/*
* 关键参数：
*
* 1. Fanout（扇出数）
* - 每次传播选择的节点数
* - 通常为常数（如 3）
* - 太大：带宽浪费
* - 太小：传播慢
*
* 2. 传播间隔 (Gossip Interval)
* - 每次传播的间隔时间
* - 通常 1-3 秒
* - 太短：带宽浪费
* - 太长：收敛慢
*
* 3. 传播轮数 / TTL
* - 数据传播多少轮后停止
* - 通常设置足够大的轮数保证收敛
*
* 收敛时间估算：
* O(log N) 轮后，所有节点都会收到消息
*
* 示例：
* - N = 1000 节点
* - Fanout = 3
* - 收敛轮数 ≈ log_3(1000) ≈ 6 轮
* - 间隔 1 秒 → 6 秒内完成收敛
*/
}
8.4 Redis Cluster 中的 Gossip
/**
* Redis Cluster 中的 Gossip 机制
*
* Redis Cluster 使用 Gossip 协议做两件事：
* 1. 成员关系（Cluster Bus）：检测节点存活、故障
* 2. 集群状态：槽迁移、配置更新
*/
public class RedisClusterGossip {
/*
* Gossip 消息格式
*
* typedef struct {
* uint32_t totlen; // 消息总长度
* uint16_t type; // 消息类型
* uint16_t count; // Gossip 节点数量
* uint64_t senderId; // 发送者 ID
* uint32_t currentEpoch; // 当前配置纪元
* uint16_t flags; // 发送者状态
* unsigned char gossip[count]; // Gossip 节点信息
* } clusterMsg;
*
* typedef struct {
* uint64_t nodeId; // 节点 ID
* uint32_t pingSent; // ping 发送时间
* uint32_t pongReceived; // pong 接收时间
* char ip[46]; // IP 地址
* uint16_t port; // 端口
* uint16_t cport; // Cluster Bus 端口
* uint16_t flags; // 节点状态
* } clusterMsgDataGossip;
*
* Gossip 包含的节点信息：
* - 节点名称、IP、端口
* - 最后 ping/pong 时间
* - 节点状态（主/从/FAIL 等）
*/
/*
* 故障检测流程：
*
* 1. 每个节点定期（每秒）向随机节点发 Ping
* 2. 被 ping 的节点返回 Pong
* 3. 如果节点超过 node_timeout 没收到 Pong，标记为疑似下线（PFAIL）
* 4. 如果多个主节点都报告某节点 PFAIL，该节点被标记为 FAIL
* 5. FAIL 消息通过 Gossip 广播给所有节点
*
* 示例：
* Node A ping Node B，B 没有返回 Pong
* A 等待 node_timeout（默认 15s）
* A 标记 B 为 PFAIL，在 Gossip 中广播
* 如果 A、B、C 三个主节点都标记 B 为 PFAIL
* 则 B 被标记为 FAIL，触发从节点升级
*/
/*
* 集群状态同步
*
* Gossip 还用于：
* - 槽迁移进度同步
* - 新节点发现
* - 配置更新传播
*/
}
8.5 Gossip vs 一致性协议
┌─────────────────────────────────────────────────────────────────────────┐
│ Gossip vs 一致性协议对比 │
│ │
│ ┌──────────────┬──────────────┬──────────────┐ │
│ │ │ Gossip │ Paxos/Raft │ │
│ ├──────────────┼──────────────┼──────────────┤ │
│ │ 一致性强度 │ 最终一致 │ 强一致 │ │
│ │ 延迟 │ 不确定 │ 确定（有上界） │ │
│ │ 领导者 │ 无 │ 有 │ │
│ │ 成员变更 │ 简单 │ 复杂 │ │
│ │ 容错 │ 高 │ 中 │ │
│ │ 适用场景 │ 元数据、状态同步│ 核心业务数据 │ │
│ │ 带宽 │ O(N) │ O(N) │ │
│ └──────────────┴──────────────┴──────────────┘ │
│ │
│ 选择建议： │
│ - 需要强一致、确定延迟 → Paxos / Raft │
│ - 可以容忍最终一致、需要高可用 → Gossip │
│ - 元数据同步、成员管理 → Gossip │
│ - 核心业务数据 → Paxos / Raft │
│ │
└─────────────────────────────────────────────────────────────────────────┘
九、高频面试题
Q1: Paxos 和 Raft 的核心区别是什么？Raft 解决了 Paxos 的什么问题？
Paxos 和 Raft 的核心区别在于Leader 的设计。Paxos 允许多个 Proposer 同时提议，需要处理活锁问题；而 Raft 强制要求有且只有一个 Leader，所有写操作必须经过 Leader。
Raft 解决了 Paxos 的可理解性问题。Paxos 论文极其简洁（只有 8 页），但极其难懂，工程师实现时容易出错。Raft 将问题分解为三个独立子问题（领导选举、日志复制、安全性），每一步都有明确的操作指引，更容易正确实现。Raft 还解决了活锁问题：通过强 Leader 和随机退避，避免多个节点同时竞争提议权。
Q2: Paxos 的活锁问题是什么？如何解决？
活锁是指数个 Proposer 不断用更高的提案编号抢占，但都无法完成 Accept 阶段。场景：P1 发出 Prepare(5) 成功后，P2 发出 Prepare(6) 让 P1 的 Accept 被拒绝；P1 失败后用 Prepare(7) 重试，又让 P2 的 Accept 被拒绝，如此循环往复。
解决方案有三个：① 随机退避：Proposer 失败后等待随机时间再重试，降低竞争概率；② Leader 选举（Multi-Paxos）：选举一个 Leader 作为唯一的 Proposer，其他节点只作为 Acceptor；③ 提案编号分配策略：让每个 Proposer 使用不同的编号空间（如 P1 用 1,4,7…，P2 用 2,5,8…），减少冲突。
Q3: ZAB 和 Raft 有什么异同？
相同点：都是类 Paxos 的共识算法，都采用领导者模式，都通过多数派投票保证一致性，都需要处理 Leader 选举和日志同步。
不同点主要有：① Leader 选举比较值不同：Raft 比较 lastLogTerm + lastLogIndex，ZAB 比较 zxid（事务 ID）；② 状态机不同：ZAB 只有 LOOKING/LEADING/FOLLOWING 三种状态，Raft 有 Leader/Follower/Candidate；③ 日志提交条件：Raft 需要新 Leader 等待当前任期日志被复制到多数节点后才能提交（避免提交旧任期日志被覆盖），ZAB 的 zxid 设计天然保证了全局顺序；④ 应用场景：ZAB 专为零信任的 ZooKeeper 设计，Raft 适用范围更广。
Q4: 什么是线性一致性和顺序一致性？有什么区别？
线性一致性（Linearizability）是最强的一致性级别：操作按真实时间排序，任何读操作都能读到之前所有完成的写操作。简单说就是”所有操作在某个瞬间原子执行，所有人看到相同结果”。
顺序一致性（Sequential Consistency）稍弱：所有节点看到相同的操作顺序，但不保证是真实时间顺序。允许操作在节点间有延迟，只要最终大家看到的顺序一致即可。
区别：线性一致性有物理时钟约束，操作按全局时钟排序；顺序一致性只保证看到的顺序相同，时间顺序可以不同。例如 T1 时刻 P1 写入 x=1，T2 时刻 P2 读取到 x=0 是线性一致违规，但如果是顺序一致只要最终所有人看到的写顺序相同就合法。
Q5: Gossip 协议是如何工作的？为什么适合分布式系统？
Gossip 协议模拟病毒传播：每个节点定期随机选择几个节点交换信息（状态、版本等），收到信息的节点再继续传播给其他节点。信息以 O(log N) 的速度扩散，最终所有节点都拥有完整信息。
适合分布式系统的原因：① 去中心化：无需协调者，任何节点都可以随时加入/离开；② 高容错：部分节点故障不影响整体传播；③ 可扩展：收敛时间是 O(log N)，与集群规模对数相关；④ 实现简单：只需要定期随机选择节点交换信息。缺点是只能达到最终一致，不保证确定性的收敛时间。
Redis Cluster 用 Gossip 做节点存活检测和集群状态同步，DynamoDB/Cassandra 用 Gossip 做成员关系和元数据同步。
Q6: FLP 不可能定理是什么？它对分布式系统设计有什么影响？
FLP 不可能定理（Fischer-Lynch-Paterson, 1985）指出：在完全异步的分布式系统中，如果至少有一个节点可能故障，那么不存在一个确定性的共识算法能够保证在有限时间内所有非故障节点达成一致。
它的实际影响是：所有实用的共识算法（Paxos、Raft、ZAB）都通过引入超时机制打破异步假设。超时不是 FLP 定理范围内的确定性保证，但在实践中提供了活性保证。此外，随机化算法（如一些拜占庭容错算法）可以绕过 FLP 限制，但需要额外的随机源。
参考链接：