Flink-CEP论文与源码解读之状态与状态转换-阿里云开发者社区

开发者社区> nicenelly> 正文

Flink-CEP论文与源码解读之状态与状态转换

简介: Flink CEP的论文与设计 Flink的CEP设计与实现重度参考了论文《Efficient Pattern Matching over Event Streams》。下面我们就来结合论文谈谈Flink CEP的设计。
+关注继续查看

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
结构如下图所示:

NFA-structure

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

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

CEP-State-class-diagram

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

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

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

NFA-b-edge-formula

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

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

State-and-StateTransition-class-diagram

状态将用于NFA中。


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

本文作者:vinoYang

本文来自云栖社区合作伙伴CSDN博客,了解相关信息可以关注CSDN博客。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
State Processor API:如何读取,写入和修改 Flink 应用程序的状态
Apache Flink 1.9.0引入了状态处理器(`State Processor`)API,它是基于DataSet API的强大扩展,允许读取,写入和修改Flink的保存点和检查点(checkpoint)中的状态。
658 0
LinkedHashMap源码分析(基于JDK1.6)
LinkedHashMap类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是插入次序,或者是最近最少使用(LRU)的次序。只比HashMap慢一点;而在迭代访问时反而更快,因为它使用链表维护内部次序(HashMap是基于散列表实现的,相关HashMap的内容可以看《Java集合类》和《HashMap源码分析》)。
575 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4519 0
Apache Flink 零基础入门教程(六):状态管理及容错机制
本文主要分享内容如下: - 状态管理的基本概念; - 状态的类型与使用示例; - 容错机制与故障恢复;
979 0
UEditor 之查询当前编辑区域的状态是源码模式还是可视化模式
在使用百度的编辑器的时候,遇到了这样的一个问题:     解决方法是 使用了两个命令:
505 0
HashSet及LinkedHashSet源码分析(基于JDK1.6)
Java容器类的用途是“保存对象”,分为两类:Map——存储“键值对”组成的对象;Collection——存储独立元素。Collection又可以分为List和Set两大块。List保持元素的顺序,而Set不能有重复的元素。
695 0
Flink1.7.2 Dataset 文件切片计算方式和切片数据读取源码分析
了解读取的文件或目录,具体进行切片拆分的实现 了解任务读取切片中的数据规则
1141 0
Flink状态管理和容错机制介绍
本文来自2018年8月11日在北京举行的 Flink Meetup会议,分享来自于施晓罡,目前在阿里大数据团队部从事Blink方面的研发,现在主要负责Blink状态管理和容错相关技术的研发
1070 0
+关注
716
文章
646
问答
来源圈子
更多
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载