Paxos是什么
Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。
问题产生的背景
在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。
相关概念
在Paxos算法中，有三种角色：
- Proposer
- Acceptor
- Learners
在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。
提案（Proposal）
最终要达成一致的value就在提案里。
注： - 暂且认为『提案=value』，即提案只包含value。在我们接下来的推导过程中会发现如果提案只包含value，会有问题，于是我们再对提案重新设计。
Proposer可以提出（propose）提案；Acceptor可以接受（accept）提案；如果某个提案被选定（chosen），那么该提案里的value就被选定了。
回到刚刚说的『对某个数据的值达成一致』，指的是Proposer、Acceptor、Learner都认为同一个value被选定（chosen）。那么，Proposer、Acceptor、Learner分别在什么情况下才能认为某个value被选定呢？
Proposer：只要Proposer发的提案被Acceptor接受（刚开始先认为只需要一个Acceptor接受即可，在推导过程中会发现需要半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。Acceptor：只要Acceptor接受了某个提案，Acceptor就任务该提案里的value被选定了。Learner：Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。
- Proposer：只要Proposer发的提案被Acceptor接受（刚开始先认为只需要一个Acceptor接受即可，在推导过程中会发现需要半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。
- Acceptor：只要Acceptor接受了某个提案，Acceptor就任务该提案里的value被选定了。
- Learner：Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。
问题描述
假设有一组可以提出（propose）value（value在提案Proposal里）的进程集合。
- 一个一致性算法需要保证提出的这么多value中，只有一个value被选定（chosen）。
- 如果没有value被提出，就不应该有value被选定。
- 如果一个value被选定，那么所有进程都应该能学习（learn）到这个被选定的value。
对于一致性算法，安全性（safaty）要求如下：
- 只有被提出的value才能被选定。
- 只有一个value被选定，并且
- 如果某个进程认为某个value被选定了，那么这个value必须是真的被选定的那个。
Paxos的目标：提出多个value，保证最终有一个value会被选定，当value被选定后，进程最终也能获取到被选定的value。
假设不同角色之间可以通过发送消息来进行通信，那么：
- 每个角色以任意的速度执行，可能因出错而停止，也可能会重启。一个value被选定后，所有的角色可能失败然后重启，除非那些失败后重启的角色能记录某些信息，否则等他们重启后无法确定被选定的值。
- 消息在传递过程中可能出现任意时长的延迟，可能会重复，也可能丢失。但是消息不会被损坏，即消息内容不会被篡改（拜占庭将军问题）
推导过程
最简单的方案——只有一个Acceptor
假设只有一个Acceptor（可以有多个Proposer），只要Acceptor接受它收到的第一个提案，则该提案被选定，该提案里的value就是被选定的value。这样就保证只有一个value会被选定。
但是，如果这个唯一的Acceptor宕机了，那么整个系统就无法工作了！
因此，必须要有多个Acceptor！
多个Acceptor
多个Acceptor的情况如下图。那么，如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢？
下面开始寻找解决方案。
如果我们希望即使只有一个Proposer提出了一个value，该value也最终被选定。
那么，就得到下面的约束：
P1：一个Acceptor必须接受它收到的第一个提案。
但是，这又会引出另一个问题：如果每个Proposer分别提出不同的value，发给不同的Acceptor。
根据P1，Acceptor分别接受自己收到的value，就导致不同的value被选定。出现了不一致。如下图：
刚刚是因为『一个提案只要被一个Acceptor接受，则该提案的value就被选定了』才导致了出现上面不一致的问题。因此，我们需要加一个规定：
规定：一个提案被选定需要被半数以上的Acceptor接受
这个规定又暗示了：『一个Acceptor必须能够接受不止一个提案！』不然可能导致最终没有value被选定。比如上图的情况。v1、v2、v3都没有被选定，因为它们都只被一个Acceptor的接受。
最开始讲的『提案=value』已经不能满足需求了，于是重新设计提案，给每个提案加上一个提案编号，表示提案被提出的顺序。令『提案=提案编号+value』。
虽然允许多个提案被选定，但必须保证所有被选定的提案都具有相同的value值。否则又会出现不一致。
于是有了下面的约束：
P2：如果某个value为v的提案被选定了，那么每个编号更高的被选定提案的value必须也是v。
一个提案只有被Acceptor接受才可能被选定，因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。
P2a：如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v。
只要满足了P2a，就能满足P2。
但是，考虑如下的情况：假设总共有5个Acceptor。Proposer2提出[M1,V1]的提案，Acceptor25（半数以上）均接受了该提案，于是对于Acceptor25和Proposer2来讲，它们都认为V1被选定。Acceptor1刚刚从宕机状态恢复过来（之前Acceptor1没有收到过任何提案），此时Proposer1向Acceptor1发送了[M2,V2]的提案（V2≠V1且M2>M1），对于Acceptor1来讲，这是它收到的第一个提案。根据P1（一个Acceptor必须接受它收到的第一个提案。）,Acceptor1必须接受该提案！同时Acceptor1认为V2被选定。这就出现了两个问题：
- Acceptor1认为V2被选定，Acceptor2~5和Proposer2认为V1被选定。出现了不一致。
- V1被选定了，但是编号更高的被Acceptor1接受的提案[M2,V2]的value为V2，且V2≠V1。这就跟P2a（如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v）矛盾。
所以我们要对P2a约束进行强化！
P2a是对Acceptor接受的提案约束，但其实提案是Proposer提出来的，所以我们可以对Proposer提出的提案进行约束。得到P2b：
P2b：如果某个value为v的提案被选定了，那么之后任何Proposer提出的编号更高的提案的value必须也是v。
由P2b可以推出P2a进而推出P2。
那么，如何确保在某个value为v的提案被选定后，Proposer提出的编号更高的提案的value都是v呢？
只要满足P2c即可(Proposer的提出，用Acceptor集合做了约束)：
对于任意的N和V，如果提案[N, V]被提出，那么存在一个半数以上的Acceptor组成的集合S，满足以下两个条件中的任意一个：
- S中每个Acceptor都没有接受过编号小于N的提案。
- S中Acceptor接受过的最大编号的提案的value为V。
Proposer生成提案
为了满足P2b，这里有个比较重要的思想：
- Proposer生成提案之前，应该先去『学习』已经被选定或者可能被选定的value，然后以该value作为自己提出的提案的value。
- 如果没有value被选定，Proposer才可以自己决定value的值。这样才能达成一致。
这个学习的阶段是通过一个『Prepare请求』实现的。
提案生成算法：
Proposer选择一个新的提案编号N，然后向某个Acceptor集合（半数以上）发送请求，要求该集合中的每个Acceptor做出如下响应（response）。
(a) 向Proposer承诺保证不再接受任何编号小于N的提案。
(b) 如果Acceptor已经接受过提案，那么就向Proposer响应已经接受过的编号小于N的最大编号的提案。
我们将该请求称为编号为N的Prepare请求。
- 如果Proposer收到了半数以上的Acceptor的响应，那么它就可以生成编号为N，Value为V的提案[N,V]。这里的V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案，那 么此时V就可以由Proposer自己选择。
- 生成提案后，Proposer将该提案发送给半数以上的Acceptor集合，并期望这些Acceptor能接受该提案。我们称该请求为Accept请求。（注意：此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合）
Acceptor接受提案
Acceptor可以忽略任何请求（包括Prepare请求和Accept请求）而不用担心破坏算法的安全性。因此，我们这里要讨论的是什么时候Acceptor可以响应一个请求。
我们对Acceptor接受提案给出如下约束：
P1a：一个Acceptor只要尚未响应过任何编号大于N的Prepare请求，那么他就可以接受这个编号为N的提案。
*如果Acceptor收到一个编号为N的Prepare请求，在此之前它已经响应过编号大于N的Prepare请求。根据P1a，该Acceptor不可能接受编号为N的提案。因此，该Acceptor可以忽略编号为N的Prepare请求。当然，也可以回复一个error，让Proposer尽早知道自己的提案不会被接受。
因此，一个Acceptor只需记住：1. 已接受的编号最大的提案 2. 已响应的请求的最大编号。
Paxos算法描述
经过上面的推导，我们总结下Paxos算法的流程。
阶段一：Prepare请求，proposer生成提议
(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
(b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。阶段二：Accept请求，产生一致采纳提议
(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。
中文版：
Learner学习被选定的value
Learner学习被选定的value
Learner学习（获取）被选定的value有如下三种方案：
如何保证Paxos算法的活性
通过选取主Proposer，就可以保证Paxos算法的活性。至此，我们得到一个既能保证安全性，又能保证活性的分布式一致性算法——Paxos算法。
Q&A
Paxos协议数据同步方式相对于基于传统1主N备的同步方式有啥区别？
一般情况下，传统数据库的高可用都是基于主备来实现，1主1备2个副本，主库crash后，通过HA工具来进行切换，提升备库为主库。在强一致场景下，复制可以开启强同步，Oracle和Mysql都是类似的复制模式。但是如果备库网络抖动，或者crash，都会导致日志同步失败，服务不可用。为此，可以引入1主N备的多副本形式，我们对比都是3副本的情况，一个是基于传统的1主2备，另一种基于paxos的1主2备。传统的1主两备，进行日志同步时，只要有一个副本接收到日志并就持久化成功，就可以返回，在一定程度上解决了网络抖动和备库crash问题。但如果主库出问题后，还是要借助于HA工具来进行切换，那么HA切换工具的可用性如何来保证又成为一个问题。基于Paxos的多副本同步其实是在1主N备的基础上引入了一致性协议，这样整个系统的可用性完全有3个副本控制，不需要额外的HA工具。而实际上，很多系统为了保证多节点HA工具获取主备信息的一致性，采用了zookeeper等第三方接口来实现分布式锁，其实本质也是基于Paxos来实现的。
以MySQL的主备复制一套体系为例来具体说明传统的主备保持强一致性的一些问题。整个系统中主要包含以下几种角色：Master，Slave，Zookeeper-Service(zk)，HA-Console(HA)，Zookeeper-Agent(Agent)
Master,Slave:分别表示主节点和备节点,主节点提供读写服务，备节点可以提供读服务，或者完全用于容灾。
Zookeeper-Service(zk):分布式一致性服务，负责管理Master/Slave节点的存活信息和切换信息。zk基于zab协议，zab协议是一种一致性协议，与paxos，raft协议类似，它主要有两种模式，包括恢复模式(选主)和广播模式(同步)。一般zk包含N个节点(zk-node)，只要有超过半数的zk-node存活且相互连通，则zk可以对外提供一致性服务。
HA-Console:切换工具，负责具体的切换流程
Zookeeper-Agent(Agent):Master/Slave实例上的监听进程，与监听的实例保持心跳，维护
Master/Slave的状态，每个实例有一个对应的Agent。大概工作流程如下：
- (1).Master/Slave正常启动并搭建好了复制关系，对应的Agent会调用zk接口去注册alive节点信息，假设分别为A和B。
- (2).如果此时Master Crash，则实例对应的Agent发现心跳失败，如果重试几次后仍然失败，则将调用zk接口注销掉A节点信息。
- (3).HA工具通过zk接口比较两次的节点信息，发现少了A节点，表示A可能不存在了，需要切换，尝试连接A，如果仍然不通，注册A的dead节点，并开始切换流程。
- (4).HA工具读取配置信息，找到对应的Slave节点B，(更改读写比配置信息，设置B提供写)，打开写。
- (5).应用程序通过拉取最新的配置信息，得知新主B，新的写入会写入B。
前面几部基本介绍了MySQL借助zk实现高可用的流程，由于zk-node可以多地部署，HA无状态，因此可以很容易实现同城或者是异地的高可用系统，并且动态可扩展，一个HA节点可以同时管理多个Master/Slave的切换。那么能保证一致性吗？前面提到的Agent除了做监听，还有一个作用是尽可能保持主备一致，并且不丢数据。 - (6).假设此时A节点重启，Agent检测到，通过zk接口发现A节点在dead目录下，表示被切换过，需要kill上面的所有连接，并回滚crash时A比B多的binlog，为了尽可能的少丢数据，然后再开启binlog后，将这部分数据重做。这里要注意rollback和replay都在old-Master上面进行，rollback时需要关闭binlog，而replay需要开启binlog，保证这部分数据能流向new-Master。
- (7).从第6步来看，可以一定程度上保证主备一致性，但是进行rollback和replay时，实际上是往new-Slave上写数据，这一定程度上造成了双写，如果此时new—Master也在写同一条记录，可能会导致写覆盖等问题。
- (8).如果开启半同步呢？old-Master crash时，仍然可能比old-Slave多一个group的binlog，所以仍然需要借助于rollback和replay，依然避免不了双写，所以也不能做到严格意义上的强一致。
分布式事务与Paxos协议的关系？
Paxos协议与分布式事务并不是同一层面的东西。
分布式事务的作用是保证跨节点事务的原子性，涉及事务的节点要么都提交(执行成功)，要么都不提交(回滚)。
分布式事务的一致性通常通过2PC来保证(Two-Phase Commit, 2PC)，这里面涉及到一个协调者和若干个参与者。
第一阶段，协调者询问参与者事务是否可以执行，参与者回复同意(本地执行成功)，回复取消(本地执行失败)。
第二阶段，协调者根据第一阶段的投票结果进行决策，当且仅当所有的参与者同意提交事务时才能提交，否则回滚。
2PC的最大问题是，协调者是单点(需要有一个备用节点)，另外协议是阻塞协议，任何一个参与者故障，都需要等待(可以通过加入超时机制)。
Paxos协议用于解决多个副本之间的一致性问题。比如日志同步，保证各个节点的日志一致性，或者选主(主故障情况下)，保证投票达成一致，选主的唯一性。
简而言之，2PC用于保证多个数据分片上事务的原子性，Paxos协议用于保证同一个数据分片在多个副本的一致性，所以两者可以是互补的关系，绝不是替代关系。对于2PC协调者单点问题，可以利用Paxos协议解决，当协调者出问题时，选一个新的协调者继续提供服务。工程实践中，Google Spanner，Google Chubby就是利用Paxos来实现多副本日志同步。
如何将Paxos应用于传统的数据库复制协议中？
复制协议相当于是对Paxos的定制应用，通过对一系列日志进行投票确认达成多数派，就相当于日志已经在多数派持久化成功。副本通过应用已经持久化的日志，实现与Master节点同步。由于数据库ACID特性，本质是由一个一致的状态到另外一个一致的状态，每次事务操作都是对应数据库状态的变更，并生成一条日志。由于client操作有先后顺序，因此需要保证日志的先后的顺序，在任何副本中，不仅仅要保证所有日志都持久化了，而且要保证顺序。对于每条日志，通过一个logID标示，logID严格递增(标示顺序)，由leader对每个日志进行投票达成多数派，如果中途发生了leader切换，对于新leader中logID的“空洞”，需要重新投票，确认日志的有效性。
Multi-Paxos的非leader节点可以提供服务吗？
Multi-Paxos协议中只有leader确保包含了所有已经已经持久化的日志，当然本地已经持久化的日志不一定达成了多数派，因此对于没有confirm的日志，需要再进行一次投票，然后将最新的结果返回给client。而非leader节点不一定有所有最新的数据，需要通过leader确认，所以一般工程实现中，所有的读写服务都由leader提供。
Ref：
http://www.cnblogs.com/RedHandLM/p/6780698.html?utm_source=itdadao&utm_medium=referral
来自《从Paxos到Zookeeper分布式一致性原理与实践》
http://www.cnblogs.com/cchust/p/5617989.html
