在过去几十年里,"Paxos 算法" 基本上是分布式共识的代名词,因为当前最常用的一批共识算法都是基于它改进的。比如,Fast Paxos 算法、Cheap Paxos 算法、Raft 算法等等。

兰伯特提出的 Paxos 算法包含 2 个部分:

可因为兰伯特提到的 Multi-Paxos 思想,缺少代码实现的必要细节(比如怎么选举领导者),所以在理解上比较难。

Basic Paxos

在我看来,Basic Paxos 是 Multi-Paxos 思想的核心,说白了,Multi-Paxos 就是多执行几次 Basic Paxos。

在 Basic Paxos 中,有提议者(Proposer)、接受者(Acceptor)、学习者(Learner)三种角色,他们之间的关系如下:

图片展示了Basic Paxos中提议者、接受者、学习者三种角色之间的关系。左侧有三个“提议者”云朵,分别指向三个“接受者”苹果,每个苹果又指向右侧一个“学习者”橙子。这体现了提议者向接受者提议,接受者再将提议结果告知学习者,学习者汇总结果这一流程,直观呈现了Basic Paxos算法中各角色的交互方式。

讲到这儿,你可能会有疑惑:前面不是说接收客户端请求的节点是提议者吗?这里怎么又是接受者呢?这是因为一个节点(或进程)可以身兼多个角色。想象一下,一个 3 节点的集群,1 个节点收到了请求,那么该节点将作为提议者发起二阶段提交,然后这个节点和另外 2 个节点一起作为接受者进行共识协商,就像下图的样子:

图片展示了Paxos算法中节点间的交互关系。左侧为客户端,向节点发送写请求;节点作为提议者/接受者,与两个接受者节点进行交互,接受者节点将成功信息反馈给节点,节点再将成功信息反馈给客户端。该图与上下文紧密相关,直观呈现了文档中提到的3节点集群中1个节点作为提议者发起二阶段提交,与另外2个节点一起作为接受者进行共识协商的场景。

其实,这三种角色,在本质上代表的是三种功能:

在 Basic Paxos 中,兰伯特也使用提案代表一个提议。不过在提案中,除了提案编号,还包含了提议值。为了方便演示,我使用[n, v]表示一个提案,其中 n 为提案编号,v 为提议值。

我想强调一下,整个共识协商是分 2 个阶段进行的(也就是二阶段提交)。那么具体要如何协商呢?

我们假设客户端 1 的提案编号为 1,客户端 2 的提案编号为 5,并假设节点 A、B 先收到来自客户端 1 的准备请求,节点 C 先收到来自客户端 2 的准备请求。

看第一个阶段,首先客户端 1、2 作为提议者,分别向所有接受者发送包含提案编号的准备请求:

图片展示了Paxos算法中准备请求阶段的时间线。左侧有客户端1和2作为提议者,分别向节点A、B、C发送准备请求,其中客户端1的请求为[1, ],客户端2的请求为[5, ]。右侧箭头表示请求发送方向,时间线从左至右表示时间流逝。该图与上下文紧密相关,直观呈现了上下文中提到的客户端1、2向节点A、B、C发送准备请求这一关键步骤,帮助理解Paxos算法中准备请求的发送情况。

要注意,在准备请求中是不需要指定提议的值的,只需要携带提案编号就可以了,这是很多同学容易产生误解的地方。

接着,当节点 A、B 收到提案编号为 1 的准备请求,节点 C 收到提案编号为 5 的准备请求后,将进行这样的处理:

图片展示了Paxos算法中准备阶段的时序图。左侧有客户端1和2作为提议者,分别向节点A、B、C发送准备请求,其中客户端1的请求为[1, ],客户端2的请求为[5, ]。右侧是节点A、B、C的准备响应,均显示“尚无提案”。图中还标注了各节点收到请求和发送响应的时间点,如节点A在收到客户端1请求后,于[1, ]时间点发送准备响应。该图直观呈现了准备阶段各节点间交互情况,与上下文对Paxos算法准备阶段的描述相契合。

另外,当节点 A、B 收到提案编号为 5 的准备请求,和节点 C 收到提案编号为 1 的准备请求的时候,将进行这样的处理过程:

图片展示了Paxos算法中节点A、B、C的准备请求与响应时间线。提案者(客户端1、2)分别发送准备请求[1, ]、[5, ]给接受者(节点A、B、C)。节点A、B收到[5, ]准备请求时,因提案编号5大于之前响应的准备请求编号1且无通过提案,返回“尚无提案”响应。节点C收到[1, ]准备请求时,因提案编号1小于之前响应的准备请求编号5,返回“尚无提案”响应。该图直观呈现了节点处理准备请求的逻辑与响应情况。

第二个阶段也就是接受阶段,首先客户端 1、2 在收到大多数节点的准备响应之后,会分别发送接受请求:

图片展示了Paxos算法中接受阶段的时序图。左侧有提议者(客户端1、2),中间是接受者(节点A、B、C)。时间轴从左至右表示时间流逝。客户端1、2分别在[1, 3]、[5, 7]时刻发送接受请求,节点A、B、C在[5, ]时刻响应接受请求。该图与上下文紧密相关,直观呈现了客户端发送接受请求及接受者响应的时序关系,辅助理解Paxos算法中接受阶段的处理过程。

当三个节点收到 2 个客户端的接受请求时,会进行这样的处理:

图片展示了Paxos算法中节点A、B、C在收到接受请求时的处理情况。当节点A、B、C收到接受请求[1,3]时,由于提案编号1小于三个节点承诺能通过的提案最小编号5,提案被拒绝,图中用红色叉号标识。之后,节点A、B、C再收到接受请求[5,7]时,因提案编号5不小于承诺编号5,通过提案[5,7],接受值7,图中用箭头指向接受结果。此图直观呈现了Paxos算法中接受请求处理的逻辑。

如果集群中有学习者,当接受者通过了一个提案时,就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案,那么它也通过该提案,接受该提案的值。

通过上面的演示过程,你可以看到,最终各节点就 X 的值达成了共识。那么在这里我还想强调一下,Basic Paxos 的容错能力,源自“大多数”的约定,你可以这么理解:当少于一半的节点出现故障的时候,共识协商仍然在正常工作。

Multi-Paxos

Basic Paxos 只能就单个值(Value)达成共识,一旦遇到为一系列的值实现共识的时候,它就不管用了。虽然兰伯特提到可以通过多次执行 Basic Paxos 实例(比如每接收到一个值时,就执行一次 Basic Paxos 算法)实现一系列值的共识。但是,很多同学读完论文后,应该还是两眼摸黑,虽然每个英文单词都能读懂,但还是不理解兰伯特提到的 Multi-Paxos,为什么 Multi-Paxos 这么难理解呢?

在我看来,兰伯特并没有把 Multi-Paxos 讲清楚,只是介绍了大概的思想,缺少算法过程的细节和编程所必须的细节(比如缺少选举领导者的细节)。这也就导致每个人实现的 Multi-Paxos 都不一样。不过从本质上看,大家都是在兰伯特提到的 Multi-Paxos 思想上补充细节,设计自己的 Multi-Paxos 算法,然后实现它(比如 Chubby 的 Multi-Paxos 实现、Raft 算法等)。

所以在这里,我补充一下:兰伯特提到的 Multi-Paxos 是一种思想,不是算法。而 Multi-Paxos 算法是一个统称,它是指基于 Multi-Paxos 思想,通过多个 Basic Paxos 实例实现一系列值的共识的算法(比如 Chubby 的 Multi-Paxos 实现、Raft 算法等)。

如果我们直接通过多次执行 Basic Paxos 实例,来实现一系列值的共识,就会存在这样几个问题:

那么如何解决上面的 2 个问题呢?可以通过引入领导者和优化 Basic Paxos 执行来解决,咱们首先聊一聊领导者。

领导者(Leader)

我们可以通过引入领导者节点,也就是说,领导者节点作为唯一提议者,这样就不存在多个提议者同时提交提案的情况,也就不存在提案冲突的情况了:

图片展示了Multi-Paxos算法中领导者(Leader)与客户端、节点间的关系。画面中央为红色的“领导者”字样,其向左下方、右下方、右上方分别指向三个蓝色的“客户端”图标,向右上方、右下方分别指向两个紫色的“节点”图标。这与上下文介绍的领导者作为唯一提议者,不存在多个提议者同时提交提案及提案冲突的情况相呼应,直观呈现了领导者与各参与方的交互关系。

在这里,我补充一点:在论文中,兰伯特没有说如何选举领导者,需要我们在实现 Multi-Paxos 算法的时候自己实现。 比如在 Chubby 中,主节点(也就是领导者节点)是通过执行 Basic Paxos 算法,进行投票选举产生的。

那么,如何解决第二个问题,也就是如何优化 Basic Paxos 执行呢?

优化 Basic Paxos 执行

我们可以采用“当领导者处于稳定状态时,省掉准备阶段,直接进入接受阶段”这个优化机制,优化 Basic Paxos 执行。也就是说,领导者节点上,序列中的命令是最新的,不再需要通过准备请求来发现之前被大多数节点通过的提案,领导者可以独立指定提案中的值。这时,领导者在提交命令时,可以省掉准备阶段,直接进入到接受阶段:

图片展示了Multi-Paxos优化Basic Paxos执行流程。客户端发起请求,提议者接收请求后,向接受者发送接受请求,接受者接收请求后,向学习者发送接受响应,学习者接收响应后进入接受阶段,最后接受者向客户端返回服务器响应。该图与上下文紧密相关,直观呈现了优化后Multi-Paxos中领导者节点省掉准备阶段,直接进入接受阶段的执行过程,与上下文提到的领导者节点独立指定提案值、省掉准备阶段等内容相呼应。

和重复执行 Basic Paxos 相比,Multi-Paxos 引入领导者节点之后,因为只有领导者节点一个提议者,只有它说了算,所以就不存在提案冲突。另外,当主节点处于稳定状态时,就省掉准备阶段,直接进入接受阶段,所以在很大程度上减少了往返的消息数,提升了性能,降低了延迟。

Chubby 的 Multi-Paxos 实现

既然兰伯特只是大概的介绍了 Multi-Paxos 思想,那么 Chubby 是如何补充细节,实现 Multi-Paxos 算法的呢?

首先,它通过引入主节点,实现了兰伯特提到的领导者(Leader)节点的特性。也就是说,主节点作为唯一提议者,这样就不存在多个提议者同时提交提案的情况,也就不存在提案冲突的情况了。

另外,在 Chubby 中,主节点是通过执行 Basic Paxos 算法,进行投票选举产生的,并且在运行过程中,主节点会通过不断续租的方式来延长租期(Lease)。比如在实际场景中,几天内都是同一个节点作为主节点。如果主节点故障了,那么其他的节点又会投票选举出新的主节点,也就是说主节点是一直存在的,而且是唯一的。

其次,在 Chubby 中实现了兰伯特提到的,“当领导者处于稳定状态时,省掉准备阶段,直接进入接受阶段”这个优化机制。

最后,在 Chubby 中,实现了成员变更(Group membership),以此保证节点变更的时候集群的平稳运行。

最后,我想补充一点:在 Chubby 中,为了实现了强一致性,读操作也只能在主节点上执行。 也就是说,只要数据写入成功,之后所有的客户端读到的数据都是一致的。具体的过程,就是下面的样子。

图片展示了Chubby的Multi - Paxos实现中主节点处理写请求的流程。客户端向主节点发送写请求(1.写请求),主节点作为提议者将写请求发送给其他节点(2.写请求),当大多数服务器接受写请求后向主节点返回成功(3.成功),最后主节点向客户端响应成功(4.成功)。该图与上下文紧密相关,直观呈现了文档中所描述的主节点处理写请求,在多数服务器接受后响应客户端成功的过程。

图片展示了Chubby的Multi-Paxos实现中主节点处理读请求的过程。左侧为客户端,右侧有三个节点。客户端向主节点发送读请求(1),主节点接收到读请求后,查询本地数据(2),然后将数据返回给客户端(3)。该图与上下文紧密相关,直观呈现了文档中提到的主节点处理读请求的具体流程,帮助理解数据读取机制。

Chubby 的 Multi-Paxos 实现,尽管是一个闭源的实现,但这是 Multi-Paxos 思想在实际场景中的真正落地,Chubby 团队不仅编程实现了理论,还探索了如何补充细节。其中的思考和设计非常具有参考价值,不仅能帮助我们理解 Multi-Paxos 思想,还能帮助我们理解其他的 Multi-Paxos 算法(比如 Raft 算法)。