使用时间和提案编号组成的坐标系来分析Paxos算法,希望能为你带来更直观的感受,使Paxos算法更加易懂。
建议先阅读Paxos算法学习笔记。然后将算法流程代入图中,分析算法在两个阶段中可能发生的情况。这会让你对Paxos算法有更加深刻的印象。
18号提案是图中用作参考系的提案。橘黄色代表Prepare成功,深绿色代表达成共识。
这里用18号提案,将面切分成4个区域。
这是一个失败的提案,在时间点11
失败。
这是已经成功的提案。如果没有成功的提案,那么18号提案将会首次达成共识。
B区域表示的是,在18号提案的Prepare阶段达成多数派Promise前,编号小于18号的提案。
如果A区域已经存在共识,共识内容会被18号提案在Prepare阶段学习到,并作为提案内容。
Acceptor不接受小于maxPrepareID的Prepare请求和Propose请求。
分界线左边还未达成共识的提案必然失败。在图中就好像是一道栅栏。
比如A区域中的12号提案,它必然会在11时间点
失败。
B区域表示的是,在18号提案的Prepare阶段达成多数派Promise后,编号小于18号的提案。
提案在Prepare阶段必然会失败。所以B区不会出现进入Accept阶段的Paxos实例。
C区域表示的是,在18号提案还未达成决议前,提案编号大于18号的提案。
这是最特殊的区域,如果这个区域有提案在Prepare阶段达成多数派,则18号提案必然失败。
因此在这个图中,这个区域必然是空的。
D区域表示的是,提案编号大于18号,且时间线也在18号提案达成共识之后。
存在已经达成的共识,在节点的任意一个多数派中,ProposalID最大的那个决议必然存有当前共识内容。
当18号提案达成共识后,根据Paxos算法,从这个时间线向后的提案,Proposor会将共识内容作为提案内容。于是,共识的内容就不会再改变。
关于这个结论的数学证明,请看Paxos算法的数学归纳法证明。