Apache Flink复杂事件处理语言的形式语义  

Formal Semantics of Apache Flink Complex Event Processing Language

作　　者：傅宣登 吴志林[1,2] FU Xuan-Deng;WU Zhi-Lin(State Key Laboratory of Computer Science(Institute of Software,Chinese Academy of Sciences),Beijing 100190,China;School of Computer Science and Technology,University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]计算机科学国家重点实验室(中国科学院软件研究所),北京100190 [2]中国科学院大学计算机科学与技术学院,北京100049

出　　处：《软件学报》2024年第10期4510-4532,共23页Journal of Software

基　　金：国家自然科学基金(61872340)。

摘　　要：Apache Flink是目前最流行的流式计算平台之一,已经在工业界得到了广泛应用.复杂事件处理是流式计算的一种重要使用场景,Apache Flink平台定义并实现了一种复杂事件处理语言(简称FlinkCEP).FlinkCEP语法特性丰富,不仅包括常见的过滤、连接、循环等操作,还包括迭代条件、匹配筛选策略等高级特性.FlinkCEP语义复杂,尚缺乏语言规范对其语义进行准确描述,只能通过实现细节来理解,因此对其语义进行形式描述对于开发人员准确理解其语义非常必要.针对FlinkCEP提出一种数据流转换器的自动机模型,该模型包括用于刻画迭代条件的数据变量、存储输出结果的数据流变量、用于刻画匹配筛选策略的迁移优先级等特性.使用数据流转换器对FlinkCEP的语义进行形式建模,并且根据形式语义设计FlinkCEP的查询求值算法,实现原型系统.进一步,生成能够较为全面覆盖FlinkCEP语法特性的测试用例集,利用这些测试用例与FlinkCEP在Flink平台上的实际运行结果进行对比实验.实验结果表明所提出的形式语义与FlinkCEP在Flink平台上的实际语义基本是一致的.而且,对实验结果不一致的情况进行分析,指出FlinkCEP在Flink平台上的实现对于组模式的处理可能存在错误.Apache Flink is one of the most popular stream computing platforms and has many applications in industry.Complex event processing(CEP)is one of the important usage scenarios of stream computation.Apache Flink defines and implements a language for complex event processing(referred to as FlinkCEP).FlinkCEP includes rich syntactic features,not only the usual features of filtering,connecting,and looping,but also the advanced features of iterative conditions and after-match skip strategies.The semantics of FlinkCEP is complex,no language specification of FlinkCEP defines its semantics precisely,so it can only be understood by checking the implementation details.This motivates the definition of formal semantics for FlinkCEP so that the developers could understand its semantics precisely.This study proposes an automaton model called data stream transducers(DST)for FlinkCEP,where the data variables are applied to capture the iterative conditions,the data stream variables are adopted to store the outputs,and transition priorities are introduced to capture the after-match skip strategies.DST is leveraged to define the formal semantics of FlinkCEP and design the query evaluation algorithms based on the formal semantics.Moreover,a prototype of the CEP engine is implemented.Finally,test case sets are generated,which cover the syntactic features of FlinkCEP more comprehensively.They are utilized to conduct comparison experiments against the actual results of FlinkCEP on the Flink platform.The experimental results show that the proposed formal semantics of FlinkCEP conforms to the actual semantics of FlinkCEP in the vast majority of the cases.Furthermore,the inconsistencies between the formal and the actual semantics are analyzed and it is discovered that the Flink implementation of FlinkCEP may not deal with the group patterns correctly.

关 键 词：流式计算 Flink 复杂事件处理 形式语义 数据流转换器 查询求值 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]