分布式共识算法
共识算法是分布式系统的核心，用于在多个节点之间就某个值达成一致。
FLP 不可能性
定理内容
FLP定理是分布式系统领域最重要的理论结果之一，由Fischer、Lynch和Paterson于1985年证明。
定理内容：在异步分布式系统中，即使只有一个节点可能发生故障，也不存在能够始终正确终止的确定性共识算法。
实际意义
虽然FLP证明了完美的共识算法不存在，但在实际系统中我们可以通过以下方式近似解决：
- 使用超时：添加超时机制，避免无限等待
- 随机化：使用随机化算法降低最坏情况概率
- 弱化活性：允许短暂的不可用换取一致性
Paxos 算法
Paxos是Leslie Lamport提出的共识算法，被认为是"分布式共识的代名词"。
算法角色
| 角色 | 职责 |
|---|---|
| Proposer | 发起提案（提议值） |
| Acceptor | 决策是否接受提案 |
| Learner | 学习被接受的提案 |
算法流程
Paxos 实现
// 简化的Paxos实现
class PaxosNode {
private String nodeId;
private int proposalNumber = 0;
private String acceptedValue = null;
private int acceptedProposalNumber = -1;
// 接收准备请求
public Promise prepare(int n) {
if (n > proposalNumber) {
proposalNumber = n;
// 返回之前接受的提案（如果有）
return new Promise(n, acceptedProposalNumber, acceptedValue);
}
// 拒绝（已有更新的提案）
return new Promise(n, -1, null);
}
// 接收接受请求
public Accepted accept(int n, String value) {
if (n >= proposalNumber) {
proposalNumber = n;
acceptedValue = value;
acceptedProposalNumber = n;
return new Accepted(n, true);
}
return new Accepted(n, false);
}
}
// Paxos共识过程
class PaxosConsensus {
private List<PaxosNode> acceptors;
private int quorum; // 多数派数量
public String propose(String value) {
// 1. 生成唯一的提案编号
int proposalNumber = generateProposalNumber();
// 2. 准备阶段：收集多数派承诺
List<Promise> promises = sendPrepare(acceptors, proposalNumber);
// 3. 检查是否有已接受的提案
Promise latest = findLatestPromise(promises);
if (latest.getAcceptedValue() != null) {
// 使用已接受的提案值
value = latest.getAcceptedValue();
}
// 4. 接受阶段：请求多数派接受
List<Accepted> accepted = sendAccept(acceptors, proposalNumber, value);
// 5. 检查是否达成共识
if (countAccepted(accepted) >= quorum) {
return value; // 共识达成
}
// 6. 共识未达成，重试
return propose(value);
}
}
Multi-Paxos
Multi-Paxos是Paxos的优化版本，用于在分布式系统中实现连续的共识：
// Multi-Paxos：连续共识
class MultiPaxosLog {
private int logIndex = 0;
private Map<Integer, String> log = new HashMap<>();
private int committedIndex = -1;
// 客户端请求
public void append(String command) {
// 1. 选择Leader（使用Paxos）
String leader = electLeader();
// 2. Leader直接接受命令（跳过准备阶段）
int index = logIndex++;
accept(leader, index, command);
// 3. 复制到其他节点
replicateToAll(index, command);
// 4. 多数派确认后提交
if (replicatedToMajority(index)) {
committedIndex = index;
}
}
}
Raft 算法
Raft是另一种流行的共识算法，相比Paxos更易于理解和实现。
算法概述
Raft将共识问题分解为三个子问题：
Leader 选举
// Raft节点状态
enum NodeState {
FOLLOWER, // 跟随者
CANDIDATE, // 候选人
LEADER // 领导者
}
// Raft节点
class RaftNode {
private NodeState state = NodeState.FOLLOWER;
private long currentTerm = 0; // 当前任期
private String votedFor = null; // 投票给谁
private String leaderId = null; // 当前Leader ID
// 选举超时计时器
private long electionTimeout;
private long lastHeartbeatTime;
// 处理心跳
public void handleRequestVote(RequestVote request) {
// 1. 如果term更大，更新自己的term
if (request.getTerm() > currentTerm) {
currentTerm = request.getTerm();
state = NodeState.FOLLOWER;
votedFor = null;
}
// 2. 判断是否投票
boolean voteGranted = false;
if (request.getTerm() >= currentTerm) {
// 尚未投票，或投票给请求者
if (votedFor == null || votedFor.equals(request.getCandidateId())) {
// 检查日志是否足够新
if (isLogNewer(request.getLastLogTerm(), request.getLastLogIndex())) {
voteGranted = true;
votedFor = request.getCandidateId();
}
}
}
// 3. 响应
sendResponse(new RequestVoteResponse(currentTerm, voteGranted));
}
// 成为候选人并发起选举
public void startElection() {
state = NodeState.CANDIDATE;
currentTerm++; // 增加term
votedFor = nodeId; // 投票给自己
// 并行发送投票请求
for (RaftNode node : cluster) {
if (!node.equals(this)) {
sendRequestVote(node, new RequestVote(currentTerm, nodeId, lastLogTerm, lastLogIndex));
}
}
// 等待投票结果...
}
}
日志复制
// 日志条目
class LogEntry {
private long term; // 任期号
private long index; // 日志索引
private String command; // 命令
private boolean committed; // 是否已提交
}
// 日志复制流程
class LogReplication {
// Leader处理客户端请求
public void appendEntries(String command) {
// 1. 添加到本地日志
LogEntry entry = new LogEntry(currentTerm, nextIndex.get(nodeId), command);
log.add(entry);
// 2. 并行复制到所有跟随者
Map<RaftNode, Integer> nextIndices = new HashMap<>();
for (RaftNode follower : cluster) {
if (!follower.equals(this)) {
// 从nextIndex开始复制
List<LogEntry> entries = log.subList(nextIndices.get(follower), log.size());
sendAppendEntries(follower, entries);
}
}
// 3. 多数派确认后提交
if (countReplicated() >= majority) {
commit(log.size() - 1);
}
}
// 跟随者处理日志条目
public AppendEntriesResponse handleAppendEntries(AppendEntries request) {
// 1. 检查term
if (request.getTerm() < currentTerm) {
return new AppendEntriesResponse(currentTerm, false);
}
// 2. 检查日志一致性
if (!matchLog(request.getPrevLogIndex(), request.getPrevLogTerm())) {
return new AppendEntriesResponse(currentTerm, false);
}
// 3. 添加新日志条目
for (LogEntry entry : request.getEntries()) {
if (!log.get(entry.getIndex()).equals(entry)) {
// 删除不匹配的条目及其后的条目
log.subList(entry.getIndex(), log.size()).clear();
log.add(entry);
}
}
// 4. 更新commitIndex
if (request.getLeaderCommit() > commitIndex) {
commitIndex = Math.min(request.getLeaderCommit(), log.size() - 1);
}
return new AppendEntriesResponse(currentTerm, true);
}
}
Raft vs Paxos
| 特性 | Paxos | Raft |
|---|---|---|
| 复杂性 | 难以理解 | 更易于理解 |
| 领导人 | 无明确Leader | 有明确的Leader |
| 日志 | 分散 | 集中管理 |
| 可理解性 | 难 | 易 |
| 实现难度 | 困难 | 相对简单 |
ZAB 协议
ZAB是ZooKeeper使用的原子广播协议，与Raft类似但有一些细节差异。
ZAB 工作流程
共识算法的选择
| 场景 | 推荐算法 | 典型系统 |
|---|---|---|
| 配置管理 | Raft | Etcd, Consul |
| 分布式协调 | ZAB | ZooKeeper |
| 分布式存储 | Multi-Paxos | Chubby |
小结
本章我们深入学习了分布式共识算法：
-
FLP不可能性
- 异步分布式系统中无法同时满足安全性和活性
- 实际系统中通过超时、随机化等近似解决
-
Paxos算法
- 共识问题的经典解法
- Prepare和Accept两个阶段
- Multi-Paxos用于连续共识
-
Raft算法
- 更易于理解的共识算法
- Leader选举、日志复制、安全性
- 分离的领导人选举和日志复制
-
ZAB协议
- ZooKeeper使用的原子广播协议
- 发现、同步、广播三个阶段
-
算法选择
- 小规模集群：Raft、ZAB
- 大规模系统：考虑分层共识