参考：
https://my.oschina.net/linlifeng/blog/78918
http://blog.csdn.net/cnh294141800/article/details/53768464
Paxos算法是分布式中一个著名的一致性算法。它的假设前提是，在分布式系统中进程之间的通信会出现丢失、延迟、重复等现象，但不会出现传错的现象。Paxos算法就是为了保证在这样的系统中进程间基于消息传递就某个值达成一致。要理解paxos算法最好还是看作者本人(Leslie Lamport)的论文《The Part-Time Parliament》。在这里只是简单地介绍paxos最核心的思想，其实它还有很多的内容。
Paxos算法的目的
Paxos算法的目的是为了解决分布式环境下一致性的问题。
多个节点并发操纵数据，如何保证在读写过程中数据的一致性，并且解决方案要能适应分布式环境下的不可靠性（系统如何就一个值达到统一）
Paxos的两个组件
提议者和决议者是这里最重要的两个角色，paxos最核心的算法就是定义他们之间的通讯规则来保证某个变量在分布式系统中的一致性。
Proposer
提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。
Acceptor
提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值
Paxos有两个原则
- 安全原则---保证不能做错的事
a) 针对某个实例的表决只能有一个值被批准，不能出现一个被批准的值被另一个值覆盖的情况；(假设有一个值被多数Acceptor批准了，那么这个值就只能被学习)
b) 每个节点只能学习到已经被批准的值，不能学习没有被批准的值。 - 存活原则---只要有多数服务器存活并且彼此间可以通信，最终都要做到的下列事情：
a) 最终会批准某个被提议的值；
b) 一个值被批准了，其他服务器最终会学习到这个值。
Paxos的两个阶段
第一阶段（prepare）
- 获取一个proposal number, n；
- 提议者向所有节点广播prepare(n)请求；
- 接收者（Acceptors比较善变，如果还没最终认可一个值，它就会不断认同提案号最大的那个方案）比较n和minProposal，如果n>minProposal,表示有更新的提议minProposal=n；如果此时该接受者并没有认可一个最终值，那么认可这个提案，返回OK。如果此时已经有一个accptedValue, 将返回(acceptedProposal,acceptedValue)；
- 提议者接收到过半数请求后，如果发现有acceptedValue返回，表示有认可的提议，保存最高acceptedProposal编号的acceptedValue到本地
第二阶段(Accept)
- 广播accept(n,value)到所有节点；
- 接收者比较n和minProposal，如果n>=minProposal,则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；
否则，拒绝并且返回minProposal - 提议者接收到过半数请求后，如果发现有返回值>n，表示有更新的提议，跳转1（重新发起提议）；否则value达成一致。
提议者是提出议案的人。每个议案都有一个议案号，议案号是区别不同议案的唯一标识，而且议案号是有大小次序的。这里的提议者不像我们真实世界里的提议者，这里的提议者提的议案内容不能随心所欲。提议者和决议者要遵循下面的规则：
1） 提议者先给议案决定一个议案号，注意整个系统中议案号都不能重复的。然后发消息给所有决议者，告诉他们我要提出第几号议案。
第一阶段，提议者甲向决议者A、B、C、D、E、F、G发出议案号16的消息。
2） 决议者收到提议者发来的议案号后先看这个议案号是否是自己收到的所有议案号中最大的。如果不是，就不予理会；如果是，就把自己最后一次投票的议案发回去，如果没投过议案就回复没投过议案。
第二阶段，决议者收到甲发来的议案号16后根据自己的情况作出回复
A、D未投过任何议案所以回复(null)
B最后一次投了2号议案所以回复(2,α)
C、F最后一次投了5号议案所以回复(5,β)
E的最大议案号是21所以不用回复
G由于网络原因没收到消息
3） 当提议者收到过半回复后才能决定议案的内容。在所有回复中议案号最大的那个议案的内容就定为当前议案的内容。如果都回复没投过议案，那议案内容就由自己定了。如果只收到不过半数的回复，那么这个过程就这样结束了。确定议案内容后就要把议案发给所有决议者。到此提议者的工作就可以结束了。
第三阶段，甲根据回复确定16号议案的内容，然后正式提出16号议案。
甲收到过半数人的回复，回复的内容有(null)、(2,α)、(5,β)，其中5是最大的议案号，所以16号议案的内容就定为β,接着甲就把(16,β)发出去。
4） 决议者收到议案后，就要对它进行投票。如果这个议案号是自己收到的所以议案号中最大的，就要投这个议案的票；否则就不予理会。这里的投票没有反对或赞成的类型之分。也就是可以认为只有赞成票。到此决议者的工作就可以结束了。
第四阶段，决议者收到16号议案并对它投票。
A、B、C、G收到(16,β)后，由于16号是他们的最大号，所以会给这个议案投票
D、E、F收到(16,β)后，由于21号是他们的最大号，所以不投票。
这个算法保证了某个变量在分布式系统中要么没有值，要么就只会有一个值。只要某个议案在某一刻有过半数的人投票，那么这个值就永远定下来了。
如上图，15号议案(内容是β)有了过半数的投票，那么它的下一号16号议案内容只能是β了，因为在第三阶段收到的回复如果过半数，那么其中一定有(15,β)，而15肯定是回复中最大的号，所以内容只能是β。而下下一号21号议案内容也只能是β，因为它的前两个议案的内容都是β，如果收到的回复过半数的话肯定包含(15,β)或(16,β)，而他们都是最大的两个，所以内容也只能是β了。可以证明其后的所有议案内容都是β。虽然paxos算法可以保证不会有两个值，但显然不能保证一定会有值。这也是理论上(CAP理论)不能解决的问题。
这里的算法是有改动的，提议者和决议者都还有后续的处理，而且关于上面的“过半数的决议者”也并不是Paxos本身的描述。Paxos本身定义的是一个更一般的“大多数”集合，每个议案都有一个“大多数”的决议者集合S，这些集合是两两相交的，对于每个议案，在第三阶段要收到S中所有决议者的回复才能继续下去。如果某个议案得到相应S的全体投票，那么这个值就这么定下来了。
我们再来看一个例子
假设的3军问题
- 1支红军在山谷里扎营，在周围的山坡上驻扎着3支蓝军；
- 红军比任意1支蓝军都要强大；如果1支蓝军单独作战，红军胜；如果2支或以上蓝军同时进攻，蓝军胜；
- 三支蓝军需要同步他们的进攻时间；但他们惟一的通信媒介是派通信兵步行进入山谷，在那里他们可能被俘虏，从而将信息丢失；或者为了避免被俘虏，可能在山谷停留很长时间；
- 每支军队有1个参谋负责提议进攻时间；每支军队也有1个将军批准参谋提出的进攻时间；很明显，1个参谋提出的进攻时间需要获得至少2个将军的批准才有意义；
- 问题：是否存在一个协议，能够使得蓝军同步他们的进攻时间？
接下来以两个假设的场景来演绎BasicPaxos；参谋和将军需要遵循一些基本的规则
- 参谋以两阶段提交（prepare/commit）的方式来发起提议，在prepare阶段需要给出一个编号；
- 在prepare阶段产生冲突，将军以编号大小来裁决，编号大的参谋胜出；
- 参谋在prepare阶段如果收到了将军返回的已接受进攻时间，在commit阶段必须使用这个返回的进攻时间；
两个参谋先后提议的场景
- 参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
- 3个将军收到参谋1的提议，由于之前还没有保存任何编号，因此把（编号1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（ok）；
- 参谋1收到至少2个将军的回复，再次派通信兵带信给3个将军，内容为（编号1，进攻时间1）；
- 3个将军收到参谋1的时间，把（编号1，进攻时间1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（Accepted）；
- 参谋1收到至少2个将军的（Accepted）内容，确认进攻时间已经被大家接收；
- 参谋2发起提议，派通信兵带信给3个将军，内容为（编号2）；
- 3个将军收到参谋2的提议，由于（编号2）比（编号1）大，因此把（编号2）保存下来，避免遗忘；又由于之前已经接受参谋1的提议，因此让通信兵带信回去，内容为（编号1，进攻时间1）；
- 参谋2收到至少2个将军的回复，由于回复中带来了已接受的参谋1的提议内容，参谋2因此不再提出新的进攻时间，接受参谋1提出的时间；
两个参谋交叉提议的场景
- 参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
- 3个将军的情况如下
a) 将军1和将军2收到参谋1的提议，将军1和将军2把（编号1）记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
b) 负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议； - 参谋2在同一时间也发起了提议，派通信兵带信给3个将军，内容为（编号2）；
- 3个将军的情况如下
a) 将军2和将军3收到参谋2的提议，将军2和将军3把（编号2）记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
b) 负责通知将军1的通信兵被抓，因此将军1没收到参谋2的提议； - 参谋1收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号1，进攻时间1）；
- 2个将军的情况如下
a) 将军1收到了（编号1，进攻时间1），和自己保存的编号相同，因此把（编号1，进攻时间1）保存下来；同时让通信兵带信回去，内容为（Accepted）；
b) 将军2收到了（编号1，进攻时间1），由于（编号1）小于已经保存的（编号2），因此让通信兵带信回去，内容为（Rejected，编号2）； - 参谋2收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号2，进攻时间2）；
- 将军2和将军3收到了（编号2，进攻时间2），和自己保存的编号相同，因此把（编号2，进攻时间2）保存下来，同时让通信兵带信回去，内容为（Accepted）；
- 参谋2收到至少2个将军的（Accepted）内容，确认进攻时间已经被多数派接受；
- 参谋1只收到了1个将军的（Accepted）内容，同时收到一个（Rejected，编号2）；参谋1重新发起提议，派通信兵带信给3个将军，内容为（编号3）；
- 3个将军的情况如下
a) 将军1收到参谋1的提议，由于（编号3）大于之前保存的（编号1），因此把（编号3）保存下来；由于将军1已经接受参谋1前一次的提议，因此让通信兵带信回去，内容为（编号1，进攻时间1）；
b) 将军2收到参谋1的提议，由于（编号3）大于之前保存的（编号2），因此把（编号3）保存下来；由于将军2已经接受参谋2的提议，因此让通信兵带信回去，内容为（编号2，进攻时间2）；
c) 负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议； - 参谋1收到了至少2个将军的回复，比较两个回复的编号大小，选择大编号对应的进攻时间作为最新的提议；参谋1再次派通信兵带信给有答复的2个将军，内容为（编号3，进攻时间2）；
- 将军1和将军2收到了（编号3，进攻时间2），和自己保存的编号相同，因此保存（编号3，进攻时间2），同时让通信兵带信回去，内容为（Accepted）；
- 参谋1收到了至少2个将军的（accepted）内容，确认进攻时间已经被多数派接受；
基本思想
Paxos主要用于保证分布式存储中副本（或者状态）的一致性。副本要保持一致，那么，所有副本的更新序列就要保持一致。因为数据的增删改查操作一般都存在多个客户端并发操作，到底哪个客户端先做，哪个客户端后做，这就是更新顺序。如果不是分布式，那么可以利用加锁的方法，谁先申请到锁，谁就先操作。但是在分布式条件下，存在多个副本，如果依赖申请锁+副本同步更新完毕再释放锁，那么需要有分配锁的这么一个节点（如果是多个锁分配节点，那么又出现分布式锁管理的需求，把锁给哪一个客户端又成为一个难点），这个节点又成为单点，岂不是可靠性不行了，失去了分布式多副本的意义，同时性能也很差，另外，还会出现死锁等情况。
所以，说来说去，只有解决分布式条件下的一致性问题，似乎才能解决本质问题。
Paxos解决这一问题利用的是选举，少数服从多数的思想，只要2N+1个节点中，有N个以上同意了某个决定，则认为系统达到了一致，并且按照Paxos原则，最终理论上也达到了一致，不会再改变。这样的话，客户端不必与所有服务器通信，选择与大部分通信即可；也无需服务器都全部处于工作状态，有一些服务器挂掉，只有保证半数以上存活着，整个过程也能持续下去，容错性相当好。
