P2P技术及其资源发现与定位

摘 要  P2P主要指机之间以对等方式形成的连接，弱化或完全取消了服务器的作用。文章从分析P2P的基本概念、需求和入手,讨论了P2P与网格和C/S的联系和区别，并列举了现今P2P的主要应用，最后，对目前P2P中存在的资源发现与定位问题做了分析和论述。关键字 P2P、资源管理、Gnutella、哈希查找 1 P2P技术简介1.1 概念及特征      P2P是peer to peer的缩写，是指：通过使用分布资源，借助于分布计算技术来完成关键任务的系统和应用的总称。这里的分布式资源包括计算能力、数据（包括存储介质和内容）、网络带宽和其它资源（如计算机、人力资源等）；分布计算包括算法、数据、元数据等，或者是三者总体；关键任务包括分布计算、数据（或内容）共享、通信与协作，或者是平台服务等。       P2P技术的主要特征是弱化服务器作用，甚至取消服务器，使分布式系统中的各个节点逻辑对等，这种技术出现的目的就是希望能够充分利用网络中所蕴含的潜在资源。与C/S模型不同，P2P模型中每个节点既可以是服务（或者资源）的提供者，也可以是使用者，充其量就是提供的服务（或资源）的类型不同。1.2 需求与背景      随着网络技术的飞速发展和网络规模的不断扩大，接入网络的主机增加，可用资源丰富，然而目前的互联网仍然是以C/S模式为主，尤其是Web技术的发展使得许多Web服务器成为信息的主要提供源，整个Internet系统依附于这些少量的服务器节点，而大量的个人主机中的资源却成了网络中的信息孤岛，无法得到充分利用，能否发挥这些闲散资源的使用效率（或者作用）构成了人们关注P2P的理由。1.3 P2P与网格的联系与区别     网格与P2P在技术上没有本质区别，都是在广域网条件下实现资源共享和分布计算。正因如此，全球网格（GGF）与对等网络研究小组（P2PWG）已宣布合并。但二者也有一定的区别。网格类似于电力系统，格点（或者节点）类似发电站，通过整个网络输送给用户，相对于P2P，更象是将一些大型资源组织起来，供社会共享，我国目前正在实施的生物研究网格和网络服务网格都可作为其辅证；P2P则泛指闲散资源的组织。（1）应用面     网格较侧重于重大计算和大型专业性的协同，其一个或多个主要节点仍有较重的服务器色彩；P2P提供普通的信息、计算服务，每个参与者明显地兼有客户、服务器双重身份。（2）访问对象     网格访问计算资源、数据资源、软件资源，相对来说，有较固定的目标；P2P完全是随机访问，随机使用。（3）安全性     网格中每个节点都有身份鉴定、授权、防火墙保护的能力；P2P每个参与者不保证这些能力，甚至是匿名的。（4）控制     网格在资源监视/分配和作业调度上仍有较多的集中控制；P2P仅有很少的或没有集中控制，主要靠自行组织。（5）服务质量     网格确保可靠的服务质量；P2P只有部分的保证，某些参与者甚至是不可信的。以上这些区别是相对而言，随着不断发展和改进，这些区别会逐步缩小。1.4 P2P与C/S的联系     从某种程度上说，也许不应该将P2P和C/S模式完全的对立起来，就某项特定的应用，以及特定的时间，P2P网络也许是以C/S方式进行工作的。例如：如果每个用户都有一些软件资源（例如文字处理程序）或者硬件设施（例如：打印机），，可以采用P2P的方式进行可控共享，此时，提供打印机的客户（本地的某个进程）就临时充当了服务器的角色。再分析一下目前的Web工作方式，我们更多的应用是文件（或者资料）的查找，Web页面成为文件资源的目录，存储对应文件的主机成为提供者，原理上，该主机可以独立于Web服务器，这也可认为是P2P的一种形式。 2  P2P资源发现与定位      目前P2P技术已在文件交换，分布式计算，搜索，信息共享，协同工作，即时通信，网络游戏等等方面得到了广泛的应用，还有一些公司在开发基于P2P的平台。但是，无论是通信、P2P协作、分布式搜索引擎还是共享计算和交互式游戏等功能的实现，都只能以很好解决网内资源的迅速准确定位问题为前提。所以，P2P网络中资源发现是及其重要的。      目前，资源的定位一般采用的是“地址查询”的方法，即：每个资源有一个全局唯一标识符OID和一个包含其所在地址的指针P，系统将<OID,P>保存起来，当用户需要访问该资源时，根据OID来查询P，从而进行定位。定位机制有不同的实现方法。按照实现系统的体系结构，主要可以分为两类：集中目录式、泛洪请求式2.1集中目录式      在集中目录式（Central Index Server）中，有一个类似于服务器的节点集中提供资源索引信息。当用户共享资源时，需将资源的<OID,P>向索引服务器进行资源注册，索引服务器中保存着系统中所有资源的标识符和指针列表。当用户需要查找资源时，首先通过资源标识符查询索引服务器，服务器返回该资源的指针，用户通过该指针定位。当定位到资源的存储位置后，资源的下载在节点之间直接进行，与索引服务器没有关系。      集中式的优点是：简单、容易实现。大多数的分布式系统采用的都是这种方法，例如：三种分布式对象计算环境（CORBA,DCOM,JAVA RMI）提供的分布对象名字服务、大量的通用目录服务（如X.500、LDAP和NIS）和一些实用分布式系统（如Napster）的资源定位方法等。集中式的缺点很明显：类似于C/S模式，缺乏可扩展性和存在单点故障问题。 图1 集中目录式            图2  泛洪请求式           图3 分布式Hash式2.2 泛洪请求式     与集中目录式不同，泛洪请求式（Flooding Request）没有中央目录服务器，用户的请求通过所有连接的节点传递，这些节点或者响应该请求，或者在不能满足请求时，将该请求向与自己相连的其他节点广播，直到请求得到响应为止（泛洪）。为了减少广播带来的网络带宽浪费，一般将广播传递限制在7~8跳以内，即如果请求在经过有限的循环广播之后，仍不能得到响应，则发送请求的节点将得到一个错误信息。       Gnutella是泛洪的经典之作，Gnutella协议设置了三种机制来控制消息数量的指数增长。      机制一:消息生存时间(Time-to-Live简称TTL)       消息生存时间主要是控制消息在网络中传播时能够生存的时间，是消息头中的一个字段，在消息生成时被赋予一个初始值。当消息被发送出去，其它主机结点接收到该消息时，首先将该消息的TTL值减1，如果为零，则将该消息丢弃掉。否则，发给它的邻居结点。TTL值越大，消息能传播的距离就越远，反之，就越近。      机制二:消息的唯一标识符(Unique Message Identification简称UID).      消息的唯一标识符是为了避免一个消息在同一个主机节点重复传播而设计的。UID也被包含在消息头中，每个消息的标识符都是不一样的。当消息被发送出去，其它主机结点接收到该消息时，取出它的消息头中的UID字段，同本地记录的UID列表相比较，如果该消息的UID己经在列表中，说明该主机结点己经看过这条消息，它将直接把这条消息丢弃掉。否则，如果该消息的UID不在本地列表中，该主机结点将储存这条消息的UID到本地UID列表，然后将该消息传播出去。       机制三:路径标识符(Path Identification)。       路径标识符是为了防止消息循环的出现及指导返回消息按原路返回而设置的。路径标识符其实是一个地址列表，记录了该消息所经过的结点的地址。当一个主机结点接收到一条消息后，该主机结点会检查自己的主机地址是否在消息所经过的地址列表中，若在，说明该条消息已经到过该主机结点，则该主机结点会将这条消息直接丢弃。否则，该主机将自己的地址加入消息的地址列表中，然后发送出去。以上三个控制机制保证了消息在中不会被无限制的扩散，从而确保Gnutella网络可以正常的运行。但是，这三种控制机制也不是尽善尽美，也会导致很多问题，其中之一便是短路效应。      泛洪请求式由于通过广播方式进行查找和定位，因此一般扩展性差，但在小范围内效率高，可靠性好。此外如果在系统中存在一些所谓的超级节点（即该节点拥有大量的资源信息），则可以显著减少带宽的浪费。      目前第二代泛洪请求式的资源定位主要采用分布式Hash表算法：赋予系统中每个节点一个全局唯一标识符NID，通过一个哈希函数建立起资源唯一标识符OID和NID之间的对应关系：NID＝HASH(OID)，NID与OID是一对多的关系。将资源的定位信息<OID,P>保存到节点标识符为HASH（OID）的节点上。当用户需要查找对象时，首先通过OID和哈希函数出该资源定位信息所在节点的标识符HASH(OID)，然后将该请求发送到该节点上，即可找到该对象。由于P2P中，任意两个节点可以通讯，并且各个节点上的哈希函数都相同，因此，只要知道对象的OID，用户可以从任何一个节点出发找到该对象。      根据节点的NID与OID之间的映射关系不同，分布式Hash表算法有许多不同的实现形式，如Chord、CAN、Pastry、Tapestry等。目前的最好效率是发现资源需要的路由表长度为logN（N为P2P网络总节点数），查询资源需要的通信量为logN。2.3 现有的问题与改进图 4 短路效应的成因       如上所述，Gnutella中存在着短路效应。如图4所示，假设Gnutella网络上有A,B,C三台主机，当有消息M(TTL=t)由主机A发出，假设有两条路径可以到达主机B，一条路径是沿Ll(x1,x2 ,…,xp),路径长度为p；一条是L2(y 1,y2 ,…,yq)，路径长度为q。另有一条由主机B到主机C的路径L3(z1,…, zr)，路径长度为r，其中有p+r>t且q+r<t。设从路径Ll传递的消息称为M1，把从路径L2传递的消息称为M2。按照Gnutella的传输协议及以上介绍的三种控制机制，从主机A发出的消息，应该能够到达所有的符合以下条件的主机：这些主机距离主机A的跳数小于初始TTL值(从一个主机到另外一个与它直接相连的主机的距离称之为一跳)。按照这条规则，从主机A发出的消息M也应该能够到达主机C，因为存在这样一条路径（y1，…，yq,z1 ,…，zr)，该路径长度(q+r)小于消息的初始TTL值t。但是，由于网络异构延迟的影响，消息M却可能无法到达主机C。原因在于从主机A到主机B的传输过程中，假设从路径Ll传递的消息M1先于从路径L2传递的消息M2到达主机B，主机B在收到M1后，检查它的UID及TTL，发现此UID并不在本地的消息列表中，它的TTL值t-p也大于0，所以它会先记录M1的UID到本地的消息列表，然后将TTL值减去1，最后将M1发送给它的所有的邻居。但是M1肯定无法到达主机C，因为从主机A到主机C的跳数p+r大于消息的初始TTL值。在主机B处理过消息M1后，沿路径L2的消息M2也将到达该主机。因为M2和M1都是同一条消息的两个副本，它们的UID也必然相同，因而当主机B检查消息M2的UID时，会发现该UID己经存在于本地的UID列表中，按照控制机制二，主机B会丢弃消息M2。如此一来，便没有可以到达主机C的消息。这就是短路效应。需要说明的是，当网络规模大到一定的程度时，由于网络结构、带宽等的差异，异构延迟现象的存在是很正常并且是很普遍的。实验表明，在现在的Gnutella网络中，在异构延迟的影响下，消息的可达率一般在55%左右，即一条消息发出后，在应该收到该消息的主机中，约有一半数量的主机实际上收不到这条消息。这就大大降低了整个Gnutella网络的查询效率。      在原来的机制二中，主机结点在检查完消息的UID后，如果发现该UID已经在本地的消息列表中，则直接就将它丢弃了。从以上的分析知道，这是不合理的，因为该消息有可能到达比己经存在的那条消息更远的距离。因此，可以首先保存每一条消息的TTL值，当一个主机结点检查一条消息的UID，发现该UID已经存在时，再检查该消息的TTL值，如果新的消息的TTL值比原来保存的TTL值要大，则将用较大的TTL值替换较小的TTL值，并将该消息继续前传播。这里用较大的TTL值替换较小的TTL值，是考虑到如果后面还有另一个网络延迟更厉害但TTL值更大的副本到达时，主机不会把它丢弃掉。但是，这样改进之后还会引发另外一个返回结果的问题。如图4，当M1到达主机B后，如果它有主机A要查询的数据，则主机B会产生一条回应消息，沿着M1来时的路径传送到主机A。那么当消息M2到达时，主机B还会产生一条回应消息，沿着M2的路径传送到主机A。但是M2的回应消息己经没有必要，因为一是M2的路径延迟要比M1厉害，二是多发送的那条消息是重复的，白白占用了网络的带宽。因此做一个规定，当一个主机先后接收到相同UID的消息后，如果需要回应，只回应第一条消息，其它的在做完TTL及UID检查后，或丢弃，或只简单的传给它的邻居结点。 3  结束语       虽然P2P的概念出现由来已久，但是随着Internet的迅猛近年来对其的研究和应用日益成为热点。目前Intel，SUN 等多家国际IT都在投入相当大的力量研究适用的P2P计算模型及其实现。由于P2P技术在对等计算、协同工作方面的强大优势，今后肯定会在这两个方面迅猛发展；将P2P技术和C/S模式的互联网结合起来，在搜索引擎、文件共享方面国内外已经有不少商业化产品投入使用，但由于P2P技术本身存在不易管理、安全性差等缺陷，造成P2P技术自出现以来，并没有大规模应用，而且这两个问题如果得不到有效解决，将会成为P2P技术在这两个方面发展的主要瓶颈。 1.L.Tassiulas and A.Ephremides,Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks.IEEE Transactions on Automatic Control，Vol 37,No 12,Dec.1992,pp:1936~19482.Dana Moore, John Hebeler著.对等网.清华大学出版社，2003    3.Andy Oram编.Harnessing the benefits fo a disruptive technolody.清华大学出版社，20034.Peer-to-Peer Computing[ EB/OL].http://www.sics.se/perbrand/,20012112035.Karl A ,Magdalena P. Improving Data Access in P2P Systems[J].IEEE Internet Computing,2002,6(1):58-67..6.吕向辰.P2P技术与应用.