基于DHT的分布式文件系统毕业论文

本科毕业论文论文题目基于DHT的分布式文件系统

目录摘要 1关键词 1Abstract 1Keywords 21绪论 21.1分布式系统的定义 31.2目标 51.2.1让用户连接到资源 61.2.2透明性 61.2.3开放性 71.2.4可扩展性 81.3分布式文件系统 81.3.1SUN网络文件系统 91.3.2不同分布式文件系统对比 122P2P技术 132.1P2P技术 132.1.1P2P的背景与发展 132.1.2．p2p技术的分类 142.1.3．p2p的特性 202.2P2P搜索技术 212.2.1非结构化搜索技术 212.2.2基于DHT的搜索技术 222.3Chord 262.3.1finger表 262.3.2Chord算法的查找过程 273基于DHT的Chord算法的改进 313.1影响搜索算法性能的因素 313.2小世界现象对P2P搜索技术的启示 323.3NChord搜索算法 363.3.1Nchord算法网络拓扑结构 363.3.2节点加入时的策略 373.3.3节点退出时的策略 383.3.4节点失效时的策略 393.3.5NChord算法原理 393.3.6Nchord搜索算法的步骤 413.3.7Nchord算法特点 42结论 43致谢 43参考文献 44PAGE45基于DHT的分布式文件系统研究学生姓名：王京学号：20077101021信阳师范学院华锐学院数计系计算机科学与技术专业指导教师：杨军职称：讲师摘要：随着信息时代的飞速发展，人们日益发现单个计算机的能力很是有限，于是自然而然想到把各个地方的计算机联合起来处理信息，这就是分布式的提出，随即涉及到资源共享的问题，这就是我们研究的分布式文件系统,随着P2P（即Peer-to-Peer）技术的发展，很好的解决了分布式存储与计算方面的问题，它作为一种全新的互联网技术，将传统的以服务器为中心的互联网应用模式提升为以用户为中心的对等模式。P2P在文件交换，对等计算，协同工作，搜索服务等方面都有着重要的应用。P2P文件交换系统的发展也由最初Npaster的完全中心化模型，Gnutella的完全非中心化模型，发展到现在的BitTorrnet、eMul/eeDoknye、KZaza等混合模型。随着近年来DHT(DisrtibutedHashTable)技术的不断发展，DHT在p2p文件交换系统中扮演着越来越重要的角色，Kdamelai作为覆盖网络被广泛使用到P2P文件交换系统中。P2P网络通常使用DHT作为其路由表，比较典型的算法有Chord、CAN、Kademlia、Tapestry、Pastry等，这些算法不仅可靠性高，容错性强，而且查找的效率非常高，查找算法的复杂度基本上都是O(LogN)，被广泛地应用于各种各样的分布式系统中。本文将比较分析以上各算法的原理和差异，重点分析、研究和改进Chord算法，减少路由跳数和系统开支。关键词：分布式;分布式文件系统;p2p;DHT;ChordAbstract：Withtherapiddevelopmentofinformationera,Peopleincreasinglyfindasinglecomputerabilityisverylimited,Naturallytheytemptedtoconnectwithcomputersineveryregiontoprocessinginformation,thusthedistributedproposed,butthencomestheresourcesharingproblem,that’stheDistributedFileSystemherewhatwearetalkingabout,asthedevelopmentofp2p(peer-to-peer)technology,theproblemofdistributedstorageandcomputingiswellsolved,thetechnologyofp2p(peer-to-peer),asanewInternettechnology,promotingthetraditionalcentralizedserverInternetApplicationModletocentralizeduserPeertoPeerModle.P2PisimportantinData-Exchange,Peer-to-PeerComputing,CoordinatedWorking,SearchService,etc,InP2Pfile-sharingsystems,itisdevelopingfromthebeginningcentralizedmodelNapsteranddecentralizedmodelGnutellatothecurrentmixedmodle,suchasBitTorrent,eMule,Kazza,etc.AstheDHT(DistritutedHashTable)technologydevelops,itplaysamoreimportantroleinP2Pfile-sharingsystem,KademliaisusedwidelyinP2Pfile-sharingsystemasanoverlaynetwork.DistributedarchitectureofthenetworkiscommonlyusedtobuildP2PnetworksusingDHTalgorithm,forinstance,Chord,CAN,Kademlia,Tapestry,Pastry,etc.Thesealgorithmsnotonlypossesshighreliabilityandstrongfaulttolerance,butalsohaveefficientlookup.ThecomplexityofsearchalgorithmisbasicallyO(LogN),sotheyarewidelyusedinavarietyofdistributedstoragesystems.ThispaperstudyandcomparetheprinciplesanddifferencesofaboveDHTalgorithms,research、analysisandpromotetheChordalgorithmmorein-depth.thusdecreasingthejumpnumbersduringtheprocessofsearchingandthecostofsystem.Keywords:distributed;distributedfilesystem;p2p;DHT;Chord1.绪论计算机系统正在经历一场革命。1945年是现代计算机时代的开始。从那时起一直到1985年，计算机一直是庞大笨重而昂贵的。即便是小型机每台也要上万美元，因而大多数机构都只有很少的几台计算机。而且由于没有把这些计算机连接起来的手段，所以只能单独的使用它们。然而，从20世纪80年代中期开始，技术领域中两方面的进步开始使这种局面有所改观。第一项进步是高性能处理器的开发。起初这些机器是8位机，但是很快16位、32位乃至64位的cpu纷至沓来，得到了普及。很多使用这些cpu的机器的计算性能都可以与大型机相媲美，而价格却比大型机便宜得多。近半个世纪以来，在计算机技术改进方面所取得的成果数量之多对于其他工业来说是完全无法想象的。一台计算机的价格从1亿美元下降到了1000美元，而运算速度却从每秒一条指令提升到每秒1千万条指令，性能价格比提升了大约1012倍。如果汽车的性能价格比在同一时期以同样的速率是提升，那么一辆“劳斯来斯”牌轿车现在只值1美元，而且每消耗1加仑（1加仑=4.5461升）汽油可以行驶10亿英里（1英里=1.6093公里）。（不幸的是如果果真如此，光是说明如何打开车门这件事，就可能在用户手册中占用长达200页得篇幅。）第二项进步是高速计算机网络的发明。利用局域网技术可以将位于同一建筑物里的数百台计算机连接起来。使用这种连接方式可以在几us内将少量数据从一台机器传输到另一台机器。如果要传输大量的数据，传输数率可以达到10～1000Mb/s。利用广域网技术可以连接全球范围内数百万台机器，机器间的数据传输速率从64Kb/s到若干Gb/s不等。现在，由于有以上这些技术可供使用，因此把若干由大量计算机组成的计算机系统彼此通过高速网络相连接，不但是可行的，而且是很容易实现的。这种系统一般称为计算机网络或分布式系统，以突出其与传统的集中式系统（centralizedsystem，也称为单处理器系统，singleprocessorsystem）的差异。传统的集中式系统一般由单个计算机及其外围设备构成，也可以包含一些远程终端。1.1分布式系统的定义已经有很多文献给出了分布式系统的定义，但是不同文献给出的定义彼此不尽相同，而且没有一种令人满意。考虑到本文的目标，我们只给出一个粗略的描述：分布式系统是若干独立计算机的集合，这些计算机对于用户来说就像是单个相关系统。这个定义包含了两方面的内容。第一方面是关于硬件的：机器本身是独立的，第二个方面是关于软件的：对用户来说他们就像在与单个系统打交道。这两个方面共同阐明了分布式系统的本质，缺一不可。我们先介绍关于软硬件的一些背景材料，与继续探讨分布式系统的定义相比，把注意力集中在分布式系统的重要特性上可能更好一些。其重要特性之一是，各种计算机之间的差别以及计算机之间的通信方式的差别对用户是隐藏的。同样，用户也看不到分布式系统的内部组织结构。另一重要特性是，用户和应用程序无论在何时何地都能够以一种一致的统一的方式与分布式系统进行交互。分布式系统的扩展或者升级应该是相对比较容易的[1]。这一特性是由于下述原因：分布式系统由独立的计算机组成，但同时隐藏了其中单个计算机在系统里所承担任务的细节。即使分布式系统中某些部分可能暂时发生故障，但其整体在通常情况下总是保持可用。用户和应用程序不会察觉到那些部分正在进行替换和维修，以及加入了哪些新的部分来为更多的用户和应用程序提供服务。为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“中件层”组织起来，该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的底层之间，如图1.1所示。这样的分布式系统有时又称为中间件（middleware）。图1.1作为中间件组织的分布式系统（请注意，中间件层延伸到了多台机器上）现在我们考察一下分布式系统的几个例子。第一个例子是位于一所大学或者某个公司部门的工作站网络。该系统除了包括每个用户自己的工作站以外，还应该包括机房内的一个处理器池。这些处理器并不分配给特定的用户，而是根据需要进行动态调配，这样的系统可能包含一个单一的文件系统，允许所有的机器通过相同的方法并且使用相同的路径名来访问所有的文件。并且，当用户键入一个命令的时候，系统将寻找执行该命令的最佳位置，也许会在自己的工作站上直接执行该命令，也可能会在别人的一个空闲的工作站上执行，还有可能有机房中某个尚未分配的处理器执行。如果系统整体外观和行为与传统的单处理器分时系统（即多用户系统）相似，那么这个系统就可以看做是分布式系统。第二个例子是某个工作流信息系统，该系统支持对账单的自动的处理。一般情况下，会有来自多个不同部门的人员在不同的地点使用这样的系统。例如，销售部的人员可能遍布在很大的一个区域，甚至全国。可以通过电话网络（或者蜂窝电话）连接到系统的膝上型计算机下达订单。收到的订单由系统自动传送到计划部，接着新的内部调货订单就会送达仓储部，同时有财务部处理账单。该系统自动将订单传送到相关人员手中。用户根本就看不到系统中订单处理的物理流程；对于用户来说，这些订单像是由一个集中式数据库处理的一样。最后一个例子是万维网。它提供了一种简单、一致并且统一的分布式文档模型。要查看某个文档，用户只须激活一个引用（即链接），文档就会显示在屏幕上。理论上（但目前在实际中并不是这样）并不需要知道该文档来自于哪个服务器，更用不着关心服务器所在的位置。要发布一个文档也很简单：只需要赋予它一个唯一的URL名，让该URL指向包含文档内容的本地文件即可。如果万维网向用户呈现的是一个庞大的集中式文档系统，也可以认为它是一个分布式系统。不幸的是，我们现在还无法做到这一点。例如，用户明白这样一个事实：文档位于不同的地点，并由不同的服务器处理。1.2目标分布式系统必须能够让用户方便地与资源连接；必须隐藏资源在一个网络分布这样一个事实；必须是开放的；必须是可扩展的。1.2.1让用户连接到资源分布式系统最主要目标是使用户能够方便地访问远程资源，并且以一种受控的方式与其他用户共享这些资源。资源几乎可以是任何东西，其典型例子包括打印机、计算机、存储设备、数据、文件、Web页以及网络，但这些只是资源中的一小部分。有很多理由要求资源共享，一个显而易见的理由是降低经济成本。例如，让若干用户共享一台打印机比为每一位用户购买并维护一台打印机要划算的多。基于同样的原因，共享超级计算机和高性能存储系统这样昂贵资源也是很有意义的。1.2.2透明性如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统，这样的分布式系统就称为透明的。(1)分布式系统的透明性透明性的概念可以运用到分布式系统中的各个方面，如图1.2所示。透明性说明访问隐藏数据表示形式的不同以及资源访问方式的不同重定位隐藏资源是否在使用过程中移动到另一个位置并发隐藏资源是否由若干相互竞争的用户共享故障隐藏资源的故障和恢复持久性隐藏资源（软件）位于内存中还是硬盘中图1.2分布式系统中不同形式的透明性（ISO1995）访问透明性指对不同数据表示形式以及资源访问方式的隐藏。例如，要将一个整型数从基于Intel处理器的工作站传输到一台SunSPARC机器上，我们必须考虑到Intel处理器传输数据字节的顺序是littleendian格式（先传输数据的高位字节），而SPARC处理器却使用bigendian（先传输数据的低位字节）。在数据表示形式上还会存在其他的差别。例如，分布式系统中的多个计算机系统可能运行的是不同的操作系统，这些操作系统的文件命名方式不同。文件命名方式的差异以及由此引发的文件操作方式的差异都应该对用户和应用程序隐藏起来。(2)透明度虽然对于任何分布式系统来说，实现分布透明性通常是可取的，但是在某些情况下，把所有分布情况都对用户屏蔽得严严实实并不见得有好处。这样的一个例子是，如果您订阅了一份电子报刊，并且要求它在每天本地时间早上7点之前就寄到邮箱里，而您现在呆在地球另一端的不同时区，您就会发现“早报”不在是早上寄到的。另外，还必须在高度的透明性和系统性能之间进行权衡，得出折衷方案。例如，许多Internet应用程序会不断尝试连接到某台服务器，多次失败后才最终放弃。这种在用户转向另一台服务器之前竭力隐藏服务器短暂故障的企图会导致整个系统变慢。在这种情况下，最好还是让用户早一些放弃，或者至少允许用户取消这种连接的尝试。在设计并实现分布式系统时，把实现分布的透明性作为目标是正确的，但是应该将它和其他方面的问题（比如性能）结合起来考虑。1.2.3开放性开放的分布式系统的另一个重要目标是，它必须是灵活的，要能够方便的把由不同开发人员开发的不同组件组合成整个系统。同时，还必须能够方便地添加新组件、替换现有的组件，而不会对那些无须改动的组件造成影响。换句话说，开放的分布式系统应该是可扩充的。例如，在灵活的系统中，要添加可运行于另一个操作系统上的部件应该是比较容易的，即使要更换整个文件系统也不应该太对困难。但根据我们从日常实践中得到的经验，要实现灵活性是比较困难的。1.2.4可扩展性通过互联网，世界范围的互联正在变得像给世界任何地方的人寄张明信片一样平常。考虑到这种情况，分布式系统开发者都将可扩展性作为最重要的实际目标之一。系统的可扩展性至少可以通过三个方面来度量（Neuman1994）。首先，系统要能在规模上扩展，也就是说可以方便地把更多的用户和资源加入到系统中去。其次，如果系统中的用户和资源可以相隔极为遥远，这种系统就称为地域上可扩展的系统。最后，系统在管理上是可扩展的，也就是说，即使该分布式系统跨越多个独立的管理机构，仍然可以方便地对其进行管理。不幸的是，在以上这三个方面或其中某一两个方面可扩展的系统常常在扩展之后表现出性能的下降。1.3分布式文件系统鉴于共享数据是分布式系统的基础，分布式文件系统是构成许多分布式应用程序的基础就不足为奇了。分布式文件系统允许多个进程在长时期内以一种安全、可靠的方式共享数据。所以，它们已被用作分布式系统和分布式应用程序的基础层。在本节中，我们把分布式文件系统看作通用分布式系统的模型[2]。我们将详细讨论两个不同的分布式文件系统。第一个实例是SUNNFS(networkfilesystem,网络文件系统)，它已经得到了广泛应用，现在正逐渐向基于Internet的大规模文件系统的方向发展。NFS的大多数实现基于其版本3规范。另一个完全不同的分布式文件系统是Coda。Coda源于AFS（Andrew文件系统），AFS是一个在设计是就考虑到可扩展性的大规模系统。Coda与许多其他文件系统的区别在于它在面对网络分区时支持连续操作。特别是那些故意时常断开网络连接的移动用户（比如，使用膝上型计算机的人们）会从中获益。我们也将简要讲述其他三个系统。Plan9是一个将所有资源都视为文件的分布式系统。从这种意义上来说，它可以被视为一个基于文件的分布式系统。我们将讲述的另一个系统是xFS，其与众不同之处在于它没有服务器，而是让客户实现文件系统。最后，我们会介绍SFS，该系统强调可扩展的安全性[3]。1.3.1SUN网络文件系统我们以SUN微系统的网络文件系统（networkfilesystem），即通常所说的NFS，开始讨论分布式文件系统。NFS最初是Sun为在它的基于UNIX的工作站上的使用而开发的，但是NFS已在许多其他系统中实现。NFS的基本思想是每台文件服务器提供它的本地文件系统的标准化视图。也就是说，它不关心如何实现本地文件系统，每台NFS服务器支持相同的模型。这个模型带有一个通信协议，该协议允许客户访问存储在一台服务器上的文件。这种方法允许大量异构进程共享一个公共的文件系统，其中的进程可能运行于不同的操作系统和机器上。(1)NFS概述与其说NFS是一个真正的文件系统，不如说它是共同为客户提供分布式文件系统模型的协议的集合。NFS协议是以不同的实现之间应该易于进行互操作为目的而设计的。因此，NFS可以运行于大量异构计算机之上。(2)NFS体系结构NFS底层的模型是远程文件服务的模型。这个模型为客户提供对远程服务器所管理的文件系统的透明访问。但是，客户通常不知道文件的实际位置，相反，NFS为客户提供访问此文件系统的接口，此接口类似于传统本地文件系统所提供的接口。也就是说，客户仅被提供包含多种文件操作的接口，而服务器负责实现这些操作。因此，这一模型也被称为远程访问模型（remoteaccessmodel），如图服务器文件位于服务器上来自客户的访问远程文件的请求服务器文件位于服务器上来自客户的访问远程文件的请求客户文件位于服务器上文件位于服务器上3.当客户程序被执行后，文件返回服务器旧文件3.当客户程序被执行后，文件返回服务器旧文件新文件客户服务器1.文件移动到客户2.在客户上执行访问1.3.1（a）上载/下载模型与之相对照，在上载、下载模型（upload/downloadmodel）中，客户从服务器下载文件后，在本地访问该文件，如图1.3.1（a）所示。客户完成对文件的访问后，再将该文件上载回服务器，以便其他客户使用该文件。当客户下载一个完整的文件，修改该文件，然后将其放回服务器时，可以使用Internet的FTP服务。尽管NFS基于UNIX的版本占主流地位，但是NFS已开发了多种版本以用于许多不同的操作系统。实际上，对所有现代UNIX系统而言，NFS通常按照图1.3.1（b）所示的层次体系结构实现。图1.3.1（b）(3)文件系统模型NFS版本四支持硬链接和符号链接。文件具有文件名，但是访问它们是通过一种类似UNIX的文件句柄（filehandle）实现的，为访问一个文件，客户必须现在命名服务器中搜索该文件的文件名，然后获得该文件关联的文件句柄。另外，每个文件有许多属性，这些属性是可以查询和修改的。下表列出了NFS支持的通用文件操作。操作描述create创建一个非常规文件link创建一个文件的硬链接rename更改文件名remove从文件系统删除一个文件open打开一个文件close关闭一个文件lookup根据文件名搜索文件readdir读取一个目录下的项目setattr设置文件的一个或多个属性值read读取文件中的数据write向文件写入数据表1.3.1（c）1.3.2不同分布式文件系统对比该表总结了5种不同分布式文件系统的各个要点：要点NFSCodaPlan9xFSSPF设计目标访问透明性高可用性统一性无服务器系统可扩展的安全性访问模型远程上载/下载远程基于日志远程通信RPCRPC特殊方法活动消息RPC客户进程瘦/胖胖瘦胖中等服务器组无有无有无装入粒度目录文件系统文件系统文件系统目录名称空间每个客户全局每个进程全局全局文件ID范围文件服务器全局服务器全局文件系统共享语义会话事务处理UNIXUNIXN/S缓存单元文件文件文件块N/S高速缓存一致性回写式回写式直写式回写式回写式复制最低限度ROWA无带区划分无容错可靠的通信复制与缓存可靠的通信带区划分可靠地通信恢复基于客户重新合成N/S检查点和记录日志N/S安全通道现存的机制重新合成N/S检查点和记录日志自证明访问控制许多操作目录操作基于UNIX基于UNIX基于NFS表1.3.2注：N/S表示无特殊规定2.P2P技术2.1P2P技术2.1.1P2P的背景与发展对等网络p2p（peertopeer），维基百科是这样定义的：P2P技术是一种网络新技术，依赖网络中参与者的计算能力和带宽，而不是把依赖都聚集在较少的几台服务器上。在P2P网络环境中，成千上万台彼此连接的计算机都处于平等的地位，整个网络一般来说不会依赖于专门的中央服务器。网络中的每一台计算机既能充当网络服务的请求者，又能对其他计算机的请求做出响应，提供资源或其他服务[8]。P2p技术的发展可以追溯到上世纪九十年代，由一个叫肖恩的大一学生编写的叫Napster的程序，这个程序能搜索音乐文件并提供检索功能。随着互联网的发展，尤其是上世纪90年代后期，计算机硬件的性能有了突飞猛进的发展，而且网络带宽等基础设施也大幅的改善，人们开始感到有必要而且能够直接控制、修改和共享资源。随后开始把服务器软件也放在单独的PC上，而且在PC与PC之间直接进行通信，这就导致了P2P技术的复兴。P2P技术主要指由硬件形成网络连接后的信息控制技术，是应用层上的一种逻辑网络，主要的代表就是在基于P2P网络协议的各种客户端软件。由上文可知，P2P网络是属于叠加在底层通信网络基础之上的逻辑网络，是应用层的程序，也是一个分布式、具有互操作性的自组织系统。P2P网络面临的最大的挑战之一就是如何在没有集中式服务器的模式下维护网络拓扑结构，以及实现资源检索等服务。在P2P网络中，如何对资源进行准确的定位是最重要的问题。现阶段P2P搜索技术的研究可以从两个方面来进行，第一个方面是从P2P搜索算法入手来进行研究，第二个方面是从P2P的体系架构入手进行研究。P2P搜索算法包括：Chord算法，Pastry算法，Tapestry算法，CAN算法和Kademlia算法等等。P2P体系架构方面包括：集中式系统，分布式系统，混合式系统。2.1.2.p2p技术的分类拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系[9]，节点之间的拓扑结构一直是确定系统类型的重要依据。P2P系统主要采用非集中式的拓扑结构，根据结构关系可以将P2P系统细分为叫种结构的拓扑形式：中心化拓扑网络、全分布式非结构化拓扑网络、全分布式结构化拓扑网络以及半分布式拓扑网络。（1）中心化拓扑网络中心化拓扑网络最大的优点是维护简单，发现效率高。由于资源的发现依赖中心化的目录系统，发现算法灵活、高效并能够实现复杂查询。最大的问题与传统c/s结构类似，容易造成单点故障，访问的“热点”现象和法律等相关问题，这是第一代p2p网络采用的结构模式，经典案例就是著名的MP3共享软件Napster。在Napster模型中，一群高性能的中央服务器保存着网络中所有活动对等计算机共享资源的目录信息。当需要查询某个文件时，对等机会向一台中央服务器发出文件查询请求。中央服务器进行相应的检索和查询后，会返回符合查询要求的对等机地址信息列表。查询发起对等机接收到应答后，会根据网络流量和延迟等信息进行选择和合适的对等机建立连接，并开始文件传输。Napster的工作原理如图2.1.2（1）所示。图2.1.2（1）Napster网络的拓扑结构采用Napster结构的中心化拓扑网络结构也存在一些问题，主要表现为：中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性较低；(2)随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本过高；（3）中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被攻击为非纯粹意义上的P2P网络模型。综合上述优缺点，对小型网络而言，中心化网络模型在管理和控制方面占一定优势。但鉴于其存在的种种缺陷，该模型并不适合大型的网络应用。（2）全分布式非结构化的P2P网络全分布式非结构化刚络采用了随机图的组织方式，结点度数服从Power—law”规律，从而能够较快发现目的结点，而对网络的动态变化体现了较好的容错能力，因此具有较好的可用性，同时可以支持复杂查询，如带有规则表达式的多关键词查询，模糊查询等[10]，采用这种拓扑结构最典型的案例便是Gnutella，如图2.1.2（2）所示。图2.1.2（2）Gnutella网络的拓扑结构Gnutella是一个P2P文件共享系统，它和Napster最大的区别在于Gnutella是纯粹的P2P系统，不存在集中式的目录服务器，并且文件的发布和网络拓扑松散相关。Gnutella网络具有以下特点：不存在中央服务器，完全依赖于网络中的交互式个人成员而独立存在；(2)在浚网络模型中，每一个联网计算机在功能上都是对等的，既是客户机同时又是服务器，所以被称为对等机。发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目前对此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性能。（3）全分布式结构化的P2P网络在这类网络中，不存在中心化的目录服务器，因此属于全分布式的P2P网络。这种类型的网络结构，采用分布式散列表(DistributedHashTable，简称DHT)的全分布式结构化拓扑网络。分布式散列表实际上是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。DHT结构能够自适应结点的动态加入与退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。最经典的案例是Tapestry、Chord、CAN和Pastry[4]。这里主要介绍一下具有代表性的chord网络模型，如图2.1.2(3)。该网络模型诞生于美国的麻省理工学院，它的目标是提供适合于P2P环境的分布式资源发现服务，它通过使用DHT技术使得发现指定对象只需要维护O(109N)长度的路由表。在DHT技术中，网络节点按照一定的方式分配一个唯一节点标识符(Node，ID)，资源对象通过散列运算产生一个唯一的资源标识符(Obiect，ID)，且该资源将存储在节点ID与之相等或者相近的节点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，Chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字(Key)映射到对应的节点(Node)。图2.1.2（3）Chord网络的拓扑结构DHT结构最大的问题是DHT的维护机制较为复杂，尤其是结点频繁加入退出造成的网络波动会极大增加DHT的维护代价。DHT所面临的另外一个问题是DHT仅支持精确关键词匹配查询，无法支持内容、语义等复杂查询。（4）半分布式的P2P网络半分布式结构吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能较高(处理、存储、带宽等方面性能)的节点作为超级节点，在各个超级节点上存储了系统中其他部分节点的信息，发现算法仅在超级节点之间转发，超级节点再将查询请求转发给适当的叶子结点。半分布式结构也是一个层次式结构，超级节点之问构成一个高速转发层，超级节点和所负责的普通节点构成若干层次。最典型的案例就是KaZaa网络结构如图2.1.2（4）所示。图2.1.2（4）Kazza网络的拓扑结构KaZaa结合了Napster和Gnutella共同的优点。从结构上来说，它使用了Gnutella的全分布式的结构，这样可以使系统更好的扩展，因为它无需中央服务器存储文件名,它是自动的把性能好的机器作为超级节点，它存储着离它最近的叶子节点的文件信息，这些超级节点再连通起来形成一个重叠网。由于超级节点的索引功能，使搜索效率大大提高。半分布式结构的优点是性能、可扩展展性较好，较容易管理，但对超级节点依赖性大，易于受到攻击，容错性也受到影响。比较标准/拓扑结构中心化拓扑全分布式非结构化拓扑全分布式结构化拓扑半分布式拓扑可扩展性差差好中可靠性差好好中可维护性最好最好好中发现算法效率最好中高中复杂查询支持支持不支持支持表2.1.2四种网络拓扑结构的性能比较2.1.3．p2p的特性与其它网络相比，p2p具有以下特性：（1）非中心性网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。(2)可扩展性P2P的分散化带来的一个直接的好处就是提升了系统的可扩展性。在P2P网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。(3)匿名性P2P中一个很重要的特性就是匿名性。匿名性的一个重要日标就是让用户在使用系统的时候不必受各种法律问题的约束，进一步的目标就是保证审查机构无法对数字内容进行审查。(4)自组织性在P2P系统中，由于可扩展性、支持容错、资源不断地连接断开以及拥有的开销等原因，使系统具有一定的自组织特性是必要的。(5)健壮性P2P架构天生具有耐攻击、高容错的优点。由于服务是分散在各个节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。而且P2P模型⋯般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。(6)高性能性性能优势是P2P被广泛关注的一个重要原因。采用P2P架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。2.2P2P搜索技术P2P搜索技术也依据P2P网络的体系结构而异，不同的体系结构有着完全不同的搜索算法。在此我们主要讨论非结构化P2P网络和结构化P2P网络的搜索技术。2.2.1非结构化搜索技术非结构化分布式P2P网络完全脱离了中心服务器，网络中每一个节点的地位都是平等的，每一个节点既是客户端又是服务器，而且它们与相邻的节点具有相同的能力，以Gnutella为典型代表的一种网络结构。非结构化的P2P网络路由技术可以分为两类：盲目搜索和利用网络中资源的分布信息进行搜索。盲目搜索是从任意一个节点出发定位目标节点，而不利用网络中资源的分布信息进行搜索，特点是网络中的每一个节点记录以前接收过的请求和响答，当开始搜索的时候可以根据记录对后续路由做出启发。非结构化P2P网络搜索技术中最典型的便是泛洪算法。泛洪算法是最早出现在非结构化的P2P网络搜索算法中，它的特点是搜索时对全网的节点进行遍历和搜索。在泛洪搜索技术中，消息像洪水一样在网络中的各个节点之间流动，所以被称作泛洪算法。泛洪搜索技术具体方法如下所示：在整个P2P网络中，某个节点要搜索某个资源时，首先它向相邻的节点发送查询消息。如果某个节点拥有这个资源，就向查询节点返回一个消息，告诉查询节点自己有这个资源，否则相邻节点就再次把查询消息转发给自己再相邻的节点。在整个查询过程中，因为怕消息发出后在一个循环的区域里传送，所以节点通过查询消息的TTL（TimeToLive，生存时间）值或者跳转数来判断查询消息是否过期，当TTL或者跳转数超过一定的数值时，接收到消息的端就舍弃该消息。泛洪搜索算法比较简单，实现起来也相对容易，但它在每次搜索的时候都进行全网的遍历，这样便给网络带来了很大负载，而且搜索效率也不高，算法的时间复杂率是O(N)，整个网络扩展性也极差，安全性也不好。2.2.2基于DHT的搜索技术分布式结构化P2P网络搜索主要采用分布式哈希表算法来组织P2P网络中的节点。首先介绍一下哈希的概念：因为DHT算法是基于一致性哈希函数（ConsistentHashing）的一种资源定位及搜索算法。一致性哈希使用的是如MD5、SHA-1等哈希函数。我们先简单介绍一下哈希函数的概念：哈希函数，就是把任意长度的输入（又叫做预映射，pre-image），通过具体的哈希算法，转换成固定长度的输出，该输出就是哈希值。这种转换是一种压缩映射，也就是，哈希值的空间通常远远小于输入的空间，不同的输入可能会哈希出相同的输出，而不可能从哈希值来唯一的确定输入值，也就是哈希函数是不可逆的。哈希函数具备以下性质：(1）可以作用于一个任意长度的数据块。(2）能产生一个固定长度的输出。(3）对任何给定的x，Hash(x)计算相对容易，用硬件或者软件都能实现。(4）对任何给定的码h，寻找x满足Hash(x)=h在计算上是不可行的(哈希函数的单向性)。(5）对任何给定的数据块，寻找不等于x的y，使得Hash(y)=Hash(x)在计算上是不可行的。有时将此称为弱抗冲突（weakcollisionresistance）。(6）寻找任何的(x,y)对满足Hash(x)=Hash(y)在计算上是不可行的，有时将此称为强抗冲突（strongcollisionresistance）。基于以上的性质我们可以得到，哈希函数可以保证数据的唯一性。比较著名并且常用的哈希算法有MD5和SHA-1算法等等。这两者可以说是目前应用最为广泛的哈希算法，而它们都是以MD4为基础设计的。下面将详细的介绍DHT算法，它是一种分布式的路由算法，在不需要服务器的情况下，每台机器只负责一小段范围的路由，并负责存储一小部分的数据，从而实现整个DHT网络的查找和存储。在实际的系统中，P2P网络的逻辑地址通常是由哈希函数得到的，每台机器都将保存其中的一部分哈希表用来路由，所以分布式结构化P2P网络通常也称为DHT网络。在分布式结构化P2P网络中，网络中的每一台计算机称为一个节点，每一个节点有一个唯一的值用来标识该节点，对于一个节点来说典型的表示就是它的IP地址和端口号。在P2P网络中，每一个节点和每一个资源都需要一个标识符，标识符必须是独一无二的一组数字，节点的标识符可以通过对一个节点的IP地址和端口号作为预映射进行哈希计算来获得；资源将其一组关键字作为预映射进行哈希，其运算的结果便作为该资源的标识符，也由此标识符决定此关键字对应的那条信息由哪个节点负责储存。用户搜索的时候，用同样的算法计算出资源的关键字的哈希值，然后根据哈希值知道该资源对应信息的存储的位置，再根据节点的DHT迭代的得到相应节点的IP和端口号，最后并与之进行通讯，从而能够迅速定位资源的位置。例如节点的标识符我们称为NodeID。资源的标识符也是一个独一无二的标识符，我们称之为KeyID。NodeID和KeyID两者本质上是一样的类型，用有可能产生冲突的哈希函数计算出来有可能相同，将会对系统产生严重的影响，所以在哈希算法的选择上有一定的要求。在基于DHT的P2P网络中，资源的关键字通过哈希计算得到要查找的key值，P2P系统中的每个节点都负责管理一部分哈希空间，它负责保存某段范围的key值。每个节点存储一张<key,value>表，就是DHT，key在这里对应着KeyID，value在这里对应着所在的节点的通讯信息，可以是IP、端口号等信息。当开始搜索某个资源的时候，先用哈希函数计算出需要搜索资源的key值，然后通过自身的DHT，在P2P网络中找到与之匹配的key值存储的节点，返回这个节点的标识符给需要查询的节点的通讯信息，通常这个过程也是一个迭代的过程，大多数情况下，需要在网络中迭代很多次才能找到相应的节点，最后与之建立连接，取得资源。目前使用的一些互联网上的共享资源的软件，一般会查找到很多节点，再用一定的策略从各个节点同时下载。DHT就是为了解决在非结构化分布式网络中查找资源的盲目性的问题而引入的。DHT的主要思想：1.将内容索引抽象为<K,V>对:K是内容关键字的Hash摘要K=Hash(key)V是存放内容的实际位置，例如节点IP地址等2.所有的<K,V>对组成一张大的Hash表，因此该表存储了所有内容的信息3.每个节点都随机生成一个标识(ID)，把Hash表分割成许多小块，按特定规则(即K和节点ID之间的映射关系)分布到网络中去，节点按这个规则在应用层上形成一个结构化的重叠网络4.给定查询内容的K值，可以根据K和节点ID之间的映射关系在重叠网络上找到相应的V值，从而获得存储文件的节点IP地址内容内容内容关键字key内容存储位置等信息value内容索引K=Hash(key)提取Hash表电影剑雨电影、剑雨/剑雨.avi内容索引K=hash(电影,剑雨)V=/剑雨.avi图2.2.2（a）kvkva.Hash表b.分布式Hash表规则?KVN1N48N16N32N8KVKVKVKVChord、CAN、Tapestry、Pastry在许多情况下,节点ID为节点IP地址的Hash摘要图2.2.2（b）插入插入(K1,V1)KVKVKVKVKVKVKVKVKVKVKV(K1,V1)查询(K1)ABK1=Hash(xyz.mp3)V1=xyz.mp3C图2.2.2（c）2.3ChordChord算法是由麻省理工学院研究开发的一种DHT算法，基本的原理是根据节点的IP地址、端口号和资源的关键字通过哈希函数计算得到全局唯一的标识符，将它们映射到一个环上去。为了保证标识符的唯一性，它采用一致性哈希函数来对资源关键字和节点进行哈希运算。哈希函数通常是采用SHA-1算法，生成160位的标识符[11]。每一个160位的标识符按大小顺序链接在一起，可以形成一个环。资源关键字通过哈希算法计算出的key值存储的规则是：每一个节点存储的key值范围从自己的前驱节点的标识符到自己标识符的左开右闭区间。检索资源的时候会根据一定的查找方法来定位某一个key值存放的节点。这个方法的基础就是将要介绍的finger表。2.3.1finger表在Chord算法，节点之前的查找是根据所谓的finger表来实现的，finger表也就是Chord算法的路由表。每个节点都存储并维护着自己的一张finger表[12]，查找的时候根据finger表相应的表项进行跳转。而finger表的结构如图所示为了简单起见，此时我们假设哈希空间是2的6次幂，一共是64个值，而在10个节点通过哈希函数分别映射成1，8，14，21，24，32，38，42，48和51，节点8的前驱节点是节点1，而后继节点是节点24。finger表的大小是由哈希空间的大小决定的，如果哈希空间的大小是2的m次幂，那么finger表的大小即为m，也就是说一共有finger表上一共有m个表项，分别记录的是节点的标识符加2i（i=0,2,…m–1）mod2m的和的值的后继节点地址。如图2-5所示，节点8的finger表就按此规则记录了与其节点标识符相差1，2，4，8，16和32的标识符的后继节点的位置。图2.3.1Chord环和finger表2.3.2Chord算法的查找过程Chord算法资源查找过程如图2.3.2(1)所示[13]，下面详细介绍下算法各步骤的具体的处理过程：(1）首先将要查找的资源关键字用SHA-1哈希函数计算出一个key值；(2）查看该key值是否存在本节点上，判断的条件是，该key值大于节点的前驱节点的标识符，而小于等于该节点的标识符；(3）如果是存在本节点，则将本节果返回结果给查找节点；(4）如果不存在本节点，则查询finger表，返回的下一跳地址是其表项标识符值是最后一个小于等于key值的后继节点，如果是finger表的第一项key值就大，则返回finger表的最后一个表项标识符的后继节点地址作为下一跳地址；(5）发送查找请求给下一跳地址，重复过程(2）到(5），直到进入过程(3）则结束。由此可见，Chord算法的查找过程是一个递归的过程，递归的结束条件是查找到该资源关键字的key值所在的节点。图2.3.2查找过程Hash节点IP地址－>m位节点ID(表示为NID)Hash内容关键字－>m位K(表示为KID)节点按ID从小到大顺序排列在一个逻辑环上<K,V>存储在后继节点上，Successor(K)：从K开始顺时针方向距离K最近的节点Hash节点IP地址－>m位节点ID(表示为NID)Hash内容关键字－>m位K(表示为KID)节点按ID从小到大顺序排列在一个逻辑环上<K,V>存储在后继节点上Successor(K)：从K开始顺时针方向距离K最近的节点下面以查找K54为例，过程如下：（a）(b) (c)(d)3基于DHT的Chord算法的改进3.1影响搜索算法性能的因素P2P搜索算法与P2P网络拓扑结构有着密切的关系[7]，针对不同的P2P网络拓扑结构，有着不同的搜索算法。对于集中式的网络拓扑结构，如图3.1(a)，由于存在中央服务器，整个系统对中央服务器的依赖度很高，一旦中央服务器受到黑客攻击出问题，整个网络系统将立即崩溃。图3.1（a）集中式网络拓扑结构对于非结构化的P2P网络拓扑结构，大多采用的是泛洪搜索算法。这种搜索算法虽然搜索范围很广，但是因为网络拓扑结构的原因，在搜索过程中会产生大量的消息冗余，另外搜索广度也不易控制，造成了资源的浪费。具体搜索过程如图3.1(b)所示。图3.1（b）消息冗余图示如图3—2，当网络中的节点A要在j网络中搜索目标对象资源的时候，它首先会向自己的邻居节点B和c发送搜索消息，当B和c接收到这个消息后，同时又会向自己的邻居节点D、E以及E、F发送广播消息，在这样一个非结构化网络拓扑中，搜索过程中就会产生大量的消息冗余，如节点B在收到搜索请求后，同样也会向节点c发送消息(冗余搜索消息为图中虚线所示)，严重影响搜索效率，同时也造成了资源的浪费。对于结构化P2P网络搜索算法，比如传统的Chord算法。由于整个网络拓扑成一个环形状，当要在该网络中搜索目标对象资源时，搜索方向足按照顺时针的方向进行搜索的，如要从N8这个节点开始搜索K54这个资源，那么搜索过程中所遍历的网络节点将会很多，虽然也能搜索到需要的资源，但是效率不高。综上所述，本文发现影响P2P搜索算法性能主要有以下两个因素：(1)P2P网络拓扑结构，网络的稳定性，包括节点的加入与退出。(2)搜索消息在网络中的路由寻址策略，即搜索算法。3.2小世界现象对P2P搜索技术的启示所谓小世界现象，或称“六度分离(sixdegreesofseparation)”，是社会网络中的基本问题，即每个人只需要很少的中间人(平均6个)就可以和全世界的人建立起联系。在这一理沦中，每个人可看作是图的节点[14]，并有大量路径连接着他们，相连接的节点表示互相认识的人。这是一个涉及社会学，数学和计算科学问题的多学科交叉问题。该问题源于社会心理学家StanleyMilgram上世纪60年代做的实验：“追踪美国社交网络中的最短路径”。他要求每个参与者寄信给一个住在波士顿附近的“目标人物”，规定每个参与者只能转发给一个他们认识的人，Mil肿m发现完整的链平均长度为6个人，如图所示3.2(a)图3.2（a）社会网络中的小世界现象Milgmm的研究有两大发现，社交网络中短路径的存在仅是其一，其二是社会中的人们，他们仅知道自己认识的人，就能很快地把信件转发到任何远方目标。用计算术语来讲，就是关于路由算法(routingalgorithm)的效率问题，这一算法可完全依靠本地信息来找到到达目的地的有效路径。这一分散路由方案也有力的揭示了计算机网络中一些潜在的惊人特点。最近，应用数学家DuncanWatts和SteveStrogatz提出利用小世界性质来研究网络：一个高度聚集的包含了“局部连接”节点的子网，连同一些随机的有助于产生短路径的长距离无规连接(randomlong—rangeshortcuts)。除了对社会、技术和生物网络的唯象研究(empiricalstudies)，Watts和Strogatz还考虑了以下简单模型系统:以一个d维格点网络开始(d-dimensionallatticenetwork)，给每个节点添加一些少量随机长距离连接，把它们连接到随机选择的一些终点上。这样构建的网络将会有局域聚集现象及短的路径，如图3.2(b)(c)所示。3.2（b）单个随机连接的二维节点网络3.2（c）多个随机连接的二维节点网络然而，更进一步研究，发现对Watts-Strogatz模型做一些微小改动就会使搜索更有效：不是均匀地加入长距离连接，而是按某种分布率在网络结点问添加连接，即让在d维空间中节点连接的几率随距离的增大以d次幂衰减。实际上，随距离的d次幂几率衰减统一了所有距离的“尺度”——与一个节点距离为1—10节点构成连接的数目大致和它与距离为10-100，100一1000等的节点构成连接的数目一样，如图3.2(d)图3.2(d)按d次幂衰减带有多个不同距离的随机连接生成的节点在P2P系统中，这一利用连接几率随距离衰减的连接方式能够建立搜索得到了证明。在P2P中，文件内容需要通过一个节点以分散方式检索另一节点。换句话说，结点执行搜索协议时就像是在参与Milgram的实验一样。通过研究小世界现象的规律，可以得出两个结论：(1)幂规律分布指出，在实际网络中，有少数节点拥有较高的“度”，而多数节点的“度”较低。“度”代表节点同其它节点的联系程度。因此，通过“度”较高的节点找到待查找信息的概率也较高；(2)小世界模型特征指出，网络拓扑具有高聚集度和短链的特性。在以小世界特征为基础的网络模型中，节点按照节点的聚集度被划分为若干簇，在每个簇中至少存在一个度最高的节点为中心节点。大量的研究表明，P2P网络符合小世界的特征，这意味着网络中存在大量的高连通节点，部分节点之间存在“短链”现象。图3.2(e)P2P网络的小世界现象因此，对P2P搜索算法的研究[15]，从如何缩短路径长度的问题变成了如何找到这些“短链”的问题。尤其是在DHT搜索算法中，如何产生和找到“短链”是搜索算法设计的一个新思路，小世界模型的引入对P2P路由算法产生了重大的影响。针对以上分析，有必要对现有的分布式P2P搜索算法进行改进，本文提出了一种分布式结构化的P2P网络拓扑，且对传统的Chord搜索算法进行了扩展改进，并把这种分布式P2P搜索算法命名为Nchord搜索算法。3.3NChord搜索算法本节提出了一种分布式结构化P2P搜索算法，这种搜索算法首先对现有的P2P网络拓扑结构进行了改造，然后在现有的传统Chord搜索算法的基础上进行了扩充与改进，并提出了一种算法，命名为NChord搜索算法。3.3.1Nchord算法网络拓扑结构在5．1节中，本文得出了一个结论：影响P2P搜索算法效率的主要因素包括P2P的网络拓扑结构。中心化网络拓扑结构以及全分布式网络拓扑结构都有它们固有的缺陷，前者对中心化服务器的依赖度非常大，后者在泛洪搜索过程中要产生大量的冗余消息，搜索量很大。因此，本节针对P2P网络的特点，结合小世界现象规律，在传统的Chord搜索模型基础上提出了一种NChord网络模型，如图3.3.1(a)所示。图3.3.1(a)Nchord网络拓扑结构模型该网络拓扑结构由内外两个环形网络组成，采用分布式散列表(DistributedHashTable，简称DHT)的分布式网络结构。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。DHT的结点既是动态的，结点数量也是巨大的，因此非中心化和原子自组织成为这种网络的重要特点由小世界现象规律可知，P2P网络中的每个节点都表现出了某些可以被捕捉到的兴趣，而兴趣相近的节点保存的内容和提交的查询也呈现出一定的相关性。通过挖掘每个节点的兴趣，将节点按照它们所表现出的相关性组成网络，使得相关性高的节点在网络中比较接近，这样对提高查询检索效率是非常有效的。网络中的各个节点按照活跃程度分布在不同的网络环中，外环上的节点属于普通节点，内环上的节点属于超级节点，内环中的节点都是系统中比较活跃的节点，表现为经常在线，而且所存储的数据对象都是当前网络中很流行的，热度较高的资源。不管是普通节点还是超级节点，节点在加入该网络的时候，根据特定的散列函数计算后，得到一个唯一的键值，散列函数可以做到负载平衡，使网络中节点的分稚达到均衡，各节点通过该键值知道自己所在的区域。如图3.7中的1，2，3，4，5代表各个区号，即各个超级节点在内环网中的具体位置。每个节点都维护着自己的一张路由信息表，该表中保存了节点的一些相关信息，包括节点存储的资源，资源的流行性以及热门度。搜索资源的时候，各节点按照自己的这张路由索引表进行消息的路由。从上图可以看出，该网络拓扑结构不同于中心化的网络拓扑结构，因此在单个重要节点受攻击或是退出的时候，对整个网络来说影响是非常有限的；比较全分布式的P2P网络结构，由于Nchord网络是环形结构，在搜索资源时，不会像有很多联通路径的三角图或树形图，在广播泛洪过程中会产生大量的冗余消息。3.3.2节点加入时的策略当一个新节点n加入NChord网络时，需要按照以下几个步骤完成工作：(1)初始化本地节点查询表。节点n加入网络时，通过散列函数的计算，得到网络中一个唯一的ID值，根据该lD值，n与内环网络中的某个超级节点n’建立连接。这时，为了初始化n的路由索引表，n将要求超级节点n’为它查找路由索引表中的其它表项：(2)更新网络中其它节点的路由索引表。节点加入网络后，将通知其它节点，让其它节点及时的更新自己的路由索引表。在更新路由索引表的时候，新节点应该参照网络中已有的路由索引表，查看自己是否存储有热门数据对象，按照资源的热门度对索引表进行更新；(3)转移关键字信息。其它节点将所有键值归属于n的关键字(即后继节点是n的关键字)转移到节点n上，更新完成后，节点n将向网络中的其它节点发送新的路由索引表，各邻居节点收到更新消息后，同时也向自己的邻居节点发送新的路由索引表，直至整个系统更新完毕；(4)在更新路由索引表的过程中，如果遇到网络堵塞或是延时，可以选择合适的时机重新更新；(5)如果加入失败，重新选择另一个较近的超级节点n”进行连接，重复上述步骤；(6)节点n完成节点加入流程。3.3.3节点退出时的策略当网络中的一个节点退出Nchord网络时，需要完成以下几个工作：(1)向邻居节点发送消息，告知对方自己将退出系统；(2)邻居节点收到退出消息后，立即更新自己的路由索引表，同时也向自己的邻居节点发送此消息，直至整个系统都已收到该消息，并更新成功；(3)保存自己的路由索引表，当再次进入该网络的时候，可以减少需要维护的路由索引表项目，下次只需要对最新的信息进行更新就可以了；(4)该节点完成退出流程。3.3.4节点失效时的策略当一个节点在加入NChord网络或退出NChord网络时，如果发送更新消息失败，则需要做如下处理：不管是加入还是退出时发送更新消息，节点向网络中自己的邻居节点发送更新消息后，邻居节点如果收到了消息，应该向发送消息的节点发送一个收到确认码。比如节点n向节点nr发送一个更新路由索引表的消息，n如果没有收到n’的确认码，说明可能是发送失败，那么这个时候节点n就应该等待一段时问，重新向n’节点发送更新消息，直到收到n’的确认消息为止；如果n总是没有收到n’的确认消息，说明这个时候n’节点可能已经失效，n节点应该修改自己的路由索引表，向其它节点发送更新请求。3.3.5NChord算法原理在Nchord网络中，网络中的客户端主机称为节点，数据项目称为对象。名字空间指系统的一个名字域，在这个名字域中所有的名字都是独一无二的。名字用来标识节点，一个节点可以有几个名字，每个名字基于不同的尺度。但总的来说，每个节点在一个名字空间中只能有一个名字。对于一个节点来说，典型的名字就是它的互联网IP地址。标识符是指在某个整数名字空间中的独一无二的整数。在Nchord系统中，标识符可以通过对一个节点的名字进行散列来获得，例如标识符Y=hash(IP)。关键字(Kev)是一个对象独一无二的标识符，它可以通过对对象名进行散列来获得，K=hash(0biect)。散列函数可以将Key映射到整数，通常可以在一个更小的集合上获得一个离散分布。散列函数是不可逆的。散列表(DHT)是一个字典，在这个字典中Key通过一个散列函数被映射到一个数组位置上。完美的散列函数是一个没有冲突的散列函数。在基于DHT的NChord系统中，文件被关联到Key(由文件名的散列产生)：系统中的每个节点拥有一部分的散列空间，它负责保存某个范围的Key。在对一个Key进行查询后，系统将返回一个保存具有Key的对象的节点标识符(如IP地址)。DHT的功能允许节点基于文件的Key来存入和取出文件。Nchord算法把平时经常在线的而且共享了很多热门的流行性资源的节点作为超级节点，这部分节点位于NChord网络体系结构的内环网中，节点n在加入网络的时候，首先要进行DHT散列函数的计算，得出该节点应该与内环网中的某个活跃的超级节点n’进行连接，如果该活跃节点n’不在线，则新节点n按照顺时针方向与该活跃节点邻近的另一个活跃节点n”进行连接，以此类推，直到与内环网络中一个活跃节点建立连接为止。在搜索查询过程中，如果节点n是位于Nchord外环网络中的普通节点，则首先判断自己要搜索资源的热门度，目标对象是否为热门资源，如果目标对象资源是热门资源，该节点首先向与自己建立了连接的超级(活跃)节点发送查询请求，超级节点查询自己的路由索引表，如果自己或者别的高级节点有要查找的资源，则直接向该超级节点发送查询消息，搜索结束。如果在该超级节点的路由索引表中，没有找到相应的资源，则按照顺时针方向，把查询请求发送给内环网络中的下一个超级节点，由该超级节点继续此查询过程，内环网络中的高级节点都遍历完了，还没有发现要找的目标对象资源，则该查询返回到外环网络中，重新从发起搜索过程的原始节点开始，按照常规的Chord算法在外环网络中查询。若是超级节点发起的查询，则直接在内环网中根据自己的路由索引表进行查询，如果没有发现资源，则返回外环网使用传统的Chord算法查询，否则查询结束。需要注意的是，该网络应该在适当的时候(如访问量较小的时候)向各节点发送路由索引表更新消息(即报告该节点当前活跃的程度，以及哪些是当前流行的资源以通知其它节点更新路由索引表)，备份节点收到该消息后会实时调整路由消息并继续转发该更新消息，根据前述的小世界现象规律可知，经过一段时间之后，系统所有的在线节点都会成功更新其路由索引表内容。这样，每个节点的路由索引表最终都包含有整个分布式系统中当前较为流行的一批数据对象及其所在节点等信息，且该信息是动态更新的。节点加入可以发送更新路由索引表消息也可以不发送(有流行性高的数据对象就发送)，而节点在离开时必须发送离开消息以通知其它节点更新路由信息。3.3.6Nchord搜索算法的步骤Nchord搜索算法主要分为两个步骤：(1)在内环网络中快速查询；(2)在外环网络中采用传统的Chord搜索算法进行查询。搜索流程如图3.3.6所示是是开始搜索是否为超级节点是否为热门资源在外环中搜索与内环超级节点建立连接查找路由表查找路由表是是是开始搜索是否为超级节点是否为热门资源在外环中搜索与内环超级节点建立连接查找路由表查找路由表是是否否找到资源找到资源找到资源找到资源否否顺时针转发消息到下一个超级节点通过传统Chord算法搜索顺时针转发消息到下一个超级节点通过传统Chord算法搜索是否否是是否否是内环遍历完外环遍历完内环遍历完外环遍历完搜索结束搜索结束图3.3.6Nchord搜索算法的步骤3.3.7Nchord算法特点优点具体描述高效性对于查询流行性的热门资源，Nchord系统可以显著的减少查询过程中的路由路径跳数负载平衡Nchord中采用一致性散列算法，保证了网络的平衡性，所有节点以同等的概率分担系统负荷，使内环网与外环网达到负载平衡分布性Nchord是分布式结构化系统，各个接待你即是服务端也是客户端，节点之间平等地完成同样的工作，这使得该系统具有很高的健壮性，可以抵抗Dos攻击可扩展性Nchord系统的开销随着系统规模（节点总数n）的增加而按照O(log(n))的比例增加，因此Nchord可以用于大规模的系统。可用性Nchord系统要求节点根据网络的变化动态地更新路由索引表，因此能够及时地恢复路由关系，使节点查询能可靠地进行。命名的灵活性NChord并未限制查询内容的结构，因此应用层可以灵活地将内容映射到名字空间，而不受底层协议的限制。结论本文主要介绍分布式系统里的资源搜索以及基于DHT的Chord算法目前，并在Chord分布式结构化网络模型的基础上，提出了一种双环结构的网络模型，针对该网络模型，设计了一种按照目标资源流行性热门度进行网络路由的Nchord搜索算法，减少路由跳数和系统开支。致谢在本论文的