注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Ooi Beng Chin 黄铭钧

Databases, Machine Learning and Systems

 
 
 

日志

 
 

P2P拓扑结构和云计算系统  

2009-08-18 10:22:26|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 一般在云计算系统中,一个或者几个大型服务器控制和维护着整个集群系统的运作。这些服务器主要有两个功能。首先,他们要维护一个分布式文件系统结构,以便于在计算机集群系统中有效的存储和访问海量的数据。其次,他们需要维护系统中每一台计算机的状态,以便分配和监视所有的执行任务。在云计算系统中,这些服务器扮演着非常重要的角色。普通的机器出现故障,不会影响整个系统的运作。而服务器出现问题,会导致整个系统瘫痪。因此,这些服务器需要特别的维护,通常使用备份服务器来防止故障发生。

为了能够减轻这些服务器的负载,增加整个系统的可扩展性,我们提出了使用P2P拓扑结构来组织云计算系统的方法。所有的机器都加入一个结构化的P2P拓扑结构,我们利用P2P拓扑结构的路由算法来进行检索和查询。这样做可以减轻服务器的负载,带来下面两个优点:

1.  经过近10年的研究,结构化P2P拓扑结构已经比较成熟,它们具有高效、高扩展性的优点。并且,它们都有比较完善的错误处理机制,如果一个节点发生了故障,其他的节点可以检测并且替代它。因此,将P2P拓扑结构运用到云计算系统中,可以降低我们的维护整个网络的代价。

2.  在结构化P2P拓扑结构中,每个节点都维护一个路由表,用来高效的检索和查询。利用该路由表,我们可以建立分布式的索引结构,从而进一步降低服务器的负载。

然而一个问题就是,在几乎所有的结构化P2P拓扑结构中,基于路由算法的查询代价为O(logN),N是整个系统中的节点数.虽然在P2P系统中,logN并不是很大的代价,然而在云计算系统,每秒需要处理大量的数据和查询,logN的查询代价将严重影响整个系统的效率.相比而言,基于服务器的系统[1],只需要1到2个网络消息,就可以得到相应的数据.虽然一些工作[2]尝试扩展拓扑结构来提高查询效率,但是它们往往过于复杂,不利于维护.这样看来,查询代价成为阻碍我们使用P2P拓扑结构的一个最大的障碍.

 

但是,我们忽略一个事实,云计算系统和P2P系统是非常不同的.在云计算系统中,所有的节点归属与服务提供商,他们对这些节点具有全部的操作权限.而在P2P系统中,每一个节点都属于一个个人,他只提供有限的服务,或者根本不予以合作.更加不同的是,在云计算系统中,为了保证服务的稳定性,所有的节点都保持在线,除非它们发生硬件故障,然而在P2P系统中,任何一个节点都可能在任何时间内离开系统.从上面的观察,我们得出一个结论,虽然我们使用结构化P2P拓扑结构来组织云计算系统中的节点,但是我们的系统绝对不是P2P系统,它只是借用拓扑结构来维护网络。在我们的系统中,拓扑结构相对是稳定的。也就是说,一个节点会一直保持它在拓扑结构的位置,除非出现故障。因此,我们的拓扑结构是相对静态的。基于这样的分析,为了加速整个系统的查询,我们在每一个节点上复制整个的拓扑结构。不需要查询它的路由邻居,该节点可以通过本地的拓扑结构副本直接找到相关的节点,从而使得查询代价将为O(1)。这种方法是否具有可行性呢?

1.从存储代价来看,一个拓扑结构就相当于一个本地的数据结构,对于Chord来说,一个环;对于BATON来说,是一个二叉树, 而BATON*  是个 多叉树。不管是哪一种结构,因为整个网络中的节点相对较少(比如Google的集群有几千台机器),存储这样的一个数据结构都不是问题。

2. 从维护代价来看,因为节点相对稳定,拓扑结构也相对稳定,所以我们并不需要经常性的更新。如果有新节点加入,或者有旧的节点发生故障,我们需要告诉网络中所有的节点来更新他们的本地副本。为了进一步降低这样的代价,我们采用Lazy Update的技术,系统并不会主动地更新节点的本地副本。只有当节点进行查询时,发现拓扑结构的变化,它才会要求进行更新。Lazy Update得可行性在于,即使本地拓扑结构副本完全实效,我们仍然可以使用路由表来找到相应的结果。也就是说,Lazy Update并不会影响整个系统的正常工作,它只是一种优化方法。

 本地节点,以提高查询效率。我们认为在云计算中,这样的策略是可行的。P2P拓扑结构的加入,降低了系统地维护代价,从而使得部署大规模的云计算系统更加容易。并且,它有效的降低了服务器的负载,使得整个系统更加的稳定和觉有可靠展性。

 

[1] Marcos K. Aguilera, Wojciech Golab, Mehul A. Shah. A practical scalable distributed B-tree. VLDB 2008.

[2] H V Jagadish and Beng Chin Ooi and Kian-Lee Tan and Quang Hieu Vu and Rong Zhang. Speeding up search in peer-to-peer networks with a multi-way tree structure. SIGMOD 2006.

[3] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo: Amazon’s highly available key-value store,” SIGOPS, 2007.

[4] Q. Vu, M. Lupu, B. C. Ooi.Peer-to-peer computing: Principles and Applications. Springer-Verlag 2009.

  评论这张
 
阅读(2032)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017