共识算法之Paxos 协议

基本概念

• 角色
  • 提议者（Proposer）：提出提案（Proposal），提案由提案编号和提案值两部分组成。通常在分布式系统中，当有节点需要确定某个值时，就会以提议者的身份提出提案。
  • 接受者（Acceptor）：负责处理接收到的提案，可以对提案进行投票。接受者根据一定的规则决定是否接受提案。
  • 学习者（Learner）：不参与提案的提出和投票过程，而是从接受者那里学习已经被选定的提案，最终获取达成一致的值。
• 提案：一个提案用二元组  表示，其中  是提案编号，具有全局唯一性和顺序性； 是提案的值，即需要达成共识的值。
• 选定（Chosen）：当一个提案被半数以上的接受者接受时，这个提案就被选定，意味着分布式系统中的各个节点就该提案的值达成了一致。

运行过程

准备阶段

1. 提议者发送准备请求：提议者选择一个提案编号 ，并向所有接受者广播准备请求（Prepare Request），请求内容包含提案编号 。
2. 接受者响应准备请求：接受者接收到准备请求后，如果该提案编号  大于它之前响应过的所有提案编号，那么接受者会承诺不再接受编号小于  的提案，并返回它已经接受过的编号最大的提案信息（如果有）；如果  不大于之前响应过的最大编号，则可以忽略该请求。

接受阶段

1. 提议者发送接受请求：如果提议者收到了半数以上接受者的响应，那么它会根据这些响应来确定提案的值。如果接受者的响应中包含了已经接受过的提案信息，提议者会选择其中编号最大的提案的值作为新提案的值；如果没有，则提议者可以自行选择一个值 。然后，提议者向所有接受者广播接受请求（Accept Request），请求内容为 。
2. 接受者处理接受请求：接受者接收到接受请求后，如果它之前已经承诺会接受该提案编号  的提案，并且没有接受过编号大于  的提案，那么它就会接受该提案；否则，它可以忽略该请求。
3. 提案选定：当一个提案  被半数以上的接受者接受时，该提案就被选定，此时学习者可以从接受者那里学习到这个被选定的提案值。

约束条件

• 安全性：
  • 只有被提出的提案才能被选定。
  • 只能有一个值被选定。
  • 一个节点在得知一个值被选定后，不能再认为另一个值被选定。
• 活性：最终总会有一个提案被选定，并且学习者能够学习到这个被选定的值。

优缺点

• 优点
  • 容错性：Paxos 协议能够在部分节点出现故障（只要超过半数的接受者正常工作）的情况下，依然保证达成共识，具有较高的容错能力。
  • 理论基础坚实：Paxos 协议是第一个被严格证明在分布式环境中能够正确工作的共识算法，为后续的分布式共识算法研究奠定了基础。
• 缺点
  • 实现复杂：Paxos 协议的原始描述和实现比较复杂，尤其是在处理多个提案同时提出、节点故障恢复等情况时，实现难度较大。
  • 性能问题：由于需要多次消息交互（准备阶段和接受阶段），在网络延迟较大的情况下，会影响协议的执行效率。

应用场景