分布式

例解Poxos算法

By fisherMartyn 2016-12-13

PaxOS算法是分布式系统中最经典的算法之一，也是不得不谈及的问题，这个博客的目的并不是去讲解它的原理，甚至去证明；而是希望通过例子的方式来体现一些细节，提升对它的理解、甚至提升对于分布式本身的理解。

CAP原理 ： 一致性、可用性和分区容错性不可兼得。

FLP Impossibility ： 在异步通信的环境下，没有一个算法可以保证数据一致性。

Paxos算法（有人也叫Paxos协议），也无法完全解决异步通信环境下数据一致性的问题，而只是在可用性上做了权衡。

Paxos算法的地位极高：

all working protocols for asynchronous consensus we have so far encountered have Paxos at their core.

所有目前存在的异步一致性协议，在核心上都是Paxos。

Paxos解决的问题 ： 分布式系统之间，如果就一个不可变的变量达成一致。

并且对于可用性，Paxos做了两点保证：

1.Liveness

只要存在多数派存活，而且多数派之间的网络是联通的，那么：

1. 肯定就变量值达成一致
2. 达成一致的值肯定可以被其他进程学习到

2. Safety

不会出错，只有一个值被确定，不会出现第二个值将其覆盖。

假设有三个进程 A, B, C，希望就变量V的值达成一致。

最直接的想法：

P1 ：集合中任一进程向其他进程提议V的值，提议被进程接收后，拒绝其他的值。

该解决方案的问题是：1、不允许任何进程故障；2、多个进程并发赋值的问题无法支持。因此我们可以针对此问题进行优化：

P2 ：集合中任一进程可以进行提议V的值，当提议被法定集合采纳，即可认为提议已经确定；当提议被接收后，进程会拒绝再次对V的提议。

该解决方案的问题是，无法支持多并发进程对V赋值的场景。我们尝试将拒绝对V的再次提议的限制条件开放。

P3 ：任一进程可以进行提议V的值，当提议被法定集合采纳，即可认为提议已经确定；当提议被进程接收后，进程仍然可以接收对V的提议。

该方案的问题主要是重复赋值的问题。例如A的进程希望赋值为i，B进程也采纳了该值；但同时C被赋值为j。按照多数派的规定，i的值已经获得了多数派的认可，这以意味着j的赋值应该受到限制。

提议前，进程询问下其他进程的建议值，如果建议为空，则提议自己定义的值；如果建议不为空，则提议出现次数最多的那个值

该方案出现了并发和时序的问题，假设很不幸的出现了A去B和C询问建议值，分别返回了i和j，这时候A就无法选择。可以引入时序变量epoch（你可以理解为一个全局id），例如A返回的是(epoch1 , i)，而B返回的是(epoch2, j)，这样就可以根据epoch的不同来进行一个选择即可。

这样所有的条件都已经具备了，至少包含几个信息：

1. 依赖法定集合而不是全集
2. 可以接受多次提议
3. 至少两个阶段，询问和提议

再考虑下并发的情况：

假设两个进程同时向集合发起询问，返回的结果都是null，这个时候两个进程都提交了提案，而且值不同。这个时候如何处理呢？

两个法定集合必然存在一个公共子进程。这是法定集合存在的意义。只需要确定公共子集的行为，即可以达到一致。可以通过一条简单的规则：只接受epoch最大的提案，拒绝其它提案。

综上，我们隐约可以推导出一个Paxos的执行过程。

Paxos的执行过程

我们首先根据是否会提出提案，将进程分为Proposer和Acceptor。前者提出提案，后者接受提案并进行处理。

1. Proposer发送Propose

   Proposer生成全局ID，并且向所有的机器发送Propose（不需要携带提案内容）。

2. Acceptor应答Propose

   收到Propose后做出两个承诺和一个应答

   两个承诺 : 不再应答Propose ID小于等于该请求的Propose；不再应答Propose小于该请求的Accept请求

   一个应答：返回已经Accept过的提案中Propose ID最大的提案的的Value和Propose ID；如果没有则返回null。

1. Proposer发送Accept

   提案生成规则：Proposer收到多数派的Propose请求后，从应答中选择存在提案，并且Propose ID最大的Value，作为本次Accept的提案。如果所有应答的Value均为空，则携带当前的Propose ID和新的值，向集群发送Accept请求。

2. 应答Accept

   Acceptor收到Accept请求后，在不违背两个承诺的前提下，持久化当前的Propose ID和Value，形成决议。

一些不同的情况

说明：

S1 - S5 ：所有的进程集合。

X，Y：由进程提出的不同的议案的值。

黑框白底：成功的Propose和Accept。

黑框绿底：虽然Accept但没有在系统中达成一致的Accept。

上图中的S1提出了X并被多数派同意，S5在提出propose时获取到了X的值。

上图中的S1提出了X，但只被S3同意；S5在提出propose时恰好询问到了S3，并将X值更新给了S4和S5。

P1并没有被多数派Accept，同时也没有被P2学习到。P2可以Accept自己的Value Y；后续P1的Accept会失败、同时进行下一轮提案，最终也学习到了Value Y。

P1并没有被Accept的时候，P2提出，然后P3提出，然后P4提出……S3永远无法应答Accept请求。

这种情况称之为活锁。

Paxos的边界

两将军问题、FLP不可能性，这都说明分布式系统在故障发生时的通过算法实现一致性无法100%保证。

我们再来看Paxos的Liveness保证，注意，这里只是保证了“肯定就变量值达成一致”，而没解释具体的结束时间。这里引申出来活锁问题：

询问阶段：确定谁的编号更高，更高编号的才能proposal。 提交阶段：编号更高者提交的proposal如果没有其它节点提出的更高的Proposal，则可以通过；如果有，则从头重来。

试想如果不停有更高Proposal的产生，则算法永远无法结束。虽然Paxos在工程中应用广泛，但活锁是Paxos无法解决的硬伤。

有兴趣的话会继续研究下Multi-Paxos和Raft。