（计算机软件与理论专业论文）基于dht的多关键字检索系统的研究与实现.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工科、计算机软件与理论 研究方向：软件技术及其在通信中的应用 作者：二零零七级硕士研究生：郭隆峦指导教师：签知值塾援 j 。 题目：基于d h t 的多关键字检索模型的研究与实现 英文题目：r e s e a r c ha n da p p l i c a t i o no fm u l t i - k e y w o r d ss e a r c hs y s t e mb a s e d d h tn e t w o r k 关键词：分布式哈希表；对等节点；多关键字；搜索；索引； 英文关键词：d i s t r i b u t e dh a s ht a b l e ( d h t ) ；p e e r - t o p e e r ( p 2 p ) ；m u l t i k e y w o r d s ； s e a r c h ；i n d e x ； 课题来源：( 1 ) 国家自然基金项目，6 0 9 7 3 1 4 0 1 f 0 2 0 8 ( 2 ) 江苏省自然基金项目，b k 2 0 0 9 4 2 5 ( 3 ) 江苏省高校自然基金项目，0 8 k j b 5 2 0 0 0 5 ( 4 ) 江苏省六大高峰项目 ( 5 ) 华为科技基金项目 艘 。 j 一 南京邮电大学硕士研究生学位论文 中文摘要 中文摘要 由于互联网资源的“成长性 、“自治性”和“多样性”，传统的c s 模式的资源搜索方 法逐渐不能满足发展需求。近年来，人们提出建立基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 的对等 网络实现资源信息的分布式发布和查询。但是d h t 技术具有精确查询的特性，导致其在 复杂查询方面存在不足。 本文在研究d h t 技术和多种基于d h t 的搜索技术的基础上，构建出一种新型的快速 的多关键字检索系统，简称为q m k s 。此系统是在本文总结出来的d h t 抽象模型基础上， 构建了d h t 资源网络；通过改进传统的m k q 模型，构建了资源的关键字索引网络。q m k s 系统通过扩展资源关键字索引的发布内容，改进节点对于关键字索引与其相关资源信息的 存储技术，使得一次多关键字搜索只需发送一个查询；同时通过在关键字索引发布时，引 入关键字的相关度，在关键字搜索时，对搜索的结果按照相关度大小进行排序。接着本文 在理论上分析了q m k s 系统的性能特点。 最后，本文实现了q m k s 原型系统，通过在实验室构建了一个基于局域网的d h t 网络 实验环境，在搜索访问节点数量、搜索响应时间、网络流量消耗、查准率和查全率这5 个 方面，与m k q 模型在作对比测试，测试结果表明，q m k s 系统具有搜索访问节点少，响应 速度快，消耗网络通信量少，查准率高等特点。 关键字：分布式哈希表：对等节点：多关键字：搜索：索引 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t d u et ot h ec h a r a c t e r i s t i c so fe v o l u t i o n ，a u t o n o m ya n dd i v e r s i t yo fi n t e m e tr e s o u r c e s ，t h e t r a d i t i o n a lc sm o d eo nr e s o u r c es e a r c hc a n tm e e tt h en e e d so fd e v e l o p m e n t r e c e n t l y , r e s e a r c h e r sp r o p o s e dt or e a l i z et h ed i s t r i b u t e dp u b l i c a t i o na n dq u e r yo fi n t e m e tr e s o u r c e i n f o r m a t i o nt h r o u g hd h t ( d i s t r i b u t e dh a s ht a b l e ) n e t w o r k ，w h i c hi sak i n do fp e e r - t o p e e r n e t w o r k h o w e v e lt h ed h tt e c h n o l o g yh a st h ee x a c tc h a r a c t e r i s t i c si nt h eq u e r y , r e s u l t i n gi n d e f i c i e n c yi nc o m p l e xq u e r y b a s e do nt h er e s e a r c ho ft h ed h tt e c h n o l o g ya n dv a r i o u sm u l t i k e y w o r d ss e a r c h t e c h n o l o g yf o rd h t , t h i sp a p e rp r o p o s e san o v e la n dq u i c km u l t i k e y w o r d ss e a r c hs y s t e mo nt h e b a s i so ft h ed h tn e t w o r k ，n a m e dq m k sf o rs h o r t t h eq m k ss y s t e mb u i l d sar e s o u r c e n e t w o r ko nt h ed h ta b s t r a c tm o d e l ，w h i c hs u m m a r i z e di nt h i sp a p e r , a n dc o n s t r u c t sa ni n d e x n e t w o r ko ft h er e s o u r c e sk e y w o r d s b yi m p r o v i n gt h et r a d i t i o n a l m k qm o d e l t h r o u g h e x t e n d i n gt h ek e y w o r d si n d e xo ft h er e s o u r c ew h e np u b l i s h e d ，a n di m p r o v i n gt h es t o r a g e m e c h a n i s ma b o u tt h ek e y w o r d si n d e xa n dt h e c o r r e s p o n d i n gr e s o u r c ei n f o r m a t i o n ，q m k s s y s t e ms u p p o r t s t h e m u l t i k e y w o r d s s e a r c he f f e c t i v e l y , a n di t o n l y u s e so n eq u e r yi na m u l t i - k e y w o r d ss e a r c h i na d d i t i o n ，i ts o r t st h es e a r c h i n gr e s u l ta c c o r d i n gt ot h ec o r r e l a t i o n m e a s u r eo fk e y w o r d a n dt h e nw e a n a l y s et h ep e r f o r m a n c eo ft h eq m k ss y s t e mt h e o r e t i c a l l yi n t h ep a p e r f i n a n l l y , w ei m p l e m e n tt h ep r o t o t y p es y s t e mo fq m k s ，a n de s t a b l i s ha ne x p e r i m e n t a t i v e d h tn e t w o r ki nt h el a no fl a b o r a t o r y s u b s e q u e n t l y , w ed os o m em u l t i k e y w o r d ss e a r c ht e s ti n o r d e rt oc o m p a r et h ec a p a b i l i t yo fq m k ss y s t e mw i t hm k qm o d e l t h et e s tr e s u l t ss h o wt h a t q m k ss y s t e mv i s i t s1 6 s sn u m b e ro ft h ep e e r s ，r e s p o n d sm o r eq u i c k l y , c o n s u m e sl e s sn e t w o r k t r a f f i c ，a n dh a sah i g h e rp r e c i s i o nr a t i oi nt h em u l t i k e y w o r d ss e a r c h k e y w o r d s ：d i s t r i b u t e dh a s ht a b l e ( d h t ) ；p e e r - t o p e e r ( p 2 p ) ；m u l t i k e y w o r d s ；s e a r c h ；i n d e x h - 蕾力【 南京邮电大学硕士研究生学位论文 目录 目录 中文摘要j i a b s t r a c t i i 目录i i i 第一章引言1 1 1 课题背景1 1 2 课题来源。2 1 3 论文结构安排。2 第二章相关技术研究4 2 1d h t 思想及其网络结构分析- 4 2 1 1c h o r d 简介。5 2 1 2p a s t r y 简介。6 2 1 3c a n 简介7 2 1 4t a p e s t r y 简介8 2 1 5d h t 网络抽象模型9 2 2 基于d h t 的多关键字搜索技术分析1 1 2 2 1m k q 搜索模型1 1 2 2 2 空间填充曲线模型1 2 2 2 3 空间向量模型：1 2 2 2 4 讨论1 3 2 3 本章小结1 3 第三章q m k s 系统的总体设计1 5 3 1 系统总体设计1 5 3 2 系统模块的功能描述1 6 3 3 系统处理流程1 7 3 3 1 资源发布流程。1 7 3 3 2 资源搜索流程1 9 3 4 本章小结2 l 第四章q m k s 系统的d h t 资源网络实现2 2 4 1d h t 资源网络的构建2 2 4 2d h t 资源网络的路由管理2 3 4 2 1 路由表的管理2 3 4 2 2 消息处理流程2 4 4 3d h t 资源网络的资源管理。2 6 4 3 1 资源表和资源的管理2 6 i l l 塑室坚皇奎堂堡主堕窒生堂垡笙茎 旦茎 _ _ _ _ 。_ _ _ _ _ _ _ _ _ - _ 。_ _ 。_ _ _ _ 。_ - 。_ - _ _ _ _ _ 。_ _ _ _ _ _ _ _ 。- 。_ _ _ _ _ _ _ _ - _ _ _ _ _ - i _ - _ - _ _ _ _ _ _ 。_ 。- - 。_ 。_ - _ - 。_ _ 。1 1 。 4 3 2 消息处理流程2 7 4 4d h t 资源网络的资源索引管理2 9 4 4 1 资源索引表的管理2 9 4 4 2 消息处理流程3 0 4 5 本章小结3 2 第五章q m k s 系统的多关键字搜索实现3 3 5 1 资源关键字索引的发布3 3 5 1 1 引入关键字的相关度。3 3 5 1 2 扩展关键字索引发布的内容3 4 5 1 3 关键字索引发布流程3 5 5 2 资源关键字索引的管理3 7 5 2 1 传统的倒排存储方式3 7 5 2 2 改进的存储方式3 7 5 2 3 关键字索引存储流程3 9 5 2 4 关键字索引查询流程4 0 5 3 多关键字的资源搜索4 3 5 3 1q m k s 系统的多关键字搜索方式4 3 5 3 2 关键字搜索模块消息处理4 5 5 4q m k s 系统的搜索特性分析。4 6 5 4 1 关键字索引存储消耗低。4 6 5 4 2 查准率和查全率4 7 5 4 3 搜索快速4 8 5 4 4 负载平衡4 8 5 5 本章小结4 9 第六章q m k s 原型系统的实现与性能测试5 0 6 1q m k s 原型系统的实现5 0 6 1 1 系统开发环境5 0 6 1 2 系统运行界面：5 0 6 2q m k s 系统的性能测试。5 7 6 2 1 测试背景5 7 6 2 2 测试结果5 8 6 3 本章小结6 2 第七章论文总结与展望6 3 7 1 全文总结6 3 7 2 本系统的不足和未来工作展望6 3 图表清单6 5 致谢6 7 参考文献6 8 攻读硕士学位期间撰写的论文与专利7 l 南京邮电大学硕士研究生学位论文 第一章引言 1 1 课题背景 第一章引言 随着互联网的飞速发展，互联网里的资源具有成长性( 资源规模不断膨胀、资源关联 关系不断变化) 、多样性( 资源属性存在广泛的差异) 和自治性( 资源局部自治、自主决 策) 等三个相互联系的特性，给资源搜索带来了挑战。由于不能适应这些特性，传统的基 于c s 模式的资源搜索方法成为了互联网应用的性能瓶颈【1 】。 近年来提出的基于p e e r - t o p e e r ( p 2 p ) 模式实现资源搜索，祢补了c s 模式的不足。 在基于p 2 p 的资源搜索中，p 2 p 网络中的每个节点在逻辑上是平等的，既充当服务器角色， 也充当客户端角色，这样就能充分发挥网络中每一台电脑的性能，大幅度地提高网络资源 的利用效率和资源的搜索效率。 根据网络中各节点的逻辑拓扑关系，采用p 2 p 资源搜索技术的网络可以分为非结构化 p 2 p 网络和结构化p 2 p 网络两大类 2 】。在非结构化p 2 p 网络中，节点问的逻辑拓扑关系 通常较为松散，具有较大的随意性，资源信息的放置通常也与网络的拓扑结构无关。在结 构化p 2 p 网络中，节点间的逻辑拓扑关系通常由确定性的算法严格控制，资源信息的放置 也是由确定性的算法发布到特定的节点上。由于采用结构化p 2 p 网络通常基于分布式哈希 表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 进行构建，因此也称为d h t 网络 3 】。由于具有更好的 可扩展性，更高的健壮性，检索具有可确定性、简单性和分布性等优点，d h t 技术在p 2 p 网络的发展中脱颖而出，得到了越来越多p 2 p 软件的支持 4 5 。 在d h t 网络( 比如b t 、e m u l e ) 的海量资源信息面前，个人用户的需求是个性化的， 这时如何快速并准确地定位需要的资源成为了热门的研究课题。以b t 为代表的文件共享 类p 2 p 下载软件，往往采用了独立于d h t 网络之外的资源索引服务器作为种子搜索引擎( 如 盯中国联盟) ，它不是基于d h t 网络的搜索，如果资源索引服务器失效，搜索就无法进行 6 7 。最近b t 中国联盟、西摩b t 站、龙漫b t 等b t 种子搜索网站被广电总局强制关闭， 意味着国内b t 时代的落幕，就证明了这一点。而e u m l e 既采用独立的资源索引服务器， 也采用d h t 网络作为搜索引擎，所以当服务器被关闭后，只要节点加入了d h t 网络，依然 能够通过d h t 网络提供的搜索引擎找到需要的资源，而d h t 网络只要有节点在线就能自动 南京邮电大学硕士研究生学位论文 第一章引言 形成，无法人为关闭，证明了基于d h t 的检索技术具有更强的健壮性。 所以，基于d h t 网络的搜索，由于具有可扩展性，分布性和健壮性，所以是未来的发 展趋势。在d h t 网络的搜索过程中，由于单关键字往往无法准确描述搜索对象，必定需要 传统的多关键字组合，通配符，同义词等复杂搜索功能，然而d h t 的哈希及分布式思想决 定了其只能支持以单关键字、多关键字组合为代表的精确搜索，无法支持以通配符，同义 词为代表的模糊搜索，所以当前的研究焦点是基于d h t 的多关键字搜索。其中多关键字的 组合一般支持“a n d 、“o r 和“n o t ”等逻辑组合方式，遵循布尔运算法则，这些方式 能一定程度上满足用户个性化的设置要求，更精确地定位需要的资源 8 9 。 综上所述，研究融合了p 2 p 技术和搜索技术的基于d h t 网络的多关键字检索系统，既 是现实的需要，也是未来p 2 p 网络发展的需要。 1 2 课题来源 本课题来源于北京华为科技基金项目“p 2 p 重叠网络及其安全关键技术的研究 ，和南 京华为科技基金项目“p 2 p s i p 原型系统研究 与“i p o s t 原型系统研究”。这些项目以研 究d h t 网络特性，建立d h t 实验网络为目标，结合s i p 技术或视频点播技术，实现传统语 音视频技术基于d h t 网络的定位和传输。 参与项目过程中，所做与本课题相关工作如下： l 、分析了d h t 网络的思想，了解了d h t 技术的优点和缺点。 2 、研究并代码实现了在d h t 中有代表性的c h o r d 算法，p a s t r y 算法，为以后对d h t 网络进行抽象总结，有了理论和实践的基础知识。 3 、从p 2 p s i p 和i p o s t 项目的实践过程中，了解到资源搜索的重要性，并用代码实现 了基于d h t 网络的单关键字资源搜索功能。 4 、对基于d h t 网络的多关键字搜索做了一些基础研究，了解该技术实现过程的重点和 难点。 1 3 论文结构安排 本文详细介绍了基于d h t 网络的多关键字检索的解决方案，提出了q m k s ( q u i c k m u l t i k e y w o r d ss e a r c h ，快速多关键字搜索) 系统，介绍了该系统的总体设计、系统中每 个模块的功能，设计和接口，介绍了多关键字搜索的原理，总结了q m k s 系统的搜索特性， 最后用代码实现了该系统，对系统的搜索特性进行了测试与分析。 2 - 南京邮电大学硕士研究生学位论文 第一章引言 本文共分七大章节，组织如下： 第一章首先简要介绍了本课题的研究背景、课题来源，项目的研究内容、以及参与 项目过程中所进行与课题相关的研究工作。 第二章列举并分析了d h t 网络技术的核心思想，和基于该思想发展出来的4 种著名 算法及其对应的网络拓扑结构，总结出d h t 网络的抽象模型。然后介绍了3 种典型的基于 d h t 的多关键字搜索技术，并讨论了每种技术的优缺点，确定了改进现有搜索技术的方向。 第三章提出了q m k s 系统的总体设计，对系统的各个功能模块进行了描述，并详细介 绍了系统进行资源发布和资源搜索的流程。 第四章介绍了q m k s 系统组建d h t 资源网络的3 个主要模块，它们是路由模块、资源 ” 管理模块和资源索引管理模块，描述了每个模块所负责的表和消息的管理过程。 第五章介绍了q m k s 系统组建资源关键字索引网络的3 个主要模块，它们是关键字索 引发布模块、关键字索引管理模块和关键字搜索模块，描述了每个模块所负责消息的处理 流程，重点介绍了关键字相关度如何计算，发布的关键字索引内容如何扩展，关键字索引 相关信息如何存储，多关键字索引如何查询等。最后总结了q m k s 系统的搜索特性，并进 行了细致的分析。 第六章实现了q m k s 原型系统，并对系统搜索流程、用户界面进行了一一介绍。然后 基于著名的d h t 网络( p a s t r y 网络) ，通过与典型的m k q 模型在搜索访问节点访问数量、 搜索响应时间、消耗的网络流量、查准率和查全率这5 个方面做对比性测试。 第七章总结本文所做的工作，并指出系统有待进一步完善之处和未来发展的方向。 南京邮电大学硕士研究生学位论文 第二章相关技术研究 第二章相关技术研究 本章分两部分介绍相关技术，第一部分主要介绍现有的d h t 网络技术，包括d h t 的核 心思想，基于该思想发展出来的4 种著名算法及其对应的网络拓扑结构，最后总结了d h t 网络的抽象模型。第二部分介绍3 种基于d h t 的搜索技术，并列出每种技术的优缺点，通 过比较和改进，确定了本文的多关键字搜索技术模型。 。_ 2 1d h t 思想及其网络结构分析 d h t ( d is t r i b u t e dh a s ht a b l e ，分布式哈希表) 是一种全分布式结构化的p 2 p 网络结构， 其采用分布式哈希算法来解决结构化的分布式存储问题。与其他p 2 p 网络拓扑结构的相比， d h t 具有更好的可扩展性，能以较低系统开销获得较大的系统规模；在节点失效、遭受攻 击和突发性高负载面前表现出更高的健壮性；而且分布式检索和路由算法具有查找可确定 性、简单性和分布性等优点 1 0 。 d h t 的核心思想是：首先，网络里面每个节点的i d 是使用一致性哈希算法映射的1 2 8 位或1 6 0 位的散列值( 简称为n o d e l d ) ，哈希算法保证了每个节点的n o d e l d 是一个全局唯 一的标识符，这样所有节点根据n o d e i d 形成一个构建于i n t e r n e t 之上的自组织的层叠网。 同时每个资源的i d 也是经过相同的一致性哈希运算得到的散列值( 简称为k ) ，这样节点 和资源都映射到同一个空间上，可以通过一致的路由算法找到节点或资源。资源一般存储 在拥有该资源的节点上，但是资源的索引信息分布式存储在网络中，所以每个资源的索引 被表示成一个( k ，v ) 对，k 是资源的i d ，可以是资源名( 或资源的其他描述信息) 的散列 值，v 是实际存储资源的节点的i p 地址( 或节点的其他描述信息) 。所有的资源索引条目( 即 所有的( k ，v ) 对) 组成一张大的资源索引哈希表，只要输入目标资源的k 值，就可以从 这张表中查出所有存储该资源的节点地址。d h t 网络其实是将上面的大资源哈希表按某种 规则分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有 参与节点上，使得每个节点负责维护其中的一块。这样，节点查询某资源时，只要d h t 网 络把查询报文路由到负责该资源索引的节点即可( 该节点的n o d e i d 与资源索引k 最接近) ， 最后查询节点根据返回的资源索引的v 值就可以找到真正存储资源的节点 1 1 - 1 2 。 这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也 4 南京邮电大学硕士研究生学位论文 第二章相关技术研究 就决定了节点需要维护特定形式的路由表，表中包含一些邻居节点的节点消息( n o d e l d 和 节点i p 等) ，以便各种消息基于消息的k e y 选择邻居节点进行转发。这个规则因具体算法 的不同而不同，c h o r d ，p a s t r y ，c a n 和t a p e s t r y 这4 种著名的d t t t 算法，都有自己的规 则，根据各种算法，分别构建了不同的网络拓扑结构，下面将对这4 种d h t 算法的拓扑构 建、消息路由以及性能进行概述。 2 1 1c h o r d 简介 c h o r d 在2 0 0 1 年由麻省理工学院提出的，其核心思想就是要解决在p 2 p 应用中遇到的 基本问题：如何在p 2 p 网络中找到存有特定数据的节点。c h o r d 使用一致性哈希作为哈希 算法。 c h o r d 网络中每个节点和关键字的标识都是一个m = 1 6 0 位的二进制串( 即0 到2 ”一1 ) ， 可以根据节点的i p 地址或关键字名称通过s h a 1 算法获得，所有节点根据节点标识符的 大小顺时针构成一个环形的拓扑结构，如图2 1 所示。给定关键字k e y ，c h o r d 首先对其 进行哈希，设h a s h ( k e y ) = x ，c h o r d 将通过一致性哈希算法，将k e y 发布到x 在环上的 后继节点( 环中沿顺时针方向最近的节点) 上。环拓扑中每个节点都维护了其后继节点的 路由信息，在环上沿后继节点总可以正确地到达任何目标节点，但这种方法效率很低。 所以，c h o r d 在一致性哈希的基础上提供了优化的路由算法：在c h o r d 中，每个节点都 维护一张路由表( f i n g e r 表) ，f i n g e r 表至多有m 项，节点n 的f i n g e r 表第i 项是值靠+ 2 ”1 在c h o r d 环上的后继节点。资源搜索时，每个节点都通过查询f i n g e r 表，将搜索请求转发 到离k e y 最近的节点上。这样形成的节点之间路由关系实际上就是折半查找算法需要的排 列关系 1 3 1 。 经过c h o r d 的优化后，查询需要的跳数由o t n ) 减少到o ( 1 0 9 ：) 。这样即使在大规模 的p 2 p 网络中( 例如n = 1 0 0 ，0 0 0 ，o o o ) ，查询的平均跳数为o ( 6 ) ，每个节点仅需存储2 7 个 ( 1 0 9 ：1 0 0 0 0 0 0 0 0 ) 其他节点的信息。c h o r d 还考虑到多个节点同时加入系统的情况并对节点 加入退出算法作了优化。 如图2 1 ，展示了节点i d 为4 位，共1 6 个节点组成的c h o r d 网络拓扑结构( n - - i 以想象成一 个环结构) ，并且给出了一个查询消息转发的路由过程，查询消息从0 0 0 0 发出，目的节点 是0 1 1 1 。 南京邮电大学硕士研究生学位论文 第二章相关技术研究 2 1 2p a s t r y 简介 - 1 1 1 0 ， i 1 1 0 1 l l o o 1 1 0 i l 。 一1 0 1 0 r o u t e ( o l “) ：l l l 0 0 。n 0 0 l i 1 0 0 1 1 0 0 00 1 黝3 图2 1c h o r d 网络拓扑结构图 p a s t r y 在2 0 0 1 年由位于英国剑桥的微软研究院和莱斯( r i c e ) 大学提出。p a s t r y 使用一致 性哈希作为哈希算法。哈希所得的键值为一维( 实际上使用的是1 2 8 b i t 的整数空间) 。p a s t r y 也没有规定具体应该采用何种哈希算法【1 4 】。 在p a s t r y 协议中，每个节点都拥有一个1 2 8 b i t 的标识( n o d ei d ) 。为了保证n o d ei d 的 唯一性，一般由节点的网络标识( 如i p 地址) 经过哈希得到。p a s t r y 中的每个节点拥有一个 路由表( r o u t i n gt a b l e ) ，一个邻居节点集( n e i g h b o r h o o ds e t ) 和一个叶子节点集合( l e a f s e t ) ， 它们一起构成了节点的状态表。其中路由表与t a p e s t r y 路由表相似，而邻居节点集和叶子 节点集则是为了提高消息路由效率和实现与物理网络的拓扑匹配。邻居集中包含了与本节 点物理延迟最低的m 个节点，叶子节点集中是与本节点标识逻辑距离最近的l 个节点 路由查询消息中将携带被查询对象i d ( o b j e c ti d ) ，又称消息键值。当收到路由消息时， 节点首先检查消息键值是否落在叶子节点集合的范围内。如果是，则直接把消息转发给叶 子节点集合中节点标识和消息键值最接近的节点；否则就从路由表中根据最长前缀优先的 原则选择一个节点作为路由目标，转发路由消息。如果不存在这样的节点，当前节点将会 从其维护的所有邻居节点集合( 包括路由表叶子集合及邻居集合中的节点) 中选择一个距离 消息键值最近的节点作为转发目标。 从上述过程中可以看出，每一步路由和上一步相比都更靠近目标节点，因此这个过程 是收敛的。如果路由表不为空，每步路由至少能够增加一个前缀匹配数位，因此在路由表 始终有效时，路由的步数至多为l o g ：。n ( b 为一个前缀的b i t 位数量) 。 南京邮电大学硕士研究生学位论文 第二童扫羞塾型! ! 堕 如图2 - 2 ，展示了节点i d 为4 8 比特位，b ：4 ，2 4 6 个节点组成的p a s t r y 网络拓扑结构 ( 可以想象成一个环结构) 。并且给出了一个查询消息转发的路由过程，查询消息从6 5 1 a f t 发出，目的节点是负责d 4 6 a l c 的节点d 4 6 7 c 4 。 2 4 60 2 1 3c a n 简介 图2 2p a s t r y 网络拓扑结构图 c a n 协议是2 0 0 1 年由a t & t a c i r i 中心研究出来的，c a n 的独特之处在于采用多维 的标识符空间来实现分布式散列算法【1 5 】。 在c a n 中，每个节点自身的i d 经由哈希后得到的d 维向量。经过这样的映射后，整 个p 2 p 系统将被映射到一个d 维笛卡尔空间中，系统中每个节点在空间中的位置由其自身 i d 决定，也就是每个节点分别负责d 维空间中的一块区域，所有节点负责整个d 维空间。 c a n 对邻居节点的定义并不要求成2 i 的关系排列，而是改为用在笛卡尔空间上相邻来表 示：在d 维笛卡尔空间中，2 个节点的d 维坐标中有d 1 维是相等的，剩余的一维是相邻 的节点称之为相邻节点。 c a n 中的节点仅存储相邻节点表。由于在d 维的空间中最多有2 d 个相邻的节点，因 此节点的相邻节点表最多有2 d 个表项。 每个资源对象有一个关键字，通过哈希函数对关键字进行哈希，进而将资源对象映射 到d 维空间中一点，资源对象就发布到负责该点的节点上。在查询资源对象的过程中，查 询节点首先计算被查询内容的键值( d 维向量) ，然后在节点列表中查找在笛卡尔空间中与该 键值最为接近的相邻节点，找到后向该节点发送查询请求。查询请求中将携带被查询内容 的键值。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点； 7 南京邮电大学硕士研究生学位论文第二章相关技术研究 如果被查询的信息不在本地，就根据相邻节点表将请求转发到与键值最接近的节点上。这 样的过程一直持续到找到相应的节点为止。在查询过程中，被查询节点到目标节点的笛卡 尔空间距离单调地减少。 如果查询节点或转发节点发现邻居节点表中无法找到可用的下一跳节点，则采用非结 构化p 2 p 常用的扩展环搜索( e x p a n d i n gr i n gs e a r c h ，使用无状态，受控的泛洪算法在重叠 网中搜索) 以找到合适的下一节点。 经过c a n 的优化后，查询需要的跳数由o ( n ) 减少到均值为l 4 d n 4 ，考虑到d 为常 数，这一值可以表示为o ( d ) 。 如图2 3 ，展示了一个2 维的【o ，l 】【0 ，1 】的笛卡儿坐标空间划分成5 个节点区域的c a n 网络拓扑结构，并且给出了一个查询消息转发的路由过程，查询消息从a 发出，目的节点 是负责 0 3 ，0 7 的节点e 。 2 1 4t a p e s t r y 简介 图2 32 维c a n 网络拓扑结构图 t a p e s t r y 是2 0 0 4 年由加州柏克莱大学提出，是利用节点i d 之间前缀匹配的结果所形 成的网状网络。t a p e s t r y 使用s h a 1 来产生1 6 0 比特的标识符，标识符用一个全局统一的 进制表示( 例如使用1 6 进制，则标识符是一个4 0 位的数字) ，所有的节点依据标识符自 组织成一个重叠网络 1 6 】。 t a p e s t r y 中的每个节点都保存有邻居映射表。邻居映射表可以用于把消息按照目的地址 一位一位地向前传递，比如从4 + + - 4 2 幸9 8 = 4 2 a 一 目的节点4 2 a d ( 这里幸表示通配符) 。 节点n 的邻居映射表分为多个级别，每个级别包含的邻居节点的数量等于标识符表示法的 基数，而每个级别中邻居节点标识符和本节点标识符的相同前缀都比前一级别多一个数 南京邮电大学硕士研究生学位论文 第二章相关技术研究 位。也就是说，第j 级邻居表的第i 项是标识符以p r e f i x ( n ，j 。1 ) + “i 为前缀而且离当前 节点最近的邻居节点。例如，节点3 2 5 a e 的邻居映射表中第4 级第9 项是系统中标识符以 3 2 5 + “9 = 3 2 5 9 为前缀的某个节点。 t a p e s t r y 采用的基本查找和路l h 机制：当一条查找消息到达传递过程中的第1 1 个节点 时，该节点和目的节点的共同前缀长度至少大于n 。为了进行转发，该节点将查找邻居映 射表的第n + 1 级中和目的标识符下一数位相匹配的邻居节点。转发过程将在每个节点中依 次进行直到到达目的节点。这种方法可以保证路由至多经过l o g b n 个节点就可以到达目的 节点，这里n 是节点标识符名字空间的大小，而b 是标识符使用的基数。所以路由最多在 o ( 1 0 9 。n ) 跳数内完成。 如图2 4 ，展示了一个节点i d 为1 6 比特位，b = 4 ，网状的t a p e s t r y 的拓扑结构。并且 给出了一个查询消息转发的过程，查询消息从5 2 3 0 发出，目的节点是4 2 a d 。 2 1 5d h t 网络抽象模型 图2 4t a p e s t r y 网络拓扑结构图 通过以上对4 种具体系统的分析，按照消息类型和处理过程，总结出d h t 网络的每个 节点主要由三个模块组成：路由模块、资源管理模块和资源索引管理模块。如图2 5 所示： 南京邮电大学硕士研究生学位论文第二章相关技术研究 网络其他节点 | t 憋 儒 伊 网络其他节点 d h t 网络节点 资源管理 模块 图2 5d h t 网络节点抽象模型 ( 1 ) 路由模块：该模块主要维护路由表，并且根据路由表转发查询消息，其中路由表 按一定的规则存储邻居节点的节点信息，路由表的存储结构和数量由具体的算法决定( 比 如c h o r d 只有一张路由表f i n g e r t a b l e ，而p a s t r y 有3 张路由表，包括l e a f s e t 、r o u t i n g t a b l e 和n e i g h b o r h o o d ) 。 ( 2 ) 资源管理模块：该模块主要维护资源表，该表存储本节点拥有的所有资源的信息， 支持对该表表项进行增加、删除、修改等操作，同时负责存储本节点拥有的所有资源和提 供这些资源给需要的节点。 ( 3 ) 资源索引管理模块：该模块主要维护资源索引表，该表存储网络中由本节点负责 管理的所有资源索引信息，同时支持对这些索引信息进行增加、删除、修改等操作。 d h t 抽象网络模型中，各个模块的交互过程如下： l 、当节点a 从网络中收到资源索引查询请求消息，首先通过路由模块查找路由表，判 断该查询请求消息是否由本节点负责，如果不是就从路由表中找出下一个更接近的节点， 并向其转发查询请求消息；如果是由本节点负责，就根据查询请求消息要求的操作，对资 源索引管理模块的资源索引表进行相应的操作( 包括查询、增加、删除、修改等) ，最终 把操作的结果作为消息应答返回给发起资源索引查询请求节点b 。 2 、当节点b 收到查询结果，从中取出拥有该资源的节点c 的地址信息，然后向节点c 发出获取资源请求。 3 、当节点c 收到该资源获取请求后通过资源管理模块，先查询资源表，得到该资源对 应的信息，然后返回该资源给节点b 。 上述消息的传递方式可以是迭代，也可以是递归，由于迭代更多地涉及到网络节点n a t 穿越，所以采用递归方式较为常见。 南京邮电大学硕士研究生学位论文第二章相关技术研究 2 2 基于d h t 的多关键字搜索技术分析 在以d h t 为基础的p 2 p 网络里面，每台p c 机都共享信息，所以提供的信息量是巨大 的，个人用户的需求也是个性化的。如何在这么多的信息里面找到自己需要的，必须依靠 搜索引擎的支持。 在现有的d h t 模型中，当需要对网络中存储的资源信息进行查找时，则给定一个关 键字，d h t 节点可以根据此关键字有效地寻找到负责该关键字的节点a ( 节点a 的n o d e i d 值与关键字哈希得到的键值k 在数值上是最接近的) ，然后在节点a 的资源表中搜索与k 相同的资源索引信息，并把得到的结果返回给查询节点。可以看出在现有d h t 模型中， 对资源信息的检索是基于单一关键字的，即节点的n o d e l d 只代表某些其负责的关键字的 信息，由于单关键字无法准确描述搜索目标，这时需要多个关键字描述，然而当对包含多 个关键字的信息进行检索时，根据哈希算法的特性( 内容相似的值哈希后得到的值相差非 常大) ，往往每个关键字分别存储在不同的节点上，所以只能分别在多个