Paxos算法简介

什么是Paxos算法：

	Paxos算法是Lamport提出的一种基于消息传递的分布式一致性算法。

解决了什么问题：

	解决了分布式系统一致性问题。分布式系统采用多副本进行存储数据，如果对多个副本执行序列不控制，那多个副本执行更新操作，由于网络延迟超时等故障导致各个副本的数据不一致。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致。

相关概念：

	提案（Proposal）：Proposal信息包括提案编号和提议的值。
	在Paxos算法中，有如下角色：
	Client：客户端，客户端向分布式系统发出请求，并等待响应。例如，对分布式文件服务器中文件的写请求。
	Proposer：提案发起者，提案者提倡客户需求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推动协议向前发展。
	Acceptor：决策者，可以批准提案，Acceptor可以接受提案，如果某个提案被选定，那么该提案里的value就被选定了。
	Learners：最终决策的学习者，学习者充当该协议的复制因素。

问题描述：假设有一组可以提出提案的进程集合，那么对于一个一致性算法需要保证以下几点：

	在这些被提出的提案中，只有一个会被选定。
	如果没有提案被提出，就不应该有被选定的提案。
	当一个提案被选定后，那么所有进程都应该能学习到这个被选定的value

推导过程：

只有一个Acceptor：
假设只有一个Acceptor，只要Acceptor接受它收到的第一个提案，则该提案被选定，改提案里的value就是被选定的value。这样就保证只有一个value会被选定。
但是，如果这个唯一的Acceptor宕机了，那么整个系统就无法工作了，因此必须要多个Acceptor。
多个Acceptor：
如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢。
首先我们希望即使只有一个Proposer提出了一个value，改value也最终被选定。那么就会有下面约束：
P1:一个Acceptor必须接受它收到的第一个提案。
但是，这会引出另一个问题：如果每个Proposer分别提出不同的value，发给不同的Acceptor。根据P1，Acceptor分别接受自己收到的第一个提案，就导致不同的value被选定。出现了不一致的情况。
因此，我们需要加一个规定：
一个提案被选定需要被半数以上的Acceptor接收。
这个规定又暗示了一个Acceptor必须能够接受不止一个提案，不然可能导致最终没有value被选定。
所以在这种情况下，我们使用一个全局的编号来标识每一个Acceptor批准的提案，当一个具有某value值的提案被半数以上的Acceptor批准后，我们就认为改value被选定了。
根据上面的内容，我们现在虽然允许多个提案被选定，但必须保证所有被选定的提案都具有相同的value值，否则又会出现不一致。
于是有了下面的约束：
P2:如果某个value为v的提案被选定了，那么每个编号更高的被选定提案的value必须也是v。
一个提案只有被Acceptor接受才可能被选定，因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。
P2a：如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接收的value必须也是v。
只要满足了P2a,就能满足P2.
但是考虑如下情况：假设总的有5个Acceptor。Proposer2提出[M1,V1]的提案，Acceptor2~5均接受了该提案，于是对于Acceptor2～5和Proposer2来讲，它们都认为V1被选定。Acceptor1刚刚从宕机状态恢复过来，此时Proposer1向Acceptor1发送了[M1,V2]的提案，对于Acceptor1来讲，这是它收到的第一个提案。根据P1，Acceptor必须接受该提案，同时Acceptor认为v2被选定。这就出现了两个问题：
1.Acceptor1认为V2被选定，Acceptor2~5和Proposer2认为V1被选定。出现了不一致。
2.V1被选定了，但是编号更高的被Acceptor1接受的提案[M2,V2]的value为V2，且V2不等于V1.这就跟P2a矛盾了。
所以我们要对P2a约束进行强化。
P2a是对Acceptor接受的提案约束，但其实提案是Proposer提出来的，所以我们可以对Proposer提出的提案进行约束。得到P2b：如果某个value为v的提案被选定了，那么之后任何Proposer提出编号更高的提案的value必须也是v.
如何保证在某个value为v的提案被选定后，Proposer提出的编号更高的提案的value都是v
P2c：对于任意的Mn和Vn，如果提案[Mn,Vn]被提出，那么肯定存在一个有半数以上的Acceptor组成的集合S，满足一下两个条件中的任意一个：
要么S中每个Acceptor都没有接受过小于Mn的提案。
要么S中所有的Acceptor批准的所有编号小于Mn的提案中，编号最大的那个提案的value值为Vn