（计算机应用技术专业论文）语义发布订阅系统数据模型和匹配算法研究.pdf

浙江大学硕士学位论文 摘要 摘要 随着计算机网络的快速发展，网络计算已进入大规模分布式计算时代。这种 大规模分布式计算与传统的计算环境相比，具有大规模、分散控制、动态性、松 散耦合等特点。发布订阅系统能够使得参与者之间在时间、空间和控制流方面 完全解耦，成为新一代分布式计算技术的基础平台。 现有的发布，_ 汀阅系统在基于内容的数据模型、匹配算法和路由算法上已经取 得了很多的研究成果，但是仍然缺乏对语义的支持。论文针对面向语义的发布 订阅系统的关键技术数据模型和匹配算法进行研究，并实现了基于语义的发布 订阅原型系统钱塘语义发布，订阅系统( j t a n gs e m a n t i cp u b l i c s u b s c r i b e s y s t e m ，简称j 胁妒s ) ，为大规模网络计算环境提供可选的中间件平台支持。 论文首先提出了一种面向语义的发布，订阅系统的数据模型，发布订阅系统 的数据模型决定了系统的表达能力，语义发布订阅系统的数据模型，包括概念 模型、事件模型和订阅模型。概念模型规定了某一领域中的概念及其之间的关系， 用o w l 语言来表示：事件模型规定了事件的表达方式，事件利用r d f 图来表 示；订阅模型规定了订阅的表达方式和过滤条件，用r d f 图模式来表示。这样 就可以使得信息被系统无歧义的理解和处理，并在不同程序间交换。此外，提出 了一种新的订阅语言j t a n g p s s l ，使得用户可以自定义订阅。 在上述语义数据模型的基础上，需要建立一种快速的匹配算法。我们的匹配 算法的根本思想是将订阅图模式和事件图分解为一系列弧的集合，以弧为单位进 行匹配。利用订阅之间的重叠性，将大量订阅合并为一个订阅，从而提高空间和 事件效率。在将一个事件转换为特定的数据结构时，利用推理机判断事件的有效 性并推理出额外的语义信息，与订阅进行匹配。在匹配过程中，利用订阅约束的 重复性，减少对变量约束的检查，提高时间效率。 最后，论文设计了一个发布订阅系统j 妒s ，实现了上述的数据模型和匹 配算法。该系统基于j a v a 技术开发，建立于已有覆盖网络之上，并提供丰富的 访问形式，测试数据表明，j t a n g p s 在表达能力和性能上有了很大的提升，能够 适应大规模网络计算的需要。 。 关键词：发布订阅系统，大规模分布式计算，中间件，语义，o w l ，匹配算法 塑垩盔兰堡主兰垡丝塞 一一一坐壁竺! 堕竺 a b s t r a c t i o n w i t ht l l er a p i dd e v e l o p m e n to fi n t e r a c t ，t h en e t w o r kc o m p u t i n gh a sc o m e i n t ot h e l a r g e s c a l e d i s t r i b u t e dc o m p u t i n ga g e c o m p a r i n gt ot h et r a d i t i o n a lc o m p u t i n g e n v i r o n m e n t ，t h er e c e n to n ei sc h a r a c t e r i z e db yt h el a r g e - s c a l e ，d e c e n t r a l i z a t i o n , d y n a m i ca n dl o o s ec o u p l i n g s i n c ep u b l i s h s u b s c r i b es y s t e m sh a v et h ea d v a n t a g eo f f u l l yd e c o u p l i n gi nt i m e ，s p a c ea n df l o w , t h e yh a v eb e c o m e t h ei n f r a s t r u c t u r ep l a t f o r m o ft h en e wd i s t r i b u t e dc o m p u t i n g t h ep u b l i s h s u b s c r i b es y s t e m sh a v eh a r v e s t e dal o ti nc o n t e n t - b a s e dd a t am o d e l ， m a t c h i n ga l g o r i t h m sa n dr o u t i n ga l g o r i t h m s ，b u tt h e ya r es t i l ls h o r to fs u p p o r to f s e m a n t i c t h et h e s i sd o e sr e s e a r c ho ns e m a n t i c b a s e dd a t am o d e la n dm a t c h i n g a l g o r i t h m s ，t h ek e yt e c h n i q u eo fp u b l i s h s u b s c r i b es y s t e m s ，a n dd e v e l o p sap r o t o t y p e o fp u b l i s h s u b s c r i b es y s t e mc a l l e dj t a n gs e m a n t i cp u b l i s h s u b s c r i b es y s t e m ，s h o r tf o r j t a n g p s ，w h i c hs t r o n g l ys u p p o r t sl a r g e - s c a l ei n t e m e tc o m p u t i n ge n v i r o n m e n t a tf i r s t ，t h et h e s i sp r o p o s e sas e m a n t i c b a s e dd a t am o d e lo fp u b l i s h s u b s c r i b e s y s t e m t h ed a t am o d e lr e g u l a t e st h ea b i l i t y o fe x p r e s s i o n t 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 mi n c l u d e sc o n c e p t u a lm o d e l ，e v e n tm o d e la n ds u b s c r i p t i o n m o d e l t h ec o n c e p t u a lm o d e ls h o wt h ec o n c e p t so fad o m a i na n dt h e i rr e l a t i o n s ， r e p r e s e n t e db yo w l ( w e bo n t o l o g yl a n g u a g e ) t h ee v e n tm o d e li u n m i n a t e st h ee v e n t e x p r e s s i o nw a y , r e p r e s e n t e db yr d f ( 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 ) g r a p h t h e s u b s c r i p t i o nm o d e ls h o w st h ee x p r e s s i o nw a ya n df i l t e rc o n d i t i o no fs u b s c r i p t i o n , r e p r e s e n t e db yr d fg r a p hp a r e m s ot h ei n f o r m a t i o ne x p r e s s e db yd a t am o d e lc o u l d b ee x c h a n g e db e t w e e nd i f f e r e n ta p p l i c a t i o n s ，b eu n d e r s t o o da n dd i s p o s e db ys y s t e m a n dm o r e ，w ep r o p o s ean e w s u b s c r i p t i o nl a n g u a g ec a l l e dj t a n g p s s l b a s eo nt h es e m a n t i cd a t am o d e l ，a ne f f i c i e n tm a t c h i n ga l g o r i t h mi sr e q u i r e d t h e b a s i ci d e ao fm a t c h i n ga l g o r i t h m si s ：d e c o m p o u n d i n gt h es u b s c r i p t i o ng r a p hp a a e m a n de v e n tg r a p hi n t oas e r i e so fa r c sw h i c ha r et h eb a s i cu n i t sf o rm a t c h i n ga l g o r i t h m s m a k i n gf u l lu s eo ft h eo v e r l a po fs u b s c r i p t i o n ，m e r g el o t so fs u b s c r i p t i o ni n t oal a r g e o n e a tt h et i m eo ft r a n s f o r m i n gae v e n t ，ar e a s o n i n gm e c h a n i s mi su s e dt oj u d g et h e v a l i d i t yo fe v e n ta n dt op r o d u c ee x t r ai n f o r m a t i o nf o rm a t c h i n gw i t hs u b s c r i p t i o n i n t h ep r o c e s so fm a t c h i n g ，w em a k eu s eo ft h eo v e r l a po fr e s t r i c t i o nt or e d u c et h ec h e c k o fv a r i a b l er e s t r i c t i o na n dt om a k et h ep r o c e s sf a s t e r a tl a s t , w ed e v e l o pap u b l i s h s u b s c r i b e s y s t e mc a l l e dj t a n g p s ，w h i c h i m p l e m e n t e dt h ep r o p o s e dd a t am o d e la n dm a t c h i n ga l g o r i t h m s t h ep r o t o t y p ei s d e v e l o p e d i nj a v a , b a s e do n ae x i s to v e r l a yn e t w o r ka n do f f e rm u l t i - w a yo f a c c e s i n g i i 塑翌奎兰堡主堂垡笙苎 一型璺竺! 兰! 苎 k e y w o r d s ：p u b l i s h s u b s c r i b es y s t e m ，l a r g e - s c a l ed i s t r i b u t e dc o m p u t i n g ，m i d d e w a r e ， s e m a n t i c ，o w l ，m a t c h i n ga l g o r i t h m s 1 1 1 图目录 图1 1 发布订阅通讯模型4 图1 2 分布式通知服务模型5 图2 1 语义w 曲的体系结构1 5 图2 2 资源”a u t h o r 的三元组描述1 7 图2 3 资源“a u t h o r 的r d f 图描述1 7 图2 4 资源”a u t h o r 的r d f x m l 描述1 7 图2 5 本体描述语言栈1 9 图2 6 食品领域部分类的层次结构2 1 图2 7 食品领域部分属性的层次结构2 3 图2 9o w l 部分推理规则2 5 图2 1 0 用户自定义推理规则2 5 图2 1 1j e n a 推理引擎结构2 6 图2 1 2i e n a 推理机的应用2 6 图2 ，1 3 葡萄酒r d f 事件图g e 2 7 图2 1 4 葡萄酒r d f 事件图的r d f x m l 表述2 8 图2 15 订阅图g s , 和g s 2 3 0 图2 16 订阅语言描述3 0 图2 17 订阅语言j t a n g p s s l 的语法规则31 图2 1 8 订阅g s l 的订阅语言描述3 1 图3 1 订阅s l 的数据结构3 6 图3 2 订阅的转换算法3 7 图3 3 订阅s 2 的数据结构3 8 图3 4 合并订阅s m 的数据结构3 9 图3 5 订阅插入算法4 1 图3 6 事件e 的r d f 图o e 4 2 图3 7 事件e 的数据结构4 3 图3 8 事件的转换算法。4 4 图3 9 事件与订阅的匹配算法4 6 图3 1 0 合并订阅s m 变量表的自然连接4 7 图3 1 1 订阅内存消耗同订阅数量关系图4 9 图3 1 2 不同参数对匹配时间的影响5 0 图3 1 3j t a n g p sv sg t o p s s 5 0 图4 1j t a n g p s 系统分层体系结构5 2 图4 2j t a n g p s 功能结构图5 3 图4 3j t a n g 应用层模块类图5 6 图4 4j t a n g 核心模块类图5 7 图4 。5j t a n g 消息模块类图5 8 图4 6 客户端连接时序图5 9 图4 7 订阅发布与处理的时序图5 9 图4 8 事件发布与处理时序图6 0 v 1 浙江大学硕士学位论文 表目录 表目录 表1 1 分布式环境各种通讯模型的比较3 表3 1 模拟实验缺省参数值4 8 v i i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝婆苤堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：士牟址 签字目期：7 粥 年矽月7 日 学位论文版权使用授权书 本学位论文存者完全了解澎婆盘茔有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权澎鎏盘堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期7 p 移年月矽日 签字日期：钐稚6 月3 日 浙江大学硕士学位论文 第1 章绪论 1 1 研究背景 第1 章绪论 随着计算机网络的兴起，计算技术已经进入分布式计算时代，分布式计算已 经成为新一代计算和应用的主流。传统的分布式计算是以请求应答( r e q u e s t r e p l y ) 的方式进行信息交互的，即客户端通过发送一个请求或者执行一个远程方法调用 ( r m i ) 【1 1 ，然后接受一个应答的方式向服务器端请求一个服务。该方式在拥有 数量比较少的客户端和服务器端的网络中能够得到很好的应用。近年来，随着 i n t e r n e t 的广泛普及，传统的基于请求应答的点对点通讯和同步通讯已经不能满 足大规模的分布式计算环境。在这种大规模的计算环境下，其参与者数量巨大， 并且分散于世界各地，通过i n t e m e t 进行大规模计算和资源共享。 这种新型的分布式计算环境与传统的分布式计算环境相比，具有如下一些典 型特征： 大规模：有大量参与者，并且参与者分散于世界各地。比如说 s e t i h o m e l 2 1 ，就有2 2 6 个国家和地区、超过5 0 0 万人和团体参与。 分散控制：在大规模分布式计算环境下，没有一个集中控制点，各个节 点都是以平等的方式参与其中。 动态性：各个参与者可以以动态的方式参与或退出。比如在旅途中利用 掌上电脑或手机等移动设备参与或退出网络。 自治性：各个参与节点都为自治体，参与某一大规模计算的一部分。 松耦合：各个参与者以一种松散耦合的方式进行资源共享和协同工作。 由于大规模分布式计算的这些特性，在过去的2 0 多年时间里，人们提出了 多种技术，包括： 中间件技术：随着上世纪9 0 年代初，面向对象技术的推广和应用，面向 对象的中间件技术逐渐成为主流，出现大量中间件标准，并产生了不同 类别的中间件产品，主要有：消息中间件( m o m ) 【3 】、数据库中间件 ( d a t a b a s em i d d l e w a r e ) 、远程过程调用中间件( r p c ) 【4 】和对象请求代 理中间件( o r b ) 等。 网格技术【5 】：随着i n t e m e t 的普及，对网格的研究越来越被重视。主要有： 维吉尼亚大学的l e g i o n l 6 计划、欧共体出资的e u r o c r r i d 项目【7 1 和美国国 家科学基金资助的t e r a g r i d 8 】项目等。 移动主体技术【9 】：移动主体是主体技术和分布式技术结合的产物，除了 具有主体的自治性、响应性、推理性以外，还具有移动性，即可以在网 浙江大学硕士学位论文 第1 章绪论 络上不同的节点之间移动，从而有效分散分布式计算中的网络负载、提 高通讯效率，并具有很好的安全性和容错能力。 p 2 p 技术：p 2 p 技术为一种通讯模式，在这个模式中，每一个节点都具 有相同的能力，可以动态的加入和退出系统而不影响系统的正常工作， 系统中每一个节点都可以同时作为客户端和服务器工作。如今，p 2 p 技 术已经成为一种重要的分布式计算技术。 w e bs e r v i c e 技术：其主要目的在于使i n t e m e t 的信息能为计算机所理解， 从而最大限度的实现网络上的资源共享。随着语义w e b 的发展，人们可 以通过计算机软件在i n t e m e t 进行智能搜索，来找到自己需要的信息和服 务。 但是上述技术都没有能够很好的解决参与者问以松散耦合的方式进行交互 的问题。所以，一种与请求应答方式完全不同的异步通讯机制一一发布订阅通 讯模型应运而生。发布订阅模型很好的解决了参与者之间松散耦合的问题，因 而越来越受到业界的重视。一个发布订阅系统一般来说包括信息生产者、信息 消费者和事件通知服务三个部分，信息生产者和信息消费者通过事件通知服务交 互。信息消费者向事件通知服务发布一个订阅条件，表示对特定信息的兴趣。而 信息的生产者则向事件通知服务发送信息，事件通知服务然后将订阅者感兴趣的 信息及时、可靠的传送给信息的消费者。在整个系统中，信息生产者和信息消费 者是以松散耦合的方式进行交互的，即生产者和消费者不是直接交互，而是通过 事件通知服务，生产者和消费者都不需要知道对方的存在。 现有的发布订阅技术的研究成果还不是很成熟，在表达能力、效率、可靠性 和安全性等方面还存在着较多的问题，仍不足以支持大规模的网络计算环境。要 使发布订阅模型真正成为网络环境下的分布式计算基础设施，仍有许多研究工 作亟待解决。因此，论文主要针对当前大规模网络计算环境，探讨对等网络下发 布订阅系统的关键技术问题，对发布订阅系统的数据模型、匹配算法进行研究， 并开发出相应的原型系统，从而为大规模网络计算提高一种可靠的中间件支持。 1 2 发布，订阅概念及应用 1 2 1 发布订阅相关通讯模型 在分布式领域，人们曾经提出了许多种通讯模型，下面列举几个比较典型的 通讯模型，并在时间耦合、空间耦合、控制流耦合和多点通讯方面与发布订阅 模型进行比较。 i 消息传递( m e s s a g ep a s s i n g ) 2 消息传递为分布式系统的底层通讯模型，其参与者通过简单的发送接收消息 来进行通讯。在此模型中，生产者和消费者在时间上和空间上是紧耦合的。在生 产者端是异步的，而在消费者端是同步的。因为一条消息只能发送给一个消费者， 所以是一对一的通讯关系。 2 远程过程调用( i 冲c ) 远程过程调用曾是最为流行的一种分布式通讯关系模型，在时间、空间和控 制流方面都是紧耦合的。 为了解决远程过程调用中的效率低下的问题，人们对其进行了改进。比如说， c o r b a 就采用了单向调用( o n e - w a y ) b 2 】的方式，但这种方式的可靠性比较低。 3 共享空间( s h a r e ds p a c e ) 分布式共享内存( d i s t r i b u t e ds h a r e dm e m o r y ) 使得在一个分布式环境下的参 与者能够共享一块空间，在这个空间里，参与者可以操作共享的数据。在语言层 次上结合了l i n d a g e l e m t e r1 9 8 5 t 1 3 1 的元组数据概念则是采用了这种机制。其主 要包括了三种方法：o u t ( ) 表示将元组数据导入元组数据空间，i i l ( ) 表示将元 组数据从元组数据空间中取出并在空间中删除此数据，r e a d ( ) 表示从空间中读 数据而不将其删除。 共享空间在时间和空间上实现了松散耦合，但并没有实现控制减耦的问题。 4 消息队列( m e s s a g eq u e u i n g ) 消息队列是中间件经常使用的通讯模型之一。在此模型中，生产者和消费者 共享一个队列，生产者将消息发送到此队列，消息队列对消息按照一定的形式进 行排序，而消费者则根据顺序从队列中得到最前面的消息。 消息队列和发布订阅模型相似，在时间、空间和控制流上都实现了松散耦合。 但是和发布订阅模型不同的是，它只能实现一对一的通讯。 很多实现了消息队列的产品，比如i b mm q s e r i e s 都在消息队列的基础上对 其进行了扩展，从而提高对发布订阅的支持。 表1 1 对上述几种模型与发布订阅模型在时间、空间、控制流和多对多通讯 方面进行了比较。 表1 1 分布式环境各种通讯模型的比较 通讯模型 时间解耦空间解耦 控制流解耦多对多通讯 消息传递 否否是否 远程过程调用否否否否 共享空间是是否否 消息队列是是是否 发布订阅是是是是 浙江大学硕士学位论文 第1 章绪论 1 2 2 发布订阅系统基本模型 发布订阅系统一般由生产者、消费者和事件通知服务组成。生产者和消费者 之间通过事件通知服务进行交互。生产者负责产生事件，消费者则消费事件，事 件通知服务则是通常意义上所说的发布订阅中间件。建立在发布订阅系统上的 分布式系统称为基于事件的系统。 在一个发布订阅系统中，生产者将产生的事件( e v e n t ) 发布( p u b l i s h ) 到 事件通知服务( n o t i f i c a t i o ns e r v i c e ) ；消费者则以订阅( s u b s c r i p t i o n ) 的形 式向事件通知服务注册，表达对特定事件的兴趣；而事件通知服务则充当生产者 和消费者的中介，负责管理订阅、匹配与订阅相符的事件，并保证将生产者发布 的事件及时、可靠的以通知( n 0 t i f i c a t i o n ) 的形式发送给感兴趣的消费者。在 发布订阅系统中，生产者称为发布者( p u b l i s h e r ) ，消费者称为订阅者 ( s u b s c r i b e r ) 。其基本模型如图1 1 所示。 多唷 c j 日e v e n t j , p u b l i s h e r() 、。 q 汐 、。 图1 1 发布订阅通讯模型 事件和订阅 事件是个很宽泛的概念，现实生活中的各种信息都可以表示为一个事件， 比如说股票市场的信息、电子商务中拍卖的物品、无线传感器网络上各节点 采集的信息等。这些事件由发布者通过网络传送到通知服务上，并由通知服 务发送给匹配的订阅者。订阅是订阅者向通知服务发送的对某些事件感兴趣 的具有一定结构的数据模型，当订阅被发送到通知服务上时，由通知服务将 订阅进行合并。当有事件到达时，事件通知服务将事件同所有订阅进行匹配， 找出所有和事件匹配的订阅，然后将事件发送给匹配的订阅者。 发布者和订阅者 发布者( p u b l i s h e r ) 即通常所称的生产者，订阅者( s u b s c r i b e r ) 为消费 者。发布者只是负责向事件通知服务发送事件，而不关心事件的具体取向， 也不需要了解订阅者的情况，一旦向事件通知服务发送消息以后，发布者的 任务就完成了，具体应该向哪个订阅者传送事件有事件通知服务来完成。而 4 浙江大学硕士学位论文 第1 章绪论 订阅者和发布者类似，只是向事件通知服务发送订阅和取消订阅，而不关心 发布者的具体位置和多少。当发布订阅完成后，找到与订阅相关的事件由事 件通知服务完成。 事件通知服务 事件通知服务即发布订阅中间件，也称为事件代理，其主要功能为：接 收发布者发布的事件和订阅者发送的订阅，并管理订阅，进行事件与订阅的 匹配，负责发送匹配的事件到订阅者。 事件通知服务的实现方式分为两种：集中式和分布式。集中式只有一个 事件代理，所有的事件和订阅都发送到此事件代理上，即所有的发布者和订 阅者都和这个唯一的事件代理进行交互。集中式事件通知服务结构简单，易 于维护。但是随着订阅数量的增加，其性能会称为系统的瓶颈。在一个大型 的发布订阅系统中，客户端会有数十万甚至上百万个，事件代理需要同时管 理这么多客户端，性能会大大的降低。 为了解决系统的瓶颈问题，大规模的发布订阅系统往往采用分布式的系 统结构，其中分布多个事件代理，这些代理会形成一定的拓补结构，例如星 形、环形、无环图等结构，而每一个事件代理都会连接一定量的本地客户， 本地客户将事件或订阅发送到其连接的事件代理上，由此事件代理负责事件 或订阅的转发。 但是不管是集中式结构或分布式结构，发布者和订阅者之间都是松散耦 合的，即他们不需要知道对方的存在，而只负责发送事件、订阅和接收事件。 除了松散耦合的特性以外，发布订阅系统还具有多点通信的特点，即一个事 件可以同时发送给多个订阅者。 图1 2 分布式通知服务模型 浙江大学硕士学位论文 第1 章绪论 1 2 3 发布订阅系统应用 发布订阅系统技术有着良好的应用环境，早期的基于主题的发布订阅系统 的成熟产品已经广泛应用于银行、证券、交通等领域，比较著名的有n a s d a q 证券交易系统、费城股票交易系统等。而面向大规模计算环境的发布订阅系统， 其技术目前尚未完善，因此尚未被广泛应用，已经应用的和可预见的应用包括： 各类电子商务系统( 网上交易系统，如阿里巴巴等) 、企业应用集成( e a i ) 、无 线传感器网络、协同计算等。 电子商务系统 电子商务具有大规模和分散性的特点。在一个大型的电子商务系统中， 消费者数量巨大且来自不同地域。他们向系统发布一个事件或订阅后并不在 线等待，而是由系统将合适的信息p u s h 给他们。这些特点就决定了发布订 阅系统将成为电子商务系统的基础平台。 企业应用集成 企业应用集成通过各自开发的应用程序之间的集成实现信息的共享。但 由于应用程序独立性，使得其集成难度大大增加。所以，就需要中间件来完 成应用程序之间的通讯和协作，实现业务逻辑与通信的分离。而发布订阅系 统本身的特点恰恰符合其要求。 无线传感器网络 无线传感器网络由大量的信息采集节点以自组织的方式连接而成。各个 节点由于计算能力和能量等条件有限，就需要对数据进行加工并选择性的传 输：另外，由于节点的不固定，无线传感器网络的拓扑结构就处于不断变化 中。这样，发布订阅系统就成为无线传感器网络数据传输的首要选择。 协同计算 在协同计算环境中，各参与者往往处于不同的领域和地域。在一个复杂 的流程中，不同领域的应用程序不能之间通信，而且各个环节之间需要数据 的互通。而发布订阅系统的松散耦合特性则能满足其环境需要，为其提供安 全、可靠的数据传输功能。 1 3 典型发布，订阅系统介绍 由于发布订阅系统的松散耦合、匿名、多对多通讯的特定，国际上对发布 订阅系统的研究越来越重视，规模也越来越大。许多著名的i t 厂商和研究单位 都对发布订阅系统表现出浓厚的兴趣，并发布自己的研究产品，如m m 公司的 m q s e r i e s i b m1 9 9 7 【l o 】、浙江大学中间件技术研究中心的j t m a f f m q 、剑桥大学 6 浙江大学硕士学位论文 第1 章绪论 的h e r m e s t 3 1 1 、中科院软件所的p 2 p o p s 系统等。 1 ) m q s e r i e s m q s e f t e s 是i b m 开发的一款基于主题的商业通讯中间件。它由一个信息传 输系统和一个应用程序接口组成。m q s e r i e s 支持点对点的消息传递方式和发布 订阅的消息传递方式。 m q s e r i e s 支持所有重要的通信协议，并提供在不同协议的网络问的路由，它 可以通过使用一个简单且一致的应用程序接i ：1 实现应用程序跨平台的相互通信。 2 ) j t a n g m q j t a n g m q 是浙江大学中间件技术研究中心推出的符合j m s l 1 规范的消息中 间件，它提供了发布订阅和消息队列两种通讯模式。 j t a n g m q 系统采用反正控制i o c ( i n v e r s eo fc o n t r 0 1 ) 技术，使得j t a n g m q 既可以作为一个独立的消息中间件，又可以很方便的被集成到j 2 e e 应用服务器 中；采用面向方面的编程a o p 技术，可以方便的插拔安全、日志等功能，适用 不同应用场合的需要。 j t a n g m q 作为一个面向内容的发布订阅系统，还不能满足当前语义发展的需 要。 3 ) h e m e r s h e m e r s 3 1 1 是被作为分布式大规模数据分发应用程序的基础平台而研制的。它 结合了发布订阅、p 2 p 、数据库、中间件和网络等多个领域的概念，实现了基于 事件类型和内容的混合的事件模型，基于r b a c 的安全控制、基于阻塞控制的 路由，并且支持复合事件处理，具有表达能力强、路由效率高、安全可靠等特点。 4 ) p 2 p o p s p 2 p o p s 是中科院软件所推出的一款面向语义w e b 的发布订阅系统。主要是 为大规模计算环境提供一种强大的中间件支持。 p 2 p o p s 系统成功的将语义的概念应用到发布订阅系统中。提供丰富的客户 端接口；采用结构化p 2 p 网络增强了系统的容错性和扩展性；支持内容数据模型 到语义数据模型的转化。为新一代计算机网络提供了一种语义发布订阅的选择。 1 4 发布，订阅系统关键技术体系 发布订阅系统作为分布式计算环境的一个基础，其关键技术体系包括表达能 力、效率和可靠性方面。 1 表达能力 发布订阅系统的表达能力由数据模型决定，现在的多数发布订阅系统在表 达能力方面存在不足，往往缺乏对语义的支持。所以，论文的发布订阅系统必 7 浙江大学硕士学位论文 第1 章绪论 须支持对语义的理解，主要表现在： 能够建立一个语义层次上的概念模型。 能够在语义层上来描述一个事件。 提高一个建立在语义层上的订阅语言。 2 效率 发布订阅系统的效率主要包括下面： 时间效率：当一个事件发布后，能够在较短的时间内找到与之相匹配的订阅， 并快速将此事件发送给符合的订阅者。 空间效率：各个事件代理需要保存大量的订阅，所以要设计一种方法使其所 占空间尽可能小。 网络效率：因为在一个覆盖网络中，每个事件代理都需要转发消息或订阅， 所以要设计一种算法使得每个事件代理尽可能的转发相对较少的事件或订 阅，以减少网络资源消耗。 3 可靠性 当一个事件被发布后，能够确定这个事件被所有满足条件的订阅者接收到。 但是，在一个发布订阅系统中，上述目标往往很难兼顾。例如，为了具有更 强的表达能力，则需要设计尽可能复杂的数据模型，而数据模型越复杂，时间效 率和空间效率就会随之降低。因此，一个具体的发布订阅系统需要在上述目标 之间找到一个比较好的平衡点。 1 5 发布，订阅系统关键技术及研究现状 如1 2 2 节所示，一个发布订阅系统包括生产者、消费者和事件通知服务。 生产者负责产生事件并将事件发布到事件通知服务，消费者负责向事件通知服务 发送订阅表达对某些事件的兴趣，而事件通知服务负责接收事件和订阅、管理订 阅、把到达的事件与订阅进行匹配并把事件转发给合适的订阅者。而事件和订阅 如果要被事件通知服务所理解，就必须要有一定的表达形式，而事件和订阅的表 达形式及与其相联系的概念模型就构成了发布订阅系统的数据模型；事件通知 服务则需要一定的匹配算法将事件和订阅进行快速匹配；在一个分布式的计算环 境中，事件通知服务还负责事件和订阅的转发，则还需要具体的路由算法。数据 模型、匹配算法和路由算法就构成了发布订阅系统的关键技术。因为论文主要 对数据模型和匹配算法进行研究，而不牵涉到路由算法，故没有对现有的路由算 法进行分析。 8 浙江人学硕i j 学位论文 第1 章绪论 1 5 1 数据模型及研究现状 到现在为止，人们已经设计出了基于不同数据模型的发布订阅系统，其中应 用最为广泛的系统包括：基于主题的系统、基于内容的系统和基于类型的系统三 大类。 1 基于主题的发布订阅系统 最要的发布订阅系统是基于主题( t o p i c 或s u b j e c t ) 的概念上的，并且工业 界已经得以实现( t i b c o 1 9 9 9 】) 。这类系统在通道的基础上得以扩展，在基于 主题的系统中，所有的事件根据主题关键字进行划分，每一个事件只能属于其中 的一个主题。生产者和消费者通过某一主题进行交互。每一个主题可以认为是一 个自身的事件服务，用一个i d 来标识，并对外提供p u b l i s h ( ) 和s u b s c r i b e ( ) 接口。订阅者通过向某个主题发送订阅消息，而后会收到该主题内所有事件，而 不用关心事件的内容。 早期的系统不能对主题进行更细粒度的划分，后来人们在此基础上对此系统 进行了改进，提出了一个具有层次的主题概念。订阅者在订阅某个主题时，会同 时订阅此节点所有的子主题。主题的名称通常用一个类似u r l 的概念来表示， 但多数系统会支持在主题名称中包含通配符，例如t i b c or e n d e z v o u s t i b c o 1 9 9 9 t j ，这样就使得可以根据关键字向几个主题同时订阅或发布事件。 2 基于内容的发布订阅系统 基于主题的发布订阅 r o s e n b l u ma n dw 6 1 f1 9 9 7 t 1 4 】系统在表达能力上存在着 欠缺，而基于内容( 或基于属性) 的系统由于可以根据事件的内容向事件通知服 务发送订阅而极大的改善了这一特性。换句话来说，事件可以不根据外部的标准， 例如主题名称，而是根据本身的属性进行划分。这类属性可以是事件数据结构的 内部属性，如g r y p h o n 、s i e n a 或e l v i n ，或是与事件相关的元数据，例如j a v a 消 息服务( j a v am e s s a g i n gs e r v i c e ) 【l 引。 基于内容的发布订阅系统可分为两类：基于“属性一值 对的系统和基于 x m l 的系统。 基于“属性一值”对的发布订阅系统 在这类系统中，我们将事件表示为一系列“属性一值”对的集合，除了 这些“属性一值对的集合外，每个事件还可以包含一段系统不可理解的数 据区，例如j a v a 消息服务中的消息。 消费者通过一种订阅语言以过滤的形式来获取事件。这种过滤形式包含 对“属性一值”对的一些约束，约束以基本的操作符( = ， ，) 来 表示。这些约束条件可以通过逻辑与绑定形成订阅条件。 9 浙江大学硕士学位论文 第1 章绪论 当一个事件中只包含一个“属性一值 对时，它就变成了基于主题的发 布订阅系统，该“属性一值”对的值就是该主题的名称。因此，可以认为基 于主题的发布订阅系统是一种特殊的基于“属性一值对的系统。 基于x m l 的发布订阅系统 随着x m l 越来越多的作为不同系统间交互的格式，人们逐渐提出了基 于x m l 的发布订阅系统。在此系统中，一个事件就被表示为一个x m l 文 档，而订阅条件用x p a t h 来表示，其中包含对x m l 文档结构的约束，又包 含对属性值的约束，这种订阅语言通常被成为“树模式 ，它比基于内容的 系统的表达能力又有了进一步的提高。 但是对于此种系统而言，订阅者如果要发布一个订阅，就必须事先知道 事件的x m l 文档所遵循的x m ls c h e m a ，因此对消费者端的使用造成了不 便。 当每个事件的x m l 文档只有一个元素节点时，此系统就变成了基于“属 性一值”对的系统，此元素节点的属性值即为主题名称。因此，可以认为基 于“属性一值对的系统是一种特殊的基于x m l 的系统。 3 基于类型的发布订阅系统 主题通常并不单单根据事件内容，有时还会根据事件结构来划分事件。这种 方式就导致了利用事件类型来划分的发布订阅模型的产生。而这种划分法使得 系统和中间件的结合更加紧密。同时，在此系统中，面向对象的思想被引入，每 个事件对象属于某个特点的事件类型，事件对象中封装了属性和方法。订阅对象 封装了订阅对象，指出了感兴趣的事件类型。这种系统提供了很强的表达能力， 但效率较低。因为无法利用各订阅条件之间的共性，因而很难设计一种高效的匹 配算法。因此它不适合大规模的发布订阅系统。 4 基于语义的发布订阅系统 现在的大部分发布订阅系统在表达能力上存在着很大的不足，不能支持对事 件本身语义的理解，所以，将语义技术和本体论引入发布订阅系统是非常重要的， 从语义上进行事件与订阅的匹配，以提供匹配的准确度。近年来，一些研究者已 经对语义发布订阅系统进行了研究，相关研究工作包括：d r e a m 、g t o p s s 3 0 i 、 o p s 等。这些系统都利用本体语言工具建立一个统一的概念模型，从而解决事件 的异构问题。 1 5 2 匹配算法及研究现状 已有的发布订阅系统的匹配算法包括基于m a p 的匹配算法、基于x m l 的匹 l o 浙江大学硕士学位论文 第1 章绪论 配算法和基于本体的匹配算法等。 1 ) 基于m a p 的匹配算法 基于m a p 的发布订阅系统的匹配算法目前已经有很多人员和单位参与研究 并形成了一系列研究成果。 a g u i l e r a t l 6 】等人在1 9 9 9 年提出了一种基于搜索树的算法。在这种算法中，所 有的订阅被组织成一个树形结构，每一条从根到叶子的路径被表示成一个订阅， 每个非叶子节点表示对某个属性的一个操作，每条边代表操作结构。当事件到达 时，对该树进行遍历，遍历方式为深度遍历，当到达叶子节点时，表明事件与此 订