（计算机软件与理论专业论文）结构化对等计算及其上数据挖掘系统.pdf

摘要 对等计算( p e e r - t o p e e rc o m p u t i n g ，简称p 2 p ) ，自2 0 0 0 年中期以来迅速成 为计算机研究界和工业界关注的热点。在对等计算系统( 简称p 2 p 系统) 中，每个 节点都拥有对等的功能与责任，即每个节点既可以充当服务器向其他节点提供数 据或服务，又可以作为客户机享用其他节点提供的数据或服务；节点之间的交互 可以是直接对等的；任何节点可以随时自由地加入或离开该系统，形成一个真正 动态的网络环境。这类系统具有许多潜在优势，如系统的可扩展性、鲁棒性、信 息可用性、系统资源利用率高以及能够满足某些特殊应用需求，因而p 2 p 被认为 是未来重构基于i n t e m e t 应用的关键技术之一。 本文主要探讨结构化对等计算应用层网络拓扑结构及其上的数据挖掘方法， 其目的是探索如何高效地利用结构化对等计算系统提供的强大的计算资源以及 高效的路由算法完成对等计算环境下的数据挖掘任务。对该问题的解决牵涉到分 布式环境下索引的构造、利用与维护；数据和统计信息在对等计算系统中的路由 ( r o u t i n g ) ；数据挖掘中的任务分配以及结果收集；系统中节点动态加入退出时 的容错性能等诸多挑战。为了应对这些挑战，我们深入研究了这类系统的关键技 术所面临的挑战，并取得了以下成果r 1 基于c h o r d c h o r d 和c a n c a n 提出了自己的结构化对等计算系统c 2 ， 整合了两个系统的优点；理论证明了c 2 的网络构架以及路由方法的有效 性和高效性，实验验证了c 2 具有良好的可扩展特性、负载均衡特性和容 错特性。 2 提出了结构化对等计算环境下的频繁模式挖掘系统p e e r f p m ；实验验证 了p e e r f p m 系统具有很小的网络通信代价和很短的相应时间；同时验证 了p e e r f p m 系统具有良好的可扩展特性、负载平衡特性、容错特性。 3 基于二项分布的大数定理，提出了降低本地支持度阈值的方法，避免了 数据偏斜造成的问题；并通过理论推导证明了该方法的有效性。该方法 不仅适用于对等计算，而且适用于分布式计算和并行计算环境。 总之，本文详细论述了实现基于结构化对等计算的频繁模式挖掘方法。本文 的工作是建立在对相关理论和已有技术的详尽分析以及大量的实验测试结果之 上的。实验结果表明，我们提出的结构化对等计算环境下的频繁模式挖掘系统能 高效地利用系统资源并有效地满足用户需求。 关键词：对等计算，结构化对等计算，数据挖掘，频繁模式挖掘 儿 a b s t r a c t p e e r - t o - p e e rc o m p u t i n g 口b b r p 2 p ) h a sb e c o m eah o ts p o ti nt h ec o m p u t e r r e s e a r c ha n di n d u s t r i a lf i e l d s i nap 2 p - b a s e ds y s t e m ，e a c hp e e r ( n o d e ) h a se q u a l f u n c t i o n a l i t i e sa n dr e s p o n s i b i l i t i e s ，i e ，ap e e rc a nb o t ha c ta sas e r v e ro fo t h e r s p r o v i d i n gt h e mw i t hd a t a s e r v i c e s ，a n d s e r v ea sac l i e n to fo t h e r sc o n s u m i n gt h e i r d a t a s e r v i c e s f u r t h e r m o r e ，t h ei n t e r a c t i o na m o n gp e e r sc a nb ed i r e c ta n ds y m m e t r i c i na d d i t i o n ，p e e r sc a nj o i ni no rl e a v ef r o mt h es y s t e ma ta n yt i m et of o r md y n a m i c n e t w o r ke n v i r o n m e n t t h i ss o r to fs y s t e m se n j o ym a n yp o t e n t i a lm e r i t s ，i n c l u d i n g s c a l a b i l i t y , r e l i a b i l i t y , h i g hi n f o r m a t i o na v a i l a b i l i t y , a n de f f i c i e n t l yu t i l i z i n gs y s t e m s r e s o u r c e s s ot h a tp 2 pi sr e g a r d e da sap r o m i s i n gt e c h n o l o g yt or e - a r c h i t e c t u r et h e f u t u r ei n t e m e t - b a s e da p p l i c a t i o n s i nt h i sp a p e r , w ef o c u so ns t r u c t u r e dp 2 po v e r l a yn e t w o r ka n df r e q u e n tp a t t e m m i n i n gi np 2 pe n v i r o n m e n ti no r d e r t od e s i g nas y s t e mw h i c hc a ni n t e g r a t er e s o u r c e i ni n t e m e tt oa c h i e v ea ne x p e n s i v ed a t am i n i n gt a s k t os o l v et h i sp r o b l e m ，w ea r r i v e a tq u i t eal o to fc h a l l e n g e ss u c ha sh o wt oc o n s t r u c t u t i l i z e m a i n t a i na ni n d e xi np 2 p e n v i m n m e n t , h o wt or o u t ed a t aa n ds t a t i s t i ci n f o r m a t i o ni np 2 ps y s t e m ，h o wt o p a r t i t i o nm i n i n gt a s k sa n dg a t h e rm i n i gr e s u l t si np 2 pe n v i r o n m e n t , h o wt oo v e r c o m e t h ed y n a m i cc h a r a c t e r i s t i ci np 2 pe n v i r o n m e n t , a n de t c t oa d d r e s st h e s ec h a l l e n g e s ， w ec o n d u c ta l le x t e n s i v es t u d yi nt h i sa r e aa n da c h i e v ef o l l o w i n gc o n t r i b u t i o n s ： 1 w ed e s i g nan e ws t r u c t u r e dp 2 po v e r l a yn e t w o r k ，c a l l e dc 2 ，w h i c hi n t e g r a t e s t h em e r i t so f c h o r d c h o r d 】a n dc a n c a n t h ee f f e c t i v e n e s sa n de f f i c i e n c y o fc 2i sp r o v e d ，a n dt h es c a l a b i l i t y , w o r k l o a db a l a n c e ，a n df a u l tt o l e r a n c e c h a r a c t e r i s t i c so f c 2i sv e r i f i e db ye x t e n s i v ee x p e r i m e n t s 2 an e ws y s t e m ，c a l l e dp e e r f p m ，w h i c hc a nc a r r yo u tf r e q u e n tm i n i n gi np 2 p e n v i r o n m e n t , i sp r o p o s e d e x p e r i m e n t ss h o wt h a tp e e r f p ma c h i e v es m a l l c o m m u n i c a t i o no v e r h e a d ，s h o r tr e s p o n s et i m e ，g o o ds c a l a b i l i t y , w o r k l o a d b a l a n c e ，a n df a u l tt o l e r a n c e 3 an e wm e t h o dw h i c hc a nl o w e rm i n i m u m s u p p o r tb a s e do nl a r g en u m b e rl a w i i i o fb i n o m i a ld i s t r i b u t i o ni no r d e rt oa v o i dp r o b l e m sc a u s e db ys k e w n e s so f d a t a a n dt h ee f f e c t i v e n e s so ft h i sm e t h o di sp r o v e d t h i sa p p r o a c hi sn o t o n l ya p p l i c a b l et op e e r - t o p e e re n v i r o n m e n tb u ta l s of e a s i b l et od i s t r i b u t e d e n v i r o n m e n ta n dp a r a l l e le n v i r o n m e n t i naw o r d ，t h i st h e s i sh a sd e t a i l e dt h ed e s i g n ，k e yt e c h n i q u e sa n de x p e r i m e n t a l r e s u l t so fas t r u c t u r e dp 2 ps y s t e ma n daf r e q u e n tp a t t e r nm i n i n gs y s t e mb a s e do ni t a l lt h e s ec o n t r i b u t i o n sa r ea c h i e v e dt h r o u g hac o m p r e h e n s i v es t u d yo nt h er e l a t e d t h e o r i e s ，e x i s t i n gt e c h n o l o g i e sa n de x p e r i m e n t a lr e s u l t s m o r e o v e r ，t h ee x p e r i m e n t a l r e s u l t sh a v ev e r i f i e do u rs y s t e mc a ne f f i c i e n t l yu t i l i z et h er e s o u r c ei np 2 ps y s t e ma n d s oa st om e e tt h er e q u i r e m e n t so f u s e r s k e y w o r d s ：p e e r - t o p e e rc o m p u t i n g ( p 2 p ) ，s t r u c t u r e dp 2 p , d a t am i n i n g ，f r e q u e n t p a t t e r nm i n i n g 第一章绪论 本文主要探讨结构化对等计算应用层网络拓扑结构及其上的数据挖掘方法， 其目的是探索如何高效地利用结构化对等计算系统提供的强大的计算资源以及 高效的路由算法完成对等计算环境下的数据挖掘任务。对该问题的解决牵涉到分 布环境下索引的构造、利用与维护；数据和统计信息在对等计算系统中的路由 ( r o u t i n g ) ：数据挖掘中的任务分配以及结果收集；系统中节点动态加入退出时 的容错性能等很多问题。 本章我们论述选题背景、研究目标和主要贡献，并指出本研究的意义。本章 第一节将首先从因特网的现状与应用的角度来分析对等计算模型，并介绍一些典 型的对等计算应用；第二节深入分析对等计算与传统的客户机，服务器模型的差 异，列举对等计算技术的主要特点及其潜在的优势：第三节主要阐述本文的研究 目标以及为达到该目标所面临的挑战。本章最后一节将介绍全文的组织结构。 作为简写，在本文的剩余部分，在不会造成歧义的情况下，对等计算将被简 写为p 2 p ，因特网将被简写为i n t e m e t 。 1 1 对等计算的研究背景 对等计算( p 2 p ) 是p e e r t o p e e r 的缩写，它起源于最初的联网通信方式，如 在建筑物内p c 通过局域网互联，不同建筑物间通过m o d e m 远程拨号互联。其 中建立在t c p i p 协议之上的通信模式构成了今日互联网的基础，所以从基础技 术角度看，p 2 p 不是新技术，而是新的应用技术模式。 现在互联网是以b ( b r o w s e r ) s ( s e r v e r ) 或s ( s e r v e r ) ，c ( c l i e n t ) 结构 的应用模式为主的，这样的应用必须在网络内设置一个服务器，信息通过服务器 才可以传递。信息或是先集中上传到服务器保存，然后再分别下载( 如网站) ，或是 信息按服务器上专有规则( 软件) 处理后才可在网络上传递流动( 如邮件) 。 对等计算( p 2 p ) 是一种新兴的网络计算模型。它在以下两个方面不同于传 统的客户机服务器( c l i e n t s e r v e r ，或c s ) 模型以及三层模型： 每个节点( p e e r ) 既可以是客户机也可以是服务器，或者同时扮演客户 机和服务器的角色； 一个节点可以根据需要在应用层与任意一个或者多个节点建立连接或 者进行通讯。 如今拥有p 2 p 软件的p c ( 或操作者) 就可以选择同样拥有此类软件的另一 p c ( 或操作者) 形成互联( 直接连接，不通过服务器) ，双方共享资源，协同 完成某种行动。而拥有同一p 2 p 软件的设备和用户，还可以形成一个互联网上的 p 2 p 专用网。 目前人们认为p 2 p 在加强网络上的即时通信交流、文件共享交换、分布协同 计算等方面有很大的前途。 文件共享 基于对等计算的文件共享就是本地文件不经过第三方文件服务器直接 共享、传递给文件请求方。基于对等计算的文件共享系统共享的主要是 多媒体文件，例如， 音频文件、视频文件等。n a p s t e r n a p s t e r 】是最早 出现的文件共享系统之一。n a p s t e r 曾经仓0 造了在十六个月由用户创建 了两千三百万个“n a p s t e r 地址”的纪录 s h i r k y , 2 0 0 1 ，而从1 9 8 6 年口诞 生开始至u 2 0 0 1 年十六年的域名总数也不过两千三百万个。虽然由于法 律原因，n a p s t e r 网站被暂时关闭 n a p s t e r ，2 0 0 3 ，但是继之而起的 g n u t e l l a 【g n u t e l l a ，2 0 0 3 】、f r e e n e t f r e e n e t ，2 0 0 3 、k a z a a k a z a a ，2 0 0 3 、 m o r p h e u s m o r p h e u s ，2 0 0 3 等文件共享软件仍然在被广泛使用。而且 k a z a a 已经成为下载量最高的共享软件( s h a r e w a r e ) k a z a a ，2 0 0 3 。 即时消息传递 基于对等计算的即时消息传递就是不同计算机的用户通过网络( 一般是 i n t e m e t ) ，相互递送消息进行对话。这不同于同一台主机不同终端用户 之间的消息传递，因为消息的递送是在两台不同的计算机之间进行的， 这两台计算机甚至可能拥有不同的体系结构、运行的是不同的操作系 统。著名的即时消息传递软件i c q 【i c q ，2 0 0 3 】曾经是下载量最大的共享 软件。其它著名的即时消息传递软件包括a o l i n s t a n t m e s s a g e ( a i m ) f a i m ，2 0 0 3 、y a h o o ! m e s s e n g e r ( y a h o o ! p a g e r ) 【y a h o o ! 一p a g e g2 0 0 3 】、 m s nm e s s e n g e r m s n - m e s s e n g e r ，2 0 0 3 等。除了简单的文字消息传递 以外，这些即时消息传递软件一般还提供多方文字会议、文件共享、即 时音频对话甚至即时图像传输功能。 协同计算 和应用领域专注于日常生活和娱乐不同，工业界、政府和学术界更重 视p 2 p 在工业、商业、科研等领域的应用。在工业界，著名的 s e t i h o m e s e t i h o m e ，2 0 0 3 】项目致力于利用分散在i n t e m e t 上大 量闲置的c p u 资源进行探索外太空的科学计算。而重要的软件生产商； 例如，m i c r o s o f t 、s u nm i c r s y s t e m 等公司，则推出了基于p 2 p 结构的分 布式平台。比较著名的有m i c r o s o f t 的n e t 构架 m i c r o s o f t n e t ，2 0 0 3 、 s u n m i c r o s y s t e m 的j x t a 平台 j x t a ，2 0 0 3 】等。这些构架和平台的目 的在于提供一种通用的机制，使得网络( 包括i n t e m e t ) 中的每一台计算 机( 或者带有计算机的各种设备) 上的应用能够相互提供和享受服务， 而不需要知道具体的服务提供者的来源、位置，其本质是对等计算。在 推出软件平台的同时，这些软件生产商还致力于制定协议和标准以规范 服务的提供、使用与查找。这些协议、标准和软件平台一起被置于w e b 服务( w e bs e r v i c e ) 的体系结构下。 在应用的推动下，学术界开展了大量关于对等计算模型、系统、核心技术的 研究。如前所述，国际上已经启动了很多研究项目，并有很多原型系统问世。这 些研究工作的目的都是利用对等计算模型，在分布的环境下，提供各种更好的服 务。近年来，在对等计算领域的研究工作的目的都是为了提供更好的信息服务， 而且它们也都取得了丰硕的研究成果，只是指导思想不同，以致采用了不同的技 术路线。前者更偏向于研究提供高质量的应用层的服务的问题，而后者注重底层 平台的支持，以及“下一代i n t e m e t ”的构建。当然，分类不是绝对的，一些研究 工作兼有两者的特点。比如，很多研究工作都试图在结构化的p 2 p 平台上提供各 种服务。本文提出了一种新的结构化对等计算系统，并且对在结构化对等计算系 统上建立协同计算的数据挖掘系统进行了深入的研究。 1 。2 对等计算的特点及其潜在优势 在本节中，我们将深入地分析对等计算与传统的客户机朋务器模型的差异， 列举对等计算技术的主要特点及其潜在的优势。 一3 1 2 1 对等计算技术与现有互联网技术的比较 目前互联网主要技术模式是c s 方式，此方式要在互联网上设置拥有强大处 理能力和大带宽的高性能计算机，配台高档的服务器软件，再将大量的数据集中 存放在上面，并且要安装多样化的服务软件，在集中处理数据的同时可以对互联 网上其他p c 进行服务，提供或接收数据，提供处理能力及其他应用。对于一台 与服务器联机并接受服务的p c 机来说，这台p c 机就是客户机，其性能可以相 对弱小。 而p 2 p 技术的特征之一就是弱化了服务器的作用，甚至取消服务器，任意两 台p c 互为服务器，同时又是客户机，即对等关系，如何表现取决于用户的要求， 网络应用由使用者自由驱动。信息在p 2 p 网络设备间直接流动，高速及时，降低 中转服务成本。构成网络设备互动的基础和应用。在使网络信息分散化的同时， 相同特性的p 2 p 设备可以构成存在于互联踺中的子网，使信息按新方式又一次集 中。表1 1 是p 2 p 与c s 方式的一些比较。 表1 , 1p 2 p 技术与c s 技术比较 p 2 p c s 数据发布 好差 数据接收 中好 数据瓦动忭 好差 数据即时性 好差 数据安全性 差好 数据更新 盘了差 数据质_ 最 中好 数据覆盖率和数量差好 数据成本控制 好差 i 数据管理方便性 差好 c s 方式造成互联网络上的集中化，无论信息资源还是成本资源均向同方 向集中，这样的模式符合一对多、强对弱的社会关系形式，如政府对个人、对企 业，大企业对小企业，学校对学生，企业对职工等等关系。所以c s 方式是符合 市场需求的。p 2 p 方式将导致信息数量、成本资源都向互联网各点均匀分布，也 就是所谓“边缘化“的趋势。此模式符合对一”的特点，以及彼此相当的社会关 系形式，如个人对个人，规模相当的企业之间，等等，这也是符合市场需求的( 如 i c q 、m s n 等) 。所以这两种方式会共存，有关p 2 p 即将替代c s 模式的说法是 不成立的。p 2 p 有其独特的市场空间，是现有互联网应用的补充，这一点应该是 毫无疑问的。 1 2 2 对等计算技术的主要特点 在对等计算( p 2 p ) 系统中，每个节点( p e e r ，如用i n t e m e t 连接起来的p c ) 都拥有对等的功能与责任，即每个节点既可以充当服务器向其他的节点提供数据 或服务，又可以作为客户机享用其他节点提供的数据或服务；节点间的交互可以 是直接与对等的；每个节点可以随时自由地加入和离开系统，形成一个真正动态 的网络环境。基于对等计算的系统主要具有节点间对等( s y m m e t r y ) 、节点自治 ( a u t o n o m y ) 、网络动态( d y n a m i c s ) 、以及大规模分布( 1 a r g e s c a l ed i s t r i b u t i o n ) 和无集中控制( d e c e n t r a l i z a t i o n ) 的特点。下面分别就每一个特点说明其和传统 分布式系统的异同： 对等特性 传统分布式计算中，节点的客户机或服务器角色区分明确。而在p 2 p 系 统中，节点间是对等的。系统中的任意一个节点都可以充当其他节点的 服务器，向其他节点提供数据或服务；也可以作为其他节点的客户机， 享用其他节点提供的数据或服务，节点功能和职责对等。同时，节点还 可以在应用层和任意一个节点进行通讯，以请求或者应答服务。所以， 对等计算系统往往构造了一个节点间应用层联系不同于底层物理网络的 “对等网络( p 2 pn e t w o r k ) ”。于是在一些文献中，对等网络又被称呼为 “覆盖网络( o v e r l a y n e t w o r k ) ”。 自治特性 传统分布式计算中，节点是受控的，而在对等计算应用中，节点是自治 的。系统中的任意一个节点主要关注本地的事务；可以独立自主地决定 本地文件的共享范围( 哪些文件可共享) 以及共享权限等；并且当节点 离开p 2 p 系统时仍然是一个功能完备的计算机系统。这意味着节点可以 在任何时候动态加入或者退出系统、节点可以以其自身的语法( 模式) 和语义( 值与含义的对应) 发布数据、节点可能具有差异相当大的处理 能力。然而，节点的自治并不意昧者节点间不能协作或者相互提供服务。 相反，一些系统要求节点必须提供服务才能享受服务，以遵守所谓的“公 平( f a i r n e s s ) ”原则。此外，一些系统通过把具有相同或者相似服务请求 的节点进行聚类并让它们相互服务的手段来实现节点间的协作。 动态特性 在采用c s 体系结构的系统中服务器( s e r v e r ) 通常以3 6 5 2 4 的方式 工作，客户机( c l i e n t ) 的扩展和退出以及它们的行为模式都有规律可循。 由于节点的自治以及网络和系统稳定性的影响，整个p 2 p 网络是动态 的。在匝p 系统中考虑的动态性不同于传统的分布式计算中考虑的动态 性。在一般分布式系统中，对动态性的考虑主要包括系统的纠错与恢复 等问题，而在p 2 p 环境下，对于动态性的考虑主要围绕如何利用当前可 用的资源提供最好的服务而展开。此外，p 2 p 系统的动态性还体现在数 据的动态性上。和传统的分布式数据库中考虑的数据动态性相似，数据 可以被插入、删除和更新。本文主要考虑数据不断增加、不经常更新的 情况，因为它适用于一大类p 2 p 环境下的数据管理问题。 大规模分布特性 传统的分布式系统中的节点个数往往只有几十到，l 百个节点，然而p 2 p 系统的规模一般远远大于传统的分布式系统，可以达到几百万甚至几千 万个节点。在有限的网络带宽和计算能力的条件下协调大量节点是p 2 p 系统和传统分布式系统的主要区别之一。 无集中控制特性( 自组织特性) 传统的分布式计算系统中一般存在集中式的控制，而在p 2 p 系统中，这 样的控制不存在。p 2 p 系统是彻底的分布式系统，在系统层面上可以没 有任何集中式机制。p 2 p 系统中的节点可以根据某种规则( 如“利润最 大化”原贝j j p r 9 5 ，以最少的代价( 消耗的带宽和计算资源最少) ，获得 最大的利润( 查询时间最短、最多的合格答案) ) 来决定自己的邻居节点。 此外，缺乏集中控制还造成系统整体情况信息的缺失每个节点都通 过有限的局部信息做出决定。这样造成的后果可能是系统不能以全局最 优的策略完成某一个特定任务。 1 2 。3 对等计算技术的潜在优势 随着研究的广泛开展，对p 2 p 系统的认识也越来越深入，已经取得的研究成 果表明，这类系统至少具备以下5 个潜在优势： 系统的可扩展性好 对于p 2 p 系统而言，每个新节点的加入都会给系统带来新的信息资源、 带宽和计算资源，因而，系统的资源会随着节点的加入而丰富，系统的 能力会随着节点的增加而增强。而对于c s 模式的系统来说，随着系统 节点的增加，服务器的能力成为系统的瓶颈，使得相当一部分节点无法 获得良好的服务。 系统的鲁棒性好 由于在系统层面可以没有任何集中式机制，p 2 p 系统不会出现c s 模式 存在的单点故障( s i n g l ep o i n tf a i l u r e ) 。此外，在一般情况下，系统中的 每个节点同时有多个邻居节点( 直接相互联接的两个节点定义为邻居) ， 某个或某些节点的退出或故障不会严重影响系统中的其他节点，所以， p 2 p 系统具有鲁棒性。 信息可用性好 在p 2 p 系统中，尤其是在以信息共享和信息备份为主要应用目标的系统 中，一个节点在维护本地用户信息的同时，还可以备份其他节点的信息。 因而，当某个或某些节点出现故障或离线时，仍然可以从其他节点获取 已备份的信息。 系统的资源利用效率高 在p 2 p 系统中，当节点的本地用户没有提交事务或处理本地用户事务的 工作负荷不高时，它可以响应远程节点发来的请求，向其他节点提供服 务。如s e t i h o m e s e t i 就是利用对等节点空闲时问的计算资源，以屏 幕保护程序的形式来完成高成本的计算工作。因而，系统在几乎不增加 软硬件成本、管理和维护费用的情况下，就能完成额外( 甚至巨额) 的 处理任务，使得系统的性价比高。 能满足各种应用需求甚至特殊应用需求 由于p 2 p 是一种具有上述四种特性的通用计算模式，因而能够有效地支 持各种应用的开发。并且，正如前面所述，p 2 p 在系统层面可以完全消 除集中式控制机制，系统可以在几乎没有集中管理的情况下运行，因而 这类系统可以满足许多特殊的应用需求，如匿名电子自口件服务等。 正因为对等计算所具备的上述特点与潜在优势，尤其是对“以数据为中心” 的新型分布式应用的支持，因而被认为是传统i n t e m e t 技术与传统数据管理技术 的结合点，也是重构未来基于i n t e m e t 应用的关键技术 g h l 0 1 1 。 1 3 对等计算研究现状 对等计算研究热的兴起首先是从应用开始的，并迅速受到工业界和研究界的 关注。目前越来越多的政府和国际组织也成为对等计算研究的主体。 在应用方面，自2 0 0 1 年以来，已经研发出大量的基于对等计算的软件系统， 主要有文件共享和即时消息传递两类。其中较为著名的包括早期的n a p s t e r i n a p s t e r 、g n u t e l l a g n u t e l l a 和i c q i c q ，以及当前流行的k a z a a k a z a a 、 m o r p h e u s 【m o r p h e u s 、m s nm e s s e n g e r m s n 和o i c q o i c q 等。它们的用户群 从早期高校学生扩展到当今的大多数i n t e m e t 用户，并且用户总数量始终保持着 上升的趋势。据统计，到2 0 0 3 年9 月，当前最流行的基于p 2 p 的多媒体文件共 享平台k a z a a 的下载次数已经达到2 3 0 ，3 0 9 ，6 1 6 次【k a z a a 】。基于p 2 p 的即时 消息传递( i n s t a n tm e s s a g e ) 就是不同的用户通过网络( 一般是i n t e r n e t ) 相互递 送消息进行对话。这与同一台主机不同终端用户之间的消息传递是不同的，因为 消息的传递是在两台不同的计算机之间进行的，这两台计算机甚至可能拥有不同 的体系结构、运行不同的操作系统。除了简单的文字消息传递以外，这些即时消 息传递软件一般还提供多方文字会议、文件共享、即时音频对话甚至即时图象传 输功能。在著名的即时消息传递软件中，i c q i c q 曾经是下载量最大的共享软件。 除此之外，还包括a o l i n s t a n t m e s s a g e ( a i m ) 【a i m 、y a h o o ! m e s s e n g e r y a h o o 、 m s nm e s s e n g e r m s n 等。 在学术界，来自计算机网络、数据库、计算理论等多个领域的学者纷纷投入 到p 2 p 系统的拓扑、协议、路由算法、底层支持平台和上层应用系统等各个方面 的研究中。自2 0 0 1 年起，a c ms i g c o m m s i g c o m m 】、v l d b 【v l d b 】、i c d e i c d e 及i e e e1 n f o c o m 【i n f c o m 等计算机领域的重要学术会议上先后开始 发表了关于对等计算的学术论文；从2 0 0 2 年开始，出现了大量的以对等计算为 主题的学术会议，例如i n t e r n a t i o n a lw o r k s h o po np e e r - t o p e e rs y s t e m ( i p t p s ) ( c a m b r i d g e ，m a ，u s a ，2 0 0 2 ；b e r k e l e y , c a ，u s a ，2 0 0 3 ；s a nd i e g o ，c a ，u s a ， 2 0 0 4 ) 、i e e ei n t e r n a t i o n a lc o n f e r e n c eo np e e r - t o p e e rc o m p u t i n g ( s w e d e n ，2 0 0 1 ， 2 0 0 2 ，2 0 0 3 ，2 0 0 4 ) 、w e be n g i n e e r i n ga n dp e e r - t o - p e e rc o m p u t i n g n e t w o r k i n g 2 0 0 2w o r k s h o p s ( p i s a ，i t a l y , 2 0 0 2 ) 、i n t e r n a t i o n a lw o r k s h o po i ld a t a b a s e s ， i n f o r m a t i o ns y s t e m s ，a n dp 2 pc o m p u t i n g0 9 b i s p 2 p ) ( b e d i n ，g e r m a n y , 2 0 0 3 ) 、 i n t e r n a t i o n a lw o r k s h o po l la g e n t sa n dp e e v t o - p e e rc o m p u t i n g ( a p 2 p c ) ( b o l o g n a ， i m l g2 0 0 2 ；m e l b o u r n e ，a u s t r a l i a ，2 0 0 3 ；n e wy o r kc i t y , u s a ，2 0 0 4 ) 等。此外，在 c i d r c i d r 等重要国际学术会议上开始出现了专门的关于对等计算的分会 ( s e s s i o n ) 。根据n e c 研究院( n e cr e s e a r c hi n s t i t u t e ) 的科学文献电子图书馆 ( s c i e n t i f i cl i t e r a t u r ed i # m ll i b r a r y , c i t e s e e r ) 网站 c i t e s e e r 上的统计，从2 0 0 0 年到2 0 0 3 年9 月，大约有7 0 0 0 多篇关于对等计算的学术论文被该网站索引，这 些文献被该网站索引的其他文献引用约为4 0 0 0 次。此外，从2 0 0 0 年到2 0 0 2 年， c i t e s e e r 网站索引文章中每年被引用率最高的论文中，有相当多的文献是关于对 等计算的。 同时，对等计算本身作为一种新兴技术已经应用于科学研究。1 9 9 9 年5 月， 由美国加州大学伯克利分校启动了名为s e t i h o m e s e t l 的项目。s e t i h o m e 是s e a r c h f o r e x t r a t e r r e s t r i a l i n t e l l i g e n c e a t h o m e 的缩写，意为：在家里寻找外星 文明。其核心思想是利用连接到i n t e r n e t 上p c 的闲置计算能力分析世界上最大 的射电望远镜获得的数据，帮助科学家探索外星生命。该项目启动以来，已有 4 5 0 万志愿者参加了这个项b ，总处理数据量已经达到了1 5 t ，平均每位参与者 让自己的电脑为s e t i h o m e 工作了1 7 个半小时，这相当于一台p c 机工作 4 8 2 0 2 3 年，相当于世界上最快的超级计算机工作4 8 年。另外，耶鲁大学医学院 倡导d 2 0 l d 2 0 l 项目正利用边缘计算资源进行抗“非典”药物筛选。 在工业界，重要的软硬件生产商，如m i c r o s o f t 、s u nm i c r o s y s g e m 以及i n t e l 等公司都致力于推出基于对等计算的分布式平台。例如，m i c r o s o f t 的 l j a r s i t e f a r s i t e $ h n e tf r a m e w o r ks d k ( 构架) 【n e t ，i n t e l 的“m a r q u a m ”以及 s u n m i c r o s y s t e m 的j x t a 平台f j x t a 等。这些构架和平台的目的在于提供一一种 通用的机制，使得网络( 包括i n t e m e t ) 中的每一台计算机( 或者有计算能力的 设备) 上的应用能够相互共享服务，而不需要知道具体服务提供者的来源和位置， 其本质就是对等计算。在推出软件平台的同时，这些软件生产商还致力于制定协 议和标准以规范服务的提供、使用与查找。这些协议、标准和软件平台一起被置 于w e b 服务( w e bs e r v i c e ) 的体系结构下。 一些政府和大型的研究机构推行的网格( g r i d ) 计划的目的是提供存储与计 算等公共信息服务。在网格计划中，由于各个网格节点往往是分布的，所以需要 整合这些节点，以向用户透明地提供统一的信息服务。在整合过程中，牵涉到节 点之间的信息交换、服务共享、负载平衡等多方面的问题。这些问题本身都是对 等计算的问题。从这个角度看，网格的目标是利用p 2 p 技术提供操作系统一级的 服务；而对等计算研究一方面考虑的是通用的对等计算模型，另一方面则更多地 考虑应用一级的服务 u l l m a n 0 3 1 。此外，一些网格项目旨在利用已经存在的边缘 ( e d g e e n d ) 计算机资源，即大量的个人电脑( p c ) ，来提供统一的存储或者计 算服务。因此，前面提到的s e t i h o m e 和d 2 0 l 项目也常常被归入网格项目。 由于这些项目往往是针对单一应用的，实质也是p 2 p 应用。同时，越来越多政府 也投入到对等计算研究当中：一方面，许多研究基金支持对等计算的研究，如我 国的国家自然科学基金和国家8 6 3 项目，以及美国国家自然科学基金都支持对等 计算和网格觋究项目等；另一方面，还成立了专门的研究机构( 如新加坡信息发 展局( i d a ) 支持的新加坡国立大学( n a t i o n a lu n i v e r s i t y o f s i n g a p o r e ) 与复旦大 学对等计算研究中心( c o m p e t e n c y o f p e e r - t o - p e e r c o m p u t i n g c e n t r e ) ) ，并设立了 专门项目( 如上海市科委重大研究项目：基于p 2 p 技术的虚拟协作虚拟研究平台 i n f o o r i d ) 等，以加速对等计算的研究与开发。 一些民闻组织也在参与对等计算系统的开发与应用拓展。例如，自n a p s t e r 以后，出现了一大批具有类似功能的开放源码软件( o p e n s o u r c es o f t w a r e ) 或自 由软件( f r e e w a r e ) ，例如g n u t e l l a g n u t e l l a 、f r e e n e t f r e e n e t 、o p e n n a p o p e n n a p 等。除了这些针对特定应用的软件以外，还有一些开放源码软件或者自由软件致 力于提供通用的基于对等计算模型的服务。例如，j a b b e r j a b b e r 主要被用来支持 开发提供基于可扩展标注语言( e x t e n s i b l em a r k u pl a n g u a g e ，或x m l b p s + 0 0 ) 的消息传递。跟i c q 等即时消息传递软件不同，j a b b e r 系统希望通过传递带标注 的x m l 消息，来达到应用程序与应用程序之间的“对话”功能。所以j a b b e r 其 实是一个通用的基于p 2 p 的消息传递平台，它既可以被一些程序用来执行即时消 息传递任务，也可以被用来开发其他应用程序。 总之，对等计算的研究热已经到来。本文正是在这样的背景下进行选题并开 展相关的研究工作的。 1 4 研究的目标与面临的挑战 由于对等计算模型具有和传统分布式计算不同的特点，对等计算环境对其上 的应用层网络以及数据挖掘技术提出了新的挑战和要求。概括而言，包括以下五 个方面： 分布性( d i s t r i b u t i o n ) ： 对等计算系统的核心是分布式计算。虽然对于用户，计算可能是位置透 明的，但是在计算的过程中，系统必须知道在哪个节点上计算什么数据， 同时在计算结果收集阶段系统必须知道在哪个节点上统计什么计算结 果。此时，系统必须要提供一种在用户没有提供数据位置、系统