P2P搜索研究综述

2022-09-11

1 P2P概述

Peer-to-Peer (P2P) 是由若干互联计算机构成的协作系统, 系统依存于边缘化设备的主动协作, 每个成员直接从其他成员而不是从服务器的参与中受益;系统中成员同时扮演服务器与客户机的角色;系统应用的用户能够意识到彼此的存在, 构成一个虚拟或实际的群体。

P2P作为一种全新的分布式计算模式, 受到了学术界和Internet用户群的广泛关注。P2P系统中的结点既作为客户端发出请求, 又作为服务器端提供服务, 消除了传统C/S模式中的单点失败和性能瓶颈问题, 具有更好的容错性和可靠性。

P2P是一个分布的协作系统, 资源共享是其最核心的功能, 资源发布与资源发现是其工作的基础前提。以自组织方式实现全分布环境中的内容分发和资源管理也是目前W e b Service、普适计算等分布式计算领域的研究热点和难点。因此, 对P2P系统中的资源管理、搜索机制、复制策略、路由算法等进行研究, 具有重要的理论价值和现实意义。

2 P2P搜索研究内容

资源搜索定位是P2P系统实现的基本问题和首要问题, 涉及到结点的组织方式、资源的组织方式和信息组织方式等多方面的关键技术;搜索算法设计和体系结构设计相辅相成, 具有统一性;所以P2P搜索一直是P2P计算研究的最核心内容之一。目前P2P搜索的研究内容主要包括以下几个方向:

P2P网络体系结构。体系结构主要研究系统由哪些部分组成以及这些部分之间的组织方式。最基本的说, P2P系统由一系列地位对等的结点组成。结点的组织方式, 主要体现在元信息的管理方式和获取方式, 而P2P搜索往往直接依赖于可使用的信息。对第一代无结构P2P搜索技术的研究主要在网络拓扑结构、消息路由策略、数据复制策略和缓存索引策略等几个方面。基于DHT的第二代结构化P2P系统研究的内容主要在于如何选取拓扑结构和路由算法, 如何增强对复杂性的支持, 如何解决物理邻近性等问题。

分布式数据结构。利用分布式哈稀表算法来管理分布式资源和路由信息, 比目录管理模型有很大改进。和中心结点服务器不同, DHT网络中的各结点并不需要维护整个网络的信息, 而是只在结点中存储其邻近的后继结点信息, 大幅减少了带宽的占用和资源的消耗。基于DHT构造的结构化覆盖网络不需要中心结点服务器, 每个客户端负责一个小范围的路由, 并负责存储一小部分数据, 从而实现整个DHT网络的寻址和存储。分布式数据结构研究的主要内容在于探索研究DHT一类可用于组织可扩展的分布式系统的数据结构、机制或算法。

智能agent和移动agent。移动Agent是一个能在异构网络中自主地从一台主机迁移到另一台主机, 并可与其他Agent或资源进行交互的程序。Agent非常适合在网络环境中来帮助用户完成信息检索的任务。在P2P软件中嵌入移动Agent, 尤其是智能agent, 在个人助手、智能搜索、实现灵活性等方面将具有很大优势。

分布式数据库。一个分布式数据库是由分布于计算机网络上的多个逻辑相关的数据库组成的集合, 网络中的每个结点具有独立处理的能力, 可执行局部应用, 同时每个结点通过网络通讯系统也能执行全局应用。所以, 除了分布式数据库更容易获取全局信息, 分布式数据库的结构功能和P2P数据共享系统具有很强的相似性。此外, 充分研究分布式数据库中的查询描述、查询解析匹配、索引缓存等技术对提高P2P共享系统的性能将会具有很大的推动作用。

3 P2P搜索技术

按照资源组织和资源发现的实现原理, P2P系统可以分为结构化P2P和无结构P2P两类。结构化P2P在结点之间添加确定的连接, 构造规则的覆盖网络, 拥有严格的资源存放规则。结构化P2P效率高, 但是破坏了P2P系统结点自治性, 不能适应网络结点的高度动态性。根据元数据管理方式, 无结构P2P体系结构通常分为集中式、全分布方式和混合式。集中式和混合式通过中心服务器或超级结点提供信息服务, 因此, 容易导致单点失败和性能瓶颈。针对全分布体系结构的搜索算法都是通过查询消息在结点之间的转发、匹配来实现的, 搜索算法的性能主要取决于查询消息路由策略和数据复制策略。

3.1 结构化P2P

在结构化P2P系统中, 每个结点拥有一个系统为之生成的唯一标识符号, 标识决定了结点在系统中的确定位置。相比较而言, 结构化P2P系统能提高系统的查找效率和保证查找的准确性。但结构定义过程中需要解决系统中所包含的大量结点和信息的命名、组织及确定结点的加入/离开方式、容错等问题。对于结构化P2P, 拓扑结构是由算法协议设计确定的, 与搜索路径长度是直接相关的。CAN、Pastry、Chord、Tapestry等都分别从不同角度定义出不同的P 2 P拓扑结构。

最近的研究集中在采用新的拓扑图构建覆盖网络, 以减少路由表容量和路由延时。这些新的拓扑关系的基本原理是在DHT一维空间的基础上引入更多的拓扑结构图来反映底层网络的结构。

D H T类搜索能够自适应结点的动态加入/退出, 有着良好的可扩展性、鲁棒性、负载均匀性和自组织能力。由于覆盖网络采用了确定性拓扑结构, DHT可以提供精确查找。只要目的结点存在于网络中D H T总能发现它, 发现的准确性得到了保证。

D H T类搜索最大的问题是D H T的维护机制较为复杂, 尤其是结点频繁加入退出造成网络波动, 会极大增加D H T的维护代价。另一方面, DHT支持精确关键词匹配查询, 对内容、语义等复杂查询缺乏有效支持。在当前的应用中, 结构化P2P仍然没有得到广泛应用。

3.2 无结构P2P

3.2.1 拓扑结构

在分布式系统中, 拓扑结构指系统中各元素之间的物理或逻辑的互联关系。由于P2P系统假设所有结点在物理层上是完全连通的, 因此, 这里的拓扑结构指结点在应用层上的连接特征。拓扑结构对系统的性能具有重要影响。对全分布的无结构P2P, 拓扑结构对搜索路径长度、搜索成功率、负载均衡等性能指标产生直接影响。

在路由算法确定的前提下, 无结构P2P网络结构会对查询消息在结点的分布造成重大影响;又由于覆盖网络在应用层构造, 构造方式简单灵活, [1]以缩短搜索路径长度为目标, 在给定数据访问频率分布的基础上设计具有特定结构的拓扑, 用来优化搜索性能。[2]旨在建立一种小直径 (O (log N) ) 的随机网络以保证较小的平均搜索路径长度。

在无结构P2P系统中, 结点根据一定原则或者以随机方式确定邻接结点。无结构P2P系统能保证结点的自治性, 更符合系统自组织特征。最初的Gnutella和Freenet自组织网络被证明是基本符合Power law结构的。

基于自组织社区的路由查找算法能保证结点的自主性和系统的自适应性, 有效压缩搜索空间, 相关研究在近几年受到广泛关注。文献[3]将“小世界模型”理论引入P 2 P系统, 对Freenet的性能进行了优化。[4]采用相近的措施, 将具有相同兴趣的节点组织成为一个簇。当发起查询时, 查询消息只在相关兴趣簇内转发, 减小搜索范围以提高效率。但是这种算法缺乏对用户访问的适应性, 当用户访问兴趣以外的内容时性能迅速下降。SETS将结点内容划分成不同的主题区, 并根据主题区建立覆盖网络。SETS构建覆盖网络时借鉴了小世界模型, 在系统中包括两种类型链路, 其中长距离链路与不同主题区互连, 而短距离链路用于创建到区内结点的连接。Khambatti等人在提出了一种基于用户兴趣和结点交互的社区划分策略, 并给出了相应的查找算法。

3.2.2 数据复制

数据复制主要受两方面的影响。首先, 从信息搜索和传输角度, 必须根据用户的信息访问模式建立自适应的数据管理机制, 减少搜索和传输延迟。其次, 从信息访问特征角度, 用户对信息访问的热门度通常呈现一定的分布 (如统计表明, 人们对视频文件、Web文件的访问满足Zipf分布) 。因此, 为实现负载均衡和避免服务过载, 必须在系统中为热门数据和信息提供多副本。

数据复制是实现数据放置目标的重要手段, 也是提高P2P搜索性能最常用的策略。一方面, P2P系统中的结点具有高度动态性, 随时加入和离开系统, 数据复制能够提高数据的可获取性。另一方面, 数据复制在降低用户访问延迟, 消除热点瓶颈, 提高系统可靠性等方面都是显著的。

在给定路由算法、网络拓扑和数据访问频率的基础上, 研究了缩短搜索路径长度的最佳数据副本数量分布。但对于全分布的P2P系统来说, 没有全局信息, 结点动态性强, 很难以精确方式达到数据预期分配并且维持最佳的预期分配。相关工作中一般采用“边访问, 边复制”的方法, 使热点数据拥有较多副本。但这种方法的缺点是不能控制把握每个数据对象在系统中所分配的副本量, 结果往往是热点数据在系统中的副本数量不断增大, 而非热门数据的副本逐渐减少, 甚至在系统中消失。

3.2.3 消息路由

在无结构P2P领域, 路由算法方面的相关工作主要在两个方面, 一是提高盲目搜索中消息数量的可控性, 二是提高基于信息搜索中消息的命中概率。

Flooding是类Gnutella采用的消息转发模式, 查询源将查询消息转发给所有与之相邻的结点。结点收到查询后匹配本地存储是否满足查询, 如果满足, 返回结果;否则继续将查询转发给所有邻居 (Gnutella不管是否满足) 。每个查询消息有一个T T L值, 用于控制查询消息转发次数。每转发一次, TTL值减1, 直至为零丢弃该查询消息。Modified-BFS是对Flooding的“横向”改进, 并非每次都转发给所有邻居结点, 而是随机选择k个以削弱查询消息扩散。Expanding Ring、Iterative Ring是对Flooding的“纵向”改进。查询源首先以较小的TTL值Flooding搜索, 如果搜索失败, 增大TTL值继续搜索, 直到搜索成功或者TTL达到某一上限值。查询者生成k个查询消息, 每个消息在结点之间依次转发传递, 实现搜索。这样的每一个消息被称为walker, 这种搜索算法也称为Random Walks。通过调整walker个数, Random Walks可以在搜索效果和消息开销之间做灵活的折中。但是由于其盲目搜索随机转发的本质, Random Walks搜索性能不能满足要求。

对消息转发模式的改进仅仅使得查询消息在数量规模上变得可控, 并不能提高搜索效率, 因为盲目搜索算法中的每个结点满足查询的概率是相同的, 搜索成功的能力取决于数据副本的“密度”以及所遍历结点的数量。

为此, 有许多工作基于信息路由, 着重提高查询消息转发的效率, 即区分选择最有可能满足查询的结点进行转发。根据Power-law拓扑, 总是选择具有最大度的结点进行转发。首先根据一定的标准判断两个查询的相似性, 然后转发给最近满足相似查询的邻居结点。但总得说来这些工作都只是为了快速发现目的文件, 会导致巨大的网络开销。

3.2.4 信息索引

局部索引 (Local Indices) 策略要求每个结点记录给定半径范围内所有结点存储的文件的索引信息, 因此每个结点都可代表这些结点处理查询请求。Freenet中结点只记录文件标识和所在结点的IP, 最终的期望目标是具有相似键值的文件聚集, 存储相似键值文件的结点聚集。APS的索引内容是邻居结点信息, 包括邻居的地址和命中查询次数等属性, 用来帮助路由。路由索引 (Routing Indices) 策略假设可将文档分成若干种类型, 每个结点维护一张路由信息表, 记录可通过邻接结点获取的各种类型文档的数量。由各结点根据一定度量标准, 结合本地路由表信息选择具有最佳转发因子的结点。信息索引可以提高检索效率, 降低搜索延迟, 减少消息传递, 抑制报文广播。但是相应的带来索引维护开销。

3.2.5 语义搜索

语义W e b、语义网格、语义搜索等语义相关研究是当前的热点。

当前的P2P搜索和信息管理主要是基于关键字的, 由于数据缺乏语义描述形式, 极大限制了对P2P搜索的自动查找、发现、匹配和整合。从整体上说, P2P搜索在语义方面的工作还仅限于覆盖网络构造方面。结点之间根据所存储内容的语义关联程度大小添加或稠密或稀疏的连接。这样就构造了基于语义的覆盖网络。所存储内容与查询之间语义的关联程度形成路由方向感, 路由过程总是选择最近的结点进行查询消息转发。

4 P2P搜索的进一步研究方向

近年来, 工业学术界从体系结构、信息查找、路由机制、系统安全等方面对P2P系统实现涉及的几个关键技术开展了工作。由于对等计算尚处于发展初级阶段, 数据管理、结点组织、信息检索等方面还有许多问题亟待解决。

覆盖网络重组, 降低网络流量。当前的P 2 P应用占用带宽已超过整个网络流量的60%, 成为Internet的“杀手级”应用。而且随着应用普及还有加大的趋势。这一方面在于计费模式的问题, 而更重要的一方面在于P2P数据组织、搜索定位等技术的不完善, 尤其是D H T s往往全局命名, 忽略物理网络结构, 造成带宽的“浪费”。P 2 P系统最大的优点之一在于充分发挥网络边缘计算能力的作用, 进一步工作应该完善覆盖网络构造过程中的物理邻近性问题。P2P网络应该通过个人日志挖掘等手段, 综合考虑物理邻近性、兴趣相近性、计算协作性, 组织成为多重性质社区的多重覆盖网络, 满足搜索定位、及时响应、带宽消耗等多方面的性能需求。

数据组织形式。以线性方式组织数据进行单个文件的关键词匹配不适合提高系统性能。今后的数据组织, 首先要结合当前的自然语言处理技术和语义描述技术, 通过信息抽取、信息分类等技术实现多方位、多层次丰富信息的存储、索引和查询;其次, 要结合语义和本体, 丰富词汇, 满足结点属性描述和数据属性描述的需求。对数据实现基于自然语言处理技术、本体技术、语义技术的自动分类和聚合, 进一步实现个性化搜索、领域化搜索、语义推理智能化搜索, 从而提高搜索性能和服务质量。在进一步工作中可以借鉴语义Web技术, 实现对数据、服务的语义描述, 扩展知识表示语言, 丰富上下文环境, 加强基于日志和语义的自动推理, 实现对P2P数据和服务的自动查找、发现、匹配和整合。

异构融合与协议标准。P 2 P系统充分整合网络边缘资源, 所以P2P系统一个很大的特点是“强之欲强, 弱之越弱”。各个独立的数据共享系统之间形成信息孤岛, 不能共享。而且, 当前P2P领域至今尚没有基本的成型的协议标准。进一步工作应该注重系统之间的互通接口, 加强系统之间的资源整合, 加强系统之间的信息和数据共享。

5 结语

总之, 当前的P2P搜索研究已经不仅仅停留在可行性研究阶段, 而是以专业化、个性化、智能化为目标, 综合带宽节约、负载均衡等性能要求, 提高成功率、响应时间方面的服务质量需求。这些问题的解答不仅对提高P2P系统性能、改善网络带宽利用具有重要的现实意义, 而且对当前web service中的资源发布、普适计算中的资源管理等也具有极其重要的参考借鉴价值。

摘要：Peer-to-Peer (P2P) 是一种可扩展的分布式系统, 系统中的物理节点在逻辑上具有相同的地位。P2P系统中的结点既作为客户端发出请求, 又作为服务器端提供服务, 消除了传统C/S模式中的单点失败、信息孤岛和性能瓶颈问题, 具有更好的容错性和可靠性。P2P信息共享系统结构以及P2P搜索算法已经成为当前分布式系统的研究重点和热点之一。本文回顾P2P的研究内容和研究方法, 介绍了P2P的发展现状, 分析了P2P研究热点以及存在的难题, 并对进一步的发展方向做了展望。

关键词：Peer-toPeer (P2P) ,P2P搜索,结构化P2P,无结构P2P,P2P复制,路由算法