社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
Flink的CEP设计与实现重度参考了论文《Efficient Pattern Matching over Event Streams》。下面我们就来结合论文谈谈Flink CEP的设计。
这篇论文探讨的话题是如何在事件流上进行高效地模式匹配。谈及模式匹配，为大众所知的可能是正则表达式匹配，而在流上运用正则表达式进行模式匹配有两个挑战：
而这篇论文提出解决方案是：设计并实现了一个正式的计算模型：
除此之外，论文还分析了运行时复杂度、展示了运行时的算法实现与优化
考虑下面这个来自论文中的股票交易业务中的模式：
PATTERN SEQ(Stock+ a[ ], Stock b)
WHERE
skip_till_next_match(a[ ], b) {
[symbol]
and a[1].volume > 1000
and a[i].price > avg(a[..i-1].price)
and b.volume < 80% * a[a.LEN].volume }
WITHIN
1 hour模式中的”[symbol]”表示分区处理。
上面的这个模式，描述了一个复杂的股票交易趋势：在过去的一段时间内，股票交易量开始升高，但在一个周期之后，当价格增长或者保持相对稳定后，交易量将会暴跌。这个模式有两个输入：在股票事件上的一个“正闭包”，结果存储于a[]中；一个分离的单一的股票事件，存储在b中。作用在a[1]上的断言指定了初始交易量，而作用在a[i]（i > 1）上的断言要求其当前事件的价格超过之前被选择事件的平均值，这样的断言会捕获交易的价格增长趋势。最后一个断言将b跟a[a.LEN]进行比较，这里a.LEN关联着a[]中最后一个被选择的事件，它会捕获最终交易量的落差。
状态和转移函数（可类比成是衔接状态转换的边）是
起始状态a[1]，表示匹配过程的开始，它等待“正闭包”的事件输入并选择一个事件到匹配缓冲区中的a[1]单元。在下一个状态a[i]，它会尝试选择另一个事件并放入缓冲区中的a[i]（i > 1）单元。接下来的状态b表示匹配过程对于a[]已经完成了一个特定的匹配且已经准备好处理下一个模式输入。而最终状态F，则表示处理完成，它将创建一个模式匹配。
CEP代码中以State类表示状态，其完整类图如下：
从类图可见，它主要封装了状态的名称、类型以及跟其有关的状态集合。StateType是枚举类型，枚举值如下：
public enum StateType {
Start, // NFA的起始状态
Final, // NFA的终止状态
Normal // 非起始非终止状态的其他正常状态
}从模式的状态图中可看到每个状态都关联着一组边，表示在状态上可以发生的转换动作。正如上图所展示的那样，首状态有一个“begin”边，每个a[i]状态有一个“proceed”边以及一个循环的“take”边。每个状态（除了起始状态和终止状态）都有一个循环的“ignore”边。
上面的这些转换动作，在代码中通过一个名为StateTransitionAction的枚举类来表示：
public enum StateTransitionAction {
TAKE, //获得当前事件并将它分配给新状态
IGNORE, //忽略当前事件并做状态转换
PROCEED //做状态转换并保留当前状态以为后续处理
}总结而言，在CEP中以State表示上图中的节点，以StateTransition表示上图中的边，也即状态之间的转化。所以这两个对象之间是互相关联的关系：
状态将用于NFA中。
微信扫码关注公众号：Apache_Flink
QQ扫码关注QQ群：Apache Flink学习交流群（123414680）
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
