Paxos

Distributed Consensus Algorithm

There is only one consensus protocol, and that's “Paxos” — all other approaches are just broken versions of Paxos

世界上只有一种共识协议,就是Paxos,其他所有共识算法都是Paxos的退化版本。

—— Mike Burrows,Inventor of Google Chubby

Paxos是由Leslie Lamport(就是大名鼎鼎的LaTeX中的“La”)提出的一种基于消息传递的协商共识算法,现已是当今分布式系统最重要的理论基础,几乎就是“共识”二字的代名词。这个评价出自于提出Raft算法的论文,更显得分量十足。尽管不像Mike Burrows说的“世界上只有Paxos一种分布式共识算法”那么夸张,但是如果没有Paxos,那后续的Raft、ZAB算法,ZooKeeper、Etcd这些分布式协调框架、Hadoop、Consul等在此基础上的各类分布式应用都很可能会延后几年面世。

文中,Lamport虚构了一个名为“Paxos”的希腊城邦,这个城邦按照民主制度制定法律,却又不存在一个中心化的专职立法机构,立法靠着“兼职议会”(Part-Time Parliament)来完成,无法保证所有城邦居民都能够及时地了解新的法律提案、也无法保证居民会及时为提案投票。Paxos算法的目标就是让城邦能够在每一位居民都无法承诺一定会及时参与的情况下,依然可以按照少数服从多数的原则,最终达成一致意见(但是并不考虑拜占庭将军问题,即假设信息可能丢失也可能延迟,但不会被错误传递)。

Lamport最初在1990年首次发表了Paxos算法,选的题目就是“The Part-Time Parliament”。由于算法本身较为复杂,用希腊城邦作为比喻反而使得描述更为晦涩,论文的三个审稿人一致要求他把希腊城邦的故事删除掉,这令Lamport感觉颇为不爽,然后干脆就撤稿不发了,所以Paxos刚刚被提出的时候并没有引起什么反响。八年之后(1998年),Lamport再次将此文章重新整理后投到《ACM Transactions on Computer Systems》,这次论文成功发表,吸引了一些人去研究,结果是并没有什么人能弄懂。时间又过去了三年(2001年),Lamport认为前两次是同行们无法理解他以“希腊城邦”来讲故事的幽默感,第三次以“Paxos Made Simple”为题,在《SIGACT News》杂志上发表文章,终于放弃了“希腊城邦”的比喻,尽可能用(他认为)简单直接、(他认为)可读性较强的方式去介绍Paxos算法,情况虽然比前两次要好,但以Paxos本应获得的重视程度来说,这次依然只能算是应者寥寥。这段跟网络段子一般的经历被Lamport以自嘲的形式放到了他自己的个人网站上。尽管我们作为后辈应该尊重Lamport老爷子,但当笔者翻开“Paxos Made Simple”读到只有一句话的“摘要”时,心里实在是不得不怀疑Lamport这样写论文是不是在恶搞审稿人和读者,在嘲讽“你们这些愚蠢的人类!”。

虽然Lamport本人连发三篇文章都没能让大多数同行理解Paxos,但是到了2006年,Google的Chubby、Megastore以及Spanner等分布式系统都使用Paxos解决了分布式共识的问题,并将其整理成正式的论文发表之后,得益于Google的行业影响力,辅以Chubby作者Mike Burrows那略显夸张但足够吸引眼球的评价推波助澜,致使Paxos一夜间成为计算机科学分布式这条分支中最炙手可热网红概念,从这时起被学术界众人争相研究。2013年,Lamport本人因其对分布式系统的杰出理论贡献获得了2013年的图灵奖,足可见技术圈里即使再有本事,也还是需要好好包装一下的。

讲完段子吃过西瓜,希望你没有被这些对Paxos的“困难”做的铺垫所吓倒,反正又不让你去实现它,假如放弃些许严谨性,并简化分支细节和特殊情况的话,Paxos是完全可能去通俗地理解的,Lamport在论文中也只用两段话就描述“清楚”了它的工作流程,下面我们正式来学习Paxos算法(在本节中均特指Basic Paxos算法)。Paxos算法将分布式系统中的节点分为三类:

  • 提案节点(称为Proposer):提出对某个值进行设置操作的节点,设置值这个行为就被称之为“提案”(Proposal)。请注意,这里的“设置值”不要类比成程序中变量赋值操作,应该类比成日志记录操作,值一旦设置成功,就是不丢失、不可变的,在后面介绍的Raft算法中就索性直接把“提案”叫做“日志”了。
  • 决策节点(称为Acceptor):应答提案节点该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受,即称该提案被批准,提案被批准即意味着该值不能再被更改,也不会丢失,且最终所有节点都会接受该它。
  • 记录节点(被称为Learner):不参与提案,也不参与决策,只是单纯地从提案、决策节点中学习已经达成一致的提案,譬如少数派节点从网络分区中恢复时,将会进入这种状态。

使用Paxos的分布式系统里的,所有的节点都是平等的,它们都可以承担以上某一种或者多种的角色,不过为了便于确保有明确的多数派,决策节点的数量应该被设定为奇数个,且在初始化时,网络中每个节点都知道整个网络所有决策节点的数量、地址等信息。

分布式环境下,我们如果说各个节点“就某个值(提案)达成一致”,所指的意思是“不存在某个时刻有一个值为A,另一个时刻该值又为B的情景”。解决这个问题的复杂度主要来源于以下两个方面因素的共同作用:

  • 系统内部各个节点通讯是不可靠的,不论对于系统中企图设置数据的提案节点抑或是决定是否批准设置行为的决策节点,其发出、收到的信息可能延迟送达、也可能会丢失,但不去考虑消息有传递错误的情况。
  • 系统外部各个用户访问是可并发的,如果系统只会有一个用户,如果每次只对系统进行串行访问,那单纯的应用Quorum机制已经足以保证值被正确地读写。

第一点是网络通讯中客观存在的现象,也是我们要重点解决的问题,而第二点其实也很好理解:现在我们讨论的是“分布式环境下操作的共享数据”的问题,而即使是在非分布式的环境下,有一个变量i当前在系统中存储的数值为2,如果同时有外部请求A、B分别对系统发送指令“把i的值加1”和“把i的值乘3”,如果不加任何并发控制的话,将可能得到“(2+1)*3=9”与“2*3+1=7”两种可能的结果。为此,对同一个变量的修改请求必须先“加锁”(实际操作上并不是并发控制中互斥量的加锁),不能让A、B的请求被交替处理。在分布式的环境下,由于还要同时考虑到分布式系统内可能在任何时刻出现的通讯问题,如果一个节点在取得同步锁之后,在释放锁之前发生失联,这将导致无限期的阻塞等待,因此还必须提供一个其他节点能抢占锁的机制,以避免死锁。

Paxos算法包括两个阶段,其中第一阶段“准备”(Prepare)就相当于上面抢占锁的过程。如果某个提案节点准备发起提案,必须先向所有的决策节点广播一个许可申请(称为Prepare请求)。提案节点的Prepare请求中会附带一个全局唯一的数字n作为提案ID,决策节点收到后,将会给予提案节点两个承诺和一个应答。

两个承诺是:

  • 承诺不会再接受提案ID小于或等于n的Prepare请求。
  • 承诺不会再接受提案ID小于n的Accept请求。

一个应答是:

  • 不违背以前作出的承诺的前提下,回复已经批准过的提案中提案ID最大的那个提案所设定的值和提案ID,如果该值从来没有被任何提案设定过,则返回空值。如果违反此前做出的承诺,即收到的提案ID并不是决策节点收到过的最大的,那可以直接对此Prepare请求不予理会。

当提案节点收到了多数派决策节点的应答(称为Promise应答)后,可以开始第二阶段“批准”(Accept)过程,这时有如下两种可能:

  • 如果提案节点发现所有响应的决策节点此前都没有批准过该值(即为空),那说明它是第一个设置值的节点,可以随意地决定要设定的值,将自己选定的值与提案ID,构成一个二元组“(n, value)”,再次广播给全部的决策节点(称为Accept请求)。
  • 如果提案节点发现响应的决策节点中,已经有至少一个节点的应答中包含有值了,那它就不能够随意取值了,必须无条件地从应答中找出提案ID最大的那个值并接受,构成一个二元组“(n, maxAcceptValue)”,再次广播给全部的决策节点(称为Accept请求)。

当每一个决策节点收到Accept请求时,都会在不违背以前作出的承诺的前提下,接收并持久化对当前提案ID和提案附带的值。如果违反此前做出的承诺,即收到的提案ID并不是决策节点收到过的最大的,那可以直接对此Accept请求不予理会。

当提案节点收到了多数派决策节点的应答(称为Accepted应答)后,协商结束,共识决议形成,将形成的决议发送给所有记录节点进行学习。整个过程的时序如下图所示:

sequenceDiagram 用户->>提案节点: 操作请求 提案节点->>决策节点: 构造新的提案ID(n),广播Prepare(n)请求 决策节点-->>提案节点: 首次设值,返回Promise(n, null)应答 opt 非首次设值 决策节点-->>提案节点: 返回Promise(acceptedProposalID、acceptedValue)应答 提案节点->>提案节点: 将acceptedValue作为提案的value end 提案节点->>决策节点: 广播Accept(n, value)请求 决策节点-->>提案节点: 返回Accepted(n, value)应答 提案节点->>记录节点: 形成决议,供记录节点学习

整个Paxos算法的工作流程确实并不复杂,如果你此前并未专门学习过分布式的知识,相信阅读到这里,不一定会对操作过程有疑惑,但估计还是不能对Paxos究竟是如何解决协商共识的形成具体的概念的,下面笔者将举一个具体例子来讲解,例子与截图来源于《Implementing Replicated Logs with Paxos》,在此统一注明,后面就不单独列出了。

假设一个分布式系统有五个节点,分别命名为S1、S2、S3、S4、S5,只讨论正常场景,不会涉及到网络分区。全部节点都同时扮演着提案节点和决策节点的身份。此时,有两个并发的请求分别希望将同一个值分别设定为X(由S1作为提案节点提出)和Y(由S5作为提案节点提出),以P代表准备阶段,以A代表批准阶段,这时候可能发生以下情况:

  • 情况一:譬如,S1选定的提案ID是3.1(全局唯一ID加上节点编号),先取得了多数派决策节点的Promise和Accepted应答,此时S5选定提案ID是4.5,发起Prepare请求,收到的多数派应答中至少会包含1个此前应答过S1的决策节点,假设是S3,那么S3提供的Promise中必将包含S1已设定好的值X,S5就必须无条件地用X代替Y作为自己提案的值,由此整个系统对“取值为X”这个事实达成了一致。如下图所示:

  • 情况二:事实上,对于情况一,X被选定为最终值是必然结果,但从图中可以看出,X被选定为最终值并不是必定需要多数派的共同批准,只取决于S5提案时Promise应答中是否已包含了批准过X的决策节点,譬如下图所示,S5发起提案的Prepare请求时,X并未获得多数派批准,但由于S3已经批准的关系,最终共识的结果仍然是X。

  • 情况三:当然,另外一种可能的结果是S5提案时Promise应答中并未包含批准过X的决策节点,譬如应答S5提案时,节点S1已经批准了X,节点S2、S3未批准但返回了Promise应答,此时S5以更大的提案ID获得了S3、S4、S5的Promise,这三个节点均未批准过任何值,那么S3将不会再接受来自S1的Accept请求,因为它的提案ID已经不是最大的了,这三个节点将批准Y的取值,整个系统最终会对“取值为Y”达成一致。

  • 情况四:从以上情况三可以推导出另一种极端的情况,如果两个提案节点交替使用更大的提案ID使得准备阶段成功,但是批准阶段失败的话,这个过程理论上可以无限持续下去,形成活锁(Livelock)。在算法实现中会引入随机超时时间来避免活锁的产生。

以上介绍是基于Basic Paxos、以正常流程(未出现网络分区等异常)、以通俗的方式介绍的Paxos算法,并未涉及到严谨的逻辑和数学原理,也未讨论Paxos的推导证明过程,对于普通的技术人员,理解起来应该并不算困难的。

本节介绍的Basic Paxos只能对单个值形成决议,并且决议的形成至少需要两次网络请求和应答(准备和批准阶段各一次),高并发情况下将产生较大的网络开销,极端情况下甚至可能形成活锁。总之,Basic Paxos是一种很学术化但对工程并不友好的算法,现在几乎只用来做理论研究,并不直接应用在实际软件研发当中。实际的应用都是基于Multi Paxos和Fast Paxos算法的,接下来我们将会了解Multi Paxos与它的理论等价算法Raft和ZAB算法。

Kudos to Star
总字数: 4,415 字  最后更新: 10/10/2020, 9:12:24 PM