第一次这么通俗易懂的讲Paxos算法

Paxos解决什么问题

大家对Paxos的看法基本是“晦涩难懂”,虽然论文和网上文章也很多,但总觉得“云山雾罩”,也不知道其具体原理以及到底能解决什么问题。

究其原因,一方面是很多Paxos的资料都是在通过形式化的证明去论证算法的正确性,自然艰深晦涩;另一方面,基于Paxos的成熟工程实践并不多。本章试图由浅入深,从问题出发,一点点地深入Paxos的世界。

一个基本的并发问题

先看一个基本的并发问题,如图116所示。假设有一个KV存储集群,三个客户端并发地向集群发送三个请求。请问,最后在get(X)的时候,X应该等于几?

http://static.cyblogs.com/Jietu20210228-000345.jpg

图116(K,V)集群多写答案是:X=1、X=3或X=5都是对的!但X=4是错的!因为从客户端角度来看,三个请求是并发的,但三个请求到达服务器的顺序是不确定的,所以最终三个结果都有可能。

这里有很关键的一点:把答案换一种说法,即如果最终集群的结果是X=1,那么当Client1发送X=1的时候,服务器返回X=1;当Client2发送X=3的时候,服务器返回X=1;当Client3发送X=5的时候,服务器返回X=1。相当于Client1的请求被接受了,Client2、Client3的请求被拒绝了。如果集群最终结果是X=3或者X=5,是同样的道理。而这正是Paxos协议的一个特点。

什么是“时序”

把问题进一步细化:假设KV集群有三台机器,机器之间互相通信,把自己的值传播给其他机器,三个客户端分别向三台机器发送三个请求,如图117所示。

http://static.cyblogs.com/Jietu20210228-000644.jpg

图117三台机器组成的(K,V)集群多写示意图假设每台机器都把收到的请求按日志存下来(包括客户端的请求和其他Node的请求)。当三个请求执行完毕后,三台机器的日志分别应该是什么顺序?

结论是:不管顺序如何,只要三台机器的日志顺序是一样的,结果就是正确的。如图118所示,总共有3的全排列,即6种情况,都是正确的。比如第1种情况,三台机器存储的日志顺序都是X=1、X=3、X=5,在最终集群里,X的值肯定等于5。其他情况类似。

http://static.cyblogs.com/Jietu20210228-000811.jpg

而下面的情况就是错误的:机器1的日志顺序是1、3、5,因此最终的值就是X=5;机器2是3、5、1,最终值是X=1;机器3的日志顺序是1、5、3,最终值是X=3。三台机器关于X的值不一致,如图109所示。

http://static.cyblogs.com/Jietu20210228-000852.jpg

通过这个简单的例子就能对“时序”有一个直观的了解:虽然三个客户端是并发的,没有先后顺序,但到了服务器的集群里必须保证三台机器的日志顺序是一样的,这就是所谓的“分布式一致性”。

Paxos解决什么

问题在例子中,Node1收到了X=1之后,复制给Node2和Node3;Node2收到X=3之后,复制给Node1和Node3;Node3收到X=5之后,复制给Node1和Node2。

客户端是并发的,三个Node之间的复制也是并发的,如何保证三个Node最终的日志顺序是一样的呢?也就是图118中6种正确情况中的1种。

比如Node1先收到客户端的X=1,之后收到Node3的X=5,最后收到Node2的X=3;Node2先收到客户端的X=3,之后收到Node1的X=1,最后收到Node3的X=5……

如何保证三个Node中存储的日志顺序一样呢?这正是接下来要讲的Paxos要解决的问题!

复制状态机

在上文谈到了复制日志的问题,每个Node存储日志序列,Node之间保证日志完全一样。可能有人会问:为何要存储日志,直接存储最终的数据不就行了吗?

可以把一个变量X或一个对象看成一个状态机。每一次写请求,就是一次导致状态机发生变化的事件,也就是日志。

以上文中最简单的一个变量X为例,假设只有一个Node,3个客户端发送了三个修改X的指令,最终X的状态就是6,如图1110所示。

http://static.cyblogs.com/Jietu20210228-001101.jpg

图1110状态机X示意图把变量X扩展成MySQL数据库,客户端发送各种DML操作,这些操作落盘成Binlog。然后Binlog被应用,生成各种数据库表格(状态机),如图1111所示。

http://static.cyblogs.com/Jietu20210228-001145.jpg

这里涉及一个非常重要的思想:要选择持久化变化的“事件流(也就是日志流)”,而不是选择持久化“数据本身”(也就是状态机)。为何要这么做呢?原因有很多,列举如下:

(1)日志只有一种操作,就是append。而数据或状态一直在变化,可以add、delete、update。把三种操作转换成了一种,对于持久化存储来说简单了很多!

(2)假如要做多机之间数据同步,如果直接同步状态,状态本身可能有一个很复杂的数据结构(比如关系数据库的关联表、树、图),并且状态也一直在变化,要保证多个机器数据一致,要做数据比对,就很麻烦;而如果同步日志,日志是一个一维的线性序列,要做数据比对,则非常容易!

总之,无论从持久化,还是数据同步角度来看,存储状态机的输入事件流(日志流),都比存储状态机本身更容易。

基于这种思路,可以把状态机扩展为复制状态机。状态机的原理是:一样的初始状态+一样的输入事件=一样的最终状态。因此,要保证多个Node的状态完全一致,只要保证多个Node的日志流是一样的即可!即使这个Node宕机,只需重启和重放日志流,就能恢复之前的状态,如图1012所示。

http://static.cyblogs.com/Jietu20210228-001253.jpg

因此,就回到了上文最后的问题:复制日志!复制日志=复制任何数据(复制任何状态机)。因为任何复杂的数据(状态机)都可以通过日志生成!

一个朴素而深刻的思想

Paxos的出现先经过了Basic Paxos的形式化证明,之后再有Multi Paxos,最后是应用场景。因为最开始没有先讲应用场景,所以直接看Basic Paxos的证明会很晦涩。本文将反过来,就以上文最后提出的问题为例,先介绍应用场景,再一步步倒推出PaxosMulti Paxos

当三个客户端并发地发送三个请求时,图118所示的6种可能的结果都是对的。因此,要找一种算法保证虽然每个客户端是并发地发送请求,但最终三个Node记录的日志的顺序是相同的,也就是图108所示的任取一种场景即可。

这里提出一个朴素而深刻的说法:全世界对数字1,2,3,4,5,……顺序的认知是一样的!所有人、所有机器,对这个的认知都是一样的!

当我说2的时候,全世界的人,都知道2排在1的后面、3的前面!2代表一个位置,这个位置一定在(1,3)之间。

把这个朴素的想法应用到计算机里面多个Node之间复制日志,会变成如下这样。当Node1收到X=1的请求时,假设要把它存放到日志中1号位置,存放前先询问另外两台机器1号位置是否已经存放了X=3或X=5;如果1号位置被占了,则询问2号位置……依此类推。如果1号位置没有被占,就把X=1存放到1号位置,同时告诉另外两个Node,把X=1存放到它们各自的1号位置!同样,Node2和Node3按此执行。

这里的关键思想是:虽然每个Node接收到的请求顺序不同,但它们对于日志中1号位置、2号位置、3号位置的认知是一样的,大家一起保证1号位置、2号位置、3号位置存储的数据一样!

在例子中可以看到,每个Node在存储日志之前先要问一下其他Node,之后再决定把这条日志写到哪个位置。这里有两个阶段:先问,再做决策,也就是Paxos2PC的原型!

把问题进一步拆解,不是复制三条日志,只复制一条。先确定三个Node的第1号日志,看有什么问题?

Node1询问后发现1号位置没有被占,因此它打算把X=1传播给Node2和Node3;同一时刻,Node2询问后发现1号位置也没有被占,因此它打算把X=3传播给Node1和Node3;同样,Node3也打算把X=5传播给Node1和Node2。

结果不就冲突了吗?会发现不要说多条日志,就算是只确定第1号位置的日志,都是个问题!

而BasicPaxos正是用来解决这个问题的。

首先,1号位置要么被Node1占领,大家都存放X=1;要么被Node2占领,大家都存放X=3;要么是被Node3占领,大家都存放X=5,少数服从多数!为了达到这个目的,BasicPaxos提出了一个方法,这个方法包括两点:

第1,Node1在填充1号位置的时候,发现1号位置的值被大多数确定了,比如是X=5(node3占领了1号位置,Node2跟从了Node3),则Node1就接受这个事实:1号位置不能用了,也得把自己的1号位置赋值成X=5。然后看2号位置能否把X=1存进去。同样地,如果2号也被占领了,就只能把它们的值拿过来填在自己的2号位置。只能再看3号位置是否可行……

第2,当发现1号位置没有被占,就锁定这个位置,不允许其他Node再占这个位置!除非它的权利更大。如果发现1号位置为空,在提交的时候发现1号位置被其他Node占了,就会提交失败,重试,尝试第二个位置,第三个位置……

所以,为了让1号位置日志一样,可能要重试好多次,每个节点都会不断重试2PC。这样不断重试2PC,直到最终各方达成一致的过程,就是Paxos协议执行的过程,也就是一个Paxosinstance,最终确定一个值。而MultiPaxos就是重复这个过程,确定一系列值,也就是日志中的每一条!

接下来将基于这种思想详细分析Paxos算法本身。

BasicPaxos算法

在前面的场景中提到三个Client并发地向三个Node发送三条写指令。对应到Paxos协议,就是每个Node同时充当了两个角色:Proposer和Acceptor。在实现过程中,一般这两个角色是在同一个进程里面的。

当Node1收到Client1发送的X=1的指令时,Node1就作为一个Proposer向所有的Acceptor(自己和其他两个Node)提议把X=1日志写到三个Node上面。

同理,当Node2收到Client2发送的X=3的指令,Node2就作为一个Proposer向所有的Acceptor提议;Node3同理。

下面详细阐述Paxos的算法细节。首先,每个Acceptor需要持久化三个变量(minProposalId,acceptProposalId,acceptValue)。在初始阶段:minProposalId=acceptProposalId=0,acceptValue=null。然后,算法有两个阶段:P1(Prepare阶段)和P2(Accept阶段)。

P1(Prepare阶段)

http://static.cyblogs.com/Jietu20210227-234242.jpg

Prepare阶段P1a:Proposer广播prepare(n),其中n是本机生成的一个自增ID,不需要全局有序,比如可以用时间戳+IP。P1b:Acceptor收到prepare(n),做如下决策:

1
2
3
4
5
if n > minProposalId,回复Yes
同时,minProposalId=n(持久化)
返回(acceptProposalId,acceptValue)
else
回复 No

P1c:Proposer如果收到半数以上的yes,则取acceptorProposalId最大的acceptValue作为v,进入第二个阶段,即开始广播accept(n,v)。如果acceptor返回的都是null,则取自己的值作为v,进入第二个阶段!否则,n自增,重复P1a。

P2(Accept阶段)

http://static.cyblogs.com/Jietu20210227-234722.jpg

P2a:Proposer广播accept(n,v)。这里的n就是P1阶段的n,v可能是自己的值,也可能是第1阶段的acceptValue。P2b:Acceptor收到accept(n,v),做如下决策:

1
2
3
4
5
6
if n > minProposalId,回复Yes。同时
minProposalId=acceptProposalId=n(持久化)
acceptValue=value
return minProposalId
else
回复 No

P2c:Proposer如果收到半数以上的yes,并且minProposalId=n,则算法结束。否则,n自增,重复P1a。

通过分析算法,会发现BasicPaxos有两个问题:

(1)Paxos是一个“不断循环”的2PC。在P1C或者P2C阶段,算法都可能失败,重新进行P1a。这就是通常所说的“活锁”问题,即可能陷入不断循环。

(2)每确定一个值,至少需要两次RTT(两个阶段,两个网络来回)+两次写盘,性能也是个问题。而接下来要讲的MultiPaxos就是要解决这两个问题。

MultiPaxos算法

问题1:活锁问题

在前面已经知道,BasicPaxos是一个不断循环的2PC。所以如果是多个客户端写多个机器,每个机器都是Proposer,会导致并发冲突很高,也就是每个节点都可能执行多次循环才能确定一条日志。极端情况是每个节点都在无限循环地执行2PC,也就是所谓的“活锁问题”。

为了减少并发冲突,可以变多写为单写,选出一个Leader,只让Leader充当Proposer。其他机器收到写请求,都把写请求转发给Leader;或者让客户端把写请求都发给Leader。

Leader的选举方法很多,下面列举两种:

方案1:无租约的Leader选举

Lamport在他的论文中给出了一个Leader选举的简单算法,算法如下:

(1)每个节点有一个编号,选取编号最大的节点为Leader;

(2)每个节点周期性地向其他节点发送心跳,假设周期为Tms;

(3)如果一个节点在最近的2Tms内还没有收到比自己编号更大的节点发来的心跳,则自己变为Leader;

(4)如果一个节点不是Leader,则收到请求之后转发给Leader。可以看出,这个算法很简单,但因为网络超时原因,很可能出现多个Leader,但这并不影响MultiPaxos协议的正确性,只是增大并发写冲突的概率。我们的算法并不需要强制保证,任意时刻只能有一个Leader。

方案2:有租约的Leader选举

另外一种方案是严格保证任意时刻只能有一个leader,也就是所谓的“租约”。租约的意思是在一个限定的期限内,某台机器一直是Leader。即使这个机器宕机,Leader也不能切换。必须等到租期到期之后,才能开始选举新的Leader。这种方式会带来短暂的不可用,但保证了任意时刻只会有一个Leader。具体实现方式可以参见PaxosLease。

问题2:性能问题

我们知道BasicPaxos是一个无限循环的2PC,一条日志的确认至少需要两个RTT+两次落盘(一次是Prepare的广播与回复,一次是Accept的广播与回复)。如果每条日志都要两个RTT+两次落盘,这个性能就很差了。而MultiPaxos在选出Leader之后,可以把2PC优化成1PC,也就只需要一个RTT+一次落盘了。

基本思路是当一个节点被确认为Leader之后,它先广播一次Prepare,一旦超过半数同意,之后对于收到的每条日志直接执行Accept操作。在这里,Perpare不再是对一条日志的控制了,而是相对于拿到了整个日志的控制权。一旦这个Leader拿到了整个日志的控制权,后面就直接略过Prepare,直接执行Accept。

如果有新的Leader出现怎么办呢?新的Leader肯定会先发起Prepare,导致minProposalId变大。这时旧的Leader的广播Accept肯定会失败,旧的Leader会自己转变成一个普通的Acceptor,新的Leader把旧的顶替掉了。

下面是具体的实现细节:在BasicPaxos中,2PC的具体参数形式如下:

1
2
prepare(n)
accept(n,v)

在MultiPaxos中,增加一个日志的index参数,即变成了如下形式:

1
2
prepare(n,index)
accept(n,v,index)
问题3:被choose的日志,状态如何同步给其他机器

对于一条日志,当Proposer(也就是Leader)接收到多数派对Accept请求的同意后,就知道这条日志被“choose”了,也就是被确认了,不能再更改!

但只有Proposer知道这条日志被确认了,其他的Acceptor并不知道这条日志被确认了。如何把这个信息传递给其他Accepotor呢?

方案1:Proposer主动通知

给accept再增加一个参数:

1
accept(n,v,index,firstUnchooseIndex)

Proposer在广播accept的时候,额外带来一个参数firstUnchosenIndex=7。意思是7之前的日志都已经“choose”了。Acceptor收到这种请求后,检查7之前的日志,如果发现7之前的日志符合以下条件:acceptedProposal[i]==request.proposal(也就是第一个参数n),就把该日志的状态置为choose。

解决方案2:Acceptor被动查询

当一个Acceptor被选为Leader后,对于所有未确认的日志,可以逐个再执行一遍Paxos,来判断该条日志被多数派确

认的值是多少。

因为BasicPaxos有一个核心特性:一旦一个值被确定后,无论再执行多少遍Paxos,该值都不会改变!因此,再执行1遍Paxos,相当于向集群发起了一次查询!

至此,MultiPaxos算法就介绍完了。回顾这个算法,有两个精髓:

精髓之1:一个强一致的“P2P网络”

任何一条日志,只有两种状态(choose,unchoose)。当然,还有一种状态就是applied,也就是被确认的日志被apply到状态机。这种状态跟Paxos协议关系不大。

choose状态就是这条日志,被多数派接受,不可更改;

unchoose就是还不确定,引用阿里OceanBase团队某工程师的话,就是“薛定谔的猫”,或者“最大commit原则”。一条unchoose的日志可能是已经被choose了,只是该节点还不知道;也可能是还没有被choose。要想确认,那就再执行一次Paxos,也就是所谓的“最大commit原则”。

整个MultiPaxos就是类似一个P2P网络,所有节点互相双向同步,对所有unchoose的日志进行不断确认的过程!在这个网络中可以出现多个Leader,可能出现多个Leader来回切换的情况,这都不影响算法的正确性!

精髓之2:“时序”

MultiPaxos保证了所有节点的日志顺序一模一样,但对于每个节点自身来说,可以认为它的日志并没有所谓的“顺序”。什么意思呢?

(1)假如一个客户端连续发送了两条日志a,b(a没有收到回复,就发出了b)。对于服务器来讲,存储顺序可能是a、b,也可能是b、a,还可能在a、b之间插入了其他客户端发来的日志!

(2)假如一个客户端连续发送了两条日志a、b(a收到回复之后,再发出的b)。对于服务器来讲,存储顺序可能是a、b;也可能是a、xxx、b(a与b之间插入了其他客户端的日志),但不会出现b在a的前面。

所以说,所谓的“时序”,只有在单个客户端串行地发送日志时,才有所谓的顺序。多个客户端并发地写,服务器又是并发地对每条日志执行Paxos,整体看起来就没有所谓的“顺序”。

参考地址

  • 文章摘自《软件架构设计》余春龙/著

如果大家喜欢我的文章,可以关注个人订阅号。欢迎随时留言、交流。如果想加入微信群的话一起讨论的话,请加管理员微信号:chengcheng222e,他会拉你们进群。

简栈文化服务订阅号