基于Rete 算法的Urule 规则引擎 设计与实现

6,158 阅读7分钟

1. 概要

规则引擎由推理引擎发展而来,是一种嵌入在应用程序中的组件,实现了将业务决策从应用程序代码中分离出来,并使用预定义的语义模块编写业务决策。接受数据输入,解释业务规则,并根据规则做出业务决策。

概念解析:

  • Fact: 业务数据对象,在规则中相当于变量对象

  • Rule:规则,相当于一个if then的逻辑体,同事本身包含属性

  • Module:模式,相当于一个判断,A>10

  • WorkingMemory:工作区,相当于一个内存的执行空间,一批规则都在一个执行空间中执行,所有的fact也存储于该内存空间

  • Session:会话,一个工作区对应于一个会话,包含参数和执行流程的规则

  • Rete:规则网络,rule的lhs部分的执行网络

  • Agenda:议程,决定执行哪些rhs的Action

2. Rule 模块说明

rule是规则管理系统中每一个子规则对应的实体,起主要包含lhs,rhs,other,分别对应 if-then-else 的逻辑表达 Urule-Rule.png

原图:www.processon.com/view/link/5…

  • lhs

    lhs存储的是一颗规则树,树中的每一个节点用Criterion接口来标示

        public interface Criterion{
            Junction getParent();
             void setParent(Junction parent);
        }
    

    Criterion 的主要实现Criteria和Junction,分别代表一个条件明细(left op value,如age > 10) 和一个联合条件(and/or)

  • rhs/other

    rule是最原子的规则,只包含单层的if-else-then,没有嵌套的if-else,所以rhs/other对应的都是一系列的动作,即Action

    public class Rhs {
      private List<Action> actions;
    ​
      public List<Action> getActions() {
        return actions;
      }
      
      public void setActions(List<Action> actions) {
        this.actions = actions;
        Collections.sort(actions);
      }
      
      public void addAction(Action action) {
        if(actions==null){
          actions=new ArrayList<Action>();
        }
        actions.add(action);
        Collections.sort(actions);
      }
    }
    

3. KnowledgeSession 模块说明

  • 各种Context是规则执行时候需要用到的上下文

  • ReteInstance用于执行所有规则的LHS,Agenda用于执行所有规则的RHS

  • KnowledgeSession是规则引擎对客户端暴露的接口,使用KnowlegeSessionFactory进行生成,需要传入KnowledgePackage,KnowledgePackage对应的是规则配置系统中的知识包

  • KnowledgeSession继承了WorkingMemory接口,拥有了维护变量对象的功能,可以通过insert()方法插入一个业务变量实体,fileRule是的时候可以通过paramters参数设置参数数据

  • 通过调用KnowledgeSession 的fireRule()方法开始进行规则计算,其最后会调用execute()方法进行执行,execute()方法首先对变量库和参数库进行归一,形成fact数组,然后调用ReteInstance的enter()方法执行规则的LHS,最后调用Agenda的execute方法执行规则的RHS

private RuleExecutionResponse execute(AgendaFilter filter, Map<String, Object> params,int max){
		this.parameterMap.clear();
		this.clearInitParameters();
		this.parameterMap.putAll(initParameters);
		// 变量是map
		for(Map<?,?> map:factMaps){
			for(Object key:map.keySet()){
				this.parameterMap.put(key.toString(), map.get(key));
			}
		}
		// 参数
		if(params!=null){
			this.parameterMap.putAll(params);
		}
		if(!facts.contains(parameterMap)){
			facts.add(parameterMap);
		}
		long start=System.currentTimeMillis();
		for(Object fact:facts){
			evaluationRete(fact);
		}
		evaluationContext.clean();
		buildElseRules(true);
		ExecutionResponseImpl resp=(ExecutionResponseImpl)agenda.execute(filter,max);
		resp.setDuration(System.currentTimeMillis()-start);
		reset();
		return resp;
	}
	
private void evaluationRete(Object fact) {
		for(ReteInstance reteInstance:reteInstanceList){
			Collection<FactTracker> trackers=reteInstance.enter(evaluationContext, fact);
			if(trackers!=null){
				agenda.addTrackers(trackers);
			}			
		}
	}

4. Rete 模块说明

rete是对执行LHS(规则)的流程封装,多个Rule的LHS交织在一起,组成一张有向无环图(DAG),起点是各个实体数据的输入(Object),经过每一个具体条件(Criteria)和联合添加(And/Or),最终如果符合某一个LHS的所有规则,则会到达终点(规则的定义-Terminal)

rete是通过DAG的形式保存在规则管理系统中,当规则引擎请求到一个规则的时候拿到的是一张Node图,Node图只表示了规则的定义但不能执行,然后其中的每个Node会调用toActivity方法进而生成一张Activity图,Activity用于执行

  • ObjectTypeNode/ObjectTypeActivity

    ObjectType对应的是规则使用的变量库/参数库的类型,该类节点是DAG的起点

  • JunctionNode/JoinActivity

    Junction有两个子类And和Or,分别对应的是联合调解

  • CriteriaNode/CriteriaActivity

    Criteria对应的是UI中的每一个条件明细,比如[用户.年龄>18]

  • Line/Path

    Line和Path标示的是DAG中的边的关系,其作为from节点实例的属性,保存了to节点的实例

  • ValueCompute

    valueCompute用于所有子表达式的计算,如变量赋值,函数执行,方法执行,控制台输出等

  • FactTracker

    FactTracker用于追踪每一个需要计算的数据实体,如果一个数据实体通过DAG的所有规则判断,到达了一个终点,会将终点内保存的规则(Rule)以及改对象保存在FactTracker中,该数据结构作为Rete模块的输出和Agenda模块的输入

  • ReteInstance

    ReteInstance封装了所有的ObjectTypeActivity(即DAG的起点),对KnowledgeSession提供统一的接口调用

    通过调用ReteInstance.enter()方法,进而以此调用所有Activity的enter()方法来完成整个LHS的判断,并返回Collection

一个DAG的示例如下:

5.agenda模块说明

agenda是对执行RHS(动作)的流程封装,规则引擎可以将多个规则换分成不同的组,属于相同组的规则的RHS会按照组的定义来执行,目前有三种组

1. 互斥组(activation-group):系统会自动将此属性相同的规则划为一组,且这个组中只有一个规则会执行,待执行的规则如设置了优先级,则优先级最高的规则执行,否则随机;

2. 执行组(agenda-group):系统会自动将此属性相同的规则划为一组,默认情况下,引擎不会执行这个组里的规则,需要我们在定义规则动作时利用系统内置的函数显示的指定要激活执行的执行组名,这样系统才会尝试匹配并执行组里的规则。

3. 默认组:不属于互斥组和执行组的规则都会被划分在默认组,默认组的规则会被顺序执行

需要注意的是,一个规则只会被划分到一个组,如果一个规则定义了多个组的属性,会按照执行组>互斥组>默认组的顺序依次判断该规则需要被添加到哪个组

下面看下agenda模块的UML类图

  • Activation

    Activation是用来具体执行RHS的接口,里面封装了rule和rule作用的对象(objectCriteriaMap的key),具体执行代码在 com.bstek.urule.action.Action#execute 106 行

    Rhs rhs=rule.getRhs();
          if(rhs!=null){
            List<Action> actions=rhs.getActions();
            if(actions!=null){
              for(Action action:actions){
                if(rule.getDebug()!=null){
                  action.setDebug(rule.getDebug());             
                }
                ActionValue actionValue=action.execute(context,objectCriteriaMap.keySet(),matchedObjects,varia    bleMap);
                if(actionValue!=null){
                  actionValues.add(actionValue);
                }
              }
            }
          }
    
  • RuleGroup

    RuleGroup对应的是上面提到的组的概念

    ActivationGroup 是互斥组,即该组内的Activation只会执行一个,所以执行完后会清楚该组所有Activation,对应代码为com.bstek.urule.runtime.agenda.ActivationGroup#execute:40

    AgendaGroup 是执行组,该组内获取焦点的规则都会执行,获取焦点有两种方式,一是在UI上配置自动获取焦点的属性,二是直接调用com.bstek.urule.runtime.agenda.AgendaGroup#setFocus使得整个组获取焦点

    默认组实际上就是顺序执行不在互斥组和执行组里的规则,所以没有对应的RuleGroup

  • RuleBox

    RuleBox 将相同的RuleGroup放在一起,执行的时候顺序执行,不同类型的RuleBox封装了对应的RuleGroup

    ActivationRuleBox(默认组) 没有 group 的概念,执行的时候直接顺序执行Activation,所以也没有RuleGroup类

    ActivationGroupRuleBox(互斥组)和AgendaGroupRuleBox(执行组) 都有 group 的概念,在UI上定义的group名一样的划分为一组,执行的时候是分组执行,所以都有对应RuleGroup类

    但ActivationGroupRuleBox和AgendaGroupRuleBox这两个类的group按顺序执行的逻辑是一模一样的,区别在于RuleGroup类的实现

  • Agenda

    Agenda封装了所有的 RuleBox,对KnowledgeSession提供统一的接口调用

    通过调用Agenda.execute()方法会依次调用所有组的规则,并将结果封装成RuleExecutionResponse

    通过调用Agenda.addTrackers()方法接受Rete模块执行的结果,并取出其中的Activation放进对应的RuleBox