分布式共识算法-paxos
背景
Paxos算法是由Lamport提出的一种基于消息传递的协商共识算法。现在Paxos算法已经成了分布式系统最重要的理论基础，为了解释清楚Paxos算法，Lamport虚构了一个叫做“Paxos”的希腊城邦，这个城邦按照民主制度制定法律，却又不存在一个中心化的专职立法机构，而是靠着“兼职议会”来完成立法。这就无法保证所有城邦居民都能够及时地了解新的法律提案，也无法保证居民会及时为提案投票。
工作流程
Paxos算法将分布式系统中的节点分为提案节点、决策节点和记录节点三类。
提案节点：称为Proposer，提出对某个值进行设置操作的节点，设置值（不一定是设置值，也可能是记录日志）这个行为就是提案（Proposal）。值一旦设置成功，就是不会丢失也不可变的。
决策节点：称为 Acceptor，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，就意味着这个提案被批准（Accept）。提案被批准，就意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受它。
记录节点：被称为 Learner，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案。比如，少数派节点从网络分区中恢复时，将会进入这种状态。
在使用Paxos算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上某一种或者多种角色
为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个，且在系统初始化时，网络中每个节点都知道整个网络所有决策节点的数量、地址等信息。
网络通讯是不可靠的，分布式环境下并发操作的共享数据问题，这两个是要重点解决的问题。
Paxos 算法包括“准备（Prepare）”和“批准（Accept）”两个阶段。
第一阶段准备就相当于抢占锁的过程。如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请（称为Prepare请求）。提案节点的 Prepare 请求中会附带一个全局唯一的数字 n 作为提案 ID，决策节点收到后，会给提案节点两个承诺和一个应答。其中，两个承诺是指：承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求；承诺不会再接受提案 ID 小于 n 的 Accept 请求。
一个应答是指：在不违背以前作出的承诺的前提下，回复已经批准过的提案中 ID 最大的那个提案所设定的值和提案 ID，如果该值从来没有被任何提案设定过，则返回空值。如果违反此前做出的承诺，也就是说收到的提案 ID 并不是决策节点收到过的最大的，那就可以直接不理会这个 Prepare 请求。
如果提案节点发现所有响应的决策节点此前都没有批准过这个值（即为空），就说明它是第一个设置值的节点，可以随意地决定要设定的值；并将自己选定的值与提案 ID，构成一个二元组 (id, value)，再次广播给全部的决策节点（称为 Accept 请求）。如果提案节点发现响应的决策节点中，已经有至少一个节点的应答中包含有值了，那它就不能够随意取值了，必须无条件地从应答中找出提案ID最大的那个值并接受，构成一个二元组(id,maxAcceptValue)，然后再次广播给全部的决策节点（称为Accept请求）。
当每一个决策节点收到 Accept 请求时，都会在不违背以前作出的承诺的前提下，接收并持久化当前提案 ID 和提案附带的值。如果违反此前做出的承诺，即收到的提案ID并不是决策节点收到过的最大的，那允许直接对此 Accept 请求不予理会。当提案节点收到了多数派决策节点的应答（称为Accepted应答）后，协商结束，共识决议形成，将形成的决议发送给所有记录节点进行学习。整个过程的时序图如下所示：