Paxos分布式理论学习

当有一系列提议者提出值时,为保证一致性,需要满足以下条件:

  1. 被选中的值必须是已经被提出的
  2. 每次只能有一个值被选中
  3. 一个值真实被选中前,不可提前知道结果

协议成员

Proposer:提议发起者

Acceptor:提议接受者

Learner:提议学习者,Learner角色的目的就是把通过的确定性取值同步给其他未确定的Acceptor。

协议过程

阶段一:

a)

Proposer选择一个提议编号n,并向所有Acceptor广播prepare(n)消息

1
2
3
4
5
graph LR
P1--"prepare(n)"-->A1
P1--"prepare(n)"-->A2
P1--"prepare(n)"-->A3

b)

如果Acceptor收到的提议编号大于之前已经回复过的prepare消息编号,那么将回应不会再接收比n小的消息,并带上之前所接受过的最大编号

1
2
3
4
5
graph RL
A1--"promise(n,{n1,v1})"-->P1
A2--"promise(n,{n2,v2})"-->P1
A3--"promise(n)"-->P1
note["A1之前接受过最大的为n1,<br>A2之前接受过最大的为n2,<br>A3未接受过(n>n1>n2)"]

阶段二:

a)

Proposer得到了多数Acceptor的承诺后,那么向所有的Acceptor发起编号为n的提议,提议的值为所有回应中最大的编号所对应的值,否则发送自己新提议的值。

1
2
3
4
5
graph LR
P1--"accept(n,v1)"-->A1
P1--"accept(n,v1)"-->A2
P1--"accept(n,v1)"-->A3
note["由于之前回应中最大提议编号为n1,<br>所以发送的值为v1"]

b)

Acceptor如果没有回复过比n大的prepare消息,则接受该提议。

Paxos分布式理论学习

https://blog.luzy.top/posts/3438488174/

作者

江风引雨

发布于

2021-08-18

更新于

2021-08-19

许可协议

CC BY 4.0

评论