一个P2P搜索引擎的架构和实现

admin管理员组

文章数量:1532440

2024年3月9日发(作者：)

维普资讯

Ｍｉｃｒｏｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏｉ．２３，Ｎｏ．６，２００７　

文章编号：１００７－－７５７Ｘ（２００７）０６－－００３２－－０３　

一

开发应用　微型电脑应用　２００７年第２３卷第６期　

个Ｐ２Ｐ搜索引擎的架构和实现　

郑仲伟，郑有才　

摘　要：Ｐ２Ｐ搜索技术是Ｐ２Ｐ研究中的一个重要的领域。本文介绍了一个基于Ｐ２Ｐ结构化覆盖网络的分布式搜索引擎的架　

构和实现。该搜索引擎采用了三层架构，良好的层次架构减少了搜索引擎核心算法与Ｐ２Ｐ覆盖网络协议和具体应用间的依赖，使　

得搜索引擎可以移植到不同的Ｐ２Ｐ结构化覆盖网络之上。由于Ｐ２Ｐ搜索过程中会消耗大量的网络带宽，所以该搜索引擎使用了　

一

些优化算法，它们不仅减少搜索过程带来的带宽消耗，而且保证了系统的可伸缩性。　

关键词：Ｐ２Ｐ；ＤＨＴ；Ｐ２Ｐ搜索引擎；架构　

中图分类号：ＴＰ３９３　文献标识码：Ａ　

近年来，基于对等网络（Ｐｅｅｒ—ｔｏ—Ｐｅｅｒ，Ｐ２Ｐ）技术的资　

源共享系统已经被广泛使用，这些系统拥有的信息资源也越　

来越丰富，这使得这些系统的用户迫切期望有一个良好的　

个地址空间（数字空间　。］［。］［　或是ｄ维的笛卡尔空间　］）中的　

一

点。ＤＨＴ具有这样的能力，可以把目的地为地址空间中的　

某一点的消息路由到在某种量度方法上标识符离该点最近的　

节点上。这种路由不需要节点有全局的知识，只需要每个节点　

维护一个包含若干必要的节点信息的路由表　消息将在节点　

间转发，每次转发都在不断逼近目标地址，若干跳之后就可以　

路由到离目标地址最近的节点。只要让数据项关联地址空间　

中的一个点，利用ＤＨＴ的路由能力，就可以在多个分布节点　

上实现类似哈希表的数据存储和检索操作。　

Ｐ２Ｐ搜索引擎能够帮助他们从数量庞大的资源中找到所需要　

的资源。相对于集中式搜索，Ｐ２Ｐ搜索能够更加充分的挖掘网　

络边缘资源，而且Ｐ２Ｐ搜索不需要专门的高性能的索引服务　

器，也不会有单点故障等问题。这些因素使得Ｐ２Ｐ搜索技术的　

研究成为了Ｐ２Ｐ研究中的一个热门的领域。　

目前有两种基本的Ｐ２Ｐ搜索技术　］，一种是利用洪泛技　

术将查询传播到Ｐ２Ｐ网络上的部分或全部节点上，这些节点　

返回其本地的查询结果，这种技术通常用于Ｐ２Ｐ非结构化覆　

盖网络中。另一种则建立在基于Ｐ２Ｐ结构化覆盖网络　］【３］ｎⅡ５］　

的分布式哈希表（Ｄｉｓｔｒｉｂｕｔｅｄ　Ｈａｓｈ　Ｔａｂｌｅ，ＤＨＴ）上，这种技术　

２　Ｐ２Ｐ搜索技术　

Ｐ２Ｐ搜索主要有两种基本的技术：按文档分割（Ｐａｒｔｉｔｉｏｎ　

ｂｙ　ｄｏｃｕｍｅｎｔ，ＰＢＤ）和按关键字分割（Ｐａｒｔｉｔｉｏｎ　ｂｙ　ｋｅｙｗｏｒｄ，　

ＰＢＫ）Ｅ１］。　

在ＤＨＴ构建出一个全网络的分布式的倒排索引，对于每个查　

询，只需要获取查询关键字对应的倒排列表，然后将这些列表　

进行并运算，就可以获得符合查询要求的所有结果。　

本文将介绍一个基于ＤＨＴ的Ｐ２Ｐ搜索引擎的架构和实　

在第一种技术中，文档在节点之间分配，每个对等节点负　

责一部分文档，并维护一个它所负责的文档的本地倒排索引。　

现，该系统具有三层的体系结构，层次架构将搜索引擎核心算　

法与Ｐ２Ｐ覆盖网络协议和具体应用逻辑分离开来，减少了这　

三者间的依赖关系，使得系统具有较好的灵活性和可扩展性。　

本文的组织结构是这样：首先简要介绍了ＤＨＴ的概念，　

接着介绍两种基本的Ｐ２Ｐ搜索技术，然后详细　

描述搜索引擎采用的层次架构及实现中使用到的优化技　

术，最后是结束语。　

每个查询都必须广播或者洪泛到部分或全部对等节点，每个　

收到查询的对等节点查询本地索引，并返回查询结果中排序　

最靠前的若干文档的信息。这项技术通常在非结构化覆盖网　

络中使用，如ＧｎｕｔｅｌｌａＣ　和ＫａｚａＡ￣　。ＰＢＤ技术简单、健壮，但　

是缺点也很明显，它的查询低效、带宽消耗严重、查全率不高，　

不适合大规模的Ｐ２Ｐ网络。　

ｌ　ＤＨＴ　

第二种技术则是建立在ＤＨＴ上。ＤＨＴ上的每个节点维　

护着若干关键字的倒排列表，每个关键字所对应的倒排列表　

ＤＨＴ提供了一个在多个分布计算节点上的哈希表抽象。　

ＤＨＴ中的每个节点被赋予一个唯一的标识符，该标识符是某　

是由网络中包含了该关键字的所有的文档信息组成，所有的　

节点上的倒排列表共同组成了一个全网络的分布式的倒排索　

作者简介：郑仲伟，西安电子科技大学信息系统技术实验室，西安

郑有才，西安电子科技大学信息系统技术实验室，西安

・３２・　

７１００７１　

７１００７１　

维普资讯

Ｍｉｃｒｏｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．２３，Ｎｏ．６，２００７　开发应用　微型电脑应用　２００７年第２３卷第６期　

引。ＤＨＴ被用来映射一个关键字到负责它的对等节点。一个　

包含多个关键字的查询只需要从这些关键字所对应的节点上　

数据，它通过哈希函数映射到ＤＨＴ的地址空间上，它可以是　

任何数据类型。存储管理器提供的接口很简单，主要有ｓｔｏｒｅ　

获取索引列表，然后进行并运算，就能够获得网络中符合要求　

的所有结果。ＰＢＫ技术高效、查询效果好，而且它可以让我们　

利用几十年来在倒排索引方面的研究成果。但是由于查询过　

程需要传送的倒排列表可能很大，ＰＢＫ技术也同样面临着带　

宽消耗严重的问题ｌ８］。　

本文所描述的搜索引擎采用的是ＰＢＫ技术。为了减少带　

宽消耗，在实现中要尽可能减少传送倒排列表。对于多关键字　

查询，通常先判断多个关键字对应的倒排列表的大小，将最小　

的倒排列表发送到较大的倒排列表所在的节点，由后者执行　

（）、ｒｅｔｒｉｅｖｅ（）、ｒｅｍｏｖｅ（），它们分别用于存储、检索和删除数　

据。ＤＨＴ模块和搜索引擎层都需要使用存储管理器来存储或　

检索节点负责的关键字的倒排列表。　

ＤＨＴ模块实现Ｐ２Ｐ结构化覆盖网络协议，并为上层提供　

使用接口，如图２所示。目前ＤＨＴ模块实现的协议是Ｋａｄｅｍｌｉ—　

ａｌ５］

。

ＤＨＴ模块使用异步编程方式实现Ⅲ１　，从图２可以看到这　

些接口函数都是异步函数，都提供了回调函数参数ｃａｌｌｂａｃｋ和　

ｅｒｒｂａｃｋ，当函数执行完毕后，就会调用ｃａｌｌｂａｃｋ函数处理返回　

结果，如果函数执行过程中出现错误，则调用ｅｒｒｂａｃｋ处理。　

ｊｏｉｎ函数可以用来加入到一个现存的Ｐ２Ｐ网络或者创建　

一

两个倒排列表的并运算，重复这样的动作直到在最大的倒排　

列表所在的节点上完成最后的并运算。完成最后的并运算的　

节点将最终结果排序，然后返回少量排名最高的结果给查询　

节点。这样的流程可以减少很多带宽消耗。　

个新的覆盖网络，参数ｉｐ和ｐｏｒｔ表示ＩＰ地址和端口号，如　

果是创建一个新网络，则将ｉｐ和ｐｏｒｔ这两个参数设为空。当要　

离开网络时应该调用ｌｅａｖｅ，它会处理各种善后事宜。ｌｏｏｋｕｐ　

函数是ＤＨＴ最基本的函数，它将一个ｋｅｙ映射到网络中的一　

３引擎架构和实现　

个节点，它是ｐｕｔ和ｇｅｔ函数的基础。ｐｕｔ和ｇｅｔ函数具有类似　

哈希表的ｐｕｔ和ｇｅｔ的语义，前者将关联一个ｋｅｙ的数据存储　

３．１架构简介　

到ＤＨＴ上，后者从ＤＨＴ获取关联ｋｅｙ的所有数据，ｖａｌｕｅ是要　

存储的数据，可以是任何类型。ｐｉｎｇ用于与一个已知的节点的　

本文描述的搜索引擎使用Ｐｙｔｈｏｎ作为编程语言。该搜索　

引擎采用了三层的架构，分别为基础设施层、搜索引擎层和应　

用层，如图１所示。　

应用层　

通信，它的第一参数ｎｏｄｅ表示已知节点，参数ｍｓｇ表示要传输　

给节点的消息，当这个参数为空时，ｐｉｎｇ函数用于判断已知节　

点是否还存在。　

搜索引擎层　

基础设施层　

图１　系统的体系结构　

基础设施层主要是为上层提供ＤＨＴ的使用接口，隐藏具　

体的结构化网络协议的细节，这使得搜索引擎移植到不同　

Ｐ２Ｐ结构化网络时不用改变上层实现。搜索引擎层是搜索引　

擎的核心，它实现了文档的标引、倒排列表的发布和维护，及　

３．３搜索引擎层　

图２　ＤＨＴ模块的接口　

搜索引擎层是搜索引擎的核心，它包括三个模块：标引模　

块、查询模块及倒排索引发布和维护模块。　

标引模块负责分析文档，从文档中提取出必要的信息，并　

建立本地索引。标引模块利用开放源代码的全文索引引擎工　

具包ＬｕｃｅｎｅⅢ１　的Ｐｙｔｈｏｎ语言版本ＰｙＬｕｃｅｎｅｌ１　来实现。Ｐ２Ｐ　

Ｐ２Ｐ搜索实现，实现中，搜索引擎还采用了一些优化算法来减　

少带宽消耗。应用层的目的是利用搜索引擎层实现各种应用，　

并提供给用户访问控制界面。　

这样的分层架构可以降低搜索引擎核心算法与覆盖网络　

和具体应用间的耦合程度，可以容易的用新的实现来替换原　

有层次的实现，可以容易的对某一层进行扩展和修改而不影　

响其他层。　

３．２基础设施层　

索引发布和维护模块启动一个独立的线程，负责将从本地索　

引文件中将各关键字对应的倒排列表发送到关键字对应的节　

点上，并维护这些数据的可用性。查询模块按照第２节所描述　

的ＰＢＫ技术实现了Ｐ２Ｐ搜索。为了减少Ｐ２Ｐ搜索中的带宽消　

基础设施层包括存储管理器和ＤＨＴ两大部分。存储管理　

器的任务是存储和检索由关联某个ｋｅｙ的数据。ｋｅｙ用于定位　

耗，在实现时还采用一些优化算法，主要有Ｂｌｏｏｍ　ＦｉｌｔｅｒⅢｑ］和　

渐增结果技术Ⅲ１］。　

・３３・　

维普资讯

Ｍｉｃｒｏｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏｉ．２３，Ｎｏ．６，２００７　

３．３．１　Ｂｌｏｏｍ　Ｆｉｌｔｅｒ　

开发应用　微型电脑应用　２００７年第２３卷第６期　

目前该搜索引擎已经实现了一个原型，在下一步工作中，　

本文作者将对该原型进行进一步的开发和优化，加强它的实　

用性，并利用此搜索引擎进行更深入的Ｐ２Ｐ搜索技术的研究。　

Ｂｌｏｏｍ　Ｆｉｌｔｅｒ利用一组哈希函数将一个集合的元素压缩　

成一个位串，而且它能够有效地支持集合元素的查找操作和　

高效的集合的并运算，而只需要付出很小的失误定位（ｆａｌｓｅ　

ｐｏｓｉｔｉｖｅ）的代价，所以它被广泛的应用在需要表达庞大数据　

参考文献：　

集及提高查找效率的系统中。　

本文描述的搜索引擎使用Ｂｌｏｏｍ　ｆｉｌｔｅｒ技术来压缩搜索　

过程中传输的关键字的倒排列表，这大大减少通信的开销。为　

了减少由Ｂｌｏｏｍ　Ｆｉｌｔｅｒ带来的失误定位，最后的结果将依次传　

到参与节点，让各个节点过滤掉失误定位导致的错误结果。　

３．３．２渐增结果　

［１］Ｐ．Ｒｅｙｎｏｌｄｓ　ａｎｄ　Ａ．Ｖａｈｄａｔ．Ｅｆｆｉｃｉｅｎｔ　Ｐｅｅｒ—ｔＯ—Ｐｅｅｒ　

Ｋｅｙｗｏｒｄ　Ｓｅａｒｃｈｉｎｇ［，Ｊ］．Ｍｉｄｄｌｅｗａｒｅ’０３，２００３．　

［２］Ｉ．Ｓｔｏｉｃａ，Ｒ．Ｍｏｒｒｉｓ，Ｄ．Ｋａｒｇｅｒ，Ｍ．Ｆ．Ｋａａｓｈｏｅｋ，ａｎｄ　

Ｈ．Ｂａｌａｋｒｉｓｈｎａｎ．Ｃｈｏｒｄ：Ａ　Ｓｃａｌａｂｌｅ　Ｐｅｅｒ—ｔＯ—ｐｅｅｒ　

Ｌｏｏｋｕｐ　Ｓｅｒｖｉｃｅ　ｆｏｒ　Ｉｎｔｅｒｎｅｔ　Ａｐｐｌｉｃａｔｉｏｎｓ口］．Ｉｎ　Ｐｒｏｃｅｅｄ—　

ｉｎｇｓ　ｏｆ　ＡＣＭ　ＳＩＧＣＯＭＭ　２００１．　

用户很少需要所有关键字检索的结果　事实上，对于任何　

给定的查询条件，满足它的结果的数量与网络中的文件的数　

量是大致成正比的，因而返回所有结果给客户的带宽消耗将　

随着网络大小线性的增长。如果只返回给用户所需数目的结　

果，发送的信息量可以极大的减少。　

［３］Ｒｏｗｓｔｒｏｎ，Ａ．ａｎｄ　Ｐ．Ｄｒｕｓｃｈｅ１．Ｐａｓｔｒｙ：Ｓｃａｌａｂｌｅ，ｄｉｓ—　

ｔｒｉｂｕｔｅｄ　ｏｂｊｅｃｔ　ｌｏｃａｔｉｏｎ　ａｎｄ　ｒｏｕｔｉｎｇ　ｆｏｒ　ｌａｒｇｅ　ｓｃａｌｅ　ｐｅｅｒ～　

ｔＯ—ｐｅｅｒ　ｓｙｓｔｅｍｓ．ｉｎ　ＩＦＩＰ／ＡＣＭ　Ｍｉｄｄｌｅｗａｒｅ．２００１．Ｈｅｉ—　

ｄｅｌｂｅｒｇ，Ｇｅｒｍａｎｙ．　

渐增结果技术是让节点只发送部分倒排列表参与倒排列　

表的并运算，产生的结果是所有结果的一个子集，如果这个子　

集中结果的数量不能满足用户的要求，那么节点继续发送另　

一

［４１８．Ｒａｔｎａｓａｍｙ，Ｐ．Ｆｒａｎｃｉｓ，Ｍ．Ｈａｎｄｌｅｙ，Ｒ．Ｋａｒｐ，ａｎｄ　

Ｓ．Ｓｈｅｎｋｅｒ．Ａ　ｓｃａｌａｂｌｅ　ｃｏｎｔｅｎｔ　ａｄｄｒｅｓｓａｂｌｅ　ｎｅｔｗｏｒｋ［，Ａ］．　

Ｉｎ　Ｐｒｏｃ．２００１　ＡＣＭ　ＳＩＧＣ０Ｍ　Ｃｏｎｆｅｒｅｎｃｅ［Ｃ］．Ｂｅｒｋｅｌｅｙ，　

ＣＡ，Ａｕｇｕｓｔ　２００１．　

部分倒排列表进行新的计算。直到获得数量足够满足用户　

要求的结果。　

［５］Ｐ．Ｍａｙｍｏｕｎｋｏｖ　ａｎｄ　Ｄ．Ｍａｚｉｅｒｅｓ．Ｋａｄｅｍｌｉａ：Ａ　ｐｅｅｒ—ｔｏ　

—

渐增结果技术只获取能满足用户需要的结果，同时减少　

ｐｅｅｒ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｘｏｒ　ｍｅｔｒｉｃ［Ａ］．　

了倒排列表的发送，它有效的减少了Ｐ２Ｐ搜索带来的带宽消　

耗，使搜索带来的开销不受网络中文档数量增长的影响，这让　

搜索引擎具有更好的可伸缩性，在网络规模增大的情况下仍　

能保持较好的性能。　

３．４应用层　

Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＰＴＰＳ０２［Ｃ］．Ｃａｍｂｒｉｄｇｅ，ＵＳＡ，Ｍａｒ．　

２００２．　

［６］Ｇｎｕｔｅｌｌａ．ｈｔｔｐ：／／ｇｎｕｔｅｌｌａ．ｗｅｇｏ．ｃｏｍ．　

，［７］Ｋａｚａａ．ｈｔｔｐ：／／ｗｗｗ．ｋａｚｚａ．ｃｏｒｎ．　

，［８］Ｊｉｎｙａｎｇ　Ｌｉ，Ｂｏｏｎ　Ｔｈａｕ　Ｌｏｏ，ｅｔｃ．Ｏｎ　ｔｈｅ　Ｆｅａｓｉｂｉｌｉｔｙ　ｏｆ　

Ｐｅｅｒ—ｔＯ—Ｐｅｅｒ　Ｗｅｂ　Ｉｎｄｅｘｉｎｇ　ａｎｄ　Ｓｅａｒｃｈ［Ｊ］．ＩＰＴＰＳ　

２００３．　

应用层的目的是利用底层提供的接口灵活的实现各种应　

用，并提供给最终用户控制界面和访问界面。目前，应用层实　

现了一个简单的ｗｅｂ服务器，它提供给用户简单的ｗｅｂ访问　

界面，用户通过ｗｅｂ页面提交查询，并从ｗｅｂ页面上浏览查询　

结果。　

［９］肖明忠，代亚非．Ｂｌｏｏｍ　Ｆｉｌｔｅｒ及其应用综述［Ｊ］．计算机　

科学，２００４　

，［１０］Ｌｕｃｅｎｅ．ｈｔｔｐ：／／ｌｕｃｅｎｅ．ａｐａｃｈｅ．ｏｒｇ／　

，［１１］ＰｙＬｕｃｅｎｅ．ｈｔｔｐ：／／ｗｗｗ．ｉｎｉｔｄ．ｏｒｇ／ｔｒａｃｋｅｒ／ｐｙｓｑｌｉｔｅ　

４结束语　

［１２］Ｒ．Ａ．Ｂａｅｚａ－－Ｙａｔｅｓ　ａｎｄ　Ｂ．Ａ．Ｒｉｂｅｉｒｏ—Ｎｅｔｏ．Ｍｏｄｅｒｎ　

Ｉｎｆｏｒｍａｔｉｏｎ　Ｒｅｔｒｉｅｖａｌ［Ｊ］．ＡＣＭ　Ｐｒｅｓｓ／Ａｄｄｉｓｏｎ—Ｗｅｓ—　

本文介绍了一个基于ＤＨＴ上的搜索引擎的架构和实现，　

它的层次架构使得它具有较好的灵活性和可扩展性，使得搜　

ｌｅｙ，１９９９．　

，［１３］Ｇｌｙｐｈ　Ｌｅｆｋｏｗｉｔｚ．Ｎｅｔｗｏｒｋ　Ｐｒｏｇｒａｍｍｉｎｇ　ｆｏｒ　ｔｈｅ　Ｒｅｓｔ　ｏｆ　

Ｕｓ［，ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｚｏｔｅｃａ．ｃｏｍ／ｉｎｆｏｒｍａｔｉｏｎ／　

ｗｐ／ｔｗｉｓｔｅｄｕｓｅｎｉｘ．ｐｄｆ　

索引擎可以方便地被修改和扩展，可以方便地移植到不同的　

Ｐ２Ｐ结构化覆盖网络之上，并应用到不同的应用中去　本文还　

介绍了使用到的几个优化技术，这些技术可以减少Ｐ２Ｐ搜索　

过程中带来的带宽消耗，能够使搜索引擎具有更好的可伸缩　

性。　

［１４］Ｒ．Ｈｕｅｂｓｅｈ　ｅｔ　ａ１．Ｑｕｅｒｙｉｎｇ　ｔｈｅ　ｉｎｔｅｒｎｅｔ　ｗｉｔｈ　ｐｉｅｒ［－Ａ１．　

Ｉｎ　ＶＬＤＢ．ｐａｇｅｓ　３２１—３３２，２００３．　

（收稿日期：２００６—０９—０６）　

・３４・　

本文标签： 搜索引擎节点网络结果查询