Paxos原理与实现(一)原理篇

几年之前学习zookeeper的时候,就断续的学习过Paxos算法,对其中的原理和如何运用到实际环境中一知半解似懂非懂,以至于后面断断续续又花了不少时间在这上面,每一次的返工都没有达到自己想要的效果.直到最近,开始做mit6.824课程的实验作业,做到lab3完成了一个Paxos算法的实验,以及基于Paxos的KV存储系统,才真正能说自己开始理解了Paxos算法以及它的运用.下面,打算花两篇博客的篇幅,从原理到这个作业的实现,来解释一下Paxos算法.这是第一篇原理篇,基于Paxos made simple 一文,加上一下自己的演绎和解释说明,如果已经熟悉原理了可以略过.

首先,需要对算法中的几个英文单词做一些说明,在参与这个决议过程的两个最重要的角色:

  • acceptor:接受提议者.
  • proposer:提交提议者,为了简化说明,这里不解释其他角色如learner(学习者)的行为,仅解释acceptor和proposer.而需要注意的是,任何一个参与了Paxos的进程都有可能同时扮演acceptor和proposer的角色.
  • majority:这是一个集合,用于表示任何含有超过半数acceptor的集合.为什么需要半数以上?因为只要任何两个majority集合,必然有相同的acceptor,用数学上的术语来说,必然有交集.

其次是这两个角色之间交互的一些行为:

  • proposal:提议,这是proposer向acceptor发起的一个动作,每一个提议包括了提议编号和提议的值,是一个二元组<n,v>,其中提议编号用n表示,提议值用v表示.
  • promise:acceptor对proposer的承诺,承诺如果接收某个提议,那么将不再接收比这个提议更小编号的其他提议.
  • accept:acceptor接收proposer的某个proposal .需要补充的是,前面提到了,一个提议是一个二元组,而接受一个提议指的是接受这个提议的提议值,而不包括提议编号,提议编号仅用来做判断前面有没有接受过更高的提案才用的,换言之,两个提案虽然提议编号不一样,但是只要提议值一样,那么认为它们提议的值是一样的.
  • chosen:指一个提议被一个majority集合中的所有acceptor accept,此时这个提议已经被选中.

下面展开讨论的时候,凡是英语单词,如果不清楚其含义,都请回来参看这里关于这些单词的解释.

接下来,可以基于前面提到的论文,来展开讨论Paxos算法的原理了.

Paxos解决的是分布式中的一致性问题,为什么会有一致性问题?因为参与到一个决策过程,可能有很多进程的参与,而在这个过程中,可能出现很多异常的状况,比如进程宕机,网络通讯故障,等等.一个分布式一致性算法(Consensus Algorithm)需要满足以下的安全性条件(safety requirement):

  • 只有被proposer提出的提议值才有可能被chosen
  • 只有一个提议值能被chosen
  • learner只能得到被chosen的提议值.

在这几个约束条件中,最核心的就是第二个条件,它要求所有参与的进程只能就一个提议值达成一致,而Paxos算法也是通过不断的加强条件来满足约束2来达到目的的.

首先来看如何满足约束条件1,显然可以通过如下的约束条件来满足:

  • P1:一个acceptor必须accept第一次收到的提案.

可是,这个约束并不是完备的,原因在于,不同的acceptor可能接受不同的proposal,这样就可能出现任何一个proposal不满足被chosen的条件的情况了.

换言之,约束1只管值从哪里来,而如何达成一致,形成被majority chosen的提议值,需要满足约束2才能解决.

接下来看如何满足约束2,约束2并不要求只通过一个proposal,这就暗示了,一个acceptor可以通过有多proposal,只要它们的提案值是一样的,那么就不违反约束2,那么可以通过下面的加强约束来满足约束2:

  • P2:一旦一个具有value v的proposal被chosen,那么之后chosen的提案必须具有value v.

需要说明的是,在上面的中文中,用了"之后"这个词语,对应到原先英文论文中,使用的是"higher-numbered"这个词,如何定义一个提案是"之前"还是"之后",使用的是前面解释的proposal二元组中的提案编号n,认为提案编号大的就是"之后"的提案,这是一个全序关系,下面不再解释"之前"和"之后"这些词语,而如何保证生成的提案是全序的,不再这里讨论,留待后面的实现篇再说明.

一个proposal被chosen的前提条件是这个proposal的提案值被majority的acceptor accept,那么又可以有如下的增强条件:

  • P2a:一旦一个具有value v的proposal被chosen,那么之后任何acceptor再次accept的proposal必须具有value v.

再接着,一个proposal被accept的前提条件是proposer提出这个提案值的proposal,那么又可以有如下的增强条件:

  • P2b:一旦一个具有value v的proposal被chosen,那么以后任何proposer提出的proposal必须具有value v。

P2b是很难满足的,原因在于,前面没有提到如何限制proposer提交的提案值,所以接着下来,又需要加强这个条件:

  • P2c:如果一个编号为n的提案具有value v,那么存在一个majority,要么它们中都没有accept编号小于n的任何proposal,要么他们已经accept的所有编号小于n的proposal中编号最大的那个提案具有value v

这里不对为何P2c满足P2b做出证明,感兴趣可以自己去看看论文或者维基百科中的说明.前面提到,P2b之所以难以满足,是因为这个约束中只说明了对proposer的约束条件,就是任何提议的值都是之前被chosen的值,但是并没有说明如何满足这个条件,而P2c给出了满足这个条件的两种方式:

  • 如果没有更低提案编号的值被chosen,那么proposer可以选择任意的提案值
  • 否则,proposer只能选择所有提案值中编号最大的那个.

这两种方式中,都需要一个proposer学习到当前acceptor已经accept的值,所以在算法中,需要一个prepare的准备过程,之后再根据这个过程的结果来形成自己的提案值.

到了这里,可以看到这整个算法中,有两个过程:prepare阶段以及accept阶段.prepare阶段中,对proposer而言,是学习当前被chosen的值的过程,而对acceptor而言,除了告诉proposer自己当前accept的值,还需要包括一个承诺,承诺不再接受比这个提案值更小的proposal.为什么需要这个承诺?考虑这种情况,proposer a提交了提案编号为n的prepare请求给acceptor 1,而在a开始该编号的accept请求之前,acceptor 1又接受了另一个proposer b的accept请求,同时这个请求的提案值与前面a的提案值不一样,那么很显然,这与前面的约束条件P2c冲突了,于是需要针对约束1做一个加强条件:

  • P1a:当且仅当acceptor没有回应过编号大于n的prepare请求时,acceptor accept编号为n的proposal

至此,Paxos算法的讲解已经结束,需要回头做一个小结.

约束条件1并不完备,这个条件只说明了该被chosen的提案值从哪里来,而并没有解决一致性问题.

约束条件2是整个一致性算法中的核心问题,从这个条件出发,一步一步加强这个条件,它们的顺序依次是这样的:

  • P2:对整个算法的一致性做了约束,任何提案值只要被chosen,那么以后的任何提案都必须是这个提案值.
  • P2a:对acceptor进行了约束,因为chosen是针对一个majority集合的概念,那么只要这个majority中的所有acceptor都accept的是这个被chosen的提案值,P2自然就满足了.
  • P2b:对proposer进行了约束,P2a要求一个majority的所有acceptor都accept的是这个提案值,那么只要proposer提交是这个提案值就可以满足P2a了.
  • P2c:同时对acceptor和proposer进行了约束,对acceptor的约束表现在,要求它做出不接受更小提案编号的提案,同时告诉proposer当前自己接受的提案.对proposer的约束表现在,它提交的提案值,必须基于前面与acceptor的交互结果.

到了这里,可以看到只要满足P2c,算法的一致性就得到了满足.而proposer如何学习acceptor已经accept的提案,就涉及到一个prepare过程,在这个过程完毕之后,proposer根据结果来形成自己的提案值.所以,整个算法是两阶段过程,其伪代码表示如下:

  1. prepare阶段:
    1. proposer选择一个提案编号n并将prepare请求发送给majority;
    2. acceptor收到prepare消息后,如果提案的编号大于它已经回复的所有prepare消息,则acceptor将自己上次接受的提案回复给proposer,并承诺不再回复小于n的提案;
  2. 批准阶段:
    1. 当一个proposer收到了majority对prepare的回复后,就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求,包括编号n和根据P2c决定的value(如果根据P2c没有已经接受的value,那么它可以自由决定value)。
    2. 在不违背自己向其他proposer的承诺的前提下,acceptor收到accept请求后即接受这个请求。

如上的分析,还是有些枯燥,可以加上一些图文的说明看看这个算法的过程,我推荐的看看这篇博客<<以两军问题为背景来演绎Basic Paxos>>. 不过,这些也只是做算法原理做了解释,而离真正的实现还是有差距,需要自己动手做一些代码上的实验,这是下一篇博客的重点了.

参考资料:

  1. Paxos算法1-算法形成理论
  2. Paxos算法
  3. 以两军问题为背景来演绎Basic Paxos

One Comment

  1. mjo 说:

    建议统一下术语“提议”和“提案”

    [回复]

Leave a Reply