P2P网络搜索技术的研究

admin管理员组

文章数量:1530882

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

第

1

期贾杏丹等

:P2P

网络搜索技术的研究　　　

・

71

・

P2P

网络搜索技术的研究

贾杏丹

,

张立臣

(

广东工业大学计算机学院

,

广东广州

510090

)

3

摘　要

:

分布式存储系统以其分布式控制、自组织性和普遍的适应性而受到越来越多的关注。搜索是所有存储

系统的重要组成部分

,

而对终端用户的反应时间是衡量一个搜索引擎优良的重要指标。讨论了目前几种流行的

P2P

网络搜索技术及特点

,

并比较其优劣

,

然后对基于分布式哈希表的搜索技术的几种改进方法进行了分析。

关键词

:P2P;

分布式哈希表

;BloomFilter;Cache

中图法分类号

:TP301

1

6

　　　文献标识码

:A

　　　文章编号

:1001

2

3695

(

2006

)

01

2

0071

2

02

ResearchonSearchTechnologyofP2PNetwork

JIAXing

2

dan,ZHANGLi

2

chen

(

FacultyofComputer,GuangdongUniversityofTechnology,GuangzhouGuangdong

510090

,China

)

Abstract:Interestindistributedstoragesystemisfueledforitsdecentralizedcontrol,adaptationandself

2

isanimportanttechnologyforallstoragesystem,andend

2

userlatencyisthemostimportantperformancemetricforasearch

sesseveralrecentpopularsearchtechnologiesofP2Psystemsandcharacterizesofthistechnologies,andcom

2

parestheiradvantagesanddisadvantages,thenanalyzesseveralimprovedwaysforDHT

2

basedstoragesystem.

Keywords:P2P;DHT;BloomFilter;Cache

　　分布式存储系统以其分布式控制、自组织性和普遍的适应

性而受到越来越多的关注。但是高级搜索技术仍是一个亟待

解决的问题

,

而在一个搜索引擎中对终端用户的反应时间是最

重要的性能指标。在分布式搜索引擎中对最终用户的反应时

间多由网络传输时间决定。因此最小化要发送的比特数和发

送花费的时间单元数是很重要的。在实际的搜索中

,

包含有多

个关键词需由多台主机协同工作才能完成的查询占大多数

,

它

们决定了网络的负载

,

因此对它们进行优化对缩短终端用户反

应时间是很重要的。

性较差的问题。在文献

[9]

中提出了针对

Gnutella

的利用搜索

相近关键词的一组节点构造节点存储的路由表进行组播来减

少洪泛查找所造成的网络流量的失控。

基于分布式哈希表的查找机制

,

如

Chord

[3]

,CAN

[4]

,Pas

2

try

[5]

,Tapestry

等。在

Chord

中每个关键字都保存在它的后

[6]

继节点上

,

查找过程就是不断接近它的后继节点最终到达目的

节点或查找失败。

CAN

基于虚拟的

d

维笛卡儿坐标实现其数

据组织和查找功能。

Pastry

使用最长共同前缀进行匹配查找。

Tapestry

使用邻居映射表进行最长前缀匹配查找

,

并可把消息

传递到最近的存放所要求的对象拷贝的节点。以上介绍的四

1

P2P

网络中常用的搜索技术的分析

具有集中式的目录服务器的搜索机制

(

如

Napster

)

,

在集中

式的目录服务器上存放对等节点的地址信息、元数据和文件的

关键词信息。它可以对请求的查询进行快速地查找并返回最合

适的目的节点。但是随着网络规模的增大

,

目录服务器必然成

为服务瓶颈

,

而且会造成单点失败

,

同时还存在扩展性问题。

采用洪泛查找机制的

P2P

网络

,

如

Gnutella

[2]

种基于分布式哈希表的查找机制有很多相似之处。下面对它

们进行简单的比较如图

1

所示。

由此可知在

Napster

和

Gnutella

中使用的关键词查询的方

法

,

在基于分布式哈希表的

P2P

系统中由于关键词经哈希函

数后成为唯一的关键值

,

就是说基于分布式哈希表查找系统通

过一个不透明的关键值来对文件进行查询。关键值选择的方

法由构筑在

DHT

之上的应用程序所决定

,

它缺少有效的关键

词查询的功能。然而经改进后

,

可以不把关键词的查询直接映

射在存有相应哈希值的节点上。而是映射在一个哈希表上

,

节

点再映射到此哈希表上来提供高效的关键词查询。在实际的

搜索中

,

包含有多个关键词需由多台主机协同工作才能完成的

查询占大多数

,

它们决定了网络的负载

,

所以以下的改良方法

针对多关键词查询。

,Freenet

等。

可以把这种完全分布式的网络看成是一组对等节点之间的自

组网络。节点在进行查找时

,

首先传播到它的所有相邻节点

,

然后在传播到相邻节点的所有相邻节点

,

直至到达预先确定的

层次为止。这种查询机制造成网络通信负担较大

,

也存在扩展

收稿日期

:2005

2

01

2

01;

修返日期

:2005

2

04

2

06

基金项目

:

国家自然科学基金

(

60474072,60174050

)

;

广东省自

然科学基金

(

04009465,010059

)

;

广东省高校自然科学研究资助

项目

(

Z03024

)

;

广东省哲学社会科学规划项目

(

03/04J02

)

・

72

・

计算机应用研究

S

B

→

S

C

:F

(

F

(

A

)

∩

B

)

=F

(

A

∩

B

)

┇

S

Y

→

S

Z

:F

(

F

(

A

∩…∩

X

)

∩

Y

)

=F

(

A

∩

B

∩…∩

Y

)

S

Z

→

S

Y

:F

(

A

∩

B

∩…∩

Y

)

∩

Z

S

Y

→

S

X

:F

(

A

∩

B

∩…∩

Y

)

∩

Z

∩

Y

┇

S

B

→

S

A

:F

(

A

∩

B

∩…∩

Y

)

∩

Z

∩

Y

…∩

B

S

A

→

S

rq

:F

(

A

∩

B

∩…∩

Y

)

∩

Z

∩

Y

…∩

B

∩

A

2006

年

2

　对现有的基于分布式哈希表查找机制的改进方法

2

1

1

BloomFilter

算法

BloomFilter

是一种表示集合的方法

,

并可简洁地测试一

[1]

个元素是否在该集合中

,

它基于哈希函数建立

,

所存储的比特

数远少于它所表示的集合。

P2P

网络传输一个基于集合

A

的

BloomFiter

而非集合

A

本身

,

可以减少需要传输的信息量以降

而且当

|A|

≤

|B|

≤

|C|

≤…≤

|Z|

时可以最优化传输的比特

数。

2

1

2

　缓存

低网络流量。但

BloomFiter

会导致可预算的错误定位率。

BloomFiter

的错误定位率随它尺寸的增大而呈指数降低。集

使用缓存若

S

B

在本地已经存储有

F

(

A

)

或

A

则可以避免

S

A

继续发送。缓存

F

(

A

)

而非

A

本身的话

,

相同的空间可以存

ε

(

S

)

,

ε

(

S

)

是错位定位数。

P

fp

合

S

的

BloomFilter

F

(

S

)

=S

∪

为错误定位率

,

则

-

kn/mK

)

,

(

k

为哈希函数的个数

,m

为

BloomFil

2

P

fp

=

(

1-e

储更多数据的

BloomFilter

。因为关键词出现的概率呈非对称分

布

(

Zipf

分布

)

,

所以这就意味着即使很小的

Cache

都可以有很

高的命中率。平均地看

,

一个

BloomFilter

已存储在另一个节点

的概率

p

与该节点

Cache

的命中率相等。此时式

(

2

)

可优化为

(

1-r

)

m

+0.6185

m

/|A|

|B|j

(

4

)

ter

的尺寸

,

n

是集合中元素的个数

)

哈希函数选择最优化时

,

错误定位率为

f=0.6185

m/n

(

1

)

所以若要保持一定的错误定位率

,

m

必须与

n

成一定的比

例

[7]

。

下面是关于

BloomFilter

的集合操作

把集合

S

转换为它相应的

BloomFilter:

F

(

S

)

←

S

BloomFilter

的交集运算

:

F

(

X

∩

Y

)

←

F

(

X

)

∩

F

(

Y

)

BloomFilter

的并运算

:

F

(

X

∪

Y

)

←

F

(

X

)

∪

F

(

Y

)

BloomFilter

和集合的运算

:

(

X

+

ε

(

X

))

∩

Y

←

F

(

X

)

∩

Y

F

(

X

)

∩

X

=

X

优化

m

后得

m

=|A|log

0.6185

[

(

1-r

)

2.081

|A|

]

|B|j

发送比特数的减少和

Cache

命中率的提高近似成线性关

系。

2

1

3

　结果的处理

请求查询并不需要返回搜索出的所有结果。如果只传输

返回所要求的查询结果

,

可以在很大程度上减少所要传输的信

息量。查询结果的数量与网络中存储的文件的数目成比例

,

所

以用于返回查询结果的带宽和网络规模的增大呈线性增长

,

因

而从系统的可扩展性来说

,

对结果进行整理是很有必要的。而

BloomFilter

和

Cache

都不能减少这种线性的增长

,

所以截去部

优化多关键词搜索重点是降低所用的网络带宽。例如

,

若

服务器

S

A

存放所有含关键词

K

A

的文件集合

A,S

B

存放所有

含关键词

K

B

的文件集合

B

。

|A|

和

|B|

分别表示集合

A

和

B

的大小

(

即它们包含的文件数目

)

。

A

∩

B

是即包含关键词

K

A

又含关键词

K

B

的文件集合。若一个节点

C

查询搜索既包含

关键词

K

A

又含关键词

K

B

的文件即

A

∩

B

。一个直接的方法

是

:S

A

发送集合

A

给集合

B

所在的节点

S

B

。

S

B

计算出

A

∩

B

然后直接发送

A

∩

B

给查询节点

C

。若使用

BloomFilter,S

A

发

送集合

A

的

BloomFilter

F

(

A

)

给集合

B

所在的节点

S

B

。

S

B

计

算并发送

F

(

A

)

∩

B

给

S

A

,S

A

通过计算

A

∩

(

F

(

A

)

∩

B

)(

与

A

∩

B

等价

)

去除错误定位的文件

,

然后发送给节点

C

。

S

A

虽可通过计算

A

∩

(

F

(

A

)

∩

B

)

在最后去除错误定位的

分结果是唯一的方法。

因为

BloomFilter

如果被分割就没有任何实际意义

,

所以

S

A

把本地存储的文件分块

,

发送一个块的

BloomFilter

给

S

B

,

S

B

返回相应块的搜索结果

(

在此期间

S

A

和

S

B

,

保持通信

)

,

直

至达到查询所要求的文件的数目。块的大小依所要返回的文

件数目而定。发送一个关键词文件的分块的

BloomFilter

而不

是所有文件的

BloomFilter

可以减少一个关键词所占用的

Cache

空间

,

从而提高

Cache

的命中率。

2

1

4

　虚拟主机的技术

P2P

系统的一个显著特点就是异构性。随机的分布关键

文件

,

但浪费了带宽。如上

,

节点

S

A

和节点

S

B

的例子中

,

共需

传递的比特数为

m

+P

fp

|B|j+|A

∩

B|j

(

j

是文件标识符的比

特数

)

。

|A

∩

B|j

是所要求的交集本身

,

不能优化。所以可优

化的比特数为

m+P

fp

|B|j

与式

(

1

)

联合可得可优化比特数为

m

+f|B|j=m+0

1

6185

m

/|A|

值可能会导致某个使用频繁的关键词被分配给一个性能不好

的节点。或者一个节点可能被分配与它的处理能力不匹配的

关键词。虚拟主机

[8]

可以降低这种可能性。使用虚拟主机一

个节点可能依它的处理能力被划分为若干个逻辑的节点。

2

1

5

　结果的排序

BloomFilter

和

2

1

3

节中对结果的处理使得对结果按相关

|B|j

(

2

)

当式

(

2

)

取值最小时

m

=|A|log

0

1

6185

(

2

1

081

|A|

)

|B|j

(

3

)

由上可知当

A,B

和

j

固定时

,

优化

m

才能得到最小的传

输比特数

,

所以要合理的选择

BloomFilter

的尺寸大小。而且

当

|A|

和

|B|

不同时优化的性能是非对称的且当

|A|

≤

|B|

时传

输的比特数更少。

BloomFilter

交集处理多关键词查询的技术可以推广到任

度排序更加复杂。

BloomFilter

只是简单地测试一个元素是否

在一个集合中

,

并不提供元素顺序信息和其他数据在文件中位

置的信息

,

甚至因为使用了

BloomFilter

而导致这些排序信息

的丢失。在

2

1

3

节中对结果的处理使用了分块的方法

,

而如果

一个块中文档的

ID

比前一个块的小

,

前一个块文档将优先被

发送。

(

下转第

97

页

)

意多个关键词

,

如下所示

:

S

rq

是请求查询的节点

,

求

A

∩

B

∩…∩

Z

S

rq

→

S

A

:queryforA

∩

B

∩…∩

Z

S

A

→

S

B

:F

(

A

)

第

1

期刘　锋等

:

一类新型的门限分享方案的设计与分析　　　

・

97

・

(

4

)

秘密恢复。当每组中

t

-1

个分享者要恢复秘密时

,

各

()

分享者

P

i

向

D

提交二元组

(

I

i

j

,S

i

)

;D

判断式

(

1

)

是否成立并

以窃取

S

也是不可能成功的

,

因为在恢复时如果双方人数均达

不到

t

-1

时

,

秘密分发者

D

将不会参与秘密的恢复

,

从而由孙

子定理知

S

也不可能被求得。式

(

1

)

可以保证秘密分发者与

分享者间以及组间分享者没有欺诈行为并且在分发者的参与

下能够防止恶意参与者提供虚假的子秘密

;

任何一方企图提供

无效的

a

0

i

以阻止秘密的恢复也是不可能的。当然

,

攻击者要

从公开的数据中导出

a

i

就等同于解离散对数问题

,

因而

a

i

也

是安全的

;

从而只有

P

i

的同组成员才知道

S

i

,

即

S

i

是相对安

()

全的。又因为每个分享者的二元组

(

I

i

j

,f

(

I

i

))

没有泄露

,

所

()

()

且统计出

A

i

组中同意恢复秘密的人数

t

i

,

从而能够判断

t

i

≥

t

-1

是否成立

:

如果不满足

,

D

宣布不能恢复出秘密

;

否则

D

利

()

用

A

j

组内汇集的

(

I

i

j

,f

(

I

i

))

并且利用定理

2

得到一个

t

-1

次

插值多项式

Q

j

(

x

)

,

然后将

Q

j

(

0

)

公开

;

则由

Q

j

(

0

)

和

I

j

以及

定理

2

可得

a

0

=

I

(

1

)

()

2

Q

1

(

0

)

-

IQ

2

(

0

)

()

(

1

)

I

(

2

)

-

I

mod

N

;

然后

P

(

1

)

,P

(

2

)

,

2

D

分别计算模素数的二次同余方程

S

≡

a

0

(

mod

p

)

,

22

S

≡

a

0

(

mod

q

)

,S

≡

a

0

(

mod

r

)

,

均取正整数解

:

()()()

S

≡

a

0

1

(

mod

p

)

,S

≡

a

0

2

(

mod

q

)

,S

≡

a

0

D

(

mod

r

)

以体制能有效地阻止消息重放。

如果

n

个成员分成了更多的有利益冲突的组

,

该方案也能

有效地解决其秘密共享问题

,

只要重复该方案就能类似地解

决

,

并且能够保证多方利益冲突的权利相互牵制和安全恢复所

分享的秘密。这也正是

Nevill

插值公式所保证的。

参考文献

:

并且公开

a

0

1

,a

0

2

,a

0

D

。从而由定理

1

和孙子定理可知

,

任一分享者均可恢复秘密

:

()()()

S

≡

M

1

a

0

1

+

M

2

a

0

2

+

M

D

a

0

D

(

mod

N

)

()()()

3

　安全性分析

I

i

定理

3

　若

a

S

i

≡

b

0

・

b

1

…

b

I

t

i

-1

(

mod

N

)

成立

,

则认为秘密

t

-1

[1]

陈景润

.

初等数论Ⅲ

[M].

北京

:

科学出版社

,1988.145

2

146.

[2]

郑慧娆

,

等

.

数值计算方法

[M].

武汉

:

武汉大学出版社

,2002.

[3]

张建中

,

肖国镇

.

一个可防止欺诈的秘密分享方案

[J].

电子科学

学刊

,1999,21

(

4

)

:516

2

521.

[4]oldCryptography[J].EuropeanTransactionson

Telecommunications,1994,5

(

4

)

:449

2

457.

[5]AsmuthC,arApproachtoKeySafeguarding[J].

IEEETransactionsonInformationTheory,1983,29

(

2

)

:208

2

210.

[6]hareaSecret[J].CommunicationsoftheACM,

1979,22

(

11

)

:612

2

613.

分享者

P

i

拥有的子秘密有效。

t

-1

证明

:

因为

a

S

i

=

a

f

(

I

i

)

=

a

k

=0

∑

a

k

I

k

i

=

∏

(

a

)

k

k

=0

t

-1

aI

k

i

≡∏

b

(

mod

k

=0

t

-1

I

k

i

k

N

)

,

所以当秘密分享者

P

i

拥有的子秘密

S

i

有效时

,

上式成立。

在恢复秘密时

,

虽然

Q

i

(

0

)

,I

j

均公开

,

攻击者能得到

a

0

;

由求模合数平方根的困难性知

,

他无法从

a

0

获得

S;

即使同一

组的

t

个成员联合攻击

,

根据上述分析可知他们也不能从

a

0

获得

S;

因为不知道

n

的因子计算模

n

的平方根问题与分解因

子的问题计算难度相同。另一方面

,

双方的少数成员企图合作

(

上接第

72

页

)

作者简介

:

刘锋

(

1980

2

)

,

男

,

硕士研究生

,

研究方向为密码学

;

张建中

(

1960

2

)

,

男

,

教授

,

博士

,

研究方向为密码学。

dressableNetwork[C].IGCOMM,SanDiego,CA,

2001.161

2

172.

[5]RowstronA,:Scalable,DistributedObjectLoca

2

tionandRoutingforLarge

2

scalePeer

2

to

2

PeerSystems[C].Procee

2

dingofthe18thIFIP/ACMInternationalConferenceonDistributed

SystemsPlatforms

(

Middleware2001

)

Heidelberg,Germany,2001.

329

2

350.

[6]HildrumK,KubatowicaJD,RaoS,

etal.

DistributedObjectLoca

2

tioninaDynamicNetwork[C].

ParallelAlgorithmsandArchitecturesWinnipeg,Manitoba,Canada,

2002.41

2

52.

[7]PatrickReynolds,AminVahdatEfficientPeer

2

to

2

PeerKeyword

Searching[C].ProceedingsofInternationalMiddlewareConference.

RiodeJaneiro,Brazil,2003.21

2

40.

[8]FrankDabek,MFransKaashoek,DavidKarger,

etal.

Wide

2

area

CooperativeStoragewithCFS[C].Proceedingsofthe18thACM

ACMSymposiumonOperatingSystemsPrinciples

(

SOSP

’

01

)

.

Press,NewYork,NY,USA,2001.202

2

215.

[9]MuraliKrishnaRamanathan,VanaKalogeraki,g

GoodPeersinPeer

2

to

2

PeerNetworks[C].IEEE/InternationalParal

2

lelandDistributedProcessingSymposiumFortLauderdale,Florida.

2002.24

2

31.

3

　结论

对分布式的数据进行有效的关键词搜索日益重要起来

,

比

较目前较流行的几种

P2P

的搜索机制

,

基于分布式哈希表的

搜索机制是今后发展的方向。但是相比较

Internet

的

WWW

和

FTP,

以及

Napster

和

Gnutella,

基于分布式哈希表的搜索机

制缺少高效的关键词搜索技术。本文主要介绍了使用关键词

搜索时

,

采用的减少网络流量和缩短对终端用户反应时间的技

术

,

来提高搜索引擎的性能。而把这些技术应用到实际的系统

中还需要更多的实践和改进。

参考文献

:

[1]LiFan,PeiCao,JussaraAlmeid,

etal.

SummaryCache:AScalable

Wide

2

AreaWebCacheSharingProtocol[EB/OL]..

wisc,edu/

～

cao/papers/summary

2

cache/

(

1998

2

5

)

/2004

2

11.

[2]

2

to

2

PeerArchitectureCaseStudy:Gnutella[C].Pro

2

ceedingsofInternationalConferenceonP2PComputing

(

P2P2001

)

,

Linkoping,Sweeden,2001.

[3]StoicaI,MorrisR,KargerD,

etal.

Chord:AScalablePeer

2

to

2

Peer

LookupServiceforInternetApplications[C].IG

2

COMM,SanDiego,2001.149

2

160.

[4]RatnasamyS,FrancisP,HandleyM,

etal.

AScalableContent

2

ad

2

作者简介

:

贾杏丹

(

1982

2

)

,

女

,

河南洛阳人

,

硕士研究生

,

主要研究方向为实时系

统

;

张立臣

,

男

,

硕士生导师

,

博士

,

主要研究方向为实时系统。

本文标签： 搜索查询节点关键词秘密