Paxos算法（一）

Basic Paxos算法核心机制

Basic Paxos通过二阶段提交（Prepare阶段和Accept阶段）实现分布式共识，确保多个节点对某个值达成一致。其核心在于角色分工和提案编号的严格比较：

• 角色分工
  • Proposer：发起提案（含提案编号和值），协调共识过程。
  • Acceptor：投票并存储已接受的提案，需满足“大多数”原则（多数派通过）。
  • Learner：被动学习最终共识值，不参与投票。
• 提案规则 提案格式为 [n, v]，其中 n 是全局唯一的提案编号，v 是提议值。Acceptor仅接受编号不小于其承诺的最小编号的提案。

解决思考题的共识流程

针对客户端1（提案 [1, 3]）和客户端2（提案 [5, 7]）并发创建只读变量 X 的场景：

Prepare阶段

1. 客户端1向节点A、B发送 Prepare(1)，客户端2向节点C发送 Prepare(5)。
   • 节点A、B响应“尚无提案”，承诺不再接受编号 ≤1 的提案。
   • 节点C响应“尚无提案”，承诺不再接受编号 ≤5 的提案。
2. 客户端2向节点A、B发送 Prepare(5)（编号更高），节点A、B更新承诺为拒绝编号 ≤5 的提案。 客户端1向节点C发送 Prepare(1) 被忽略（编号低于C的承诺）。

Accept阶段

1. 客户端1收到多数派（A、B）响应，发送 Accept([1, 3])，但被所有节点拒绝（编号1 < 承诺的5）。
2. 客户端2收到多数派（A、B、C）响应，发送 Accept([5, 7])，所有节点接受该提案，达成共识值 X=7。

关键设计要点

1. 容错性 基于“大多数”原则（如3节点中需2个同意），允许少数节点故障时仍能达成共识。
2. 避免活锁 提案编号严格递增确保高编号提案最终被接受，避免低编号提案无限竞争。
3. 值传递规则 Proposer在Accept阶段必须选择Prepare响应中最高编号对应的值（若存在），否则使用自己的值。此机制保证已通过的提案不会被覆盖。

Multi-Paxos的优化方向

Basic Paxos的局限性在于每次共识需完整的两阶段提交，Multi-Paxos通过以下改进提升性能：

1. 选举稳定Leader：减少Proposer竞争，避免频繁Prepare阶段。
2. 日志复制：连续执行多个Basic Paxos实例，复用同一提案编号区间。

应用建议

• 实现要点
  • 确保提案编号全局唯一且单调递增（如时间戳+节点ID）。
  • Acceptor需持久化存储承诺的最高编号和已接受的值。
• 扩展场景 当需要连续共识（如日志复制）时，可结合Leader选举（类似Raft）优化性能，但需额外解决Leader故障转移问题。