分布式一致性算法-关于Paxos算法的理解

Paxos算法是一种一致性算法，用于在一个分布式多节点系统中确定一个确认的值，这个值可以是一条日志，可以是选举领导者，也可以是自己定义的任意数据。

在paxos中，存在三种角色：提议者、仲裁者、学习者。每个节点可以身兼数职，但至少是其中一个。

Paxos确定的值是一组，曾经决策确定过的值，一个值在当次仲裁中被选定，那么便可以保证这个值不会丢失。

在每次仲裁过程中，提议者负责提出提案，仲裁者负责仲裁，学习者将最终仲裁的值学习。

Paxos的约束条件如下：

P1：一个Acceptor必须接受它收到的第一个提案。

P1a：一个Acceptor只要尚未响应过任何编号大于N的Prepare请求，那么他就可以接受这个编号为N的提案。

P2：如果某个value为v的提案被选定了，那么每个编号更高的被选定提案的value必须也是v。

P2a：如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v。

P2b：如果某个value为v的提案被选定了，那么之后任何Proposer提出的编号更高的提案的value必须也是v。

P2c：对于任意的N和V，如果提案[N, V]被提出，那么存在一个半数以上的Acceptor组成的集合S，满足以下两个条件中的任意一个：

S中每个Acceptor都没有接受过编号小于N的提案。

S中Acceptor接受过的最大编号的提案的value为V。

具体流程：

提议者需要维护本次仲裁中，本节点的提案轮次N。

仲裁者会维护2个数据：当前最大轮次N，当前本节点推选提案。

提议者提议分为两个阶段，准备阶段和提议阶段。

准备阶段：提议者向所有仲裁者发送准备请求，包含自己本次提议的轮次N。

仲裁者接到准备请求后，将请求中的N与仲裁节点中维护的最大轮次N对比，若请求中的N小于或等于节点N则忽略，否则维护节点N，并发送响应，响应包含原节点N和原提案。

提议者收到半数以上仲裁者响应后，开始提议阶段。

提议阶段：仲裁者响应中若包含已选定提案，则提议阶段使用该提案进行提议，否则选择响应中N最大的提案，若响应中不包含提案，则提议者自己决定提案。

学习者则不断获取每个仲裁者的仲裁情况，当得到某一轮次的仲裁者超过半数仲裁了同一个值，则学习者确认该值为本次仲裁的最终值。

个人理解：

1. 提议者在提议阶段时候，使用了自己的轮次N对半数以上的仲裁者询问，在本次交互中，提议者相对于锁住了轮次N的提议，也就是说当提议者提议的时候，这一轮次只有这个提议者可以提议，因为超过半数的仲裁者回应代表着其他提议者一定拿不到半数以上的轮次N回应。
2. 提议者提议阶段，仲裁者检查轮次是否匹配，匹配则接收，否则丢弃。丢弃出现的时候必然是因为有更高的轮次被锁住，即轮次N被抢占了。
3. 不可能存在N轮次超过一半仲裁者仲裁的值与N+1轮次不同（比如5个节点，3个节点在轮次2仲裁A值，1个节点在轮次3选择B值），理由如下：若要达成当前局面，首先有提议节点的N+1轮次在准备阶段结束时必须获取超过一半的响应，并且响应中不存在N轮次的值（否则该节点的N+1轮次提出的值必然是N轮次的值），由此可推出超过一半仲裁者在N+1轮次的准备请求到达前必然没有收到N轮次的提议，又因为N+1轮次的准备请求会将N轮次的提议请求无效化（锁抢占），即N轮次提议也不能在N+1轮次响应后被接受，出现矛盾，论证成立。
4. 由3递推可得将结论扩展到N与N+k的场景，也就是定律P2。
5. 该算法与活锁的思路类似，经过推理后发现该算法也存在活锁可能存在的问题：即提议者在准备阶段互相抢占其他提议者的轮次锁，导致轮次不断增加却没有提议者能够进入提议阶段。这种问题的解决方案可以参考RAFT的随机延迟方法，可以简单高效的将概率降低。