Paxos 算法是非拜占庭容错的, 使用二阶段提交的分布式共识算法, 实现了共识和可用性.

Paxos 算法

组成

• Basic Paxos
• Multi-Paxos

概念

• 提案
• 准备（Prepare）请求
• 接受（Accept）请求
• 角色

三种角色

• 提议者（Proposer）, 提议一个值，用于投票表决。
• 接受者（Acceptor）, 对每个提议的值进行投票，并存储接受的值.
• 学习者（Learner）, 被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。

达成共识过程

1. 准备（Prepare）阶段

选择 提案编号 大的提案.

2. 接受（Accept）阶段

其他

二阶段提交用来实现:

• 分布式事务
  • 不能容错, 所有节点都同意才能进行
• Paxos 算法
  • 实现了容错, 大多数节点同意
• 本质上而言，提案编号的大小代表着优先级

根据提案编号的大小，接受者保证三个承诺，具体来说：

• 如果 准备请求 的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；
• 如果 接受请求 中的提案的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；
• 如果接受者之前有通过提案，那么接受者将承诺，会在 准备请求的响应 中，包含已经通过的最大编号的提案信息。