Paxos是一个用于实现可容错的分布式系统的算法，主要用于保证分布式集群中多备份系统之间的操作和数据的
一致性。这样集群中的每台机器对外相当于完全一致，从而其互相之间可以互为备份，从而使得系统能够容忍一定
数量的机器出问题（宕机、断网、硬盘损坏等等）。
一、相关概念
paxos是什么
Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于1990年提出的
一种基于消息传递的一致性算法。
paxos诞生背景
Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。
在分布式系统中，多个系统维护数据的最终一致性，Paxos算法就是一种基于消息传递模型的一致性算法。
paxos算法适用的几种情况：一台机器中多个进程/线程达成数据一致；分布式文件系统或者分布式数据库中多客户端
并发读写数据；分布式存储中多个副本响应读写请求的一致性
paxos算法定义的三个角色
- proposers：提案提出者
- acceptors：提案表决者
learners：提案获取者
提案可以理解成所有进程对等待确定的数据的提议值。
安全性前提
- 只有通过提案，才可以接受值，如果没有提案则没有值被接受
- 一个提案只会有一个值被接受
- 只有当一个值被接受后，proposers才知道那个值被接受了
二、推理过程
整个流程可以简单描述为，proposers发出提案，然后acceptors投票表决提案，learners决定用那个提案。
下面通过从简单到复杂的情况推理出算法。
只有一个proposer，一个acceptor
因为只有一个提案被提出，当然应该被批准通过。假设没有失败或者消息丢失，即使仅有一个proposer提出了一个提案，
我们也希望能选择一个提案。因此推导出以下约束
约束1：acceptor必须批准它接收到的第一个提案。
但如果acceptor所在的机器挂了，就没法批准提案了， proposer会等待acceptor的表决，整个流程没法继续下去。
只有一个proposer，多个acceptor
proposer发出提案后，假设acceptors返回两种决策结果，一部分同意改提案，另外一部分就是不同意该提案，
为了公平性，超过一半的acceptors决策者的结果为最终结果，这就意味着需要acceptors的数量为奇数，
而且proposer知道acceptor的数量。
约束2：一个提案的选定，需要半数以上的acceptor批准
acceptor接受一个提案称为“接受”，当有majority个acceptor都接受某提案后，这个提案被“通过"。
同样单个proposer也会出现机器挂了的可能，因此需要多个proposer
多个proposer，多个acceptor
如果有多个proposer，如果每个proposer的提案都不一样，这样所有acceptor接受的值都不一样，这样就没法选出唯一的值。
所以acceptor可以接受多个proposer的提案，但只要是同一个acceptor接受的提案值必须一致。
这样的话我们就需要给每个proposer提案加个id和值，并且必须保证不同提案的id一定不同。id越大，提案时间就最新,ID递增
约束3：如果一个提案【m+value】，并且这个提案通过了，那么后面所有被acceptor接受的提案值都必须是【value】
由于提案如果想被接受，则至少有一个acceptor接受它。为了达到约束3要求，我们可以在满足约束3的基础上，加强约束：
约束4：如果一个值为【m+value】的提案被通过，那么之后被任意一个acceptor接受的提案，其值必须为【value】
假设有proposer1 向acceptorA、acceptorB、acceptorC提出提案1【m+value】，acceptorA和acceptorB都接受了，
acceptorC因为网络问题没有接受，这时候proposer2 向acceptorB发出提案，acceptorC网络好了，在约束一的作用下，
acceptorC通过了提案2，那这样就会同时又两个提案被通过了，会和约束三矛盾，为了达到约束三的要求，我们就需要继续加约束
约束5：如果一个值为【m+value】的提案被通过，则之后(提案的编号大于被接受的提案编号M)任意一个proposer提出的每个提案，值都必须为【value】
当约束1、约束2、约束5满足的时候，约束4一定满足，从而约束3满足。约束5蕴含着约束4
(因为acceptor接受的值都是proposer提出的)，是一个更强的约束。但在约束5的要求下，proposer
需要知道最后一个被通过的提案是哪个，其值是多少。
约束5的特殊情况
会不会出现多个proposer同时提出提案，由于消息传输时间任意，一个proposer无法在提交自己的提案前，
无法知道另一个proposer提交的提案是否在未来先到达acceptor被通过。
比如proposerA、proposerB，提出提案值为m n，A先提出提案,B这时也要提出提案，它该提还是不提呢？
约束5要求下，A需要知道B的提案是否能被通过，从而判断自己提案的值是否必须和B提案一样，
还是可以自己选一个新值？这个对A来说无法回答。所以我们要加强约束5。
假设有编号为m的提案，值V已经被通过了，我们要证明M之后的提案必须是值V从而证明约束5。
设 n > m，假设 m .. (n - 1) 提案的值都是v。 提案我们假设被通过，
则一定有多个acceptor组成集合C，C内每个acceptor都接受了v这个值。
在约束4的要求下，我们可以说，C集合内的每个acceptor都接受了从m ~ (n-1)中的
某个提案(单是假设就保证了这些acceptor都至少接受了m提案)，
并且m ~ (n-1)个提案中，被任意一个C集合内的acceptor接受的提案，值都得为v。
那么递推到第n个提案，它找出一个集合S，由多个acceptor组成。那么n提案如果想被接受，
S内所有acceptor要么从未接受过任何提案(当前面m提案被通过的假设成立的时候这个条件不成立)，
要么第n提案的值也为v。因为S集合必然会和C集合有交集，都是多数的。作为交集的那个acceptor值已经接受了v值，
所以n提案如果不用v值，则不可能让S内所有acceptor都接受。
约束6 : 有多个acceptor组成集合S，为了值为v提案号为n的提案被通过，必须保证以下条件之一成立
a) S内所有acceptor没有接受过任何在n之前的提案；
b) S内任意一个acceptor之前接受过的小于n的提案值为v。
但如果n提案之前的n-1提案，可能还在传输过程中。proposer在提出提案n的时候，即使询问acceptor并
得到回应说从未接受过某提案，proposer提出提案n的时候可能还是比n-1提案晚。
出现询问n提案能不能提出 < n-1提案被接受 < n提案到达acceptor。的时间序，从而破坏约束6
所以，
约束7：proposer询问acceptor是否能提出提案n时，必须要求acceptor给出一个保证，保证n提案之前的提案一定不被接受，
或者acceptor可以批准一个编号为n的提案，当且仅当它没有回应过一个编号大于n的提案，从而保证约束6。
三、算法流程
1、准备阶段
prepare请求只需要带着提案号，而不需要带着值。
1、proposer获取一个提案编号M，根据M向一个acceptor集合（超过半数）的所有acceptor询问当前是否有已经被
批准的提案，acceptor判断M是否大于自己已经批准过的所有的提案编号，如果是，则返回已批准的编号<M且最大的提案。
2、如果否，可以不响应，如果acceptor之前没有批准过任何提案，则返回空
3、acceptor不再批准编号小于M的提案
4、proposer收到acceptor的响应（acceptor超过半数），如果为空，则自己可以任意设置value的值，
如果返回了已批准的提案，则必须以编号最大的提案的value作为自己的value，生成<M,value>作为自己要发起的提案。
如果未超过半数，则重复此阶段。
假设：M>M1>m0,acceptor1，acceptor3之前都同意过批案M1，acceptor4之前同意过批案M0，acceptor2
没有批准过任何批案。
超过半数返回，而且M1编号最大，由此可以推导出proposer将以M1的value作为自己的提案<M,value>发起表决请求。
2、表决阶段
1、proposer确定了自己的提案<M,value>后，会向一个acceptor集合（超过半数且不一定是上一个集合）
的所有acceptor发起提案
2、当且仅当acceptor没有对某个编号大于M的prepare请求做过响应时就可以批准该提案，
或者acceptor没有批准过比M编号更小的提案，就可以批准该提案。
3、超过半数的acceptor批准了提案后，就对value的值达到了一致性，没有的话，则从准备阶段重复
假设：acceptor4，acceptor5，acceptor6 都没有批准过比M更小的提案，那就可以通过该提案了。
3、学习阶段
提案被确定后就可以通过learner获取了，获取的方式有很多种，可以根据具体情况选择，如：
1、acceptor批准提案后，立即发送给所有learner
2、acceptor批准后都把提案发给特定的learner，然后由此learner通知其它learner
3、acceptor批准后都把提案发给特定的learner集合，由此集合通知其它learner