发布订阅系统中Carzaniga匹配算法优化

张 颖，高申勇，曾 虹

（1.浙江水利水电专科学校计算机与信息工程系，浙江 杭州310018；2.杭州电子科技大学计算机学院，浙江 杭州310018）

0 引 言

随着网络快速发展，生活当中出现越来越多的分布式计算环境，传统的客户/服务器模式难以适应这种环境。发布/订阅系统是一种基于事件的通信范型，具有异步、多点通信等优点，可广泛应用分布式计算及移动环境［1］。因此近年来，发布/订阅系统成为研究热点，特别是基于内容的发布订阅系统，典型系统如SIENA［2］等。其中，系统中必须解决事件与订阅间高效匹配问题，匹配算法的性能直接影响到系统性能。匹配算法分为两类：基于计数法和基于搜索树匹配［3］。目前算法都未能解决订阅与事件重复匹配问题，如主流算法Carzaniga［4］只支持订阅覆盖，没有考虑多个订阅可能存在谓词间的覆盖关系，引发较严重重复匹配，从而影响匹配效率，导致系统整体性能低。针对上述问题，本文提出改进算法，它能同时支持订阅覆盖和谓词覆盖，实验表明与Carzaniga相比，本算法能进一步减少重复匹配，提高匹配效率，也提高系统整体性能，更适合应用于大规模的发布订阅系统。

1 PPSMTBOAD算法描述

已有的较有影响的原型系统SIENA采用Carzaniga算法，它利用订阅间的覆盖关系以及合并订阅思想，减少和事件进行匹配的订阅数目。算法的基础思想如下，以树结构组织所有订阅，以覆盖与被覆盖方式组织树中的结点。事件e从树的根结点向下逐级匹配，当且仅当e通过所有的中间结点到达叶结点时匹配结束，被匹配到的订阅条件就是叶结点所指代的订阅条件。

但是Carzaniga算法［5］仅考虑订阅间的覆盖关系，没有考虑多个订阅可能存在相同谓词及谓词间的覆盖关系，若相同谓词被多次存储和判定，将产生时间和空间上的冗余。在其基础上，充分吸收覆盖思想，提出一种改进算法，称为基于属性划分的并行谓词集匹配树算法（Parallel Predicate Set Matching Tree Based on Attribute Division，PPSMTBOAD）。

PPSMTBOAD算法结合基于计数法和基于搜索树匹配策略，充分兼顾多个订阅间可能存在相同谓词和谓词间覆盖关系，并且通过构造多个并行谓词集匹配树加速匹配，以及利用谓词间的覆盖关系减少不必要重复匹配进行优化。

1.1 订阅语言和事件模型

设计合理的事件模型和订阅语言能降低系统的事件匹配复杂度，提高系统性能。本算法采用的策略是：发布者通过事件模型发布事件，订阅同时支持合取和析取操作。

（1）谓词或约束：谓词是一个含有命名变元的命题，4个命名变元为（type，attribute，operator，value）的四元组。

（2）过滤：Filterp=constraintp，q谓词合取关系的复合命题。

（3）订阅：subscriptioni=Filteri，p过滤上使用析取关系的复合命题，表明有一个过滤为真，该订阅就为真。

（4）事件或通知：事件是发布者发送到发布/订阅系统的具体信息，事件采用属性集合来描述，Notifications=attributes，t，attributet=（typeα，nameα，valueα）。

1.2 匹配和覆盖规则

规则 1 如果属性α=（typeα，nameα，valueα）与属性β=（typeβ，nameβ，operatorβ，valueβ）约束之间满足（typeα=typeβ）∧（nameα=nameβ）∧（operatorβ=valueβ）⇒（operatorα=valueα），则称约束β包含属性α，或记为α＜β。

规则 2 判定约束β1和β2具有覆盖关系则β1和β2必须满足（typeβ1=typeβ2）∧（nameβ1=nameβ2）∧（operatorβ1=valueβ1）⇒（operatorβ2=valueβ2），则称β1覆盖β2，或记为β2＜β1。

规则3 如果对于订阅中的每个属性约束φ，事件中至少存在一个属性α，使得α＜φ，则称事件与订阅匹配，记为 n＜s⇔∀β∈s：∃α∈n：α＜β。

1.3 算法数据结构

算法数据结构如图1所示，首先处理订阅集，将订阅分解为谓词集合，剔除重复谓词，将谓词按照属性名分为若干个谓词集，利用规则2，即以覆盖与被覆盖方式组织树中的结点、前驱结点后继结点组建多个匹配树，结点代表谓词，称为谓词集匹配树。从覆盖范围最广的第一级谓词结点开始匹配，采用深度优先搜索逐级往下级匹配，当某一级谓词不满足匹配，表明从该级直至最后一级谓词都不满足匹配，因此立即停止匹配。

给定事件e，根据属性名快速定位，并从根结点开始查找满足匹配的谓词，如事件与某个谓词集匹配树中的谓词不匹配，则该谓词以后直至谓词集匹配树的叶子结点都不满足该事件，无需再逐个进行比较。另外，在谓词集匹配树中，为了保持谓词和订阅之间的隶属关系，采用了谓词-订阅者的链表结构，每个谓词指向一个链表结构，该链表存储了所有包含该谓词的订阅者标识，为了区别同一订阅者的不同订阅消息，又建立了订阅者-订阅消息的链表结构，存储了订阅消息标识符。

为了将匹配谓词集求交集，建立了一个谓词集匹配表，如图2所示，以属性名作为键，存储每个成功匹配谓词所包含订阅者标识和订阅消息标识。当一个订阅条件所有的谓词都匹配时，说明该订阅匹配成功。

1.4 算法步骤

描述PPSMT算法。为了形式化描述该算法，定义如下符号：保存与事件中的某个三元组匹配的谓词标识matching-predicater（cj.sk）；保存与某事件匹配的订阅标识matching-subscriptionr（cj.sk）：

图1 谓词集并行匹配树结构

图2 谓词集匹配表

（1）以单个三元组 attributet=（typet，α，namet，α，valuet，α）为匹配单位，并行遍历谓词集匹配树，遍历至某个谓词时，三元组与之进行匹配，若满足规则1匹配成功，保存谓词标识cj.sk至matching-predicater（cj.sk），若存在与之不匹配的谓词，不继续进行匹配，匹配结束。之后判断matching-predicater（cj.sk）是否为空，如果为空，即不存在与事件相匹配的订阅，算法结束，go to Step3；

（2）对所有matching-predicater（cj.sk）链表中的元素求交集，保存结果至匹配集matching-subscriptionr（cj.sk），该结果集就是与事件匹配的订阅；

（3）算法结束。

2 算法性能

在一台CPU为Intel Pentium IV 3.00 GHz，内存为1.00GB普通台式电脑上，对SINEA原型系统进行了模拟实验。SINEA是科罗拉多大学一个开放源码基于内容的分布式发布订阅系统，提供了标准的publish、subscribe和unsubscribe API等接口，具有良好的性能。实验结果中的每个数据点都是以同样的参数运行了15次求得的平均值。实验中包括一个数据产生器，按照自动配置产生相应的事件与订阅，产生规则如下：

（1）属性类型，使用四种基本数据类型Int、Float、String、Bool；其中Int类型占40%，其余各占20%；

（2）属性名称，定义一个长度为n的字符数组，称为属性名表，表中的每个字符是从24个英文字母表中随机选取5个字母组成，属性名是从属性名表中随机选取；

（3）操作符，包括＞，＜，=，!，"5种操作符，在测试中的比例各占20%；

（4）属性值，对于Int/Float类型，在0-1 000之间取值；对于String类型，从属性名表随机选取；对于Bool类型，随机取“真”或“假”。

本实验将比较最原始基于计数法的匹配算法Naive、Carzaniga算法和PPSMTBOAD算法，从以下方面来进行比较。属性取值范围对匹配时间的影响：取属性表的长度变化范围为50～500，对每个属性表随机生成5 000个订阅，各订阅的谓词个数在515平均分配，测得的匹配计算耗时如图3所示。订阅数量对算法匹配时间的影响：生成一个长度为600的属性表，随机生成包含25个属性的事件，随机生成若干组订阅，订阅个数的变化范围为1 000～100 000，各订阅的谓词个数在5～20平均分配，测得的匹配计算耗时如图4所示。

图3 不同属性取值范围的匹配时间

图4 不同订阅数量的匹配时间

由图3可知，属性取值范围变化对Naive基本没有影响，对Carzaniga算法，由于它支持订阅覆盖，当属性种类越多，取值范围扩大，那么覆盖范围越分散，匹配效率有所提高。PPSMTBOAD除支持订阅覆盖，还支持谓词覆盖，划分并行谓词集匹配树可减少搜索树的节点数，降低对存储空间的需求，并潜在地缩短事件匹配时间，尤其适合于节点分支数多而匹配分支少时的情况，当属性种类越多，谓词集匹配树越多，覆盖范围更加分散，进一步减少了重复匹配提高，匹配效率显著提高。由图4可知，随着订阅数量增加，本算法的降幅小于其他两种算法，系统可扩展性提高，更适合应用于大规模的发布订阅系统。

3 结束语

在Carzaniga算法基础上提出了PPSMTBOAD，建立了订阅模型和事件模型，定义了匹配和覆盖规则，该算法充分挖掘谓词间的覆盖关系，同时支持订阅和谓词覆盖，进一步减少了重复匹配。在基于SINEA的原型系统进行了模拟实验，结果表明，与Carzaniga算法相比，该算法的匹配效率有了一定的提高。

［1］ Carzaniga A，Wolf A L.Design and Evaluation of a Wide-Area Event Notification Service［J］.ACM Transaction on Computer Systems，2001，19（3）：332-383.

［2］ Eugster PT，Felber PA，Guerraoui R，et al.The Many Faces of Publish/Subscribe［J］.ACM Computing Surveys，2003，35（2）：114-213.

［3］ 马建刚，黄涛.面向大规模分布式计算发布订阅系统核心技术［J］.软件学报，2006，17（1）：134-147.

［4］ Carzaniga A，Wolf A L.Design and Evaluation of aWide2Ar2ea Event Notification Service［J］.ACM Trans on Computer Systems，2001，19（3）：322-383.

［5］ 苑洪亮.基于内容的“发布/订阅”若干关键技术研究［D］.长沙：国防科学技术大学，2006.