,of,41,云计算,第三版配套,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!,序言下载提示：该课件是本店铺精心编制而成的，希望大家下载,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,4,10.2 DHT,算法,Chord,中,DHT,的具体实现,Chord,Chord,环,Chord,中所有节点按节点,ID,大小顺时针排列并首尾相接组成一个拥有,2m,（,m,一般为,160,）个节点的环空间,后继,节点,successor,消息的目标节点就是节点,ID,大于或者等于消息,Key,值的节点中节点,ID,最小的一个,完全分布,可扩展性,可用性好,负载均衡,410.2 DHT算法Chord中DHT的具体实现Chor,5,Chord,模型示意图,10.2 DHT,算法,Chord,中,DHT,的具体实现,m=6,且只有,10,个节点的查找示意图，其中节点标识前加上,N,而关键字标识前加上,K,加以区别，图中给出了节点,N8,、,N42,、,N51,的,finger,表。,5Chord模型示意图10.2 DHT算法Chord中DH,6,10.2 DHT,算法,Chord,中,DHT,的具体实现,节点,N,的加入过程,初始化新节点,的,指针,表,更新现有其他节点的指针表,从后继节点把关键字传递到节点,N,节点的退出过程,在,Chord,中，当节点,N,失效时，所有指针表中包括,N,的节点都必须把,N,替换成,N,的后继节点。,在失效处理中最关键的步骤是维护正确的后继指针,610.2 DHT算法Chord中DHT的具体实现节点N的,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,8,10.2 DHT,算法,Pastry,中,DHT,的具体实现,1,节点的加入,假定新加入节点的节点号为,N,，节点号的分配过程是由应用程序决定,的,。,N,的加入过程主要包括初始化自己的节点数据结构，并通知其他节点自己已经加入系统。,N,在加入,Pastry,之前，需要知道一个相邻节点,A,的位置信息。,2,节点的退出,Pastry,网络中的节点可能会随时失效或者不发出通知离开系统。,当相邻节点不能和某个,Pastry,节点通信时，就认为该节点发生了失效。,810.2 DHT算法Pastry中DHT的具体实现1节,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,10,10.2 DHT,算法,CAN,中,DHT,的具体实现,CAN,是内容可编址网络（,Content-Addressable Network,）的缩写,CAN,可以在,Internet,规模的大型对等网络上提供类似哈希表的功能。,CAN,具有可扩展、容错和完全自组织等特点。,CAN,类似于一张大哈希表，基本操作包括插入、查找和删除。,CAN,由大量自治的节点组成，每个节点保存哈希表的一部分，称为一个区。,CAN,的设计完全是分布式的，不需要任何形式的中央控制点。,CAN,具有很好的可扩展性，节点只需要维护少量的控制状态而且状态数量独立于系统中的节点数量。,CAN,支持容错特性，节点可以绕过错误节点进行路由。,1010.2 DHT算法CAN中DHT的具体实现CAN是内,11,二,维坐标空间中,CAN,的节点示意图,10.2 DHT,算法,CAN,中,DHT,的具体实现,C,(0-0.5,0.5-1.0),D,(0.5-0.75,0.5-1.0),E,(0.75-1.0,0.5-1.0),A,(0-0.5,0-0.5),B,(0.5-1.0,0-0.5),0.0,1.0,1.0,整个区域坐标由,5,个节点,A,，,B,，,C,，,D,，,E,组成，每个节点负责部分区域,，,CAN,中通过哈希函数把资源映射到,d,维空间中的一点，资源对象就发布在该节点上。,11二维坐标空间中CAN的节点示意图10.2 DHT算法C,12,CAN,路由模型的路由过程,10.2 DHT,算法,CAN,中,DHT,的具体实现,(0,1),(1,0),(0,0),(1,1),Key=(0,8,0,9),Node=(0.75,0,0.75,1),查询操作通过在,d,维笛卡儿坐标空间中转发查询消息被执行，转发从查询初始化点沿着坐标系上最接近直线的路径到达存储关键字的节点。,12CAN路由模型的路由过程10.2 DHT算法CAN中D,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,14,10.2 DHT,算法,Tapestry,中,DHT,的具体实现,Tapestry,分层路由和组织结构的查询算法，它为面向广域网的分布式应用提供了一个分布式查找和路由定位基础平台。,Tapestry,网络中每个节点和文档通过哈希变换得到各自,160,位比特的唯一标识符,Tapestry,基于文档标识符的后缀进行,路由,Tapestry,基于,Plax ton,中提出的定位和路由机制进行,优化,Tapestry,采用的基本定位和路由机制和,Plax ton,很,类似,Tapestry,中的每个节点都可以用,Plax ton,中描述的算法转发,消息,1410.2 DHT算法Tapestry中DHT的具体实现,15,10.2 DHT,算法,Tapestry,中,DHT,的具体实现,1,节点的加入,Tapestry,的节点加入算法和,Pastry,很类似。,构造完自己的数据结构后，节点,N,将通知网络中的其他节点，自己已经加入网络。,构造过程中还需要进行一些优化工作。,2,节点的退出,一种情况是节点从网络中自行消失，在这种情况下，它的邻居可以检测到它已经退出网络并可以相应地调整路由表；,另一种机制是节点在退出系统之前，利用后向指针确定所有把它作为邻居的节点，这些节点会相应调整路由表并通知对象服务器该节点已经退出网络。,1510.2 DHT算法Tapestry中DHT的具体实现,10.1 Paxos,算法,10.2,DHT,算法,10.3 Gossip,协议,10.1 Paxos算法10.2 DHT算法10.3,10.3 Gossip,协议,10.3.1 Gossip,协议的特点,10.3.2 Gossip,协议的通信方式及收敛性,10.3.3 Gossip,节点管理算法,10.3.4 Cassandra,中,Gossip,协议的具体实现方式,10.3.5 CoolStreaming,系统中,Gossip,协议的具体实现方式,10.3 Gossip协议10.3.1 Gossip协议,18,10.3 Gossip,协议,Gossip,协议的特点,Gossip,协议具有以下几个,优点,:,分布式容错,最终一致性,去中心化,当系统中有节点因为宕机而重启，或有新节点加入，经过一段时间后，这些节点的状态仍会与系统中其他节点达成一致，也就是说,Gossip,天然具有分布式容错的特点。,Gossip,协议虽然无法保证在某个时刻所有节点状态保持一致，但可以保证在“最终”所有节点一致。“最终”是一个现实中存在，但理论上难以证明的时间点。,Gossip,协议不要求节点知道系统中所有节点的状态，节点之间完全对等，不需要任何中心节点。,1810.3 Gossip协议Gossip协议的特点Gos,Gossip,协议的缺点也很,明显,冗余通信会大大增加,网络和,CPU,的,负载,并,进一步影响算法收敛的,速度,Gossip协议的缺点也很明显冗余通信会大大增加网络和CPU,10.3 Gossip,协议,10.3.1 Gossip,协议的特点,10.3.2 Gossip,协议的通信方式及收敛性,10.3.3 Gossip,节点管理算法,10.3.4 Cassandra,中,Gossip,协议的具体实现方式,10.3.5 CoolStreaming,系统中,Gossip,协议的具体实现方式,10.3 Gossip协议10.3.1 Gossip协议,21,10.3 Gossip,协议,Gossip,协议的通信方式及收敛性,传染病算法,（,Epidemic Algorithm,）,中,存在三种不同单元：,人口,（,population,）,交互,（,a set of interactive,）,交流,（,communicating,）,这三个单元通过既定规则决定如何传递信息。规则可以由用户自由设定，但是任意单元在特定时间 内必须处于以下三种状态之一。,易受感染,（,Susceptible,）,传染,（,Infective,）,恢复,（,Recovered,）,单元不了解信息的内容，但可以收到这条信息。,单元知道（接收到）信息，按照指定规则进行传播。,单元知道（接收到）信息，但不进行转发。,2110.3 Gossip协议Gossip协议的通信方式及,22,10.3 Gossip,协议,Gossip,协议的通信方式及收敛性,1,感染,-,传染（,Susceptible-Infective,，,SI,）,该类算法中几乎每个单元最初都设定为感染状态，当一个单元接收到更新的信息后立即转为传染状态，并保持这种状态直到所有单元都成为传染状态。,与,SI,算法模型不同，,SIS,算法可以决定在全部人口被传染前停止传播。,SIR,算法和,SIS,算法唯一区别是恢复单元在停止传播信息之后便不再收到传染。,2,感染,传染,感染（,SIS,）,3,感染,传染,恢复（,SIR,）,2210.3 Gossip协议Gossip协议的通信方式及,10.3 Gossip,协议,10.3.1 Gossip,协议的特点,10.3.2 Gossip,协议的通信方式及收敛性,10.3.3 Gossip,节点管理算法,10.3.4 Cassandra,中,Gossip,协议的具体实现方式,10.3.5 CoolStreaming,系统中,Go