【实践课】规则引擎设计与实现
【实践课】规则引擎设计与实现
【实践课】规则引擎设计与实现
一、概述
1.1 前言
规则引擎是一种嵌入在应用服务中的组件,可以将灵活多变的业务决策从服务代码中分离出来。通过使用预定义的语义模块来编写业务逻辑规则。在执行时接受数据输入、解释业务规则,并做出决策。规则引擎能大大提高系统的灵活性和扩展性。
在字节跳动,规则引擎已经在风控识别、活动运营、配置下发等场景得到了广泛的应用。开发人员可以将业务逻辑与服务代码解耦,实现灵活、高效的业务策略发布。目前公司内部基于规则引擎的动态决策系统已经承接了千万级别QPS的决策请求。
规则引擎的实现需要在满足大容量、高请求、低延迟的基础上尽可能做到简单易上手。本次课程将会带领大家实现一个简单版的规则引擎。
1.2 课程目标
- 了解规则引擎的组成部分和应用场景。
- 学习并掌握规则引擎的设计与实现原理。
- 明确一个规则引擎的设计目标,并完成各部分的设计与实现步骤拆解。
- 动手实现规则引擎项目,完成预定目标。
- [课外扩展] 结合其他课程,完成一个在线 规则引擎 服务。
1.3 课程重难点
重点
- 规则引擎的设计 。明确设计目标、完成步骤拆解、完成各部分状态机的详细设计
- 规则引擎的实现。基于项目工程完成词法分析、语法分析、抽象语法树的执行功能
难点
- 规则引擎的核心原理(理论)。词法分析、语法分析、类型检查、语法树执行
主要涉及到编译原理的部分
二、课前预习
课前必看!!!
本部分是需要大家在上课之前了解的内容,主要是一些基本的概念和原理。
在这门课程之前你可能根本没有听说过规则引擎这个东西,当然也可能是浅浅的大概知道这是个什么东西,或者是个规则引擎方面的资深专家(还没毕业,五年工作经验那种🐶,如果是这样请赶紧找我内推)。都没有关系,这门课包教包会!!!(学不会的下课后可以找我们运营人员联系我一对一教学)
当然,这门课程还是有一定的门槛的,这也就是我为什么要说这么多一定要让你仔细看看这部分的原因。经过实验,课程的内容如果只依赖于课上老师的讲解,只能做到:能听懂,能跟上,来不及思考。要想能够理解掌握这部分内容,能跟别人battle下,再向自己的知识山峰上加那么一块小石头,得好好预习。
开始之前先百度或者Google一下 “规则引擎”简单浏览下哈,📪📪📪另外掘金app上面也有许多不错的文章。可以先浏览看看。
2.1 数据结构基础
数据结构得学过吧,考多少分?😁
这块的预习目标呢,包括以下几个部分
- 精通常用数据结构:数组、结构体、指针、队列、二叉树 等等等,课本上有的都得看看
- 熟练掌握二叉树的各种遍历方式:前中后序遍历,层序遍历,打印二叉树,有时间可以自己写几个小demo,当然最基础的是需要知道各种遍历方式的区别
2.2 Go语言基础
- 掌握Go语言的基础语法,能读懂项目代码
是的,就这一个要求,其实学完青训营的前几节课就可以达到了
2.3 编译原理基础
编译原理被誉为"程序员的三大浪漫"之一,足以可见这块知识的深度与广度,我们这次课程也是简单的介绍一下与规则引擎相关的概念。
那么可能会有疑问了,不是讲规则引擎么?为啥还得学编译原理?
规则引擎的本质呢就是我们自己定义一套语法,然后去解析用这套语法写的表达式,然后根据解析的内容执行表达式。这个过程其实就是编译和执行的过程。
因此呢需要自行了解以下的内容
- 编译的概念:
- 编译的过程发生了什么?
- 一般分为哪几个步骤,每个步骤的中间结果是什么?
- 词法分析:
- 词法如何表示?| 正则文法
- 词法分析阶段的输出是什么
- 词法分析阶段是怎么做的?
- 词法分析可能会产生什么问题?
- 如何解决词法分析过程中产生的问题?| 左递归问题怎么解决
- 语法分析
- 语法如何表示?上下文无关语法、巴克斯范式怎么理解
- 语法分析阶段的输出是什么? 一般怎么表示
- 语法分析有哪些方式?什么是递归下降算法?
- 抽象语法树
- 抽象语法树是什么?
- 抽象语法树如何执行?
- 类型检查
- 类型检查怎么做?有哪些方式?
- 类型检查什么时候做?有什么区别?
2.4 环境搭建
课程之前,大家需要根据项目工程,来完成环境的搭建和Demo的运行
项目地址:
相信大家已经完成了Go环境的搭建,项目工程依赖了hertz框架,如果在之前的课程中完成了项目环境搭建可以直接复用。
项目环境:
- go语言环境搭建
- 需要安装docker环境
- 安装docker-compose工具
项目clone到本地后,可以执行测试脚本来测试环境的可用性。如果有错误欢迎百度和Google解决
git clone https://github.com/qimengxingyuan/young_engine.git
chmod a+x ./setup.sh
./setup.sh
脚本执行成功,则环境可以支持项目的执行
项目说明:
本项目是一个简单的规则引擎的实现,详细目录可以参考README.md
项目实现时间有限,没有做比较完备的测试,如果在demo执行的过程中出现某些bug或者执行异常可以直接在github提交issue或者修复后提起PR
三、课中知识点补充
3.1 什么是编译
编译的过程就是 把某种语言的源程序, 在不改变语义的条件下 ,转换成另一种语言程序(目标语言程序)
- 如果源代码编译后要在操作系统上运行,那目标代码就是汇编/机器代码。
- 如果编译后是在虚拟机里执行,那目标代码就可以不是汇编代码,而是一种解释器可以理解的中间形式的代码即可。
解释型语言和编译型语言
- 有的语言提前把代码一次性转换完毕,这种就是编译型语言,用的转换工具就叫编译器,比如C、C++、Go。一次编译可重复执行
- 编译后产物不能跨平台,不同系统对可执行文件的要求不同。.exe
- 特殊的,c、c++、汇编、源代码也不能跨平台
- 有的语言则可以一边执行一边转化,用到哪里了就转哪里,这种就是解释性语言,用的转化工具叫虚拟机或者解释器,比如java python、javascript
关于 Java 和 Python .
- Java既有编译又有解释。但是编译并没有直接编译成机器码,而是编译成字节码,然后再放到虚拟机中执行。
- Python执行过程也是经过两个阶段,先编译成字节码 .pyc 再放到虚拟机中去执行
JVM 和 Python解释器 | 为什么一个叫虚拟机一个叫解释器
- “虚拟机”对二进制字节码进行解释,而“解释器”是对程序文本进行解释。
- 从历史上看,Java 是为解释二进制字节码而设计和实现的,而 Python 最初是为解释程序文本而设计和实现的。因此,“Java 虚拟机”这个术语在 Java 社区中具有历史意义并且非常成熟,“Python 解释器”这个术语在 Python 社区中具有历史意义并且非常成熟。人们倾向于延长传统并使用很久以前使用的相同术语。
- 对于 Java,二进制字节码解释是程序执行的主要方式,而 JIT 编译只是一种可选的和透明的优化。而对于 Python,目前,程序文本解释是 Python 程序执行的主要方式,而编译成 Python VM 字节码只是一种可选的透明优化。
3.2 词法分析
把源代码字符串转换为词法单元(Token)的这个过程。
确定的有限自动机 DFA | Deterministic Finite Automaton
确定的有限自动机就是一个状态机,它的状态数量是有限的。该状态机在任何一个状态,基于输入的字符,都能做一个确定的状态转换。
3.3 语法分析
词法分析是识别一个个的单词,而语法分析就是在词法分析的基础上识别出程序的语法结构。这个结构是一个树状结构。这棵树叫做抽象语法树(Abstract Syntax Tree,AST)。树的每个节点(子树)是一个语法单元,这个单元的构成规则就叫“语法”。每个节点还可以有下级节点。
Token -> AST
上下文无关语法 Context-Free Grammar
语言句子无需考虑上下文,就可以判断正确性
... a = 0; ... 这是一个赋值语句,无论此语句的前后是什么代码,此语句所代表的操作是确定的。即给变量a赋值等于0
编程语言为什么不用人类的语言(自然语言),而是用上下文无关的文法呢? 因为
- 便于设计编译器。 客观上技术目前无法实现,如果使用了上下文相关文法,那就是真正实现了人工智能,NLP领域将会有重大突破。
- 便于代码开发维护。 如果开发出来的代码像高考的语文阅读理解一样,每个人都有不同的理解,那么,到底哪个才是作者真正想要表达的?如果人类都确定不了含义,那计算机同样也确定不了,最终结果就是错误执行或无法执行。
- 汇编语言/机器语言是上下文无关的。CPU执行指令时,读到哪条执行哪条。如果CPU需要考虑上下文,来决定一个语句到底要做什么,那么CPU执行一条语句会比现在慢千倍万倍。考虑上下文的事情,完全可以用户在编程的时候用算法实现。既然机器语言是上下文无关的,那高级语言也基本上是上下文无关的,可能有某些个别语法为了方便使用,设计成了上下文相关的,比如脚本语言的弱类型。在便于使用的同时,增加了解析器的复杂度。
上下文无关语法G:终结符集合T + 非终结符集合N + 产生式集合P + 起始符号S
G由T、N、S和P组成,由语法G推导出来的所有句子的集合称为G语言!
终结符: 组成串的基本符号。可以理解为词法分析器产生的token集合。比如 +
Id
(
)
等
非终结符: 表示token的的集合的语法变量。比如 stmt
varDecl
等等
start:blockStmts ; //起始
block : '{' blockStmts '}' ; //语句块
blockStmts : stmt* ; //语句块中的语句
stmt = varDecl | expStmt | returnStmt | block; //语句
varDecl : type Id varInitializer? ';' ; //变量声明
type : Int | Long ; //类型
varInitializer : '=' exp ; //变量初始化
expStmt : exp ';' ; //表达式语句
returnStmt : Return exp ';' ; //return语句
exp : add ; //表达式
add : add '+' mul | mul; //加法表达式
mul : mul '*' pri | pri; //乘法表达式
pri : IntLiteral | Id | '(' exp ')' ; //基础表达式
产生式:表示形式,S : AB ,就是说S的含义可以用语法AB进行表达
S : AB
A : aA | ε
B : b | bB
展开(expand):将P(A->u )应用到符号串vAw中,得到新串vu **w
折叠(reduce):将P(A->uu )应用到符号串vuu w中,得到新串vAw
推导(derivate):符号串u 应用一系列产生式,变成符号串v ,则u =>v:S => ab | b | bb
巴科斯范式
BNF是描述上下文无关理论的一种具体方法,通过BNF可以实现上下文无关文法的具体化、公式化、科学化,是实现代码解析的必要条件。
<expr> ::= <expr> + <term>
| <expr> - <term>
| <term>
<term> ::= <term> * <factor>
| <term> / <factor>
| <factor>
<factor> ::= ( <expr> )
| Num
BNF本质上就是树形分解,分解成一棵抽象语法树
- 每个产生式就是一个子树,在写编译器时,每个子树对应一个解析函数。
- 叶子节点叫做 终结符 ,非叶子节点叫做 非终结符 。
递归下降算法 Recursive Descent Parsing
基本思路就是按照语法规则去匹配 Token 串。比如说,变量声明语句的规则如下:
varDecl : types Id varInitializer? ';' ; //变量声明
varInitializer : '=' exp ; //变量初始化
exp : add ; //表达式
add : add '+' mul | mul; //加法表达式
mul : mul '*' pri | pri; //乘法表达式
pri : IntLiteral | Id | '(' exp ')' ; //基础表达式
如果写成产生式格式,是下面这样:
varDecl -> types Id varInitializer ';'
varInitializer -> '=' exp
varInitializer -> ε
exp -> add
add -> add + mul
add -> mul
mul -> mul * pri
mul -> pri
pri -> IntLiteral
pri -> Id
pri -> ( exp )
而基于这个规则做解析的算法如下:
匹配一个数据类型(types)
匹配一个标识符(Id),作为变量名称
匹配初始化部分(varInitializer),而这会导致下降一层,使用一个新的语法规则:
匹配一个等号
匹配一个表达式(在这个步骤会导致多层下降:exp->add->mul->pri->IntLiteral)
创建一个varInitializer对应的AST节点并返回
如果没有成功地匹配初始化部分,则回溯,匹配ε,也就是没有初始化部分。
匹配一个分号
创建一个varDecl对应的AST节点并返回
int a = 2
- 对于一个非终结符,要从左到右依次匹配其产生式中的每个项,包括非终结符和终结符。
- 在匹配产生式右边的非终结符时,要下降一层,继续匹配该非终结符的产生式。
- 如果一个语法规则有多个可选的产生式,那么只要有一个产生式匹配成功就行。如果一个产生式匹配不成功,那就回退回来,尝试另一个产生式。这种回退过程,叫做回溯(Backtracking)。
四、课后作业
4.1 实现一个在线规则引擎
课上我们重点讲了规则引擎的设计和实现,结合前面课程的内容课后实现一个在线版本的规则引擎
4.1.1 项目要求
使用Hertz框架开发一个HTTP服务,服务使用mysql,支持表达式的增删查改和编译执行。
并实现以下接口
直接表达式执行
请求参数为待执行的表达式和表达式中参数的值,并输出编译结果
实时编译并执行结果,不需要写入DB中
POST api/engine/run
- Request
{
"exp": "uid == 12345 && did > 0",
"params": {
"uid": 123456,
"did": 0
}
}
- Response
{
"code": 0,
"message": "success",
"data": { // 执行结果
"result": true
}
}
新增表达式
新增一条表达式到DB中,并返回表达式在DB中的ID
需要检测表达式 是否已经存在 ,如果已经存在,直接返回表达式的ID
需要检测表达式是否合法(编译是否通过) ,如果编译失败,返回错误码 20001
和编译错误
POST api/engine/exp/new
- Request
{
"exp": "uid == 12345 && did > 0",
}
- Response
{
"code": 0,
"message": "success",
"data": { // 表达式ID
"id": 1
}
}
// 编译失败时
{
"code": -1,
"message": "compile error: xxxxx", // 编译失败的信息
"data": { // 表达式ID
"id": 0
}
}
查询表达式
查询数据库中所有的表达式
GET api/engine/exp/list
- Response
{
"code": 0,
"message": "success",
"data": [
{
"id": 1,
"exp": "uid > 0"
}
]
}
删除表达式
根据ID删除表达式,表达式不存在时返回错误码 20002
, 和错误信息
删除成功返回被删除的表达式信息
DELETE api/engine/exp/:id
- Response
// 删除成功时
{
"code": 0,
"message": "success",
"data": { // 表达式ID
"id": 1,
"exp": "uid > 0"
}
}
// 删除失败时
{
"code": -1,
"message": "exp id 1 not exist", //查询失败的信息
"data": {}
}
执行表达式
根据表达式的ID,查询出表达式内容,并编译执行。表达式不存在时返回错误码 20002
, 和错误信息
POST api/engine/exp/run
- Request
{
"exp_id": 1,
"parmas": {
"uid": 123456,
"did": 0
}
}
- Response
{
"code": 0,
"message": "success",
"data": { // 执行结果
"result": true
}
}
// 表达式不存在时
{
"code": -1,
"message": "exp id 1 not exist", //查询失败的信息
"data": {}
}