聊聊分布式一致性算法协议 Paxos
共 6062字,需浏览 13分钟
·
2022-06-12 05:29
Google的粗粒度锁服务Chubby的设计开发者Burrows曾经说过:所有一致性协议本质上要么是Paxos要么是其变体。
Paxos是什么?
难以理解 在工程是实现上比较复杂。
问题产生的背景
“ 这里某个数据的值并不只是狭义上的某个数,它可以是一条日志,也可以是一条命令(command)。根据应用场景不同,某个数据的值有不同的含义。
”
相关概念
Proposer (提案者) Acceptor (人大代表) Learners (广大群众)
初次认识
回到刚刚说的『对某个数据的值达成一致』,指的是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被选定。
问题描述
只有被提出的value才能被选定。 只有一个value被选定。 如果某个进程认为某个value被选定了,那么这个value必须是真的被选定的那个。
“ Paxos的目标:保证最终有一个value会被选定,当value被选定后,进程最终也能获取到被选定的value。 ”
每个角色以各自任意的速度进行通信执行,在这个过程中可能会因为各种原因出错而导致执行停止或重启。当一个value被选定之后,因为故障原因才恢复正常的角色因为失去了某些重要的信息,导致它们无法确定被选定的值。
消息在传递过程中可能出现任意时长的延迟,可能会重复,也可能丢失。但是消息不会被损坏,即消息内容不会被篡改(拜占庭将军问题)。
推导过程
最简单的方案——只有一个Acceptor
多个Acceptor
“ P1:一个Acceptor必须接受它收到的第一个提案。
”
但是,这样又会出现其它的问题:如果每个Proposer所提出的提案value是不同的,并且将提案发送给不同的Acceptor。根据P1约束,每个Acceptor都接受它收到的第一个提案,就会出现不同value被选定的情况,出现了不一致。
刚刚是因为『一个提案只要被一个Acceptor接受,则该提案的value就被选定了』才导致了出现上面不一致的问题。因此,我们需要加一个规定:
“ 规定:一个提案被选定需要被半数以上的Acceptor接受 ”
“ P2:如果某个value为v的提案被选定了,那么每个编号更高的被选定提案的value必须也是v。
”
一个提案只有被Acceptor接受才可能被选定,因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。
“ P2a:如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v。
”
人大代表1认为V2被选定,人大代表2-5和人民法院认为V1被选定。出现了不一致。 V1被选定了,但是编号更高的被人大代表1接受的提案[M2,V2]的value为V2,且V2≠V1。这就跟P2a(如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v)矛盾了。
所以,我们要对P2a约束进行加强!
P2a是对Acceptor接受的提案约束,但其实提案是Proposer提出来的,所有我们可以对Proposer提出的提案进行约束。得到P2b:
“ P2b:如果某个value为v的提案被选定了,那么之后任何Proposer提出的编号更高的提案的value必须也是v。
”
“ P2c:对于任意的N和V,如果提案[N, V]被提出,那么存在一个半数以上的Acceptor组成的集合S,满足以下两个条件中的任意一个:
S中每个Acceptor都没有接受过编号小于N的提案。
S中Acceptor接受过的最大编号的提案的value为V。
”
Proposer生成提案
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算法描述
Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求。
如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话) 作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案。
如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor(和之前的Acceptor不一定相同)。注意:V就是收到的响应中编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定。
如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案。
Learner学习被选定的value
Learner学习(获取)被选定的value有如下三种方案:
方案一
Acceptor接受到一个提案,就将该提案发送给所有Learners.
优点:Learner能够快速获取被选定的value
缺点:通信次数为M*N(M为提案数,N为Learner数)
方案二
Acceptor接受一个提案,就将提案发送给主Learner,主Learner再通知其它Learner
优点:通信次数减少(M+N-1)(M为提案数,N为Learner数,M个提案发送给主Learner,然后主Learner通知N-1个Learner)
缺点:单点故障问题(主Learner可能出现故障)
方案三
Acceptor接受一个提案,就将提案发送给Learner团,Learner团再通知其它Learner
优点:解决了方案二单点故障问题,可靠性好
缺点:实现复杂,网络通信复杂度高
如何保证Paxos算法的活性
通过选取主Proposer,就可以保证Paxos算法的活性。通过选取主Proposer,并规定只有主Proposer才能提出议案。这样一来只要主Proposer和过半的Acceptor能够正常进行网络通信,那么但凡主Proposer提出一个编号更高的提案,该提案终将会被批准,这样通过选择一个主Proposer,整套Paxos算法就能够保持活性。至此,我们得到一个既能保证安全性,又能保证活性的分布式一致性算法——Paxos算法。
总结
到此,我们针对Paxos算法是什么、它的特性以及算法的具体推导过程做了详细的阐述。Paxos算法是现在很多一致性算法的变体,非常值得我们学习~
来源:码哥字节
(版权归原作者所有,侵删)