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

作者：wynnliu， 腾讯IEG增长中台 后台开发工程师

出师之名

提到规则引擎，大部分人都会先想到DSL(Domain Specific Language)，进而联想令人生畏的编译原理、递归下降、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(Client IP)/VIP等更多请求属性配置，与及这些属性规则的组合配置，比如业务需要配置API的读写分离，并且灰度测试，就需要配置请求Method和请求Header这样的并集规则。

Json实现

我最开始没有往DSL的方向想，写几个像下面的简单的规则函数，用json格式定义规则，再用Go的反射库解析json，三下五除二就完成了规则判断。

不同的规则函数：

// IRule
type IRule interface {
  Match(req *http.Request) bool
}

// HeaderMatch 匹配header
func HeaderMatch(key, value string) bool {
  ...
  return false
}

// CookieMatch 匹配Cookie
func CookieMatch(key, value string) bool {
  ...
  return false
}

...

规则定义：

{
    "op":"AND",
    "matcher":[
        "header",
        "cookie"
    ],
    "header":{
        "key":"X-APP-ID",
        "value":"Ves"
    },
    "cookie":{
        "name":"feature",
        "value":"dev/wynnliu/qualify-rule"
    }
}

规则解析框架(非反射库版)：

// 遍历判断规则
for _, matcher := range matchers {
    var m map[string]interface{}
    err := json.Unmarshal([]byte(data["matcher"]), &m)
    if err != nil {
      log.Fatal(err)
    }

    switch matcher {
    case "header":
      ...
       result[matcher] = HeaderMatch(rule.key, rule.Vaule)
    case "coolkie":
      ...
       result[matcher] = CookieMatch(rule.name, rule.Vaule)
    }
    ...
  }
...
// 综合计算规则结果
switch op {
case "AND":
  ...
case "OR"
...
}
....

上面是一个常见的二元表达式规则，从规则定义到规则解析可以看出，用Json的方式实现非常方便，已经满足简单的规则场景。不好的地方就是解析的代码太灵活，一条龙的switch case，如果加入更多逻辑，复杂度就会上升，维护性也只会越来越差。

比如，一开始的规则条件只有等值匹配，接着增加范围匹配，非匹配，正则匹配等，后面再在这些基础上加入规则优先级，就得需要引入更多的json定义，规则解析框架也要相应地覆盖更多的抽象维度。

那有没有抽象度更高、实现也不复杂的解析实现方式呢？就是说，有没有比Json方式更好地表达这些规则的存在？

答案肯定是有的，不然怎么写下去🐶。

如果仔细分析上面的规则，可以发现这些规则经过一波计算后只需得到一个布尔值，与其他算术表达式、关系表达式不同，这些规则都是布尔表达式。

网上了解到，国内知名Go领域专家曹大(Xargin )在基于 Go 的内置 Parser 打造轻量级规则引擎一文中提到：Go的ast语法树可以完美表达布尔表达式，使用 Go 的内置 parser 库可以完成一个基本规则引擎的框架。

于是，我开始尝试使用Go自带的ast库及parser库完成转发规则的解析。

AST实现

Go的编译过程

Go的ast库和parser库都是Go编译过程中的工具库，Go的编译过程跟大部分高级语言的编译过程一样，分为6步：词法分析、语法分析、语义分析、中间码生成、代码优化和机器码生成。

引用《程序员的自我修养》里面的图，就是下面这一串流程：

每步的输入输出，具体做的事情总体如下表：

我们要拿来做规则引擎的就是前面两步的产物：词法分析得到的Token和语法分析的AST。

Token(记号)

Token是高级语言中最小的词法单元，Go主要有标识符、关键字、运算符和分隔符等Token，更多的token定义参考token文件。

比如我们扫描`println(”Hello World”)`，得到以下token：

扫描代码：

package main

import (
  "fmt"
  "go/scanner"
  "go/token"
)

func main() {
  var src = []byte(`println("Hello World!")`)

  var fset = token.NewFileSet()
  var file = fset.AddFile("hello.go", fset.Base(), len(src))

  var s scanner.Scanner
  s.Init(file, src, nil, scanner.ScanComments)

  for {
    pos, tok, lit := s.Scan()
    if tok == token.EOF {
      break
    }
    fmt.Printf("%s\\t%s\\t%q\\n", fset.Position(pos), tok, lit)
  }
}

扫描结果：

hello.go:1:1  IDENT "println"
hello.go:1:8  ( ""
hello.go:1:9  STRING  "\\"Hello World!\\""
hello.go:1:23 ) ""
hello.go:1:24 ; "\\n"

其中`println`是标识符(IDENT)Token， `Hello World`则是字符串Token。

AST(抽象语法树)

有了Scanner扫描出来的Token序列，到语法分析这一步，就可以进一步构造AST，但如果看具体的AST，会发现AST中不止有Token，比如同样是这段`println(”Hello World”)`，它的AST如下：

解析代码：

package main

import (
  "go/ast"
  "go/parser"
  "go/token"
)

func main() {
  src := `
package main
func main() {
  println("Hello, World!")
}
`
  // Create the AST by parsing src.
  fset := token.NewFileSet() // positions are relative to fset
  f, err := parser.ParseFile(fset, "", src, 0)
  if err != nil {
    panic(err)
  }

  // Print the AST.
  ast.Print(fset, f)

}

 解析结果：

     0  *ast.File {
     1  .  Package: 2:1
     2  .  Name: *ast.Ident {
     3  .  .  NamePos: 2:9
     4  .  .  Name: "main"
     5  .  }
     6  .  Decls: []ast.Decl (len = 1) {
     7  .  .  0: *ast.FuncDecl {
     8  .  .  .  Name: *ast.Ident {
     9  .  .  .  .  NamePos: 3:6
    10  .  .  .  .  Name: "main"
    11  .  .  .  .  Obj: *ast.Object {
    12  .  .  .  .  .  Kind: func
    13  .  .  .  .  .  Name: "main"
    14  .  .  .  .  .  Decl: *(obj @ 7)
    15  .  .  .  .  }
    16  .  .  .  }
    17  .  .  .  Type: *ast.FuncType {
    18  .  .  .  .  Func: 3:1
    19  .  .  .  .  Params: *ast.FieldList {
    20  .  .  .  .  .  Opening: 3:10
    21  .  .  .  .  .  Closing: 3:11
    22  .  .  .  .  }
    23  .  .  .  }
    24  .  .  .  Body: *ast.BlockStmt {
    25  .  .  .  .  Lbrace: 3:13
    26  .  .  .  .  List: []ast.Stmt (len = 1) {
    27  .  .  .  .  .  0: *ast.ExprStmt {
    28  .  .  .  .  .  .  X: *ast.CallExpr {
    29  .  .  .  .  .  .  .  Fun: *ast.Ident {
    30  .  .  .  .  .  .  .  .  NamePos: 4:2
    31  .  .  .  .  .  .  .  .  Name: "println"
    32  .  .  .  .  .  .  .  }
    33  .  .  .  .  .  .  .  Lparen: 4:9
    34  .  .  .  .  .  .  .  Args: []ast.Expr (len = 1) {
    35  .  .  .  .  .  .  .  .  0: *ast.BasicLit {
    36  .  .  .  .  .  .  .  .  .  ValuePos: 4:10
    37  .  .  .  .  .  .  .  .  .  Kind: STRING
    38  .  .  .  .  .  .  .  .  .  Value: "\\"Hello, World!\\""
    39  .  .  .  .  .  .  .  .  }
    40  .  .  .  .  .  .  .  }
    41  .  .  .  .  .  .  .  Ellipsis: -
    42  .  .  .  .  .  .  .  Rparen: 4:25
    43  .  .  .  .  .  .  }
    44  .  .  .  .  .  }
    45  .  .  .  .  }
    46  .  .  .  .  Rbrace: 5:1
    47  .  .  .  }
    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
//
// There are 3 main classes of nodes: Expressions and type nodes,
// statement nodes, and declaration nodes. The node names usually
// match the corresponding Go spec production names to which they
// correspond. The node fields correspond to the individual parts
// of the respective productions.
//
// All nodes contain position information marking the beginning of
// the corresponding source text segment; it is accessible via the
// Pos accessor method. Nodes may contain additional position info
// for language constructs where comments may be found between parts
// of the construct (typically any larger, parenthesized subpart).
// That position information is needed to properly position comments
// when printing the construct.

// All node types implement the Node interface.
type Node interface {
  Pos() token.Pos // position of first character belonging to the node
  End() token.Pos // position of first character immediately after the node
}

// All expression nodes implement the Expr interface.
type Expr interface {
  Node
  exprNode()
}

// All statement nodes implement the Stmt interface.
type Stmt interface {
  Node
  stmtNode()
}

// All declaration nodes implement the Decl interface.
type Decl interface {
  Node
  declNode()
}

常见的表达式有：

UnaryExpr 一元表达式
BinaryExpr 二元表达式
ParenExpr 括号表达式,被括号包裹的表达式
...

常见的语句有：

AssignStmt 赋值语句
SwitchStmt switch 语句
DeferStmt 延迟语句
ForStmt for 语句
...

更多定义在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: bad
     8  .  .  .  .  .  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: STRING
    21  .  .  .  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: STRING
    43  .  .  .  Value: "\\"Ves\\""
    44  .  .  }
    45  .  }
    46  }

有了AST结构，我们可以分别获取左边(X)的key值和右边(Y)的值根据逻辑运算符(Op)完成判断，如下是简单的判断实现：

// Parse
func Parse(expr string, header http.Header) (bool, error) {
  exprAst, err := parser.ParseExpr(expr)
  if err != nil {
    return false, err
  }
  // 打印 ast
  //fset := token.NewFileSet()
  //ast.Print(fset, exprAst)
  return judge(exprAst, header), nil
}

// 判断
func judge(bop ast.Node, header http.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值

  // 等值匹配
  return header.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(Yet Another Compiler Compiler)，是一个经典的生成语法分析器的工具，GoYACC是Golang版本的YACC。

用GoYACC解析自己设计的BNF/EBNF(巴科斯范式／扩展巴科斯范式，定义语法规则)。GoYACC整体使用原理基本还是上文提到的编译过程，但涉及的细节较多，本文不展开，有兴趣的读者朋友可以参考TiDB SQL Parser，了解TiDB的sql解析器如何基于GoYACC设计完成sql解析。