《云计算（第三版）》配套ppt之34：第10章云计算核心算法（一）

《《云计算（第三版）》配套ppt之34：第10章云计算核心算法（一）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1云计算的基础技术是集群技术，支撑集群高效协同工作需要一系列资源和任务调度算法，良好的调度算法可以提高集群处理能力，有效分配资源，加速作业进度。三种核心算法Paxos算法DHT算法Gossip协议解决分布式系统中信息一致性问题解决分布式网络的应用层选路问题解决分布式环境下信息高效分发问题10.1Paxos算法10.2DHT算法10.3Gossip协议Paxos算法解决的问题是一个分布式系统如何就某个value（决议）达成一致。Paxos算法作为分布式系统中最著名的算法之一，在目前所有的一致性算法中，该算法最常用而且被认为是最有效的。10.1Paxos算法10.

2、1.1Paxos算法背景知识10.1.2Paxos算法详解10.1.3Paxos算法举例510.1Paxos算法Paxos算法背景知识processor可以担任三个角色“proposer”、“accepter”和“learner”中的一个或多个角色。proposal和value：proposal一般译为“提案”，value一般译为“决议”。proposer可以propose（提出）proposal；accepter可以accept（接受）proposal各个processor之间信息的传递可以延迟、丢失，但是在这个算法中假设传达到的信息都是正确的123410.

3、1Paxos算法10.1.1Paxos算法背景知识10.1.2Paxos算法详解10.1.3Paxos算法举例710.1Paxos算法Paxos算法详解Paxos算法的核心是，只要满足下面三个条件就能保证数据的一致性：1一个value只有在被proposer提出之后才可以被choose；2每次只有一个value被choose；3value只有被choose之后才能被learners所获取。810.1Paxos算法Paxos算法详解对一个proposal的提出和接受做一个系统的描述，这个过程分为请求和提出两个阶段。请求阶段提出阶段proposer选择一个编号n，

4、并向accepter多数派发出一个prepare请求如果accepter接受到的prepare所带有的编号n比它之前所做出过回应的prepare请求的编号都要高，则该accepter回应proposer一个promise如果proposer收到了accepter多数派对它所发出的prepare请求所做的回应，则它发出带有proposal的accept请求，proposal=(num,value)，value为回应所带回的proposal的value值如果accepter接受到一个accept请求，如果该accepter之前没有对任何编号大于n的prepare请

5、求做出过promise，则接受该proposal9PR：preparerequest（假设p1到a3的PR丢失）a1和a2是第一次接受到prepare请求，所以返回promise（不带回proposal），此时p1收到了a1和a2的promise，但是根据提出阶段的proposer必须接受来自多数派的promise才可以提出accept请求，因此不会出现先前例子中的情况。10.1Paxos算法Paxos算法详解p1a1a2a3PRPRPR10.1Paxos算法10.1.1Paxos算法背景知识10.1.2Paxos算法详解10.1.3Paxos算法举例1110

6、.1Paxos算法Paxos算法举例S2（Accepter）S3（Accepter）S4（Accepter）S5（Accepter）S1（Proposer）PrepareRequestPrepareRequestPrepareRequestPrepareRequestS1选定编号1（假设第一个命令编号为1），向集合database={s2,s3,s4,s5}的一个多数派子集发送PrepareRequest（PR）步骤一1210.1Paxos算法Paxos算法举例S2（Accepter）S3（Accepter）S4（Accepter）S5（Accepter）S1

7、（Proposer）PromiseProposalPromiseProposalPromiseProposalPromiseProposal步骤二如果通信顺利，所有的多数派都收到了PR如果通信部分失败导致接受到PR的节点不构成多数派则S1重复步骤1（PR编号递增）13S1接收到多数派的Paromise，向集合database发出带有第一个SQL命令（这里的SQL命令就是之前的value）的Proposal，编号为1，因为Promise没有带回Proposal所以这里的SQL命令没有限制。10.1Paxos算法Paxos算法举例步骤三1410.1Paxos算法P

8、axos算法举例S2（Accepter