最近大家都在讨论Paxos算法。Paxos有一些了解，这里总结一下，希望对大家有所启发。为什么需要PaxosPaxos需要解决的问题是分布式系统中的一致性问题。那么究竟什么是“分布式系统中的一致性问题”呢？在分布式系统中，为了保证数据的高可用性，我们通常会保存数据的多个副本（replicas），这些副本会被放置在不同的物理机上。为了保持副本的一致性，所有副本的更新顺序必须一致。因为数据的增删改查操作一般会有多个客户端并发，哪个客户端先做哪个客户端后做，所以必须保证更新的顺序。如果不是分布式的，可以使用加锁的方式，谁先申请锁就先操作，但是这样有单点问题。Paxos协议主要有两个用途：用于实现全局锁服务或命名配置服务，如GoogleChubby和ApacheZooKeeper。使用它将用户数据复制到多个数据中心，例如GoogleMegastore和GoogleSpanner。以分布式KV数据库为例，假设数据库提供Put和Get两种操作，具体架构如下：在这样的架构下，多台服务器可以组成集群，避免单点问题。我们需要解决的是三台服务器必须保持同步，即如果向集群发送请求Put("a",1)成功，那么整个集群中的任何一台服务器都必须包含("a",1).另外，假设此时有多个客户端并发访问集群，不同客户端的请求可能会落在不同的Server机器上。比如同时存在Put("b",2)和Put("c",3)。我们需要保证哪个客户端请求先完成，哪个客户端请求后完成，保证更新的顺序。这就是Paxos算法需要解决的问题。要深入浅出地理解Paxos算法，我们先简单描述一下Paxos算法，对算法本身有一个直观的认识，然后再结合下面的例子来进一步理解。在Paxos算法中，主要有3个角色：Proposer：ProposerAcceptor：DecisionmakerLearner：当最终的决策学习器实现时，往往会用到一组固定数量的服务器，每个服务器同时扮演以上三个角色时间。Paxos算法分为以下三个阶段：在Prepare阶段，Proposer向大多数Acceptor发起Proposal(epochNo,value)的Prepare请求。当Acceptor收到Prepare请求时，如果epochNo小于之前收到的epochNo，则直接拒绝；如果epochNo大于之前收到的epochNo，它会将收到的epochNo***返回Proposal给Proposer。Proposer发起的Proposal至少要收到上述大部分Acceptor的Prepare响应才能进入下一个Accept阶段，否则需要重新发起Prepare阶段向大部分Acceptor发起Prepare请求。在Accept阶段，Proposer在收到大多数Acceptor的Prepare响应后，检查Acceptor是否已经接受了Proposal。如果没有被接受的Proposal，则提出Proposal并发起Accept请求；如果已经有acceptedProposal，则从中选择epochNo***的Proposal，并对该Proposal发起Accept请求。Acceptor收到请求后，若Proposal的epochNo大于其上次响应Prepare请求的epochNo，则接受请求；否则它拒绝请求。Learn阶段所有Acceptor接受的Proposal必须不断通知Learner，否则Learner会主动询问，一旦Learner确认Proposal被大多数Acceptor接受。那么就意味着这个Proposal的value被Chosen了，Learner可以学习到这个Proposal的Value，同时自己的server也不会再接受Proposor的请求。我喜欢通过例子来理解理论。理论来源于生活。下面我将结合生活中的例子来描述该算法。假设一群驴友决定春节去旅游。全国有10个驴友。为了达成一致，这10个人又找了5个人当组长。5个队长互不交流，只给10个驴友发短信。第一阶段（申请阶段），驴友给5位队长发短信申请与队长通讯，队长任何时候只能与一位驴友通讯。每条发送的短信都有时间，组长采用的原则是同意以短信发送时间最长的驴子进行交流。如果有更新的短信，与更新短信的朋友沟通。至少大部分舰长都同意沟通，这位驴友可以进入实质性沟通的第二阶段了。在第二阶段（交流阶段），获得交流权的驴友A收到队长发给他的旅行目的地。可能有以下几种情况：情况#1：所有沟通过的船长都还没有决定去哪里旅游，此时驴友A将自己想去的旅游目的地发给船长（比如马尔代夫）。这样一来，估计大部分舰长都同意了。整个过程完成后，就该去马尔代夫旅游了。其他旅行的朋友迟早会知道的。除此之外，它表示失败。可能组长没有回复（他给女朋友打电话），或者其他驴友接管了交流权。如果失败，A需要重新启动第一阶段申请，再次发短信给队长申请通讯权。第二种情况：至少有一个领队已经决定了旅行目的地。此时A会收到多个由不同领队决定的旅行目的地。这些旅行目的地是不同的领队和不同的驴友在不同的时间做出的决定。A会先检查一些旅游目的地是否得到大多数（超过半数）船长的认可。如果是（这里假设3个船长决定去三亚，一个去拉萨，一个可能因为某种原因没有回应），证明整个决策过程达成一致，A收拾行李去三亚，结束了！如果都没有达到一半（比如2个去三亚，1个去拉萨，1个去昆明，1个忽略），此时A可能想去马尔代夫，但是他没有t做他想做的（这里是Paxos的）关键是后者承认前者，否则整个过程没完没了）。A会根据机长收到的所有旅行目的地找到***的决策地点（比如去昆明的机长1分钟前决定的，去拉萨的机长半小时前决定的，去拉萨的机长半小时前决定的）去三亚是1小时前决定的），所以A决定去昆明。这个时候去昆明的决定又更新了，这样下一个抢到通讯权的驴子很有可能去昆明，所以越来越多的队长决定去昆明。一旦大多数（超过半数）的船长同意在某个时刻去某个地方，比如去昆明，随后获得通讯权的驴友B会发现，大部分船长都决定去去昆明，它会服从，最终所有游友都一致同意去昆明。Paxos的基本思想大致就是上面的过程。Paxos使用选举和少数服从多数的思想。只要N个（N为奇数，至少大于等于3）个节点中有[N/2]+1个（N/2向下取整）个或多个节点同意某个决策，则系统被认为已达成一致。在这种情况下，客户端不需要与所有服务器通信，而是可以选择与大部分服务器通信；不需要所有服务器都处于working状态，部分服务器挂掉，只保证一半以上存活，整个过程可以继续，容错性很好。Paxos中的Acceptor相当于上面的船长，Proposer相当于上面的驴友，epochNo号相当于例子中申请短信的发送时间。Paxos最耗时的部分是需要超过半数的参与方同意才能进入第二步进行通信。试想，一开始，所有的驴友都给队长发了短信，而每个队长最后收到的短信来自不同的驴友。这样一来，就很难达到一半以上的参与者都同意与某位驴友交流的状态。为了减少这个时间，Paxos还对FastPaxos等进行了改进。另外，Paxos并不是指一个协议，而是一类协议的总称。比较常见的Paxos协议包括：basicpaxos和multi-paxos。这里的例子是关于基本的paxos。基本的paxos协议比较复杂，效率也比较低。因此，凡是涉及到paxos相关协议的系统，一般都是基于multi-paxos来实现的。有兴趣的可以参考文章：https://zhuanlan.zhihu.com/p/25664121Paxos在数据库高可用中作为DBA使用。为了实现高可用，最常用的高可用方式是主从模式。以MySQL为例，主要有以下几种：强同步复制binlog同步到从库，从库返回主库ok后，才能返回客户端提交成功。这是一个问题。一旦主从网络出现波动，甚至从库宕机，主库将无法再提供服务。这种模式实现了数据的强一致性，但牺牲了服务的可用性。异步复制主库本地写入成功后，立即返回给客户端成功，无需等待从库的响应。这样，一旦主库宕机，可能会有少量日志没有同步到从库，造成部分数据丢失。这种模式可用性好，但是牺牲了数据的一致性。半同步复制的模式是一种折衷。主要是指至少有一个从库节点接收到日志并返回给主库ok。这时候就可以返回给客户端提交成功了。当网络环境不好时，可能会退化为异步复制。另外，主从模式还有一个绕不过去的问题，就是master的选择。对于主从模式，很早就诞生了很多高可用方案，比如MMM、MHA、中间层等等，但是显然理论和思想都不先进。综上所述，主从方式处理数据库的高可用存在很多缺陷。改进这种数据同步方式，可以梳理出数据库高可用的几个需求：数据不丢失、服务持续可用、自动选主、自动容错、使用Paxos协议的日志同步可以实现以上三点要求。当然，Paxos协议需要依赖一个基本假设。Master和Backup之间有过半数机器（N/2+1），网络通信正常。如果不满足这个条件，则无法启动服务，也无法读写数据。所以我们可以使用Paxos来复制redolog或者binlog来保证一个高可用和一致的集群。您无需担心主从切换。你只需要一个VIP，后台在后面的数据库中映射多个点。Paxos会自动保证多个点的写入一致。阿里云在业界使用Paxos或者raft做企业级三节点MySQL集群。平台事业部DBA蒲聪，2013年6月加入去哪儿，目前负责支付平台事业部MySQL数据库和HBase的整体运维工作。白手起家搭建了去哪儿的HBase运维系统。在Hbase数据库的架构、调优和故障排除方面具有丰富的经验。目前专注于分布式数据库领域的研究和实践工作。
