（计算机应用技术专业论文）twohop：p2p网络的一种搜索协议.pdf

摘要 p 2 p 网络现在已经相当流行，目前提出了很多种p 2 p 协议，且多数是基于 分布式h a s h 表( d h t ) 的结构，有些也已经在实际中得到了应用，如基于 t a p e s t r y 1 9 】【2 0 】的o c e a n s t o r e 基于k a d c m l i a 1 7 】的o v c m e t 等等。在研究这些协 议之后发现，多数协议只考虑了网络的规模化问题，都有着相当的查询延迟， 这只适合于那些对查询延迟要求不高的应用( 如文件备件等等) ，虽然o n c h o p l l 2 l 和k c l i p s i “】的查询代价为o ( 1 ) ，但前者在网络规模增大时对带宽需求急剧增加， 后者在稳定网络状态方面需要很高的代价。 本文首先介绍了对等网的研究现状和发展趋势，然后对目前的p 2 p 协议进 行了分析，分类，比较，并对各种模式的适用范围进行了系统的讨论。 本文主要的工作是提出一种p 2 p 协议t w o h o p ，该协议的网络结构类似 o r l c h o p ，都是采取三层结构：在结点路由信息的存储上类似k c l i p s ，同样分为 内部信息和外部信息。这样做的目的是保证快速的查询延迟，同时所需要的带 宽在网络规模很大( 结点数1 0 8 ) 时也能接受。 在仿真实验中，将看到t w o h o p 和o n e h o p 的主要特点，以及与之楣比的 优势，但任何一个协议都有它工作的环境，t w o h o p 在网络规模较大( 结点数 1 0 6 以上) ，且网络状态的变动较小时，才能体现出它的优势。 本文所提出的t w o h o p 协议尚未有实际的应用，但在仿真部分的c + + 代码 部分地实现了t w o h o p 协议的功能和目的。 关键词： 对等网分布式h a s h 表o n c h o pt w o h o p a bs t r a c t n o w a d a y st h ep 2 pn e t w o r ki sv e r yp o p u l a r , a n dt h e r ea r ep l e n t y0 fp 2 p p r o t o c o l sm o s to fw h i c ha r eb a s e do nt h es t r u c t u r eo fd i s t r i b u t e dh a s ht a b l e ( d h t ) 晦色c a l ls e es o m ea p p l i c a t i o n su s i n gp 2 pp r o t o c o l ss u c ha s0 c e a n s t o r eb a s e do n t a p e s t r y 1 9 儿2 0 1 ，a n do v e r n e tb a s e do nk a d e m l i a 1 7 c u r r e n t l yp 2 ps y s t e m sh a v e h i g hl o o k u pl a t e n c ya n da r et h e r e f o r eo n l yw e l l s u i t e df o ra p p l i c a t i o n st h a td on o t m i n dh i g h l a t e n c ys t o r ea n dr e t r i e v eo p e r a t i o n s ( e g b a c k u p s ) o rt h a ts t o r ea n d r e t r i e v em a s s i v ea m o u n t so fd a t a ( e g ，as o u r c et r e ed i s t r i b u t i o n 、) a l t h o u g _ ) h o n e h o p 1 2 a n dk e l i p s 1 8 g u a r a n t e et h a tf i l el o o k u p sa r er e s o v e dw i t h0 0 ) t i m e a n dc o m p l e x i t y ( i e ，i n d e p e n d e n to fs y s t e ms i z e ) ，t h ef o r m e ri s n tf i t t e df o rt h el a r g e s c a l a b l en e t w o r kb e c a u s ei tw i l lc o n s u m em o r eb a n d w i t ht h a nb e i n gt o l e r a t e d ，a n d t h el a t t e rn e e d sm o r et i m et os t a b i l i z et h en e t w o r kw h e ns o m ee v e n t sh a p p e n e d t h i sd i s s e r t a t i o nb e g i n sw i t ht h ec u r r e n tr e s e a r c hs i t u a t i o na n dt h ed e v e l o p i n k t r e n do fp 2 pn e t w o r k ，a n dt h e ni n t r o d u c e st h ec u r r e n tp 2 p p r o t o c o l s i nt h i sd i s s e r t a t i o n ，w ed e s c r i b ean e ws c a l a b l ep 2 pp r o t o c o l ，t w o h o p ，p a r t l y o r i g i n a l l yf r o mo n e h o p 1 2 ，u s i n g3l a y e r si nt h en e t w o r k e a c hn o d ek e e p st w o p a r t sr o u t i n gi n f o r m a t i o nl i k ek e l i p s 1 8 ，o n ef o rl o c a ll o o k u p s ，a n dt h eo t h e rf o r r e m o t el o o k u p s t w o h o pc a ne n s u r et h el o wl o o k u pl a t e n c ya n dt h ea c c e p t a b l e b a n d w i t hc o n s u m i n ge v e ni nt h el a r g es c a l en e t w o r k ( e g ，1 0 6n o d e s ) i nt h es i m u l a t i o n ，w ec a ns e ed i f e e r e n c e sb e t w e e no n e h o pa n dt w o h o p t 钾o h o pi s s u i t a b l ef o rt h el a r g es c a l en e t w o r ka n di nt h er e l a t i v e l ys t a b l e e n v i r o n m e n t 1 h e r ea r en oa p p l i c a t i o n su s i n gt o h o pa tp r e s e n t a n dt h ec + + c o d e si n s i m u l a t i o n sp a r t l ya c c o m p l i s hf u n c t i o n sa n dg o a l si nt o h o pp r o t o c 0 1 k e y w o r d s ： p e e r - - t o - - p e e rn e t w o r kd i s t r i b u t e dh a s ht a b l e o n e h o pt w o h o p 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得 的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得鑫注盘堂或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示了谢意。 学位论文作者签名：毛糸绞签字日期：勺石年2 月豸日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权鑫盗盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：云参贬 签字日期：矽6 年1 月移 导师签名： 弘动= 1 签字日期：馕p g 年 2 - , e l 够日 签字日期：馕p 年日 第一章绪论 第一章绪论 结构化的对等网络，如c h o r d 垌，k a d e m l i a ! r n ，k e l i p s 堋，t a p e s t r ，1 9 捌， 为构建大规模分布式应用提供了基础环境，它们允许应用程序通过有限步的查 找而定位系统中的某个对象。由于他们认为p 2 p 网络的成员是经常变化的，所 以每个结点存储的路由信息不能太大，多数协议取o ( 1 0 9 ) ( n 为网络结点数) ， 于是多数协议在定位对象时的查找步数也d ( 1 0 9 ) 。而g u p t a 等人提出了一种 新的协议o n e h o p l l 2 1 ，其中每个结点存储p 2 p 网络的所有路由信息，因此在定 位对象时只需d ( 1 ) 的查找时间，他们证明了在网络结点数在1 0 6 以内，且成员 变动较小时，此种定位算法是可行的。但当网络结点更多或成员变动频繁变动 时，o n e h o p 可能失效，本文依据o n e h o p 的思想提供了另一种协议t w o h o p ， 在极高的概率下保证定位对象的查找步数为2 。本章主要介绍了对等网络的概 念和方法，分布式h a s h 表( d h t ：d i s t r i b u t e dh a s ht a b l e ) 的相关技术，以及 作者所做的工作。 1 1 对等互联( p e e r - t o p e e r ) 技术 本节将简要介绍对等互联技术、对等网的概念、分类、应用领域、发展研 究现状。 1 1 1 对等互联和对等网( p e e r t o p e e rn e t w o r k ) 概述 目前网络规模与网络应用呈爆炸性的增长，在传统的客户机服务器模式 下，当并发请求很多的时候，服务器往往无法同时为如此多的客户端提供服务， 从而造成服务质量的下降，这就形成了服务器的瓶颈；相反，大量的客户机的 资源却无法被其他机器共享，我们来做一个计算：假设同时有1 千万台1 0 0 m h z 的计算机连接在网络上( 事实上远不只这些) ，每台可以提供1 0 0 兆的空余空间、 1 0 0 0 b p s 的空余带宽和1 0 的空余c p u 时间，则这些机器总共提供了 i o p b ( i o ”b y t e s ) 的存储空间，1 0 0 亿b p s 的带宽( 大约是1 2 5 g b p s ) 和1 0 万 m h z 的计算能力! 对等互联( p e e r - t o p e e r ) 技术的目的正在于此。 b w ( j x r a b o o k 的作者) 给出这样一个定义：p 2 p 使得任何网络设备可以 为其他网络设备提供服务( p e e r - t o - p e e rt e c h n o l o g ye n a b l ea n yn e t w o r k a w a r e 第一章绪论 d e v i c et op r o v i d es e r v i c e st oa n o t h e rn e t w o r k a w a r ed e v i c e ) 。也就是在p 2 p 网络 中，所有节点( 设备) 的角色、行为、责任和义务都是平等的( 对等的) 。 p 2 p 和客户，服务器( c l i e n t s e r v e r ，简称c ，s ) 模式相对应，不过p 2 p 的实 现是使通信双方同时拥有服务器端和客户端的功能。p 2 p 是互联网整体架构的 基础，互联网最基本的t c p 口协议并没有客户端或服务器端的概念，通信中， 所有设备都是平等的一端。但后来发展的那些架构在t c p i p 之上的软件的确 采用了客户机服务器的结构：浏览器和w e b 服务器，邮件客户端和邮件服 务器。p 2 p 技术使在网络上传输的“内容”所在的位置由中心走向边缘，也就 是说内容不再只存放在服务器上，它同样有可能存放在所有用户的p c 机中， 使得p c 机在接受内容的同时也具备了服务器的特性。p 2 p 技术的典型形式是 在应用层上基于p 2 p 网络协议的客户端软件。 使用对等互联( p 2 p ) 技术构建的网络体系称为对等网( p e e r - t o - p e e r n e t w o r k ) ，对等网中最重要的一点是搜索，基于此，可以将对等网分为三类： 1 无索引的对等网络：网络中的结点没有索引，搜索请求在结点中传播， 直到相应的搜索内容被找到。这种搜索机制为满足一个查询，以洪泛 ( f l o o d i n g ) 的形式将该查询在网络中传播。这种方法简单有效，且有 相当的健壮性，但在洪泛的同时也耗费了大量的网络带宽。典型的这 种类型的对等网有：c m u t e h a 。 2 有专用索引结点的对等网络：中心搜索，网络中有中心服务器( 专用 索引结点) ，各节点之间可以建立连接，但必须通过服务器统一管理， 集中认证，建立索引，区别于c s 模式中的服务器，这种p 2 p 模式中 的服务器仅用于辅助节点之间建立连接，一旦连接成功，服务器正常 情况下将不再干涉节点之间的传输操作。与无索引的对等网络相比， 这种结构的优点是效率( 一条信息就可以解决搜索请求) ，然而此专用 索引结点就成了瓶颈，易受攻击且难以保证索引的时效性。这种类型 的应用有：n a p s t e r 等。 3 每个结点都有索引的对等网络：分散式搜索，每个结点维护部分索引， 当传播请求时，根据索引选择路由，为了易于维护，此种索引应比较 小。目前p 2 p 网络中流行的协议均为此类如：c h o r d ，k a d e m l i a , p a s t r y 等等。这种搜索机制兼有以上两者的优点，即有相当的健壮性且响应 请求的效率比较高，但此类协议比较复杂。r o u t i n gi i l d i c e s 【1 1 】也是分布 式索引的一种形式。本文的重点也在此。 第一章绪论 1 1 2 对等网应用现状 p 2 p 技术引导网络计算模式从集中式向分散式偏移，也就是说，网络应用 的核心由中心服务器向边缘的终端设备扩散，对等网的应用主要体现在如下几 个方面： 1 对等计算：研究如何把网络中多台计算机闲置的计算能力集合起来，使 用累积的能力来完成超级计算机的任务，其本质是c p u 资源共享，应 用实例如：d i s t r i b u t e n e t ； 2 文件共享：基于p 2 p 技术的网络客户端可以脱离服务器直接从含有所需 内容的对等节点机下载相应文件内容，从而减少瓶颈形成的可能性，典 型的有n a p s t e r 和g n u t e l l a 等； 3 即时通信：终端之间可以快速、直接的进行交流，而且不仅限于在计算 机之间，还可以在多种异构设备间进行通信，比如：m i r a b i l i si c q 、腾 讯q q 和m s n m e s s e n g e r 等； 4 搜索引擎：p 2 p 技术使用户能够深度搜索文档而无须w e b 服务器，同时 可以不受信息文档格式和宿主设备的限制，达到传统目录式搜索引擎无 可比拟的深度，其应用实例包括；i n f r a s e a r c h 等，而且最新资料表明， 著名的搜索引擎g o o g l e 也计划使用p 2 p 技术进行优化。 5 应用层多播：应用层多播是p 2 p 技术的一种新的应用领域，它起源于 p 2 p 技术在文件共享方面的成功推广，由于p 2 p 技术工作于应用层，而 多播的核心思想就是复制转发，所以基于p 2 p 网络构建一个多播系统由 端机来完成复制转发的工作是非常实际的设想。 1 2 分布式h a s h 表( d i s t r i b u t e dh a s ht a b l e ) p 2 p 网络中的一个基本问题是定位，即确定哪个结点包含所需的信息。为 此，引入一种数据结构，d h t ( 分布式h a s h 表) ，以下简要介绍之。 h a s h 表存储着一系列的( k e y , v a l u e ) 有序对，并提供g e t ( k e y ) 和p u t ( k e y , v a l u e l 两个操作；一个h a s h 函数将每个k e y 映射成一个h a s h 值，同时保证h a s h 值在 所有可能的h a s h 值空间中均匀分布，这些h a s h 值决定了有序对的存储位置， 同时也使得p u t 0 和g e t o 操作很容易的执行。分布式h a s h 表( d h t ) 也是h a s h 表，但有序对不只保存在一个结点，而是分散在各个结点。这里对p 2 p 网络结 构进行了抽象，中间层是d h t ，最上一层是应用程序，底下一层是搜索协议， 它们的关系如图1 - 1 所示： 第一章绪论 图l d p 2 p 应用的层次结构 d h t 使得应用程序的接1 3 相当简单，只有两个操作g e t ( k e y ) 和 p u t ( k e y , v a l u e ) ，从而简化了p 2 p 大规模应用程序的布署。基于d h t 之上，已经 出现了多种应用，如文件共享( c f s ，o c e a n s t o r e ) ，w e b 代理( s q u i r r e l ) ，域 名系统( c h o r d d n s ) 等等。 1 3 本文工作 p 2 p 网络相当盛行，目前已经有多种流行的p 2 p 网络协议，本文所做的第 一个工作即是对这些p 2 p 协议进行了系统的分析和分类比较，指出各类系统的 特点和所适用的应用领域。 随后本文提出了t w o h o p 协议，这是本文最主要的部分，t w o h o p 协议取 自o n e h o p 协议，针对o n e h o p 的不可规模化的特点，结合了c h o r d 和k e l i p s 等协议的特点，采用层次结构的方式，对p 2 p 网络进行结构化，然后针对不同 层次的结点安排不同的任务。 接下来，为了证明t w o h o p 的有效性，本文对其进行了详尽的数学推导论 证，对其关键性能评价指标，如所需网络带宽和平均延迟界限都做了估算，为 后面的仿真实验奠定了理论基础。 在进行了理论分析之后，本文对系统有效性进行了仿真实验，在仿真实验 中，重点对查询的效率，查询的准确性和健壮性，以及带宽需求进行了仿真， 并和o n e h o p 、c h o r d 等协议进行了对比，并得出结论：t w o h o p 对网络带宽的 需求随着网络结点增加而增加的幅度远远小于o n e h o p ，这也从一定角度验证 了t w o h o p 的分析结果。 第一章绪论 论文的以后部分将如下安排：第二章介绍了现有的几种p 2 p 搜索协议：第 三章提出t w o h o p 协议的设计思想，核心概念；第四章详细分析t w o h o p 的性 能指标，对其进行数学推导过程；第五章描述仿真的场景、方法、结果及同其 它协议的比较结论；第六章是全文总结和研究展望。 第二章现有的p 2 p 搜索协议及其比较 第二章现有的p 2 p 搜索协议及其比较 p 2 p 网络中各个结点是对等的，没有等级层次之分，其网络结构是松散的， 要维护这样一个系统面临着很多问题，如在g n u t e l l a i 均中，因为网络结构的无 序性，使查询信息只能以洪泛的形式扩展，消耗了大量的网络网络带宽。为此 人为的引入了多种抽象网络结构，如环状，树状，或是多维坐标空间，将p 2 p 网络结点放入有结构的网络中，使得查询更有目的性，大大改善了搜索性能， 此举虽然增大了开销( 如维护网络特定结构) ，但仿真实验和实际应用都表明， 这种方法是有效的。本章对目前结构化的p 2 p 协议，如c h o r d l l 6 1 ，k a d e m l i a 1 7 1 ， k e l i p s l l s l ，t a p e s t r y l l 9 1 1 2 0 1 ，一一作以介绍。 2 1c h o r d c h o r d 1 6 1 是目前的一个研究热点，本文所论之协议也有部分思想出于此。 c h o r d 是一种分布式h a s h 表，但它不负责数据存储的机制。 2 1 1 连续h a s h i n g ( c o n s i s t e n th a s h i n g ) c h o r d 只提供一种操作：给定一个关键字( k e y ) ，则将它映射成p 2 p 网络 结点( n o d e ) 。通过将关键字和数据有序对( k e y , d a t a ) 存储在与k e y 相对应的 结点( n o d e ) 中，c h o r d 可以根据关键字( k e y ) 容易的确定数据( d a t a ) 所在 的位置。c h o r d 利用c o n s i s t e nh a s h i n g 【3 1 1 将关键字k e y 映射为c h o r d 结点，其 h a s h 映射函数可以为s h a - i 3 2 1 。一个结点的标识符是将其p 地址( 或域名等) 运用h a s h 函数而得到，一个关键字的标识符同样如此。在此“k e y ”同时指原 始的关键字或其在h a s h 函数下的像，“n o d e ”也是如此，可以根据上下文加以 区分，这些标识符的长度固定为m 位( 在s h a - 1 中为1 6 0 位) 。 标识符( 同时包括k e y 和n o d e ) 以模2 “运算顺序构成一个“标识符环”， 关键字k 映射到标识符等于或紧跟在k 之后的结点，该结点称为关键字k 的“后 继结点”，记作s u c c e s s o r ( k ) 。如将标识符用o 到2 m 一1 表示，则s u c c e s s o r ( k ) 为 从k 起顺时针方向的第一个结点。图2 1 展示了一个标识符环，其中m = 6 ，环 中有1 0 个结点，存储着5 个k e y 。标识符1 0 的后继是结点1 4 ，则关键字1 0 将定位于结点1 4 ，以此类推，关键字5 4 定位于结点5 6 等等。 c o n s i s t e nh a s h i n g 的设计使得结点进入和离开时花的代价较小，当结点n 第二章现有的p 2 p 搜索协议及其比较 加入时，那些被映射到n 的后继结点且值不大于n 的k e y 将被重映射到结点n ； 当结点n 离开时，只需将原来映射到n 的所有关键字k e y 重映射到n 的后继结 点，其他的无需改动。 图2 - 11 0 个结点存储5 个关键字的m 环 在川中已经证明，每个结点对应的关键字数为d ( 1 0 9 ) ，即每个结点存储 o ( 1 0 9 ) 个路由信息；当第n + 1 个结点进入或离开时，有d 伍) 个关键字改 变映射结点。由此可以看出c h o r d 能适应网络的变动。 2 1 2c h o r d 中的查询机制 p 2 p 协议的关键部分便是搜索，在c h o r d 中的任务即是，给定一个关键字 k e y ，确定其对应的结点n o d e ，最简单的可以从一个结点出发，顺时针逐个比 较，如果k e y 值在某个结点n o d e 和其后继之间，则n o d e 的后继即为所求。此 方法虽然简单，但为线性查询，最坏情况下可能会访问网中的所有结点，故不 可取。为提高搜索效率，可以用空间换时问，在每个结点处存储少许路由信息， 在c h o r d 中称之为f i n g e r 表( f i n g e rt a b l e ) ，按如下方式构建f i n g e r 表： 假设标识符长度为m 位，每个结点n 的f m g c r 表的项数为m ，其中第i 项 记录着结点s ，它是距离结点n 至少2 n d 的第一个结点，即s = s u c c e s s o r ( n + 2 “d 1 ( 其中的运算都是模2 m 运算) 。将结点s 记为n f i n g e r i 。一个f i n g e r 表包含结 点的标识符和其i p 地址( 加上端口号) 。n f i n g e r i 为i 1 的后继结点，称之为 s u c c e s s o r o 在查询某个标识符的后继结点时，便可以利用f i n g e r 表了，而且单独一个 结点的f i n g e r 表还不足以完成查询，可能要经过多点的传递，图2 2 详细地描 述了这个过程。其中图2 - 2 ( a ) 为结点8 的f i n g e r 表图示，图2 2 伪) 为结点8 利用 的f i n g e r 表，查找关键字5 4 的后继结点的路径。 第二章现有的p 2 p 搜索协议及其比较 艏0 ( a ) 图2 - 2 ( a ) 为结点8 的f i n g e r 表； ( b ) 为结点8 查找关键字弱的路径图 图2 - 2 ( a ) 由结点8 开始无法确定k e y 3 4 的后继结点3 8 ，因为3 8 结点不在 结点8 的丘i i g c r 表中，所以查找过程可能需要多个结点的中继，以下为寻找k e y 的后继结点的算法： 算法：确定k e y 的后继结点 l | a s k n o d e t o f i n d t h e 萄砬o 馘o f l y n f i n ds u c c e s s o r ( k 。y ) i f ( k e y e ( n ，n 鲫c o e s s o r ) r e t u mn s u c c e s s o r ；, e l s en = e l o s e s t p r e e e d i n g _ n o d e ( k e y ) ； r e t u n ln f i o ds u c c e s s o r ( k e y ) ； 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 r o f k e y n c l o s e s tp d m gn o d e ( k e y ) f o r i = md o w n t 0 1 i f ( f i n g e r i 】( n ，k e y ) ) r e t u r nf i n g e r i ； r e l u r n ： 在【1 6 】中已经证明，如果网络的结点数为n ，则确定一个k e y 的后继结点可 能需要的步数是d ( 1 0 9 ) ，且平均查找时间可以缩短到1 2 0 ( 1 0 9 n ) 。 第二章现有的p 2 p 搜索协议及其比较 2 1 3c h o r d 网络的动态维护 当结点加入系统和结点离开或崩溃时，c h o r d 网络需要适当调整。首先需 要保证结点的后继指针是实时更新的，这是通过c h o r d 网络的定时更新得到的， 称之为“s t a b i l i z a t i o n ”。当结点n 加入时，先和c h o r d 网络中的某个结点n 取得 联系，通过n 找到n 的后继，此时结点n 加入c h o r d 环，然后再根据1 1 的后继 结点构建n 的f i n g e r 表。经过若干次的结点加入且同时伴随着更新操作，则当 最后一个结点加入一段时间后，c h o r d 网络环会趋向稳定。 c h o r d 协议的正确性依赖于每个结点知道自己的后继结点s u c c e s s o r ，但在 某些情况下，如在图2 - 1 中，结点1 4 ，2 1 ，3 2 同时瘫痪时，结点8 没法知道结点 3 8 现在是它的后继，因为在它的f m g e r 表里没有它，如果此时查找就会出现问 题。为提高健壮性，每个c h o r d 结点包含着一个长度为r 的后继链，可以适当 选择r ( 在c h o r d 中r = l o g n ) ，这样就可以在网络特殊情况下，也能保证查询 的正确性。 2 2k a d e m l i a l a d e m l i a 【1 7 l 也是一种分布式h a s h 表，用于文件共享的应用o v e r a c t 就是基 于此的，其中的p 2 p 软件有e m u l e ，e d o n k e y ；另外，b i t s p i r i t 和新版本的b i t t o r r e n t 也支持k a d e m l i a 网络。 k a d e m l i a 的处理类似于c h o r d ，同样结点和查询关键字也是h a s h 成m ( 此 处取1 6 0 位) 位值后操作。k a d e m l i a 在处理查询信息时，还会据此更新路由表。 其中引入了结点间距离的概念，给定两个结点标识符，x 和y ，它们的距离通过 异或运算求得，即a ( x ，) ，) - z o y 。可以看到，此“距离”有很多种性质： d ( x ，工) 一0 ；如果有x i , ty ，则a ( x ，y ) 0 ；对称式，a ( x ，y ) 一d ( y ，功；且有类 似的三角不等式，d ( x ，y ) + d ( y ，z ) d o ，z ) 。和c h o r d 的顺时针环一样，k a d e m l i a 的异或运算也是单向的，即给定一个结点x 和距离，0 ，存在唯一的一个标识 符y 使得d ( x ，y ) = a 。 2 2 1 结点状态 在k a d e m l i a 的网络中，结点按其h a s h 后的标识符构成一个二叉树( 图2 3 ) ， 二叉树的叶子是网络结点。图2 3 给出了在网络中前缀为0 0 1 1 的个结点( 用 实点表示) 。对任意一个结点，可以将二又树分成若干个互不相交的子树，且其 9 第二章现有的p 2 p 搜索协议及其比较 中不含该结点。 图2 - 3k a d e m l i a 的二叉树，黑点为结点u 的位置， 灰色区域为结点n 分成的子树 k a d e m l i a 协议保证每个结点至少知道任意子树中一个结点的位置，由此引 入k - b u c k e t 的概念。对每个0 f 9 8 = * 5 9 8 = 4 5 9 8 ， 为通配符) 地，将路由信息传送到目标结点。在此处是从右向左处理结点d 的，如果反方向处理一样可行。这种路由方式和域名处理的方式极其相似。每 个结点都存储着多级的邻接表，第j 级表的第i 条数据定义为”i + s u f f i x ，j - 1 ) ， 举例来说，结点3 2 5 a e 的第4 级表的第9 条数据为距离结点3 2 5 a e 最近的且 以9 5 a e 结尾的结点。 一种比较直观的方法是将t a p e s 仃y 的路由看作一个根树，它是整个网络的 一个生成树。一般来说网络是连通的，故以任意一个结点为根，都可以生成一 个到达其余任何结点的生成树。图2 - 4 给出了在t a p e s t r y 中路由的一个例子。 在t a p e s t r y 中查找结点是递归的。 为保证一定能到达目标结点，在每级路由表中至少有一个邻居结点是活动 的，所以t a p e s t r y 会定期的检查每级路由表中主要邻居结点的活动性，如果它 没有响应，下一个最接近的结点( 如果存在) 就会变成主要的邻居结点。 t a p e s t r y 和c h o r d 一样，查找的时间大致为o ( 1 0 9 n ) 。目前网络上已经有 成熟的t a p e s t r y 应用o c e a n s t o r e l 2 8 。 第二章现有的p 2 p 搜索协议及其比较 图2 - 4p l a x t o n 路由倒子，其中发起结点为0 3 2 5 ，目标结点为4 5 孵，粗线为路 径，此处结点m 的位数为4 ，基数为1 6 ，即结点m 空间大小为6 5 5 3 6 2 4k e l i p s k e l i p s 1 8 】和以上不同，它将结点d 空间分成k 个组，称为a f f i n i t y g r o u p s ， 其中k 是常数，且约等于结点数的平方根，从0 到k - 1 进行命名。每个结点隶 属于唯一的组，这可以通过对结点d 和端口的映射得到，映射函数通常选用 s h a - 1 ，这个保证在很大程度上，每个组中结点的个数大致为n k 。 每个结点存储的路由信息有三种：同组结点的信息，称之为a f f i n i t yg r o u p v i e w ；对于不同的组，至少存储其中的一个结点，称之为c o n t a c t s ；文件组 ( f i l e t u p l e s ) ，其中记录着文件名和存储该文件的结点，其中的存储文件的结点 必须和该结点同组。图2 5 给出了结点的路由信息示例。 由此可以得出结点存储信息的量，因为k 约为结点数n 的平方根，故可计 算得出存储的信息量约为五的若干倍，即为0 l 五j 。 当某个结点需要查找文件时，它用相同的h a s h 函数将该文件映射到组里， 然后在自己的路由信息表里找到该组的一个结点，向其发送一个查询消息，如 果一切正常，将返回该文件的存储位置，即该查询时间为d ( 1 ) 且信息复杂度亦 为d ( 1 ) 。但这个查询时间要基于结点路由信息的正确性，即当一个事件发生后 多长时间，系统才能将该事件传遍整个网络。在实验性的1 0 0 0 个结点下，时间 需要1 0 多秒，这是可以接受的；但当结点数增至1 0 6 时，可能需要花1 个小时 才能将事件传遍整个网络，所以在查询过程中，有好多结点的路由信息都可能 是错误的，则k e l i p s 的效率就会大大降低。 第二章现有的p 2 p 搜索协议及其比较 n o d e l l 0 图2 - 5 结点1 1 0 存储的路由信息 2 5p 2 p 网络中的搜索过程 以上介绍了p 2 p 网络的若干协议，下面对p 2 p 网络的搜索过程进行一下描 述。以p 2 p 应用的文件共享为例，用户所做的，只是输入关键字进行搜索，然 后找到自己感兴趣的条目进行操作。如果是带有中心索引的p 2 p 网络，和中心 结点进行交互即可；如在分布式索引下，需要利用分布式反相索引1 2 1 1 1 2 2 1 2 3 1 ( d i s t r i b u t e di n v e r t e di n d e x ) 这种数据结构来实现。 分布式反相索引【2 1 j i l l 2 3 1 ( d i s t r i b u t e di n v e r t e di n d e x ) 将关键字( w o r d ) 映 射成文件( f i l e ) ，此文件包含其所在的结点位置。构建和更新反相索引是在搜 索之前预先完成的，一旦共享文件中的字被摘出，则与此相关的索引就将建立， 其中包含字( w o r d ) 和一个文件指针。反相索引可以本地创建，以服务于单个 服务器或站点，g o o g l e 便是例子。而分布式反相索引，则将索引条目分布到网 络中的各个结点，p 2 p 网络的关键字搜索便是如此。 -_iilil-llij 9 一 一 一 一 itlllil ，l“一 芝，南；h二黜。同三=hu 第二章现有的p 2 p 搜索协议及其比较 2 5 1 反相索引的建立 当一个结点加入p 2 p 网络时，如果它有共享文件，则首先对文件构建反相 索引，从文件中抽出所有的关键字，这些将是以后用户可能用以搜索的关键字。 然后对其排序并删掉重复( 这里没有考虑重复次数) ，然后对每个字构建反相索 引条目，为简单起见，只为单个字( w o r d ) 构建。 表2 - 1 分布式索引的结构 k e y i 瓜i ， h a s h ( a )h t t p ：2 0 2 1 1 3 3 9 3 a m p 3 h a s h ( b )h t t l ：l ：2 0 2 1 1 3 3 9 3 b m p 3 h a s h ( c )h t t r i ：2 0 2 1 1 3 3 9 3 c j p g 。 表2 - 1 便是一个简单的反相索引，也可以对多个字进行索引，如h a s h ( a b ) ， 在某些情况下f 2 n ，双字索引的效率较高。 2 5 2 分配反相索弓 将上述生成的反相索引，利用p 2 p 协议，在网络结点在均匀分发。以c h o r d 为例，它将上述h a s h 值设为k e y ，利用c h o r d 查询此k e y 值的后继结点，找到 后将上述对应条目传送到该结点。如果该结点没有相应的k e y 值，则接收之； 如果已有该k e y 值，则代表已经存储了相应的关键字的索引，则将对应的文件 位置添加在此索引条目后。因为协议所有的h a s h 函数会将值在h a s h 空间中均 匀分布，因此反相索引也会均匀的分布到网络中的各个结点。结点在存储反相 索引时采取何种策略，这也是个很重要的问题，相关条目在【2 2 】i 刎中。在分配索 引时传递的信息较多，代价较高，但已有研究表明1 2 4 】，p 2 p 网络中大约6 6 的 结点不提供共享文件，所以这些结点的加入不需要进行插入索引的操作。 2 5 3 查询过程 用户输入关键字进行查询，首先分成一系列的单个关键字，对每个关键字 取h a s h 值，然后根据协议找到p 2 p 网络中对应该h a s h 值的结点，从而获取反 相索引，然后对所有反相索引的u r l 取“交集”，即得到一系列的文件及其位 置，其上包含用户想要的关键字，然后用户和这些结点进行交互以获得其上的 第二章现有的p 2 p 搜索协议及其比较 文件信息。【2 2 1 中分析了此种查询的复杂度，以及若干可以提高效率的优化手段， 如缓存、预先计算、有距离的压缩等等。 2 5 4 网络结构的动态维护 除了g n u t e l l a 以外，大多数的p 2 p 网络都将网络抽象成一个结构，所有查 询都依赖于网络结构的稳定，当网络结构变化时，系统必须自动调整其上的信 息。当有结点加入时，根据具体p 2 p 协议，该结点可能需要存储某些反相索引， 即查询关键字的相应结点需要若干调整；当结点主动离开时，它需要将其存储 的反相索引发送到相应的结点；如果结点崩溃，则系统会在定期的检查中发现 此事件，于是系统开始“稳定”操作，将此事件通知到相关的结点，并修改各 自的路由信息，对丢失的反相索引，还需要重新生成，或者由上层应用负责( 比 如某些上层应用会将索引进行冗余存储，如某个结点崩溃，则冗余结点的索引 值将会利用) 。 第三章t w o h o p 的设计 第三章t w o h o p 的设计 在如今的网络中，最重要的资源是网络带宽，而存储容量已经不是一个瓶 颈，故我们尽可能的减少网络带宽的消耗。t w o h o p ，是对等网络的一种查询机 制，也是一种分布式h a s h 表。它保证在大多数情况下可以两步之内完成查询， 每个结点存储的信息容量为o ( n ) ，但其网络带宽的消耗在网络结点数为1 0 8 时 仍然可以接受。g u p t a 等人提出了o n e h o p 1 2 】协议，本文有很多思想借鉴于此。 3 1o n e h o p 协议简介 t w o h o p 的思想有一部分来自于o n e h o p 1 2 】协议，所以先简单介绍一下 o n e h o p 。目前流行的一些分布式h a s h 表，如c h o r d ，k a d e m l i a 等，它们均假设 网络结点很多，且p 2 p 网络变化频繁，所以它们力求使每个结点保存的状态尽 可能少，这样才可能使得p 2 p 网络大规模化。但在o n e h o p 中，此种假设并非是 必要的，在某些情形下，如在公司或校园里，网络状态改变的事件就很少；举 例来说在某软件公司的6 4 ，6 1 0 台机器中，有一半的机器在9 5 9 6 b 寸间内一直是开 着的【矧。在这些情形下，让每个结点维护所有结点的信息就变成可能，如此在 搜索关键字时，大部分情形下只一步便可获得所需信息。 o n e h o p 在映射关键字到结点时，可以利用c h o r d ! 垌，将结点i d 构成环状， 关键字k e y 的对应结点为其后继结点，这是在i d 环中从k e y 开始的第一个结点， 但利用其他映射机制也是可以的。 在p 2 p 网络中很重要的一点是对网络的维护，即保证各个结点路由信息的 正确性。0 n e h o p 中，是将网络抽象成一个树状结构，即人为的加入了结点的等 级关系，从而使网络维