分布式共识算法之Paxos

算法主要实体组成

1. 客户端：向分布式系统发送请求的主体
2. 提议者：当提议者接受到客户端的请求后，发起提案让接收者接受
3. 接收者：又可以叫投票者，接受或者拒绝提议者的提案，当超过半数的接收者接受了某一提案，那么提案就被接受了
4. 学习者：只会学习提案，不会参与决议，学习接收者同意的提案，向客户端响应，可以设置多个学习者实现系统的高可用

算法的实现流程

整个算法主要分为两个阶段：

第一阶段/prepare

提议者接受到客户端的请求后，开始向超过半数的接收者进行广播提案编号，这次广播不会涉及提案值，仅向接收者广播本次提案的编号。

接受者收到提议者的议案编号广播后，处理流程如下：

首先看接受到的提案编号是不是接收者见到的值最大的提案编号，如果已经见过比本次提案编号更大的提案编号了，就拒绝响应，否则，就看看自己是否已经接受了某个提案值，如果已经接受了之前提案编号的提案值，就把接受的提案值和提案编号作为内容响应提议者，如果没有过接受提案值，那么就向提议者响应promise，并承诺不会再接受小于此次提案编号的提案值

第二阶段/propose

当提议者接受到了超过半数的接受者响应的promise后，就开始向多数派发起accept请求了，这次会带上提案编号和提案值。

提案值的选择按照这样的规则，首先在收到的半数的接受者响应的promise中有没有已经接受的提案值，如果有的话，就选取其中提案编号最大的提案值作为本次accept请求的提案值，如果一个都没有，那就自己决议提案值是什么。

接受者收到提议者的accept请求后，处理流程如下：

当接受到提议者的accept请求后，先查看提案编号是不是自己见过的最大的编号值，如果是的话，就保存本次accpet的提案编号值和提案值，然后向提议者和所有学习者响应，否则的话就拒绝请求。

活锁问题

这里的Paxos有一个活锁问题，如下案例：提议者a发送prepare请求，接收者接受到了提议者a的prepare请求，但是由于网络的原因，提议者2的prepare请求编号更大，且先于提议者a的accept请求，如此进行反反复复造成活锁，接受者会始终处于决议提案编号的过程中，谁也不能最终决议。