简介

Paxos 是分布式算法中的老大哥，可以说 Paxos 是分布式共识的代名词。最常用的分布式共识算法都是基于它改进。比如 Raft 算法

Paxos 算法主要包含两个部分：

• Basic Paxos 算法：多个节点之间如何就某个值达成共识。（这个值我们称作提案 Value）
• Multi-Paxos 算法：执行多个 Basic Paxos 实例，就一系列值达成共识。

角色

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
• Acceptor: 参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数

Acceptors的接受，则称该Proposal被批准。

• Learner: 不参与决策，从Proposers/Acceptors学习最新达成一致的提案(Value)。

流程

第一阶段：准备（Prepare）

1. 发起准备请求：
   • Proposer选择一个提案编号n，并向多数Acceptor发送带有该编号n的Prepare(n)请求。
2. 响应准备请求：
   • Acceptor收到Prepare(n)请求后，如果其还没有对任何编号大于或等于n的Prepare请求做出过承诺，则Acceptor会承诺不再响应编号小于n的Prepare请求，并将之前接收到的最大提案编号及其对应的值（如果有）回复给Proposer。

第二阶段：接受（Accept）

1. 发起接受请求：
   • Proposer根据收到的承诺信息确定一个提案值v，并向多数Acceptor发送带有编号n和提案值v的Accept(n, v)请求。
2. 响应接受请求：
   • 如果Acceptor没有对任何编号大于n的Accept请求做出过响应，则Acceptor接受提案，并存储提案值v，并回复确认给Proposer。