B 站新一代 golang 规则引擎的设计与实现

发布于: 29 分钟前

随着对业务的理解深入和不断的抽象,可以发现很多业务场景的功能都可以抽象成“规则+指标”的模式。

这种模式,可以应用于很多很场景的场景:如风控场景,识别黑产,需要各种规则来进行判别;如流量分发场景,需要基于各种可收集的指标,组成规则,然后进行针对化的内容分发;推荐场景,推荐本身一个基于多指标的典型场景模式(或者说,机器学习就是一个收集数据指标,然后进行学习,进行推广的过程)。

有规则,有指标了,当然还需要一个可以执行规则的引擎。

1. 规则引擎的发展历程

第一代规则引擎,仅支持逻辑运算符(&&, ||, !, 外加括号 ) 主要是用来解析逻辑表达式,通过定义特定占位符,来绑定具体的子操作,然后使用子操作的结果来进行逻辑运算,并得到逻辑表达式的最终结果:

如,逻辑表达式: "$1 && $2", $1 和 $2占位符 接受规定个数的参数,然后分别输出true或false,逻辑表达式再对占位符的结果进行完整的逻辑运算,并得到最终的结果。

第一代规则引擎特点:简单;因为简单,所以执行性能相当好;但扩展能力不强,可以满足逻辑判别要求,但无法满足数值判别要求;当添加新的占位符运算时,需要工程重新发版。

第二代规则引擎,基于某些解释型语言的规则引擎,如java支持的javascript的执行引擎,那么规则编写语言就是javascript,规则引擎就是java虚拟机支持的javascript执行引擎本身。

第二代规则引擎特点也很明显,所引入的解释型语言有多强,规则表现能力有多强;无需重新发版;但执行性能略差;还有一个致命的缺陷是,使用者为了配置几个规则,不得不多学习一门语言,加大了规则的配置难度,以致于不便推广;不易测试;

第三代规则引擎,为了延续规则的表现能力,同时为了克服规则的配置难度,为了免于学习一门新语言的代价,第三代规则引擎将实现规则引擎自身的语言作为规则配置语言,借助该语言的自身的发展而发展。同时加入了一些有用的规则属性,如“规则名称”、“规则优先级”、“规则描述”。第三代规则引擎的代表时java实现的drools。

第三代规则引擎的特点是,规则表现力强,可基于用户指定的规则优先级,来先后执行规则,同时简化了一些复杂的不必要的语法。第三代规则引擎适合熟悉规则引擎开发语言自身的开发人员使用,但当推广至其他人员使用时,依旧免不了要让不熟悉此语言的人重新学习一门语言(规则配置复杂度并没有完全消除);同时,也不能完全满足实时高性能服务场景的需求。

2. 规则的执行模式

通过对各种业务场景的提炼分析,一个规则引擎至少要满足至少三种执行模式,但实际上,规则执行模式至少有五种,我归纳如下图所示:

如上图,顺序模式

规则优先级高的先执行,规则优先级低的后执行。这也是drools支持的模式。此模式的缺点很明显:随着规则链越来越长,执行返回的速度越来越慢。

如上图,并发执行模式

多个规则执行时,不考虑规则优先级,规则与规则之间并发执行。规则执行的返回的速度等于所有规则中的执行时间最长的那个规则。性能优异,但无法满足规则优先级

如上图,混合执行模式(mix model)

选择规则优先级最高的一个规则最先执行,剩下的规则并发执行。规则执行返回耗时 = 最高优先级的那个规则执行时间 + 并发执行中执行时间最长的那个规则耗时;此模式兼顾优先级和性能,适合于有豁免规则的场景。

如上图,逆混合模式

优先级最高的n-1个规则并发执行,执行完毕之后,再执行剩下的一个优先级最低的规则。和混合模式类似,兼顾性能和优先级。

如上图,桶模式

名字源于桶排序,规则池基于规则优先级进行分桶,优先级相同的规则置于一个桶中,桶内的规则并发执行,桶间的规则基于规则优先级顺序执行。

3. B站新一代规则引擎的设计与实现

B站大部分业务线,最开始是使用的是第一代规则引擎。其他使用java的业务线使用的规则引擎是drools。

因为初期业务少且简单,并发量不高,所以选择使用第一代规则引擎或者drools。

但随着业务发展,业务请求并发的显著提升,基于第一代引擎的规则迭代周期长、开发新规则的耗时多。因此有必要开发出一套能满足业务快速迭代、且健壮的规则引擎。

3.1 我们预期的规则引擎的样子

1.支持规则优先级

2.使用足够简单。这其实对规则与具体的代码的边界划分提出了要求。同时,我们我们的目标不仅是让程序员觉得使用简单,还要让无代码开发经验的产品、运营同学也能够觉得使用简单,让他们几乎不需要学习,便能自主配置规则,以此来完成不同的业务需求。

3.足够的灵活性。支持完整的逻辑运算,支持完整的四则运算,支持if..else选择结构,支持用户自定义API...

4.可选择的规则执行模式。不同的场景需要不同的规则执行模式。

5.高性能。这当然是最重要的,如果不能满足高性能,高并发的需求,最终还是会被扔到历史的垃圾堆中。

6.和golang的无缝对接。B站是以golang为主要开发语言,因此,开发的规则引擎要能和golang无缝对接。

7.其他的小确幸:支持注释...等等

3.2 基于golang与AST(抽象语法树)的规则引擎实现

第一代规则引擎解析简单的逻辑表达式,有的是基于正则实现,有的是基于简单的AST实现的。如果是简单的逻辑表达式,正则是足够用的。如果仅用AST来解析逻辑表达式,显然又有点大材小用。

为了不让抽象语法树(AST)屈才,也受此启发,我们最终选用了基于AST来方式来解析和执行具体的规则语法。我们实现规则引擎时所用到的具体技术如下:

a.基于Antlr4来自定义规则的语法,最终生成语法树结构

b.基于golang的反射技术来实现对用户自定义API的调用

c.基于golang的并发变成技术实现高性能的规则执行能力

3.2.1 关键核心语法定义
grammar gengine;
primary: ruleEntity+;
ruleEntity: RULE ruleName ruleDescription? salience? BEGIN ruleContent END;
ruleName : stringLiteral;
ruleDescription : stringLiteral;
salience : SALIENCE integer;
ruleContent : statements;
statements: statement+;
statement : ifStmt | methodCall | functionCall | assignment;
expression : mathExpression
| expression comparisonOperator expression
| expression logicalOperator expression
| notOperator ? expressionAtom
| notOperator ? '(' expression ')'
;
mathExpression : mathExpression mathMdOperator mathExpression
| mathExpression mathPmOperator mathExpression
| expressionAtom
| '(' mathExpression ')'
;
expressionAtom
: methodCall
| functionCall
| constant
| mapVar
| variable
;
assignment : (mapVar | variable) (assignOperator | setOperator) mathExpression;
ifStmt : 'if' expression '{' statements? '}' elseStmt? ;
elseStmt : 'else' '{' statements? '}';
constant
: booleanLiteral
| integer
| realLiteral
| stringLiteral
| atName
;
functionArgs
: (constant | variable | functionCall | methodCall | mapVar) (','(constant | variable | functionCall | methodCall | mapVar))*
;
integer : '-'? INT;
realLiteral : MINUS? REAL_LITERAL;
stringLiteral: DQUOTA_STRING ;
booleanLiteral : TRUE | FALSE;
functionCall : SIMPLENAME '(' functionArgs? ')';
methodCall : DOTTEDNAME '(' functionArgs? ')';
variable : SIMPLENAME | DOTTEDNAME ;
mathPmOperator : PLUS | MINUS ;
mathMdOperator : MUL | DIV ;
comparisonOperator : GT | LT | GTE | LTE | EQUALS | NOTEQUALS ;
logicalOperator : AND | OR ;
assignOperator: ASSIGN ;
setOperator: SET;
notOperator: NOT;
mapVar: variable LSQARE (integer |stringLiteral | variable ) RSQARE;
atName : '@name';

在语法定义好之后,使用idea的antlr4插件,生成遍历语法树的listener和visitor模式的代码。

语法树的可扩展能力决定了规则引擎的可扩展能力,当需要为规则引擎新增功能时,仅需修改语法定义,重新生成代码即可。

3.2.2 定义语法树节点

具体的代码请查看github:https://github.com/rencalo770/gengine/tree/master/base

3.2.3 使用listener模式来遍历语法树

使用listener遍历模式,将定义的语法树节点对应到具体的节点代码实现上

//此golang文件的更多代码请查看github:
//https://github.com/rencalo770/gengine/blob/master/iparser/GengineParserListener.go
import (
"gengine/base"
"gengine/core/errors"
parser "gengine/iantlr/alr"
"github.com/antlr/antlr4/runtime/Go/antlr"
"github.com/golang-collections/collections/stack"
"strconv"
"strings"
)
func NewGengineParserListener(ctx *base.KnowledgeContext) *GengineParserListener {
return &GengineParserListener{
Stack: stack.New(),
KnowledgeContext: ctx,
ParseErrors: make([]string, 0),
}
}
type GengineParserListener struct {
//继承antlr生成的基础架构代码
parser.BasegengineListener
ParseErrors []string
KnowledgeContext *base.KnowledgeContext
Stack *stack.Stack
ruleName string
}

3.2.3 其他核心构件

RuleBuilder.go 用于从字符串解析出具体的语法树

KnowledgeContext.go 用于存储解析出来的规则

DataContext.go 是用户向规则引擎中添加可用API的接口

Gengine.go 提供各种规则执行模式的接口

3.2.4 规则引擎支持的执行模式

规则引擎当前支持的执行模式有三种

a.顺序执行模式

b.并发执行模式

c.混合执行模式

3.2.5 规则引擎测试

一个超级测试:

代码见于: https://github.com/rencalo770/gengine/blob/master/test/Gengine_base_test.go

import (
"fmt"
"gengine/base"
"gengine/builder"
"gengine/context"
"gengine/engine"
"github.com/sirupsen/logrus"
"testing"
"time"
)
type User struct {
Name string
Age int64
Male bool
}
func (u *User)GetNum(i int64) int64 {
return i
}
func (u *User)Print(s string){
fmt.Println(s)
}
func (u *User)Say(){
fmt.Println("hello world")
}
const (
base_rule = `
rule "测试" "测试描述" salience 0
begin
// 重命名函数 测试; @name represent the rule name "测试"
Sout(@name)
// 普通函数 测试
Hello()
//结构提方法 测试
User.Say()
// if
if !(7 == User.GetNum(7)) || !(7 > 8) {
//自定义变量 和 加法 测试
variable = "hello" + (" world" + "zeze")
// 加法 与 内建函数 测试 ; @name is just a string
User.Name = "hhh" + strconv.FormatInt(10, 10) + "@name"
//结构体属性、方法调用 和 除法 测试
User.Age = User.GetNum(8976) / 1000+ 3*(1+1)
//布尔值设置 测试
User.Male = false
//规则内自定义变量调用 测试
User.Print(variable)
//float测试 也支持科学计数法
f = 9.56
PrintReal(f)
//嵌套if-else测试
if false {
Sout("嵌套if测试")
}else{
Sout("嵌套else测试")
}
}else{ //else
//字符串设置 测试
User.Name = "yyyy"
}
if true {
Sout("if true ")
}
if true{}else{}
end`)
func Hello() {
fmt.Println("hello")
}
func PrintReal(real float64){
fmt.Println(real)
}
func exe(user *User){
/**
不要注入除函数和结构体指针以外的其他类型(如变量)
*/
dataContext := context.NewDataContext()
//注入结构体指针
dataContext.Add("User", user)
//重命名函数,并注入
dataContext.Add("Sout",fmt.Println)
//直接注入函数
dataContext.Add("Hello",Hello)
dataContext.Add("PrintReal",PrintReal)
//初始化规则引擎
knowledgeContext := base.NewKnowledgeContext()
ruleBuilder := builder.NewRuleBuilder(knowledgeContext, dataContext)
//读取规则
start1 := time.Now().UnixNano()
err := ruleBuilder.BuildRuleFromString(base_rule)
end1 := time.Now().UnixNano()
logrus.Infof("规则个数:%d, 加载规则耗时:%d ns", len(knowledgeContext.RuleEntities), end1-start1 )
if err != nil{
logrus.Errorf("err:%s ", err)
}else{
eng := engine.NewGengine()
start := time.Now().UnixNano()
// true: means when there are many rules, if one rule execute error,continue to execute rules after the occur error rule
err := eng.Execute(ruleBuilder, true)
end := time.Now().UnixNano()
if err != nil{
logrus.Errorf("execute rule error: %v", err)
}
logrus.Infof("execute rule cost %d ns",end-start)
logrus.Infof("user.Age=%d,Name=%s,Male=%t", user.Age, user.Name, user.Male)
}
}
func Test_Base(t *testing.T){
user := &User{
Name: "Calo",
Age: 0,
Male: true,
}
exe(user)
}

尽管测试看起来形式过于复杂,但规则本身只有4种形式:

a.逻辑运算

b.四则运算

c.if...else结构

d.函数API调用

a、b、c三种形式,学过简单数学的都会用,d形式,仅需简单识别即可,为了进一步简化d,可以固定一个函数接口,基于改变指标名称的方法取不同的值。如下

//如果golang支持方法重载,这种用法就美滋滋了:
//配置规则的人就可以不必关心函数的返回是什么,他只需要知道,传入“指标名” + 参数,就能获得他想要的数据,
//剩下的一切交给规则引擎来打理
DataService.GetData("指标名", "参数1","参数2"...)

到这里,任何人,只要学会这4种形式就可以开始配置规则了。

4.gengine规则引擎在B站的使用情况

  1. B站使用情况:当前已经接入了数个场景,并在逐步扩展至更多的业务场景(因为业务脱敏需要,所以在此详述)。 B站在此规则引擎上构建了规则管理系统,用于在界面上配置规则,并向各个业务场景实时动态下发规则,无需重启服务。为了使规则配置更加简单,我们开发了一套可复用于所有场景的指标管理系统(这个由我的另一个同事研发实现)。

  2. 关于性能:真实的线上grpc服务,单场景线上10个规则,10个4核8G的docker容器,压测15分钟,平均2万QPS, 平均响应耗时在2到4ms,也有极个别请求的耗时在700ms左右,但不超过750ms;配合实体机使用效果会更好。

5.gengine规则引擎对机器学习的支持

如果大家看过周志华的《机器学习》这本书,大家一定知道,“规则学习”(我们配置的规则)也是一种机器学习,“规则学习”也是符合一般机器学习的理论和方法的。如具体场景的“规则学习”针对具体的场景识别或处理,也有准确率、精度、召回等一般机器学习在概念上的对应。规则引擎对于这种“硬”“规则学习”显然是天然支持的。

那么,规则引擎如何支持更一般的机器学习模型调用呢?通常训练出来的模型最终会暴露出对外服务的接口API,这是函数来支持的,也是在3.2.5小节说的形式d(定义函数)来支持。

另外,通常会有很多模型的待识别数据具有很多feature,feature其实就是规则中的指标。因此,基于函数接口取指标完全是OK的。如果从规则外部基于网络连接来取指标,而且是顺序取(规则上不可能支持复杂的并发支持,因为这样会破坏简单性,所以一般也是顺序取),那么这样带来的结果就是严重拖慢规则执行速度。

基于此考量,在未来不久的时间,我们会在语法树上定义一个简单的语法块,用以支持规则内的并发调用,形式大致如下:

rule "ruleName" "discri" salience 10
begine
//用此关键字来调用底层复杂的并发能力
conc{
metric1 = DataService("指标1","参数1","参数2"...)
metric2 = DataService("指标2","参数1","参数2"...)
//
metricn = DataService("指标n","参数1","参数2"...)
}
res = MachineService.predict(metric1, metric2, ..., metricn)
end

如上,基于语法块 “conc{...}”,就实现了“指标1”到“指标n”的并发取参数,最终n个指标的调用耗时不是累加,而是等于这n个指标调用中的最长耗时的那个指标。

6规则引擎代码实现的github地址

https://github.com/rencalo770/gengine

7.联系我

如果你有任何疑问或好的建议,可以随时给我发送邮件,或在github上提问:

我的公司邮箱:renyunyi@bilibli.com(此邮箱可能会被禁止接受外部邮件)

我的校友邮箱:M201476117@alumni.hust.edu.cn

发布于: 29 分钟前 阅读数: 10
用户头像

calo

关注

还未添加个人签名 2020.06.25 加入

还未添加个人简介

评论

发布
暂无评论
B站新一代golang规则引擎的设计与实现