本文转自【Qunar技术沙龙】，经平台同意授权转载。

近期大家都在讨论Paxos算法，我看了很多网上的文章，总觉得有些晦涩难懂，经过一段时间研究，对Paxos有了一些理解，在这里总结一下，希望能抛砖引玉。

1、为什么需要Paxos

Paxos要解决的问题，是分布式系统中的一致性问题。那么，到底什么是“分布式系统中的一致性问题”呢？在分布式系统中，为了保证数据的高可用，通常我们会将数据保留多个副本(replica)，这些副本会放置在不同的物理的机器上。副本要保持一致，那么所有副本的更新序列就要保持一致。因为数据的增删改查操作一般都存在多个客户端并发操作，到底哪个客户端先做，哪个客户端后做，更新顺序要保证。如果不是分布式，那么可以通过加锁的方法，谁先申请到锁谁就先操作，但这就存在单点问题。

Paxos协议主要有两种用法：一种用法是用来实现全局的锁服务或者命名和配置服务，例如Google Chubby以及Apache ZooKeeper。另外一种用法是用它来将用户数据复制到多个数据中心，例如Google Megastore以及Google Spanner。以一个分布式的KV数据库为例，假设数据库对外提供2种操作Put和Get，具体架构如下：

在这样一个架构下，可以通过多台server组成集群来避免单点问题。我们需要解决的是3台server必须保持同步，也就是说，如果向集群发送请求Put(“a”,1)并成功，那么整个集群任意一台server必须含有("a",1)。另外，假设此时多个client并发访问集群，不同客户端的请求可能会落入到不同的server机器上，比如并发有Put("b”,2)和Put(“c”,3)，我们需要保证哪个客户端请求先做，哪个后做，保证更新顺序，这就是Paxos算法需要解决的问题。

2、Paxos算法

我们先来简单描述一下Paxos算法，对算法本身有一个直观的认识，然后再结合后面的例子来进一步理解。

在Paxos算法中，主要有3种角色：

• Proposer：提议者

• Acceptor：决策者

• Learner：最终决策学习者

实现的时候往往采用一组固定数目的Server，每个Server同时担任上述三个角色。

Paxos算法分为以下三个阶段：

1、Prepare阶段

（1）Proposer向大多数Acceptor发起Proposal(epochNo,value)的Prepare请求。

（2）Acceptor收到Prepare请求，如果epochNo比之前接收到的小，直接拒绝；如果epochNo比之前已经接收的大，就将已经接收到的epochNo最大的Proposal返回到Proposer。

（3）Proposer发起的Proposal至少要收到大多数以上的Acceptor的Prepare应答后，才能进入接下来的Accept阶段，否则需要重新进行Prepare阶段向大多数Acceptor发起Prepare请求。

2、Accept阶段：

（1）Proposer收到大多数的Acceptor的Prepare应答后，看Acceptor是否已经有被接受的Proposal。如果没有已经接受的Proposal，就自己提出一个Proposal，发起Accept请求；如果已经有被接受的Proposal，就从中选出epochNo最大的Proposal，发起对该Proposal的Accept请求。

（2）Acceptor收到请求后，如果该Proposal的epochNo比它最后一次应答Prepare请求的epochNo要大，那么就接受该请求；否则拒绝该请求。

3、Learn阶段：

所有Acceptor接受的Proposal要不断通知Learner，或者Learner主动去查询，一旦Learner确认Proposal被大多数的Acceptor接受，那么表示这个Proposal的Value被Chosen，Learner就可以学习这个Proposal的Value，同时自己的Sever上就不再受理Proposor的请求。

我喜欢通过例子来理解理论，理论源于生活，下面我以生活中的例子来进行该算法的描述。（该例借鉴自《分布式理论之一：Paxos算法的通俗解释》，链接 http://www.mamicode.com/info-detail-198650.html）

假设一群驴友决定端午去旅游，驴友遍布全国各地，一共10人，为了能达成一致，这10个人另外找5个作为队长。5个队长之间相互不通信，只跟10个驴友发短信。

第一阶段（申请阶段），驴友发短信给5个队长，申请与队长进行沟通。队长在任何时刻只能与一个驴友沟通。发送的每条短信都带有时间，队长采用的原则是同意与短信发送时间最新的驴友沟通，如果出现更新的短信，则与短信更新的驴友沟通。至少大多数队长同意沟通了，这个驴友才能进入第二阶段实质性沟通。

第二阶段（沟通阶段），获得沟通权的驴友A收到队长们给他发的旅游地，可能有几种情况。

第一种情况：沟通的队长们全部都还没有决定到底去哪里旅游，此刻驴友A会把自己想去的旅游地发给队长们（比如马尔代夫），结果可能大多数队长同意了，整个过程执行完毕，就是去马尔代夫旅游了，其他的驴友迟早会知道。除此之外就表明失败了，可能队长没有回复(跟女友打电话去了)，可能被其他驴友抢占沟通权了（上面说过队长只跟最新的短信的人进行沟通）。如果失败了，A需要重新开始第一阶段申请，重新给队长们发短信申请沟通权。

第二种情况：至少有一个队长已经决定旅游地了，这个时候A会收到不同队长决定的多个旅游地，这些旅游地是不同队长跟不同驴友在不同时间做的决定。A会先看看有的旅游地是不是被大多数（半数以上）队长同意了，如果有(这里假设3个队长决定去三亚，一个去拉萨，另外可能某种原因没搭理），那证明整个决定过程已经达成一致了，A收拾收拾去三亚吧，结束！

如果都没有达到半数（比如2个去三亚，1个去拉萨，1个去昆明，1个没搭理），这时候A可能想去马尔代夫，但也不按照自己意愿乱来了（这里是Paxos的关键所在，后者认可前者，否则整个过程无止境了），A会根据收到队长的所有旅游地中找到最新的那个决定地（比如去昆明是那个队长是1分钟前决定的，去拉萨的队长是半小时前决定的，去三亚的队长是1小时前决定的），于是A顶最新的决定，去昆明。这时候去昆明的决定又更新了，这样下一个抢到沟通权的驴友也很大可能会顶去昆明，这样决定去昆明的队长会越来越多。

一旦某个时刻大多数（半数以上）队长都同意了去某个地点，比如去昆明，后续获得沟通权的驴友B会发现大多数队长都决定去昆明了，它也会服从，最终所有的驴友都达成一致去昆明。

Paxos的基本思想大致就是上面过程，Paxos利用的是选举，少数服从多数的思想，只要N个(N为奇数，至少大于等于3)节点中，有[N/2]+1(这里N/2为向下取整)或以上个节点同意了某个决定，则认为系统达到了一致，这样的话，客户端不必与所有服务器通信，选择与大部分通信即可；也无需服务器都全部处于工作状态，有一些服务器挂掉，只有保证半数以上存活着，整个过程也能持续下去，容错性相当好。

Paxos中的Acceptor相当于上面的队长，Proposer相当于上面的驴友，epochNo号就相当于例子中申请短信的发送时间。Paxos最消耗时间的地方就在于需要半数以上同意沟通了才能进入第二步，试想一下，一开始，所有驴友就给队长狂发短信，每个队长收到的最新短信的是不同驴友，这样，就难以达到半数以上都同意与某个驴友沟通的状态，为了减小这个时间，Paxos还有Fast Paxos的改进等等，这里不再细说。另外，Paxos并不指代一个协议，而是一类协议的统称，比较常见的Paxos类协议有：basic paxos和multi-paxos，这里的例子说的是basic paxos，basic paxos协议较复杂，且相对效率较低，所以现在所有和Paxos有关的协议的系统，一般都是基于multi-paxos来实现的，有兴趣了解可以参考文章https://zhuanlan.zhihu.com/p/25664121

3、Paxos在数据库高可用上的使用

作为DBA，为了实现高可用，最常用的高可用方式是主从模式，以MySQL为例，主要有几种：

（1）强同步复制，binlog同步到从库之后，从库返回给主库ok之后才能返回给客户端提交成功，这就有个问题，一旦主从之间网络出现抖动，甚至从库宕机，则主库就无法再继续提供服务，这种模式实现了数据的强一致，但是牺牲了服务的可用性。

（2）异步复制，主库写本地成功后，立刻返回给客户端说成功，无需等待从库应答，这样一旦主库宕机，可能会有少量的日志没有同步到从库造成部分数据丢失，这种模式可用性很好，但是牺牲了数据的一致性。

（3）半同步复制，这种模式是一个折中，主要指至少有一个从库节点收到日志返回给主库ok之后，这是就可以返回给客户端提交成功，当网络环境不好的时候可能退化为异步复制。

另外主从模式还有一个无法绕过的问题，就是选主，为了主从模式的选主，长期以来也诞生了很多种高可用方案，MMM、MHA、中间层等等，但显然理论和思路都不是最先进的。

总结一下，针对主从方式处理数据库高可用有诸多缺陷，要想改进这种数据同步方式，可以梳理数据库高可用的几点需求：

• 数据不丢失

• 服务持续可用性

• 自动选主

• 自动容错

使用Paxos协议的日志同步就可以实现以上的三个需求，当然Paxos协议需要依赖一个基本假设，主备之间有多数派机器(N/2+1)是存活且它们之间的网络通讯正常，如果不满足这个条件，则无法启动服务，数据也无法写入和读取。

所以我们可以使用Paxos进行redolog或者binlog的复制，从而保证高可用强一致的集群，主从的切换也不需要担心，只需要有个vip，后端映射后面数据库的多点就行，Paxos会自动保证多点的一致性写入，业界阿里云使用Paxos或者Raft来做的企业三节点的MySQL集群。