云计算核心算法(一)
云计算的基础技术是集群技术,支撑集群高效协同工作需要一系列资源和任务调度算法,良好的调度算法可以提高集群处理能力,有效分配资源,加速作业进度。
一、Paxos算法
Paxos算法解决的问题是一个分布式系统如何就某个value(决议)达成一致。Paxos算法作为分布式系统中最著名的算法之一,在目前所有的一致性算法中,该算法最常用而且被认为是最有效的。
(一)Paxos算法背景知识
在介绍Paxos算法之前,先介绍以下背景知识:
(1)processor可以担任三个角色“proposer”、“accepter”和“learner”中的一个或多个角色。
(2)proposal和value:proposal一般译为“提案”,value一般译为“决议”。
(3)proposer可以propose(提出)proposal;accepter可以accept(接受)proposal。
(4)各个processor之间信息的传递可以延迟、丢失,但是在这个算法中假设传达到的信息都是正确的。
(二)Paxos算法详解
Paxos算法的核心是,只要满足下面三个条件就能保证数据的一致性:
(1)一个value只有在被proposer 提出之后才可以被choose;
(2)每次只有一个value被choose;
(3)value只有被choose之后才能被learners所获取。
这三个条件其实很好理解,而这三个条件中最重要的就是条件2, Paxos算法也就是对条件2的不断加强。如何保证每次只有一个value被chosen呢?
首先,来看一个单点问题:只有一个proposer和一个accepter, proposer传递有一个proposal给accepter,accepter接受并执行。这种机制很简单也很容易实现。但是如果其中一个processor宕机或者重启导致没有接收到信息那么整个系统就瘫痪了。显然,这不是理想的系统。 当系统有多个processor时(分布式系统),一个proposer向一组acepter发送proposal,这些acepter可能接受这个proposal也可能不接受(例如proposal丢失)。现在来加强条件2:
①条件
2
②任意两个majority至少
含有一个公共accepter
}
③一个accepter只能接受一个value
\left. \begin{array}{l} ①条件2\\[2ex] ②任意两个\text{majority}至少\\ 含有一个公共\text{accepter} \end{array} \right\} ③一个\text{accepter}只能接受一个\text{value}
①条件2②任意两个majority至少含有一个公共accepter⎭
⎬
⎫③一个accepter只能接受一个value
这一步推导很简单,例如,有一个accepter集合,这个集合里有3个accepter,显然多数派至少含有两个accepter,如果有两个value则有两个多数派,而两个多数派至少有一个重合的accepter,也就是说这个accepter接受了两个不同value (议案)。这样有了3的限制则保证了只有一个value被chosen。
假设当分布式系统刚刚运行的时候只有一个proposer提出了一个proposal,如果所有的accepter都不接受这个proposal则系统不会运行,因此要求p1。
p1:每个accepter都必须接受它收到的第一个proposal。
注意,p1是不完备的,例如,由两个proposer和4个accepter组成的分布式系统中,如果两个proposer几乎同时提出了两个value不同的proposal,而这两个proposal分别被两个accepter接受了,这样就没有value被chosen,因为这个案例中的多数派至少由3个accepter组成。但是我们现在暂时搁置这个问题,在后面会进行讲解。
由于p1,显然,一个accepter可以接受多个proposal (由③可以知道这些proposal有着相同的value)。根据③,通过引入 proposal=[num, value],于是有了限制p2。
p2:如果一个value为v的proposal被choose,那么此后被choose的编号更大的proposal的value也必须是v。
然而,一个proposal要被choose必须被大多数accepter所接受,故得到了p2的加强版本p2a。
p2a:如果一个value为v的proposal被choose,那么此后被任意accepter接受的编号更大的proposal的value也必须是v。
到这里出现了一个矛盾,如果一个value为v1的proposal p1被choose了,随后又有一个proposer提出了一个value为v2的proposal p2,这个p2送达了accepter x,巧合的是之前所有送往x的proposal都丢失了,也就是说这个p2是送达x的第一个proposal,根据p1这个x必须接受p2,而根据p2a 则不能,因此对p2a再做一次加强。 因为一个proposal要被accepter所接受,它必须被proposer所提出,故得到了对p2a的加强版本p2b。
p2b:如果一个value为v的proposal被choose,那么此后被任意proposer提出的编号更大的proposal的value也必须是v。
这三个限制的关系是,p2b→p2a→p2,即p2b蕴含p2a,p2a蕴含p2。
到这里p1和p2b已经可以保证分布式中的一致性,然而,p2b虽然在逻辑上满足要求却很难在实际中实现,因为proposer提出的proposal是难以限制的。所以,编者对p2b又做了一次加强。
p2c:如果一个 proposal=(
n
n
n,v) “想要”被提出,那么存在一个多数派S,要么(a)S中没有accepter接受任何num<
n
n
n的proposal,要么(b)S中accepter所接受的proposal中编号最大的proposal的value是v。
从p2b到p2c是整个Paxos算法最难以理解的地方,维基百科和一些人的博客对此处的理解都不太一样,p2c是p2b的加强,即p2c→p2b。现在解释一下p2c的含义,如果 proposal(
n
n
n,v) 想要被提出,有两种情况:
(1)S中没有accepter接受num≤
n
n
n的proposal,也就是说proposal是第一个proposal。num==1的proposal的提出是不受到限制的。
(2)S中accepter所接受的proposal中编号最大的proposal的value是v,S中accepter接受了某个或者一些proposal,那么这些proposal的value已经被choose。前面说过p2c是p2b的加强,p2b要求一旦某个value被choose,则以后提出的proposal的value必须跟被choose的value一致。proposal想要被提出则它的value必须和编号最大的proposal value一致。为什么是编号最大的而不是编号为
n
n
n-1 (
n
n
n为当前接受的proposal的编号) 的呢?因为一个proposal被多数派S接受之后它后续的proposal有可能丢失。
为了满足p2c,一个proposer要想提出一个编号为
n
n
n的proposal,它必须知道accepter多数派中已经接受的或者将要接受的编号小于
n
n
n的最大的编号是多少。知道已经接受的proposal的编号是很简单的,但是预测就比较难实现了,Paxos通过让accepter承诺不再接受任何编号小于
n
n
n的proposal来控制。因此,proposer提出一个proposal需要经过以下两步:
(1)proposer选择一个编号
n
n
n并向一组accepter发送一个prepare请求 (包含所选择的编号
n
n
n),要求accepter返回promise,promise包含两个信息:①不再接受任何编号小于
n
n
n的proposal的承诺;②该accepter所接受的小于
n
n
n的最大编号的proposal,如果该accepter还未接受过任何proposal则不用返回这个信息。
(2)如果proposer接收到大多数的accepter所返回的promise,则该proposer可以提出编号为
n
n
n,value为promise所带回的proposal的value的proposal,如果promise没有带回有关的proposal则value可以为任意值。
proposer通过向一组 (不一定是发给它promise的那一组) accepter发送accept请求来发送一个已经被接受的proposal。以上是proposer提出proposal的算法,下面看看accepter接受proposal的算法。
p1a:当且仅当accepter没有对任何编号大于
n
n
n的prepare做出过promise时,它可以接受一个编号为
n
n
n的proposal。
显然,p1a蕴含p1。与proposer不同的是,即使是宕机或者重启accepter也必须“记住”它所接受的最大编号的proposal以及它所做出过回应的最大编号的prepare请求。而proposer只要保证不提出重复的proposal即可。
对一个proposal的提出和接受做一个系统的描述,这个过程分为请求和提出两个阶段。
1)请求阶段
(1)proposer选择一个编号n,并向accepter多数派发出一个prepare请求。
(2)如果accepter接受到的prepare所带有的编号n比它之前所做出过回应的prepare请求的编号都要高,则该accepter回应proposer一个promise。
2)提出阶段
(1)如果proposer收到了accepter多数派对它所发出的prepare请求所做的回应,则它发出带有proposal的accept请求,proposal = (num,value),value为回应所带回的proposal的value值。
(2)如果accepter接受到一个accept请求,如果该accepter之前没有对任何编号大于n的prepare请求做出过promise,则接受该proposal。
PR:prepare request(假设p1到a3的PR丢失)。a1和a2是第一次接受到prepare请求,所以返回promise(不带回proposal),此时p1收到了a1和a2的promise,但是根据提出阶段的proposer必须接受来自多数派的promise才可以提出accept 请求,因此不会出现先前例子中的情况。
(三)Paxos算法举例
在一个分布式数据库系统中,有5个节点S1、S2、S3、S4、S5,假设各节点的初始状态一致,则每个节点都执行相同的操作序列,那么它们最后能得到一个一致的状态。现在用Paxos算法保证每个节点都执行相同的操作序列。假设S1只传输sql命令 (proposer),剩下的都是数据库节点 (accepter)。
步骤一
S1选定编号1(假设第一个命令编号为1),向集合database={s2, s3, s4, s5}的一个多数派子集发送Prepare Request(PR)。
步骤二
如果通信顺利,所有的多数派都收到了PR。如果通信部分失败导致接受到PR的节点不构成多数派则S1重复步骤1(PR编号递增)。
步骤三
S1接收到多数派的Paromise,向集合database发出带有第一个SQL命令(这里的SQL命令就是之前的value)的Proposal,编号为1,因为Promise没有带回Proposal所以这里的SQL命令没有限制。
步骤四
如果通信顺利,所有的数据库节点都收到了S1所提出的proposal (编号为1),而它们之前并没有做过任何编号大于1的prepare,因此它们接收这个proposal,由此多数派形成,决议也就产生了。然后各个节点执行决议的内容也就是SQL命令,然后等待S1提出第二个SQL命令:如果通信部分失败,这种情况下,如果接受到proposal1的节点可以构成多数派则和通信顺利的情况下一样;反之则不然,由于构不成多数派则不能产生决议,所有的数据库节点都不执行SQL命令,从而保证了数据库内容的一致性。
步骤五
重复以上操作,注意Proposal、Prepare以及Promise的编号递增,以及Promise根据情况带回Proposal。
原文地址:https://blog.csdn.net/Morse_Chen/article/details/140592375
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!