FlinkCEP的底层理论：NFA-b Automaton原理介绍

1. 基本概念

1.1. NFA^b介绍

FlinkCEP是基于《Efficient Pattern Matching over Event Streams》这篇论文的思想实现的。

该论文提出了一种在事件流上进行高效模式匹配的方法，即带匹配缓存的非确定有限自动机【Non-deterministic finite automaton】，又称为NFA^b自动机。

1.2. SASE+

SASE+语言：一个复杂的事件语言，它支持事件流上的Kleene闭包，并对该语言的可表达性提供了形式化的分析。
SASE+是一种专门用来描述CEP pattern的通用语言

1.3. CEP模式操作符

CEP模式操作符
【org.apache.flink.cep.operator.CepOperator】

• 针对键控输入流【keyed input stream】，对于每个键，CepOperator创建一个NFA和一个优先队列来缓冲顺序乱序的事件，这两种数据结构都使用托管键控状态进行存储。
• 针对于非键控输入流，CepOperator创建一个的全局NFA。

当事件被处理时，它