一种面向实时事件流的复杂事件处理方法

技术领域

本发明公开涉及信息处理技术领域，尤其涉及一种面向实时事件流的复杂事件处理方法。

背景技术

复杂事件处理是一种动态环境下对事件流进行分析的技术，随着信息社会的进一步发展，越来越多的行业采用复杂事件处理(Complex Event Processing，CEP)技术来对海量的事件流进行实时的分析。复杂事件处理通过分析事件中的关系，通过关联、聚合、过滤等技术，根据事件间的时序关系和聚合关系制定查询规则，持续地从事件流中获取符合要求的事件序列。该技术在金融交易分析、传感器网络、物联网等领域都有着广泛的应用。

目前，基于有限状态自动机(Nondeterministic Finite Automata，NFA)的处理模型是最流行的复杂事件处理技术实现方式。通过NFA的方式来实现的复杂事件处理技术，在事件流上进行匹配的过程中都会产生临时匹配，用以保证该临时匹配结果能够被后续的事件使用形成新的临时匹配以及最终匹配结果。所以匹配过程中会在事件流上产生大量且重叠的部分匹配，有限状态自动机需维护大量的重复匹配状态，导致基于该技术的方法都会出现冗余计算的问题。尤其当复杂时间查询的时间窗口跨度大时，冗余计算将会给处理器和存储器等硬件资源带来巨大的额外开销。

发明内容

鉴于此，本发明公开提供了一种面向实时事件流的复杂事件处理方法，以解决有限状态自动机匹配过程中导致的冗余计算问题，从而提高复杂事件匹配的效率。

本发明提供的技术方案，具体为，一种面向实时事件流的复杂事件处理方法，包括如下步骤：

1)将查询解析为一个有限状态自动机，读取事件流，基于“事件实例覆盖”和“复杂事件实例覆盖”定义，建立查询与事件流的临时匹配之间的关联关系；

2)构建临时匹配的链式分区存储结构，将所述结构作为复杂事件实例覆盖的载体，在所述结构上，查询在事件流上进行复杂事件实例覆盖匹配，得到匹配结果复杂事件实例覆盖集，其中匹配时，采用复杂事件匹配算法CoverMatch；

3)采用CombineMatch算法将所得到的匹配结果进行一个反向的匹配结果联结，最终获取全部匹配结果。

优选地，所述事件流S(s1,s2,…,sn)由一系列的基本事件实例构成，其中si为事件实例，它包含了事件的类型、事件的属性和事件发生时的时间；

所述查询为复杂事件查询Q，是由一组定义在基本事件上的约束条件构成，用以定义和表示更高层次的复杂事件的属性特征；

所述“事件实例覆盖”定义为：当事件实例s

所述“复杂事件实例覆盖”定义为：对两个匹配结果M

优选地，上述方法具体包括如下步骤：

S1：假设有一个查询Q以及一个事件流S，将查询Q编译成NFA，其中在Q被编译成NFA之后，存在主要状态及多个分区；

S2：查找事件流中的事件e；如果事件e不为空则进行步骤S3，否则进行步骤S6；

S3：检查事件e的属性；如果符合要求则进行步骤S4，否则进行步骤S2；

S4：使用事件e在上一个分区中遍历暴露的匹配节点，将能够进行更新的节点拷贝，进行更新生成新的节点；

S5：检查此节点的时间窗口是否大于事件流S的时间范围，如果是，则进行步骤S2，否则进行步骤S6；

S6：查找事件e所在的分区region，进入到当前分区进行复杂事件实例覆盖的检查，查找当前事件e所在分区region中的每一个临时匹配链的链尾节点，如果事件e不是本分区所有链尾节点的复杂事件实例覆盖，就单独成链，否则成为某个链的链尾节点；

S7：查找本事件流的最后一个分区，找到本分区的每一个临时匹配链，并且使用prev直接定位到链尾节点，将这些链尾节点存储到复杂事件实例覆盖集R中，从而得到最终复杂事件实例覆盖集R；

S8：由于匹配过程中采用的是双向环形链式结构，则从最底端的复杂事件实例覆盖集R出发，反向遍历所在的链表；收集每个分区的该链表节点的最后一个事件实例，最后通过递归实现各个分区事件实例的联结，最终得到所有匹配结果。

本发明提出了一种面向实时事件流的复杂事件处理方法，对NFA进行了增强，为其设计了一个临时匹配的链式分区存储结构，用以替代现有技术中的集中式的临时匹配存储方式。本发明采用临时匹配链式分区存储结构则借助事件实例覆盖和复杂事件实例覆盖的概念来设计，规避了集中式临时匹配存储的缺点。

应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本发明的公开。

附图说明

此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本发明的实施例，并与说明书一起用于解释本发明的原理。

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员而言，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明一种面向实时事件流的复杂事件处理方法中所述临时匹配链式分区存储结构示意图；

图2是本发明公开实施例中在ABC数据集上处理5组查询的性能对比示意图；

图3是本发明公开实施例中在交通数据集上处理5组查询的性能对比示意图；

图4是本发明公开实施例中在ABC数据集上时间窗口约束的大小对性能影响的实验对比；

图5是本发明在交通数据集上时间窗口约束的大小对性能影响的实验对比示意图。

具体实施方式

这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本发明相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本发明的一些方面相一致的系统的例子。

针对基于NFA的复杂事件处理中产生的大量临时匹配和拷贝而导致的冗余计算等问题，本实施方案提供了一种面向实时事件流的复杂事件处理方法，提出了复杂事件实例覆盖的概念，通过复杂事件实例覆盖，可以建立临时匹配之间的关联关系，基于此关系来减少临时匹配的冗余产生和冗余复制。设计了一个临时匹配链式分区存储结构，通过该结构避免了临时匹配的集中式存储及使用，同时该结构也作为复杂事件实例覆盖的载体，构建了临时匹配之间的关联。提出了基于临时匹配链式分区存储结构的复杂事件匹配算法CoverMatch和CombineMatch。通过这两个算法，能够在减少临时匹配数量和复制的情况下保证复杂事件处理匹配结果的正确性和完整性。

一种面向实时事件流的复杂事件处理方法，包括：1)将查询解析为一个有限状态自动机，读取事件流，基于“事件实例覆盖”和“复杂事件实例覆盖”定义，建立查询与事件流的临时匹配之间的关联关系；

2)构建临时匹配的链式分区存储结构，将上述结构作为复杂事件实例覆盖的载体，在所述结构上，查询在事件流上进行复杂事件实例覆盖匹配，得到匹配结果，其中匹配时，采用复杂事件匹配算法CoverMatch；

3)采用CombineMatch算法将所得到的匹配结果进行一个反向的匹配结果联结，最终获取全部匹配结果。

上述事件流S(s1,s2,…,sn)由一系列的基本事件实例构成，其中si为事件实例，它包含了事件的类型、事件的属性和事件发生时的时间；

上述查询为复杂事件查询Q，是由一组定义在基本事件上的约束条件构成，用以定义和表示更高层次的复杂事件的属性特征；

上述“事件实例覆盖”定义为：当事件实例s

上述“复杂事件实例覆盖”定义为：对两个匹配结果M

上述方法中对现有的NFA进行了增强，为其设计了一个临时匹配的链式分区存储结构，用以替代原来的集中式的临时匹配存储方式。集中式的临时匹配存储方式在每次新的事件到来时都需要对所有的临时匹配进行遍历验证，严重消耗计算资源。而本实施方案中的临时匹配链式分区存储结构则借助事件实例覆盖和复杂事件实例覆盖的概念来设计，规避了集中式临时匹配存储的缺点。

一种面向实时事件流的复杂事件处理方法中，假设当前存在查询Q

在Q

其中基于链式分区存储结构的匹配算法CoverMatch具体为：

输入：事件流S

输出：复杂事件实例覆盖集R

在上述算法中，第g行的buildTempMatch方法表示了使用事件e在上一个分区中遍历暴露的匹配节点，将能够进行更新的节点拷贝，进行更新，然后再进入到当前分区进行复杂事件实例覆盖的检查，如果不是某个节点的复杂事件实例覆盖，就单独成链(第o行)，否则成为某个链的链尾节点(第m行)。最后返回的最终的复杂事件实例覆盖，由于采用的是双向环形链式结构，所以第q行使用prev可以直接定位到链尾节点从而得到最终复杂事件实例覆盖。

通过临时匹配链式分区存储结构以及上述匹配算法，查询Q

进一步地，如果用户要的是距离当前时间最近的一个复杂事件实例，只需要指定系统保存

本发明进一步地完善了匹配结果的生成。当用户指定需要获取全部匹配结果时，则需要使用CoverMatch算法对所得到的结果去进行一个反向的匹配结果联结，继续使用查询Q

由于采用的是双向环形链式结构，可以从最底端的复杂事件实例覆盖出发，反向遍历所在的链表。只需要收集每个分区的该链表节点的最后一个事件实例，最后通过递归实现各个分区事件实例的联结，该过程如下CombineMatch所示。对于Q

匹配结果联结算法CombineMatch

输入：复杂事件实例覆盖R。

输出：所有匹配结果M。

在上述算法第g行的方法getPrevBlockNode中，通过传入链表顶点R，能够获取上一个分区中R的父节点。第i行使用了递归的形式来获取最终的联结结果，其中采用doCombine方法进行了联结操作。

使用图1中最左侧的链表来举例，首先拿到C分区的节点

综上，一种面向实时事件流的复杂事件处理方法，包括如下步骤：

S1：假设有一个查询Q以及一个事件流S，将查询Q编译成NFA，在Q被编译成NFA之后，存在几个主要状态，并且会产生几个分区；

S2：查找事件流中的事件e；如果事件e不为空则进行步骤S3，否则进行步骤S6；

S3：检查事件e的属性；如果符合要求则进行步骤S4，否则进行步骤S2；

S4：使用事件e在上一个分区中遍历暴露的匹配节点，将能够进行更新的节点拷贝，进行更新生成新的节点；

其中，在复杂事件处理中中，临时匹配的拷贝处理需要使用深拷贝来实现。完成一次临时匹配的深拷贝需要在内存中产生一个新的临时匹配实例，并且将原临时匹配实例中的全部属性值以及实例中存在的引用，复制到新的临时匹配实例中。传统方法中临时匹配的拷贝是在遍历所有临时匹配的过程中进行的，这将不利于为复杂事件处理提供良好的系统吞吐能力，系统的计算开销也将增大。同时，所有临时匹配都被找出并显式地在内存中以实例的形式存在，将增加内存的开销。

S5：检查此节点的时间窗口是否大于事件流S的时间范围，如果是，则进行步骤S2，否则进行步骤S6；

S6：查找事件e所在的分区region，进入到当前分区进行复杂事件实例覆盖的检查，查找当前事件e所在分区region中的每一个临时匹配链的链尾节点，如果事件e不是本分区所有链尾节点的复杂事件实例覆盖，就单独成链，否则成为某个链的链尾节点；

S7：查找本事件流的最后一个分区，找到本分区的每一个临时匹配链，并且使用prev直接定位到链尾节点，将这些链尾节点存储到复杂事件实例覆盖集R中，从而得到最终复杂事件实例覆盖集R。

对前七步进行时间复杂度和空间复杂度的分析，若系统正在对事件e进行处理，假设e事件所属分区的上一个相邻分区中所暴露的临时匹配节点数量为x，且e事件所属分区中的链式结构实例数量为y，设临时匹配中的事件序列平均长度为k，则进行复杂事件实例覆盖检查的时间复杂度为O(k)，通过事件e得到新的临时匹配节点的时间复杂度为O(x+ky)。由于在事件e所在的分区的临时匹配链式结构中，只有尾节点会参与构建新的临时匹配节点，因此通过事件e得到新的临时匹配节点的空间复杂度为O(k(x+y))。

S8：由于采用的是双向环形链式结构，可以从最底端的复杂事件实例覆盖集R出发，反向遍历所在的链表。只需要收集每个分区的该链表节点的最后一个事件实例，最后通过递归实现各个分区事件实例的联结，最终得到所有匹配结果。

对步骤S8进行时间复杂度和空间复杂度的分析，当前分区数为n，则通过递归调用函数次数最多为n次，若每个分区中与复杂事件实例覆盖R关联的临时匹配链平均长度为m,则空间复杂度为O(nm)。由于每次递归函数体中的执行操作复杂度为O(m),因此时间复杂度为O(nm)。

在复杂事件匹配的过程中，如果只去匹配复杂事件实例覆盖的话，在出现连续的相同事件类型实例的情况下，可以以更快的效率完成匹配任务。同时，相对于SASE中的基于NFA下的skip-till-any-match利用大量临时匹配计算所有结果的策略，使用本发明提出的方法可以在匹配复杂事件实例覆盖的同时，利用结果联结算法，可以得到所有的匹配结果，过程高效并且不产生额外临时匹配，从而达到减少冗余计算的目的。

下面结合具体对比实验对本发明作进一步描述通过在模拟数据集和真实数据集上对优化方法的性能进行对比实验和分析，验证了所提方法和算法的有效性和高效性。

实施例1

通过实验对比来对本发明提出的基于临时匹配链式分区存储结构的匹配优化方法的有效性进行了分析和验证。实验采用Java实现了优化方法的编写。将从多个维度对实验结果进行分析说明，并通过性能对比证明其有效性。

本实施例在两个数据集上进行了实验，其中第一个数据集是通过事件流生成器所生成的模拟数据流，第二个数据集是真实数据集。

第一个数据集是ABC类型事件流，通过把事件类型简写为大写英文字母方式来定义事件的类型，其中每个事件都带有时间戳以及各自的属性值。生成事件流之前可在事件流生成器中自定义事件类型的数量、属性个数以及属性值的范围，流中的每个事件都是随机生成的。实验中该数据集包含了100000个原始事件。

第二个数据集包含了车辆交通数据，该数据由传感器收集，来自于丹麦奥胡斯市。该数据集是通过传感器在449个观测点位收集了4个月的数据而得到的，总共包含13577132个原始事件。每个事件代表一个观察点的交通情况，一个事件的属性包括ID、该点平均车速以及过去5分钟内观察到的车辆总数。

本实施例的优化方法将与目前比较流行的基于有限状态自动机的SASE方法和Siddhi方法进行对比实验。其中本实施例提出的基于临时匹配链式分区存储结构的匹配优化方法记为LinkedCEP，实验在Intel Core 2.60GHz CPU i7和16G内存的Linux系统上进行。

首先实验比较的是本实施例中的LinkedCEP与SASE、Siddhi在不同数据集上的匹配性能和临时匹配产生的数量。由于本实施例提出的CoverMatch算法只会匹配事件流中的复杂事件实例覆盖，并不会产生所有的匹配结果，为了公平地进行匹配性能的比较，在LinkedCEP中将包含匹配结果联结算法CombineMatch以支持产生所有的匹配结果。

由于两个数据集的原始事件、事件属性存在差异，为了更好地在两个数据集上执行匹配，针对两个数据集分别合成了不同的查询，并在两个数据集上分别使用LinkedCEP、SASE、Siddhi来执行对应的查询。以下将设计两组实验进行对比分析。

实验一：对两个数据集各合成了5组查询，每组查询包含10个基本复杂事件查询，这些复杂事件查询的序列长度为3，由于时间窗口对匹配时间的影响很大，所以时间窗口统一为50s，对应的值则是该组查询的平均匹配时间。

图2与图3所示为分别在ABC事件流和交通时间流上匹配性能的对比结果。在查询序列长度和事件窗口一致的情况下，无论在任一组查询上，LinkedCEP的匹配效率都要优于其余两种方法。例如，对于图2中Q

实验二：测试在不同时间窗口下的匹配性能。使用查询一中的查询组，更改查询的时间窗口为50s、100s、150s、200s、300s，对应的值为该组查询的平均匹配时间。

如图4和图5所示，在不同的时间窗口下，LinkedCEP的处理性能优于其余两个方法。例如图4的实验对比结果中，当时间窗口为200s时，LinkedCEP的处理性能比SASE提升了34％，比Siddhi提升了19％。并且通过图4和图5可以发现，随着时间窗口的增大，LinkedCEP对比另外两个方法的性能提升更大，这是因为时间窗口的大小会影响临时匹配的数量，当时间窗口很大，堆积的临时匹配就多，对性能的影响也越大。

上述实验表明，本发明提出的方法能够有效地提升基于有限状态自动机的复杂事件处理技术的匹配效率，无论是在查询序列长度较多还是查询时间窗口较大的情况下都能够通过减少冗余计算来获得效能的提升。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和变形，这些改变和变形也应视为本发明的保护范围。