如何用Go快速实现规则引擎

见贤思齐

作者：wynnliu，腾讯IEG增长中台后台开发工程师出师之名提到规则引擎，大部分人都会先想到DSL(DomainSpecificLanguage)，进而联想令人生畏的编译原理、递归下降、LL或LR。但规则引擎有大有小，它们在不同场景的存在不一样，并不一定都要这么复杂。比如在一个小型支付系统的简单风控场景里，产品同学想设置一些规则，避免用户的银行卡被盗刷或者商户被薅羊毛（仅为示例，并不代表现实中也是应用了同样策略）：24小时内支付总金额超10万的用户1小时使用信用卡支付金额超5万的用户1小时被发起退款金额超10万的商户30分钟内频繁支付又退款超过10次的用户......为了快速实现需求，我们开发一个单独的规则类或者库，类里面有不同规则判断函数。规则不断增加，规则函数就不断扩展，这个膨胀的规则类库就是一个微小的规则引擎。虽然在业务调用的地方会有很多switch或者if...else..，但这个微小的规则引擎并不需要引入DSL，一样能好好工作。而在另外一些业务系统，比如贷款系统，同样是风控场景，产品同学也会设置一些规则做不同的金额审批决策（仅为示例，并不代表现实中也是应用了同样策略）：征信评分达到650，申请金额2000元以下可以直接审批征信评分达到650，申请金额在5000以下，如果月均消费达到2000块可以直接审批征信评分在550~600之间，申请金额在5000以下的三四线城市用户，如果月均消费达到1000块还需要其他消费评估，如果月收入未达到1万需要工资流水证明......在这些规则未增多之前，我们发现单单写规则类库，业务方通过调用不同函数判断，就已经痛不欲生。这些风控规则相比上文来说，涉及的用户属性多，判断条件复杂，而且还有不同的优先级。如果没有更好的规则抽象，代码复杂度只会越来越高，这时就需要设计一套DSL来满足更多的规则判断。所以，在我们真正要实现一个规则引擎之前，下定决心设计DSL与编译原理拉扯之前，我们首先看简单的规则类库是否就已满足需求。需求背景Gopass是一个API网关，作为一个网关，网关必不可少的能力是路由转发，精细化路由更是高频需求。业务需要根据不同需求场景做不同的路由配置，比如灰度发布、A/B测试、限流、负载均衡等。Gopass现有的转发规则只能基于请求Method和URL(Host/Path/Query)作简单配置，欠缺根据请求Header、Cookie、CIP(ClientIP)/VIP等更多请求属性配置，与及这些属性规则的组合配置，比如业务需要配置API的读写分离，并且灰度测试，就需要配置请求Method和请求Header这样的并集规则。Json实现我最开始没有往DSL的方向想，写几个像下面的简单的规则函数，用json格式定义规则，再用Go的反射库解析json，三下五除二就完成了规则判断。不同的规则函数：//IRuletypeIRuleinterface{Match(req*http.Request)bool}//HeaderMatch匹配headerfuncHeaderMatch(key,valuestring)bool{...returnfalse}//CookieMatch匹配CookiefuncCookieMatch(key,valuestring)bool{...returnfalse}...规则定义：{"op":"AND","matcher":["header","cookie"],"header":{"key":"X-APP-ID","value":"Ves"},"cookie":{"name":"feature","value":"dev/wynnliu/qualify-rule"}}规则解析框架(非反射库版)：//遍历判断规则for_,matcher:=rangematchers{varmmap[string]interface{}err:=json.Unmarshal([]byte(data["matcher"]),&m)iferr!=nil{log.Fatal(err)}switchmatcher{case"header":...result[matcher]=HeaderMatch(rule.key,rule.Vaule)case"coolkie":...result[matcher]=CookieMatch(rule.name,rule.Vaule)}...}...//综合计算规则结果switchop{case"AND":...case"OR"...}....上面是一个常见的二元表达式规则，从规则定义到规则解析可以看出，用Json的方式实现非常方便，已经满足简单的规则场景。不好的地方就是解析的代码太灵活，一条龙的switchcase，如果加入更多逻辑，复杂度就会上升，维护性也只会越来越差。比如，一开始的规则条件只有等值匹配，接着增加范围匹配，非匹配，正则匹配等，后面再在这些基础上加入规则优先级，就得需要引入更多的json定义，规则解析框架也要相应地覆盖更多的抽象维度。那有没有抽象度更高、实现也不复杂的解析实现方式呢？就是说，有没有比Json方式更好地表达这些规则的存在？答案肯定是有的，不然怎么写下去🐶。如果仔细分析上面的规则，可以发现这些规则经过一波计算后只需得到一个布尔值，与其他算术表达式、关系表达式不同，这些规则都是布尔表达式。网上了解到，国内知名Go领域专家曹大(Xargin)在基于Go的内置Parser打造轻量级规则引擎一文中提到：Go的ast语法树可以完美表达布尔表达式，使用Go的内置parser库可以完成一个基本规则引擎的框架。于是，我开始尝试使用Go自带的ast库及parser库完成转发规则的解析。AST实现Go的编译过程Go的ast库和parser库都是Go编译过程中的工具库，Go的编译过程跟大部分高级语言的编译过程一样，分为6步：词法分析、语法分析、语义分析、中间码生成、代码优化和机器码生成。引用《程序员的自我修养》里面的图，就是下面这一串流程：每步的输入输出，具体做的事情总体如下表：输入步骤输出说明源代码词法分析Tokengo文件被输入到扫描(Scanner)，它使用一种类似于有限状态机的算法，将源代码的字符系列分割成一系列的记号(Token)Token序列语法分析AST将Token转化为AST(抽象语法树)。AST语义分析正确的AST对上一步的AST进行类型检查(名称检查、类型推断等)。正确的AST中间码生成SSA特性的中间码(IR)中间码的作用之一是适配不同操作系统，兼容不同平台。 静态单赋值（StaticSingleAssignment、SSA）是中间代码的特性，如果中间代码具有静态单赋值的特性，那么每个变量就只会被赋值一次。SSA特性的中间码(IR)代码优化优化后的中间码优化后的中间码机器码生成汇编代码（Plan9）对不同系统指令集、CPU架构翻译成不同的机器码。我们要拿来做规则引擎的就是前面两步的产物：词法分析得到的Token和语法分析的AST。Token(记号)Token是高级语言中最小的词法单元，Go主要有标识符、关键字、运算符和分隔符等Token，更多的token定义参考token文件。比如我们扫描`println(”HelloWorld”)`，得到以下token：扫描代码：packagemainimport("fmt""go/scanner""go/token")funcmain(){varsrc=[]byte(`println("HelloWorld!")`)varfset=token.NewFileSet()varfile=fset.AddFile("hello.go",fset.Base(),len(src))varsscanner.Scanners.Init(file,src,nil,scanner.ScanComments)for{pos,tok,lit:=s.Scan()iftok==token.EOF{break}fmt.Printf("%s\\t%s\\t%q\\n",fset.Position(pos),tok,lit)}}扫描结果：hello.go:1:1IDENT"println"hello.go:1:8(""hello.go:1:9STRING"\\"HelloWorld!\\""hello.go:1:23)""hello.go:1:24;"\\n"其中`println`是标识符(IDENT)Token，`HelloWorld`则是字符串Token。AST(抽象语法树)有了Scanner扫描出来的Token序列，到语法分析这一步，就可以进一步构造AST，但如果看具体的AST，会发现AST中不止有Token，比如同样是这段`println(”HelloWorld”)`，它的AST如下：解析代码：packagemainimport("go/ast""go/parser""go/token")funcmain(){src:=`packagemainfuncmain(){println("Hello,World!")}`//CreatetheASTbyparsingsrc.fset:=token.NewFileSet()//positionsarerelativetofsetf,err:=parser.ParseFile(fset,"",src,0)iferr!=nil{panic(err)}//PrinttheAST.ast.Print(fset,f)} 解析结果：0*ast.File{1.Package:2:12.Name:*ast.Ident{3..NamePos:2:94..Name:"main"5.}6.Decls:[]ast.Decl(len=1){7..0:*ast.FuncDecl{8...Name:*ast.Ident{9....NamePos:3:610....Name:"main"11....Obj:*ast.Object{12.....Kind:func13.....Name:"main"14.....Decl:*(obj@7)15....}16...}17...Type:*ast.FuncType{18....Func:3:119....Params:*ast.FieldList{20.....Opening:3:1021.....Closing:3:1122....}23...}24...Body:*ast.BlockStmt{25....Lbrace:3:1326....List:[]ast.Stmt(len=1){27.....0:*ast.ExprStmt{28......X:*ast.CallExpr{29.......Fun:*ast.Ident{30........NamePos:4:231........Name:"println"32.......}33.......Lparen:4:934.......Args:[]ast.Expr(len=1){35........0:*ast.BasicLit{36.........ValuePos:4:1037.........Kind:STRING38.........Value:"\\"Hello,World!\\""39........}40.......}41.......Ellipsis:-42.......Rparen:4:2543......}44.....}45....}46....Rbrace:5:147...}48..}49.}50.Scope:*ast.Scope{51..Objects:map[string]*ast.Object(len=1){52..."main":*(obj@11)53..}54.}55.Unresolved:[]*ast.Ident(len=1){56..0:*(obj@29)57.}58}整个AST包括Package、Name、Decls、Scope跟Unresolved，其中核心内容在Decls里边（第6行～49行）。Decls是声明declaration的集合，里边有FuncDecl(函数声明)，有BlockStmt(块语句)，还有CallExpr(表达式)等。深入ast库，可以发现这三个正是AST节点的主要类型，它们都实现了Node(节点)接口，就是说，AST这颗树挂的都是这三个玩意。//----------------------------------------------------------------------------//Interfaces////Thereare3mainclassesofnodes:Expressionsandtypenodes,//statementnodes,anddeclarationnodes.Thenodenamesusually//matchthecorrespondingGospecproductionnamestowhichthey//correspond.Thenodefieldscorrespondtotheindividualparts//oftherespectiveproductions.////Allnodescontainpositioninformationmarkingthebeginningof//thecorrespondingsourcetextsegment;itisaccessibleviathe//Posaccessormethod.Nodesmaycontainadditionalpositioninfo//forlanguageconstructswherecommentsmaybefoundbetweenparts//oftheconstruct(typicallyanylarger,parenthesizedsubpart).//Thatpositioninformationisneededtoproperlypositioncomments//whenprintingtheconstruct.//AllnodetypesimplementtheNodeinterface.typeNodeinterface{Pos()token.Pos//positionoffirstcharacterbelongingtothenodeEnd()token.Pos//positionoffirstcharacterimmediatelyafterthenode}//AllexpressionnodesimplementtheExprinterface.typeExprinterface{NodeexprNode()}//AllstatementnodesimplementtheStmtinterface.typeStmtinterface{NodestmtNode()}//AlldeclarationnodesimplementtheDeclinterface.typeDeclinterface{NodedeclNode()}常见的表达式有：UnaryExpr一元表达式BinaryExpr二元表达式ParenExpr括号表达式,被括号包裹的表达式...常见的语句有：AssignStmt赋值语句SwitchStmtswitch语句DeferStmt延迟语句ForStmtfor语句...更多定义在ast文件中都可以找到，并不难以理解。需求实现认识了Token跟AST后，我们看怎么简单实现我们的规则解析，还是用上文的例子，要判断http请求header的key/value及cookie的name/value是否满足以下规则："header":{"key":"X-APP-ID","value":"Ves"},"cookie":{"name":"feature","value":"dev/wynnliu/qualify-rule"}以header的规则解析AST为例，`header.key=="X-APP-ID"&header.value=="Ves"`，打印的AST如下，AST很清晰地表示这条规则是个BinaryExpr，即二元表达式，二元表达式的左边为X，右边是Y，逻辑运算符为Op。 0*ast.BinaryExpr{1.X:*ast.BinaryExpr{2..X:*ast.SelectorExpr{3...X:*ast.Ident{4....NamePos:-5....Name:"header"6....Obj:*ast.Object{7.....Kind:bad8.....Name:""9....}10...}11...Sel:*ast.Ident{12....NamePos:-13....Name:"key"14...}15..}16..OpPos:-17..Op:==18..Y:*ast.BasicLit{19...ValuePos:-20...Kind:STRING21...Value:"\\"X-APP-ID\\""22..}23.}24.OpPos:-25.Op:&26.Y:*ast.BinaryExpr{27..X:*ast.SelectorExpr{28...X:*ast.Ident{29....NamePos:-30....Name:"header"31....Obj:*(obj@6)32...}33...Sel:*ast.Ident{34....NamePos:-35....Name:"value"36...}37..}38..OpPos:-39..Op:==40..Y:*ast.BasicLit{41...ValuePos:-42...Kind:STRING43...Value:"\\"Ves\\""44..}45.}46}有了AST结构，我们可以分别获取左边(X)的key值和右边(Y)的值根据逻辑运算符(Op)完成判断，如下是简单的判断实现：//ParsefuncParse(exprstring,headerhttp.Header)(bool,error){exprAst,err:=parser.ParseExpr(expr)iferr!=nil{returnfalse,err}//打印ast//fset:=token.NewFileSet()//ast.Print(fset,exprAst)returnjudge(exprAst,header),nil}//判断funcjudge(bopast.Node,headerhttp.Header)bool{//断言成二元表达式expr:=bop.(*ast.BinaryExpr)x:=expr.X.(*ast.BinaryExpr)key:=x.Y.(*ast.BasicLit)//key值y:=expr.Y.(*ast.BinaryExpr)value:=y.Y.(*ast.BasicLit)//value值//等值匹配returnheader.Get(strings.Trim(key.Value,`"`))==strings.Trim(value.Value,`"`)}更进一步通过以上的简单例子，我们大概可以利用go的ast库和parser库实现个简单的规则引擎。但这可能还不够，如果要覆盖更复杂的规则，不仅仅是只有布尔表达式，就要设计自己的规则原语，比如将`header.key=="X-APP-ID"&header.value=="Ves"`和`cookie.name=="feature"&cookie.value=="dev/wynnliu/qualify-rule"`设计成`req_header_pair_is("X-APP-ID","VES")&req_cookie_contain("feature","dev/wynnliu/qualify-rule")`。这时就需要引入GoYACC，YACC(YetAnotherCompilerCompiler)，是一个经典的生成语法分析器的工具，GoYACC是Golang版本的YACC。用GoYACC解析自己设计的BNF/EBNF(巴科斯范式／扩展巴科斯范式，定义语法规则)。GoYACC整体使用原理基本还是上文提到的编译过程，但涉及的细节较多，本文不展开，有兴趣的读者朋友可以参考TiDBSQLParser，了解TiDB的sql解析器如何基于GoYACC设计完成sql解析。