多事件模式并行CEP处理研究

荆 心，张 璟

（1.西安工业大学 计算机科学与工程学院，西安710021；2.西安理工大学 计算机科学与工程学院，西安710048）

物联网技术的发展，促生了大量的分布式应用，其以事件通知作为系统运行的数据来源，这些数据源将始终持续地发送出海量的原子事件.这些简单的原子事件需要被解释、组合成高级的具有一定抽象含义的复杂事件后才能被高层应用正确理解与使用.此类高层应用以事件驱动为核心，目标在于发现现在正在发生着什么，其与以往的目标在于发现过去发生了什么的基于数据库的应用存在本质差别.由于信息的价值与时效性有较大关系，因此这类应用更具实用价值［1］.基于事件驱动应用的一般架构通常由发生器、接收器、CEP引擎三部分组成［2］.CEP引擎类似人类的大脑，是架构中最复杂、最核心的部分，其负责对原子事件流进行模式识别，发现蕴含其中的因果、时序、逻辑等关系，并产生出新的复杂输出事件.

近期，CEP技术在学术及业界都得到了广泛的关注，以SASE［3］为代表的大量的CEP系统被提出.虽然这些CEP系统已经具备了表达能力强大的规则语言，以及高效的实现模型和优化算法.但是其仍然面临着复杂的问题，即数据源的并行处理与多事件模式的有效共享与关联.目前CEP处理引擎多采用集中处理方式，来自多个数据源的事件流合并后才能进入，引擎随后对每个已注册的事件模式逐一匹配，由此事件流及事件模式均被线性化了.因此CEP引擎的工作方式完全是串行的.而在现实情况下，数据的接收与每个模式匹配的过程都应该是并行的.引擎接收到的事件不应经历排队等待的过程，而应直接路由给对应的事件模式，同样待匹配的模式也不应等待其他模式的完成，而应并行对同一输入进行处理.此外，相互关联或模式相似的多个模式间的有效共享，以及共享后可能存在的冲突问题（即共享节点可同时参与每个父模式的匹配，或一次仅允许参与某一个父模式的匹配，详细见第三小节），在现有的CEP引擎中还未曾提及.仅通过增强规则语言的表达能力是无法解决这些问题的，这是目前CEP引擎面临的最大的挑战.

由此，文中针对以往CEP研究在上述方面的不足，结合文献［4］中Petri网的并行处理能力，对其库所和变迁计算进行了时间扩展（使其能够支持时间窗口及时序检测的要求），综合了有色Petri网的化简能力，提出了一个11元组的复杂事件检测模型CEP-PN（CEP Petri Net），该模型能够实现多数据流的并行接收与处理.给出了该模型可构造的基础网结构，以及由这些网结构构造出事件模式的一般方法.通过Petri网基本性质证明了合并计算网能够得到与独立计算网完全相同的计算结果，并给出了多个事件模式的合并算法.

1 有色Petri网事件检测模型

Petri网是一种直观的图形化并行系统建模工具［5］.由于使用Petri网中的库所表示事件，变迁表示操作符，可以很轻易的构造出事件模式，因此用其对于复杂事件检测进行建模具有天然的优势［6－7］.标准的有色Petri网能实现对大多数操作符的建模，但是还无法对时间约束、选择与消耗策略、非事件等CEP具有的特殊方面进行建模，因此文中对标准网进行了时间扩展，提出了如下的Petri网模型（CEP-PN），用于形式化描述复杂事件的检测过程.

定义1 CEP-PN是一个11元组：CEP-PN＝（P，T，A，C，W ，M，U，G，E，Pin，Pout），且满足以下条件为

① 其中（P，T，A）是一个网，P、T、A分别表示库所、变迁和弧的有限集，且满足下列条件：

P∪T≠Φ∧P∩T＝Φ∧A⊆×T）∪（T×P）；

②C是颜色的一个有限集合C＝｛c1，c2…cn｝，代表事件类型，可包括原子与复合事件类型；

③W：A→L（C）＋，W描述弧上消耗或产生的托肯数和颜色；

M：P→L（C），M描述库所上托肯的颜色及数量，是CEP-PN的标识；

L（C）表示定义在颜色集C上的一个非负整数系数线性函数，L（C）＋表示系数不全为0的L（C），即L（C）＋＝b1c1＋b2c2＋……＋bkck，bi（i＝1，2，…，k）均为非负整数，且b1＋b2＋……＋bk≠0；

④U：P→L（C），表示库所中各托肯的失效时间，U与M 形式相同但作业不同，其中bi为零则表示不失效.M中的ci为托肯颜色，而bi为托肯数量，U与之不同的是ci为托肯颜色，而bi表示时间窗口单元；

⑤G表示守卫函数，描述了事件属性的约束条件，是与输入库所颜色相关的布尔表达式.

⑥E表示变迁操作表达式，描述了如何计算输出事件的属性值.

⑦Pin⊆P，Pout⊆P，且满足Pin≠Φ∧Pout≠Φ∧Pin＝P－Pout∧｛∀∈Pout｜p·＝Φ｝，是网的输入库所与输出库所，除去输入库所外的其他库所均可作为输入库所，其中：p·＝｛t｜t∈P∪T∧（p，t）∈A｝；

⑧ 对t∈T，如果p∈·t→M（p）≥W（p，t）∧G（t）＝ture，那么变迁t在标识M 有发生权（M［t＞），在标识M下发生变迁t，产生一个新的标识 M’（M［t＞ M’）

定义中①～⑦描述了CEP-PN的静态结构，而⑧描述了网运行的动态行为.

2 基本Petri网结构

由于CEP中事件模式的基本构件是事件操作符，因此使用CEP-PN对其进行建模，从而构造出来的基本网结构，可作为构造事件模式Petri计算网实例的原子部件.如果按照操作数的数目对事件操作符进行分类，其可以被自然划分为双操作数与单操作数两类.因此CEP-PN对事件操作符的建模也可分为两类，即双输入变迁与单输入变迁结构（分别如图1（a）～ （b）所示）.基本网的输出可作为另一个基本网的输入，由此可以将基本网关联起来，从而形成目标计算网（如图1（e）所示）.

在图1（a）中，A、B库所上都只有一种颜色，该基本网实现简单，但当使用其去构造复杂的事件模式时，将产生庞大的网结构.为精简Petri网整体规模，可以对双输入变迁结构中的库所，按照CEPPN的定义进行合并（如图1（c）所示）.合并后的库所具有两种颜色，可同时接收并存储两类事件.图1（d）为对图1（e）进行合并后的Petri网实例，前者与后者比较库所数量明显减少，且网结构更加紧凑.

使用CEP-PN共享相同的库所节点时将面临两种选择，即并发与冲突（分别如图1（f）、1（g）所示）.在并发情况下共享节点将参与每个子模式的匹配，因此在构造时需对该节点进行复制.而在冲突情况下，共享节点每次仅能够参与某一个子模式的匹配，因此在构造时需要对该节点进行合并.需要注意的是，在合并方式中还可以存在反馈结构，即共享节点上的事件实际上不被消耗，从而重复多次参与子模式的匹配（如图1（g）中的圆弧线所示）.基本网具体采用何种构造方式进行联接，将由事件模式的消耗策略决定.

图1 基本Petri网结构Fig.1 The basic structure of Petri net

3 多事件模式的合并

CEP系统中存在大量事件模式合并的情况.由于无法使用一条规则定义整个系统的运行，一个复杂的情景通常需要先由多条规则分别定义出来，然后经过合并才能形成.另外，在一条规则内部，同样需要经历先构造出基本网结构，然后合并的过程.合并后的Petri计算网，能够有效减小CEP系统的整体运行规模，提高系统运行效率.由此，以下给出事件模式合并的语义与算法.

定义2 设CEP-PN为一个网，如果存在t∈T，使M［t＞M′，则称M′为从M直接可达的.如果存在变迁序列t1，t2，…tn（记为σ）和标识序列 M1，M2，…Mn使得 M［t1＞ M1［t2＞ M2…Mn－1［tn＞Mn（记为M［σ＞Mn），则称Mn为从M 可达的.从M可达的一切标识的集合记为R（M），规定M∈R（M）.

定义3 设CEP-PN为一个网，M1和M2是网的两个标识.如果 ∀p∈P 都有M1（p）≤M2（p），则称M1被M2覆盖，记作M1≤M2.

定义4 设CEP-PN为一个网，M为网的一个标识.若 ∃M′∈R（M0），使得M≤M′，则称M 为CEP-PN的一个可覆盖标识.

根据以上定义可以很容易的证明多模式合并后的可达性.例如：可将如图1（a）所示的网记为＜a；b＞→ab，则＜a；b；d＞→abd事件模式，可视为＜a；b＞→ab与＜ab；d＞→abd两个基本网连接形成的合并网.记其初始状态为M0，a；b发生为M1，ab；d发生为M2，由于M1∈R（M0），且M2∈R（M1）：M2∈R（M0），因此R（M1）R（M0）.即如果变迁序列σ1导致M0→M1可达，σ2导致M1→M2可达，则一定存在σ＝σ1＋σ2导致M0→M2可达，其中M1是合并网的一个可覆盖标识.

对于任意两个网A、B，如果存在一个公共可覆盖标识M，使得M ∈RA（M0），且M ∈RB（M0），则A与B是可以合并的，其中RA（RB）为A（B）初始标识的可达标识集合.根据以上结论可知，＜a；b；c；d，a；b；c；e＞ 两个网是可以直接合并的（称为前结合模式），＜a；b；c；d，b；c；e＞ 亦是可以合并的（称为中间结合模式，后者网b；c可视为前者网a；b；c的特殊子模式），而 ＜a；b；c，e；b；c＞ 是不能直接合并的（称为后结合模式），由于a；b的变迁t1与e；b的变迁t2不是同一个变迁，因此不存在共同的可覆盖标识，但该类情况可采用后面先合并的方式，即将模式重写为 ＜a；（b；c），e；（b；c）＞ 的形式，以（b；c）为模式起始进行网合并，而后才将前面的库所与由合并形成的结果库所输入到一个变迁上去.后结合模式面临一定的风险，即当前事件不满足条件时，后事件的检测将浪费计算资源.

两个独立的网合并时会面临两种情况：并发与冲突（如图1（f）与1（g）所示）.并发情况下，合并库所采用复制模式产生出多个中间结果，同时用于每个事件模式的匹配.而冲突情况下，合并库所采用共享模式，仅参与多个事件模式匹配中的一条.系统使用模式的策略如下：对位于一条规则中的基本网结构和串联结构，采用连接模式合并，前结合与中间结合采用共享模式合并，后结合采用复制模式合并，对位于多条规则中的网则均采用复制模式合并.多事件模式合并算法为

①将预加入CEP引擎运行Petri网中的用户事件模式分解为多个（FirstPlace，Transition，Second Place，Out put Place）四元组，根据其中的操作符类型生成相应的基本网结构；

②将该事件模式产生基本网结构单元，依次采用连接模式进行合并，直到最后；

③采用从头比对的方法，将该事件模式与运行Petri网中事件模式列表中的其他模式进行逐一比较，如果未发现同类库所存在，则将其直接加入到运行Petri网中；

④ 如果发现新事件模式的首库所与某运行事件模式从首库所开始匹配，则采用前结合方式合并相同的子模式部分；

⑤ 如果发现新事件模式的首库所与某运行事件模式从其中间某库所开始匹配，则采用中间结合方式合并相同的子模式部分；

⑥ 如果发现新事件模式与某运行事件模式存在中间部分匹配，则采用后结合方式合并；

⑦直到与运行事件模式列表全部匹配完毕.

4 实验与分析

由于目前没有开源的以有色Pertri网为模型的CEP引擎，因此选择以自动机为模型的SASE原型系统进行比较.与SASE进行比较的其他重要原因在于，自动机模型是CEP社区最为流行的模式匹配方法，因此通过两者的比较能够清楚的发现两种基础实现思想的优缺点.为确保准确测试两者的性能，文中构造了相同的环境.首先事件模式采用了SASE提供的检测三支价格相等的股票序列的示例，然后让两个系统使用同一个事件发生器作为输入，并检查两者具有完全相同的输出.显然在输入、输出相同的情况下，占用越少时间、空间的系统性能越好，系统吞吐量则越大.

如果一个原子事件未参与复合而被过滤掉了，那么其显然不会充分占用计算时间.为最大限度的估算系统的计算能力，本实验的事件发生器产生三支股票事件各3，000个，并使得其全部参与计算，最终复合出3，000个匹配结果.为研究多模式在并发数据环境下的性能，复制事件模式从10倍至50倍.复制模式可以保证两个系统使用同一输入，同时输出一致的结果.例如：50个事件模式时，两者均输出150，000个复杂事件.如图2所示，当同时运行的模式数量小于20时，SASE运行较快，但随着模式数量的增加，SASE处理时长的增长速度明显高于CEP系统.其主要原因在于，随着注册模式的增加，在SASE中活动的自动机数量快速增长，使得用于检索活动状态的索引的效率持续降低，而Petri网系统可以通过在其库所和变迁上创建更多的并发进程有效降低处理时间.由此可知，当并发模式数量较少时，自动机模型执行高效.相反，Petri网模型则具有较好的运行效率.

图2 与SASE系统的比较Fig.2 Comparison with the SASE system

5 结 论

通过对有色Petri网进行时间扩展，使其能够较好的用于CEP事件模式的建模，以前、中、后三种结合模式进行连接的基本网结构，能够形式化、准确的表达事件模式.给出的Petri计算网自动合并算法，能够实现多个独立事件模式的关联共享，由此降低系统计算资源的利用，提高系统整体的运行效率.通过与目前流行的CEP引擎的比较与分析可知，Petri网系统在多模式并行执行时具有更好的性能，将能够有效应对大量事件并行输入与多模式并行处理的实际情况.

［1］ CUGOLA G，MARGARA A.Processing Flows of Information：From Data Stream to Complex Event Processing［J］.ACM Computing Surveys（CSUR），2012，44（3）：15.

［2］ CUGOLA G，MARGARA A.Complex Event Processing with T-Rex［J］.Journal of Systems and Software，2012，85（8）：1709.

［3］ AGRAWAL J，DIDOA Y，GYLLSTROM D，et al.Efficient Pattern Matching over Event Streams［C］／／Proceedings of the 2008ACM SIGMOD International Conference on Management of Data.Vancouver：ACM，2008：147.

［4］ 黃毅，郑力，向晴.基于复杂事件处理的RFID辅助实时生产监控［J］.清华大学学报：自然科学版，2013，53（5）：721.HUANG Yi，ZHENG Li，XIANG Qing.RFID Integrated Real－Time Manufacturing Monitoring Based on Complex Event Processing［J］.Journal of Tsinghua University：Science and Technology，2013，53（5）：721.（in Chinese）

［5］ 程苏珺，王永剑，孟由，等.PMTree：一种高效的事件流模式匹配方法［J］.计算机研究与发展，2013，49（11）：2481.CHENG Su－Jun，WANG Yong－jian，MENG You，et al.PMTree：An Efficient Pattern Matching Method for Event Stream Processing ［J］.Journal of Computer Research and Development，2013，49（11）：2481.（in Chinese）

［6］ 叶蔚，黄雨，赵文，等.基于Petri网的 RFID中间件中复合事件检 测研 究［J］.电子学报，2009，36（B12）：1.YE Wei，HUANG Yu，ZHAO Wen，et al.Research on Complex Event Detection in RFID Middleware Based on Colored Petri Net［J］.Acta Electronica Sinica，2009，36（B12）：1.（in Chinese）

［7］ 王中生，杨盛泉.Petri网的总线型DCS的通信机制［J］.西安工业大学学报，2010，30（3）：281.WANG Zhong－sheng，YANG Sheng－quan.Research of Communication Mechanism in Bus Topology DCS System Based on Petri Net［J］.Journal of Xi’an Technological University，2010，30（3）：281.（in Chinese）