分布式算法-Paxos
最近工作中遇到了分布式相关的问题，由于我们业务场景的要求，需要我们实现强一致性并且目前采用了CAP协议，满足CP舍弃了A。下面就让我们一起学习一下这个大名鼎鼎的Paxos算法吧。
这个是分布式算法高频的面试考点哦。
一、简介
Paxos算法
是Leslie Lamport在1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。它是一组协议，用于在不可靠或易出错的处理器组成的网络中解决一致性问题。协商一致意见是一组与会者就一项结果达成一致意见的过程。
自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。
二、角色
Paxos算法一共存在三个角色分别为
proposers
，
acceptors
，和
learners
（允许身兼数职）。
-
proposers
提出提案，提案信息包括提案编号和提议的 value；
-
acceptor
收到提案后可以接受（accept）提案，若提案获得多数派（majority）的 acceptors 的接受，则称该提案被批准（chosen）；
-
learners
只能“学习”被批准的提案。划分角色后，就可以更精确的定义问题：
-
决议（value）只有在被 proposers 提出后才能被批准（未经批准的决议称为“提案（proposal）”）；
-
在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value；
-
learners 只能获得被批准（chosen）的 value。
三、Basic Paxos算法
Paxos算法分为两个阶段，具体如下：
3.1 Prepare-阶段一
-
a).Proposer 收到client请求或发现本地有未提交的值，选择一个提案编号N，然后想半数以上的Acceptor发送编号为N的Prepare请求。
-
b).Acceptor收到一个编号为N的Prepare请求，如果该轮Paxos
1.本节点已经有
已提交的
value记录，对比记录的编号和N，大于N则拒绝回应，或者返回该记录value及编号2.没有已提交记录，判断本地是否有编号N1，N1>N，则拒绝回响，否则讲N1改为N（如果没有N1,则记录N），并响应prepare
3.2 Accept-阶段二
-
a).如果Proposer收到半数以上Acceptor对其发出的编号N的prepare请求的响应，那么它就会发送一个针对[N，V]提案的Accept请求给半数以上的Acceptor。V就是收到响应中编号最大的value，如果响应中不包含任何value，那么V就是由Proposer自己决定。
-
b).如果Acceptor收到一个针对编号为N的提案的Accept请求，Acceptor对比本地的记录编号，如果小于等于N，则接受该值，并提交记录value，否则拒绝请求
Proposer如果收到大多数的Acceptor响应，则选定该value值，并同步给leaner，使未响应的Acceptor达成一致。
四、参考