paxos协议通俗理解

2012-09-16

从提议者的角度来观察:

第一阶段,获取提议权

某提议者:

我要提议! 消息编号SN1
(消息编号是提议者自己编号的,并且保证每一轮大于其它所有提议者的上一轮编号
比如说提议者甲的各轮提议编号1 5 9 13...
提议者乙的各轮提议编号2 6 10 14...
提议者丙的各轮提议编号3 7 11 15)

投票者的反应:

A说我认同你的提议权
B懒得鸟你,不回你话(即是拒绝你提议的权利)
C我已经接受了另一个人的提议(消息编号SNX,提议内容是VX),我可以认可你的提议权(消息编号SN1)。但丑话说在前面:如果你跟他提议的内容是一样的,我接受你的提议,否则我不接受你的提议。(就是现实生活中的,我可以不同意你的观点,但我不剥夺你发表观点的权利)

提议者若被大多数认同了提议权,进入第二阶段,提议内容

提议者是个没主见的人,如果在提议权阶段投票者类型都是A,他只能提出自己的提议(SN1,V1)

但如果提议权阶段包含了C类型的回复,为了讨好C类型的投票者,他就发送会被C接受的提议内容。

来自多个C类型回复中提到的提议可能有好多个不同的(SNx,Vx),选最新的那个,即SNx最大的那个对应的Vx,发出消息(SN1,Vx)

投票者: 同意你的提议/不理你 如果收到多数同意了,就意味着这个提议被接受了。否则发起新一轮的提议权(SN2)。

从投票者的角度来观察:

提议权阶段

有人在喊“我要提议! 消息编号SN1”

B类型的投票者,我上次把提议权给某人了,而且那个人消息(SNX)到的比这家伙的SN1新。无视他的请求。

AC类型投票者的前提条件是,他的消息SN1比我上次承诺提议权的消息SNX都要新。

A:我同意你的提议权,因为我之前并没接受谁的提议。

C:我上次已经同意某人了(SNX,VX)。(考虑到你的消息比他新SN1>SNX)我可以同意你的提议权,但不一定接受你的提议哦,亲。

提议阶段

如果这个提议(SN1)比之前给予提议权的消息编号(SNX)旧,即SN1<SNX,则忽略请求。否则接受提议。

paxos