Skip to content

Latest commit

 

History

History
48 lines (31 loc) · 5.12 KB

basic-paxos-9-pages-notes-05.md

File metadata and controls

48 lines (31 loc) · 5.12 KB

基础Paxos算法笔记(5/9)

       第五页笔记会结合Paxos算法的约束,再次梳理细化提案批准过程,设想ProposerAcceptor的属性与状态。

       关键词:ProposerAcceptorLearner准备阶段批准阶段

       准备阶段是Proposer发起Prepare请求给到Acceptor,请求的内容是提案(包括:提案编号和议题)。准备阶段的发起方式Proposer,但实际是Citizen,也可以理解为客户端。准备阶段的目的是为了获得设置值的资格,而其载体就是提案。以Proposer的视角来看一下,如下图:

       Citizen需要设置值,将请求Request发送给ProposerProposer内部会具有一个提案列表,它包括了该Proposer提交的所有提案,也拥有将Request转换为Proposal的能力。

       Proposer收到了Request,然后通过询问多数的Acceptor(s),它们最新的提案编号是多少。Proposer再得到足够信息后,开始尝试将Request转换为Proposal,然后进入到提案的Prepare阶段。这里可以看出来,提案除了包含议题和编号,还会有Request的相关信息,比如:请求ID,Citizen的关键信息,以及当前Proposer的关键信息等,这样的Proposal才显得充分。

       当Proposer接收到了(发起提案的)足够多表示同意的Promise后,Proposer会发起该提案的批准接受Accept请求,使得回复了同意PromiseAcceptor能够完成提案值的设置以及Resolution的生成。这里存在一个问题,两个阶段是在Proposer上还是在Proposal上?如果同一时刻一个Proposer只能提出一个提案的话,设置在Proposer上是没有问题的,但如果Proposer会同时创建多个提案,那就必须设置在Proposal上。由于Paxos算法是通过异步消息进行通信,并行处理是必然,所以阶段是设置在Proposal,也就是提案上,因此提案会有批准Acceptor的列表等信息,这些运行时信息如果能够体现出多数的**Acceptor(s)**同意,那么该提案就进入了批准阶段。

       以Acceptor的视角来看,如下图:

       Acceptor收到ProposerPrepare请求,然后回复PromiseAcceptor有提案列表,也有决议列表,如果收到的提案编号能够在决议中找到,那就会回复忽略的Promise,因为这都已经成为决议了,没有必要再提了。提案以及回复的Promise如下表所示:

收到提案的情况 回复Promise 含义
提案编号如果能够在决议列表中找到 忽略 已经成为决议了,没有必要再提
提案编号如果大于提案列表中最新的提案编号 同意 没有收到过该提案,可以通过
提案编号如果小于提案列表中最新的提案编号 中止 已经收到过提案,该提案还没有进入批准阶段,但已经有Proposer提过,可以中止
提案编号如果等于提案列表中最新的提案编号 建议 提案编号一样,但多个**Proposer(s)提出了,那回复发送请求的Proposer(s)**一个建议,建议使用已经存在的提案

       Proposer不断的收到Promise,如果发现其中某个提案中的支持(或同意)数量已经过了半数,那就代表该提案需要进入到批准阶段。进入批准阶段的提案,Proposer会发起Accept请求,而Acceptor一旦收到,就会按照要求将决议转换为决议,并将其发布通知给Learner

       可以看到在阶段控制上是通过Proposer来做到的,接下来看一下Learner,如下图:

       Acceptor发布了ResolutionLearner收到后会记录下当前决议,同时进行广播给其他Learner(s),最后将Resolution转换为Response,回复给Citizen

       这么长的链路,Learner怎么能够知道Citizen呢?因为Resolution包含了Proposal,而Proposal包含了Request,这样自然就能从某一个决议找到发起请求的Citizen了。