（通信与信息系统专业论文）基于xml的发布订阅系统的研究和设计(1).pdf

摘要 摘要 i n t e m e t 技术的飞速发展和广泛普及，使人们获取信息的方式发生了革命性的 变革。传统的方式是信息查询，即访问w e b 网站或搜索感兴趣的w e b 页，人们需 要花费很多时间才能找到自己感兴趣的信息，反复查询的方式也使网络上增加了 许多不必要的流量。发布订阅( p u b l i s h s u b s c r i b e ) 的通信方式能够解决这个问题。 发布订阅系统包含发布者、事件中介、订阅者三个部分，发布者向事件中介发布 信息，订阅者向事件中介订阅感兴趣的信息，事件中介将订阅者感兴趣的信息准 确而及时地转发给订阅者。发布者和订阅者之间不直接通信，这样的系统具有很 好的松散耦合特性，与w e b 访问、远程过程调用( i 冲c ) 、消息队列等传统的通信 方式相比，更适合大规模分布式系统的实现，同时，信息是按需传递的，降低了 网络流量。因此近年来发布订阅系统得到了学术界和工业界的广泛关注。 对于发布订阅系统来说，用来表示信息的数据模型直接影响到系统的表达能 力和扩展性。可扩展标记语言( x m l ) 可以结构化地表示数据，扩展性强且具有 平台无关性，因此非常适合作为发布订阅系统的数据模型。x m l 的相关标准x p a t h 更是可以作为发布订阅系统中理想的订阅模型。x m l 目前已经成为数据交换和数 据表示领域事实上的标准，基于x m l 的发布订阅系统已经成为发布订阅系统研 究的热点。用x m l 来结构化地表示数据，虽然可以进行精确地匹配和路由，但是 验证和解析x m l 需要花费大量的时间。s a r v e g a 等公司的x m l 加速设备和x m l 路由器可以对x m l 进行高达1 g b p s 的线速处理，使得实现基于x m l 的大规模发 布订阅系统更加可行。 发布订阅系统的关键技术主要包括数据模型、订阅模型、匹配算法、拓扑结 构和路由算法五个方面。本文从这五个方面出发，比较分析了各个关键技术目前 的科研成果，设计并实现了一个基于x m l 的发布订阅原型系统。 关键词：发布订阅，分布式系统，可扩展标记语言，x p a t h ，匹配，路由。 a b s t r a c t a st h ei n t e m e tt e c h n o l o g yd e v e l o p sa t v e r yf a s ts p e e da n di su s e dw i d e l y , t h e m e t h o dt h a tp e o p l eg e ti n f o r m a t i o nc h a n g e sg r e a t l y ，n l et r a d i t i o n a lm e t h o do fg e t t i n g i n f o r m a t i o nf r o mi n t e r a c ti sl o o k i n gf o ri to nw e bs i t e so rs e a r c h i n gf o rt h ew e b p a g e s u s i n gs e a r c h i n ge n g i n e sl i k eg o o g l ea n db a i d u 1 1 1 i sk i n do f m e t h o dw a s t e sp e o p l em u c h t i m ei nl o o k i n ga r o u n da n df r e q u e n t l yc l i c k i n go nt h el i n k sm a k e sm u c hr e d u n d a n td a t a f l o wo nt h ei n t e r n e t t h ep u b l i s h s u b s c r i b ec o m m u n i c a t i o nm o d ec a l ls o l v et h i s p r o b l e m ap u b l i s h s u b s c r i b es y s t e mc o n s i s t so fp u b l i s h e r s ，i n f o r m a t i o nb r o k e r sa n d s u b s c r i b e r s p u b l i s h e rp u b l i s h e si n f o r m a t i o nt ot h ei n f o r m a t i o nb r o k e r s ，s u b s c r i b e r s u b s c r i b e si n f o r m a t i o nt ot h eb r o k e r sa n dt h eb r o k e r ss e n dt h ei n f o r m a t i o ns u b s c r i b e dt o t h es u b s c r i b e r se x a c t l ya n dt i m e l y p u b l i s h e ra n ds u b s c r i b e rd on o tc o m m u n i c a t ew i t h e a c ho t h e rd i r e c t l y , s ot h es y s t e mi sl o o s e l yc o u p l e d ，w h i c hm a k ei tn l o r ee f f i c i e n tt o r e a l i z el a r g es c a l ed i s t r i b u t e ds y s t e mt h a nt r a n d i t i o n a lm o d e ss u c ha sr e m o t ep r o c e d u r e c a l la n dm e s s a g eq u e u e s op u b l i s h s u b s c r i b es y s t e mg a i n sm o r ea n dm o r ea t t e n t i o n f r o ma c a d e m i cc o m m u n i t i e sa n dc o m p a n i e s i np u b l i s h s u b s c r i b es y s t e m ，t h ed a t am o d e lo fi n f o r m a t i o nd i r e c t l ya f f e c t st h e s y s t e me x p r e s s i o na b i l i t ya n ds c a l a b i l i t y 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 ) c a l l d e n o t ed a t a s t r u c t u r a l l y , s o i ti sav e r yg o o dc h o i c ef o rt h ed a t am o d e lo f p u b l i s h s u b s c r i b es y s t e m ，a n di t se x c e l l e n ts c a l a b i l i t ya n dp l a t f o r mi n s e n s i b i l i t yi sa p l u s x p a t h ，as t a n d a r di nt h e ls t a n d a r ds u i t ，c a l lb eu s e de f f e c t i v e l ya ss u b s c r i p t i o n p r o f i l e x m lh a sb e e nt h ed ef a c t os t a n d a r di ni n f o r m a t i o ne x c h a n g ea n di n f o r m a t i o n d e n o t a t i o ni nt o d a y s n t c m e ta p p l i c a t i o n s d a t ac a l lb ee x a c t l ym a t c h e da n dr o u t e di n t h ef o r m a to fx m l ，h o w e v e r , t h ev a l i d a t i n ga n dp a r s i n go fx m la r ec p uw a s t e dj o b s s o m en e wc o m p a n i e ss u c ha ss a r v e g aa n dd a t a p o w e rd e s i g n e dx m l a c c e l e r a t i n g d e v i c ea n d ) ( 】lm u t e rw h i c hc a l lp r o c e s sx m ld a t ai n1g b p sl i n es p e e d ，w h i c hm a k e i tm o r ef e a s i b l yt or e a l i z ep u b l i s h s u b s c r i b e s y s t e mi nl a r g e s c a l ed i s t r i b u t e d e n v i r o n m e n t t h ek e yt e c h n o l o g i e so fp u b l i s h s u b s c r i b es y s t e mm a i n l yi n c l u d ed a t am o d e l ， l i ! ! 望! ! ! 兰! 篁! 一 一一 。一_ _ 一一。一。 s u b s c r i p t i o np r o f i l e ，m a t c h i n ga l g o r i t h m ，t o p o l o g y a n dr o u t i n ga l g o r i t h m t h i s d i s s e r t a t i o nd i s c u s s e st h ep u b l i s h s u b s c r i b es y s t e mi n t h ef i v ep o i n t sa b o v ea n d a n a l y z e dt h e s t a t e o f - a r tr e s e a r c hf r u i to ft h e s et e c h n o l o g i e s t oe v a l u a t et h ek e y t e c h n 0 1 0 西e sa n dr e s e a r c hp u b l i s h s u b s c r i b es y s t e mf u r t h e r , w ed e s i g n e da n d r e a l i z e d ax m l - b a s e dp u b l i s h s u b s c r i b ep r o f i l es y s t e m k e ) , w o r d s ：p u b l i s h s u b s c r i b e ，d i s t r i b u t e ds y s t e m ，x m l , x p a t h ，m a t c h i n g ，r o u t i n g 1 1 1 缩略词 d f a d o m d t d e d i m o m n f a p 2 p r d f r m i i 冲c r s s s a x s g m l s s l x s l x m l 缩略词 d e t e r m i n a t e df i n i t ea u t o m a t e d o c u m e n to b j e c tm o d e l d o c u m e n tt y p ed e f i n a t i o n e l e c t r o n i cd a t ae x c h a n g e m e s s a g eo r i e n t e dm i d d w a r e n o n d e t e r m i n a t e df i n i t ea u t o m a t e p e e r - t o - p e e r r e s o u r c ed e s c r i p t i o nf r a m e w o r k r e m o t em e t h o di n v o c a t i o n r e m o t ep r o c e d u r ec a l l r e a l l ys i m p l es y n d i c a t i o n s i m p l ea p if o rx m l s t a n d a r df o rg e n e r a lm a r k u pl a n g u a g e s e c u r es o c k e t sl a y e r e x t e n s i b l es t y l e s h e e tl a n g u a g e e x t e n s i b l em a r k u pl a n g u a g e v i 确定性有限状态机 文档对象模型 文档类型定义 电子数据交换 消息中间件 非确定性有限状态机 对等网络、点对点网络 资源描述框架 远程方法调用 远程过程调用 聚合内容 简单编程接口 通用标记语言标准 安全套接口层 可扩展样式表语言 可扩展标记语言 第一章引言 1 1 题目背景 第一章引言 i n t e r n e t 技术的飞速发展和广泛普及，使人们获取信息的方式发生了革命性的 变革。现在占据统治地位的i n t e r n e t 访问方式是w e b 访问和搜索，即人们到指定网 站上去查找需要的信息或者用搜索引擎搜索自己需要的信息链接。这种方式给人 们带来了很大的自主性，但信息的定位不够精确，仍需花费大量的时间来进一步 查找，而且反复的查询，增加了许多不必要的网络流量。如果能只需打开一个软 件，就可以获得自己想看到的最新新闻、股票报价、拍卖、b l o g 更新、网站新帖 等信息，那将会大大节约人们获取信息的时间。因此人们想到了发布订阅 ( p u b l i s h s u b s c r i b e ) 的通信方式。 发布订阅是一种信息驱动的通信方式，它由三部分组成：信息发布者、信息 中介系统和信息订阅者。信息订阅者向中介系统订阅自己感兴趣的信息，信息发 布者向中介系统发布自己的信息，信息中介系统将信息转发到订阅者手中。此系 统中的信息发布者和订阅者无需互相通信，即实现了完全的解耦。因此发布订阅 系统至少有下面三个优点：第一，这种通信方式具有非常好的松散耦合性，与传 统的w e b 访问、远程信息调( r p c ) 等通信方式相比，更适合于组建大规模分布 式系统；第二，这种信息驱动的方式使人们可以及时准确地获得自己感兴趣的信 息，大大节约了人们获取信息的时间；第三，信息可以根据内容进行精确过滤， 使得有需要的信息才在网络上传输，有效节约了网络带宽。因此发布订阅系统成 为目前分布式系统领域中一个研究热点。早期的基于主题的发布订阅系统已经有 n a s d a q 证券交易系统、费城股票交易所业务系统等应用，未来基于内容的发布 订阅系统在各类电子商务系统( 网上拍卖系统、网上交易市场) 、企业应用集成、 基于事件的供应链管理、电子新闻分发、在线网络游戏和大规模环境监测等领域 都可能会被广泛应用【l j 。 另一方面，x m l 正在逐渐成为电子信息领域中数据表示和数据交换的基本格 式。x m l 可以结构化地表示数据，而且具有扩展性强和平台无关性等优点。用 x m l 作为发布订阅系统中的数据模型，可以大大提高系统的表达能力。目前基于 电子科技大学硕学位论文 x m l 的发布订阅系统已经是发布订阅系统中研究的热点，国外在x m l 过滤算法、 基于内容的路由算法等方面已经有了许多科研成果，并且有了一些可以实际应用 的原形系统，但是面向大规模分布式系统的相关技术还不够成熟。用x m l 来结构 化地表示数据，虽然可以进行精确地匹配和路由，但是对x m l 文档的解析、验证 等额外的处理工作仍然需要花费大量的时间。s a r v e g a ( 已被i n t e l 收购) 等公司的 x m l 加速设备和x m l 路由器可以对x m l 进行高达1 g b p s 的线速处理，使得实 现基于x m l 的大规模发布订阅系统更加可行。 因此研究基于x m l 的发布订阅系统的关键技术，结合x m l 加速和x m l 路 由器的概念，具有非常重要的现实意义。如果发布订阅系统能够大规模应用，将 会带来巨大的社会效益和经济效益。 1 2 主要工作 本课题属于新技术探索性研究，主要目的是研究x m l 在发布订阅系统中的应 用，研究基于内容的发布订阅系统的关键技术，并设计一个原型系统。本系统的 设计主要考虑事件模型、订阅模型、匹配算法、拓扑结构、路由算法等关键技术 的研究。主要工作如下： 1 研究x m l 相关技术标准； 2 比较全面地分析比较了目前主要的x m l 匹配算法； 3 研究基于内容的发布订阅系统的各项关键技术的研究现状和原型系统的 研究现状； 4 根据当前的理论支持和自己的改进，设计并实现了一个基于x m l 的发布 订阅原型系统； 5 总结发布订阅系统的设计经验，提出需要改进的地方，明确研究方向。 1 3 章节安排 第二章介绍了x m l 相关标准，这些标准都是基于x m l 的发布订阅系统的研 究中需要用到的。第三章将发布订阅系统与其他通信方式向比较，分析其松散耦 合( l o o s e l y - c o u p l e d ) 的特性；介绍了发布订阅系统基于主题( s u b j e c t b a s e d ) 和 2 第一章引言 基于内容( c o n t e n t - b a s e d ) 的分类；介绍了发布订阅系统的事件模型、订阅模型、 匹配算法、拓扑结构和路由算法五项关键技术，重点对x m l 过滤算法进行了分析 比较，并介绍了被采用的y f i l t e r 匹配算法；介绍了目前学术晃和工业界主要的基 于内容的发布订阅系统；第四章根据五项关键技术的研究成果和自己的改进，给 出了原型系统的设计方案和原型系统的具体实现。第五章对本文工作进行总结， 并提出了未来的工作方向。 1 4 本章小节 本章介绍了课题的研究背景，介绍了作者的主要工作，并介绍了下面各章的主 要内容。 电子科技大学硕学位论文 2 1x m l 概述 第二章x m l 及相关标准 可扩展标记语言( 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 ) 是从通用标记语言 ( s g m l ) 衍生出来的一种简单、灵活的标记语言。它是一种元标记语言，任何行 业和组织可以根据x m l 的语法规则，根据其内部数据格式的特点制定出自己的 x m l 标记语言。x m l 最初的设计目的是用来满足大规模电子信息交换的需求， 目前x m l 在w e b 服务、数据表示、数据挖掘和各种数据交换等领域扮演越来越 重要的角色【2 1 。它由w 3 c 提出并被微软、i b m 等几乎全球信息领域的所有大公司 支持。目前x m l 有w 3 c 支持的非常丰富的标准，应用极其广泛。可以查询得到 的x m l 标记语言有5 0 0 种以上，比如用于重写h t m l 的x h t m l 、电子商务领域 的e x m l 、音频领域的v o i c e x m l 、流媒体领域的s m i l 、数学领域的m a t h x m l 等等。x m l 现在已经成为数据表示和数据交换领域的通用格式和事实上的标准。 根据市场调研厂商z a p t h i n k 的分析人士预测，基于x m l 的互联网和企业网流量 在所有网络流量中的比例将由2 0 0 4 年的1 5 提高到2 0 0 8 年的约5 0 。 x m l 由嵌套的元素标签、元素属性、元素内容等组成，使得信息被结构化地 表示，从而大大提高信息表示的准确性和处理效率。这种结构不但使人们对文档 的结构和内容一目了然，对计算机来说x m l 文档也是可读的。图1 1 是一个表示 个人信息的一个x m l 文本段。 4 第二章x m l 及相关标准 1 ) 级，如果x p a t h 表 达式以开头，则该x p a t h 路径为相对路经；謇为通配符，与任意节点匹配； 位置匹配用来匹配元素出现的次序。例如： 1 2 第二章x m l 及相关标准 s i t e p e o p l e p e r s o n 1 】匹配p e o p l e 的第一个p e r s o n 子元素； s i t e p e o p l e p e r s o n 1 a s t o 匹配p e o p l e 的最后一个p e r s o n 子元素； s i t e p e o p l e p e r s o n p o s i t i o n o 1 】匹配p e o p l e 的p e r s o n 子元素中位置号大于1 的 r p 一：# 所伺p e r s o n 兀系。 属性匹配用来匹配元素中的属性值，属性名前用“ 来标志。例如： s i t e p e o p l e p e r s o n i d = “1 2 3 4 5 6 7 8 9 ”】匹配属性值为“1 2 3 4 5 6 7 8 9 ”的p e r s o n 元素； 另外属性节点可以是【d 】，表示只要包含此属性即匹配： 木 表示只要包含属性 则匹配； n o t ( i d ) 表示不包含此属性才匹配。 亲属关系匹配由x m l 文档的树型结构引发而来。通常把节点之间的归属关系 归结为一种亲属关系，如父亲、孩子、祖先、后代、兄弟等等。在对元素进行匹 配时，同样可以用到这些概念，亲属匹配是路径匹配的扩充，具有回溯匹配功能。 例如，在满足路径匹配的前提下： n a m e p a r e n t ：* 匹配所有n a m e 节点的父节点元素； a g e a n c e s t o r ：* 匹配所有a g e 元素的祖先节点元素； s i t e c h i l d ：* 匹配s i t e 的子元素，与s i t e * 相同； s i t e d e s c e n d a n t ：* 匹配s i t e 的所有后代元素，与s i t e * 相同； a g e s e l f ：* 匹配所有a g e 的自身元素： a g e a n c e s t o r - o r - s e l f ：* 匹配所有a g e 元素及它的祖先节点元素； s i t e p e o p l e d e s c e n d a n t o r - s e l f ：* 匹配p e o p l e 元素及它们的后代元素； s i t e p e o p l e f o l l o w i n g - s i b l i n g ：* 匹配p e o p l e 元素后序的所有兄弟元素； s i t e p e o p l e p r e c e d i n g s i b l i n g ：* 匹配p e o p l e 元素前序的所有兄弟元素； s i t e p e o p l e p e r s o n f o l l o w i n g ：事匹配p e r s o n 元素后序的所有元素； s i t e p e o p l e p r e c e d i n g ：幸匹配p e o p l e 元素的前序的所有元素； 条件匹配就是利用一些函数的运算结果的布尔值来匹配符合条件的节点。常用 于条件匹配的函数有四大类：节点函数、字符串函数、数值函数、布尔函数。例 如前面提到的l a s t 0 、p o s i t i o n o 等等，例如： s i t e p r o f i l e i n c o m e 1 0 0 0 0 a g e t e x t o 2 0 ，该表达式匹配p r o f i l e 的i n c o m e 属性值大于1 0 0 0 0 并且元素a g e 的值大于2 0 的a g e 元素。 上面的匹配方法多是结合使用。 电子科技大学硕学位论文 2 5 本章小节 本章介绍了x m l 标准体系中的主要标准，这些标准是x m l 应用的基石，是 基于x m l 的发布订阅系统的研究和设计所必需的知识。其中d t d 和s c h e m a 是 x m l 文档格式的框架，任何类型的x m l 都是由d t d 或s c h e m a 限定的。处理x m l 文档首先要对其进行解析，d o m 和s a x 是两种截然不同的解析方法，他们各有 优缺点，须根据不同的应用环境来选定。x p a t h 是对x m l 文档进行匹配的有效工 具，在x m l 的过滤算法中广泛采用，因此本节进行了较为细