B 站新一代 golang 规则引擎的设计与实现
![B站新一代golang规则引擎的设计与实现](https://static001.geekbang.org/infoq/52/52bc2c7b5b1136d78e822a0f28ce9c06.png)
前言
本文已经哔哩哔哩(www.bilibili.com)官方授权发表,gengine规则引擎代码已经哔哩哔哩哔官方授权,基于BSD协议开源 !
在此,首先感谢哔哩哔哩(www.bilibili.com)对开源的热爱与支持!!!
感谢哔哩哔哩领导和同事对我的工作支持和配合!!!
也感谢业界各位大佬对这篇文章的喜爱与支持,以及对技术的追求与执着!!!
引言
随着对业务理解的不断深入和抽象,可以发现很多业务场景的功能(代码)都可以抽象成“规则+指标”的模式。这种模式,可以应用于很多场景,如:
1.风控场景,识别黑产,需要各种规则来进行判别;
2.流量(内容)分发场景,需要基于各种可收集的指标,组成规则,然后基于规则,来对用户进行定制化的内容分发;
3.推荐场景,推荐本身就是一个基于多指标的典型规则场景模式(或者说,机器学习就是一个收集数据指标,然后进行学习,最后进行推广的过程)。
4.数据清洗场景,有些业务数据需要使用规则进行打标、清洗、识别,最后落表使用。
有规则,有指标了,当然还需要一个可以执行规则的引擎。
一、规则引擎的发展历程
1.1 第一代规则引擎
仅支持逻辑运算符(&&, ||, !, 外加括号 ),主要是用来解析逻辑表达式,通过定义特定占位符,来绑定具体的子操作,然后使用子操作的结果来进行逻辑运算,并得到整个逻辑表达式的最终结果。
如,逻辑表达式规则: "$1 && $2", $1 和 $2占位符(也叫指标), 接受规定个数的参数,然后分别输出true或false,逻辑表达式再对占位符的结果进行完整的逻辑运算,并得到最终的结果。
第一代规则引擎特点:
a. 简单,因为简单,所以执行性能相当好;
b. 扩展能力弱,可以满足逻辑判别要求,但无法满足数值判别要求;
c. 工程需要重新发版,当添加新的占位符运算时,工程需要重新发版。
d. 不利于记忆,这种规则表现形式,不利于人记忆,时间久了,要搞清楚占位符代表的是什么,还要回头去看当初写的文档。
1.2 第二代规则引擎
基于某些解释型语言的规则引擎,如java支持的javascript的执行引擎,那么规则的编写语言就是javascript,写规则就是在写javascript。规则引擎就是java虚拟机支持的javascript执行引擎本身。
第二代规则引擎特点也很明显:
a. 表现能力强,所引入的解释型语言有多强,规则表现能力有多强。
b. 无需重新发版。
c. 执行性能略差。
d. 接入成本高,使用复杂,使用者(常常是数据挖掘、数据分析、产品等人员,他们常常缺乏代码能力)为了配置几个规则,不得不花很多精力去学习一门语言,即使开发者自身,如果不熟悉规则配置语言,也一样要去学习。如此一来,规则的配置难度和使用成本极大,以致于难以推广;毕竟,如果都学会了这门语言,我何不直接撸代码呢?那样性能还高,也直接。
1.3 第三代规则引擎
为了延续规则的表现能力,同时为了降低规则的配置难度,且免于学习一门新语言的代价,第三代规则引擎将实现规则引擎自身的语言作为规则配置语言,同时还加入了一些有用的规则属性,如“规则名称”、“规则优先级”、“规则描述”等。
第三代规则引擎的典型代表是java实现的drools。
第三代规则引擎的特点是:
a. 规则表现力强,可基于用户指定的规则优先级,来先后执行规则;
b. 配置简化,简化了一些复杂的且不必要的语法。
c. 对开发友好,对配置规则者不友好, 第三代规则引擎适合熟悉规则引擎开发语言自身的开发人员使用,但当推广至其他人员使用时,依旧免不了要让不熟悉此语言的人重新学习一门语言(规则配置复杂度并没有真正消除);
d. 性能偏弱,不能完全满足实时、高性能服务场景的需求(具体见下文举例)。
二、规则的执行模式
通过对各种业务场景的分析提炼,一个规则引擎至少应该满足3种执行模式。但实际上,规则执行模式至少有5种,具体执行模式,我归纳如下图所示:
2.1 顺序模式
![](https://static001.geekbang.org/infoq/72/726d805290cc7216f358c07673f34065.png)
如上图,规则的顺序模式(sort model)
规则优先级高越高的越先执行,规则优先级低的越后执行。这也是drools支持的模式。此模式的缺点很明显:随着规则链越来越长,执行规则返回的速度也越来越慢。
2.2 并发执行模式
![](https://static001.geekbang.org/infoq/1e/1e60a9a9c61e901d0e43be061369c031.png)
如上图,规则的并发执行模式(concurrent model)
在此执行模式下,多个规则执行时,不考虑规则之间的优先级,规则与规则之间并发执行。规则执行的返回的速度等于所有规则中的执行时间最长的那个规则的速度(逆木桶原理)。执行性能优异,但无法满足规则优先级。
2.3 混合执行模式
![](https://static001.geekbang.org/infoq/fa/fab139f8eb5022e5da86c50ab4c0eea7.png)
如上图,规则的混合执行模式(mix model)
规则引擎选择一个优先级最高规则的最先执行,剩下的规则并发执行。规则执行返回耗时= 最高优先级的那个规则执行时间 + 并发执行中执行时间最长的那个规则耗时;此模式兼顾优先级和性能,适合于有豁免规则(或前置规则)的场景。
2.4 逆混合模式
![](https://static001.geekbang.org/infoq/16/16abe1341c6e9e8f1d24ff956a749bf7.png)
如上图,规则的逆混合执行模式(inverse mix model)
优先级最高的n-1个规则并发执行,执行完毕之后,再执行剩下的一个优先级最低的规则。这种模式适用于有很多前导判断规则的场景。其特性与混合模式类似,兼顾性能和优先级。
2.5 桶模式
![](https://static001.geekbang.org/infoq/b2/b241e7e99c72eff16dc97e4191288503.png)
如上图,规则执行的桶模式
名字源于《算法导论》中的桶排序。规则引擎基于规则优先级进行分桶,优先级相同的规则置于同一个桶中,桶内的规则并发执行,桶间的规则基于规则优先级顺序执行。
一个小故事:
我当年考研究生(跨专业)的时候,研究生的卷子上有一个桶排序的考题,因为自己复习不到位,导致自己没做出来。后来考完了,去翻《算法导论》才搞清楚这个算法是怎么回事。从此以后,我就记住了有这么一种排序,叫桶排序。只是当初没有想到的是,它曾经绊倒过我,但也会在未来的某一天,激发我创造出新的东西。
三、B站新一代规则引擎设计实现
3.0 起个名字
以golang开发,以引擎(engine)为核心,所以就叫gengine吧!
3.1 背景
目前大部分业务线,尤其是以golang为开发语言的业务线,基本上使用的是第一代规则引擎,此中原因,无非是因为当前的golang生态不够完善,如果基于其他语言创造相同的轮子,golang又没有相应的语言的某些特性支持,抑或开发人员对其他语言的某些框架根本不甚了了。
公司的少部分以java为主要开发语言的业务线,使用的规则引擎是drools。
在业务发展的初期,业务少且简单(无需复杂的规则),并发量也不高,所以选择使用第一代规则引擎或者drools,基本是合情合理的。
但随着业务发展,业务日趋复杂,业务请求并发的显著提升,基于第一代引擎的规则迭代周期长、开发新规则(新指标)的就要重新编码开发,指标难以复用、且每次上线规则必须重启(增加了服务的不稳定性和崩溃率)。因此有必要开发出一套能满足业务快速迭代、健壮、高性能的规则引擎。
3.2 我们预期的规则引擎的样子
1.支持规则优先级 新的同类型的产品,不应该丢掉老版产品的优点,这些优点不仅是优点,还是一种业务开发财产。
2.使用足够简单、灵活。这个要求,对规则在配置上的难易程度提出了要求。本质上是提出了规则 与具体代码之间的界限划分。
第一代规则引擎,足够简单,但没有包含规则表现业务的必要成分,所以注定要被代替。
第二代和第三代规则引擎,很灵活多了,但没有划分清楚规则与具体的代码语言之间的界限,导致他们使用起来注定过于复杂。尤其是你将规则配置工作交给产品、数据分析、数据挖掘的同学,让他们(代码真的不是他们的强项:不要对外界条件给予过高期望;不要相信用户输入)来使用规则和指标来表现他们所做的工作的时候,注定会导致各种个样的问题发生。
所以,如果要足够简单,且足够灵活,我们的目标不仅是让程序员觉得使用简单,还要让无代码开发经验的产品、运营、数据挖掘、数据分析的同学也能觉得使用简单,让他们几乎不需要学习,便能自主配置规则,以此来完成不同领域的业务需求。
通过对代码的分析与抽象,我们发现,所有的代码逻辑由这四种成分构成:逻辑运算,四则运算,if..else选择分支结构,接口API调用。
3.可选择的规则执行模式。因为通过观察各个场景发现,没有一种执行模式是万能的,无论是基于性能考量,还是基于业务本身考量,不同的场景需要不同的执行模式。
4.高性能。这当然是最重要的,如果不能满足高性能,高并发的需求,最终还是会被扔到历史的垃圾堆中。
5.和golang的无缝对接。因为B站业务开发是以golang为主要开发语言,因此,开发的规则引擎必须要要能和golang无缝对接才行。
6.其他的小确幸:支持注释,变量...等等
3.3 基于golang与AST的规则引擎实现
第一代规则引擎解析简单的逻辑表达式,有的是基于正则实现,有的是基于简单的AST(抽象语法树)实现的。如果是简单的逻辑表达式,正则是足够用的。如果仅用AST来解析逻辑表达式,显然有点大材小用。
为了不让抽象语法树(AST)屈才,也受此启发,我们最终选用了基于AST来方式来解析和执行具体的规则语法。我们实现规则引擎时所用到的具体技术如下:
a.基于Antlr4来自定义规则的语法,最终生成语法树结构
b.基于golang的反射技术来实现对用户自定义API的调用
c.基于golang的并发编程技术来实现高性能的规则执行能力
3.3.1 关键核心语法定义
在规则的语法定义好之后,使用idea的antlr4插件,生成遍历语法树的listener和visitor模式的代码。
语法树的扩展能力决定了规则引擎的扩展能力,当需要为规则引擎新增功能时,仅需修改语法定义,重新生成代码即可。我们在使用过程发现,只要不改变语法树的整体结构,新增语法,重新生成代码之后,总能完美兼容老版的规则。
3.3.2 定义语法树节点
具体的代码请查看github:
https://github.com/rencalo770/gengine/tree/master/internal/base
![](https://static001.geekbang.org/infoq/ed/ed23231d83fd5f3ee75a9793ced9d9a3.png)
使用golang代码定义在语法文件中定义的规则语法对应的抽象语法树节点。
将用户输入的字符串,解析为具体的语法时,需要这些定义好的节点来承接具体的数据。在执行具体的规则时,就是在语法树上的遍历递归,就是基于语法树遍历的顺序,来执行这些定义好的节点代码。
这其实也是代码编译器、或执行器的一般过程。任何计算机语言的编写到最终执行,无外乎此过程。
3.3.3 listener模式遍历语法树
使用listener遍历模式来遍历语法树,将定义的语法树节点对应到具体的节点代码实现上:具体代码如下(部分):
listener模式非常简单,无需用户自己控制遍历语法树的过程,解析器会去主动遍历,当遍历到某个用户定义了回调的节点时,会引发用户代码的回调,来执行用户代码逻辑。属“被动模式”。
visitor模式,解析器不会主动去遍历语法树,需要用户自己控制遍历语法树的过程。此模式复杂,但可以满足某些特殊语法的解析需求。属“主动模式”。
因为我们的设计初衷就是简单易用,所以,我们也不会去定义“拗口”的特殊语法来让规则使用者去学习。
3.4 其他核心构件
RuleBuilder.go 用于从字符串中解析出具体的语法树
KnowledgeContext.go 用于存储解析出来的规则
DataContext.go 是用户向规则引擎中添加可用API的接口或结构体
Gengine.go 提供各种规则执行模式的接口
具体代码,详见于github。
3.5 规则引擎支持的执行模式
规则引擎当前支持的执行模式有三种:
a.顺序执行模式
b.并发执行模式
c.混合执行模式
其他执行模式(逆混合模式、桶模式)因当前没有需求场景,所以没有开发实现,如果后续有相关需求(无论是公司内部,还是看到这篇文章的人),都可以去github提issue,说一下自己具体的应用场景,我们如确有必要,我们就会进行这两种模式的开发实现。
3.6 规则引擎测试
一个超级测试:
尽管形式看起来复杂,但其实本质只有4种:
a.逻辑运算
b.四则运算
c.if...else选择结构
d.预加载的API
a、b、c三种形式,学过简单的数学就会用。形式d,仅需简单识别即可。为了进一步简化系统设计和规则配置,用户可以固定一个函数接口,基于改变指标名称的方法取不同的值,这种思路暗合java中当下正在流行的“基于名称的注册与发现式的服务”。操作代码如下:
到了这里,任何人只要学会这4种形式,就可以开始配置规则了。
指标则依赖于具体的业务领域场景,抽象的越好,规则使用也会越简单。这里也有一点小技巧,通常,我们看到的所有数据形式也只有三种:字符串、数字、布尔型。基于此,我们在这3个基础上来抽象具体领域的指标。
另外,规则的解析和规则执行是异步的(用户可以在任何时候解析新来的规则字符串),所以规则引擎特别适合实时的、动态修改、下发规则。
四、gengine规则引擎的使用
4.1 使用情况
当前已经接入了数个场景,并在逐步扩展至更多的业务场景(因为业务脱敏需要,所以不在此详述)。另外,在此规则引擎上,我们构建了规则管理系统和规则服务系统,用于在界面上配置规则,并向各个业务场景实时动态下发规则,无需重启服务。
为了使规则配置更加简单,我们开发了一套可复用于所有场景的指标管理系统(开发以“服务的注册与发现”为导向)。
为了保证在规则变成在运行的代码前尽可能的避免问题或错误,我们在规则从界面提交到之后,在规则管理后台,使用了gengine规则引擎的规则解析模块做了语法校验,如果有语法错误,规则将不会被提交成功。
另外,如果用户想要避免运行时错误,可以在规则管理后台构建规则规则运行环境,使用直接运行的方式来检测错误。
4.2 关于性能
真实的线上grpc服务,单场景线上10个规则,10个4核8G的docker容器,每个规则内都有外部网络请求,压测15分钟,平均2万QPS, 平均响应耗时在2ms到4ms,容器cpu使用率在30%,负载在20%- 30%,但也有极个别请求的耗时在500ms左右,但不超过700ms;
配合实体机使用效果会更好,因为在高并发情况下,容器确实会有一些网络问题。我们在压测日志上看到,规则执行速度都非常好,稳定在2ms-4ms以下,但请求返回外部之后,某些响应的耗时就变得糟糕。
五、gengine对机器学习的支持
5.1 规则学习
如果你看过周志华的《机器学习》这本书,你一定知道“规则学习”(我们配置的规则)也是一种机器学习,“规则学习”也是符合一般机器学习的理论和方法的。如具体场景的“规则学习”针对具体的场景数据(request)识别或处理的结果,也有准确率、精度、召回等一般机器学习的概念上的对应。规则引擎对于这种“硬”“规则学习”,显然是天然支持的。
那么,规则引擎如何支持更一般的机器学习模型调用呢?通常训练出来的模型最终会以API接口的形式向外提供服务,这个正好由函数来支持的,也是在3.6节说的形式d(定义函数)来支持。
另外,通常会一个机器学习模型的待识别的一条数据具有很多特征(feature),feature其实就是规则中的指标。因此,基于3.6节所叙述的,定义好一个接口,基于“名称来访问数据指标”,完全是非常OK的。
5.2 考虑一点性能问题
通常,一个机器学习模型,输入的指标可能多达十几个或者几十个,例如一个复杂的随机森林(Random Forest)模型, 如果要能提供实时的对外服务,当用户提供一个输入,规则引擎可能不得不去查询数十个指标,这些数据指标基本不可能存储在本地。于是,规则引擎不得不通过指标服务的网络调用去取回需要的指标数据。然而,规则引擎只有规则间的并发模式, 没有规则体内的并发执行模式,如果顺序的取指标,假设一个网络指标的服务响应时长是0.5ms(这速度比较OK,redis可以降低至30us-80us,相当乐观),那么如果有20个指标的话,顺序取下来,一个规则耗时会达到10ms,这还没有考虑可能会有很多规则,如果QPS比较高的话,系统基本处于崩溃的边缘。
5.2.1一个例子
曾经,我所在的一个在某行业属独角兽的公司,做风控,以数据过规则的模式来实现风控防刷,使用java实现的drools规则引擎,规则中加载了一个随机森林模型,需要取十几个指标,这些指标还是从redis中取回来的,因为drools只支持顺序执行模式,加载的所有规则都以顺序模式执行,规则内的取指标也不例外。每次一到数据高峰(300-500QPS,其实这个根本算不上高QPS吧?!)的时候,数据就会发生严重堆积,最后经确认,就是这个加载了随机森林的规则,基于uid来取关联指标的时候,因为指标过多,耗时过长导致的。当他们只要把随机森林这个模型规则一停,堆积瞬间消除(狗头尴尬)。
5.2.1 gengine应对这种场景
可能大家很快就能想到,gengine不是天然支持逆混合执行模式吗?我们可以把前n-1个规则做成取数据指标规则,这些取指标规则先并发执行,然后模型识别作为最后一个第n个规则,最后一个执行。这样当然是可以的,但是看起来不是很优雅,因为这种操作模式至少有两种问题存在:
a.把一个规则做成了一个规则池,再添加需要共同生效的规则时,会显得很混乱。
b.只有用户传入的结构体是“超级变量”(可类比于计算机语言中的全局变量,每一个规则类比于定义的一个函数),能被所有规则读取到,如果有n-1个指标要取,那用户不得不定义n-1个结构体字段,来存储这n-1个数据指标,然后使用这个“超级变量”的n-1个字段,将指标带到第n个规则中来执行。这种操作对扩展极为不利,应该也没有人愿意这样做。
基于此考量,在不久,我们会在语法文件中定义如下的语法块:
如上规则代码所示: 语法块"conc{...}"的含义就是并发执行其内部的表达式。以此,便实现了规则内的并发取指标能力。那么最终这n个指标的执行耗时就等于这n个指标中执行时间最长的那个指标耗时。
需要提醒的是,用户如果使用"conc{...}" 语法块,用户应该要保证自己所提供的DataService是线程安全的,或者至少自己能明确,当并发执行内部的所有表达式时,不会引起线程安全问题。其实,只要用户使用包含并发执行的逻辑,用户就应该考虑到线程安全问题。
六、gengine使用教程
第五章所述的conc{}语法块功能已经实现,具体的使用教程可以看这里《gengine官方文档》
七、gengine开源代码地址
github地址: https://github.com/rencalo770/gengine
八、联系我
如果你有任何疑问或建议,可以随时给我发邮件,或者在本文下留言,或者在github上提issue。
我的校友邮箱:M201476117@alumni.hust.edu.cn
我的公司邮箱:renyunyi@bilibili.com(因为公司屏蔽等原因,可能收不到外部邮件,请见谅)
版权声明: 本文为 InfoQ 作者【calo】的原创文章。
原文链接:【http://xie.infoq.cn/article/40bfff1fbca1867991a1453ac】。文章转载请联系作者。
评论 (13 条评论)