55基于分布式哈希表的对等系统关键技术研究

上海交通大学博士学位论文基于分布式哈希表的对等系统关键技术研究姓名：邹福泰申请学位级别：博士专业：计算机系统结构指导教师：马范援20041101申请上海交通大学博士学位论文摘要-I-基于分布式哈希表的对等系统关键技术研究摘要对等(peer-to-peer，简称P2P)系统是一个迅速发展的研究领域。P2P系统的应用已从传统的文件共享领域逐步扩展到更广泛的广域分布计算领域，因而需要P2P系统提供确定性定位与低查询开销等关键特性。基于分布式哈希表(DistributedHashTable，简称DHT)的P2P系统在广域网支持巨量集的数据一致性分布，并提供低跳步的路由精确定位，以及具有低查询开销和高容错自组织等优良性能，已经成为学术界研究的热点。分布式哈希表技术密切相关于P2P系统的设计，主要是拓扑、路由和查询此三个紧密相关的关键设计技术，并由此深刻影响着P2P系统的资源定位和查找的这一系统应用的核心问题。首先，分布式哈希表技术引入对传统P2P系统的拓扑结构的一种根本变革，将拓扑结构由一种随机、adhoc的非结构拓扑转变为确定的、有序的结构化拓扑；其次，分布式哈希表技术引入导致了路由技术的根本不同，由传统P2P系统的基于无向性的泛洪路由技术而转变为基于精确定位导向的单播路由技术；昀后，由于分布式哈希表技术对于拓扑、路由的变革影响，也导致了查询由传统P2P系统的自由式的随机查询且查询结果具不确定性转变为严格控制的查询且查询结果具确定性。这些变革特性，使得P2P系统在广域网级对诸如网络存储、组通信、名字服务、信息搜索等应用提供了极具竞争力的优良性能，从而大大超越了传统的文件共享的应用王国，给P2P系统带来新的发展和机遇。然而，分布式哈希表技术的引入在带来其先进性的变革影响的同时，也带来了新的挑战性问题。第一，由于拓扑是一种结构化的拓扑，相对比非结构化的拓扑，其维护开销显著加大。特别是在大规模和动荡的网络环境下，维护开销相当可观。第二，尽管路由采用了精确的定向单播技术，减少其路由跳数仍然是个重要的问题。在保证高度的分散性前提下，如何尽可能减少其路由跳数是研究所特别关注的，通常也称之为路由的状态与效率折衷问题。第三，基于分布式哈希表的查询是一种单关键字的精确匹配，尽管相对于非结构化系统它使得系统资源可被确定性的查询到，但它也极大地限制了查询的应用范围。这些问题对于P2P申请上海交通大学博士学位论文基于分布式哈希表的对等系统关键技术研究-II-系统的可用性和效率是重要而又关键的。本文研究了P2P系统中应用分布式哈希表技术所存在的这些极富挑战性的问题，在保障分布式哈希表技术带来的优良性能的前提下，在一定程度上突破了DHT技术应用的局限性，初步解决了上述的挑战性问题，取得了有价值的进展，主要的创新性贡献如下：1．提出了在动态网络环境下自适应的拓扑调整模型――SHT(SessionHeterogeneityTopology)，能够有效地控制DHT拓扑维护开销并提高了系统资源的可用性，较好解决了DHT拓扑维护的高开销问题。SHT利用节点的会话异构特性将DHT重构，将DHT的拓扑构造变成仅由稳定节点组成，从而大大降低了拓扑适应动态环境的调整开销。研究揭示出会话时间短的节点是拓扑调整的主要扰动因子，因此建议拓扑设计时将它们聚簇于稳定节点，并由稳定节点代理它们的请求，从而在保证它们能够正常使用系统的同时又将它们的扰动限制于局部于稳定节点的动荡。理论分析和实验表明一个合理的聚簇大小存在使得拓扑达到近似昀优化，此时减少的开销达到近似昀小。2．提出了基于小世界理论的概率缓存链技术，能够在高度分散的低状态路由表下达到较高的路由效率，较好解决了DHT路由的低效率问题。研究利用了DHT路由的贪婪特性及查询的反馈机制，构造了概率缓存的路由快捷链，由此在路由表链间形成了一个小世界，使得系统的路由性能得到全局性的优化。设计充分考虑了静态与动态下的收敛问题，并设计主动查询机制以适应动态环境并加速收敛，使系统性能得到保障。由于设计采用的是查询反馈机制以及缓存技术，具有较强的现实意义。特别对于当前的一大类采用低状态DHT路由表的具有高度松散结构的P2P系统，能够在轻微的修改下达到路由效率的可观的提高。3．提出了基于向量空间模型(VSM)的相似文档搜索方法和技术，使得DHT查询能支持多关键字查询和相似文档搜索，从而突破了DHT查询的单关键字的精确匹配约束，使DHT查询的应用范围大为扩展，较好解决了DHT查询的应用局限性问题。研究在两方面对DHT查询进行改进。一方面，目前基于DHT的多关键字查询技术，通常采用单关键字的组合查询的模式，带来较多的网络开销。通过VSM技术将多个关键字形成了向量空间模型VSM中的向量，并使得查询相关于此向量，从而能够支持多关键字查询并去除了单关键字组合查询所需的大量网络开申请上海交通大学博士学位论文摘要-III-销。另一方面，当前DHT查询的局限性本质是由于哈希使得查询失去了语义性支持，仅能够支持精确匹配，而利用VSM技术进行文档标识的哈希空间重映射，使得DHT文档标识具有相似性的语义，从而支持相似性文档搜索。关键词：对等系统，分布式哈希表，拓扑，路由，查询，会话异构，小世界模型，相似文档搜索申请上海交通大学博士学位论文ABSTRACT-V-RESEARCHONTHEKEYTECHNIQUEOFPEER-TO-PEERSYSTEMSBASEDONDISTRIBUTEDHASHTABLEABSTRACTPeer-to-Peer(P2P)systemisaresearchfieldwithrapiddevelopment.FortheapplicationareasofP2PsystemshavegraduallyexpandedfromtraditionalfilesharingtodistributecomputingoverInternet,somekeyfeaturessuchasdeterministiclocatingandlowqueryoverheadsareneededforP2Psystems.P2Psystem,basedonDistributedHashTable(DHT),canprovideaserialofniceperformancesuchastheconsistentdistributionofmegadataintheInternet,theexactlocatingofroutingswithfewhops,highfault-toleranceandself-organizationetc.,soithasbecometheresearchhot.DHTtechniqueistightlyrelatedtothewholedesignofP2Psystems,especiallytothethreekeydesigntechniques:topology,routingandquery.Asamatteroffact,itdeeplyaffectsthecoreproblems—resourcelocatingandresourcesearchinginP2Psystems.Firstly,DHTtechniquetriggersaradicalrevolutionforthetopologyofP2Pandchangesthetopologyfromakindofrandom,adhocstructuretodeterministic,orderedstructure.Secondly,DHTtechniqueresultsinarevolutiononroutingtechniqueandchangesthetraditionalrouting,whichbasedonunidirectionalbroadcast,intotheunicastroutingaccordingtoexactdirection.Finally,forDHTtechniqueexertstherevolutionaryeffectonthetopologyandrouting,itchangesP2Pquery,whichusedtorelyonthetopologyandroutingfromthefreeandrandomquerymodewithuncontrolledresults,toastrictlycontrolledquerymodewithdeterministicresults.AllthesenewrevolutionarycharacteristicsallowP2Psystemsprovideacompetitivelyniceperformanceintheapplicationsinthelevelofwideareanetwork(WAN),forinstance,networkstorage,groupcommunication,nameservice,informationretrievaletc,andthushavegreatlysurpassedthekingdomoffilesharingandhavebroughtP2Psystemsnewchancesanddevelopments.However,DHTtechniquebringsthenewchallengeswhileitbringstheadvanced,revolutionaryeffects.Firstly,DHTtopologyisstructuredwithhighoverheads申请上海交通大学博士学位论文基于分布式哈希表的对等系统关键技术研究-VI-comparedwithunstructuredtopology.Especially,themaintainingoverheadswouldremarkablyriseupindynamicnetwork.Secondly,thoughDHTroutingusestheexactlydirectedunicasttechnique,toreduceroutinghopsisstillasignificantproblem.Howtoreducetheroutinghopsasmuchaspossibleundertheguaranteeofhighdecentralizationisafocusoftheroutingresearch.Generally,itisalsocalled“stateefficiencytradeoff”problem.Finally,DHTqueryisakindofexactmatchonthesinglekeyword.ThoughitassuresthattheresourceinthesystemcanbedeterministicallysearchedincontrasttotheunstructuredP2Psystems,DHTquerygreatlylimitstheapplicationareaofP2Pquery.AlltheseproblemsareimportantandcrucialfortheusabilityandefficiencyofP2Psystems.Inthisthesis,wemakearesearchonthesechallengingproblemsofDHTtechniquewhenitisappliedonP2Psystems.WeresolvethesechallengingproblemswithoutthelossofniceperformanceofDHTtechnique,soastobreakthroughthelimitationofDHTtechnique.Thecontributionofthisdissertationisinthefollowinga