分布式 Paxos算法总结

前言

参考文献

《图解超难理解的 Paxos 算法（含伪代码）》
《【超详细】分布式一致性协议 - Paxos》

Basic-Paxos @ 基础帕克索斯算法

Paxos算法是目前公认解决分布式一致性问题的最有效算法之一，甚至可以说它是过去几十年里一切分布式一致性算法的源头。我们对Paxos算法进行描述时通常都会带上“容错&共识”两个关键字，那么它们具体代表的是什么呢？

容错：是指分布式系统在部分节点宕机的情况下依然能够对外提供服务，即CAP理论中的分区容错性；
共识：是指分布式系统的各节点都能就某个操作达成共识，即所有节点都批准执行这个操作。例如在分布式系统中操作A/B都想访问某服务，那么令集群中的所有（超半数/自定义数量）服务都批准执行操作A/B的的过程就是所谓的达成共识。

概念

在正式对流程进行阐述之前，我们需要先对Paxos算法的各类角色&变量进行讲解。Paxos算法具有四类角色…其名称/作用具体如下：

client @ 客户端：负责向提案者发送操作请求；
proposer @ 提案者：提案者负责接收&封装客户端的操作请求为proposal @ 提案，并为之生成全局唯一&增长的编号。随后向各接收者广播准备/接收请求，并根据其返回的通过/批准情况决定是否继续发送接收请求/判定其已达成一致；
acceptor @ 接收者：接收者负责对准备&接收请求中的提案进行判定，以决定是否通过/批准该提案；
learner @ 学习者：学习者负责获取已达成共识的提案并应用于分布式系统中。

Paxos算法具有三类“持久化”变量…其名称/作用具体如下：

maxProposal @ 最大提案：接收者在准备请求中通过的最大提案编号；
acceptedProposal @ 已批准提案：接收者在接收请求中批准的最大提案编号；
acceptedValue @ 已批准值：接收者在接收请求中批准的最大提案值。

流程

Paxos算法的流程分为“批准/获取”两个部分，这其中“批准”部分负责提案的实际批准，具体又可分为“准备/接收”两个阶段；而“获取”部分则负责提案批准后的对外开放。关于提案批准的完整流程具体如下：

prepare @ 准备阶段：提案者在接收到客户端的操作请求后，其会将之封装为提案并为之生成全局唯一&增长的编号，关于全局编号的具体生成方式此处不予讨论；
提案者会向各接收者广播（即全体发送）准备（当前提案编号）请求；
各接收者在收到准备（当前提案编号）请求后会比较“当前提案编号”和“最大提案”的大小，如果“当前提案编号” > “最大提案”则记录“最大提案”为“当前提案编号”并返回通过回应。而如果该接收者曾chosen @ 选中/批准过某项提案，则“已批准提案/已批准值”会随通过回应一同返回；否则便会无视请求/返回拒绝回应。而在未能收到超过半数/自定义数量通过回应的情况下，提案者会为提案生成重新新编号并再次开始流程；
accept @ 接收阶段：提案者在收到超过半数/自定义数量的通过回应后会向接收者广播接收（当前提案编号&当前提案值）请求。如果在之前的准备请求回应中存在“已批准值”，那么在接收请求中携带的“当前提案值”就必须应用该值；否则就由当前提案者负责自定义。通过该规则可以得知：Paxos算法只支持单个值/操作的共识；
各接收者在收到接收（当前提案编号&当前提案值）请求后会再次比较“当前提案编号”与“最大提案”的大小，如果“当前提案编号” >= “最大提案”则记录“已批准提案&已批准值”为“当前提案编号&当前提案值”，并将“当前提案编号”返回，意味着已批准当前提案；否则便将原本的“最大提案”返回；
提案者在收到超过半数/自定义数量的“当前提案编号”后便会认为各接收者已对当前提案达成共识，至此该提案便可以被学习者所获取&应用于分布式系统了；否则便意味着当前提案被否决，提案者需要为提案重新生成新编号以再次开始流程。

当提案达成共识后，如何让学习者获取该提案也是值得细究的问题。提案获取通常有以下几种方案：

全量发送：接收者一旦批准提案便将该提案广播给所有学习者。这种做法虽然可以让学习者尽快的获得批准提案，但是却需要每个接收者与所有学习者逐一进行通信，通信次数为二者乘积，所以效率较低；
主从同步：选定主学习者，提案批准后由接收者通知主学习者，并由主学习者负责通知其它的学习者。这个方案虽然多了一个步骤，但是通信次数大大降低，通信次数为学习者的数量。该方案同时引出另一个问题：主学习者随时可能出现故障。
多主从同步：在主从同步的基础上，由单个主学习者扩展成一个主学习者集合。集合中学习者数量越高，可靠性也越好。

模拟

为了更好的熟悉Paxos算法，此处我们举例描述Paxos算法“提案批准”的完整过程，该案例中的Paxos集群共有A/B/C三个节点。注意！这里的任意节点都可同时扮演提案者&接收者。

提案者A/B分别将X赋值成3/5的操作请求封装为提案，并为之生成全局唯一&增长的编号1/2，随后向各接收者广播。在准备阶段它们的交互结果如下：

在这里插入图片描述

提案者A/B分别进入准备阶段，并向各接收者广播准备（1/2）请求；
接收者A/B在收到提案者A的准备（1）请求后发现自身并没有通过/批准任何准备/接收请求，因此直接返回空的通过回应；
接收者C由于在收到&通过提案者B的准备（2）请求之后再收到提案者A的准备（1）请求，并且提案者B的提案编号2大于提案者A的提案编号1，因此无视了准备（1）请求/返回了拒绝回应；
接收者A/B在收到提案者B的准备（2）请求后由于其提案编号2 > 已通过的提案编号1，因此两者都会返回空的通过回应。

由于提案者A/B的准备请求都收到了超过半数的通过回应，因此提案者A/B都将进入Paxos算法的接收阶段。

在这里插入图片描述

提案者A向各接收者广播接收（1&3）请求。由于之前的通过回应中没有携带“已批准提案”，因此提案的值可以完全自定义；
接收者A/B/C在收到接收（1&3）请求后，由于其之前已经各自通过了准备（2）请求，因此其都会返回提案编号2来表示未曾批准该请求；
提案者A在收到回应后发现提案编号2比自己的提案编号1大，因此知晓自身提案未曾被批准，因此重新回到准备阶段进行协商；
提案者B向各接收者广播接收（2&5）请求。由于之前的通过回应中没有携带“已批准提案”，因此提案的值可以完全自定义；
接收者A/B/C在收到接收（2&5）请求后，由于其都未通过提案编号更大的准备请求，因此其都会返回提案编号2来表示批准了该请求；
提案者B在收到回应后发现提案编号2与自身提案编号相同且数量超过半数，因此判定接收者对该提案已达成共识，学习者可正式获取&应用该提案。

在提案批准的流程中还有一种常见的情况是接收者在已批准某项提案的情况下收到提案编号更大的准备请求，这种情况下其就需要在通过回应中返回已批准提案的编号&值…模拟如下：

在这里插入图片描述

提案者B向各接收者广播接收（3&6）请求；
接收者A收到&批准了提案者B的接收（3&6）请求；
提案者A向各接收者广播准备（4）请求；
接收者B/C收到&通过提案者A的广播准备（4）请求，并因此未批准提案者B的接收（3&6）请求；
接收者A收到&通过提案者A的准备（4）请求，并在通过回应中携带了已批准提案编号&值（3&6）；
提案者B判定接收者未能就提案达成共识，重新进入准备阶段；
提案者A因为收到超过半数的通过请求而进入接收阶段，向各接收者广播接收（4&6）请求。这其中6是因为在之前接收者A的通过回应中包含有已批准提案值，因此该值便被作为了提案者A的提案值；
接收者A/B/C收到&批准了接收（4&6）请求，提案者A判定各接收者已就该提案达成共识。

Multi-Paxos算法 @ 多帕克索斯算法

原始的Basic-Paxos算法只能达成一个值/操作的共识，而Leslie Lamport则提出可以通过多次执行Basic-Paxos算法来达成一系列值/操作的共识。但由于多次协商会增加通信开销&影响协商活性（即指协商进入死循环），因此Leslie Lamport则进一步提出了名为Multi-Paxos算法的解决方案。

Multi-Paxos算法对于Basic-Paxos算法的主要区别在于其引入了领导提案者的概念。在Multi-Paxos算法中，提案（准备&接收）请求的发送是由领导提案者专属负责的。Multi-Paxos系统会在启动时先通过Basic-Paxos算法从各提案者中选举出唯一的领导提案者用于“串行”发送提案请求，这样就能避免并发提交而解决Basic-Paxos算法的活锁（接收者不断通过编号更大的提案而导致无法批准已通过的旧提案，该问题正常情况下可通过随机延迟的方式进行缓解）问题。此外由于领导提案者会连续发送提案请求，因此除去首个提案请求需要完整执行准备&接收两个阶段（为了应对网络分区而保留，否则也可以不执行）外，后续提案请求的发送都可以只执行接收阶段，从而便能减少RPC来提升共识的达成效率。

Multi-Paxos算法可以支持多领导提案者并存的场景。在实际的Multi-Paxos系统中，由于网络分区情况的存在，其可能出现选举出多个领导提案者的情况。对于这种情况Multi-Paxos算法是提供支持的，因为如此一来其会自动退化成Basic-Paxos算法的多次执行场景。

领导提案者的宕机会导致Multi-Paxos系统不可用。对于一个功能完善的Multi-Paxos系统，其应该具备对领导提案者的故障监测&转移功能。理论上，领导提案者需要不断向系统中的其它节点发送心跳以表示自身存活，而一旦在指定时间内未收到心跳（及一系列综合性盘点），那么Multi-Paxos系统就会判定领导提案者已经宕机。这种情况下其就会选举新的领导提案者来代替工作，即使旧领导提案者只是因为网络分区而无法连接。而在不存在可用提案者的情况下，Multi-Paxos系统将陷入不可用的状态。