使用坐标系分析Paxos算法

使用时间和提案编号组成的坐标系来分析Paxos算法，希望能为你带来更直观的感受，使Paxos算法更加易懂。

前言

建议先阅读Paxos算法学习笔记。然后将算法流程代入图中，分析算法在两个阶段中可能发生的情况。这会让你对Paxos算法有更加深刻的印象。

图

总览

1. 横轴代表时间点，纵轴为提案的编号。
2. 一个Paxos实例表示为提案编号所在行的一个线段，从Accept阶段开始。
3. 编号较小的提案也可能比编号较大的提案更晚在prepare阶段达成多数派。

提案

18号提案

18号提案是图中用作参考系的提案。橘黄色代表Prepare成功，深绿色代表达成共识。
这里用18号提案，将面切分成4个区域。

12号提案

这是一个失败的提案，在时间点11失败。

11号提案

这是已经成功的提案。如果没有成功的提案，那么18号提案将会首次达成共识。

区域

A区域

B区域表示的是，在18号提案的Prepare阶段达成多数派Promise前，编号小于18号的提案。
如果A区域已经存在共识，共识内容会被18号提案在Prepare阶段学习到，并作为提案内容。

A和B区域的分界线

Acceptor不接受小于maxPrepareID的Prepare请求和Propose请求。

分界线左边还未达成共识的提案必然失败。在图中就好像是一道栅栏。
比如A区域中的12号提案，它必然会在11时间点失败。

B区域

B区域表示的是，在18号提案的Prepare阶段达成多数派Promise后，编号小于18号的提案。
提案在Prepare阶段必然会失败。所以B区不会出现进入Accept阶段的Paxos实例。

C区域

C区域表示的是，在18号提案还未达成决议前，提案编号大于18号的提案。
这是最特殊的区域，如果这个区域有提案在Prepare阶段达成多数派，则18号提案必然失败。
因此在这个图中，这个区域必然是空的。

D区域

D区域表示的是，提案编号大于18号，且时间线也在18号提案达成共识之后。

C和D区的分界线

存在已经达成的共识，在节点的任意一个多数派中，ProposalID最大的那个决议必然存有当前共识内容。

当18号提案达成共识后,根据Paxos算法，从这个时间线向后的提案，Proposor会将共识内容作为提案内容。于是，共识的内容就不会再改变。
关于这个结论的数学证明，请看Paxos算法的数学归纳法证明。

其它

为什么Paxos的实例的表示从Prepare阶段成功开始？

1. Prepare阶段没有成功，提案就终止了，不会提交提案内容，所以不会影响到共识。
2. 因为没有形成多数派，所以不能阻止ProposalID比它小的提案达成共识。可以认为没有影响整体状态。
3. 从Accept阶段开始可显著降低图的复杂度。

总结

1. 分析18号提案的线段，可以得出，起点影响的是更小编号的提案。终点影响的是未来提案编号更大的提案。
2. 新共识的线段，必然是在旧共识线段的右下角，两个线段在时间线上的投影不会重合。
3. 可以想象，新达成的共识在图上留下的线段，会向右下角不断迭代下去。