本次分享主要介绍面向数据加工DSL的一项编译优化：公共子表达式删除（common subexpression elimination）。SLS数据加工服务是什么？公共子表达式删除的初衷？公共子表达式删除是怎么实现的？有哪些实际价值？
SLS数据加工服务是什么？
日志服务提供可托管、可扩展、高可用的数据加工服务。数据加工服务可用于数据的规整、富化、流转、脱敏和过滤。
数据加工DSL提供了30多种场景方案、200多个内置函数、400多项GROK模式，内置函数包含转换、分发、分裂、复制、富化五大类，并且内置函数之间没有前后强依赖关系，可以*编排，由此客户只需以函数调用的方式编写DSL即可实现复杂业务需求。
数据加工概述：https://help.aliyun.com/document_detail/125384.html
数据加工DSL简介：https://help.aliyun.com/document_detail/125439.html
数据加工DSL函数总览：https://help.aliyun.com/document_detail/159702.html
数据加工架构设计：https://topic.atatech.org/articles/208924
公共子表达式删除的初衷？
数据加工服务客户多，各个客户的业务需求较为复杂，DSL灵活性强，由此导致数据加工作业数量较多，且数据加工作业内容差异较大。由于数据加工采用了按量收费，优化门槛较高，客户性能优化积极性不高。客户往往只关心正确性的问题，而不会关心性能，出现了问题再去解决，后知后觉，客户体验较差。如果采用研发人员手动优化的方式提升数据加工作业的执行效率，工作量巨大，成本极高。由此，采用编译技术将“优化意识”自动化是一种较优的DSL优化解决方案。
重复的子函数操作在数据加工作业原始DSL中大量出现，如上图所示，比如v(“content”)和其包装函数json_select(v(“content”), “Content”),经过优化后会把这些公共子表达式抽出为临时变量，依次消除部分冗余函数计算。优化之后的DSL如下图所示。在原始content字段较大的情况下，经过上述公共子表达式优化性能会提升至少1倍。
公共子表达式删除是怎么实现的？
公共子表达式是一种经典的冗余删除编译技术，有没有一个相对权威的描述？Steven S.Muchnick在《高级编译器设计与实现》（编译原理的经典著作：鲸书，最好的编译优化参考书？）中是这样描述公共子表达式的：程序中一个表达式的一次出现是公共子表达式，如果存在着该表达式的另一次出现，在执行顺序上它的计算总是先于这个表达式的计算，并且在这两个计算之间该表达式的操作数没有发生改变。公共子表达式删除是一种转换，它删除公共子表达式的重复计算，并用保存的值来替代它们。
数据加工DSL较通用程序语言具有一定的特殊性。由于面向数据加工的DSL的基本计算单元是函数，因此面向数据加工的“公共子表达式删除”的基本单元也是函数。数据加工的数据流是自上而下垂直方向的，不包含复杂的循环跳转函数，由此函数的上下文作用域推导也极为简洁。数据加工作业包含一个隐式的变量：全局事件，这个事件流向也是垂直的，从数据加工作业的第一条语句一直执行到最后一条语句。通常程序语言的公共子表达式删除需要重复遍历多次抽象语法树，而面向数据加工DSL的公共子表达式删除只需遍历一次抽象语法树，减少了循环遍历的次数，从而加快了编译优化速度，时间复杂度较小。
公共字表达式删除主要包含如下步骤：
- 词法语法分析
首先，采用词法语法解析工具将数据加工作业的DSL解析并改写为语义一致且具有父子关系的AST（抽象语法树，Abstract Syntax Tree）。
然后，将跳转函数e_if()、e_if_else()、e_switch()需改写为条件判断形式的AST节点。由于函数e_split()表示基于某个字段的值分裂出多个事件。如果e_split()函数独立使用，则后面的所有语句均在分裂的具体事件的基础上执行，因此将e_split()改写为循环嵌套形式的AST节点。
由于条件判断和循环嵌套的出现，随之引入了多层作用域变量的问题，也就是同名变量会出现相互覆盖的情况。
- 公共子表达式定位
为了简化抽象语法静态分析逻辑，假设子节点对“当前事件”的影响范围同时会扩展到父节点。例如：条件判断语句具有两个分支，那么条件判断语句的影响范围为两个子分支的并集。
为了实现全局作用域感知功能，需要将字段名称及当前字段版本存储到字典“公共子表达式字典common_subexpression_dict”，此字典的键为字符串类型，值为列表类型。
为了定位字表达语义是否相同，需要生成表达式的唯一性标识符。采用深度优先的方式依次遍历AST的各个节点。当节点为事件处理类函数，则将影响（添加、更新和删除）的字段版本号version_id加1。在遍历节点的同时，采用附加输入字段版本号的序列化字符串作为当前作用域下表达式的“标识符expression_id”，此标识符能够同时区分表达式和作用域，当两者任何一个发生改变时，标识符expression_id都会发生改变，并将标识符expression_id和节点作为键值对存储到字典“公共子表达式字典common_subexpression_dict”。
注意：用于跳转作用域（if\switch）通常只有一个分支会被执行，因此，上文描述的作用域包含“字段作用域”和“跳转作用域”两部分。
- 公共变量替换
遍历“编译上下文compiler_context_map”，如果值中包含多个元素，则表示这几个元素可以采用“公共子表达式变量common_sub_expression_var”统一代替。为了保证变量名称的的唯一性common_sub_expression_var变量名称需添加后缀“{全局递增编号}_{行号}_{列号}”。
“公共子表达式变量common_sub_expression_var”声明的位置为同组公共子表达式的父抽象语法树节点，以此保证“公共子表达式变量common_sub_expression_var”的作用域的正确性。
有哪些实际价值？
- 优化门槛低
优化过程极为简单，完全由后台程序自动实现，客户无需深入分析及手动优化。
- 执行速度快
删除了公共子表达式，避免了相同代码的重复执行，提高了运行时的执行速度，优化了事件吞吐率和实时性。在原始子表达式计算复杂度较高的情况下，优化之后会有数倍的性能提升，有效降低了客户数据加工作业出现延时的概率。
- 运营开销少
翻译生成了较优的运行时代码，避免了相同代码的重复执行，加快了数据处理速度，缩短了处理延时，减少了服务器使用数量，节省了运营成本。
数据加工性能优化包含数十项详细优化，可以分为“DSL编译优化”和“运行时优化”两大类。本文是数据加工性能优化系列文章的第一篇。
联系方式
对我们工作感兴趣的，可以通过如下方式了解更多，谢谢关注！
- 微信公众号：日志服务 or LogAnalytics