,of,34,云计算,第三版配套,PPT,课件,云计算,（第三版）,CLOUD COMPUTING,Third Edition,第,10,章,云计算核心算法,(,一,),云计算（第三版）CLOUD COMPUTING Third,序言,下载提示：该课件是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。课件下载后可定制修改，请根据实际需要进行调整和使用，谢谢！,Download reminder:This courseware is carefully compiled by this shop.I hope that after you download it,it can help you solve practical problems.The courseware can be customized and modified after downloading,please adjust and use it according to actual needs,thank you!,序言下载提示：该课件是本店铺精心编制而成的，希望大家下载,3,云计算的基础技术是集群技术，支撑集群高效协同工作需要一系列资源和任务调度算法，良好的调度算法可以提高集群处理能力，有效分配资源，加速作业进度。,三种核心算法,Paxos,算法,DHT,算法,Gossip,协议,解决分布式系统中信息一致性问题,解决分布式网络的应用层选路问题,解决分布式环境下信息高效分发问题,3云计算的基础技术是集群技术，支撑集群高效协同工作需要一系列,10.1 Paxos,算法,10.2,DHT,算法,10.3 Gossip,协议,10.1 Paxos算法10.2 DHT算法10.3,Paxos,算法,解决的问题是一个,分布式系统,如何就某个,value,（决议）达成一致,。,Paxos,算法作为分布式系统中最著名的算法之一，在目前所有的一致性算法中，该算法最常用而且被认为是最有效的。,Paxos算法解决的问题是一个分布式系统如何就某个value,10.1 Paxos,算法,10.1.1 Paxos,算法背景知识,10.1.2 Paxos,算法详解,10.1.3 Paxos,算法举例,10.1 Paxos算法10.1.1 Paxos 算法背,7,10.1 Paxos,算法,Paxos,算法背景知识,processor,可以担任三个角色“,proposer”,、“,accepter”,和“,learner”,中的一个或多个角色。,proposal,和,value,：,proposal,一般译为“提案”，,value,一般译为“决议”。,proposer,可以,propose,（提出）,proposal,；,accepter,可以,accept,（接受）,proposal,各个,processor,之间信息的传递可以延迟、丢失，但是在这个算法中假设传达到的信息都是正确的,1,2,3,4,710.1 Paxos算法Paxos 算法背景知识proc,10.1 Paxos,算法,10.1.1 Paxos,算法背景知识,10.1.2 Paxos,算法详解,10.1.3 Paxos,算法举例,10.1 Paxos算法10.1.1 Paxos 算法背,9,10.1 Paxos,算法,Paxos,算法详解,Paxos,算法的核心是，只要满足下面三个条件就能保证数据的一致性：,1,一个,value,只有在被,proposer,提出之后才可以被,choose,；,2,每次只有一个,value,被,choose,；,3,value,只有被,choose,之后才能被,learners,所获取。,910.1 Paxos算法Paxos 算法详解Paxos算,10,10.1 Paxos,算法,Paxos,算法详解,对,一个,proposal,的提出和接受做一个系统的描述，这个过程分为请求和提出两个阶段。,请求,阶段,提出,阶段,proposer,选择一个编号,n,，并向,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,请求做出过,promise,，则接受该,proposal,1010.1 Paxos算法Paxos 算法详解对一个pr,11,PR,：,prepare request,（假设,p1,到,a3,的,PR,丢失）,a1,和,a2,是第一次接受到,prepare,请求，所以返回,promise,（不带回,proposal,），此时,p1,收到了,a1,和,a2,的,promise,，但是根据提出阶段的,proposer,必须接受来自多数派的,promise,才可以提出,accept,请求，因此不会出现先前例子中的情况。,10.1 Paxos,算法,Paxos,算法详解,p1,a1,a2,a3,PR,PR,PR,11PR：prepare request（假设p1到a3的P,10.1 Paxos,算法,10.1.1 Paxos,算法背景知识,10.1.2 Paxos,算法详解,10.1.3 Paxos,算法举例,10.1 Paxos算法10.1.1 Paxos 算法背,13,10.1 Paxos,算法,Paxos,算法举例,S2,（,Accepter,）,S3,（,Accepter,）,S4,（,Accepter,）,S5,（,Accepter,）,S1,（,Proposer,）,Prepare Request,Prepare Request,Prepare Request,Prepare Request,S1,选定编号,1,（假设第一个命令编号为,1,），向集合,database=s2,s3,s4,s5,的一个多数派子集发送,Prepare Request,（,PR,）,步骤一,1310.1 Paxos算法Paxos 算法举例S2（Ac,14,10.1 Paxos,算法,Paxos,算法举例,S2,（,Accepter,）,S3,（,Accepter,）,S4,（,Accepter,）,S5,（,Accepter,）,S1,（,Proposer,）,Promise Proposal,Promise Proposal,Promise Proposal,Promise Proposal,步骤二,如果通信顺利，所有的多数派都收到了,PR,如果通信部分失败导致接受到,PR,的节点不构成多数派则,S1,重复步骤,1,（,PR,编号递增）,1410.1 Paxos算法Paxos 算法举例S2（Ac,15,S1,接收到多数派的,Paromise,，向集合,database,发出带有第一个,SQL,命令（这里的,SQL,命令就是之前的,value,）的,Proposal,，编号为,1,，因为,Promise,没有带回,Proposal,所以这里的,SQL,命令没有限制,。,10.1 Paxos,算法,Paxos,算法举例,步骤三,15S1接收到多数派的Paromise，向集合databas,16,10.1 Paxos,算法,Paxos,算法举例,S2,（,Accepter,）,S3,（,Accepter,）,S4,（,Accepter,）,S5,（,Accepter,）,S1,（,Proposer,）,SQL,SQL,SQL,SQL,步骤四,通信顺利,决议产生,接收,Proposal,通信失败,构成多数派,决议,不,产生,不,构成,多数派,1610.1 Paxos算法Paxos 算法举例S2（Ac,17,重复,以上操作，注意,Proposal,、,Prepare,以及,Promise,的编号递增,，以及,Promise,根据情况带回,Proposal,。,10.1 Paxos,算法,Paxos,算法举例,步骤,五,17重复以上操作，注意Proposal、Prepare以及P,10.1 Paxos,算法,10.2,DHT,算法,10.3 Gossip,协议,10.1 Paxos算法10.2 DHT算法10.3,19,10.2 DHT,算法,Client/Server,计算模式（即客户,服务器计算模式）主要应用于小规模的网络环境。,Client/Server,计算模式采用中央集中式架构，中央节点（服务器）对整个网络服务具有决定性的作用。,大部分的计算都集中在服务器端，因而引起负载的不平衡。即所谓的“服务器端的计算瓶颈”，而客户机端则存在资源浪费的情况。,集中式计算模式对用户的隐私以及数据安全也将存在不可能解决的难题。,1910.2 DHT算法Client/Server计算模式,20,10.2 DHT,算法,P2P,计算模式是一种非集中计算模式。,P2P,网络中的每台计算机（或称对等点），具有同样的地位，既可以请求服务，也可以提供服务。,P2P,计算模式具有资源充分利用，网络规模可扩展（节点越多网络越稳定，不存在瓶颈）等优点。,下一代计算机网络（即云计算和物联网）都是巨大的网络，因此，未来的计算模式应该是,P2P,计算模式,2010.2 DHT算法P2P计算模式是一种非集中计算模式,21,10.2 DHT,算法,P2P,按照拓扑结构的不同可以分为三,种：,集中式拓扑模式,这种模式必须有中央服务器。当系统中节点数增多时，中央服务器就成为系统的瓶颈。,分布式非结构化拓扑模式,在非结构化,P2P,系统中，信息搜索的算法难免会带有一定的盲目性。,分布式结构化拓扑模式,由于用户预先知道应该搜索哪些节点，避免了非结构化,P2P,系统中使用的泛洪式查找，提高了信息搜索的效率。,2110.2 DHT算法P2P按照拓扑结构的不同可以分为三,10.2 DHT,算法,10.2.1 DHT,原理介绍,10.2.2 Chord,中,DHT,的具体实现,10.2.3 Pastry,中,DHT,的具体实现,10.2.4 CAN,中,DHT,的具体实现,10.2.5 Tapestry,中,DHT,的具体实现,10.2 DHT算法10.2.1 DHT原理介绍10.2,23,DHT,技术的基本概念,10.2 DHT,算法,DHT,原理介绍,事件通知,网络存储,其他应用,DHT,TCP/IP,应用层,DHT,层,网络层,DHT,分布式哈希表采用,Hash,函数加速了查找速度和增强了安全性，而且便于管理，同时不会占用太多的网络带宽,23DHT技术的基本概念10.2 DHT算法DHT原理介绍,24,DHT,应用层的接口,10.2 DHT,算法,DHT,原理介绍,应用层,DHT,Node,Node,Node,Insert,（,Key,，,data,）,LookUp,（,Key,）,通过,DHT,层的,LookUp(Key),操作，可以把应用层的数据均匀分布在网络的各个节点内，这种方法使下层网络完全不受中心控制,24DHT应用层的接口10.2 DHT算法DHT原理介绍应,25,10.2 DHT,算法,DHT,原理介绍,所有的,DHT,路由算法都主要包括三个方面,:,第一方面,第二方面,第三方面,DHT,的散列值空间的描述,DHT,中各节点如何分配管理散列空间,路由发现算法,即如何进行散列,即散列后的信息如何决定其存储的节点位置,即对散列值进行查询时节点如何高效地路由到存储目标信息的节点,2510.2 DHT算法DHT原理介绍所有的D