本文章来源于：https://github.com/Zeb-D/my-review ，请star 强力支持，你的支持，就是我的动力。
[TOC]
背景
下面介绍Paxos 协议，它是一个比两阶段提交要轻量的保证一致性的协议。
在分布式系统中，节点之间的信息交换有两种方式，
一种是通过共享内存共用一份数据；
另一种是通过消息投递来完成信息的传递。
而在分布式系统中，通过消息投递的方式会遇到很多意外的情况，
例如网络问题、进程挂掉、机器挂掉、进程很慢没有响应、进程重启等情况，这就会造成消息重复、一段时间内部不可达等现象。Paxos 协议是帮助我们解决分布式系统中一致性问题的一个方案。
拜占庭将军问题
使用Paxos 协议有一个前提，那就是不存在拜占庭将军问题。
拜占庭位于现在土耳其的伊斯坦布尔，是东罗马帝国的首都。当时拜占庭罗马帝国国土辽阔，防御敌人的各个军队都分隔很远，将军与将军之间只能靠信差传消息。
在战争时，拜占庭军队内所有将军和副官必须达成共识，决定出是否有赢的机会才去攻打敌人的阵营。但是，在军队内可能有叛徒或敌军的间谍，扰乱将军们的决定又扰乱整体军队的秩序，他们使得最终的决定结果并不代表大多数人的意见。这时，在已知有成员谋反的情况下，其余忠诚的将军应该如何不受叛徒的影响达成一致的协议？
拜占庭将军问题就此形成。也就是说，拜占庭将军问题是一个没有办法保证可信的通信环境的问题，Paxos 的前提是有一个可信的通信环境，也就是说信息都是准确的，没有被篡改。
Paxos 算法 角色
Paxos 算法的提出过程是，虚拟了一个叫做Paxos 的希腊城邦，并通过议会以决议的方式介绍Paxos 算法。
首先把议员的角色分为了Proposers 、Acceptors 和Learners ，议员可以身兼数职，介绍如下。
Proposers ，提出议案者，就是提出议案的角色。
Acceptors ，收到议案后进行判断的角色。Acceptors 收到议案后要选择是否接受（Accept ）议案，若议案获得多数Acceptors 的接受，则该议案被批准（Chosen ）。
Learners ，只能“学习”被批准的议案，相当于对通过的议案进行观察的角色。在Paxos 协议中，有两个名词介绍如下。Proposal ，议案，由Proposers 提出，被Acceptors 批准或否决。
Value ，决议，议案的内容，每个议案都是由一个{ 编号，决议} 对组成。在角色划分后，可以更精确地定义问题，如下所述：决议（Value ）只有在被Proposers 提出后才能被批准（未经批准的决议称为“议案（Proposal ）”）。在Paxos 算法的执行实例中，一次只能批准（Chosen ）一个Value 。Learners 只能获得被批准（Chosen ）的Value 。
协议过程
对议员来说，每个议员有一个结实耐用的本子和擦不掉的墨水来记录议案，议员会把表决信息记在本子的背面，本子上的议案永远不会改变，但是背面的信息可能会被划掉。每个议员必须（也只需要）在本子背面记录如下信息：LastTried[p] ，由议员p 试图发起的最后一个议案的编号，如果议员p 没有发起过议案，则记录为负无穷大。PreviousVote[p] ，由议员p 投票的所有表决中，编号最大的表决对应的投票，如果没有投过票则记录为负无穷大。NextBallot[p] ，由议员p 发出的所有LastVote （b,v ）消息中，表决编号b 的最大值。
基本协议的完整过程如下。
（1 ）议员p 选择一个比LastTried[p] 大的表决编号b ，设置LastTried[p] 的值为b ，然后将NextBallot （b ）消息发送给某些议员。
（2 ）从p 收到一个b 大于NextBallot[q] 的NextBallot （b ）消息后，议员q 将NextBallot[q] 设置为b ，然后发送一个LastVote （b,v ）消息给p ，其中v 等于[q] （b≤NextBallot[q] 的NextBallot （b ）消息将被忽略）。
（3 ）在某个多数集合Q 中的每个成员都收到一个LastVote （b,v ）消息后，议员p 发起一个编号为b 、法定人数集为Q 、议案为d 的新表决。然后它会给Q 中的每一个牧师发送一个BeginBallot （b,d ）消息。
（4 ）在收到一个b=NextBallot[q] 的BeginBallot （b,d ）消息后，议员q 在编号为b 的表决中投出他的一票，设置[p] 为这一票，然后向p 发送Voted （b,q ）消息。
（5 ）p 收到Q 中每一个q 的Voted （b,q ）消息后（这里Q 是表决b 的法定人数集合，b=LastTried[p] ），将d （这轮表决的法令）记录到他的本子上，然后发送一条Success （d ）消息给每个q 。
（6 ）一个议员在接收到Success （d ）消息后，将决议d 写到他的本子上。
从上面的介绍可以看出，Paxos 不是那么容易理解的，不过总结一下核心的原则就是少数服从多数。
总结
大家会发现，如果系统中同时有人提议案的话，可能会出现碰撞失败，然后双方都需要增加议案的编号再提交的过程。而再次提交可能仍然存在编号冲突，因此双方需要再增加编号去提交。这就会产生活锁。
解决的办法是在整个集群当中设一个Leader ，所有的议案都由他来提，这样就可以避免这种冲突了。这其实是把提案的工作变为一个单点，而引发的新问题是如果这个Leader 出问题了该如何处理，那就需要再选一个Leader 出来。
参考
以上对于Paxos 的介绍只是一个非常基础的介绍，读者如果想对此有更深入的了解，可以阅读The Part-Time Parliament 、Made Simple 、on Transaction Commit 、Paxos 、Paxos 等论文，也可以参考维基百科上Paxos 的资料，网址为-http://en.wikipedia.org/wiki/Paxos_ （computer_science ）。
延伸
有兴趣的小伙伴可以参考下 ZAB算法与paxos算法对比，也可以了解下数据一致性算法