一致性协议

一致性协议

一致性协议（Consensus Protocol）是分布式系统中多个节点就某个值或状态达成一致的算法。它是构建可靠分布式系统的核心，确保即使部分节点故障或网络分区，系统仍能维持数据一致性和正确性。常见应用包括数据库复制、区块链、分布式存储等。

基本概念

在分布式系统中，节点间需要通过通信协作完成任务。由于网络延迟、节点故障等因素，各节点可能观察到不同数据状态。一致性协议的目标是：

• 安全性（Safety）：所有正确节点最终达成相同决定。
• 活性（Liveness）：系统最终能做出决定（不无限阻塞）。

典型问题如拜占庭将军问题描述：如何让分散的将军（节点）在存在叛徒（故障节点）时达成一致进攻或撤退的决定。

常见协议

1. Paxos

由Leslie Lamport提出，分为准备阶段和接受阶段：

1. 提案者（Proposer）向接受者（Acceptor）发送提案编号。
2. 接受者承诺不接受比当前编号更小的提案。
3. 提案者收到多数派接受后发送提案值。

# 简化版Paxos伪代码
class Acceptor:
    def __init__(self):
        self.promised_id = 0
        self.accepted_value = None

    def prepare(self, proposal_id):
        if proposal_id > self.promised_id:
            self.promised_id = proposal_id
            return {"status": "promised", "accepted_value": self.accepted_value}
        return {"status": "rejected"}

    def accept(self, proposal_id, value):
        if proposal_id >= self.promised_id:
            self.accepted_value = value
            return {"status": "accepted"}
        return {"status": "rejected"}

2. Raft

更易理解的替代方案，将节点分为Leader、Follower和Candidate三种角色：

• Leader处理所有客户端请求并复制日志。
• Follower被动接收更新。
• Candidate参与选举。

stateDiagram-v2 [*] --> Follower Follower --> Candidate: 选举超时 Candidate --> Leader: 获得多数票 Leader --> Follower: 发现更高任期 Candidate --> Follower: 发现更高任期

3. PBFT（实用拜占庭容错）

解决拜占庭故障（节点可能恶意响应），需至少3f+1个节点容忍f个故障节点。分三阶段：

1. 客户端向主节点发送请求。
2. 主节点广播至备份节点。
3. 节点执行请求并回复客户端。

数学基础

共识协议通常满足以下条件：

• 协定性（Agreement）：所有正确节点决定相同值。
• 完整性（Integrity）：每个节点最多决定一个值。
• 有效性（Validity）：若某节点决定值v，则v必由某节点提出。

形式化表示为： $\mathrm{\forall }p,q\in \text{Correct}:{\text{decision}}_p={\text{decision}}_q$

实际案例

案例1：Etcd中的Raft

Kubernetes使用Etcd存储集群状态，其Raft实现保证：

• Leader选举：5秒内完成故障转移。
• 日志复制：所有写操作需多数节点确认。

案例2：比特币的Nakamoto共识

通过工作量证明（PoW）实现概率性共识：

• 矿工竞争解哈希难题。
• 最长链被接受为有效历史。

挑战与权衡

协议对比

协议	故障模型	消息复杂度	延迟
Paxos	崩溃故障	O(n²)	2轮RTT
Raft	崩溃故障	O(n)	1轮RTT
PBFT	拜占庭	O(n²)	3轮RTT

进阶主题

• 最终一致性（Eventual Consistency）：如DNS系统，允许临时不一致。
• CAP定理：一致性（Consistency）、可用性（Availability）、分区容忍（Partition Tolerance）三者不可兼得。
• 量子共识：未来可能利用量子纠缠实现超快共识。