什么是规则引擎

规则引擎是处理复杂规则集合的引擎。通过输入一些基础事件，以推演或者归纳等方式，得到最终的执行结果。规则引擎的核心作用在于将复杂、易变的规则从系统中抽离出来，由灵活可变的规则来描述业务需求

Drools 简介

Drools 是 Java 编写的一款开源规则引擎。Drools 的核心算法基于 Rete。早些版本中，Drools 使用的是基于 Rete 二次开发的 ReteOO 算法。在 7.x 版本的 Drools 中，其内部算法已经改为使用 Phreak。Phreak 也是Drools 团队自研的算法，虽然网上关于该算法的资料很少，但是总体来说与 Rete 算法相似。阅读本文之前可以先了解下 Rete 算法

编写一个简单的规则

使用 Drools 需要我们将原有的代码抽象成：Rule（规则） + Fact（事实）

首先我们先来编写一个简单的 demo 用于后文的原理学习

引入 pom 依赖

<properties>
    <drools.version>7.62.0.Final</drools.version>
</properties>
//...
<dependency>
    <groupId>org.drools</groupId>
    <artifactId>drools-compiler</artifactId>
    <version>${drools.version}</version>
</dependency>

<dependency>
    <groupId>org.drools</groupId>
    <artifactId>drools-mvel</artifactId>
    <version>${drools.version}</version>
</dependency>

resource 目录下新建 order.drl

// 包名用于逻辑上区分 rule
package com.example.drools.order;

import com.example.drools.demo.HelloDrools.Order
import com.example.drools.demo.HelloDrools.User
import java.util.ArrayList;

global java.util.List list

// 指定方言为 java
dialect  "java"

// 规则的组成包括，条件（when 部分）和动作（then 部分）
// 当满足 when 时，会执行 then 的逻辑
rule "order can pay"
    when
        // 要求插入的 fact 必须有一个 User 对象
        // 并且 Order fact 必须满足 price < $user.price
        $user: User()
        $order: Order(price < $user.price)
    then
        System.out.println("username:" + $user.getName() + ", order price:" + $order.getPrice());
end

rule "calculate member point"
    when
        $user: User(level > 0)
        $order: Order()
    then
        Double point = $user.getPoint();
        if ($user.getLevel() > 10) {
            $user.setPoint(point + $order.getPrice());
        } else {
            $user.setPoint(point + $order.getPrice() * 0.5);
        }
        System.out.println("previous point:" + point + ", present point:" + $user.getPoint());
end

rule "user age > 18"
    when
        $user: User(age > 18)
    then
        System.out.println("user age > 18");
end

resource 下新建 META-INF\kmodule.xml

<?xml version="1.0" encoding="UTF-8"?>
<kmodule xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xmlns="http://www.drools.org/xsd/kmodule">
</kmodule>

java 代码部分

package com.example.drools.demo;

import lombok.Data;
import org.kie.api.KieServices;
import org.kie.api.runtime.KieContainer;
import org.kie.api.runtime.KieSession;


/**
 * @author tianwen.yin
 */
public class HelloDrools {

    public static void main(String[] args) {
        // 初始化
        KieServices kieServices = KieServices.Factory.get();
        KieContainer kieContainer = kieServices.newKieClasspathContainer();
        KieSession kieSession = kieContainer.newKieSession();
        // 构建 fact
        User user = new User();
        user.setName("taven");
        user.setPoint(10D);
        user.setLevel(5);
        user.setPrice(100D);
        user.setAge(19);

        Order order = new Order();
        order.setPrice(58D);
        // insert fact
        kieSession.insert(user);
        kieSession.insert(order);
        // 触发所有规则
        int fireCount = kieSession.fireAllRules();
        System.out.println("fireRuleCount:" + fireCount);
        kieSession.dispose();
    }

    @Data
    public static class Order {
        private Double price;
    }

    @Data
    public static class User {
        private String name;
        private Integer age;
        private Double price;
        private Integer level;
        private Double point;
    }

}

执行结果如下

username:taven, order price:58.0
previous point:10.0, present point:39.0
user age > 18
fireRuleCount:3

Drools 执行流程浅析

Drools 的使用看起来还是比较简单的，但是实际上真正落地使用还是需要详读官方文档的，不是本文重点，就不多赘述了。接下来我们进入正题，分析下执行流程

上述的图，是我结合源码总结的 Drools 执行流程图，最终目的就是根据插入的 fact 进行推演，如果能走到最后的 Terminal 节点则代表规则会被执行

我们先来了解一下上图中的所有节点

Object Type Node：简称 OTN，fact 会根据类型流转到不同的 OTN
Alpha Node：也被称为单输入节点，所有单对象的约束条件都会被构建为 Alpha 节点，例如 “age > 18”，”leve > 0”
Beta Node：双输入节点，不同对象之间的约束会被构建为 Beta 节点，例如 “order.price > user.price”；当一个节点需要同时满足多个单对象约束时也是 Beta 节点；一个节点有超过两个条件约束时，会构建为多个 Beta 节点相连

Beta 节点又分为 Join，Not，Exist 等，本文主要以 Join 节点为例进行说明。对于其他节点来说流程也是一样的，只不过某些具体细节的实现不同

补充一张多 Beta 节点相连的图

LeftInputAdapterNode：左输入节点，这个节点的作用我最开始也很迷惑。后来在反复 Debug 后终于顿悟了，Beta 节点被设计成只存储右侧进入的 fact，左侧的数据来自 LeftInputAdapterNode 或者另一个 Beta 节点（可能理解不了，请继续往下读）
Rule Terminal：当一个 fact 流转到 Terminal 时，代表当前 fact 会触发该规则
内存结构：关于 Drools 内存结构这块，与传统 RETE 算法不太一样，我也没有太仔细的研究这块，上图中只是把会存储 fact 的位置标识了出来

实际上 Drools 的源码非常复杂，其中包含的节点远不止提到的这些，我这里仅是基于 RETE 算法的核心内容来刨析下 Drools 原理

注：这里我补充下，Beta 节点的右侧分支，在进入到 Beta 之前，也是可以有 Alpha 节点的。并且当多个 rule 中包含相同条件时也会共用分支。改图和编 demo 实在太麻烦了

准备环节

在解析规则文件时，应该就已经创建了类似上图的节点关系（这个具体源码没有阅读）
上述示例中，kieSession.insert(user); 会将 fact 插入到 PropagationList
调用 kieSession.fireAllRules(); 后，进入到规则引擎核心环节

fireAllRules

字面意思已经很明显了，触发 Session 中的所有规则

flush 阶段

传播 PropagationList 中所有 fact，对照上图中 flush，OTN 下游的所有分支都会遍历访问

如果某条分支全部都是 Alpha 节点的话，可以直接传播到 Terminal 节点
如果 fact 流转到 LeftInputAdapterNode 的话，会将 fact 存储在 LeftInputAdapterNode 对应的内存中
如果 fact 流转到 Beta 节点右侧的话，会将 fact 存储在 Beta 节点的右侧

当分支走到 Alpha Terminal 节点时，构建一个 RuleAgendaItem 插入到 InternalAgendaGroup 中。这个动作代表当前规则需要进行下一个阶段 evaluateAndFire

Beta 节点的逻辑是，当所有的分支入口都存储了数据时，插入 InternalAgendaGroup（这句话可能不太好理解，当仅有一个 Beta 节点时，左右都存储了数据，就会插入 InternalAgendaGroup。如果是多个 Beta 节点相连的话，必须要满足第一个 Beta 的左右，以及下游所有 Beta 的右节点都有数据时才会插入 InternalAgendaGroup）。

evaluate（评估）

纯 Alpha 节点的分支，是没有这个步骤的

以 Beta 节点为例，evaluate 就是基于左右内存进行匹配，找到所有配对成功的数据放入一个集合，将这个集合继续带入到下一个节点，下个节点又可能是 Beta 节点或者 Terminal 节点。

如果是 Beta 节点的话，则继续进行匹配，配对成功的集合带入到下一个节点…
如果是 Terminal 节点的话，会将数据插入到 RuleExecutor 的 tupleList 中。这步又是啥意思呢，tupleList 的数据代表，这些数据会真正的代入到规则执行当中去（Alpha Terminal 也会执行这个操作）

Beta 节点这里还有一个细节，就是在进行左右配对的时候，并不只是遍历查找，而是在条件允许的情况下，Drools 在存储这些数据的时候会建立索引。上述示例的话，并没有建立索引，随便把条件改成 xx.a = yy.b 这种条件的话，就会建立索引。具体索引的实现也很简单，Drools 实现了一个类似 HashMap 的结构来管理索引，感兴趣的同学可以自己打个断点 debug 下。

断点 Class：PhreakJoinNode

注：上图中两个位置，只有一处会被执行

fire

这里会遍历 RuleExecutor 的 tupleList 执行这些规则。我们的规则文件在 Drools 运行时会被编译成字节码动态执行，具体这块具体用啥实现的没研究。

fire 阶段还有一个细节就是，我们的规则文件内部是可以调用 insert modify 这些函数的，这些 fact 同样会被插入到 PropagationList 中，内部也会再执行一次 PropagationList flush 操作。整个 fireAllRules 方法内部是一个循环，如果 fire 内部的 fact 命中了规则的话，在 fire 结束后还会继续执行 evaluateAndFire 直到全部触发完为止（所以在规则编写错误的情况下，Drools 可能进入死循环）

Conflict resolution

冲突解决简单来说就是，当我们知道了要执行的规则都有哪些时，还需要明确这些规则执行的顺序。

Drools 这里如何解决顺序问题的呢？回顾一下上面提到的 flush 阶段。RuleAgendaItem 插入到 InternalAgendaGroup 中这一步，InternalAgendaGroup 的默认实现为 AgendaGroupQueueImpl，AgendaGroupQueueImpl 中使用了 BinaryHeapQueue（二叉堆队列）来存储元素

通过二叉堆算法保证每次队列弹出优先级最高的规则，优先级的计算通过 PhreakConflictResolver 来完成

PhreakConflictResolver 从两个方面来判断优先级

规则是否声明 salience（salience 越大，优先级越高）
无法通过 salience 来计算的话，则通过规则 loadOrder 来决定优先级（规则在文件中越靠前则 loadOrder 就越高）

总结下

Drools 这种算法逻辑有什么好处呢？下述结论参考了 https://en.wikipedia.org/wiki/Rete_algorithm

通过共享节点来减少节点的冗余（如果多个 Rule 中有相同的条件，不会重复计算）
fact 的变化，不需要完全重新评估，只需要进行增量评估（只需要对 fact 对应的 OTN 重新评估就可以）
支持高效的删除 fact （从 Drools 的角度来看这句话，fact 存储时会建立一个双向关联，也就是 fact 知道自己被哪些节点存储了，所以可以高效的删除）

本文介绍了 Drools 的执行流程，由于网上没有找到太多参考资料，大多数结论都是我自己总结出来的，如果有写错的地方欢迎各位指正。

最后

如果觉得我的文章对你有帮助，欢迎点赞，关注，转发。你的支持是对我最大的帮助

欢迎关注公众号【殷天文】

规则引擎 Drools 执行流程浅析