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

浙江人学硕l ? 学位论文 摘要 摘要 普适计算、移动计算等新一代网络计算是以大规模、分散控制、动态性、自 治性和松耦合为主要特征的大型分布式计算，发布订阅系统具有松耦合、匿名、 多对多通信和可扩展的特点，已成为支持新一代网络计算的重要基础中间件平 厶 口0 有状态发布订阅系统是在普通发布订阅系统基础上，实现了复合事件检测 的发布订阅系统。它不仅支持对单个事件的订阅，也支持对复合事件的订阅，使 得各发布者所发布的一系列事件所组成的事件序列满足某一种条件时通知客户， 这样可以高效的处理复杂的事件，从而改善系统的性能，具有重要的应用价值与 研究意义。 论文针对现有有状态发布订阅系统数据模型的表达能力、匹配算法性能等方 面存在的问题，结合国家8 6 3 课题、国家自然科学基金课题，研究有状态发布 订阅系统的数据模型与匹配算法。 论文第一部分论述了发布订阅系统的研究背景和研究意义。在阐述发布订 阅系统概念模型的基础上，介绍数据模型、匹配算法、系统拓扑结构和路由算法 等关键技术的国内外研究现状，分析有状态发布订阅系统的挑战与研究热点。 第二部分提出了一种支持多种复合事件操作的有状态发布订阅系统数据模 型。在分析传统的复合事件模型基础上，提出支持多种复合事件操作的数据模型， 并从复合事件模型和订阅模型两个方面介绍了有状态发布订阅系统的数据模型。 复合事件模型包括复合事件模式和时间模型，复合事件模式描述多个单一事件或 者复合事件的触发关系，时间模型描述多个事件之间时间序列上的关系。订阅模 型关注的是订阅者想要得到的数据，体现了系统的表达能力。订阅模型包括订阅 语言和观察模型。订阅语言用于描述订阅者感兴趣的复合事件，本文提出了一种 类似s q l 的查询语言，该语言支持多种复合事件订阅操作，并用形式化语言对各 种订阅操作进行了描述。观察模型用于描述感兴趣事件的检测机制，本文提出了 浙江大学硕j ：学位论文摘要 一种基于扩展的非确定型有限自动机的复合事件检测机制。 第三部分提出了利用谓词推导关系的快速匹配算法。高效的匹配算法是调和 系统丰富表达能力和可扩展性矛盾的关键。论文先介绍了整个匹配过程，明晰相 关挑战和难点。然后，提出一种流水线事件处理过程，以多线程的方式使匹配过 程中的事件扫描、过滤操作、事件匹配、重新发布或者通知订阅者流水处理，从 宏观上改进了复合事件检测算法。接下来，从微观上充分挖掘谓词间的推导关系， 提出了关系谓词匹配算法。该算法通过把订阅中的谓词组织成一种特殊的数据结 构，称为谓词关系表，来提高匹配效率。根据谓词判断顺序对谓词推导作用的影 响，提出了有序谓词匹配算法，可利用历史数据规律，预测将来的数据，把订阅 中的谓词组织成有序谓词关系表，进一步提高了匹配效率。最后，对关系谓词匹 配算法和有序谓词匹配算法进行了实验测试，并与一种基础的算法进行比较。结 果表明，有序谓词匹配算法体现出了很好的事件处理效率，很好的改善了有状态 发布订阅系统性能。 第四部分提出一种可扩展和可配置的有状态发布订阅系统体系结构。该原型 系统主要包括匹配管理器、订阅管理器、事件管理器和发布管理器。通过对各个 模块的扩展支持，以及配置管理和元服务管理的设计，使得系统可扩展和可配置。 最后，介绍了有状态发布订阅原型系统。 关键词：有状态发布订阅系统，复合事件，自动机，数据模型，事件匹配，谓 词推理 浙江人学硕i ：学位论文 a b s t r a c t a b s t r a c t n e t w o r kc o m p u t i n gs u c ha sp e r v a s i v ec o m p u t i n g ，m o b i l ec o m p u t i n ga n ds oo ni s an e wg e n e r a t i o no fl 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 、杭t ht h em a i nf e a t u r e so f l a r g e - s c a l e ，d e c e n t r a l i z e dc o n t r o l ，d y n a m i c ，a u t o n o m o u sa n dl o o s e l yc o u p l e d s i n c e p u b l i s h s u b s c r i b es y s t e m s h a v et h ea d v a n t a g e so fl o o s ec o u p l i n g ，a n o n y m i t y , m a n y - t o m a n yc o m m u n i c a t i o na n ds c a l a b i l i t y , t h e yh a v eb e c o m ei m p o r t a n ti n f r a s t r u c t u r em i d d l e w a r ep l a t f o r m ss u p p o r tf o r t h en e w g e n e r a t i o no fn e t w o r kc o m p u t i n g s t a t e f u lp u b l i s h s u b s c r i b es y s t e mi sb a s e do ng e n e r a lp u b l i s h s u b s c r i b es y s t e m ， a n dr e a l i z e st h ec o m p o s i t ee v e n td e t e c t i o n i tn o to n l y s u p p o r t ss i n g l e e v e n t s u b s c r i p t i o n s ，b u t a l s o s u p p o r t s f o rc o m p o s i t ee v e n ts u b s c r i p t i o n s w h e nt h e p u b l i s h e r sp u b l i s has e q u e n c eo fe v e n t sw h i c hs a t i s f yac e r t a i nc o n d i t i o i n ，n o t i f yt h e s u b s c r i b e r s s oy o uc a l le f f i c i e n t l yh a n d l ec o m p l e xe v e n t s ，t h e r e b yi m p r o v i n gs y s t e m p e r f o r m a n c e i th a si m p o r t a n ta p p l i c a t i o nv a l u ea n dr e s e a r c hs i g n i f i c a n c e f o rt h ed e f i c i e n c yo fd a t am o d e l s e x p r e s s i v ea b i l i t ya n di n s u f f i c i e n tp e r f o r m a n c e o fm a t c h i n ga l g o r i t h mo fe x i s t i n gs t a t e f u lp u b l i s h s u b s c r i b es y s t e m s ，t h i st h e s i sm a k e s t h er e s e a r c hm a i n l yo nk e yt e c h n o l o g i e si n c l u d i n gd a t am o d e la n dm a t c h i n ga l g o r i t h m o fs t a t e f u lp u b l i s h s u b s c r i b es y s t e m s t h ew o r kh a sb e e ns u p p o s e db yt h en a t i o n a l h i g h - t e c h r & dp r o g r a m ，c h i n a i nt h ef i r s tp a r to ft h e s i s ，w ed i s c u s st h er e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c eo f p u b l i s h s u b s c r i b es y s t e m a f t e re x p l a i n i n gt h ec o n c e p t u a lm 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 ，w ei n t r o d u c er e s e a r c hs i t u a t i o no fk e yt e c h n o l o g i e si n c l u d i n gd a t am o d e l ， m a t c h i n ga l g o r i t h m ，s y s t e m s t o p o l o g ya n dr o u t i n ga l g o r i t h m f i n a l l y , w ei n t r o d u c e t h ec o n c e p to fs t a t e f u lp u b l i s h s u b s c r i b es y s t e m sa n da n a l y z et h ec h a n l l e n g e sa n d r e s e a r c hf o c u so fs t a t e f u lp u b l i s h s u b s c r i b es y s t e m s i nt h es e c o n dp a r t ，w e p r e s e n tt h ed a t am o d e lo fc o m p o s i t ee v e n t f i r s t ，w e a n a l y z et h et r a d i t i o n a lc o m p o s i t ee v e n tm o d e l s ，a n dc o m p a r et h e i ra d v a n t a g e sa n d d i s a d v a n t a g e s t h e nd a t am o d e lo fo u rs t a t e f u lp u b l i s h s u b s c r i b es y s t e mi si n t r o d u c e d f r o mt w oa s p e c t s ：c o m p o s i t ee v e n tm o d e la n ds u b s c r i p t i o nm o d e l c o m p o s i t ee v e n t 浙江人学硕i j 学位论文a b s t r a c t m o d e li n c l u d e sc o m p o s i t ee v e n tp a t t e r na n dt i m em o d e l c o m p o s i t ee v e n tp a t t e r n d e s c r i b e st h et r i g g e rr e l a t i o n s h i p so fm u l t i p l es i n g l ee v e n t so rc o m p o s i t ee v e n t s ，a n d t i m em o d e ld e s c r i b e st h et i m er e l a t i o n s h i pb e t w e e ne v e n t s s u b s c r i p t i o nm o d e li s c o n c e r n e da b o u tw h a ts u b s c r i b e r sw a n tt og e t ，a n di t g r e a t l yd e c i d e st h es y s t e m s e x p r e s s i v n e s s s u b s c r i b em o d e li n c l u d e ss u b s c r i p t i o nl a n g u a g ea n do b s e r v a t i o nm o d e l s u b s c r i b el a n g u a g ei su s e db ys u b s c r i b e r st os u b s c r i b ec o m p o s i t ee v e n t sw h i c ht h e y a r ei n t e r e s t e di n t h i sp a p e rp r e s e n t sa ns q l l i k eq u e r yl a n g u a g e ，w h i c hs u p p o r t sa v a r i e t yo fc o m p o s i t ee v e n ts u b s c r i p t i o no p e r a t i o n s a n dw eu s ef o r m a ll a n g u a g et o c l e a r l yd e s c r i b et h e s es u b s c r i p t i o no p e r a t i o n s o b s e r v a t i o nm o d e li su s e dt od e t e c tt h e c o m p o s i t ee v e n t sw h i c hs u b s c r i b e r sa r ei n t e r e s t e di n ，a n dw ep r o p o s et h ee x t e n d e d n o n - d e t e r m i n i s t i cf i n i t ea u t o m a t af o ro b s e r v a t i o nm o d e l i nt h et h i r dp a r t , w ep r o p o s ef a s te v e n tm a t c h i n ga l g o r i t h m u s i n go ft h e r e l a t i o n s h i po fp r e d i c a t e s e f f i c i e n tm a t c h i n ga l g o r i t h mi st h ek e yt or e c o n c i l et h e c o n t r a d i c t i o n sb e t w e e na b u n d a n te x p r e s s i o na n ds c a l a b i l i t yo fs y s t e m w ef i r s t i n t r o d u c et h ee n t i r em a t c h i n gp r o c e s s ，i n c l u d i n gt h ef e a t u r e sa n dt h ed i f f i c u l t i e si n i m p l e m e n t a t i o n t h e n , w ep r o p o s eap i p e l i n e de v e n tp r o c e s s i n gm e t h o d ，w h i c ht a k e s a d v a n t a g eo fm u l t i - t h r e a d e da p p r o a c ht om a k et h em a t c h i n gp r o c e s sp i p e l i n i n g t h i s m e t h o di m p r o v e st h ee v e n tm a t c i n ge f f i c i e n c yf r o mt h em a c r ol e v e l n e x t ，w ef u l l y e x p l o i tt h er e l a t i o n s h i po fp r e d i c a t e sf r o mm i c r ol e v e l ，a n dp r o p o s ea na l g o r i t h m ， c a l l e dr e l a t i o np r e d i c a t e sm a t c h i n ga l g o r i t h m t h i sa l g o r i t h mb u i l d sas p e c i a ld a t a s t r u c t u r e ，c a l l e dp r e d i c a t er e l a t i o nt a b l ef o ri n d e x i n gt h ep r e d i c a t e so ft h es u b s c r i p t i o n s a st h eo r d e ro ft h ep r e d i c a t e st ob ej u d g e da l s op l a y sa ni n p o r t a n tr o l ei nt h ee v e n t m a t c h i n g ，w ee x p l o i tt h eo r d e ro ft h ep r e d i c a t e st ob ej u d g e d ，a n dp r o p o s et h eo t h e r a l g o r i t h m ，c a l l e do r d e rp r e d i c a t e sm a t c h i n ga l g o r i t h m i tu s e so fh i s t o r i c a ld a t at o p r e d i c tf u t u r ed a t a , a n do r g a n i z et h ep r e d i c a t er e l a t i o nt a b l ei ns e r t a i no r d e ra c c o r d i n g t ot h eh i s t o r i c a ld a t a , t of u r t h e ri m p r o v et h em a t c h i n ge f f i c i e n c y f i n a l l y , w ed o e x p e r i m e n tf o rr e l a t i o np r e d i c a t e sm a t c h i n ga l g o r i t h ma n do r d e rp r e d i c a t e sm a t c h i n g a l g o r i t h m ，w i t hb a s ea l g o r i t h mf o rc o m p a r i s o n r e s u l t ss h o wt h a to r d e rp r e d i c a t e m a t c h i n ga l g o r i t h md e m o n s t r a t e sav e r yg o o de v e n tm a t c h i n ge f f i c i e n c y , a n dag o o d i m p r o v e m e n ti ns y s t e mp e r f o r m a n c e 浙江火学硕l ：学位论文 a b s t r a c t i nt h ef o n l lp a r t w ep r o p o s eas c a l a b l ea n dc o n f i g u r a b l es t a t e f u l p u b l i s h s u b s c r i b es y s t e ma r c h i t e c t u r e t h ep r o t o t y p e s y s t e mm a i n l yi n c l u d e sm a t c h i n g m a n a g e r , s u b s c r i p t i o nm a n a g e r , e v e n tm a n a g e r , a n dn o t i f ym a n a g e r b ye a c hm o d u l e s e x p a n s i o ns t r a t e g y , m e t a - s e r v i c em a n a g e m e n ta n dc o n f i g u r a t i o nm a n a g e m e n t ，w e m a k et h es y s t e me x t e n s i b l ea n dc o n f i g u r a b l e f i n a l l y , w ei n t r o d u c et h es t a t e f u lp u b l i s h s u b s c r i b ep r o t o t y p es y s t e m k e y w o r d s ：s t a t e f u lp u b l i s h s u b s c r i b es y s t e m s ，c o m p o s i t ee v e n t ，a u t o m a t a , d a t am o d e l ， e v e n tm a t c h i n g ，p r e d i c a t ei n f e r e n c e v 浙江人学硕i ：学位论文 图目录 图目录 图2 1 发布订阅系统的概念模型6 图3 1 股票事件类型规范2 1 图3 2x m l 格式订阅例子2 4 图3 3 订阅实例图2 8 图3 4 代数表达式对应的解析数结构2 9 图3 5 自动机实例图3 0 图4 1 订阅处理过程图3 3 图4 2 自动机实例更新图3 4 图4 3 谓词关系表数据结构。3 7 图4 4 关系谓词匹配算法处理示意图4 0 图4 5 订阅规模与算法匹配效率的关系图4 5 图4 6 事件属性数量与算法匹配效率的关系图4 5 图4 7 订阅长度与算法匹配效率的关系图4 6 图4 8 自动机边上谓词数量与算法匹配效率的关系图4 7 图4 9 事件属性分布与算法匹配效率的关系图4 8 图5 1 系统概念体系结构5 2 图5 2 有状态发布订阅系统的体系结构5 4 图5 3 支持查询语言订阅元服务管理器结构图。5 5 图5 4 有状态发布订阅系统内核体系结构图5 6 图5 5 匹配管理组件交互及处理流程图5 6 图5 6 订阅管理组件交互及处理流程图5 7 图5 7 自动机实例和事件的类结构图5 9 图5 8 自动机实例对象回收5 9 图5 9 共享数据对象的分代收集机制6 0 图5 1 0 订阅注册与处理时序图6 2 图5 1 1 事件发布与处理时序图6 3 图5 1 2 复合事件匹配时序图6 4 图5 1 3 复合事件匹配情景图6 4 图5 1 4 复合事件满足订阅的情景图6 5 浙江人学硕1 ：学位论文 表目录 表目录 表3 1 一个事件序列的例子3 0 表3 2 一个自动机处理事件的例子3 1 表4 1 实验影响因素设计4 4 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝姿盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字同期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权滥婆盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签名： 签字同期：年月日签字同期：年月同 浙江人学硕j ：学位论义第1 幸绪论 第1 章绪论 1 1 课题背景 随着网络、通信技术和i n t e m e t 的飞速发展，计算技术已进入分布式计算时 代。传统的网络计算把服务和数据看作一组静态的对象和数据集，以请求应答 ( r e q u e s t r e p l y ) 的方式处理信息交互，产生了基于r p c ( r e m o t ep r o c e d u r ec a l l ) 的中 间件u 和面向对象的中间件技术f 2 1 。由于请求应答通讯机制具有同步、紧耦合的 特点，使得该机制对网络的稳定性要求非常高，而且系统的性能严重受制于服务 器的工作效率，削弱了系统的扩展能力。为了适应复杂动念的网络环境，人们在 紧耦合的通讯机制上进行改进，提出异步的通讯方法，引入了某种间接的、减祸 的交互形式。比如单向调用( o n e w a y ) f 3 1 、回调( c a l l b a c k ) 【4 】、句柄( h a n d l e ) 【5 1 、异步 远程调用1 6 j 等。 然而，随着移动设备和宽带的普及，软件系统的主要形态、运行方式、生产 方式和使用方式发生巨大的变化，网络计算的复杂度越来越高。新一代的网络计 算将是以大规模、分散控制、动态性、自治性和松耦合为主要特征的分布式计算 阴。为适应复杂大规模的网络计算，一种与请求应答完全不同的异步通讯机制应 运而生，即发布订阅( p u b l i s h s u b s c r i b e ) 通讯模型。 发布订阅系统是由信息生产者( 发布者) 、信息消费者( 订阅者) 和事件代理组 成的基础中间件，发布者以“事件”形式发布信息到事件代理，订阅者向事件代 理订阅感兴趣的事件，事件代理把发布的事件及时可靠地路由给感兴趣的订阅。 该平台具有松耦合、匿名、多对多通信的特点，广泛应用在面向服务的架构、普 适计算等新型网络计算领域。 有状态发布订阅系统是在普通发布订阅系统基础上，实现了复合事件检测 的发布订阅系统。它不仅支持对单个事件的订阅，也支持对复合事件的订阅。这 样可以高效的处理复杂的事件，从而改善系统的性能，具有重要的应用价值与研 究意义。 浙江人学硕i j 学位论义第1 章绪论 现有的发布订阅系统，如h e n n e s 【8 1 、g r y p h o n l 9 1 ，只提供了原子事件订阅匹 配功能，这些系统都缺少支持复合事件订阅的语言，复合订阅需求只能由上层的 开发人员来完成；也有一些发布订阅系统，如s i e n a l l0 1 、r e b e c a l l 、p a d r e s l l 2 】 等，提供了对复合事件订阅的支持。但s i e n a 只能表达事件的顺序发生关系，且 实现的扩展性不强，严重限制了其应用领域。r e b e c a 支持事件之间的“与、或、 非”逻辑关系，并可以检测多个相同事件的发生，在实现上通过事件、条件、行 为( e v e n t c o n d i t i o n a c t i o n ，e c a ) 规则来检测复合事件，其中通过滑动窗口来 确定哪些事件是有效事件。p a d r e s 支持对与、或、顺序发生、重复发生四种事 件关系上的复合订阅，在实现上是将复合订阅映射到j e s s i m 】可以识别的规则， 然后利用j e s s 推理引擎完成复合订阅的检测。另外，主动数据库领域的一些研 究工作【1 5 , 1 6 , 1 7 , 1 9 】也涉及复合事件匹配。 现有的有状态发布订阅系统在表达能力、事件处理效率和系统扩展型等方面 尚存在较大的改进空间，不足以支持大规模的i n t e m e t 计算环境。要使有状态发 布订阅系统真正成为在i n t e m e t 环境下，高效、通用、可靠的分布式计算基础设 施，还有许多关键技术问题有待于解决。 1 2 研究意义 有状态发布订阅系统不仅支持对单个事件的订阅，也支持对复合事件的订 阅，极大的提高了发布订阅系统的表达能力。例如，订阅某支股票半小时内涨了 5 。普通发布订阅系统不支持复合事件的检测，用户实际上并不对股票上涨的 单个事件感兴趣，但为检测整个复合事件，他不得不订阅它，这无疑浪费了用户 的带宽，并造成事件的订阅数过多给系统带来很大的负担，使系统的性能下降。 而有状态发布订阅系统具备了检测复合事件的能力，挺高了系统的表达能力和灵 活性，节省了带宽和系统资源。 有状态发布订阅系统可以应用到股票交易、网络管理、智能交通、指挥决策 等领域。随着空间信息的广泛应用，在远程监控和移动位置服务( l o c a t i o nb a s e d s e r v i c e ，l b s ) 等领域，也需要实现与空间有关的复合事件检测。 2 浙江人学硕l ：学位论文第1 章绪论 一网络管理 网络管理需要对网络资源进行监视、测试、配置、分析、评价和控制，它具 有五大功能：故障管理、计费管理、配置管理、性能管理和安全管理。利用有状 态发布订阅系统可以使复合事件的检测以松耦合的方式进行，提高网络管理的性 能。 智能交通 智能交通是一个基于现代电子信息技术面向交通运输的服务系统。它的突出 特点是以信息的收集、处理、发布、交换、分析、利用为主线，为交通参与者提 供多样性的服务。有状态发布订阅系统非常适合做道路流量规律获取、多条道路 流量比较等。 l b s l b s 是通过电信移动运营商的网络( 如g s m 网、c d m a 网) 获取移动终端用 户的位置信息，在电子地图平台的支持下，为用户提供与位置相关的各类信息服 务。例如检测某个位置方圆1 公里内既有电影院，又有图书馆。在移动计算中， 计算节点的移动导致网络拓扑动念地变化。动态变化的网络拓扑使得移动系统不 得不面对系统的重配置，因此采取集中控制和同步通信手段几乎不太现实。有状 态发布订阅系统能够很好的解决移动计算和复合事件检测问题： 1 3 论文工作 结合国家8 6 3 课题、国家自然科学基金课题，本文的研究工作是围绕基于内 容的有状念发布订阅系统的以下关键技术展开研究： 1 ) 数据模型 传统的发布订阅系统中，各参与者所发布的事件都是同一结构。为了是发布 事件在语义和结构上具有异构性，需要有新型的、可扩展性好的数据模型，使系 统表达能力更强。而且复合事件模型需要支持多个单一事件或者复合事件的触发 关系，此外，还需要有不同于普通发布订阅系统的时间模型和观察模型。 2 ) 匹配算法 浙江人学硕t - 学位论文第l 幸绪论 高效的匹配算法是调和系统丰富表达能力和可扩展性矛盾的关键。匹配算法 与数据模型密切相关，而数据模型的表达能力和匹配算法的效率是一对矛盾的事 务。一般说来，表达能力却强，匹配效率越低。在大规模的发布订阅系统中，系 统需要处理大量的事件匹配。如果事件和订阅逐一比较，则效率太低，难以满足 大规模发布订阅系统的要求。因此，有状念发布订阅系统必要要有一种高效的 匹配算法，在短时间内找到受事件影响的所有订阅，以胜任繁重的工作负荷。 3 ) 体系结构 面向不同应用领域的发布订阅系统的概念模型虽然一致，但体系结构各不相 同。因此，需要针对不同计算环境的特点，解决订阅模型、事件模型等的扩展问 题，解决适应不同应用程序需求的服务模块的管理问题，解决不同计算环境下的 异构协议问题。 1 4 论文组织 基于内容的有状态发布订阅系统中间件具有广阔的应用前景，本文从中间件 的基本概念入手，阐述了有状态发布订阅系统的相关概念，研究了前人提出的数 据模型、匹配算法和体系结构，在此基础上对数据模型进行了改进，提出了基于 谓词推导关系和谓词判断顺序的有序谓词匹配算法，并用实验证明了该算法的正 确性，可行性和高效性。最后，介绍了系统的体系结构和原型系统实例。本文组 织如下： 第一章：绪论，介绍了本课题的研究背景和意义，以及论文研究的主要工作， 最后说明了本文的组织结构。 第二章：发布订阅系统相关研究，主要介绍了当前发布订阅系统的研究情 况和热点，包括发布订阅系统概念模型、拓扑结构、数掘模型、匹配算法和路由 算法等方面，并分析了现有方法的优缺点。还讨论了有状态发布订阅系统的相关 技术、当前研究进展和存在的不足。 第三章：有状态发布订阅系统的的数据模型。先对传统的支持复合事件的系 统数据模型进行了分析，比较它们的优缺点。然后从复合事件模型和订阅模型两 4 浙江人学预1 ：学位论文 第1 章绪论 个方面介绍了有状念发布订阅系统的数据模型，复合事件模型包括复合事件模式 和时间模型，订阅模型包括订阅语言和观察模型。复合事件模式描述多个单一事 件或者复合事件的触发关系。时间模型描述多个事件之间时间序列上的关系。订 阅语言用于描述订阅者感兴趣的复合事件，该订阅语言是一种类似s q l 的查询语 言。为了更好的介绍订阅语言，我们还对订阅操作进行了形式化的描述。观察模 型检测感兴趣的事件，本文采用了一种扩展的非确定型有限自动机。 第四章：有状态发布订阅系统的匹配算法。我们先介绍了整个复合事件匹配 过程，包括特点和实现难点。然后，我们提出了一种流水线事件处理过程，以多 线程的方式使匹配过程流水处理，从宏观上改进了复合事件检测算法。接下来， 提出了关系谓词匹配算法和有序谓词匹配算法。最后，我们对关系谓词匹配算法 和有序谓词匹配算法进行了实验测试，并与一种基础的算法进行比较。实验结果 表明，有序谓词匹配算法体现出了很好的事件处理效率，很好的改善了系统性能。 第五章：可扩展和可配置的有状态发布订阅系统的体系结构设计。该原型系 统主要包括匹配管理器、订阅管理器、事件管理器和发布管理器。通过对各个模 块的扩展支持，以及配黄管理和元服务管理的设计，使得系统可扩展和可配置。 还介绍了有状态发布订阅系统的几个主要处理流程，以及原型系统的实例。 第六章：总结和展望，总结了本论文所做的工作以及研究创新点，并且展望 了下一步将要努力的方向。 浙江人学硕1 ：学位论文 第2 章发布订阅系统概述 第2 章发布订阅系统概述 发布订阅系统是一种各参与者以“发布订阅”的方式进行异步通信的中间 件系统。本章首先介绍了发布订阅系统的概念模型，然后介绍数据模型、匹配算 法、系统拓扑结构和路由算法等关键技术的国内外研究现状。最后分析了有状态 发布订阅系统的挑战与研究热点。 2 1 发布订阅概念模型 发布订阅系统是一种使分布式系统各参与者以“发布订阅”的方式进行异 步通信的中间件系统。发布订阅通信范型在时间、空间和控制流三个方面都完全 解耦，支持匿名通信、多对一通信和可扩展性。在发布订阅系统中，信息的生产 者和消费者之间以“事件 为载体进行信息交互。生产者将“事件”发送给某个 接入的事件代理( e v e n tb r o k e r ) ；消费者则向事件代理发出一个“订阅条件”，表示 对系统中的哪些事件感兴趣：而事件代理则保证将所发布的事件及时、可靠地传 送给对之感兴趣的信息消费者。信息的生产者称为发布者( p u b l i s h e r ) ，信息的消费 者称为订阅者( s u b s c r i b e r ) ，发布者和订阅者统称为客p ( c l i e n t ) 。发布订阅系统的 概念模型如图2 1 所示。 图2 1 发布订阅系统的概念模型 发布订阅系统主要的特点有如下四点： 1 ) 松耦合性。具体体现在：在空间上，信息生产者和消费者都不知道对方 地址；在时间上，生产者和消费者不需要同时在线。在控制流上，生产 6 浙江人学硕j ：学位论文第2 章发布订阅系统概述 者和消费者都以非阻塞方式处理信息。 2 ) 可扩展性。在系统本身不做任何改动的情况下，新的客户可以很方便地 加入系统中。 3 ) 匿名性。信息生产者和消费者互相不需要向对方暴露自己的身份信息。 4 ) 多对一通信。一个事件可以同时被发送到多个信息消费者，多个事件也 可以同时被发送到同一个信息消费者。 发布订阅系统作为一种通用的分布式计算基础设施，它的设计目标是实现一 个高效、表达能力强和可靠性高的系统。为了达到这些目标，发布订阅系统需要 关注的关键技术包括：匹配算法、数据模型、系统拓扑结构和路由算法。 2 2 发布订阅数据模型 数据模型包括事件模型和订阅模型。事件模型定义事件内容的数据结构，订 阅模型指定订阅的表达和过滤方式。数据模型决定了发布订阅系统的表达能力。 在发布订阅系统的发展过程中，出现了多种数据模型，其表达能力越来越强。经 过多年的研究，现有的发布订阅系统数据模型主要有基于主题的系统、基于m a p 的系统和基于x m l 的系统三大类。基于m a p 的系统和基于x m l 的系统又被统 称为基于内容的系统。此外，还有其它一些具有特定数据模型的发布订阅系统。 事件模型有元组、记录、对象等模型，订阅模型有基于渠道的、基于主题的、基 于类型( 对象) 的、基于内容的和混合型等模型。基于内容的订阅模型又可分为基 于“名字值”对属性、基于x p a t h 2 4 】两类。 2 2 1 事件模型 事件模型决定了发布事件的语义和语法。它是发布信息的载体，定义了如何 对发布信息进行编码。常见的事件模型主要有三类：元组模型、记录模型和对象 模型。 基于元组的事件模型：事件被表达为一组有序的字符串属性，每个属性没有 指明类型，其意义和类型必须事先规定好。比如一个股票报价信息事件 7 浙江火学硕i ：学位论文第2 章发布川蒯系统概述 ( s t o c k q u o t e ，“i b m 9 9 95 0 2 ) 指出一只具体的股票“i b m ”，报价为5 0 2 。元组模型 的优点是简单高效，只需根据“属性位置”进行匹配。缺点是结构单一，不能任 意选择属性或改变属性位置。一些发布订阅系统是基于元组的事件模型，如 j e d i l 2 u 将通知建模为字符串元组，其中第一个字符串代表通知名字，其它字符串 代表正常的属性。 记录模型又分为两类：结构化记录( s t r u c t u r e dr e c o r d ) 和半结构化记录 f s e m i s t r u c t u r e dr e c o r d ) 。在结构化记录模型中，事件被表示成个包含多个“名字 值”对的集合，集合中的每个属性名是唯一的，并具有一定的类型，如字符串、 整形等。结构化记录模型是上面提到的基于m a p 发布订阅系统的事件模型。结 构化记录模型和元组模型比较类似，但其匹配是根据属性名而非属性位置，因此 具有更大的灵活性。在半结构化记录模型中，事件是一个定义格式良好的x m l 文档。与结构化记录不同，半结构化记录中的属性名不必唯一，并且具有树状结 构，因此具有更强的表达能力。 对象模型把事件表达为一个对象，每个事件对象封装了描述事件内容的属 性，并提供设置和提取属性的方法。由于引入了面向对象技术，这种模型具有面 向对象技术的封装、继承和多态性优点。 2 2 2 订阅模型 订阅模型是指订阅者订阅感兴趣事件的模型。订阅模型对于系统的表达能力 和可扩展性有直接的影响，对于基于内容的发布订阅系统来说是一个挑战。不同 类型的发布订阅系统，所对应的订阅模型也具有不同的表达方式和开销。订阅模 型有基于渠道的、基于主题的、基于类型的、基于内容的和混合型等模型。 基于渠道的订阅模型( c h a n n e l b a s e d ) 在基于渠道的订阅模型中，发布者把事件发布到一个指定的渠道，订阅者根 据渠道的名字订阅渠道内的所有事件。由于订阅者不能对渠道内的事件做选择， 因此事件的接收与事件的内容是无关的【2 。这种模型实现简单，表达能力很弱， 主要应用于早期的发布瑚阅