资源描述:
《基于对等结构的广域网分布式存储系统研究》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、基于对等结构的广域网分布式存储系统研究(申请清华大学工学博士学位论文)培养单位:计算机科学与技术系学科:计算机科学与技术研究生:胡进锋指导教师:郑纬民教授二○○五年四月I摘要近年来,基于对等结构(Peer-to-Peer,简写为“P2P”)的大规模分布式系统迅速发展起来,成为占用Internet带宽最多的网络应用。本文的研究对象是对等结构的广域网分布式存储系统,它力图帮助用户在广域网范围内分布数据以提高数据的可靠性、可用性和访问性能。而P2P系统具有的大规模、高动态性、高异构性、强异步性等新特点为系统设计增加了难度。本文对广域网分布
2、式存储系统所涉及到的多个方面进行了细致充分的研究,提出了新颖有效的实用算法。本文的主要贡献包括:(1)提出了大规模P2P系统中结点信息收集算法PeerWindow,解决了已有算法不支持异构性的问题,使得P2P系统的结点可以根据各自能力决定结点信息收集量,同时,该算法具有很高的收集效率,结点每付出1kbps的带宽就可以收集到上千个其它结点的信息。(2)提出了异构环境下基于前串匹配的应用层组播算法,实现了异构系统中无冗余的组播算法,保证消息组播到所有相关结点,并且每个消息每个结点只收到一次。通过理论分析可以证明该算法具有完整性,且组播过
3、程无冗余。实验数据验证了算法的正确性并显示算法具有很高的组播效率。(3)提出了结构化覆盖网路由协议Tourist,解决了已有算法不具有自适应性的问题。Tourist充分利用了P2P系统中所有结点的可用带宽资源,在给定的系统环境下自动优化,取得最佳路由效率。同时,Tourist具有路由高效性,在500万结点的超大规模P2P系统中,所有消息路由都可以在两跳之内完成。(4)提出了P2P环境中的索引管理算法PB-linkTree,解决了已有算法在执行联合查询时带宽消耗过大的问题。PB-linkTree通过哈希定位将B+树分布到多个结点上,使
4、得联合查询的执行过程中不需要进行中间结果的大规模传输。实验表明,PB-linkTree较之传统的分布式索引管理算法DB-linkTree在查询过程中数据传输量更小,查询时间更短。(5)提出并实现了广域网分布式存储系统Granary,该系统利用本文的研究成果进行面向对象的数据存储和管理,支持基于属性的数据查询,具有更好的数据访问模式和更强的查询处理能力,方便上层应用的快速开发。关键词:对等系统分布式存储系统结构化覆盖网面向对象存储AbstractIIAbstractPeer-to-Peersystems(abbreviatedto“P
5、2Psystems”)havebeingexperiencingarapidgrowthinthepastseveralyears.Currently,ithasbecometheonethatoccupiesthemostamountofInternetbandwidthamongallthenetworkapplications.Inthisdissertation,wefocusonP2Pstoragesystems,whicharedeployedinthewide-areanetworkandintendtohelpuse
6、rsscattertheirfilesonotherpeers’storagedevicestoimprovedata’savailability,reliabilityandaccessefficiency.DesigningsuchasystemmustfacethenewpropertiesofP2Psystemswhichdidnotappearintraditionalcluster-scaleorLAN-scalesystems,i.e,largeamountofnodes,highdynamic,highheterog
7、eneity,highasynchrony,etc.WeproposeseveralnovelandpracticalagrithmsthataddressproblemsinvariousaspectsofP2Pstoragesystems.Maincontributionofthisdissertationisasfollows.(1)AnodecollectionprotocolinP2Psystems,PeerWindow,isproposed,whichletseverynodecollectalargeamountofi
8、nformationofothernodesataverylowcost.Furthermore,thisprotocolalsohasthepropertiesofhighefficiency,heterogeneity,self-