1、paxos是什么，怎么提出来的
Paxos算法是Lamport于1990年提出的一种基于消息传递的一致性算法。Paxos 算法是分布式一致性算法，用来解决一个分布式系统如何就某个 决议 达成一致的问题，目前公认的解决分布式一致性问题最有效的算法之一。
Lamport大师说:
The Paxos algorithm, when presented in plain English, is very simple.
Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。
Paxos 协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。
2、作用、用途
在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。paxos算法理论就是 解决这种分布式场景中的一致性问题。
在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个"一致性算法"以保证每个节点看到的指令一致。
chubby锁服务使用paxos作为chubby cell中的一致性算法，paxos的人气从此一路狂飙。
zookeeper的zab协议也是paxos的变种。
PhxPaxos是腾讯公司微信后台团队自主研发的一套基于Paxos协议的多机状态拷贝类库。
“X-Paxos”是阿里巴巴数据库团队面向高性能、全球部署以及阿里业务特征等需求，实现的一个高性能分布式强一致的Paxos独立基础库。
3、原理过程
- 三个角色
提议者proposer:提出议案
接受者acceptor:
学习者learner:
有的，还有client的角色。
一个进程可以有多种角色。
- 条件（约束）
Paxos是基于消息传递的通讯模型的。
Paxos保证以下三点：1. 只有被提出提案才能被选定；2. 只有一个值被选定；3. 如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个。
多个Acceptor(如果是一个，那宕机就完蛋了)
P1：一个Acceptor必须接受它收到的第一个提案。
规定：一个提案被选定需要被半数以上的Acceptor接受
P2：如果某个value为v的提案被选定了，那么每个编号更高的被选定提案的value必须也是v。
P2a：如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v。
P2b：如果某个value为v的提案被选定了，那么之后任何Proposer提出的编号更高的提案的value必须也是v。
-
两个阶段（主要）
prepare 阶段（预提案阶段）：
1.Proposer 选择一个提案编号 n，然后向acceptor的某个超过半数的子成员发送编号为n的 prepare 请求；
2.Acceptor 收到 prepare 消息后，如果提案的编号n大于该acceptor已经回复的所有 prepare 请求的编号，则 Acceptor 将自己已经批准的最大编号提案回复给 Proposer，并承诺不再接受任何编号小于 n 的提案；
acceptor阶段（提案阶段）：
1.当一个 Proposer 收到了半数以上的 Acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的 Acceptors 发送 accept 请求，包括编号 n 和根据 prepare阶段 决定的 value。这里的value是所有响应中编号最大的提案的value（如果根据 prepare 没有已经接受的 value，那么它可以自由决定 value）。
2.在不违背自己向其他 Proposer 的承诺的前提下，Acceptor 收到 accept 请求后即接受这个请求。即如果acceptor收到这个针对n提案的accep请求，只要改acceptor尚未对编号大于n的prepare请求做出过响应，它就可以通过这个提案。 -
learner学习阶段
示例：
4、优缺点
算法本身的推导过程有点晦涩难懂，理论性算法，工程上实现起来比较麻烦（别人说的）
活锁问题
参考 ：
https://www.zhihu.com/question/19787937
http://harry.me/blog/2014/12/27/neat-algorithms-paxos/
网友评论