P2P网络的搜索技术研究.doc

中国通信标准化协会课题编号： P2P网络的搜索技术研究2008年 9 月 研 究 报 告 要 点资源搜索是P2P技术的一个很重要的研究点，搜索方式涵盖了P2P的网络结构、路由算法、索引方式、查询方式和存储分布等P2P技术的多个重要方面。该报告从索引方式入手开始介绍P2P搜索技术。三四章从覆盖层网络结构的角度将搜索方案分为结构化和非结构化的，并分布详细介绍了多种路由算法。第五章介绍了语义的概念，并深入调研了非语义查询方式，此外还有多样化的查询类型，都是解决当前用户的需要的、正进一步深入的研究方向。第六章梳理了现有的搜索方案的存储方式及其负载均衡的情况。（技术工作委员会、工作组名称）TC1-WG4研究单位： 北京邮电大学项目完成人： 皮人杰、陈辉、吕月梅、乐观、宋美娜项目参加人： 王虹、陈墨源完成日期： 2008年目录前言6缩略语71P2P Search概述81.1P2P Search概述81.1.1P2P 技术简介81.1.2P2P Search的定义81.1.3P2PSearch的分类81.2P2P Search的研究现状91.3P2P Search的研究要点101.4P2P Search面临的问题102索引类型112.1索引概述112.2索引的类型和比较122.2.1本地索引122.2.2集中索引142.2.3分布式索引153非结构化网络下的P2PSearch技术163.1概述163.2现有搜索方法173.2.1Flooding搜索方法173.2.2迭代泛洪193.2.3启发式泛洪203.2.4本地索引法203.2.5Randomwalk搜索方法213.2.6Gnutella2搜索方法213.2.7基于移动Agent搜索方法213.2.8Modified-BFS搜索方法223.2.9小世界模型对搜索技术的影响224结构化网络下的P2PSearch技术224.1概述224.2常见拓扑结构234.2.1Plaxton树（Pastry，Tapestry）234.2.2环（Chord，DKS）244.2.3Tori（CAN）254.2.4Butterfly（Viceroy）254.2.5Bruijn（D2B,Koorde，距离二等分，ODRI）264.2.6skip图275查询285.1非语义查询285.2语义查询285.2.1关键字查询295.2.2向量模型（PlanetP, FASD, eSearch）的语义检索方案295.2.3隐含语义检索（pSearch）的语义检索方案305.3查询的分类315.3.1范围查询325.3.2多属性查询345.3.3连接查询355.3.4聚集查询356存储366.1P2P存储系统概述366.2容错机制376.3一致性与副本396.4存储负载均衡问题436.4.1结构化P2P系统负载均衡问题446.4.2复制446.4.3地址空间平衡(Address-space Balancing )456.4.4结点平衡(Nodes Balancing)476.4.5使用虚拟节点(Virtual Nodes)476.4.6其他方案486.4.7负载平衡小结497P2P Search的标准现状497.1现有国际标准、国家标准和相关行业标准、企业标准497.2标准化建议49参考文献49前言P2P技术作为当前主流分布式应用所采用的一种技术，通过自组织的方式来构建应用系统，充分的利用了网络边缘节点的计算和存储资源，具有很好的可扩展性、健壮性以及避免单点瓶颈的特性。目前也逐渐的为运营商所接受，用来构建未来的核心网络，也体现了该技术在性价比方面的优势。搜索应用作为当前已经比较普及的应用，其价值已被大家广泛认识，这将是用户从互联网海量的信息中获取所需信息的必备工具。当前的搜索应用主要采用“爬虫”从互联网上广泛的获取网站信息，并存储这些资源，然后建立集中式的文件及关键词索引，收到用户的查询请求后将采用特定的查询方式从索引中找到相关的文件信息，根据特定算法计算相关文档的相关度，然后根据相关度排序并将结果返回给用户。这一领域在索引以及查询方式等方面都还在深入研究中，同时目前也存在语义搜索、多媒体搜索等多方面的研究。如何在P2P中进行搜索与现有的互联网搜索相比又是一个有所不同的领域，主要的不同点存在以下几个方面：首先是索引的建立的方式将有所不同，以往的索引都是通过“爬虫”来收集其他主机的资源来建立索引，P2P网络中则不需要“爬虫”来实现网络资源的集中，同时索引方式根据P2P网络组网方式的不同也有不同的建立索引的方式。另外一个不同是在查询的路由方式，现有互联网搜索基于C/S的模式，不需要进行查询的路由，而P2P网络中由于资源的分布式特性，则需要将查询进行路由来进行搜索。最后的不同在于对搜索结果的处理上，对不同节点返回的信息如何进行相关度以及可信度的排序将与现有的C/S搜索存在较大差异。本文档主要参考RFC4981:Survey of Research towards Robust Peer-to-Peer Networks: Search Methods, 对以上相关问题进行了深入的调研和整理。缩略语DHTDistributed Hash Table分布式哈希表TTLTime to Live生存周期BFS宽度优先搜索PRRPlaxton，Rajiaraman，Richa三种P2P方案KSSKeyword Search System关键字搜索系统FASDFault-tolerant，Adaptive，Scalable，Distributed可容错的、自适应的、可扩展的、分布式的SDDSScalable Distributed Data Structure可扩展的分布式数据结构MAANMultiple Attribute Address Network多属性地址网络LDPCLow Density Parity Check低密度校验码1 P2P Search概述1.1 P2P Search概述1.1.1 P2P 技术简介P2P（Peer to Peer）即对等计算或对等网络，通常简称为P2P，可以简单地定义成通过直接交换来共享计算机资源和服务。在P2P网络环境中，成千上万台彼此连接的计算机都处于对等的地位，整个网络一般来讲不依赖于专用的集中服务器。网络中的每一台计算机既能充当网络服务的请求者，又能对其他计算机的请求做出响应，提供资源与服务。通常这些资源和服务包括：信息的共享与交换、计算资源（如CPU的共享）、存储资源（如缓存和磁盘空间的使用）等。P2P网络有如下三条特点：自组织、对等通信、分布式控制。P2P网络是自组织的，当节点加入、离开或故障时能自主地做出相应的调整；P2P网络是对等的，网络中的对等体（Peer）在通信中既可充当服务端，又可充当客户端；P2P网络是分布式的，网络中没有集中控制的实体。1.1.2 P2P Search的定义目前，关于P2P技术研究的一个主要问题是搜索问题，研究P2PSearch技术具有重要的学术意义和实用意义。简单来说，P2P Search主要解决的是如何在P2P网络上搜索特定的资源与服务。传统的搜索主要采用的是C/S模式，用户在客户端输入要查找的信息，通过网络送达到服务器上，服务器经过处理将相应的结果返回给客户端，这就完成了一次搜索过程。这样的搜索不仅给服务器带来巨大的处理任务，而且在一个不稳定的网络环境下，搜索过程可能持续很长时间，甚至完全终止。在P2P技术飞速发展并充分应用到网络中的背景下，我们把注意力集中到P2P技术中，通过P2P技术实现分布式地搜索与查找。从学术上来说，P2P网络上资源的存在形式对搜索技术提出了新的要求。P2P网络上的资源丰富多样，包括文件、程序等软件资源和打印、传感器等硬件资源，也包括空闲的CPU周期等。P2P网络的资源还具有极大的分散性，资源分布在许多节点上，同时每个节点上的资源并不多。由于节点自由的加入或退出，P2P网络的资源还处于不断的动态变化之中。P2P网络的资源存在形式决定了P2P的搜索技术和现有的搜索技术有很大的不同，所以，研究P2P网络的搜索技术具有重要的学术意义。从实用意义上讲，在P2P应用仅有的短短几年发展时间里，它成为了占用Internet流量的主要应用类型，根据2007年3月美国的最新统计，P2P文件交换已经占美国Internet流量的70%以上，而2004年这一数据仅为40%左右。根据Internet权威专家预测，这一比例在未来几年还将继续上升。现阶段互联网上大量资源被闲置，没有充分地被利用。P2P搜索技术可以帮助人们方便地找到各种资源，从而提高资源的利用率，实现资源的充分共享。同时，P2P搜索技术可以方便人们即时找到协作对象，能够进行跨越地理位置障碍的协同工作。P2P系统支持大量用户的能力，已经开始显示出技术优势：它能够以较低成本快速地部署强大的、大规模的分布式应用。所以，研究P2P的搜索技术也有重要的实用意义。1.1.3 P2PSearch的分类从资源搜索的集中程度为标准，可以将P2P网络分为集中索引模式、纯P2P模式以及混合P2P模式。我们会在第二章详细介绍这不同模式下的索引方式。从P2P网络有没构建有结构的覆盖层来分，P2P网络又分为结构化网络和非结构化网络。目前也有一些介于非结构化和结构化之间的网络方式。1.1.3.1 非结构化对等网络在非结构化拓扑的P2P系统中，结点间的逻辑拓扑关系通常较为松散，具有较大的随意性。资源（或资源元信息）的放置通常与P2P系统的拓扑结构无关，一般只放置在本地。非结构化拓扑的实现和维护相对简单，可支持灵活的资源搜索条件，但高效的资源搜索通常较为困难（通常都是采用广播搜索、随机转发和选择性转发等方法），适用于由大量自治性强的结点组成、对服务质量没有严格要求的应用，如P2P文件共享应用等。非结构化拓扑可进一步按照分散度进行分类：如Napster和BitTorrent是集中式非结构化拓扑，Gnutella和Freenet是全分布式非结构化拓扑，FastTrack是部分分布式非结构化拓扑。1.1.3.2 结构化对等网络在结构化拓扑的P2P系统中，结点间的逻辑拓扑关系通常由确定性的算法严格控制，资源（或资源的元信息）的放置也是由确定性的算法精确发布到特定的结点上。结构化拓扑P2P系统通常采用分布哈希表技术(Distributed Hash Table, DHT)1,2构建。结构化拓扑的优点是资源定位准确并且可保证一定的效率，有着良好的可扩展性和性能，因而适用于对可用性要求高的系统。结构化拓扑的应用领域广泛，包括分布式存储、应用层组播和名字服务等。但结构化拓扑的维护相对复杂，通常只支持精确匹配资源搜索，对复杂搜索条件的支持较差。结构化拓扑的P2P系统大都是全分布式的，如Chord10, Tapestry13 ,CAN3等；也有少部分是部分分布式的，如Brocade4。非结构化拓扑和结构化拓扑具有不同特点，可分别适用于不同需求的P2P系统。图1-1给出了P2P系统的分类。图11 P2P系统的分类P2P系统非结构化拓扑结构化拓扑集中式拓扑（Napster）部分分布式拓扑（FastTrack）全分布式拓扑（Gnutella）部分分布式拓扑（Brocade）9全分布式拓扑（Chord、CAN、Tapestry）1.2 P2P Search的研究现状早期的搜索方案都是基于集中式的非结构化网络的，主要采用泛洪的方式，可扩展性差，查询效率也低。随后兴起的是基于DHT的搜索方法。DHT是一种结构化的分布式的方法，具有良好的可扩展性和查询效率，并满足一定的负载均衡，但它主要提供精确匹配的查找，无法满足模糊的、多属性的关键字搜索。因此有了介于结构化和非结构化之间的方法，提出了语义查询的概念。利用非结构化网络的特性，可以实现语义搜索，但DHT的方法又可以带来高查询效率和易扩展到优点。两者的进一步结合是将来的一个很重要的工作。1.3 P2P Search的研究要点通过对大量研究资料的考察，我们可以按以下几个部分来整体把握P2PSearch所要涉及到的研究要点:索引、结构化与非结构化方法、查询类型、存储。实际上，索引方式、结构拓扑、路由算法和查询类型往往是组合在一起的，彼此关联和制约，从而构成一个完整的P2P搜索方法。现有的不同的P2P方案就是这些组合下形成的一个个整体的方案。索引方式在一定程度上决定了P2P的体系结构，索引结构会影响到覆盖层路由方式和查询检索方式的设计，一般来说可以根据索引的集中化程度分为本地式、集中式和分布式。结构化和非结构化，即使是否构造有结构的覆盖层网络。在本文中，我们将结拓扑和基于结构拓扑的路由算法捆绑在一起来做介绍和分析。P2PSearch的大部分研究也集中在此。结构化方法和非结构化方法各有优缺点，对两者的取舍和融合是未来P2PSearch的重要工作。查询类型首先可以分为语义查询和非语义查询两个大类。这两类查询各有优缺点，但当前比较受欢迎的是语义查询，因为它可以捕获资源直接的关联，可以为用户提供更多智能化的、多样的、模糊的查询。针对用户的选择，查询类型还可以分为范围查询、多属性查询、连接查询和聚集查询等，这些具体的多样查询，涉及到的具体技术是不一样的，值得深入研究和探讨。存储相对来说，和P2PSearch联系不是那么紧密，但作为完整的P2PSearch方案，在设计其路由算法和网络拓扑时，是必须考虑存储方式的。此外，存储的负载均衡问题也P2PSearch常常会考虑的方面。1.4 P2P Search面临的问题P2P搜索技术是构建P2P系统的基础性关键技术，对P2P系统的可扩展性、性能和鲁棒性等各方面都有着重要影响。与传统的分布式系统不同，P2P系统具有的诸多特点给资源发现技术带来了很多新的挑战：(1) P2P系统通常具有较大的规模著名的P2P文件共享系统Napster创建一年多后用户就增长到5千万，Kazaa系统的注册用户达到1.5亿，参与SETIHome的计算机数量达到480万5。大量的用户使得P2P系统中共享了海量的计算、数据、存储和带宽等各类资源。据统计6, P2P系统Morpheus的470,000用户总共共享了约360TB的数据，SETIHome项目聚集的计算能力达到了68.83TeraFlops5。大量用户和海量资源使得P2P系统具有重要的应用价值，但也使得P2P系统中的资源定位成为一个具有挑战性的难题。因此，P2P资源发现技术必须具有较好的可扩展性和性能，能够支持大规模的用户与资源。(2) P2P系统具有很强的分布性P2P系统中参与的用户和资源众多，并且各个结点和各类资源地理上广泛分布。强分布性有利于P2P系统的鲁棒性和负载平衡，但也使得系统的资源定位变得复杂。很多P2P系统是完全分布的，所有结点地位完全平等，既是客户端也是服务器，系统中没有任何传统意义上的服务器来提供服务（如Gnutella和Chord等）；有些P2P系统中，存在着某种形式的服务器（如Napster等），但其中服务器的作用通常只是用来协调结点间的通信和协作，具体的任务仍然由分布的各结点来完成。因此，P2P资源定位技术通常需采用分散式(decentralized)的结构，通过有效的分布式算法来实现资源的组织与发现。(3) P2P系统具有很强的动态性在P2P系统中，结点可能会由于各种原因（结点自主意愿或网络连接不稳定等）随时加入或退出，结点的动态加入与退出是系统的一种常态。研究指出7，Internet上计算机的平均无故障时间约为13小时，即在10000个结点的P2P系统中，平均每2分钟有一个结点失效。对典型P2P文件共享系统Napster和Gnutella的研究表明8，结点加入和退出系统的频率相当高，结点每次平均在线时间只有1小时。P2P系统的动态性会引起P2P网络拓扑的频繁变化，增加了P2P系统中资源发现的难度。因此，P2P资源发现技术必须具有较好的自适应性与鲁棒性，在结点和网络环境发生动态变化时维持系统的稳定性、可用性和性能。(4) P2P系统中结点具有较强的异构性一方面，结点的异构性是由于各个结点在计算能力、存储能力和网络带宽等方面广泛存在着客观上的差别。另一方面，结点的异构性也受结点自身自治性行为的影响，例如目前很多流行的P2P文件共享软件都允许用户自主选择使用上下行带宽、网络连接数和共享的资源数量等。对Gnutella系统的监测表明8，Gnutella网络中各结点在网络带宽等方面有着显著的异构性。因此，P2P搜索技术应能充分考虑结点间的异构性，以提高P2P系统的整体效能。由于P2P系统的这些特点，P2P搜索技术需具有下面的几个特性：(1) 分散性。P2P搜索技术通常应采用分散式(decentralized)的结构，通过有效的分布式算法来实现资源发现，尽可能不依赖于少数中心服务器；(2) 可扩展性。P2P搜索技术应能适应不同结点规模的P2P系统，能够支持大规模 的结点和资源；(3) 自适应性。P2P搜索技术应能够自适应系统中结点的动态加入或退出，提供相对稳定的资源定位服务；(4) 鲁棒性。P2P搜索技术应能够提供一定的容错能力，在部分网络连接或结点失效时仍能保证系统的可用性。2 索引类型2.1 索引概述P2P的索引是实现P2P 搜索的基础，一方面索引将文件的信息保存在网络中，另一方面，P2P网络通过索引找到目的节点。P2P索引可分为本地索引、集中索引和分布式索引。如果采用本地索引，节点只能保存自己的数据信息，不能保存其他节点上的数据信息，早先产生的P2P系统Gnutella就是采用这种索引。如果采用集中式索引，那么网络中就会有一个独立的服务器保存各个节点的数据信息，典型的例子就是Napster系统。如果采用分布式索引，指向数据信息的索引分布在若干个节点中，最早的分布式索引系统就是Freenet。在今天的大多数P2P设计中，使用的是分布式索引。P2P索引还可以分为转发型和非转发型。当非转发型索引引导查询时，查询通过一跳直接跳到含目标数据的结点。当需要大量对等点的可扩展性时，这些方案被扩展到两跳。转发型的P2P系统更常见一些，这些系统跳数将随着对等点总数的变化而变化，通常呈对数关系。在路由状态、查询延迟、更新带宽和对等点流动性之间的相关权衡对整个系统的可信任性至关重要。2.2 索引的类型和比较2.2.1 本地索引在早期的Gnutella上寻找对等点时，在整个P2P网络上广播“ping”信息。“ping”信息就是用来发现网络中可用的主机的。接收到“ping”信息的可用对等点，将以“pong”信息回应。然后，当有对等点要发起查询时，就广播一个“query”信息，这个信息一般不超过256比特，对等点可能会抛弃超过256比特的“query”信息，而超过4kb的信息，一定会被对等点抛弃。在“query”信息中有一项是搜索条件(Search Criteria)，它是一串关键字列表。接收到该“query”信息的对等点，将该关键字列表与自己的本地共享文件相比较，若有文件包含所有关键字，那么它就发送“Query Hit”回应9。为了提高本地索引式P2P网络的可扩展性，学者们做了很多尝试。Gnutella使用了固定的TTL(time-to-live)环，查询的生存时间被设置为少于7到10跳9。短的生存时间可以减少网络流量和对等点上的负载，但是也减少了成功查询的几率。一篇报道甚至说，这种固定的基于TTL的机制无法工作10。为解决TTL的选择问题，他们提出了以下几个方案：1） 扩展环(expanding ring)，即别的地方所说的迭代加深11。它使用依次增大的TTL计数器直到找到匹配项。泛洪法（flooding）、环形法(ring)和扩展环法(expanding ring)都因复制了查询消息，而增加了网络负载。2） 随机漫步法(random walk)，没有复制查询消息，单个查询消息漫步整个网络，这确实减少了网络的负载，但却大大增加了搜索延迟。其中一种解决方法是，请求结点发出k个查询信息，而且每个查询信息自由选择漫步路由，这被称为随机k-walker法。为能终止漫步，k-walker法与两种方法相结合TTL和“检查(checking)”。与TTL法相结合，意味着k-walker法也是在一定跳数后，终止漫步,这种方法同样也面临着TTL的选择问题。而“检查”意味着，每个漫步者周期性的在去往下一个结点时，检查查询发起者。例如，实验证明，每经过4跳检查一次，可以达到很好的效果67。Adamic、Lukose等人建议随机漫步搜索应该被直接引导到连接度较高的结点，即这些结点连接较多的对等点 12。他们假设连接度较高的结点也有较高的查询吞吐量。然而，如果没有一些平衡设计方案，那样的对等点将会被整个P2P信号流量淹没。3） “直接广度优先(directed breadth-first)”算法11。它根据先前的性能，例如成功查询结果的数量，来选择一个对等点的子集，在这个子集中推进查询。4） 依概率泛洪。这种方法中结点以概率p向它的邻结点推进查询。这样减少了两结点间的通路数以减少网络中查询的流量，同时又保持了可达性。这种方法已使用过滤理论建立模型13。一些性能研究单位调查了本地建索引的P2P系统。Jovanovic注意到Gnutella的幂指数特性14。Sen和wang比较了Gnutella、Fasttrack271、Direct Connect的性能15,16,17。当时，只有Gnutella使用了本地数据索引。这三种方案现在都使用分布式数据索引，并以超级对等点（ Ultrapeer ,在 Gnutella中），超级结点（Super-Nodes ,在FastTrack中），枢纽（Hubs,在Direct Connect中）的形式分层。据发现，只有少数对等点连接度较高，而且整个系统的可信任性受这些对等点的支配。当对等点的运行时间和带宽重尾时，它们不能很好的满足齐夫分布。幸运的是对于互联网服务提供者，通过IP前缀和自治系统提供的综合措施，比单个IP地址要稳定得多。一个关于华盛顿大学流量的研究中发现，Gnutella和Kazaa占了整个大学TCP总流量的43%18。他们还报告说，有600个外部对等点（共281026）的重尾分布分发26%的Kazaa字节给内部对等点。而且，从P2P网络检索出来的对象比Web对象多三个数量级300个对象几乎占了总Kazaa带外带宽的一半。另外的报告说，Gnutella的覆盖网络拓扑与物理网络拓扑不匹配。我们知道因特网是由一些自治系统组成的，自治系统内运行相同的内部网关协议。穿越自治系统的花费比在本地通信要贵，但是我们发现虽然40%以上的结点都处于前10个自治系统中，但仅有2-5%的Gnutella连接在同一个自治系统中。这意味着由Gnutella形成的穿越自治系统的流量无疑大大增加了花费19。这些研究共同强调了多媒体共享应用的重要性。他们激发了有趣的的高速缓存和定位方法来解决拓扑不匹配问题。同样是这些研究，证实了一个主要的可信任性课题：整个系统的可信任性可能对连接度高的对等点的可信任性敏感。Scamp的设计者把这个发现转化为设计启发，“使每个结点的连接度大致相同”20。他们分析了一个N结点的系统，平均度为c.log(n)(c是一个参数，决定了对于结点失效的恢复性)，链接失效以概率e独立发生。如果d>0是固定的，而且c>(1+d)/(-log(e)，那么当N趋于无穷大时，图断开的概率趋近于0。否则，如果c<(1-d)/(-log(e),那么当N趋于无穷大时，断开的概率趋于1。他们提出了一个算法localizer，它只使用本地信息，在Scamp协议下实现两个目标：一是减小连接花费（这里花费可以是指时延或是存储等）；二是使每个结点的连接度大致相等。Scamp协议是一种全分布式的自组织协议，用于建立非结构化的覆盖层网络。图2-1显示了Scamp节点加入的算法过程。图21 Scamp结点加入算法新结点任选网络中的一个结点连接。收到连接请求的结点将向它所有的邻结点推进这个连接请求。而收到被推进的连接请求的结点在有选择的向它的邻结点推进此请求。而localizer算法是在此基础上进行平衡。从图2-2可以看出此算法所做的是平衡每个结点的度。图22 localizer的作用效果Scamp覆盖建造算法可以支持上面任一种泛洪法和路由方案，或者其他的对这一问题流行的多播方案。对高扰动率的恢复性还有待将来的进一步研究。2.2.2 集中索引集中式方案，例如Napster21，十分重要，因为它们是第一个证明了来自将数据索引与数据本身分离的P2P可扩展性。最终3600万的Napster用户失去了服务，这不是因为技术上的失败，而是因为单个的管理者易受到合法唱片公司的攻击22。关于集中式数据索引的P2P系统的研究一直很少。那些系统同时也被称作“混合式”，因为索引是集中式的，但数据是分布式的。Yang和Garcia-Molina 发明了一种四类的混合式系统分类方法23：非链式服务器，这里用户的索引在一个服务器上，且看不到其他服务器上的索引；链式服务器，这里接受查询的服务器如果自己没有索引，它将推进查询到一系列别的服务器上；完全复制式，这里所有集中式服务器保存一个所有可用元数据的完全索引；散列式，这里关键字被散列到保存相关倒序表的服务器上。Napster使用了非链式结构，但它有个缺点，即用户不能看到系统中所有被建立索引的数据。严格地说，其他三种方式说明了分布式数据索引，而不是集中式索引。链式结构是当时被认为是最合适音乐交换应用的。通过客户更新中心索引的方法被分类为批量式、或者增加式，由查询-登录率确定最佳方式。测量法源自于OpenNap,是Napster的一个克隆24。另一个关于活动的Napster数据的研究报告说，对等点有效性的广泛变化，广泛的不愿意共享文件（20%-40%的对等者很少共享或几乎不共享文件），普遍的对可用带宽的低估，以至于阻碍了其他对等点共享自己的链接25。受Napster早夭的影响，P2P研究团体可能过早的放弃了集中式结构。Chawathe, Ratnasamy等认为Google和Yahoo证明了集中式索引的生存能力。他们认为，类似Napster设计的真正障碍不是技术方面的，而是法律和经济上的26。虽然这个在集中式结构方面的观点可能过于尖锐但它暗示了它们总是有比分布式结构更严峻的上前期资本障碍。越是关注可扩展的集中式结构，与分布式结构的区别就越来越不重要。例如，很明显，Google的设计者考虑Google是一个分布式的，而不是集中式的文件系统27。Google证明了规模和性能在商业硬件上是可能的，但仍有一个对每一个Google簇运转至关重要的集中控制者。时间将会证明，不管是集中式的，还是分布式的分类，形成中的P2P网络的价值是，在整个范围和地理分布中，它们降低了资本支出，消除了单点失效。2.2.3 分布式索引一个很重要的关于分布式索引的早期P2P方案是Freenet28,29,30。当它主要强调的是对等点的匿名性时，它引入了一个新颖的索引方案。文件由低等级的“内容-哈希”键和“安全符号子空间”键确定，这保证了只有文件所有者可以写文件，而其他用户只可以读文件。为找到一个文件，发出请求的对等点首先检查自己的本地表，是否有键值最接近目标的结点。当那个结点接受了查询，它同样查询是否有匹配项或者另一个键值最接近目标的结点。最终，这个查询或是找到了目标，或是超出了TTL限制。查询响应反向穿过成功查询路径，在每一个对等点中存入一个新的路由表项（被请求的键和数据保持者）。插入信息同样的一步步朝目标结点迈进，同时更新路由表项，最后在那里存储文件。与早期的Gnutella使用广度优先泛洪法不同，Freenet使用一种更经济的深度优先搜索31。图2-3表示了Freenet的查找过程。图23 Freenet查找过程对Freenet的鲁棒性有一个早期的评估。它显示，一个具有1000个结点的网络，30%的结点失效时，查询路径长度中值保持低于20跳。当Freenet设计者认为这可以证明，即使有相当大的失效时，系统仍出奇的强健30，相同的数据点很有可能在有意义的操作范围外。当在一个仅有1000个结点的网络中，第一个四分位数的查询有几百跳的路径长度时，有多少应用是有用的？对于数据，没有关于Freenet的动态鲁棒性的分析。例如，当结点频繁的到达和离开时，它性能如何？对于早期的Freenet工作，既有批评，也有推广。Gnutella的支持者认同了Freenet避免了查询广播的优点32。然而，有两项是至关重要的：建立一个查询需要精确的文件名；对于每一个查询，需要返回精确的一个匹配项。使用DHT的P2P系统，享有相同的特征一个精确的查询形成产生一个精确的响应。这个相似性并不令人惊奇，因为Freenet也使用哈希函数来形成键值。然而，DHT系统使用的查询路由有坚实的理论基础。和DHT系统的另一个不同点是，当一个新结点加入到网络中时，Freenet需要花时间去建立一个可以促进有效查询路由的索引。据发明者自己承认，这将破坏用户的第一印象33。提议在启动的时候，从种子结点下载一个路由表的副本，即使新结点可能离种子结点较远。Freenet的慢启动促使Mache, Gilbert等人，在请求失败后修改覆盖，并在成功请求后增加了索引项他们声称平均查询路由长度减小了一个数量级31。Clarke还强调对于有效地查询路由决定，缺少可用的位置和带宽信息33。他提出，对于查询路由表的每一个项，每一个结点收集响应时间、连接时间和请求成功率。当所要查询的键值不在自己的路由表中时，提议先从路由数据中最接近的已知键值预估响应时间，从而选择可以最快检索数据的结点。响应时间启发式的假设在键值空间里相邻的结点有相近的响应时间。这个假设源于早期的部署观察，即Freenet对等点似乎专于键值空间的部分空间这还没有被分析证明。Kronfol致力于Freenet无法做关键字搜索方面34。他提出，对等点缓存有权重的关键字列表，以向使用TFIDF标准和倒序索引的文件发送查询（部分4.2.1）。用这些方法，对等点可以为简单关键字列表，或更复杂的联合与非联合关键字发送查询。关于Kronfol的提案的鲁棒性分析和仿真仍保持开放。3 非结构化网络下的P2PSearch技术3.1 概述目前Internet上流行的P2P系统大都采用了非结构化拓扑。非结构化拓扑P2P系统的拓扑构造和维护相对简单，易于支持灵活的资源搜索条件（P2P系统将原始的资源搜索请求转发到各个结点上，搜索条件的具体匹配操作通常是由本地结点来完成），因而得到了大量的实际应用。但在非结构化拓扑的P2P系统中，资源的组织和管理相当松散，拓扑构造随意性大，资源对象的放置通常都与P2P系统的拓扑结构无关，从而给资源发现带来了诸多难题。早期的P2P系统Napster使用中央目录服务器来支持资源发现。Napster是集中式非结构化拓扑，通过中央目录服务器维护了系统中各结点上资源对象的索引信息，但结点之间的文件交换是直接的。中央目录服务器使得资源搜索实现简单，各结点只需通过查询中央目录服务器就可实现资源对象的定位，并易于支持灵活的搜索条件。但中央目录服务器也带来了可扩展性差、单点失效和性能瓶颈等一系列问题。由于中央目录服务器的缺点，随后出现的Gnutella和Freenet等P2P系统采取了全分布式的非结构化拓扑。在这种拓扑的P2P系统中，没有任何中央服务器，所有结点是完全平等的，结点间按照某种松散规则形成拓扑结构，资源对象的放置通常与系统的拓扑结构无关。以Gnutella系统为例，Gnutella系统的拓扑构造过程具有相当大的随意性：新结点加入系统时，首先与系统中某几个已知结点建立连接，通过这几个结点获知系统中其它部分结点的列表，然后从结点列表中选取几个结点作为邻居。在Gnutella系统中，各结点上的资源对象（数据文件）都保存在本地，资源搜索是通过受限泛洪(flooding)技术实现。Gnutella系统避免了Napster系统的中央服务器带来的问题，但其泛洪式搜索在系统中产生了大量的消息，严重影响系统的可扩展性和性能35，36。并且受限泛洪技术的搜索范围有限，不能确保一定能够搜索到己经存在的资源对象。另外一些 P2P系统采取部分分布式非结构化拓扑来提高资源定位的效率，典型系统如FastTrack等。部分分布式拓扑是集中式拓扑和全分布式拓扑的折衷，系统中通过动态选择一些超级结点来提供部分目录服务，以加快资源搜索过程，减少消息开销。但超级结点之间的搜索请求转发仍然是通过类Gnutella的泛洪等方式进行的。非结构化拓扑的P2P系统由于具有实现和维护相对简单等特性，目前在Internet上得到大量的实际应用，对非结构化拓扑的P2P资源定位技术的研究具有非常重要的应用价值。目前研究者们提出了泛洪化6，37和随机搜索37，38等很多方法，来提高非结构化拓扑P2P资源定位技术的性能和准确性。但总体说来，非结构化拓扑P2P系统中资源发现技术的可扩展性和性能较差、资源定位的效率和准确率难以保证等问题仍相当突出，有待深入研究。3.2 现有搜索方法非结构化下的搜索策略，可以分为两大类：盲目搜索和启发式搜索。盲目搜索通过在网络中传播查询信息并且把这些信息不断扩散给每个节点。通过这种泛洪方式来搜索想要的资源。而启发式搜索在搜索的过程中利用一些己有的信息来辅助查找过程。由于信息搜索对资源的存储有一些知识，所以信息搜索能够比较快的找到资源。下面是常见的搜索方法：3.2.1 Flooding搜索方法在现在的P2P网络中，泛洪搜索法使用比较多。一个节点向所有邻居节点广播查询消息，邻居节点再向自己的邻居节点广播，这个过程不断进行下去。为了限制搜索的范围，消息被设置了一个初始的TTL值。消息每经过一个节点，TTL值减1。当TTL值为0时，搜索过程终止。泛洪有以下特点：1、节点覆盖率高一项研究表明，在Gntualel网络中，采用泛洪方式，能够搜索到59%的节点(在Gnuta