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阶段就会因为没有超过半数通过而废弃。
这个问题还不知道怎么解决。