Paxos算法Paxos算法基于yxdkh在1990年提出的消息传递，是一种容错的一致性算法。
在有问题的分布式系统中的节点通信中存在两种模型：共享存储器(Shared memory )和消息传递。
在基于消息收发通信模型的分布式系统中，不可避免地出现以下错误。 进程可能会变慢、被杀、或重新启动、消息可能会延迟、丢失、重复。 在基本的Paxos场景中，首先不考虑有可能发生消息篡改，也就是拜占庭错误。
Paxos算法解决的问题是，在可能发生上述异常的分布式系统中，如何对某个值达成一致，确保出现上述任何异常都不破坏决议的一致性。
一个典型的情况是，在分布式数据库系统中，每个节点的初始状态一致，每个节点执行相同的操作序列最终会得到一致的状态。
为了使每个节点执行相同的指令序列，必须对每个指令执行一致性算法，以确保每个节点所识别的指令的一致性。
常用的一致性算法可以应用于许多场景，是分布式计算中的重要问题。
很久以前，在国王dsdbbt Lamport的统治下，有一个黑暗的希腊城邦paxos。
城邦里有三种人，
决策者们虽然这是一个黑暗的城邦，但却是民主的。 按照议会民主制的政治模式制定法律，大众无论有什么提案和意见都可以写提案交给提案人。 提案人将提案交给决策者决定。 决策者有奇数个，为什么需要奇数个呢？ 之所以简单，是因为决策方式麻木不仁，少数服从多数。
最后决策者向天下呼吁了刚出台的决策，大众知道了决策结果。
等一下，哪里黑了？ 问题是“提案者将提案交给决策者进行决策”，那么很多提案决策者首先会做出谁的决策呢？ 谁给了很多钱决定是谁的。
那有几个问题。 决策者很多。 保证最后决策是同样的建议。 而且，如何保证获得所有提案人中的最高报价？
聪明贪婪的决策者想出了分两个阶段报价的方法。
第一阶段的决策者接受所有比目前持有报价的人更高的报价，不会通知持有以前报价的人
提案者向所有决策者提出报价，如果有人高于自己的报价，就涨价，如果半数以上的决策者接受自己的报价，就中止报价。
第一阶段结束的状态下任何提案人都很高兴半数以上的大人物接受了自己的提案。
决策者群体目前的状态是一致的，半数以上同意的建议只有一个，这是报价最高的(因为高的总是可以覆盖低的)，具体是谁给出的who care，一致就可以了。
第二阶段的提案人去给收到自己钱的大人物签合同。 这里有三种情况。
大牌收了别人更高的价格，回去拿钱继续行贿，回到第一阶段重新升级大牌收到的最高报价是自己的，美滋滋的，半数以上签署了合同，提案成功； 据了解，在提案人回去拿钱回来继续行贿的过程中，签订了合同，半数以上在这个提案上签名。 不要，把自己的提案变成已经签订的提案，再提交给所有的大人物，看能不能分一杯羹遇到还没有签订的大人物。 第二阶段结束后的状态是所有提案人手头的提案都一样，因为有“尽快用已经签字的提案替换自己的提案”的步骤； 决策者小组所有成员最终接受的建议是一样的。
好的目的已经达到，把这个提案证实给天下，让所有的群众都知道这件事。
谈话结束后，用正确的姿势简单介绍paxos
paxos算法的介绍角色在paxos算法中可以分为四种角色。
加速器：决策者
Proposer :提案人
客户端：产生议题的人(大众) ) )。
Learner :最终的决策学习者(大众) )
第一阶段的Proposer将Prepare请求发送到半数以上的加速器，并编号n。
如果加速器收到编号为n的Prepare请求，并且n大于该加速器已经响应的所有Prepare请求的编号，则它将向Proposer发送已接受的编号最大的建议(如果有)作为响应
如果Proposer没有收到半数以上加速器的响应，编号1将继续启动请求。
阶段2(proposer收到半数以上的加速器对发出的编号n的Prepare请求的响应时，会向半数以上的加速器发送[N，提案]的accept请求。
如果加速器收到对编号为n的建议的Accept请求，则只要加速器没有响应编号为sxdxs的Prepare请求，它就会接受该建议
此外，一个Paxos流程只能批准一个value，只有在prepare中的value被许多加速器接受后才能批准，并且授权的value允许learner使用。
为什么需要多个决策者Acceptor？ 如果一个加速器有多个proposer，则加速器可以选择其中一个方案。 很棒，但有一个单一的问题。
为什么要用“半数以上通过”的方法进行决策？ 一个集合不能同时存在两个以上一半以上的子集，一半的思想保证所提出的value在同一点是分布式系统中唯一一致的。
这个提交方法与propose无关
r接受到的消息是接受了谁的提议过半，只保证是有提议过半了的。然后再在第二阶段确定这个过半了的提议，让所有节点知道这件事。因此算法如果能保证value被半数acceptor接受，则意味这此时被认定的value是唯一的。 为什么acceptor要接受多个提案？如果acceptor只能够接受一个提案，则可能发生所有proposer提出的提案都无法达到多数，决策者接收一个就结束了，状态无法一致。
当Proposer有很多个的时候，会有什么问题？很难有一个proposer收到半数以上的回复，进而不断地执行第一阶段的协议，决策收敛速度慢，很久都不能做出一个决策。
提案为什么要带上编号（即故事中用来贿赂的钱）？带上编号是为了决策者可以在自身接受到的提案的对比中做出最终的唯一决策。
试想如果按照提案到达时间对比提案，且不说这样就变成了只接收一个第一到达的提案，还可能因为网络原因每个决策者接受到的提案的先后顺序不一样，凉凉。
接着上面的问题，那如果把所有决策者收到的提案汇集起来选出个时间最早的呢？把提案汇集，这时候肯定需要一个master来做判断，大家有没发现这个master好像就变成了propser，它拿到最早的提案，交给决策者…
其实，这就演变成了paxos的变种协议。
后记为了避免竞争，加快收敛的速度，有人在算法中加入leader来代替propser，且leader在集群中只有一位，也就是说只有leader有权提议。
这时leader会有单点问题，于是又加入了leader选举机制保证健壮性，到目前为止paxos演变的越来越像我下一篇要讲的zab协议了。
协议描述 节点角色Paxos协议中，有三类节点：
Proposer 提案者。Proposer 可以有多个， Proposer 提出议案 value ）。
所谓 value ，在工程中可以是任何操作，例如“修改某个变量的值为某个值”、“设置当前 primary 为某个节点”等等。
Paxos 协议中统一将这些操作抽象为 value。
不同的 Proposer 可以提出不同的甚至矛盾的 value ，例如某个Proposer 提议“将变量 X 设置为 1 ”，另一个 Proposer 提议“将变量 X 设置为 2 ”，但对同一轮 Paxos过程，最多只有一个 value 被批准。
Acceptor ：批准者。Acceptor 有 N 个， Proposer 提出的 value 必须获得超过半数 (N/2+ 的 Ac ceptor 批准后才能通过。
Acceptor 之间完全对等独立。
Learner ：学习者。Learner 学习被批准的 value 。
所谓学习就是通过读取 各个 Proposer 对 value 的选择结果 ，如果某个 value 被超过半数 Proposer 通过，则 Learner 学习到了这个 value 。
这里 类似 Quorum 机制，某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准，从而学习者需要至少读取 N/2+1 个 Accpetor ，至多读取 N 个 Acceptor 的结果后，能学习到一个通过的 value 。
上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。
流程描述Paxos 协议一轮一轮的进行，每轮 都有一个编号。
每轮 Paxos 协议可能会批准一个 value，也可能无法批准一个 value。
如果某一轮 Paxos 协议批准了某个 value，则以后各轮 Paxos 只能批准这个value。
上述各轮协议流程组成了一个 Paxos 协议实例，即一次 Paxos 协议实例只能批准一个 value 这也是 Paxos 协议强一致性的重要体现。
每轮 Paxos 协议分为阶段，准备阶段和批准阶段，在这两个阶段 Proposer 和 Acceptor 有各自的 处理流程。
Proposer 的流程（准备阶段）
向所有的 Acceptor 发送消息“ Prepare(b) 这里 b 是 Paxos 的轮数，每轮递增如果收到任何一个 Acceptor 发送的消息“ Reject( B ))”，则对于这个 Proposer 而言本轮 Paxos 失败，将轮数 b 设置为 B+ 1 后重新步骤 1 （批准阶段，根据收到的 Acceptor 的消息作出不同选择）如果 接收 到的 Acceptor 的“ Promise(b, v _i ))”消息 达到 N/2+1 个（ N 为 Acceptor 总数，除法取整，下同） v_i 表示 Acceptor 最近一次在 i 轮准过 value v 。3.1 如果收到的“ Promise(b, v ))”消息中 v 都 为空， Proposer 选择一个 value v ，向 所有 Acceptor 广播 Accept(b, v)
3.2 否则，在所有收到的“ Promise(b, v i ))”消息中 选择 i 最大的 value v 向所有 Acceptor 广 播消息 Accept(b v
如果收到 Nack(B) B)，将轮数 b 设置为 B+1 后重新步骤 1 Accpetor 流程（准备阶段）
接受某个 Propeser 的消息 Prepare(b) 。参数 B 是该 Acceptor 收到的最大 Paxos 轮数编号 V 是 Acceptor 批准的 v alue ，可以为空
1.1 如果 b>B ，回复 Promise(b, V _B ))，设置 B=b; 表示保证不再接受编号小于 b 的提案。
1.2 否则，回复 Reject(B)
（批准阶段）
接收 Accept(b, v）2.1 如果 b < B, 回复 Nack(B) B)，暗示 propo ser 有一个 更大 编号的提案被这个 Acceptor 接收了
2.2 否则 设置 V=v 。表示这个 Acceptor 批准的 Value 是 v 。广播 Accepted 消息。