Basic Paxos

名词

client-客户端、proposer-提议者、proposal-提案、acceptor-接受者、learner-学习者

投票过程

client（客户端）向 proposer（提议者）发起一个 proposal（提案），由 proposer 向 acceptor 进行提议，整个投票过程涉及两个阶段：

prepare/promise 阶段

提议者向接受者们发送 prepare 消息（prepare 消息中只需含提案编号 N 即可），此时有如下两种情况

• 如果当前 N 大于当前接受者已经接受过的提案编号

接受者接受该 prepare 消息，并对 prepare 消息进行响应，响应的内容根据以下两种情况来区别：

①如果当前接受者此前从未通过任何提案，则响应：[没有提案]

②如果当前接受者此前曾经通过过提案，则响应：[原提案编号,原提案值]

同时接受者会进行承诺：不会再接受提案编号小于等于当前提案编号 N 的提案准备消息，不会通过其他编号小于当前提案编号 N 的提案；

• 如果当前 N 小于等于当前接受者已经接受过的提案编号

接受者拒绝接受该 prepare 消息

注意点：提议者在接收各个接受者的响应时，如果响应中含有接受者之前通过的提案信息则会选取各响应中提案编号最大的提案值，设置到自己提出的提案中，比如提议者自己原先的提案是[6,"hello"]，而接受者响应的信息中有：[4,"oh my god"]、[3,"congratulations"]、[5,"handsome boy"]，则原提案变为[6,"handsome boy"]

propose/accept 阶段

提议者向上一阶段中回复 prepare 消息的接受者发送 propose 消息，此时接受者们接收到 propose 消息，判断提案中的编号是否小于自己最新的承诺编号：

① 如果提案中的编号不小于当前接受者最新的承诺编号，则接受 propose 消息；

② 如果提案中的编号小于当前接受者最新的承诺编号，则拒绝 propose 消息；

最终提案是否通过的条件：提议者如果得到的 accept 响应中，接受者数大于接受者数的一半及以上，则提案通过，反之则提案失败；而当提案通过时，接受者会通知学习者，学习者将学习并接受接受者的最新提案。

故事案例

故事背景

羊村村委会最近在考虑立项建村 128 周年庆纪念活动，村委会的一些成员提议周年庆全村应该放假进行庆祝，将周年庆纪念活动放假提案写入羊村的村委条令中，但村委会中有两个不同的意见，一个是周年庆放 1 天假，一个是周年庆放 3 天假。羊村村长最后提出了建议，说：”你们各自派个提案代表咨询并通知到三个随机群众代表，最后群众代表同意放几天就放几天“，大家都觉得这个提议很好，便派出了代表鸭弟和狗哥进行抽签，鸭弟抽中了内容为"放假 1 天"的提案，狗哥抽中了内容为"放假 3 天"的提案，随后第二天他们分别向三个随机群众代表进行了咨询和通知。

未通过提案前提下

发送提案准备邮件

鸭弟和狗哥分别在第二天上午各个时间点向三个随机群众代表发送了村里准备要新增提案的邮件，提案的编号选用进行邮件发送的第一封邮件的时间点，群众代表也对应做出了响应，如下图所示：

① 11:00:00，鸭弟向喜羊羊发送了准备新增提案的邮件，喜羊羊由于之前没有接收过任何其他邮件，所以回了邮件并承诺：不会再接受提案编号小于等于当前提案编号 110000 的提案准备消息，不会通过其他编号小于当前提案编号 110000 的提案；

② 11:15:00，狗哥向喜羊羊发送了准备邮件，喜羊羊虽然此前收到了鸭弟的准备邮件并且做出了承诺，但由于狗哥的提案编号 111500 大于鸭弟的邮件编号 110000，所以喜羊羊向狗哥回复了邮件，并做出了对应承诺；

③ 11:20:00，鸭弟向懒羊羊发送了准备邮件，由于之前懒羊羊没有接收过任何其他邮件，所以回复了鸭弟邮件并做出了承诺；

④ 11:25:00，狗哥向懒羊羊发送了准备邮件，懒羊羊在 11:20:00 的时候收到了鸭弟的准备邮件并做出了承诺，但由于狗哥的提案编号 111500 大于鸭弟的邮件编号 110000，所以懒羊羊也向狗哥回复了邮件，并做出了对应承诺；

⑤ 11:30:00，狗哥向美羊羊发送了准备邮件，美羊羊此前没有接收过任何其他邮件，所以回复了狗哥邮件并做出了承诺；

⑥ 12:20:00，鸭弟向美羊羊发送了准备邮件，但由于鸭弟的邮件编号 110000 小于美羊羊在 11:30:00 时接收的狗哥的准备邮件编号，所以没有对鸭弟的邮件做出回复；

发送提案内容邮件

鸭弟和狗哥在通知了三个群众代表之后，将各自的规定内容以邮件的形式再次发送给了对应的群众代表，如下图所示：

① 12:30:00，鸭弟向喜羊羊发送了提案内容的邮件，由于之前喜羊羊最后承诺的是不会再接受提案编号小于等于狗哥的提案编号 111500 的提案准备消息，同时不会通过其他编号小于提案编号 111500 的提案，所以喜羊羊对鸭弟的提案内容的邮件没有做出回复；

② 12:35:00，狗哥向喜羊羊发送提案内容邮件，由于提案编号符合喜羊羊的承诺，所以喜羊羊接受了狗哥的提案且回复了狗哥的邮件；

③ 12:40:00，鸭弟向懒羊羊发送提案内容邮件，由于提案编号小于懒羊羊之前所承诺的编号，所以懒羊羊拒绝鸭弟的提案没有回复邮件；

④ 12:45:00，狗哥向懒羊羊发送提案内容邮件，提案编号符合懒羊羊之前的承诺规则，所以懒羊羊接受了狗哥的提案并回复了邮件；

⑤ 12:50:00，狗哥向美羊羊发送提案内容邮件，提案编号符合美羊羊之前的承诺规则，所以美羊羊也接受了狗哥的提案并回复了邮件；

（其中因为美羊羊在接收鸭弟的提案准备邮件的时候并没有回复鸭弟，所以鸭弟并没有给美羊羊发送提案内容邮件）

​ 至此，结合故事中准备承诺阶段和提议接受阶段的分析，我们可以看到，狗哥的提案被三个代表所接受，由于接受的人数占大多数（大于一半以上），最终狗哥的提案通过了。

以上是羊代表们此前没有通过任何提案的情况下，那么现在提案编号为 111500 提案内容为"放假 3 天"的提案通过后，如果此时有人发起了一次新提案内容的投票，那么羊代表们会对应做出什么举动呢？

​ 在鸭弟和狗哥与羊代表们沟通的过程中有群众觉得其实三天假期根本不够，于是提出多加一天的时间以便更好的准备周年庆，但是要通过就必须得到羊代表们的同意，所以群众立马派了代表猴哥进行沟通。

已通过提案前提下

发送提案准备邮件

猴哥在各个时间点向羊代表们发送提案准备邮件，邮件内容是提案编号 130000，此前由于羊代表们通过过提案【111500,"放假 3 天"】，所以羊代表们回复此前通过的提案编号最大的提案内容给猴哥，即回复【111500,"放假 3 天"】。

发送提案内容邮件

猴哥在查阅羊代表们的回复之后，才知道，原来羊代表们已经通过了提案【111500,"放假 3 天"】，所以便不再提出自己的建议【130000,"放假 4 天"】了，而是将所有羊代表们的回复中选取提案编号最大的提案的内容即提案值"放假 3 天"当成自己的提案发送给羊代表们，即猴哥发送的提案内容是：【130000,"放假 3 天"】，羊代表们也查阅了猴哥的提案内容邮件并进行了回复，最终羊代表们本身通过的最新的提案为【130000,"放假 3 天"】。

Multi Paxos

变化

Multi Paxos 主要就是执行多次 Basic Paxos，它与 Basic Paxos 的主要区别是引入 Leader 节点，提案都由 Leader 发起。

解决问题

由于 Basic Paxos 的 prepare/promise 阶段是为了解决发现接受者已经通过的提案值，而 Multi Paxos 因为提案都由 Leader 发起，所有也就没有必要进行 prepare/promise 阶段了，因为 Leader 的提案就是最新的。省去 prepare/promise 阶段，这样就减少了通讯次数，相当于对 Basic Paxos 进行了优化。