发布/订阅中间件中基于过滤器的信息选择机制

◆谷晓鹏 张凡石 王 叶



发布/订阅中间件中基于过滤器的信息选择机制

◆谷晓鹏1张凡石2王 叶1

（1.海军指挥所 北京 100841；2.中国电科集团28所 江苏 210007）

发布订阅中间件因其松耦合的特性得到广泛的关注和应用。在某些应用场景中订阅方仅对所订阅主题中的部分信息感兴趣，因此需要提供信息选择机制以满足这种应用需求。本文提出了一种发布订阅中间件中基于过滤器的信息选择机制，并在发布订阅中间件原型系统中实现了该机制。该机制遵循OMG DDS规范，采用Flex&Bison工具生成编译器，将遵循类SQL语法的订阅表达式解析生成过滤语法树，通过对接收数据的解析和对过滤语法树的遍历作出是否过滤接收数据的决定。对原型系统的测试验证了该信息选择机制的正确性和合理性。

信息过滤；发布订阅中间件；数据分发服务；过滤器

0 引言

发布订阅系统是一种以发布订阅机制实现参与者之间交互的分布式系统，该系统参与者之间松耦合的特性正使其获得越来越多的关注[1]。在发布订阅机制中，订阅者专注于获取信息，发布者专注于发布信息，系统通过一定的方法完成相互的匹配，从而进行信息传输。这样的处理方式使得发布者和订阅者在时间、空间、同步方面实现了解耦，大大增加相关应用程序的灵活性和可扩展性[2,3]。OMG组织制定了实时系统数据分发服务规范（Data Distribution Service for Real-time Systems, DDS），已成为信息分发发布订阅系统的工业标准， RTI DDS等业界领先的发布订阅系统均遵循该规范[4,5,6,7]。

在基于主题的发布订阅系统的实际应用中，订阅者往往只对该主题下的部分信息感兴趣，如何使得这些订阅者更好，更快地“捕捉到”自己感兴趣的信息就成为了发布订阅中间件系统提高服务质量的一大重点。例如：一个股票信息集成管理系统中发布和订阅的信息为股票名称及其价格，而订阅者往往只关心某几只股票的情况。如果不加过滤地将全部几千只股票的信息全部提交给用户，那么无关信息将占用用户大量的处理时间，因此发布订阅中间件需要向用户提供信息过滤的功能。OMG DDS规范中提出了ContentFilteredTopic机制以提供该功能[2]，目前主要的发布订阅中间件产品中均实现了这种功能[4,5]。本文在现有信息集成管理软件（基于OMG DDS规范的发布订阅原型系统）的基础上，遵循OMG DDS规范中ContentFilteredTopic机制的相关接口，通过应用Flex&Bison等工具构建过滤语法树，并与信息发布订阅处理流程相集成实现了信息过滤功能。

1 过滤规则语法定义

过滤规则也称为订阅表达式，用于描述对信息相关数据的要求，表示用户的“兴趣”。OMG DDS规范中采用类SQL语法作为其语法定义。类SQL语法具体是指SQL语句中where从句部分的语法，该从句用于描述所查询数据应满足的条件[2,6]。

该语法所支持的条件表达式有：

1.简单比较运算

用于比较主题信息中某个字段的值是否等于（不等于、大于、小于）某个设定值，或者落在某个设定的取值区间，例如：key=10，key>20，key between 10 and 20等。

2.复杂逻辑运算

对简单比较运算表达式的与、或、非操作。例如：key<10 and key>20。

理论上该语法可以描述足够复杂的订阅表达式。

除OMG DDS规范定义的语法规则外，本文还加入了支持字符串型数据模糊过滤的strlike运算符，该运算符根据编辑距离的概念（即将一个字符串修改为另一个字符串所需改动的字符个数），判断两个字符串是否相似。

2 基于过滤器的信息选择机制

2.1 信息选择机制的框架

图1 信息选择机制框架图

图1所示为信息选择机制的框架和处理流程，其核心部分为过滤规则编译器和过滤器。

过滤规则编译器由通用的编译器生成工具Flex&Bison离线生成。以过滤规则语法及其对应的动作代码为输入，生成过滤规则编译器源代码，该源代码连编到发布订阅中间件系统库文件中，供发布订阅系统运行过程中在线使用[8]。

其中，动作代码是指当生成的编译器发现其输入满足某条语法规则时需要执行的相应语句，在本文中，用户的订阅表达式通过编译器被表示成相应的过滤语法树，因此，此处的动作代码对应着过滤语法树中相应节点的添加[8]。

当订阅者想要订阅相关主题信息时，首先需要向系统注册，此时，订阅者应提供订阅表达式（过滤规则）以表示其订阅兴趣，过滤规则编译器接受该输入编译生成相应的过滤语法树。

在数据发布订阅阶段，当订阅端接收到发布者发布的数据时，订阅者的过滤器将获取该数据，并根据该数据中各分量的值遍历过滤语法树，计算出当前数据是否应该过滤，如需要过滤则丢弃，否则向上提交给用户。

2.2 过滤语法树的生成

文中选择树形数据结构作为订阅表达式的表示方式，该结构能够比较直观地表达订阅表达式各部分之间的逻辑关系，并且便于过滤计算过程中的使用，例如：对于股票信息订阅表达式StockCode=AAPL（苹果股票） OR StockCode=MSFT（微软股票）解析过程如图2所示。当过滤规则编译器对一个满足规约条件的表达式进行规约时，会生成和这个表达式对应的语法树，图2中首先是对于子式StockCode=AAPL进行规约，然后是对子式StockCode=MSFT进行规约，完成前面两个规约之后，此时满足了OR连词表达式的规约条件，通过规约的相应动作将刚才生成的两棵子树以OR操作符对应的节点为根节点，形成一棵新的语法树。

图 2a StockCode=AAPL

图2b StockCode=MSFT

图2 StockCode=AAPLOR StockCode=MSFT对应树形结构示意图

编译器生成过程中所需要的动作代码[7]就是基于Flex&Bison提供的规则规约处理机制，在相关语法规则之后添加当输入满足该规则进行规约时需要进行的处理。以图2a为例，子式StockCode=AAPL对应的规则的动作代码就是图2a中树节点的声明以及节点间关系建立。

2.3 发布订阅过程的过滤计算

过滤计算是过滤器根据过滤语法树，提取出数据中与规则相关的数据分量，根据规则的逻辑关系进行计算以判断对于该数据的取舍。

在语义树中主要存在三类与数据有关的节点：（1）确定值对应的节点。该类节点是由用户定义规则中明确的数值经过编译生成的，数据的类型以及值的信息均存储于节点结构中。（2）参数对应的节点，该类节点由输入规则中‘%n’形式表示的参数编译生成，其中n表示该参数对应参数值在参数存储队列中的索引位置,在过滤计算过程中根据索引信息查询到对应数值，参数的设计主要是为了提供过滤的灵活性，通过修改参数值就可以影响过滤的结果，不必重构过滤表达式。（3）变量对应的节点，该类节点需要过滤器在原始数据中查询到变量对应的实际值。

过滤计算过程中，首先将数据相应分量的值代入到过滤语法树中相应节点，然后对过滤语法树进行自叶节点向根的遍历计算，遍历完整棵树后的计算结果即表示是否过滤。

如图3所示，当到达的数据中StockCode变量的实际值为IBM（IBM股票代码）时，图2中过滤语法树中StockCode节点的值被替换成IBM，过滤计算最终结果为False，表示这个数据不符合订阅表达式，将会被过滤掉。

图3 过滤计算过程示意图

不同类型的发布订阅系统，过滤器的调用方式也不相同。对于有信息代理的集中式发布订阅系统，由信息代理进行信息的过滤，因为代理计算功能相对较强而且相关资源（计算能力，内存）等也比较充裕，同时提高端点（发布端，订阅端）的运行效率。对于纯分布式的系统，采用在订阅端过滤，考虑到发布端计算任务相对繁重（信息的产生以及发布），资源相对较少（用于信息存储等），所以采取订阅端过滤的方式，在订阅者网络层接收到数据，解析线程进行解析时过滤。但是，在某些特殊情况下，发布端过滤会有更好地收益，因为发布端过滤可以减少网络上的数据个数，节约带宽资源，当网络带宽资源相对较紧缺时，或者大部分订阅端有相同的订阅表达式时，可以考虑采用发布端过滤，而且发布端过滤没有必要将表示数据结构的typecode传递到订阅端。

3 实验结果及分析

对过滤功能实现的相关功能测试显示，该实现遵循OMG DDS规范，能够满足对于信息过滤的需求且具备较好的错误处理能力。为进一步验证实现方案的合理性，本文主要针对发布订阅中间件系统的两个主要性能指标：处理时延和数据吞吐量进行性能测试。过滤器中对影响相关指标的因素主要是过滤计算的处理时间，该处理时间受过滤规则复杂度和相关数据查询时间影响。过滤规则复杂度越高时，遍历语法树所需时间越长，而数据结构越复杂，查找其中分量对应实际数值所需时间也越长，因此，测试过程中选取简单和复杂两类数据类型，按照无过滤、简单过滤表达式、复杂过滤表达式这三种过滤场景设计测试用例，测试不同用例下的时延和吞吐量。测试用例设计如表1所示。

表 1 性能测试测试用例

图4 时延指标测试结果

时延测试结果如图4所示。由图可知：无过滤情形在所有情形中时延最短，而复杂过滤规则下时延最长；采用相同的过滤表达式时，复杂数据类型的时延高于简单数据类型。测试结果表明：数据类型的复杂性会影响发布订阅系统的时延，但相比而言，订阅表达式的复杂程度对于时延的影响更大。考虑到本文中复杂条件情形下的规则复杂度为简单条件情形下的5倍（以过滤语法树中节点个数计），而时延仅增长15%左右，说明过滤器在过滤规则复杂度明显增加时，具有较好的性能。

在吞吐量测试中，由于数据大小对吞吐量测试结果有一定影响，故将简单数据类型扩充到与复杂数据类型大小一致后再进行测试，经测试该扩充不会造成原始数据获取时间明显增长。测试结果如图5所示。

图5 吞吐量指标测试结果

上图中纵轴数据代表订阅端每秒处理的数据个数（因为数据大小相同，所以用个数来代表吞吐量）。由图5可知：过滤规则的复杂程度及数据类型的复杂程度均会影响发布订阅系统的吞吐量，相比较而言，过滤规则的复杂程度是影响该指标的最主要因素。

4 总结

本文采用Flex&Bison工具，提出了一个发布订阅中间件系统中基于过滤语法树的过滤器实现方案，以实现发布订阅系统中的信息选择机制，并在一个已有的发布订阅中间件原型系统——信息集成管理软件的基础上实现了该方案。测试结果表明该实现方案遵循OMG DDS规范，较好地实现了信息选择机制，其性能也与预期相符。

[1]Patrick TH. Eugster, Pascal A. Felber,Rachid Guerraoui, Anne-Marie Kermarrec, The Many Faces of Publish/Subscribe, ACM Computing Surveys, Vol. 35, No. 2, June 2003, pp. 114–131.

[2]Object Management Group, Data Distribution Service for Real-time Systems Specification,Version1.1, Nov.2005

[3] Object Management Group, The Real-time Publish/Subs cribe Wire Protocol DDS Interoperability Wire Protocol Specification .Version 2.1 2009.

[4] Gerardo P C. OMG Data-Distribution Service (DDS): Architectural Update. 2004 IEEE Military Communications Conference, 2004.

[5] Schneider S, Farabaugh B, Using the DDS Standard for High Reliability Applications. Real-Time Innovations.Inc, 2004.

[6] Real-Time Innovations. The Real-Time Publish/Subsc ribe Middleware User's Manual. Version 4.5C. 2010

[7] Object Computing, Inc. OpenDDS Developer’s Guide. Version 2.3,2007.

[8] Jobn Levine. flex与bison.陆军译.南京：东南大学出版社.2011.

本文受国家自然科学基金项目（60903163）和航空科学基金项目（20101969010）资助。