Flink CEP的论文与设计
Flink的CEP设计与实现重度参考了论文《Efficient Pattern Matching over Event Streams》。下面我们就来结合论文谈谈Flink CEP的设计。
这篇论文探讨的话题是如何在事件流上进行高效地模式匹配。谈及模式匹配，为大众所知的可能是正则表达式匹配，而在流上运用正则表达式进行模式匹配有两个挑战：
- 要求丰富的语言特性：在事件流上进行模式匹配的语言明显要比用正则表达式进行模式匹配的语言所需要的能力丰富得多。这些事件模式语言需要包含对表达序列、Kleene闭包、否定以及复杂断言的构建，同时还包含从混杂着相关、不相关事件的输入流中提取相关事件的策略；
- 流上处理的效率：在事件流上进行的模式查询如何被高效地计算，需要新的算法和优化工作；
而这篇论文提出解决方案是：设计并实现了一个正式的计算模型：
除此之外，论文还分析了运行时复杂度、展示了运行时的算法实现与优化
NFA-b模型
考虑下面这个来自论文中的股票交易业务中的模式：
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中。
原文发布时间为：2017-03-03
本文作者：vinoYang
本文来自云栖社区合作伙伴CSDN博客，了解相关信息可以关注CSDN博客。
