（计算机软件与理论专业论文）基于p2p的分布式搜索引擎体系研究.pdf

l 暂钾r 囊害 p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究兰州大学硕十学短论文 摘要 随着互联网的飞速发展，人们享受着丰富的网络资源，但能够满足用户个性 化需求的网络服务非常匮乏。于是，产生了庞大的数字化网络信息与有限的获取 所需信息能力的尖锐矛盾，并且随着网络及其资源的急速膨胀而日益突出。搜索 引擎在一定程度上解决了这个矛盾，但仍存在一些亟待解决的问题，诸如如何实 现基于内容的视频，音频等多媒体信息的援索，如何提高海量数据上的检索更新 效率，如何有效存储海量数据。 解决上述问题已成为下一代搜索引擎技术的研究方向。目前流行的对等网络 具有分布式、可量铡性、负载平衡的优点，为解决这些问题提供了可能性。本文 在深入研究p 2 p 技术和搜索引擎技术的基础上，大胆地结合局部遍历型搜索技 术与p 2 pc h o r d 协议，提出了一个基于p 2 p 的分布式搜索引擎系统方案 ( p 2 f b a s c dd i s t r i b u t e ds e a r c he n # n e ，p p d s e ) 。该系统方案可有效地减少相似 度查询的计算复杂性，提高查询效率；并且在海量数据存储与查询操作并发方面 占有优势。该系统方案具有技术上的先进性和操作上的可行性 p p d s e 系统方案包含两个模块，p p d s e a g e n t 和p p d s e f o c k c t 。p p d s e a g e n t 为用户提供注册服务，是p p d s e 系统的智能代理服务中心；p p d s ep o c k e t 是 p p d s e 系统的核心部分，设计为三层框架结构，用户应用层、控制层、数据层。 其中，用户应用层提供用户查询、上传数据资料等功能；控制层使用局部遍历型 搜索技术对信息进行聚类，建立信息树，将多维空问上的相似度度量问题转化成 一维度量空间上的间隔问题；数据层提供了快速的资源定位机制、高效的结点路 由机制和并行处理机制，提出了将局部遍历搜索应用于c h o r d 协议上的s e c h o r d 算法。 关键词：局部遍历型搜索技术、p 2 f 、c h o r d 、s e ，c h o r d 算法 麓钾r ：害p p d s e 基于p 2 p 的骨布武搜索弓j 擎系统研究兰州大学硕十学短论文 a b s t r a c t w i t ht h ei n t e m e t sr a p i dd e v e l o p m e n t ，p e o p l ea r ee n j o y i n gt h er i c hn e t w o r k r e s o u r c e s ，b u tt h en e t w o r ks e r v i c e st h a tm e e tt h eu s e i s i n d i v i d u a l i t yn e e d sa r e d e f i c i e n t s o ，t h ei n c i s i v ec o n t r a d i c t i o na p p e a r sb e t w e e nt h eh u g cd i g i t i z e dn e t w o r k i n f o r m a t i o na n dt h el i m i t e da b i l i t yo fg a i n i n gi n f o r m a t i o n ，w h i c hi sp r o m i n e n td a yb y d a yw i t ht h er a p i di n f l a t i o no ft h en e t w o r ka n di t sr e s o u r c e s i nt h ec e r t a i nd e g r e et h e s e a r c he n g i n eh a sr e s o l v e dt h i sc o n t r a d i c t i o n ，b u tt h e r ea r es o m ep r o b l e m sa w a i t e dt o b es o l v e du r g e n t l y s u c ha sh o wt oa c h i e v et h er e t r i e v a lo fm u l t i m e d i ai n f o r m a t i o n , h o wt oe n h a n c et h er e t r i e v a le f f i c i e n c yi nt h em a g n a n i m o u sd a t aa n dh o wt os t o r et h e m a g n a n i m o u sd a t ae f f e c t i v e l y i th a sb e c o m et h er e s e a r c hd i r e c t i o no ft h en e x tg e n e r a t i o ns e a r c he n g i n e t e c h n o l o g y a tp r e s e n tt h ep o p u l a rp e e r - t o - p e e rn e t w o r kh a sm a n ym e r i t s ，s u c ha s d e c e n t r a l i z a t i o n , l o a db a l a n c e ，s c a l a b i l i t ya n ds oo u ，w h i c hp r o v i d e st h ep o s s i b i l i t yt o s o l v et h ea b o v ep r o b l e m s b a s e do nt h es t u d yo ft h ep 2 pt e c h n o l o g ya n dt h es e a r c h e n g i n et e c h n o l o g y ，t h i sa r t i c l ei n t e g r a t e st h el o c a ls p r e a d i n gs e a r c ht e c h n o l o g ya n d t h ep 2 pc h o r dp r o t o c 0 1 a n dp r o p o s e sas o l u t i o n o ft h eb a s e d p 2 pd i s t r i b u t i o n a l s e a r c he n g i n e ( p p d s e ) w h i c hr e d u c e st h ei s s u eo fs i m i l a r i t ya n db r i n gt w o b e n e f i t s ( d i s t r i b u t i o no ft h es t o r a g ea n dp a r a l l e l i z a t i o no ft h et i m e - c o m s u m i n gq u e r y e x e c u t i o n 、i ti sa d v a n e e di ut h et e c h n o l o g ya n df e a s i b l ei nt h eo p e r a t i o n 。 t h ep p d s es o l u t i o nc o n t a i n st w om o d u l e sw h i c ha r et h ep p d s ea g e n tm o d u l e a n dt h ep p d s ep o c k e tm o d u l e t h ep p d s ea g e n tm o d u l ep r o v i d e st h er e g i s t r a t i o n s e r v i c e w h i c hi st h ei n t e l l i g e n ta g e n ts e r v i c ec e n t e r0 ft h ep p d s es o l u t i o n 。t h e p p d s ep o c k e tm o d u l ei st h em o s tc o r em o d u l eo ft h ep p d s es o l u t i o n , w h i c 五 c o n t a i n st h r e es t r u c t u r e s ：t h ea p p l i c a t i o nl e v e lf o ru s c l s ，t h ec o n t r o ll e v e la n dt h ed a t a l e v e l t h ea p p l i c a t i o nl e v e lp r o v i d e st h ef u n c t i o n so fs e a r c h i n ga n du p l o a d i n gd a t a r e s o u r c ef o ru s e ：i s t h ec o n t r o ll e v e lu s e st h el o c a ls p r e a d i n gs e a r c ht e c h n o l o g yw h i c h g a t h e r st h ek i n do fi n f o r m a t i o na n dc o n s t r u c t st h ei n f o r m a t i o nt r e e t r a n s f o r m i n gt h e s i m i l a rm e a s u r eq u e s t i o n si nm u l t i - d i m e n s i o n a ls p a c ei n t ot h eg a pq u e s t i o ni nt h e o n e - d i m e n s i o n a lm e t r i cs p a c e t h ed a t al e v e lp r o v i d e st h ef a s tl o c a l i z a t i o n m e c h a n i s mo fr e s o u r c e s ，t h ee f f e c t i v er o u t em e c h a n i s mo fp o i n t sa n dt h ep a r a l l e l p r o c e s s i n gm e c h a n i s m ，a n di tp u tf o r w a r dt h es e - c h o r da l g o r i t h mw h i c hm a k e st h e l o c a ls p r e a d i n gs e a r c ht e c h n o l o g ya p p l yo nt h ec h o r dp r o t o c 0 1 k e yw o r d s ：t h el o c a ls p r e a d i n gs e a r c ht e c h n o l o g y , p 2 p , c h o r d ， s e c h o r d a l g o r i t h m - 1 1 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名： 鞠乌 日期：至艺：! ! ! ! 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：皇吐导师签名：e 盘遵兰日期：兰叠型 篱，岬矢害 p p d s e 一肇于p 2 p 的分布式锼素。；l 擎系统研究 兰州大学颈 学位论文 1 1 研究工作背景 第一章前言 随着互联网的飞速发展，人们享受着丰富的网络资源，但能够满足用户个 性化需求的网络服务非常匮乏。于是，产生了庞大的数字化网络信息与有限的 获取所需信息能力的尖锐矛盾，并且随着网络及其资源的急速膨胀而日益突出。 搜索引擎在一定程度上解决了这个矛盾，但仍存在一些亟待解决的问题，诸如 如何实现基于内容的视频、音频等多媒体信息的搜索，如何提高海量数据上的 检索更新效率，如何有效存储海量数据。解决这些问题已成为下一代搜索引擎 技术的研究方向。 近年来，对等网络( p e e r - t o p e e r n e t w o r k ，l y 2 p ) t 2 j 在文件共享( f i l es h a r i n g ) f 3 、即时通讯( i n s t a n tm e s s a g i n g ) 【7 8 喀领域得到了广泛的应用，其具有负载 均衡、自适应、自组织和容错能力强等优点【9 l 。因此，基于p 2 p 的分布式搜索 引擎的研究也逐步引起了人们的重视，越来越多的研究机构和公司开始参与到 这个领域研究中。 在p 2 p 应用方式下，每个对等节点( p e e r ) 既是服务的提供者，又是服务 的享用者。对等节点为系统提供有限的计算或存储资源，节点之间的协作为其 他节点提供服务，实现将服务器的负载分散到每个对等节点上。加入系统的节 点越多，节点为系统贡献的资源也就越多，整个系统总的服务能力也就越强， 从而有效地减轻了服务器的负载，极大地提高了系统的可扩展性。 因此，将p 2 p 技术应用到搜索技术中是一个颇受瞩目的搜索引擎技术研究 方向。 1 2 本文研究的内容和创新之处 鉴于此，本文在深入研究p 2 p 技术和搜索引擎技术的基础上，大胆地结合局 部遍历型搜索技术与p 2 pc h o r d 协议，提出了一个基于p 2 p 的分布式搜索引擎系统 方案( p p d s e ) 。 本文研究的主要内容和刨新之处包含以下几个方面： l 暂钾r 囊害 p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究兰州大学硕十学短论文 介绍了局部遍历型搜索技术，主要以文本为例： 介绍了p 2 p 技术，详细地阐述了d h t 中的c h o r d 算法。 在上述技术的基础上，提出了基于p 2 p 的分布式搜索引擎( p p d s e ) 系统方案。 - 采用了全分布式结构化拓扑结构，使系统具备较好的负载均衡、分 布式、可扩展性等优点； - 采用局部遍历型搜索技术，对信息进行聚类，建立信息树，将多维 空间上的相似度度量问题转化为在一维度量空间上的阃隔问题，提 高查询速度； - 采用c h o r d 协议，提供了快速的资源定位机制、高效的结点路由机制 和并行处理机制，提出了将局部遍历型搜索应用于c h o r d 协议上的 s e - c h o r d 算法。 1 3 本文的组织结构 第一章：主要介绍了本文的研究背景，阐述了主要的研究内容和成果。 第二章：主要以文本为例介绍了局部遍历型搜索技术。 第三章：介绍了p 2 p 技术，详细阐述了d h t 中的c h o r d 算法。 第四章：提出了基于p 2 p 的分布式搜索引擎( p p d s e ) 系统方案，分别对 其两个模块p p d s ea g e n t 和p p d s ep o c k e t 进行了简单的概述。 第五章：对p p d s ea g e n t 模块进行了详细的研究论述。 第六章：对p p d s ep o c k e t 模块进行了详细的研究论述。 第七章：对本文进行了总结，并对下一步的工作进行了展望。 麓翻哼虫害 p p d s e 一基于p 2 p 的分布式搜索弓i 擎系统研究 兰州人学坝1 ：学位论文 第二章局部遍历型搜索技术 本文使用局部遍历型搜索技术，对信息进行聚类，建立信息树，搜索时只 需要从树的一个分支下去遍历。局部遍历有一定的规则，且对每一个加入的索 引进行相对准确的位置安排，使得放置在合适的节点上，保证搜索的效率。 该技术具有抗压、搜索精度高和搜索效率高等优点，但设计复杂以及索引 调整不易是该技术的缺点。将局部遍历型搜索技术与p 2 pc h o r d 协议大胆地结 合，有效地解决了局部遍历型搜索技术的缺点。 本文提出的p p d s e 系统支持各种类型的信息处理，下面主要以文本信息为 例来简单介绍一下局部遍历型搜索技术的相关理论。 2 1 文本的表示 文本是一种无结构文档，文本表示就是要将这些无结构文档结构化，以一 定的特征项( 如词语) 来代表文档信息文档。表示所采用的模型有很多种，近年 来应用较多且效果较好的是向量空间模型v s m 。 在v s m 中，每一篇文档都被映射成多维向量空间中的一个点，对于所有的 文档类和未知文档，都可用此空间中的向量伍，嘶；疋，；l ，h 么) 来表示( 其中 z 为特征词条，彬为霉对应的权值，用以刻画该词在描述此文档内容时的重要 程度1 ，从而将文档信息的表示和匹配问题转化为向量空间中向量的表示和匹配 问题来处理。 2 l 1 基于汉语的文本特征提取 前面提到了文本表示，其中v s m 模型的重要环节就是得到特征词条t i ，所 谓的文本特征提取就是特征词条的抽取过程。一个英语句子的词与词之间是用 空格分开的，它的特征提取非常容易实现。但是，汉语句子是线性排列的，使 得特征提取成为一个难点。 2 1 2 切词 迄今为止，人们已经提出了许多种基于字典的计算机自动分词算法，这些 3 萄埘幺害p p d s e 基于p 2 p 的分布式搜索。l 擎系统研究兰州人学烦十学位论文 算法【l l l 大致可分为两类：机械匹配方法、理解式切分方法。 ( 1 ) 机械匹配方法 机械匹配方法主要是基于字符串匹配的原理进行的，即它以“足够”大的 词表为依据，采用一定的处理策略将汉语文本中的字串与词表中的词逐一匹配， 若成功，便认定该字串为词。 ( 2 ) 理解式切分方法 针对机械匹配法的不足，人们提出了理解式切分方法。这样的分词系统由 三部分组成：词库、知识库、推理机。 词库中存放词条；知识库中存放已形式化的各种语法规则语法知识，以及 语言学专家在分词过程中进行推理判断的经验知识：推理机利用词库和知识库 提供的大量数据与知识，模拟语言学专家的逻辑思维过程，实现自动分词。这 实际上就是一个自动分词专家系统。 从理论上讲，它较匹配算法无疑是一个进步，同时也似乎更易为人们所接 受。但其有效性和可行性尚待进一步验证。因为现代汉语毕竟缺乏标志，缺乏 通用的分词规则。语言界中现有的词法( 构词法，构形法) 、句法及组合规则 仍然是十分笼统与复杂的，要想使其有效的、系统的转换成可为机器采用的形 式，还有待进一步的研究，因此，这种方法在现阶段是难以付诸于实践的。 综上所述，不论采用哪一种分词方法，建立分词词库( 或称机器词典) 都 是汉语自动分词系统的基础，并且词库的优劣直接影响分词的正确率和分词速 度。 2 1 3 特征的选取 特征选取是文本特征提取在中文自动分词完成之后，选取可以表示该文档 内容特征的特征词汇，而除掉那些与表达内容特征无关的多余词汇。 不同的词条在文档中的作用是不同的，常用词( 例如“的”、“和”等虚词) 在所有文档中有很高的出现频率，而稀有词则在全部训练文档中出现的次数很 少，这两类词的词频统计特性很难确定，不适合作为特征项，应予以滤除。还 有一些词在所有文档中出现的频率基本相同，区分性差，不能作为特征项也应 滤除。同简单的词汇相比，词组和短语的表达能力强，更能表现文档内容，因 此应尽量多的采用词组和短语作为特征项，提高特征项的表示能力。 l 锈鲥幺害p p d s e 皋于p 2 p 的分布式搜索弓l 笨系统研究 兰州大学颈1 ：学位论文 2 2 文本特征缩减 使用前面提到的方法来表示待学习的文档时，表示文档的特征向量会达到 数十万维的大小。有人曾利用一些相关的文档集特征提取算法对y a h o o 上4 9 6 0 0 个文档提取作为特征的词串，最后得到3 2 0 0 0 0 个特征词串。如此高维的特征可 能会大大增加机器的学习时间而仅产生较少与特征子集相关的学习分类结果。 所以，文本特征缩减( 特征子集的选取) 便显得异常重要。 目前，文档特征子集选取算法一般是构造一个评价函数，对特征集的每个 特征进行独立的评估，这样每个特征都获得一个评估分，然后对所有的特征按 照其评估分大小进行排序，选取预定数目的最佳特征作为结果的特征子集。 2 3 文本聚类分析介绍 文本聚类是一个将文本集分组的全自动处理过程，是一种典型的无指导的机 器学习问题。类是通过相关数据发现的一些组合，类内的文本和其它组相比更为 相近。因此，文本聚类的目标是找到这样一些类的集合，类之间的相似度最小， 而类内部的相似性最大。 2 3 1 中文文本聚类的一般过程 中文文本的内容使用中文书写，不像英文单词之间存在自然的形态间隔， 中文需要分词处理。而且分词的效果能够显著地影响分类效果。下图给出了中 文文本自动分类的一般过程： 2 3 2 相似度度量 图2 3 1 1 中文文本聚类的一般过程 相似性度量是文本分类、聚类的基础，正确选择相似性最高的类作为目标 文本判断标准是分类、聚类成功的关键。 在聚类过程中，为了找到目标文本的最近邻居，必须度量文本之间的相似 l 暂钾r 囊害 p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究 兰州大学硕十学位论文 性，然后选择相似性最高的若干文本作为目标文本的最近邻居。目标文本的最 近邻居查询是否准确直接关系到整个文本聚类系统的聚类质量。准确查询目标 文本的最近邻居是整个聚类过程成功的关键。 令d 一 d 1 ，d 2 ，d 厅 表示文本的集合，? 4 f 1 ，2 ，f 坍 表示特征项集，t 由 文本集中的所有或部分特征项组成，文本d f 用特征项空间中的向量 t 1 ，2 ，” 表示，其中：。哆) 表示特征项j 在文本d i 中的权值，表示特征项j 在文本d i 中出现的 频率，称为项频，哆则表示文本集d 中出现了特征项j 的文本数目的倒数， 称为反向文本频率。 度量文件d i 和文件d j 之间相似性的方法是，首先得到文件d i 和文件d j 的特 征向量，然后通过不同的相似性度量方法计算文件d i 和文件d j 之甸的相似性， 记为d ( d ；，d ) 。 2 3 2 1 传统的相似度度量方法 度量文件问相似性的方法有多种，主要包括如下3 种方法【1 2 】：余弦相似性、 距离相似性以及相关相似性。 余弦相似性i n c ) ：在聚类分析中，从特征项空间中的向量 - ，2 ，h 磊，中所包含的词条重叠度考虑，作为文件d i 和文件d j 的相 似度。通常用其对应向量和i 的夹角余弦值来定义，向量夹角越小( 即夹 j 角余弦值越大) 表明其相似度越高文件d i 和文件d i 的相似性d ( d i ，d j ) 为： d ( d i ，6 j ) t c 0 8 晖，) 。 分子为两个文本特征向量的内积，分母为两个文本特征向量模的乘积。 距离相似性( c o 玎c l a t i o n ) ：对于有m 个特征项的文本来说，1 1 个文本特征 项向量可以视为m 维空触中的n 个点，可以设想用点问的距离来度量文本间的 肌_ 1 b 一 x 鬈一吲 l 暂钾r 囊害 p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究兰州大学硕十学短论文 相似程度。常用的距离定义如f ： 明氏( m i n k o w s k i ) 距离： d i j ( q ) ；( 墨- w j k i q ) 1 7 q d i j q k 兰l l w i k - w j l q ) l 。q 当q 分别为1 、2 、一时，明氏距离即为绝对距离、欧氏( e u c l i d ) 距离和切 比雪夫距离。 马氏( m a h a l a n o b i s ) 距离： d i j ( m ) l ( 飞一w j ) z 。1 ( w i w j ) 相关相似性：文件d i 和文件d i 的相关系数可以记为： r 1 l j ! 篓! 查兰! 堡! ! ：墨! p 2 p ! 畛布式搜索g j 擎系统研究 兰州大学硕十学短论文 第三章对等网络 对等网络( p e e rt op e e r ，p 2 p ) 是一种分布式网络，网络的参与者共享他们 所拥有的一部分硬件资源( 处理器、存储器能力、网络带宽、打印机等) ，这 些共享资源需要由网络提供服务和内容，能被其它对等节点( p e e r ) 直接访问 而无需经过中间实体。在此网络中的参与者既是资源( 服务和内容) 提供者 ( s e r v e r ) ，又是资源( 服务和内容) 获取者( c l i e n t ) 。 利用p 2 p 技术构架搜索引擎服务系统，打破了传统的c l i e n l s e r v e r ( c s ) 搜 索引擎服务模式。网络中每个结点的地位都是对等的，每个结点既充当服务器， 为其他结点提供服务，同时又充当客户端，享用其他结点提供的服务。 3 。l 完全分布式结构化拓扑 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系， 结点之间的拓扑结构是确定系统类型的重要依据。 根据拓扑结构的关系将p 2 p 网络分为4 种形式【1 3 1 ：中心化拓扑( c e n t r a l i z e d t o p o l o g y ) , 全分布式 # 结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) 半 分布式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 和完全分布式结构化拓扑 ( d e c e n t r a l i z e ds t r u c t u r e dt o p o l o g y ，也称作d h t 网络) 。 本文采用了完全分布式结构拓扑网络。 由于非结构化系统中的随机搜索造成的不可扩展性，大量研究集中在如何 构造一个高度结构化系统。而如何有效地查找、发现信息成为了研究的重点。 完全分布式结构化拓扑使用了分布式散列表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 1 4 , 1 5 来组织p 2 p 网络。 基于d h t 的分布式发现和路由算法能够很好地避免类似中心化拓扑 ( n a p s t e r l 6 1 ) 的中央服务器问题，又不像全分布式非结构化拓孚卜( g n u t e l l a ) 那 样基于广播进行查找，而是通过分布式散列函数，将待查询的信息唯映射到 某个结点上，然后通过某些路由算法同该结点建立连接。 蔫州幺害 p p d s e - 一基于p 2 p 的分布式搜索。l 擎系统研究兰州人学帧卜学位论文 3 2d h t 算法 分布式散列表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 1 1 4 d 5 j 是p 2 p 网络中节点组织 的一种非常有效的方式，在本文提出的p p d s e 系统就借鉴了这种思想来对系统 中节点进行组织管理。 d h t 实际上是一个由广域范围大量结点共同维护的巨大散列表。散列表被 分割成不连续的块，每个结点被分配一个属于自己的散列块，并成为这个散列 块的管理者。d h t 算法能够为p 2 p 网络提供有效的搜索与路由机制【1 6 1 。在d h t 算法中，系统中的每个节点所拥有的资源都会根据h a s h 算法映射到一个码空间 ( k e ys p a c e ) ，而每个节点都会保存一定范围的码空间及一个以k e y 值为索引的 路由表。当有节点在网络中进行数据搜索时，只需将所搜索的数据通过h a s h 函数进行码空间的映射得到k e y 值，然后在路由表中进行路由。通过这个路由 表，系统保证了从任意节点出发，查找任意数据，仅须经历有限的节点数。简 单来说，就是网络结点按照一定的方式分配到一个唯一节点标识符( n o d ei d ) ， 资源对象通过散列运算产生一个唯一的资源标识符( o b j mi d ) ，且该资源将存 储在节点m 与之相等或者相近的节点上。需要查找该资源时，采用同样的方法 可定位到存储该资源的节点。 d h t 结构有着良好的可扩展性、健壮性和自组织能力i r 丌。由于重叠网络采 用了确定性拓扑结构，d h t 可以提供精确的发现。只要目的结点存在于网络中 d h t 总能发现它，发现的准确性也得到了保证。 目前比较成熟的d h t 算法有t a p e s t r y 1 引、p a s t r y 1 们、c a n m i 和c h o r d 2 1 捌 等等。本文采用c h o r d 算法。 3 3c h o r d 算法 3 3 1 思想 c h o r d 算法 2 v 2 3 l 是由m f f 提出的一种分布式查找协议，c h o r d 算法提供了 一个适合于p 2 p 环境的分布式资源发现服务，它通过使用d h t 技术使得发现 指定对象只需要维护d ( 1 0 9 2 ) 长度的路由表。 l 暂钾r 囊害 p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究兰州大学硕十学短论文 在c h o r d 协议中，通过对结点和资源进行哈希，得到在同一个特定名字空 间内m 位节点标识符和m 位资源标识符1 3 3 】，每个节点存储数量大概相等的资 源标识符来平衡负载，并且使得当节点加入或退出时索引信息的相对移动比较 小。因为c h o r d 环中的路由表是分散的，c h o r d 环中的节点仅仅需要知道系统 中其它少数节点的路由消息，通过与其交流来获取查询路径信息。一个包含 节点的网络在稳定状态下，每个节点仅仅需要保持d l l o g ，n 其他节点的信息， 、-， 查询操作也仅仅需要发送d ll o g ，n 条消息到其他节点。当节点加入和离开时， 、， ， 一 、 在绝大多数情况下网络所产生的消息量不超过d li o g ，l 。 3 3 2 特点 负载均衡 由一致性哈希来实现。所有的结点以大概相同的概率分担系统负荷，从而 避免某些结点负载过大的情况。 分布性 纯分布式系统。结点之间完全平等并完成同样的工作，可抵御d o s ( d e n i a l o f s e r v i c e ) 攻击。 可扩展性 随着系统规模( 结点总数n ) 的增加，查询跳数按照d ( 1 0 9 2 ) 的比例增加。 可用性 系统结点根据网络的变化动态她更新查询表，及时恢复路由关系，使得查 询可靠地进行。 命名灵活性 未限制查询内容的格式，因此应有层可以灵活的将内容映射到键值空阐。 3 3 3 哈希算法 哈希表( h a s ht a b l e ，也叫散列表) 是根据关键码值( k e yv a l u e ) 而直接进 行访问的数据结构。也就是说，它通过把关键码值映射到了表中一个位置来访 l 暂钾r 囊害p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究兰州大学硕十学短论文 问记录，以加快查找的速度。该映射函数叫做哈希函数，存放记录的数组叫做 哈希表。 c h o r d 使用一致性哈希作为哈希算法【2 4 i 。一致性哈希1 2 5 洲函数为每个结点 及资源分配了一个m 位标识符。哈希结点的l p 地址得到结点标识符，同样哈 希资源内容得到资源标识符。并且标识符长度1 1 1 必须确保两个结点或资源被哈 希到同一个标识符的可能性可忽略不计。 哈希函数按照如下规则将资源分配给结点： ( 1 ) 结点标识符被有序地分配在一个模2 辨的c h o r d 标识符圆环上。 ( 2 ) 资源标识符k 被分配到标识符空间内第一个i d 值大于等于k 的结点 上。该结点称为资源标识符k 的后继结点，标示为s u c c e s s o r ) ，即c h o r d 环上 从k 顺时针出发第一个被访问到的结点。 下图以m = 6 、包含1 0 个结点标识符以及5 个资源标识符的c h o r d 环为例： 图3 。3 3 - 1c h o r d 环资源分配 当结点n 加入或者离开网络中时，菜些资源标识符会重新进行分配，从而 达到网络的自适应。 定理3 3 3 1 ：给定n 结点和k 资源标识符，高概率地实现 ( 1 ) 每个结点最多负责o + o k j v 资源标识符； ( 2 ) 当第n + 1 个结点加入网络或某结点离开网络时，大约有o ( k n ) 资 源标识符需要改变存放位置( 转移到新加入的结点上或从离开的结点上转移到 它的后继结点上) 。 定理中，s o ( 1 0 9 ) 。 l 暂钾r 虫害 p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究兰州大学硕十学短论文 3 3 4 键值定位 3 3 4 1 简单键值定位 在简单的键值定位1 2 7 j 过程中，每个结点只需要获知其后继结点的路由信息。 给定标识符的查询请求在c h o r d 环上逐个结点地传递，直到到达的结点上存放 了查询的标识符信息对( 信息对中第二部分存放的信息就是查询键值所对应的 结点信息) 。 如下图所示： 图3 3 4 1 1 简单键值定位 伪代码： a s k n o d e n 协t h d t h e m c a s 口o f t d n 伍吐眦c 铝。婚d ) f i k i d ( m s u c c e o r ) r e t u r n s u c c e s s o r , 出c f r o w a r d t h e q u e r y a r e e n d t h e c 廿d i e f d 啪飘l e 烈l 岛4s u 苎s 嘶曲； ) 3 3 4 2 可扩展键值定位 简单键值定位过程中，传递的消息数与c h o r d 环上存在的结点数成线性关 系。为了提高查询效率，c h o r d 增加了附加路由信息。 下面介绍一种有效的且准确快速的c h o r d 搜索算法嘲。如前所述，假设 k e d e 对的标识符为m 位，每个结点拥有一张最多包含m 条记录的路由表， 该路由表称为f i n g e r 表a ! 塑! 当害 p p d s e - - - 堆于p 2 p 的分布式搜索日i 擎系统研究兰州人学硕十学位论文 定义3 3 4 2 - l ：f i n g e r k ：c h o r d 环上第一个标识符为( i d2n + 2 “) m o d 2 m 的 结点目l 1 - ：k sr n ： 定义3 3 4 2 - 2 ：s u c c e s s o r ：在c h o r d 环上的直接后继结点，即f i n g e r 1 ； 定义3 3 4 2 - 3 ：p r e d e c e s s o r ：在c h o r d 环上的前驱结点。 结点n 的f i n g e r 表中第i 项表示与结点1 1 至少相差2 f 一1 的第一个结点s ， s 一跚c c 鲫，o + 寥- 1 ) ，1 c i 车历，即s 为胛肋i f 】。f i n g c r 表中项包含了结点的 m 以及对应的口地址。如下图( a ) ： ( a ) ( i ) 图3 3 4 2 - 1 可扩展键值定位 根据图( b ) ，具体搜索方法如下： ( 1 ) 当查找的资源标识符i d 落在n 及n 的后继结点之间，p n d 蹦c c b ， 操作完成，返回其后继结点。 ( 2 ) 否则，n 搜索其f i n g e r 表中最靠近i d 的结点m ，然后递归调用 归耐一s u c c e s s o r 函数，直到找到资源标识符i d 的后继结点。 伪代码： ，a g k n o d e n t of m d e t h e 飘l c c 咏o r o f j d n 缸dg u e 鼯呱i 由 i 唧 s u c 璐o f d f d ms u c c e s s o r , e l s e n k l o s c 乱p f 。d m g _ n o ； f 曲j m l r 伍l d 羽c 嚣s 呱i c o , ) ) l 暂钾r 囊害 p p d s e 基于p 2 p 的骨布式搜索弓j 擎系统研究兰州大学硕十学短论文 “s e a r c h t h e l o c a l t a b l e f o r t h e h i g h e s t p r e d e c e s s o ro f i d n c l o s e s t _ p r o c e 螗n o d e ( i d ) ( f o r ( i f f i l ；i m ) ( n e x t = l l o g ( s u c c e s s o r - n ) j + t f i r s t n o n - - t d v i a l f i n g e r 缸g 巾酬；缸d - s u 粥o n + “1 ) ； ) ) c a g e dp 咖d i c 蛳c h e c k s w h e t h e r p r e d e c e s s o r h a s 跚e d l l c h i _ p f e d 鄂s o f o ( i 日( p r e d e c e s s o rl l a sf a i l 醐 p r e d e c e s s o r = 帕i l ； ) ( 1 ) 当结点n 首次加入系统时，将调用n j o i n ( n 。) 函数，其中n 是任意一 个结点n 获知的c h o r d 环上的结点；或者结点n 调用h f r 即地o 创建一新c h o r d 环。结点n 调用 j o i n ( n ) 主要是请求结点疗来获取其后继结点信息。 ( 2 ) 每个结点周期地运行s 细6 甜泐o 函数，其目的是实时地获知新加入结 麓簟一幺害 p p d s e 一基十p 2 p 的分布式搜索引擘系统研究 兰州人学颂一i ：学位论文 点信息，更新并保证结点的后继结点及前驱结点信息的j 下确性。 ( 3 ) 同样，每个结点也周期地运行豇一f i n g e r s o 函数，目的是确保结点 f i n g e r 表的j 下确性。一方面，新结点加入系统时，该函数用来初始化该结点的 f i n g e r 表：另一方面，系统中已存在结点通过该函数将新加入结点的信息添加到 它的f i n g e r 表中。 ( 4 ) 另外，每个结点周期地运行c h e c k p r e d e c c e s s o r 0 函数，当结点的前 驱结点失败时，该函数将重新设置结点的前驱结点。 3 3 5 2 新加入结点的影响 新加入结点对查询操作的影响主要从两个方面考虑：正确性和性能效果。 关于正确性： 当某结点加入c h o r d 环时，它将影响c h o r d 环的某些区域的查询操作；在 s t a b i l i z e 0 函数没有运行前，关于查询操作将会出现以下三种情况： ( 1 ) 通常情况下，查询操作过程中所参与的结点的f i n g e r 表都是正确的， 且其后继结点信息也是正确的，查询操作将在0 ( 1 0 9 ) 步内正确完成； ( 2 ) 结点的后继结点信息是正确的，但其f i n g e r 表是不正确的，在这种情 况下，查询操作能正确完成，但消耗的时间比较长； ( 3 ) c h o r d 环上新结点加入区域结点的后继结点信息不正确，或资源键值 的查询操作不能遍历到新加入结点，最终导致查询操作失败。这种情况下，应 用在c h o r d 层之上的高层应用程序将会注意到查询失败，高层应用程序会在一 定间隔后重试此查询操作。该问隔时间会很短，因结点的础曲比z e o 会很快地更 新结点的后继结点信息。 关于性能效果： ( 1 ) 当s t a b i l i z e 0 运行完毕后，新加入结点的影响仅仅是增加了o ( 1 0 9 9 n ) 中n 的值： ( 2 ) 如果黝6 m 理o 没有运行完毕，c h o r d 环上已存在结点的f i n g e r 表中未 保存新加入结点的信息。如果新加入结点处在查询目标结点的前驱结点和查询 1 6 蔺赍r 矢害 p p d s e 基于p 2 p 的分布式搜索。l 擎系统研究兰州大学硕j ：学位论文 目标结点之间，将会影响查询的速度。 3 3 5 3 失败结点的影响 c h o r d 协议的正确性主要依赖于c h o r d 环上的每个结点都能正确地获知其 后继结点的信息。然而，这种正确性会因为某些结点失败而变化。 例下图所示： 图3 3 5 3 1 失败结点的影响 当结点1 4 、2 1 、3 2 同时发生失败时，结点8