paxos算法及加锁的思考

paxos算法:

proposer, acceptor两个角色

每次proposer提交的都是一个唯一且递增的N

maxN是acceptor曾经accept过的最大提案编号

 

2个步骤:prepare, accept, 两次都要将acceptor的maxN和提案N比较,accept完成后如果响应过半,直接commit无须再比较。

 

具体过程:

1.prepare:

proposer提出一个N,发给所有的acceptor, acceptor将这N与本地接受过的最大编号maxN比较

如果N > maxN, 就返回通过了N 给proposer; 如果N < maxN就放弃该提案

当prepare有超过半数通过,才会发accept; 如果没有超过半数通过,就放弃该提案

2. 当proposer超过半数通过,则进入accept阶段,proposer会z再次将真正的提案N发给acceptor,acceptor会再次拿出自己曾经acceptor过在最大变化maxN或者记录下的prepare编号与N比较

当超过半数通过,acceptor就会发送接受了N给proposer. 如果没有半数通过,就放弃该提案

3.当proposer超过半数通过,则进入commit阶段, 直接commit.

 

 

这会产生一个问题, commit的时候没有比较,可能在这时候会发生修改,确实如此

加锁: 当accept后,就将状态改成Lock, 这样accept到commit之间,就不会因为有更新的提案而使得这次提交了一个过时的提案。

 

 

思考:

但是如果加了Lock后还有一个问题,在没有commit完成阶段如果有N+1提案,N+1提案会被放弃

因为如果进入了accept阶段,说明N的提案超过半数通过了, 这半数会将状态修改为Lock则不可以做操作。但是commit前来了一个N+1, 在N+1 prepare阶段就会因为没有超过半数通过而废弃。

这个问题还不知道怎么解决。

 

上一篇:第一部分:分布式架构理论


下一篇:Paxos协议理解