（管理科学与工程专业论文）基于Chord的P2P搜索模型研究及其应用.pdf

苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文囱 论文作者签名：塞! 鳖 e l 导师签名：经过毫e l 期：丝! ! ! i i d j 基于c h o r d 的p 2 p 搜索模型研究及其应用摘要 摘要 搜索引擎的出现为互联网检索信息提供了极大的便利，但随着网络的进一步发 展，资源更新越来越快，传统搜索引擎也显示出不足。而当前研究热门的基于p 2 p 的分布式网络结构具有可扩展性、健壮性、负载均衡等特点，与传统分布式系统相 比，具有无可比拟的优势，适用于构建分布式信息检索系统，能实现计算机本地信 息查询检索和共享。 本文在分析c h o r d 网络的不足之后，首先提出了一种基于c h o r d 的改进路由算 法r c h o r d 。通过对c h o r d 的路由表添加邻居结点表和结点缓存表改进路由算法。 邻居结点表使路由选择接近真实物理位置，结点缓存表则优先考虑热点结点。 然后，结合改进的r c h o r d 算法和无结构p 2 p 网络g n u t e l l a ，利用l u c e n e 的全 文索引技术，本文提出一种基于p 2 p 的两层分布式搜索引擎模型，并对模型中超级 结点行为进行优化。模型中，以性能强的结点作为超级结点，其他的为普通结点。 超级结点间形成c h o r d 模型网络，主要负责定位查询到相关结点。查询时先通过结 点索引定位包含关键字信息的相关超级结点，再由超级结点转发查询到与其相连接 的普通结点。通过结点在本地数据索引返回结果，最终实现查询。模型中的超级结 点的控制尤为重要，对此本文也提出了一个控制缓存策略，记录候选超级结点，随 时替代离开的超级结点或性能变低的超级结点，保持超级结点的稳定。 最后，本文实现了一个保密检查系统。应用前文提出的搜索引擎模型，本文实 现了一个校园保密检查原型系统，对终端主机中保存的可能涉密信息保密检查。 关键字：对等网络；p 2 p ；搜索引擎；c h o r d ：分布式 作者：彭俊 指导老师：徐汀荣 a b s t r a c t r e s e a r c ha n da p p l i c a t i o no f p 2 ps e a r c hm o d e lb a s e do nc h o r d a b s t r a c t t h ee m e r g e n c eo fs e a r c he n g i n eh a sb r o u g h tg r e a tc o n v e n i e n c et ou s e r si nr e t r i e v i n g o nt h ei n t e m e t b u tt h et r a d i t i o n a ls e a r c he n g i n ea l s os h o w e sd e f i c i e n c i e sa st h ef u r t h e r d e v e l o p m e n to ft h en e t w o r ka n dm o r eq u i c k l yt h ec o n t e n to fi n t e r n e tu p d a t e s a n dt h e d i s t r i b u t e dn e t w o r kb a s e do np 2 p , p o s s e s s e ss c a l a b i l i t y , r o b u s t n e s s ，l o a db a l a n c i n g ，e t c ， c o m p a r e d 、i t ht r a d i t i o n a ld i s t r i b u t e ds y s t e m s p 2 pt e c h n o l o g yh a st h eu n p a r a l l e l e d a d v a n t a g e s ，a n di ss u i t a b l ef o rb u i l d i n gd i s t r i b u t e di n f o r m a t i o nr e t r i e v a ls y s t e m st o i m p l e m n tt h el o c a li n f o r m a t i o no nt h ec o m p u t e r s w ef i r s t l yp r o p o s e da ni m p r o v e dr o u t i n ga l g o r i t h mr c h o r db a s e do nc h o r db y a d d i n gan e i g h b o rn o d el i s ta n dan o d ec a c h et a b l et oc h o r d sr o u t i n gt a b l e t h en e i g h b o r n o d el i s tp r o v i d e sn o d e sa d j a c e n tt ot h en o d ei np h y s i c ，a n dt h en o d ec a c h et a b l ep r o v i d e s t h eh o tn o d e s b o t ho ft h e mc a ni m p r o v et h ee f f i c i e n c yo fs e a r c h i n g t h e nc o m b i n e d 、析t l lt h ei m p r o v e dr c h o r da l g o r i t h ma n du n s t r u c t u r e dp 2 pn e t w o r k g n u t e l l a ，p 2 pt e c h n o l o g i e sa n ds e a r c he n g i n e ，w ep r o p o s e dat w o t i e rd i s t r i b u t e ds e a r c h e n g i n em o d e lb a s e do np 2 p , a n do p t i m i z e dt h eb e h a v i o ro fs u p e r - n o d e si n t h i sm o d e l e a c hh o s ti san o d e ，a n ds u p e rn o d e 谢t l ls t r o n gp e r f o r m a n c e ，a n dt h eo t h e r sa r et h e c o m m o nn o d e s s u p e r - n o d e sf o r mt h ec h o r dm o d e la n da r er e s p o n s i b l ef o rp o s i t i o n i n g t h ei n d e xn o d e sc o n t a i n i n gk e y w o r d sr e l a t e dt os u p e r - n o d ei n f o r m a t i o n , a n dt h e n f o r w a r d i n gq u e r i e st oc o m m o nn o d e s t h ec o n t r o lo fs u p e r - n o d e si nt h em o d e li sv e r y i m p o r t a n t ，a n dw ep r o p o s e dac o n t r o ls t r a t e g yo ft h ec a c h ew h i c hr e c o r d st h ec a n d i d a t e s u p e r - n o d et os u b s t i t u t ef o rt h el e a v i n gs u p e r - n o d eo rs u p e r - n o d e 、航t i ll o wp e r f o r m a n c e f i n a l l y , w ei m p l e m e n tac o n f i d e n t i a li n s p e c t i o ns y s t e mb a s e do nt h ea p p l i c a t i o n m o d e l u s et h em o d e lp r o p o s e d ，w ed e s i g na n di m p l e m e n tac a m p u sc o n f i d e n t i a l i n s p e c t i o ns y s t e m ，t oc h e c kt h ec o n f i d e n t i a li n f o r m a t i o no nt h ee n dh o s t s k e y w o r d s ：p e e r - t o p e e r ；p 2 p ；s e a r c he n g i n e ；c h o r d ；d i s t r i b u t i o n i i w r i t t e nb yj u np e n g s u p e r v i s e db y t i n g r o n gx u 目录 第一章绪论。1 1 1 论文研究背景1 1 2 国内外研究现状。3 1 3 主要研究工作5 1 4 本文组织结构6 第二章基于c h o r d 的对等网络搜索模型分析7 2 1d h t 简介7 2 2c h o r d 模型分析8 2 2 1 路由查找8 2 2 2 结点的加入和离开1 1 2 2 3c h o r d 自适应算法1 3 2 3c h o r d 总结1 4 第三章基于c h o r d 改进的路由算法1 6 3 1 改进路由算法r c h o r d 。1 6 3 1 1 邻居表建立1 6 3 1 2 结点缓存表。17 3 1 3r c h o r d 路由算法描述1 7 3 1 4 路由表维护1 9 3 2 仿真实验与结果分析1 9 3 2 1 仿真工具描述1 9 3 2 2 仿真条件设置2 3 3 2 3 仿真实验2 4 3 2 4 实验小结2 6 第四章基于c h o r d 的两层分布式搜索模型。2 7 4 1 模型结构2 7 4 1 1 模型网络拓扑结构2 7 4 1 2 结构组成。2 8 4 1 3 索引方式2 9 4 2 结点优化3 1 4 2 1 结点加入和离开3 1 4 2 2 自适应策略。3 2 4 2 3 结点优化策略3 2 4 3 路由查询3 5 4 4 性能分析：3 6 4 4 1 网络性能分析假设一3 6 4 4 2 网络拓扑性能分析3 7 4 5 仿真实验3 9 4 6 月、结4 0 第五章基于c h o r d 的对等网络搜索模型在保密检查中的应用4 1 5 1 应用背景4 1 5 2 系统整体框架及结构4 2 5 3 开发环境4 4 5 4 保密检测4 4 5 5 性能分析4 5 5 6 实验结果4 5 5 7 小结4 8 第六章总结与展望4 9 6 1 总结。4 9 6 2 进一步研究方向4 9 参考文献5 1 攻读硕士学位期间发表( 录用) 的论文5 6 致谢。5 7 基于c h o r d 的p 2 p 搜索模型研究厦其应用 1 1 论文研究背景 第一章绪论 第一章绪论 随着信息技术的不断提高，互联网发展迅猛，应用广泛，已成为当今世界人们 获取资源和信息交流的主要场所。然而，面对浩如烟海的网络，信息的准确查找定 位变得异常重要。而搜索引擎的出现大大地方便了人们对信息的查询。 传统的搜索引擎g o o g l e ，通过爬行w e b 上的资源，并对网页处理和建立索引， 为人们提供搜索查询。但随着网络的进一步发展，内容的更新也越来越快。传统搜 索引擎开始显示出一些局限性【1 】： ( 1 ) 搜索深度不够。传统搜索引擎对发布在i n t e m e t 上的资源进行索引，来提 供检索，而对于储存在个人电脑上但没有发布到i n t e m e t 的共享资源不能实现检索 查询。即使对于i n t e r n e t 资源，也没有一个搜索引擎能1 0 0 涉及。据清华大学i t 可用性实验室2 0 0 5 年对中文搜索引擎进行的较为全面的对比研究后发现，具有中 文网页样本覆盖率最高的百度也只有3 2 5 3 的网络资源覆盖率【2 】。 ( 2 ) 时效性较差。服务器每隔一段时间对索引更新一次。如果服务器更新周 期过长，网页内容和地址发生变化，容易产生大量的无效链接。事实上，采用网络 蜘蛛爬行技术是无法避免无效链接的。只能通过缩短更新周期来尽量减少无效链 接。 ( 3 ) 成本较高。海量的资源索引信息需要庞大的服务器来维护。每一条检索 请求都将发送给服务器来处理，因此要求服务器有强大的处理能力、存储能力以及 网络带宽。 ( 4 ) 健壮性不足。虽然目前大型搜索引擎都采用分布式的架构，服务器分布 在网络中的多个对等点，可以提高其对网络攻击的抵抗能力。但是其中一个或某些 服务器因攻击而停止服务，也会导致整个搜索引擎的服务能力降低。 传统搜索引擎存在上述不足，促使人们寻找各种解决办法，而如果利用当前发 展迅速的p 2 p ( p e e r - t o p e e r ) 【3 ，4 】技术来实现搜索，正是一种可行的解决方案。 p 2 p 即对等网络，可以简单地理解为通过直接交换，共享计算机资源和服务。 在这种网络中，网络的参与者共享他们所拥有的一部分硬件资源( 处理能力、存储 第一章绪论 基于c h o r d 的p 2 p 搜索模型研究及其戍用 能力、网络连接能力、打印机等) ，这些共享资源需要由网络提供服务和内容，能 被其它对等结点( p e e r ) 直接访问而无需经过中间实体【5 1 。网络中的参与者既是资 源( 服务和内容) 提供者( s e r v e r ) ，又是资源( h i 务和内容) 获取者( c l i e n t ) 。各 对等点具有相同的责任与能力并协同完成任务。对等点之间通过直接互连共享信息 资源、处理器资源、存储资源甚至高速缓存资源等，无需依赖集中式服务器或资源 就可完成。 与传统的客户端h i 务器( c l i e n t s e r v e r ，简称c s ) 结构相比，p 2 p 网络具有良 好的健壮性，扩展性，成本低1 6 】。实际上，p 2 p 也可以像c s 一样有中心服务器， 不过中心服务器不是直接提供内容，而是维护索引以提供搜索等服务，真正的内容 交互在对等点之间完成。 p 2 p 是一种基于互联网环境的新的技术应用模式，它的技术特点和优势在于1 7 j ： ( 1 ) 非中心化( d e c e n t r a l i z a t i o n ) ：网络中的资源和服务分散在所有结点上，信 息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的介 入，避免了可能的瓶颈。 ( 2 ) 可扩展性：在p 2 p 网络中随着用户的加入，不仅服务的要求增加了，系 统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个 体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ( 3 ) 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各 个结点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一 般在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络通 常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。p 2 p 网络还能 够根据网络带宽、结点数、负载等变化不断地做自适应的调整。 ( 4 ) 负载均衡：p 2 p 网络环境下可以根据策略灵活分布信息。负载均衡模块可 以监控各种信息的流量和请求率，然后重新分布这些信息以减轻单个结点的负载。 这种负载平衡策略可以提供分布式缓存才能实现的功能，且具备简单和低价的特 点。 ( 5 ) 信息资源丰富：任何p 2 p 网络用户能够扫描活动结点并搜索需要的信息， 然后直接从这个结点上下载信息。用户可以在他们的机器上把下载的信息共享出 来，这样，请求率高的文件能够很快地在许多结点上扩展开来。在一个开放网络环 境下，p 2 p 网络能够很快积累相当丰富的信息。 2 基于c h o r d 的p 2 p 搜索模型研究及其应用 第一章绪论 ( 6 ) 冗余和容错：p 2 p 网络的多个结点间的信息复制导致高度冗余，其直接结 果是提高了信息的可用性，使之为更多的用户提供服务。另外，冗余使得网络不会 产生“单点失效”问题，所以分散式的p 2 p 网络提高了网络的容错性和安全。 ( 7 ) 基于内容的寻址：在w e b 上，u r l 地址并不能直接反映它们的内容。但 在p 2 p 网络中，存储特定信息的结点地址对于用户是透明的，用户向网络提交查询 请求时，请求中便包括需要查询的信息，p 2 p 软件把请求转换成存放这些信息的结 点地址，所以把信息按照内容分类后再发布在网络上，这更易于信息、资源的查找。 ( 8 ) 有效的搜索：w e b 搜索引擎存在一些问题，因为这些搜索引擎依赖执行 程序在i n t e m e t 上进行搜索，得到的信息存储在巨大的、可扩展的数据库中。这些 信息仅包括开放的服务器，并且数据库不会随着网络状态动态更新。但在p 2 p 网络 中，任何结点的信息只有当结点在线的时候才被加入路由表，因此路由表信息与网 络状态同步。p 2 p 网络不依赖搜索程序重新访问链接来修改数据库信息，这种动态 信息和对信息的有效搜索使得p 2 p 具有显著优势。 p 2 p 网络区别于传统客户端服务器( c s ) 模式，拥有独特的优势，它在文件共享、 分布式计算、分布式存储、协同工作、应用层组播、流媒体服务等方面已有广泛应 用。 1 2 国内外研究现状 由于p 2 p 具有c s 所无可比拟的优势，国内外的众多学校，科研机构，企业都 投入了大量人力、物力对p 2 p 进行研究，提出并开发了多种p 2 p 系统，也提出了很 多有效的搜索方法，包括集中式搜索，洪泛法和基于分布式哈希表的搜索方法等。 集中式搜索，以n a p s t e r 8 】为典型代表，采用中央索引的方法实现资源的搜索。 任何一个注册的结点，都要向中央服务器传送自己所共享资源的一个索引。一个结 点想要搜索资源，将搜索请求发送到中央服务器，由中央服务器进行搜索，并把拥 有该资源的结点列表返回给搜索请求者，请求者直接从中央服务器返回的结点下载 资源。n a p s t e r 模式集中搜索的特点决定了其可伸缩性和可靠性不是很好。 洪泛法【9 】( f l o o d i n g ) 是无结构p 2 p 网络最直接的路由方法，也是绝大多数无结 构p 2 p 网络采用的方法。c r n u t e l l a 1 0 采用洪泛搜索方法。当一个结点需要搜索一个 文件时，它向所有邻居结点发送这个请求，消息到达目的地或者跳数限制t t l 为0 第一章绪论基于c h o r d 的p 2 p 搜索模型研究及其应用 时消息不再转发。这种模型由于消息量过大，网络负担过重，使得性能较差的结点 很快就成为整个系统的瓶颈，搜索效率不高，另外产生的大量冗余消息浪费了大量 带宽，对于现在相对非常宝贵的带宽资源是种极大的浪费。针对这种情况，学者们 提出了各种有用的改进算法，如r a n d o mw a l k s k - r a n d o mw a l k s i l l 】， i t e r a t i v e d e e p e n i n g e x p a n d i n g r i n g s , 1 2 ，b f s t l 3 】，这些算法本质上还是洪泛的方式， 但在性能上比洪泛法提高了很多。 为了避免洪泛式搜索产生的冗余消息，研究者提出了基于内容的搜索模式，采 用分布式哈希表的结构化p 2 p 系统，c a n 1 4 1 ，c h o r d 15 1 ，p a s t r y t l 6 1 以及t a p e s t r y 1 7 1 都属于这种结构化系统。结构化p 2 p 系统的一个优点就是在进行资源定位时，消息 所经过的路径具有较少的跳数。对于结构化的p 2 p ，如果系统的结点数为n ，对于 c h o r d ，p a s t r y 和t a p e s t r y ，路由跳数为o ( 1 0 9 ( n ) ) ，而对于c a n 则路由跳数为d ( d 刈刀) ， 其中d 是覆盖网络构成的虚拟坐标空间的维数。 目前基于p 2 p 的w e b 搜索研究的搜索对象是各类w e b 文档，通常以关键词查 询的方式提供服务，因此本质上属于基于关键词的全文搜索。在p 2 p 全文搜索方面， 已有很多研究成果【1 8 。2 2 1 。 在搜索引擎方面，针对传统集中式搜索引擎的不足，研究者提出了基于p 2 p 的 w e b 搜索技术，也就是在p 2 p 网络中构建w e b 搜索引擎，提供w e b 搜索服务。目 前也有很多公司都在研究如何将p 2 p 技术应用到搜索引擎当中。1 5d i g i t a l 公司开发 的搜索引擎p a n d a n g o 2 3 ，2 4 】运用了p 2 p 网络的架构特性，德国的m a x p l a n c k 计算机 研究所推出了一个p 2 p 搜索引擎m i n e r v a 2 5 ，2 6 1 。其它研究性项目有国外的 o d i s s e a 2 7 1 以及国内清华大学周晋等人提出的c o o p e e r t 2 8 ，2 9 】等。 p a n d a n g o 是1 5d i g i t a l 公司运用p 2 p 网络架构开发的搜索引擎。p a n d a n g o 动态 地将当前p 2 p 网络中各个r e f e r r e r 的内容进行收集，用户下载完p a n d a n g o 后再输入 欲搜索的关键字，就能和1 0 0 名r e f e r r e r 组成的网络相连，然后进入他们的电脑搜 索其上网历史及标识的书签，再通过这1 0 0 人的电脑与另外一万名r e f e r r e r 的电脑 相连，再去搜索。也就是说，每次搜索就可涵盖1 0 0 万笔相关资料。 不仅如此，p a n d a n g o 的设计还可让网民按时间和搜索主题更改r e f e r r e r 名单的 排序，常被搜索的r e f e r r e r 就会被排得比较靠前，借此方式筛选出和自己比较匹配 的1 0 0 名r e f e r r e r 名单，搜索的相符性自然就大大提高了。 c o o p e e r 是清华大学周晋等人提出的一个基于p 2 p 的w e b 搜索系统，它的主要 4 基于c h o r d 的p 2 p 搜索模型研究及其应用第一章绪论 特点是充分利用p 2 p 系统中人的因素，在搜索过程中引入用户协作，使得搜索结果 更具人性化( h u m a n i z a t i o n ) 和个性化( p e r s o n a l i z a t i o n ) 。系统根据反映用户兴趣和偏好 的u s e rp r o f i l e 对搜索结果进行过滤，从而使搜索结果个性化；根据用户兴趣形成的 兴趣团体则可以将查询路由限制在- , b 部分结点中，从而减少搜索开销，提高搜索 效率。 l i 【3 0 】等人从w | e b 搜索的负载和p 2 p 搜索系统的资源限制的角度对基于p 2 p 的 w e b 搜索的可行性进行了分析，并认为简单实现的基于p 2 p 的w e b 搜索是不可行 的，因为p 2 p 搜索系统能够提供的资源不足以满足w e b 搜索的巨大负载要求，尤 其是在系统通信开销方面。上述系统都从追求或达到现有集中式引擎的规模、水平 出发进行全局性搜索引擎设计，难以有效解决边缘网络结点动态自治分布式环境与 查询路由、索引切分和网页收集排序等矛盾性问题，并需要大规模的部署和开销以 应对w e b 搜索的巨大规模。 1 3 主要研究工作 本文针对传统搜索引擎的不足，利用热点的p 2 p 搜索技术和l u c e n e 全文索引 技术实现一个基于c h o r d 的p 2 p 搜索引擎，最后应用到网络保密系统中。为此，本 文通过分析c h o r d 模型的原理和路由算法，对c h o r d 路由算法进行改进，并提出了 一种基于p 2 p 的分布式搜索模型来解决这些问题。本文主要研究内容包括以下四方 面： ( 1 ) 分析c h o r d 模型。对c h o r d 的基本原理和算法分析总结，研究已有p 2 p 算法。 ( 2 ) 针对c h o r d 模型的不足，提出改进路由算法。 ( 3 ) 提出了一种基于c h o r d 的两层分布式搜索模型。模型结合了结构化和无 结构p 2 p 网络特点，由超级结点和普通结点组成。利用超级结点，能提高系统的稳 定性，而又不会消耗大量的资源。利用p 2 p 搜索，能改善搜索引擎的搜索深度，对 用户个人电脑上的共享资源进行检索。 ( 4 ) 实现网络保密检查系统。信息技术发展，使得对网络信息保密越来越重 要。利用( 3 ) 中提出的p 2 p 全文搜索引擎模型，实现个网络保密检查的原型系 统。 第章绪论 基于c h o r d 的p 2 p 搜索模型研究及其应用 1 4 本文组织结构 第一章绪论，介绍了本课题的研究背景，然后简述当前p 2 p 搜索的发展及国内 外研究现状。最后总结了本文的主要工作。 第二章c h o r d 模型分析。首先介绍了结构化p 2 p 中分析c h o r d 的路由结构化对 等网络以及c h o r d 模型优缺点。 第三章提出种基于c h o r d 路由的改进算法r c h o r d 。针对第二章对c h o r d 的 分析总结出的不足，提出一种改进的路由算法r c h o r d 。然后对改进的r c h o r d 算法 进行了阐述，最后通过实验对r c h o r d 和原c h o r d 仿真和对比分析。 第四章提出一种基于p 2 p 的两层混合分布式搜索模型。结合改进的r c h o r d 和 无结构路由，提出了一种两层混合分布式搜索模型，并对混合模型中超级结点行为 优化，同时对模型性能进行数学分析。最后，对超级结点行为优化算法进行模拟实 验和分析。 第五章系统实现。基于p 2 p 全文搜索引擎的网络保密检查的应用。以学校为例， 应用第四章提出的两层分布式搜索实现校园网络保密检查系统。 第六章总结了本文的研究内容，并对今后进一步研究展望。 6 基于c h o r d 的p 2 p 搜索模型研究及其应用 第二章基于c h o r d 的对等网络搜索模型分析 第二章基于c h o r d 的对等网络搜索模型分析 2 1d h t 简介 分布式散列表1 3 1 1 ( d i s t r i b u t e dh a s ht a b l e ，简称d h t ) 是结构化p 2 p 网络的核 心设施。如图2 1 所示，它通常基于一致性散列函数，提供对于任何一个结点、数 据对象在覆盖网中的位置映射。 图2 1d h t 在p 2 p 系统中的位置 d h t 的主要思想是：首先，每条文件索引被表示成一个( k ，v ) 对，k 称为 关键字，v 可以是文件名( 或文件其他信息) 的哈希值，也可以是实际存储文件的 结点的i p 地址( 或结点的其他描述信息) 。所有的文件索引条目( 即所有的( k ，v ) 对) 组成一张大的文件索引哈希表，只要输入目标文件的k 值，就可以从这张表中 查出所有存储该文件的结点地址。然后，再将上面的大文件哈希表分割成很多局部 小块，按照特定的规则把这些小块的局部哈希表发布到系统中的所有参与结点上， 使得每个结点负责维护其中的一块。这样，结点查询文件时，只要把查询信息路由 到相应的结点即可。分布式哈希表在结点失败，遭受攻击和突发性高负载方面都能 表现出很好的健壮性，它具有良好的可扩展性，能以较低的系统开销获得较大的系 统规模。 结点要按照一定的规则来分割整体的哈希表，也就决定了结点要维护特定的路 由表，以及搜索过程。而这个规则在不同的系统中，如c a n ，c h o r d ，p a s t r y 和t a p e s t r y 是不同的。 d h t 使用分布式哈希算法【3 2 1 来解决结构化的分布式存储问题。分布式哈希算 第二章基于c h o r d 的对等网络搜索模型分析 基于c h o r d 的p 2 p 搜索模型研究及其府用 法的核心思想是通过将存储对象的特征( 关键字) 经过哈希运算，得到键值来进行 查找，大致有以下步骤： ( 1 ) 对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映 射到了一个具体的数值范围中，拓扑网中的每个结点负责数值范围中的特定段落。 例如，结点a 负责存储键值从1 0 0 0 1 9 9 9 的对象；而结点b 负责2 0 0 0 2 9 9 9 的对 象。对象集合也就分布地存储在所有的结点中。结点可以直接存储对象本身，如文 件中的一个片段；也可以存储对象的索引，如该对象所在结点的i p 地址。 ( 2 ) 结构化的分布式存储后，就是用户如何才能找到存储着目标信息的结点。 在有着大量结点( 如1 0 0 万个) 的p 2 p 系统中，任何结点都不可能拥有全部的结点， 键值，内容的对应关系；因此用户获得了键值之后，如何找到该键值对应的结点就 被称为d h t 的路由问题，d h t 协议必须定义优化的查找( 路由) 算法来完成这一 搜寻的工作，不同的d h t 协议定义了不同的路由算法。 2 2c h o r d 模型分析 c h o r d 是麻省理工学院提出的一种基于d h t 的路由模型，其目的是为了在p 2 p 网络中找到存在有特定数据的结点。c h o r d 专门为p 2 p 应用设计，因此考虑了在p 2 p 应用中可能遇到的特殊问题。c h o r d 在c f s 3 3 1 ( c o o p e r a t i o nf i l es y s t e m ) 中得到了 应用。 2 2 1 路由查找 c h o r d 协议中规定使用的散列算法是s h a 1 ，并在此基础上提供了优化的路由 算法。它采用一维的环形拓扑结构，关键字和结点都用m 位的标识符表示1 3 引，表 示范围为0 2 ”一l 。在c h o r d 中，每个结点需要存储m 个其他结点的信息，这些 信息的集合被称为查询表( f i n g e r t a b l e ) 。在c h o r d 中，f i n g e r 表中结点间的间距以 2 扣2 的关系排列( k 表示f i n g e r 表中的数组下标) 。这样形成的结点间的路由关系实 际上就是折半查找算法需要的排列关系。c h o r d 查询表结构含义如表2 1 所示，其 中n 为网络中的最大结点数，m 为查询表级数( 即l b n ) ，a 为本地结点的i d 。 8 基于c h o r d 的p 2 p 搜索模型研究及其应用第二章基于c h o r d 的对等网络搜索模型分析 表2 ic h o r d 路由表结构含义 路由表项 定义 f i n g e r k s t a r t( a + 2 扣1 ) m o d2 ”，1 k m i n t e r n a l ( f i n g e r k s t a r t ，f i n g e r k + 1 s t a r t ) n o d ef i r s tn o d e a f i n g e r k s t a r t s u c c e s s 0 r在环上离本地结点最近的后一个结点，也就是 f i n g e r 1 n o d e p r e d e c e s s o r在环上离本地结点最近的前一个结点 在c h o r d 中，关键字存储在与键值最接近的前向结点上，如图2 2 所示，在这 个c h o r d 网络中，n 为8 ，当前有3 个结点，分别为结点0 ，结点1 和结点2 。键值 为1 的关键字信息存储在与它最接近的前向结点1 上，键值为2 的关键字信息存储 在与它最接近的前向结点3 上，键值6 的关键字存储在与它最接近的前向结点0 上。 s u 图2 - 2c h o r d 网络关键字存储 在c h o r d 模型的路由过程中，每个结点只需要知道它在c h o r d 环中的后继结点。 在查询过程中，查询结点将请求发送到与键值最接近的结点上。收到查询请求的结 点如果发现自身存储了被查询的信息，可以直接回应查询结点；如果被查询的信息 不在本地，在自己的路由表中，从后往前找到键值前且与键值最近的结点。在新的 结点中，以同样的方式继续查找，一直持续到找到相应的结点为止。不难看出，查 询过程实际上就是折半查找的过程。c h o r d 的查找算法如下表2 2 的算法2 1 所示。 9 第二章基于c h o r d 的对等网络搜索模型分析 基于c h o r d 的p 2 p 搜索模型研究及其应用 表2 - 2c h o r d 查找算法 算法2 1 【3 5 】 请求结点n 查找与i d 匹配的后继结点 n f i n d _ s u c c e s s o r ( i d ) n = f m d _ _ p r e d e c e s s o r ( i d ) ； r e t u r nn s u c c e s s o r ； 请求结点查找与i d 匹配的前驱 n f m d _ p r e d e c e s s o r ( i d ) n = n ； w h i l e ( i d 在( n ，n s u c c e s s o r 范围内) n = n c l o s e t _ p r e c e d i n g _ f i n g e r ( i d ) ； r e t u r nn ： 返回i d 前最近的f i n g e r n c l o s e t _ p r e c e d i n g _ f i n g e r ( i d ) f o ri ；md o w n t o1 i f ( f i n g e r i n o d e ( n ，i d ) ) r e t u r nf i n g e r i n o d e ； r e t u r nn ： 在c h o r d 模型中，查询需要的跳数为o ( 1 0 9 n ) 。这样即使在大规模的p 2 p 网络 中( 例如n = 1 0 00 0 00 0 0 ) ，查询的跳数也仅为0 ( 2 7 ) ，每个结点仅需存储2 7 个( 1 b ( 1 0 0 0 0 0o o o ) ) 路由结点的信息。 举例说明，如图2 3 所示，结点3 想要查询k e y l ，它首先检查自己是否存储了 k e y l ，然后通过查询表确定与k e y l 键值最接近的结点0 ，发送查询消息；结点0 收到查询消息后，检查自己是否存储了k e y l ，然后通过查询表确定与k e y l 键值最 接近的结点1 ；结点1 收到查询消息后，确定k e y l 存储在本地，向结点0 确认。 1 0 基于c h o r d 的p 2 p 搜索模型研究及其应用第二章基于c h o r d 的对等网络搜索模型分析 q u s 切nl a t m r a ln o d e s l a t ti n t e r v a ln o d e 1 【1 ，碜 l 2 【2 ，母 3 一 2 【2 ，彤 3 3 【3 ，5 3 k e 4 【4 。1 ) o 5 【5 ，1 ) o j 弋 复 i 尚q 丫l o o kf o r1 j s t a r tl m e r v a ln o d e r 麓一 4 【4 ，匀 0 弋孓哆 5 【5 ，乃 0 7 【7 ，萄 o 2 2 2 结点的加入和离开 图2 - 3c h o r d 网络查询 ( 1 ) 结点加入。在c h o r d 中，结点的加入分为3 个阶段，如表2 - 3 3 5 1 所示。 表2 - 3 结点加入阶段 加入阶段细节描述 结点a 加入网络时必须知道网络中的某个结点 初始化本地结点查询表a 。这时，为了初始化a 的查询表，a 将要求结 点a 为它查找查询表中其他项 结点加入网络后通知其他结点，让其他结点即 更新其他结点查询表 时地更新自己的查询 其他结点将所有键值归属于a 的关键字( 即后 转移关键字信息 继结点是a 的关键字) 转移到结点上 假设新结点1 1 通过某种方法联系到一个c h o r d 现存结点n ( n 通常是众所周知 结点) ，n 通过n 初始化自己的信息，将自己加入到网络中，再将其后继中应该由 自己负责的对象移到自身。结点n 初始化，是通过n ，帮自己查找后继来初始化自 己的路由表。然后，结点n 通知其他应该在路由表中引用n 的结点更新信息。结点 加入的算法如下表2 4 的算法2 2 所示。整个结点加入的时间复杂度是o ( 1 0 9 2n ) ， 如果采用更加复杂的算法，可以把复杂度降低到o ( 1 0 9 n ) 。 第二章摹于c h o r d 的对等网络搜索模型分析基于c h o r d 的p 2 p 搜索模型研究及其应用 表2 - 4c h o r d 结点加入算法 算法2 2 【3 5 1 # d e f i n es u c c e s s o rf i n g e r 1 n o d e 结点n 加入网络 n 是网络中任意结点 n j o i n ( n 3 i f ( n 3 i n i t _ f i n g e r t a b l e ( n ) ； u p d a t e o t h e r s ( ) ； 将其后继结点中i d 位于( p r e d