难过又厉害的 Paxos

Basic Paxos

角色定义

• Proposer 提议者

• Acceptor 接受者

• Learner 学习者

Proposer 提议者

提出提案，用于投票表决，提案包括提案编号和提案内容

Acceptor 接受者

对每个提议值进行投票，并存储接受的值。

Learner 学习者

接受已达成共识的值，并存储保存，不参与投票的过程。

三个阶段

1. Prepare： P 向 A 发出 prepare 请求，A 针对收到的请求进行 Promise 承诺

2. Accept：P 收到大多数 A 的 Pomise 后，向 A 发出 propose 请求，A 收到 Propose 请求进行 Accept 处理

3. Learn：P 收到大多数 A 的 Accept 后，证明本次提案成功，向 L 发送这次提案内容进行同步

两个承诺一个应答

1. 承诺不接受小于等于当前提案编号的 prepare 请求（在第一个阶段的那个请求）

2. 承诺不接受小于当前提案编号的 accept 请求（在第二个阶段的那个请求）

3. 如果接受者之前已经有通过的提案，那么准备请求的应答中包含已经通过的最大编号的提案信息

过程描述

准备阶段

image.png

1. 提案者 A 和 B 分别在不同的时间不同提案编号的 prepare 请求

2. XYZ 接受者在不同时间收到 prepare 请求并进行反馈

3. 只有 Z 接受者由于网络延迟，2 号提案在 4 号提案之后才收到，由于承诺过，所以不做应答（承诺不接受小于等于当前提案编号的 prepare 请求，当前为 4，收到为 2）

接受阶段

image.png

1. 提案者 A 发现有之前的 prepare 有两个回复，所以发送 Accept 请求；提案者 B 发现之前的 prepare 有三个回复，所以同样发送 Accept 请求（只要收到大多数回复即可）

2. XYZ 接受者收到 Accept 请求并进行反馈

3. 对于 2 号提案，XYZ 三个接受者均直接忽略（承诺不接受小于当前提案编号的 accept 请求 ）；对于提案 4，XYZ 三个接受者均回复 ACCEPTED

学习阶段

1. 当接受者通过一个提案时，就通知所有的学习者

2. 学习者发现大多数接收者都通过了某个提案，那么自己也接受该提案

一些重要条件

• 节点可以处于多个角色

• 节点必须要知道当前整个集群中多数节点是多少

• 节点必须持久化接受的数据，不能忘记自己之前接受过的提案

• 节点必须按照规则去达成自己的承诺

• paxos run 目标是达成一个共识，一次达成一个

Multi Paxos

Basic Paxos 的不足

• 一次只能达成一个共识，如果需要达成多个共识，则需要多次执行

• 多次的同时执行会导致大量冲突，冲突后又需要重新进行提案然后重新准备通信消耗大

整体思路

• 想办法搞出一个领导者 Leader

• 当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段（也就是领导者直接发给所有接受者，接收到大多数接受者的返回时就认为成功）

• 主节点作为唯一提议者，这样就不存在多个提议者同时提案会冲突的情况了

Chubby 的 Multi-Paxos 实现

想法

总结

参考链接