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

本科毕业论文论文题目 基于dht的分布式文件系统 目 录摘 要1关键词1abstract1key words21 绪 论21.1分布式系统的定义31.2 目 标51.2.1 让用户连接到资源61.2.2 透明性61.2.3 开放性71.2.4可扩展性81.3 分布式文件系统81.3.1 sun网络文件系统91.3.2不同分布式文件系统对比122 p2p技术132.1 p2p技术132.1.1 p2p的背景与发展132.1.2p2p技术的分类142.1.3p2p的特性202.2 p2p搜索技术212.2.1非结构化搜索技术212.2.2基于dht的搜索技术222.3 chord262.3.1 finger表262.3.2 chord算法的查找过程273 基于dht的chord算法的改进313.1影响搜索算法性能的因素313.2小世界现象对p2p搜索技术的启示323.3 nchord搜索算法363.3.1 nchord算法网络拓扑结构363.3.2节点加入时的策略373.3.3节点退出时的策略383.3.4节点失效时的策略393.3.5 nchord算法原理393.3.6nchord搜索算法的步骤413.3.7nchord算法特点42结论43致谢43参考文献44基于dht的分布式文件系统研究学生姓名：王京 学号：20077101021信阳师范学院华锐学院数计系 计算机科学与技术专业指导教师：杨军 职称：讲师摘 要：随着信息时代的飞速发展，人们日益发现单个计算机的能力很是有限，于是自然而然想到把各个地方的计算机联合起来处理信息，这就是分布式的提出，随即涉及到资源共享的问题，这就是我们研究的分布式文件系统,随着p2p（即peer-to-peer）技术的发展，很好的解决了分布式存储与计算方面的问题，它作为一种全新的互联网技术，将传统的以服务器为中心的互联网应用模式提升为以用户为中心的对等模式。p2p在文件交换，对等计算，协同工作，搜索服务等方面都有着重要的应用。p2p文件交换系统的发展也由最初npaster的完全中心化模型，gnutella的完全非中心化模型，发展到现在的bittorrnet、emul/eedoknye、kzaza等混合模型。随着近年来dht(disrtibuted hash table)技术的不断发展，dht在p2p文件交换系统中扮演着越来越重要的角色，kdamelai作为覆盖网络被广泛使用到p2p文件交换系统中。p2p网络通常使用dht作为其路由表，比较典型的算法有chord、can、kademlia、tapestry、pastry等，这些算法不仅可靠性高，容错性强，而且查找的效率非常高，查找算法的复杂度基本上都是o(logn)，被广泛地应用于各种各样的分布式系统中。本文将比较分析以上各算法的原理和差异，重点分析、研究和改进chord算法，减少路由跳数和系统开支。 关键词：分布式;分布式文件系统;p2p;dht;chordabstract：with the rapid development of information era, people increasingly find a single computer ability is very limited, naturally they tempted to connect with computers in every region to processing information,thus the distributed proposed,but then comes the resource sharing problem,thats the distributed file system here what we are talking about,as the development of p2p(peer-to-peer) technology,the problem of distributed storage and computing is well solved,the technology of p2p(peer-to-peer), as a new internet technology,promoting the traditional centralized server internet application modle to centralized user peer to peer modle.p2p is important in data-exchange,peer-to-peer computing,coordinated working,search service,etc,in p2p file-sharing systems,it is developing from the beginning centralized model napster and decentralized model gnutella to the current mixed modle, such as bittorrent,emule,kazza,etc.as the dht(distrituted hash table) technology develops,it plays a more important role in p2p file-sharing system,kademlia is used widely in p2p file-sharing system as an overlay network. distributed architecture of the network is commonly used to build p2p networks using dht algorithm,forinstance,chord,can,kademlia,tapestry,pastry,etc.these algorithms not only possess high reliability and strong fault tolerance,but also have efficient look up.the complexity of search algorithm is basically o(logn),so they are widely used in a variety of distributed storage systems. this paper study and compare the principles and differences of above dht algorithms,research、analysis and promote the chord algorithm more in-depth.thus decreasing the jump numbers during the process of searching and the cost of system.key words:distributed;distributed file system;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内将少量数据从一台机器传输到另一台机器。如果要传输大量的数据，传输数率可以达到101000mb/s。利用广域网技术可以连接全球范围内数百万台机器，机器间的数据传输速率从64kb/s到若干gb/s不等。 现在，由于有以上这些技术可供使用，因此把若干由大量计算机组成的计算机系统彼此通过高速网络相连接，不但是可行的，而且是很容易实现的。这种系统一般称为计算机网络或分布式系统，以突出其与传统的集中式系统（centralized system，也称为单处理器系统，single processor system）的差异。传统的集中式系统一般由单个计算机及其外围设备构成，也可以包含一些远程终端。1.1分布式系统的定义 已经有很多文献给出了分布式系统的定义，但是不同文献给出的定义彼此不尽相同，而且没有一种令人满意。考虑到本文的目标，我们只给出一个粗略的描述： 分布式系统是若干独立计算机的集合，这些计算机对于用户来说就像是单个相关系统。 这个定义包含了两方面的内容。第一方面是关于硬件的：机器本身是独立的，第二个方面是关于软件的：对用户来说他们就像在与单个系统打交道。这两个方面共同阐明了分布式系统的本质，缺一不可。我们先介绍关于软硬件的一些背景材料，与继续探讨分布式系统的定义相比，把注意力集中在分布式系统的重要特性上可能更好一些。其重要特性之一是，各种计算机之间的差别以及计算机之间的通信方式的差别对用户是隐藏的。同样，用户也看不到分布式系统的内部组织结构。另一重要特性是，用户和应用程序无论在何时何地都能够以一种一致的统一的方式与分布式系统进行交互。 分布式系统的扩展或者升级应该是相对比较容易的1。这一特性是由于下述原因：1、 分布式系统由独立的计算机组成，但同时隐藏了其中单个计算机在系统里所承担任务的细节。2、 即使分布式系统中某些部分可能暂时发生故障，但其整体在通常情况下总是保持可用。3、 用户和应用程序不会察觉到那些部分正在进行替换和维修，以及加入了哪些新的部分来为更多的用户和应用程序提供服务。 为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“中件层”组织起来，该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的底层之间，如图1.1所示。这样的分布式系统有时又称为中间件（middleware）。图1.1作为中间件组织的分布式系统（请注意，中间件层延伸到了多台机器上）现在我们考察一下分布式系统的几个例子。第一个例子是位于一所大学或者某个公司部门的工作站网络。该系统除了包括每个用户自己的工作站以外，还应该包括机房内的一个处理器池。这些处理器并不分配给特定的用户，而是根据需要进行动态调配，这样的系统可能包含一个单一的文件系统，允许所有的机器通过相同的方法并且使用相同的路径名来访问所有的文件。并且，当用户键入一个命令的时候，系统将寻找执行该命令的最佳位置，也许会在自己的工作站上直接执行该命令，也可能会在别人的一个空闲的工作站上执行，还有可能有机房中某个尚未分配的处理器执行。如果系统整体外观和行为与传统的单处理器分时系统（即多用户系统）相似，那么这个系统就可以看做是分布式系统。第二个例子是某个工作流信息系统，该系统支持对账单的自动的处理。一般情况下，会有来自多个不同部门的人员在不同的地点使用这样的系统。例如，销售部的人员可能遍布在很大的一个区域，甚至全国。可以通过电话网络（或者蜂窝电话）连接到系统的膝上型计算机下达订单。收到的订单由系统自动传送到计划部，接着新的内部调货订单就会送达仓储部，同时有财务部处理账单。该系统自动将订单传送到相关人员手中。用户根本就看不到系统中订单处理的物理流程；对于用户来说，这些订单像是由一个集中式数据库处理的一样。 最后一个例子是万维网。它提供了一种简单、一致并且统一的分布式文档模型。要查看某个文档，用户只须激活一个引用（即链接），文档就会显示在屏幕上。理论上（但目前在实际中并不是这样）并不需要知道该文档来自于哪个服务器，更用不着关心服务器所在的位置。要发布一个文档也很简单：只需要赋予它一个唯一的url名，让该url指向包含文档内容的本地文件即可。如果万维网向用户呈现的是一个庞大的集中式文档系统，也可以认为它是一个分布式系统。不幸的是，我们现在还无法做到这一点。例如，用户明白这样一个事实：文档位于不同的地点，并由不同的服务器处理。1.2 目 标 分布式系统必须能够让用户方便地与资源连接；必须隐藏资源在一个网络分布这样一个事实；必须是开放的；必须是可扩展的。1.2.1 让用户连接到资源 分布式系统最主要目标是使用户能够方便地访问远程资源，并且以一种受控的方式与其他用户共享这些资源。资源几乎可以是任何东西，其典型例子包括打印机、计算机、存储设备、数据、文件、web页以及网络，但这些只是资源中的一小部分。有很多理由要求资源共享，一个显而易见的理由是降低经济成本。例如，让若干用户共享一台打印机比为每一位用户购买并维护一台打印机要划算的多。基于同样的原因，共享超级计算机和高性能存储系统这样昂贵资源也是很有意义的。1.2.2 透明性 如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统，这样的分布式系统就称为透明的。 (1)分布式系统的透明性 透明性的概念可以运用到分布式系统中的各个方面，如图1.2所示。透明性说明访问隐藏数据表示形式的不同以及资源访问方式的不同重定位隐藏资源是否在使用过程中移动到另一个位置并发隐藏资源是否由若干相互竞争的用户共享故障隐藏资源的故障和恢复持久性隐藏资源（软件）位于内存中还是硬盘中图1.2 分布式系统中不同形式的透明性（iso 1995） 访问透明性指对不同数据表示形式以及资源访问方式的隐藏。例如，要将一个整型数从基于intel处理器的工作站传输到一台sun sparc机器上，我们必须考虑到intel处理器传输数据字节的顺序是little endian格式（先传输数据的高位字节），而sparc处理器却使用big endian（先传输数据的低位字节）。在数据表示形式上还会存在其他的差别。例如，分布式系统中的多个计算机系统可能运行的是不同的操作系统，这些操作系统的文件命名方式不同。文件命名方式的差异以及由此引发的文件操作方式的差异都应该对用户和应用程序隐藏起来。(2)透明度 虽然对于任何分布式系统来说，实现分布透明性通常是可取的，但是在某些情况下，把所有分布情况都对用户屏蔽得严严实实并不见得有好处。这样的一个例子是，如果您订阅了一份电子报刊，并且要求它在每天本地时间早上7点之前就寄到邮箱里，而您现在呆在地球另一端的不同时区，您就会发现“早报”不在是早上寄到的。 另外，还必须在高度的透明性和系统性能之间进行权衡，得出折衷方案。例如，许多internet应用程序会不断尝试连接到某台服务器，多次失败后才最终放弃。这种在用户转向另一台服务器之前竭力隐藏服务器短暂故障的企图会导致整个系统变慢。在这种情况下，最好还是让用户早一些放弃，或者至少允许用户取消这种连接的尝试。 在设计并实现分布式系统时，把实现分布的透明性作为目标是正确的，但是应该将它和其他方面的问题（比如性能）结合起来考虑。1.2.3 开放性 开放的分布式系统的另一个重要目标是，它必须是灵活的，要能够方便的把由不同开发人员开发的不同组件组合成整个系统。同时，还必须能够方便地添加新组件、替换现有的组件，而不会对那些无须改动的组件造成影响。换句话说，开放的分布式系统应该是可扩充的。例如，在灵活的系统中，要添加可运行于另一个操作系统上的部件应该是比较容易的，即使要更换整个文件系统也不应该太对困难。但根据我们从日常实践中得到的经验，要实现灵活性是比较困难的。1.2.4可扩展性 通过互联网，世界范围的互联正在变得像给世界任何地方的人寄张明信片一样平常。考虑到这种情况，分布式系统开发者都将可扩展性作为最重要的实际目标之一。 系统的可扩展性至少可以通过三个方面来度量（neuman 1994）。首先，系统要能在规模上扩展，也就是说可以方便地把更多的用户和资源加入到系统中去。其次，如果系统中的用户和资源可以相隔极为遥远，这种系统就称为地域上可扩展的系统。最后，系统在管理上是可扩展的，也就是说，即使该分布式系统跨越多个独立的管理机构，仍然可以方便地对其进行管理。不幸的是，在以上这三个方面或其中某一两个方面可扩展的系统常常在扩展之后表现出性能的下降。1.3 分布式文件系统 鉴于共享数据是分布式系统的基础，分布式文件系统是构成许多分布式应用程序的基础就不足为奇了。分布式文件系统允许多个进程在长时期内以一种安全、可靠的方式共享数据。所以，它们已被用作分布式系统和分布式应用程序的基础层。在本节中，我们把分布式文件系统看作通用分布式系统的模型2。 我们将详细讨论两个不同的分布式文件系统。第一个实例是sun nfs(net work file system,网络文件系统)，它已经得到了广泛应用，现在正逐渐向基于internet的大规模文件系统的方向发展。nfs的大多数实现基于其版本3规范。 另一个完全不同的分布式文件系统是coda。coda源于afs（andrew文件系统），afs是一个在设计是就考虑到可扩展性的大规模系统。coda与许多其他文件系统的区别在于它在面对网络分区时支持连续操作。特别是那些故意时常断开网络连接的移动用户（比如，使用膝上型计算机的人们）会从中获益。 我们也将简要讲述其他三个系统。plan9是一个将所有资源都视为文件的分布式系统。从这种意义上来说，它可以被视为一个基于文件的分布式系统。我们将讲述的另一个系统是xfs，其与众不同之处在于它没有服务器，而是让客户实现文件系统。最后，我们会介绍sfs，该系统强调可扩展的安全性3。1.3.1 sun网络文件系统 我们以sun微系统的网络文件系统（network file system），即通常所说的nfs，开始讨论分布式文件系统。nfs最初是sun为在它的基于unix的工作站上的使用而开发的，但是nfs已在许多其他系统中实现。nfs的基本思想是每台文件服务器提供它的本地文件系统的标准化视图。也就是说，它不关心如何实现本地文件系统，每台nfs服务器支持相同的模型。这个模型带有一个通信协议，该协议允许客户访问存储在一台服务器上的文件。这种方法允许大量异构进程共享一个公共的文件系统，其中的进程可能运行于不同的操作系统和机器上。(1)nfs概述 与其说nfs是一个真正的文件系统，不如说它是共同为客户提供分布式文件系统模型的协议的集合。nfs协议是以不同的实现之间应该易于进行互操作为目的而设计的。因此，nfs可以运行于大量异构计算机之上。(2)nfs体系结构nfs底层的模型是远程文件服务的模型。这个模型为客户提供对远程服务器所管理的文件系统的透明访问。但是，客户通常不知道文件的实际位置，相反，nfs为客户提供访问此文件系统的接口，此接口类似于传统本地文件系统所提供的接口。也就是说，客户仅被提供包含多种文件操作的接口，而服务器负责实现这些操作。因此，这一模型也被称为远程访问模型（remote access model），如图服务器文件位于服务器上来自客户的访问远程文件的请求客户文件位于服务器上3.当客户程序被执行后，文件返回服务器 旧文件新文件客户服务器1.文件移动到客户2.在客户上执行访问 1.3.1（a）上载/下载模型与之相对照，在上载、下载模型（upload/download model）中，客户从服务器下载文件后，在本地访问该文件，如图1.3.1（a）所示。客户完成对文件的访问后，再将该文件上载回服务器，以便其他客户使用该文件。当客户下载一个完整的文件，修改该文件，然后将其放回服务器时，可以使用internet的ftp服务。尽管nfs基于unix的版本占主流地位，但是nfs已开发了多种版本以用于许多不同的操作系统。实际上，对所有现代unix系统而言，nfs通常按照图1.3.1（b）所示的层次体系结构实现。 图1.3.1（b） (3)文件系统模型 nfs版本四支持硬链接和符号链接。文件具有文件名，但是访问它们是通过一种类似unix的文件句柄（file handle）实现的，为访问一个文件，客户必须现在命名服务器中搜索该文件的文件名，然后获得该文件关联的文件句柄。另外，每个文件有许多属性，这些属性是可以查询和修改的。下表列出了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.1 p2p技术2.1.1 p2p的背景与发展 对等网络p2p（peer to peer），维基百科是这样定义的：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结构的中心化拓扑网络结构也存在一些问题，主要表现为： (1) 中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性较低； (2)随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本过高；（3）中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被攻击为非纯粹意义上的p2p网络模型。综合上述优缺点，对小型网络而言，中心化网络模型在管理和控制方面占一定优势。但鉴于其存在的种种缺陷，该模型并不适合大型的网络应用。（2）全分布式非结构化的p2p网络 全分布式非结构化刚络采用了随机图的组织方式，结点度数服从powerlaw”规律，从而能够较快发现目的结点，而对网络的动态变化体现了较好的容错能力，因此具有较好的可用性，同时可以支持复杂查询，如带有规则表达式的多关键词查询，模糊查询等10，采用这种拓扑结构最典型的案例便是gnutella，如图2.1.2（2）所示。 图2.1.2（2）gnutella网络的拓扑结构gnutella是一个p2p文件共享系统，它和napster最大的区别在于gnutella是纯粹的p2p系统，不存在集中式的目录服务器，并且文件的发布和网络拓扑松散相关。 gnutella网络具有以下特点： (1) 不存在中央服务器，完全依赖于网络中的交互式个人成员而独立存在；(2)在浚网络模型中，每一个联网计算机在功能上都是对等的，既是客户机同时又是服务器，所以被称为对等机。 发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目前对此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性能。（3）全分布式结构化的p2p网络 在这类网络中，不存在中心化的目录服务器，因此属于全分布式的p2p网络。这种类型的网络结构，采用分布式散列表(distributed hash table，简称dht)的全分布式结构化拓扑网络。分布式散列表实际上是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。 dht结构能够自适应结点的动态加入与退出，有着良好的可扩展性、鲁棒性、结点id分配的均匀性和自组织能力。最经典的案例是tapestry、chord、can和pastry4。这里主要介绍一下具有代表性的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.3p2p的特性 与其它网络相比，p2p具有以下特性：（1）非中心性网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。 (2)可扩展性 p2p的分散化带来的一个直接的好处就是提升了系统的可扩展性。在p2p网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。 (3)匿名性 p2p中一个很重要的特性就是匿名性。匿名性的一个重要日标就是让用户在使用系统的时候不必受各种法律问题的约束，进一步的目标就是保证审查机构无法对数字内容进行审查。 (4)自组织性 在p2p系统中，由于可扩展性、支持容错、资源不断地连接断开以及拥有的开销等原因，使系统具有一定的自组织特性是必要的。 (5)健壮性 p2p架构天生具有耐攻击、高容错的优点。由于服务是分散在各个节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。而且p2p模型般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。 (6)高性能性 性能优势是p2p被广泛关注的一个重要原因。采用p2p架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。2.2 p2p搜索技术p2p搜索技术也依据p2p网络的体系结构而异，不同的体系结构有着完全不同的搜索算法。在此我们主要讨论非结构化p2p网络和结构化p2p网络的搜索技术。2.2.1非结构化搜索技术非结构化分布式p2p网络完全脱离了中心服务器，网络中每一个节点的地位都是平等的，每一个节点既是客户端又是服务器，而且它们与相邻的节点具有相同的能力，以gnutella为典型代表的一种网络结构。非结构化的p2p网络路由技术可以分为两类：盲目搜索和利用网络中资源的分布信息进行搜索。盲目搜索是从任意一个节点出发定位目标节点，而不利用网络中资源的分布信息进行搜索，特点是网络中的每一个节点记录以前接收过的请求和响答，当开始搜索的时候可以根据记录对后续路由做出启发。非结构化p2p网络搜索技术中最典型的便是泛洪算法。泛洪算法是最早出现在非结构化的p2p网络搜索算法中，它的特点是搜索时对全网的节点进行遍历和搜索。在泛洪搜索技术中，消息像洪水一样在网络中的各个节点之间流动，所以被称作泛洪算法。泛洪搜索技术具体方法如下所示：在整个p2p网络中，某个节点要搜索某个资源时，首先它向相邻的节点发送查询消息。如果某个节点拥有这个资源，就向查询节点返回一个消息，告诉查询节点自己有这个资源，否则相邻节点就再次把查询消息转发给自己再相邻的节点。在整个查询过程中，因为怕消息发出后在一个循环的区域里传送，所以节点通过查询消息的ttl（time to live，生存时间）值或者跳转数来判断查询消息是否过期，当ttl或者跳转数超过一定的数值时，接收到消息的端就舍弃该消息。泛洪搜索算法比较简单，实现起来也相对容易，但它在每次搜索的时候都进行全网的遍历，这样便给网络带来了很大负载，而且搜索效率也不高，算法的时间复杂率是o(n)，整个网络扩展性也极差，安全性也不好。2.2.2基于dht的搜索技术分布式结构化p2p网络搜索主要采用分布式哈希表算法来组织p2p网络中的节点。首先介绍一下哈希的概念：因为dht算法是基于一致性哈希函数（consistent hashing）的一种资源定位及搜索算法。一致性哈希使用的是如md5、sha-1等哈希函数。我们先简单介绍一下哈希函数的概念：哈希函数，就是把任意长度的输入（又叫做预映射，pre-image），通过具体的哈希算法，转换成固定长度的输出，该输出就是哈希值。这种转换是一种压缩映射，也就是，哈希值的空间通常远远小于输入的空间，不同的输入可能会哈希出相同的输出，而不可能从哈希值来唯一的确定输入值，也就是哈希函数是不可逆的。哈希函数具备以下性质：(1）可以作用于一个任意长度的数据块。(2）能产生一个固定长度的输出。(3）对任何给定的x，hash(x)计算相对容易，用硬件或者软件都能实现。 (4）对任何给定的码h，寻找x满足hash(x)=h在计算上是不可行的(哈希函数的单向性)。(5）对任何给定的数据块，寻找不等于x的y，使得hash(y)=hash(x)在计算上是不可行的。有时将此称为弱抗冲突（weak collision resistance）。(6）寻找任何的(x,y)对满足hash(x)=hash(y)在计算上是不可行的，有时将此称为强抗冲突（strong collision resistance）。基于以上的性质我们可以得到，哈希函数可以保证数据的唯一性。比较著名并且常用的哈希算法有md5和sha-1算法等等。这两者可以说是目前应用最为广泛的哈希算法，而它们都是以md4为基础设计的。下面将详细的介绍dht算法，它是一种分布式的路由算法，在不需要服务器的情况下，每台机器只负责一小段范围的路由，并负责存储一小部分的数据，从而实现整个dht网络的查找和存储。在实际的系统中，p2p网络的逻辑地址通常是由哈希函数得到的，每台机器都将保存其中的一部分哈希表用来路由，所以分布式结构化p2p网络通常也称为dht网络。在分布式结构化p2p网络中，网络中的每一台计算机称为一个节点，每一个节点有一个唯一的值用来标识该节点，对于一个节点来说典型的表示就是它的ip地址和端口号。在p2p网络中，每一个节点和每一个资源都需要一个标识符，标识符必须是独一无二的一组数字，节点的标识符可以通过对一个节点的ip地址和端口号作为预映射进行哈希计算来获得；资源将其一组关键字作为预映射进行哈希，其运算的结果便作为该资源的标识符，也由此标识符决定此关键字对应的那条信息由哪个节点负责储存。用户搜索的时候，用同样的算法计算出资源的关键字的哈希值，然后根据哈希值知道该资源对应信息的存储的位置，再根据节点的dht迭代的得到相应节点的ip和端口号，最后并与之进行通讯，从而能够迅速定位资源的位置。例如节点的标识符我们称为nodeid。资源的标识符也是一个独一无二的标识符，我们称之为keyid。nodeid和keyid两者本质上是一样的类型，用有可能产生冲突的哈希函数计算出来有可能相同，将会对系统产生严重的影响，所以在哈希算法的选择上有一定的要求。在基于dht的p2p网络中，资源的关键字通过哈希计算得到要查找的key值，p2p系统中的每个节点都负责管理一部分哈希空间，它负责保存某段范围的key值。每个节点存储一张表，就是dht，key在这里对应着keyid， value在这里对应着所在的节点的通讯信息，可以是ip、端口号等信息。当开始搜索某个资源的时候，先用哈希函数计算出需要搜索资源的key值，然后通过自身的dht，在p2p网络中找到与之匹配的key值存储的节点，返回这个节点的标识符给需要查询的节点的通讯信息，通常这个过程也是一个迭代的过程，大多数情况下，需要在网络中迭代很多次才能找到相应的节点，最后与之建立连接，取得资源。目前使用的一些互联网上的共享资源的软件，一般会查找到很多节点，再用一定的策略从各个节点同时下载。dht就是为了解决在非结构化分布式网络中查找资源的盲目性的问题而引入的。dht 的主要思想：1.将内容索引抽象为对:k是内容关键字的hash摘要 k = hash(key)v是存放内容的实际位置，例如节点ip地址等2. 所有的对组成一张大的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）k va. hash表b. 分布式hash表规则?k vn1n48n16n32n8k vk vk vk vchord、can、tapestry、pastry在许多情况下,节点id为节点ip地址的hash摘要图2.2.2（b）插入 (k1,v1)k vk vk vk vk vk vk vk vk vk vk v(k1,v1)查询(k1)abk1=hash(xyz.mp3)v1=xyz.mp3c 图2.2.2（c）2.3 chordchord算法是由麻省理工学院研究开发的一种dht算法，基本的原理是根据节点的ip地址、端口号和资源的关键字通过哈希函数计算得到全局唯一的标识符，将它们映射到一个环上去。为了保证标识符的唯一性，它采用一致性哈希函数来对资源关键字和节点进行哈希运算。哈希函数通常是采用sha-1算法，生成160位的标识符11。每一个160位的标识符按大小顺序链接在一起，可以形成一个环