Paxos的通俗理解及其在数据库高可用上的使用

蒲聪 2017-06-19 18:35:20

本文转自【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集群。 

活动预告