Flink CEP的论文与设计

Flink的CEP设计与实现重度参考了论文《Efficient Pattern Matching over Event
Streams》。下面我们就来结合论文谈谈Flink CEP的设计。

这篇论文探讨的话题是如何在事件流上进行高效地模式匹配。谈及模式匹配，为大众所知的可能是正则表达式匹配，而在流上运用正则表达式进行模式匹配有两个挑战：

• 要求丰富的语言特性：在事件流上进行模式匹配的语言明显要比用正则表达式进行模式匹配的语言所需要的能力丰富得多。这些事件模式语言需要包含对表达序列、Kleene闭包、否定以及复杂断言的构建，同时还包含从混杂着相关、不相关事件的输入流中提取相关事件的策略；
• 流上处理的效率：在事件流上进行的模式查询如何被高效地计算，需要新的算法和优化工作；

而这篇论文提出解决方案是：设计并实现了一个正式的计算模型：

NFAb

，它包含一个非确定性的有限自动机（NFA）和一个匹配缓冲区（buffer）。该模型为完整的事件模式查询集合提供了清晰的语义，允许进行优化并且可产生能在事件流上执行的查询计算计划，同时设计了一个共享的基于版本的缓冲区来优化针对每次运行构建独立匹配缓冲区所带来的资源开销。

除此之外，论文还分析了运行时复杂度、展示了运行时的算法实现与优化

NFA-b模型

NFAb

这一计算模型是由Flink CEP所参考的《Efficient Pattern Matching over Event
Streams》论文提出的。NFA[^1]（nondeterministic finite
automaton，全称：非确定有限自动机）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。

NFAb

相较于NFA的改进是它配备了一个匹配缓冲区（buffer），用来作为模式的查询、计算模型。

考虑下面这个来自论文中的股票交易业务中的模式：

模式中的”[symbol]”表示分区处理。

上面的这个模式，描述了一个复杂的股票交易趋势：在过去的一段时间内，股票交易量开始升高，但在一个周期之后，当价格增长或者保持相对稳定后，交易量将会暴跌。这个模式有两个输入：在股票事件上的一个“正闭包”，结果存储于a[]中；一个分离的单一的股票事件，存储在b中。作用在a[1]上的断言指定了初始交易量，而作用在a[i]（i
>
1）上的断言要求其当前事件的价格超过之前被选择事件的平均值，这样的断言会捕获交易的价格增长趋势。最后一个断言将b跟a[a.LEN]进行比较，这里a.LEN关联着a[]中最后一个被选择的事件，它会捕获最终交易量的落差。

状态和状态转换

状态和转移函数（可类比成是衔接状态转换的边）是

NFAb

的两种基本组成要素，用于示例的股票模式的

NFAb

结构如下图所示：

起始状态a[1]，表示匹配过程的开始，它等待“正闭包”的事件输入并选择一个事件到匹配缓冲区中的a[1]单元。在下一个状态a[i]，它会尝试选择另一个事件并放入缓冲区中的a[i]（i
>
1）单元。接下来的状态b表示匹配过程对于a[]已经完成了一个特定的匹配且已经准备好处理下一个模式输入。而最终状态F，则表示处理完成，它将创建一个模式匹配。

CEP代码中以State类表示状态，其完整类图如下：

从类图可见，它主要封装了状态的名称、类型以及跟其有关的状态集合。StateType是枚举类型，枚举值如下：

从模式的状态图中可看到每个状态都关联着一组边，表示在状态上可以发生的转换动作。正如上图所展示的那样，首状态有一个“begin”边，每个a[i]状态有一个“proceed”边以及一个循环的“take”边。每个状态（除了起始状态和终止状态）都有一个循环的“ignore”边。

NFAb

会将模式中的“WHERE”以及“WITHIN”查询子句翻译成相关的语法附加到对应的边上，股票模式的各个边的条件语法如下图所示：

上面的这些转换动作，在代码中通过一个名为StateTransitionAction的枚举类来表示：

总结而言，在CEP中以State表示上图中的节点，以StateTransition表示上图中的边，也即状态之间的转化。所以这两个对象之间是互相关联的关系：

状态将用于NFA中。

原文发布时间为：2017-03-03

本文作者：vinoYang

本文来自合作伙伴CSDN博客，了解相关信息可以关注CSDN博客。