Paxos协议

Paxos 协议：分布式一致性的经典解决方案

在分布式系统中，多个节点通过消息传递协同工作时，如何就某个值达成一致（如数据更新、主节点选举）是核心挑战。Paxos 协议是解决这一问题的经典算法，由 Leslie Lamport 提出，其设计目标是在节点可能崩溃（但不会恶意篡改消息）的情况下，保证分布式系统的一致性。

分布式系统中，节点可能因网络延迟、崩溃等原因导致状态不一致。Paxos 协议需解决的问题是：让所有节点对某个 “提议”（如一条日志、一个决策）达成一致，即使部分节点故障，最终仍能确定一个唯一的结果。

Paxos 协议不解决 “拜占庭将军问题”（节点恶意发送虚假消息），其前提是：

Paxos 协议中，节点被划分为三种角色（同一节点可同时承担多个角色）：

角色	功能描述
Proposer（提议者）	提出 “提议”（Proposal），每个提议包含一个唯一编号（Proposal ID）和提议值（Value）。
Acceptor（接受者）	接收并判断提议，决定是否接受。只有当提议被多数 Acceptor 接受时，该提议才算 “通过”。
Learner（学习者）	不参与提议过程，仅学习已通过的提议，同步最终一致的结果（如从 Acceptor 获取通过的提议）。

Paxos 协议通过 “准备（Prepare）” 和 “批准（Accept）” 两个阶段，确保最终只有一个提议被通过，且所有节点对此达成一致。

Proposer 发起提议前，需先确认自身提议的编号足够大，避免与其他提议冲突。

Proposer 动作：
- 选择一个全局唯一的提议编号 n（编号需递增，确保后续提议编号更大）；
- 向所有 Acceptor 发送 Prepare(n) 消息，请求确认是否可以用编号 n 发起提议。
Acceptor 动作：
- 维护两个状态：max_n（已响应的最大提议编号）、accepted_n（已接受的提议编号）、accepted_v（已接受的提议值）；
- 若收到的n > max_n：
  - 更新 max_n = n，承诺不再响应编号小于 n 的提议；
  - 回复 Promise(n, accepted_n, accepted_v) 消息，告知 Proposer 自己已接受的提议（若有）；
- 若 n <= max_n：忽略该消息（遵守之前的承诺）。

Proposer 收到多数 Acceptor 的 Promise 响应后，进入批准阶段，确定最终提议值并请求 Acceptor 接受。

Proposer 动作：
- 若多数 Acceptor 回复了Promise：
  - 检查响应中是否有已接受的提议（accepted_v）。若有，选择其中编号最大的 accepted_v 作为本次提议值；
  - 若没有已接受的提议，Proposer 自行决定提议值 v；
- 向所有 Acceptor 发送 Accept(n, v) 消息，请求接受编号为 n、值为 v 的提议。
Acceptor 动作：
- 若收到的n >= max_n（不违背之前的承诺）：
  - 接受该提议，更新 accepted_n = n、accepted_v = v；
  - 回复 Accepted(n, v) 消息，确认接受；
- 若 n < max_n：忽略该消息。

当一个提议被多数 Acceptor 接受（即收到多数 Accepted 响应），该提议正式 “通过”。

若多个 Proposer 同时发起提议，可能导致彼此的提议编号相互覆盖，陷入 “提议 - 被拒 - 再提议” 的循环（活锁）。

解决方案：选举一个唯一的 “Leader Proposer”，所有提议由 Leader 发起。Leader 崩溃后重新选举，避免多 Proposer 竞争。

Paxos 协议是分布式系统一致性的基础，许多主流技术均基于其思想实现：