腾讯开源的 Paxos库 PhxPaxos 代码解读---Accept阶段(一)
在看Accept阶段代码之前, 我们再回想一下 Basic Paxos算法;
1. Basic Paxos 算法是为了使集群中的Acceptor们达成一个最终的值, 或者不能达成一个最终的值;
就是说, 要么达成一个最终的值, 某个时间点上, 多数派节点都是一个一致的值, 这个值就是最终的值;
否则, 没有多数派在某个时间点达成一个一致的值, 这个值不断被新的提议(Proposal)刷新, 无法达成最终值;
这种情况一般意味着发生了活锁;
2. 一个最终的值一旦被确定, 不能再有Proposor发出提议进行修改, 为了确保这点, 有了针对Proposor的约束:
Proposor必须收到多数派的响应, 才能进行Accept提议; 原因如下:
Proposor只有收到多数派响应消息, 才能确定是否已经有多数派接受过提议(Proposal),
如果多数派响应消息里面已经携带了接受过的提议, 则有两种可能:
1. 多数派已经已经达成了一致, 必然会有某些Acceptor的响应携带了这个值;
2. 多数派还没有达成一致, 但是Proposor正好收到了某个已经接受过提议的Acceptor的响应;
上述情况不论是哪种, Proposor都需要用已有的提议发起Accept请求, 选择最大ProposolID的那个;
这样是为了促使Acceptor们尽快的达成一致;
3. 对于Acceptor的约束, 则是必须要大于等于当前已经接受过的最大ProposalID, 才能刷新这个值,;
我们给出一个典型的场景来说明, 以3个Acceptor为例:
第1个时间片段:
Proposor1发起Prepare请求(1, null), 成功到达 Acceptor1和Acceptor2, Acceptor的状态如下:
Acceptor1(1, null); Acceptor2(1, null); Acceptor3(null, null)
第2个时间片段:
Proposor2发起Prepare请求(2, null), 成功到达 Acceptor1和Acceptor2, Acceptor的状态如下:
Acceptor1(2, null); Acceptor2(2, null); Acceptor3(null, null)
第3个时间片段:
Proposor1发起Accept请求(1, 100), 1 < 2, 被Acceptor拒绝, Acceptor的状态如下:
Acceptor1(2, null); Acceptor2(2, null); Acceptor3(null, null)
第4个时间片段:
Proposor2发起Accept请求(2, 100), 2=2, 被Acceptor接受, Acceptor的状态如下:
Acceptor1(2, 100); Acceptor2(2, 100); Acceptor3(null, null)
第5个时间片段:
Proposor1重新发起Prepare请求(3, null), 到达Acceptor2和Acceptor3,
收到响应之后, 用Acceptor2接受的值发起Accept请求(2,100),成功到达Acceptor2和Acceptor3,
状态变为如下:
Acceptor1(2, 100); Acceptor2(2, 100); Acceptor3(2, 100)
在处理Prepare和Accept请求时, 我们不仅要考虑网络中的异步情况, 还要考虑在接受一个提议时代码执行的异步情况;
前面一篇博客已经简单介绍过phxpaxos中Prepare阶段的代码, 下面简单的介绍一下Accept阶段的代码;
phxpaxos\src\algorithm\proposer.cpp
这里的代码是Proposor的逻辑
phxpaxos\src\algorithm\acceptor.cpp
这里的代码是Acceptor的逻辑
下面的图是Proposor发起Accept请求的操作:
下面的图是Acceptor收到Accept请求的操作:
下面的图是Propsor收到Acceptor返回响应的操作:
结束:
微信开源的Paxos库有很多照顾性能的实现, 后面慢慢讲吧;