Home
吐槽 源码研究 我的 算法挑战 网络 科学吧 文青 关于我

paxos笔记

22 Mar 2014 by LelouchHe

问题

分布式系统中必不可少的是replica,利用数据冗余来提高可用性,避免数据丢失.但数据冗余带来了一致性问题,即多个replica可能会由于网络和机器故障等原因造成内部数据的差别.对于一些一致性要求不严格的服务,这也许不是什么问题,比如最后我们可以通过重新dump一遍数据,更新所有的replica即可.但对于其他服务,比如分布式DB,一致性是必须的

如何保证一致性,在这里有了简单的描述,本文主要是介绍其中一个解决方法,即paxos算法

适用前提

paxos适用于非拜占庭将军的异步系统,即:

其实可以看到,这个场景其实是绝大部分分布式系统的常见场景

paxos服务在系统中的位置

一开始我的理解是paxos服务就是提供数据的servers,clients直接向paxos服务提交请求,然后由paxos进行一致性处理,然后在内部进行具体的数据处理

但也可以将真正的数据servers和paxos服务划分出来,如下图

[][]

整个服务的步骤如下:

  1. clients向数据servers并行的提交改变数据servers状态的请求(如果都是不改变的请求,就成了只读服务器了,没必要搞一致性)
  2. 数据servers将请求编号,并向paxos提交请求
  3. paxos服务使用paxos算法,从多个并行请求中选择一种执行序列,并返回数据servers该序列
  4. 数据servers获取该执行序列,并按照该序列对数据servers内部的状态进行修改,然后返回clents
  5. clients可以根据返回的状态,判断是执行成功还是失败,是否需要回滚或者重新提交请求

当然,执行序列只是一个一般的说法,真正的数据servers可以单个单个的串行提交,或者一批一批的batch提交,又或者异步并行的提交请求,这些都不会影响paxos的处理

将数据servers和paxos服务分割开来,主要的目的是为了paxos的复用,即一个paxos服务可以被多个不同的要求数据一致性的数据servers使用.paxos处理的应该是服务内部抽象的请求编号,而不是真正的直接请求

可以说,相对于paxos服务而言,数据servers就是它的clients,提交的请求就是对应的请求编号

角色划分

针对于paxos服务而言,clients(即上面的数据servers)提交的是一些value(这个value是对应的数据servers抽象的请求编号),paxos做的只是决定哪些value被接受了,哪些value被驳回了,至于被驳回的这个value最后如何,这就得看clients对于不同返回状态的处理了,和paxos无关

而在paxos内部,各个机器有这不同的角色划分:

这些角色的划分,并不是物理的划分,而是逻辑的划分.同一个机器可以有多个角色,但我感觉,如果将一个机器的角色安排的过多,有时候不是特别的好,比如一台机器fail之后,多个角色都fail了.当然,这需要各种trade off了,就是现实的问题了

instance的概念

最简单的情景就是从多个value中选取一个value,然后驳回其他所有的value.为了能从多个value中得到一个一致性的序列,可能需要迭代的执行多次上述最简单的过程,每次使value数少1.

上面说的最简单的情景,就是一个instance,后面进行的迭代,就是多个instance的迭代.当然,这里不是说instance只能串行,instance可以像请求一样,并行的来操作

但是要记住一点,instance是各自独立的,相互之间并不影响,每个instance只是决定接受单一的某个value,而这些instance的组合才会决定所有value的最后一致性的安排

instance执行的演变

instance的执行是paxos的核心(synod),即如何从多个value中选择唯一value.这个的算法不是一蹴而就的,而且同后续多instance的执行也有些联系.所以此处,我们选择沿着解决问题的思路来讲解synod的演变,而不是像上面一样,直接给出结论(结论就简单的几句话,但理解需要整个过程来看)

总体原则

paxos的总体判断原则是,如果一个value被acceptor中的majority接受,那么这个value就算被整体接受了

paxos保证的是,只要确实被majority接受,就肯定会被所有的接受.此处的majority不一定指的是数量,如果每个机器的权值不一样的话,还代表权值和的majority.不过我们此处讨论的只是数量,为了简便起见

paxos的算法,就是要通过精心设计的算法步骤,来保证这一点.细分来看,就是要保证下面3点必然能成功:

下面通过讨论这些性质的充分条件,来对算法的性质进一步的约束,从而最后得到算法的具体步骤

可以被接受

单纯考虑这个性质,只要acceptor可以接受请求的value即可.

还需要什么特殊的条件么?

假设paxos服务只有一个proposor和一个acceptor(比如其他角色全部挂掉了),那么此时的acceptor并不能对value有特别的要求,只能是proposor提出什么请求,就接受哪个value,如果非要等待某个特殊性质的value的话,会导致服务陷入无限等待中

而且,instance只要决定选择某个value即可,并不要求value是什么,那么此时最优的选择,肯定是第一个value(因为后面的value存在与否,能否到来都是不可知的)

所以性质1的充分条件,目前可以总结为:

当然,这只是能够满足条件的一个充分条件而已,在满足要求的前提下,自然是怎么方便怎么处理,比如,我们自然也可以把性质1的充分条件总结为:

可以被majority接受

一旦提到majority,必然有多于1个的proposer和acceptor,假设存在P1和P2(分别请求v1和v2),A1和A2.此时的majority就是A1+A2.

按照C1的性质,我们来考虑最理想的情况,P1向A1和A2提出请求,A1/A2都接受了(因为是第一个请求),此时形成了majority,P2再向A1/A2请求时,就直接被拒绝了.此时,就得到了v1作为本次instance选取的最后value.P1成功,而P2失败

但是,还有种非理想的情况,即P1向A1提出了请求并被接受,P2向A2提出了请求并被接受(请求时机和网络之类的因素,很容易产生类似情况),此时,P1/P2的新的请求肯定不会被A2/A1接受(根据C1),或者无法达成一致(根据C1a,P1/P2一直不停的向A1/A2提交请求),这样就无法形成majority,此次就只能hang在这里了.

从这一点来看,C1/C1a的性质是可疑的,即我们无法同时满足C1和majority.majority性质是必须的性质,就说明C1/C1a这个充分条件是不合适的,我们需要重新寻找新的充分条件来满足性质1

所谓特殊性质,简单说来,就是能从请求之间的相对关系来进行选择,最通俗的说法,就是让请求有序,即让各个请求之间存在一定的顺序关系,否则,我们无法在多个类似请求之间进行选择(随即选择倒也是选择,但无法保证一定一致).同时,这个”有序”不能是时间上的顺序,否则就成了C1a,无限的循环下去了.

那么第一步,是个所有的请求进行编号,要求是所有的编号不能重复而且有序.此处,我们简单的假设P1的请求号为n1,P2的请求号为n2,且n1<n2(有序的一种性质),同时,将C1修改为:

这个性质就可以很好的解决刚才的非理想情况(A1接受P1,A2接受P2),此时P2向A1发送请求,A1比较下请求号,自然就接受了P2的请求,但P1向A2的请求,则被拒绝.此时,P2的请求得到了majority的接受,v2成了majority值.证明此种条件下,有可以被majority接受的value

有没有什么更奇葩的情况呢?P1会不会主动的增加请求号,来争取被接受呢?这是个问题,由于网络原因(接受请求的应答延迟或丢失了),或者被拒绝(有更大的请求号),P1有可能提高请求号来促使自己的请求被接受

但是,这也不是个问题.失败重发机制是非常常见的,我们不能禁止proposer重复发送请求,比如proposer不知道请求接受了没有,还是丢失在网络中,所以没有在一定时间内没有显式应答,肯定需要重发的.

在C1a的情况下,此时的请求肯定就是新的请求了(又回到C1a的无限循环了).当然,我们可以说,”把请求真正产生的时间记录下来不就可以了么?”.自然,如果请求的真正产生时间可以用来比较请求的先后,那么这个就类似于请求编号了,而且,分布式系统中,各个机器的物理时间是最不可靠的,我们不能依赖于近似与各自独立的元素来达成分布式的一致

在C1b的情况下,我们可以避免这种竞争行为,因为重发并不会改变请求的编号,只有在显式得到”被拒绝”的的应答,才会考虑增加请求编号.不过我们为什么要增加呢?本请求被拒绝,说明有别的请求被接受,那么本instance的执行有了选择,就已经完成了执行的本意,所以我们自然可以控制不去重发类似的请求

综上所述,独立不重复编号+C1b+不重发新增编号的请求确实可以保证有value可以被majority接受

可以被全体接受

还是假设如上的情况,A1接受P1,A2接受P2,然后A1接受了P2,A2拒绝了P1,此时,P2成了majority,同时也是全体acceptor,此时P2自然可以宣布说v2是最终的选择,然后让learner学习v2

这算是一种理想情况了,假设如下的情景,A1接受P1,A2也接受了P1(P2没来得及发送,或者被延迟,或者被丢失了),此时P1能否宣布v1被选择了呢?自然不行,假如P2的请求正在路上,紧跟着被A1/A2接受了,那么接受v1肯定就带来了不一致.

此处解释下,为什么A1/A2要接受P2.按照C1b,确实应该接受编号更大的请求.如果我们试图修改C1b为下面的条件:

C1c貌似能解决我们的问题,但必须思考的是,A1/A2是独立在分布式系统中的,我们通过什么让A1/A2知道自己接受的value已经是majority呢?让他们之间通信么?进行广播么?自然,这些手段在这里都是不可靠的,而且不能阻止acceptor接受P2.那么能否组织P2进行提交呢?自然也不能,P2的请求可能已经在路上了

我们需要保证的是,当P1的v1被接受之后,不会再有新的value被提交了.通过majority的广播之类是无法解决的(上面已经分析了),我们只能从另一个侧面来解决

问题的根源在于,既然已经有一个value(即v1)被majority接受了,我们为什么还要接受另一个呢?本instance的目的不就是选择一个value么?既然有了,我们自然应该直接进行选择就好,干嘛多此一举再来呢?

既然不能广播majority,那么让proposer提交对应的majority的value也行.现在我们就面对这样一个情况,将请求和value分开提交.先通过一个阶段学习当前可能的majority的value,然后再根据情况进行处理即可

我们引入2阶段的处理:

预提交阶段

所谓”预提交阶段”,就是相互竞争majority阶段,根据C1b,各个请求之间竞争是以请求编号为key的,最大的请求编号最后会被acceptor接受,编号较小的请求会被拒绝.

接受预提交请求后,acceptor应该返回什么value呢?自然,如果没有接受过真提交请求的话,自然是没有value返回,直接返回空.

如果有value被接受过,怎么办?我们可以想象一下,有value是什么情况.既然有value了,证明之前有proposer确认自己的预提交请求被majority接受了,那么它真提交的value在理想状态下应该就是majority的value了,所以我们此处直接返回这个value,告知其他的proposer即可

上面理想的情景假设的是预提交和真提交之间是没有间隔的.假如在真提交全部接受之前,即对应的value真正成为majority之前,有更大编号的预提交请求达到了,怎么办?

一个简单的办法是拒绝,但这就又回到上面的问题,单个的acceptor无法判断是否为majority,如果acceptor有已经接受的value时,该acceptor可以做出判断,但如果没有value,但靠acceptor是无法判断这个的,所以acceptor只能按照简单的C1b来进行判断,而把问题交给proposer来判断

真提交阶段

proposer在上一阶段收到的每个acceptor应答可能有3种:

只有接到majority的成功应答,proposer才会进入真提交阶段,此时应该提交什么value呢?

假设如下的情景,P1向A1/A2预提交成功,接着P2向A2/A3预提交成功,二者都认为自己是majority,而且acceptor都没有返回value,二者都要进行真提交.P1向A1提交成功,P2向A2提交成功.如果此时,又有P3预提交给A3,A3没有办法只能接受,然后P3分别向A1/A2预提交,二者也只能接受并返回对应的v1/v2.此时P3全被接受了,成为majority,P1/P2的真提交会被A2/A3拒绝.

这个时候,P3提交哪个value呢?v1?v2?v3?我们假设几个可能的选择:

那我们是选择v2,还是P3的新v3呢?这个还需要斟酌.假设P3的预提交比较晚,P2的真提交已经被接受,成为了majority的值,此时v2已经被选择出来了,是否还有必要提交v3呢?个人感觉没有必要,这一方面带来新一轮的迭代,而且如果proposer不停的加入进来,这个过程就永远没有终止的时候了;就算P2还没有成为majority,但P2是当前返回的最大编号请求,不做任何处理,也会在将来获取majority的地位,它代表的value肯定是majority的value,我们提交v3只能提前终止这个情况,并让算法继续迭代下去,得不偿失

记住,我们的目标是选出一个value,不在乎这个value是谁的,只要有一个即可

所以,在提交value时,我们的选择限制在acceptor返回的请求编号和value中,从里面选择最大编号的value来进行提交

此时的acceptor该如何应对呢?有如下2种情况:

这样,我们可以保证某个value会被全体接受

重复发送请求

在”可以被majority接受”一节中,我们阐述了一个观点,即被拒绝的proposer不再发出新的请求了.这对于当时讨论的单阶段请求来讲,是合理的,但对于目前改进后的2阶段提交有着比较大的冲突

设想这样的情景,P2向A1/A2预提交请求,都被接受,P2挂了.P1向A1/A2预提交请求,被拒绝.采用刚才的策略,P1就不会在发请求了.这样,整个算法就因为P2的挂机hang在这里,而此时,我们还没有可以使用的value

去掉不重复发送的约束,就可以解决这个问题,比如让P1再被拒绝之后,提高请求编号,重新发送预提交请求,此时的A1/A2就可以接受P1的请求,从而继续算法过程不至于hang掉.至于P2哪天又重新恢复,继续真提交请求其value,由于编号太小,也会被acceptor集体忽略的.

这又带来一个问题,P2此时需要重复提交么?因为P2并没有足够的信息了解当时的情况,所以它的情景和P1当时被拒绝是类似的,所以P2肯定是要重复提交的.如果此时A1/A2已经接受了P1的真提交请求,倒也无妨了,P2最多就是重复提交P1的v1而已.但如果P1还没有完成majority的真提交请求,P2就开始重复发送,导致P1无法完成相应的流程.P1就只好继续重复发送请求.(可以看到,在2阶段的任意阶段被拒绝,都是要增大请求编号,并重新发送请求的)

如此往复,算法就又hang住了.不要小看这种情况,在大规模分布式系统里,任何小概率事件都会发生的.

此时怎么办?

一个思路是我们只让一个proposer可以增加请求编号,就是所谓的leader.leader是proposer之一,负责所有的proposer的提交,当被acceptor拒绝后,会主动提高请求编号,来迫使acceptor接受请求.其他proposer不能提交请求,只能将收到的请求转发给leader

谁是leader

leader是怎样选出来的?

可能的做法是把proposer机器进行编号,当前存活机器中编号最高的就是leader.这样看来,leader需要定时的向proposers发送存活信息,来确保自己的leader地位.

但有可能这样的信息延迟或者丢失,导致某些proposer认为leader已挂.我们能选择次高的么?应该不行,最大编号的机器可能没挂,只是存活信息丢失了,或者即使挂了,我们怎么确保次高的没挂呢?难道系统中的每个机器都要不停的广播子集的存活信息,然后确保所有机器都接收到这样的信息么?

显然不可能.

我们需要一种可以选择出leader的算法.我们手边的paxos就可以.

当proposer认为leader已挂时,就开始提出自荐leader的请求.这个请求和普通的请求一样,只是我们不会主动的增加请求编号了.只要被拒绝,就认为leader仍然存活或已经选出,否则,该proposer就成为了新的leader,并对此进行广播

也就是说,在接收到拒绝应答后,proposer因其状态的不同,有不同的反应:

有了这样的策略,就不用担心两个proposer不停的增加请求编号的竞争局面了.在大部分时间里,都只有leader一个proposer进行提交,没有任何冲突,instance执行的很快.只有在leader的存活信息失效或丢失时,才会出现多个proposer竞选的局面,但paxos保证了只有一个proposer会被接受,从而选择出leader,又恢复到原来的情况了

细节提醒

有几点是需要清楚的了解的:

  1. 请求和value是分离的.proposer虽然代表着client提交请求,但算法的根本目的是选择一个value,而不是请求.所以为了这一点,有的时候某个proposer会提交非自己value的请求,这是为了保证算法的结束.
  2. 真提交阶段value的来源有2种,要不是还没有proposer提交过,所以自己随便提交(自己的value即可),或者已经有人真提交value了,从中选取最大编号的value即可.
  3. majority之间必有一个元素.acceptor依赖这个性质把已接受的value放心的返回给proposer,而proposer放心的从返回的majority应答中,挑选最大编号的value进行提交
  4. 被acceptor接受不代表某value被选择了.只有在value被majority都接受之后,才被成为”选择”.此时根据第2点的限制,保证了之后提交请求的value都是这个value
  5. 最重要的一点,本instance的执行只是为了选择某个value,并没有说哪个value,所以只要有一个value即可,并不对value有特别的要求

学习阶段

proposer真提交阶段后,受到majority的成功应答,就表明自己提交的value(可能不是自己原本的value)被选择了.此时需要做的,就是通知paxos服务内部的所有learner,让它们学习这个value,作为本次instance的最后结果.

由于是majority接受了,很有可能的情况是,剩下的minority的value还是别的值.但是,我们不关心.因为只有learner学习到的才是真正有用的,acceptor的值在下一次的instance中就无效了,所以我们根本不关系它们的值是多少

由此,我们让成功的proposer通知所有的leaner,并得到成功应答后,就可以顺利的返回该value,告知服务的调用方,新的value是什么了

几个不一样的情况

上面描述的算法和我看到的别的地方的讲解有些不一样的地方,下面列出一些我知道的不同,和我对此的解释:

  1. acceptor只能为奇数: 这个是在这里里看到的,但我觉得这是错误的.偶数的acceptor同样有majority,并不影响paxos的执行,选择奇数更可能是实现上的原因,而不是算法本质的问题
  2. 2阶段的本质: 我这里没有采用通常的说法,而是自己感觉出来的结论.我觉得2阶段的本质就是请求和value的分离,以便于proposer判断出真正的majority,从而避免错误的提交.acceptor不关心value是什么,相反,它只关心接受最大编号的请求;proposer也不关心value是谁的,只要提交自己已知的最大编号的value即可(甚至这个value都不是最大编号自己的,也是通过类似途径提交的).二者的正确性由集合的majority必然有交集和majority只接受一个value的限制来保证
  3. 学习阶段由acceptor发起: 在我看来,算法一直避免的是让acceptor来判断majority,因为这个不可能.相对的是,由于proposer必须获取到majority的成功应答,那么此处才是majority判断的合理位置.学习阶段必须在majority接受真提交请求的value之后,而这一点,只能proposer保证,所以我觉得,这个应该是proposer发起的通知,通知对象是所有的learner