什么是規(guī)則引擎

規(guī)則引擎是處理復(fù)雜規(guī)則集合的引擎苛吱。通過(guò)輸入一些基礎(chǔ)事件，以推演或者歸納等方式器瘪，得到最終的執(zhí)行結(jié)果翠储。規(guī)則引擎的核心作用在于將復(fù)雜、易變的規(guī)則從系統(tǒng)中抽離出來(lái)橡疼，由靈活可變的規(guī)則來(lái)描述業(yè)務(wù)需求

Drools 簡(jiǎn)介

Drools 是 Java 編寫(xiě)的一款開(kāi)源規(guī)則引擎援所。Drools 的核心算法基于 Rete。早些版本中衰齐，Drools 使用的是基于 Rete 二次開(kāi)發(fā)的 ReteOO 算法任斋。在 7.x 版本的 Drools 中，其內(nèi)部算法已經(jīng)改為使用 Phreak。Phreak 也是Drools 團(tuán)隊(duì)自研的算法废酷，雖然網(wǎng)上關(guān)于該算法的資料很少瘟檩，但是總體來(lái)說(shuō)與 Rete 算法相似。閱讀本文之前可以先了解下 Rete 算法

編寫(xiě)一個(gè)簡(jiǎn)單的規(guī)則

使用 Drools 需要我們將原有的代碼抽象成：Rule（規(guī)則） + Fact（事實(shí)）

首先我們先來(lái)編寫(xiě)一個(gè)簡(jiǎn)單的 demo 用于后文的原理學(xué)習(xí)

1. 引入 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>

2. resource 目錄下新建 order.drl

// 包名用于邏輯上區(qū)分 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"

// 規(guī)則的組成包括澈蟆，條件（when 部分）和動(dòng)作（then 部分）
// 當(dāng)滿足 when 時(shí)墨辛，會(huì)執(zhí)行 then 的邏輯
rule "order can pay"
    when
        // 要求插入的 fact 必須有一個(gè) User 對(duì)象
        // 并且 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>

3. 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();
        // 構(gòu)建 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);
        // 觸發(fā)所有規(guī)則
        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;
    }

}

4. 執(zhí)行結(jié)果如下

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

Drools 執(zhí)行流程淺析

Drools 的使用看起來(lái)還是比較簡(jiǎn)單的，但是實(shí)際上真正落地使用還是需要詳讀官方文檔的趴俘，不是本文重點(diǎn)睹簇，就不多贅述了。接下來(lái)我們進(jìn)入正題寥闪，分析下執(zhí)行流程

上述的圖太惠，是我結(jié)合源碼總結(jié)的 Drools 執(zhí)行流程圖，最終目的就是根據(jù)插入的 fact 進(jìn)行推演疲憋，如果能走到最后的 Terminal 節(jié)點(diǎn)則代表規(guī)則會(huì)被執(zhí)行

我們先來(lái)了解一下上圖中的所有節(jié)點(diǎn)

• Object Type Node：簡(jiǎn)稱 OTN凿渊，fact 會(huì)根據(jù)類型流轉(zhuǎn)到不同的 OTN

• Alpha Node：也被稱為單輸入節(jié)點(diǎn)，所有單對(duì)象的約束條件都會(huì)被構(gòu)建為 Alpha 節(jié)點(diǎn)缚柳，例如 "age > 18"埃脏，"leve > 0"

• Beta Node：雙輸入節(jié)點(diǎn)，不同對(duì)象之間的約束會(huì)被構(gòu)建為 Beta 節(jié)點(diǎn)秋忙，例如 "order.price > user.price"彩掐；當(dāng)一個(gè)節(jié)點(diǎn)需要同時(shí)滿足多個(gè)單對(duì)象約束時(shí)也是 Beta 節(jié)點(diǎn)；一個(gè)節(jié)點(diǎn)有超過(guò)兩個(gè)條件約束時(shí)灰追，會(huì)構(gòu)建為多個(gè) Beta 節(jié)點(diǎn)相連

  Beta 節(jié)點(diǎn)又分為 Join堵幽，Not，Exist 等弹澎，本文主要以 Join 節(jié)點(diǎn)為例進(jìn)行說(shuō)明谐檀。對(duì)于其他節(jié)點(diǎn)來(lái)說(shuō)流程也是一樣的，只不過(guò)某些具體細(xì)節(jié)的實(shí)現(xiàn)不同

  補(bǔ)充一張多 Beta 節(jié)點(diǎn)相連的圖

  
  

• LeftInputAdapterNode：左輸入節(jié)點(diǎn)裁奇，這個(gè)節(jié)點(diǎn)的作用我最開(kāi)始也很迷惑。后來(lái)在反復(fù) Debug 后終于頓悟了麦撵，Beta 節(jié)點(diǎn)被設(shè)計(jì)成只存儲(chǔ)右側(cè)進(jìn)入的 fact刽肠，左側(cè)的數(shù)據(jù)來(lái)自 LeftInputAdapterNode 或者另一個(gè) Beta 節(jié)點(diǎn)（可能理解不了，請(qǐng)繼續(xù)往下讀）

• Rule Terminal：當(dāng)一個(gè) fact 流轉(zhuǎn)到 Terminal 時(shí)免胃，代表當(dāng)前 fact 會(huì)觸發(fā)該規(guī)則

• 內(nèi)存結(jié)構(gòu)：關(guān)于 Drools 內(nèi)存結(jié)構(gòu)這塊音五，與傳統(tǒng) RETE 算法不太一樣，我也沒(méi)有太仔細(xì)的研究這塊羔沙，上圖中只是把會(huì)存儲(chǔ) fact 的位置標(biāo)識(shí)了出來(lái)

實(shí)際上 Drools 的源碼非常復(fù)雜躺涝，其中包含的節(jié)點(diǎn)遠(yuǎn)不止提到的這些，我這里僅是基于 RETE 算法的核心內(nèi)容來(lái)刨析下 Drools 原理

注：這里我補(bǔ)充下扼雏，Beta 節(jié)點(diǎn)的右側(cè)分支坚嗜，在進(jìn)入到 Beta 之前夯膀，也是可以有 Alpha 節(jié)點(diǎn)的。并且當(dāng)多個(gè) rule 中包含相同條件時(shí)也會(huì)共用分支苍蔬。改圖和編 demo 實(shí)在太麻煩了

準(zhǔn)備環(huán)節(jié)

1. 在解析規(guī)則文件時(shí)诱建，應(yīng)該就已經(jīng)創(chuàng)建了類似上圖的節(jié)點(diǎn)關(guān)系（這個(gè)具體源碼沒(méi)有閱讀）

2. 上述示例中，kieSession.insert(user); 會(huì)將 fact 插入到 PropagationList

3. 調(diào)用 kieSession.fireAllRules(); 后碟绑，進(jìn)入到規(guī)則引擎核心環(huán)節(jié)

fireAllRules

字面意思已經(jīng)很明顯了俺猿，觸發(fā) Session 中的所有規(guī)則

flush 階段

傳播 PropagationList 中所有 fact，對(duì)照上圖中 flush格仲，OTN 下游的所有分支都會(huì)遍歷訪問(wèn)

1. 如果某條分支全部都是 Alpha 節(jié)點(diǎn)的話押袍，可以直接傳播到 Terminal 節(jié)點(diǎn)
2. 如果 fact 流轉(zhuǎn)到 LeftInputAdapterNode 的話，會(huì)將 fact 存儲(chǔ)在 LeftInputAdapterNode 對(duì)應(yīng)的內(nèi)存中
3. 如果 fact 流轉(zhuǎn)到 Beta 節(jié)點(diǎn)右側(cè)的話凯肋，會(huì)將 fact 存儲(chǔ)在 Beta 節(jié)點(diǎn)的右側(cè)

當(dāng)分支走到 Alpha Terminal 節(jié)點(diǎn)時(shí)谊惭，構(gòu)建一個(gè) RuleAgendaItem 插入到 InternalAgendaGroup 中。這個(gè)動(dòng)作代表當(dāng)前規(guī)則需要進(jìn)行下一個(gè)階段 evaluateAndFire

Beta 節(jié)點(diǎn)的邏輯是否过，當(dāng)所有的分支入口都存儲(chǔ)了數(shù)據(jù)時(shí)午笛，插入 InternalAgendaGroup（這句話可能不太好理解，當(dāng)僅有一個(gè) Beta 節(jié)點(diǎn)時(shí)苗桂，左右都存儲(chǔ)了數(shù)據(jù)药磺，就會(huì)插入 InternalAgendaGroup。如果是多個(gè) Beta 節(jié)點(diǎn)相連的話煤伟，必須要滿足第一個(gè) Beta 的左右癌佩，以及下游所有 Beta 的右節(jié)點(diǎn)都有數(shù)據(jù)時(shí)才會(huì)插入 InternalAgendaGroup）。

evaluate（評(píng)估）

純 Alpha 節(jié)點(diǎn)的分支便锨，是沒(méi)有這個(gè)步驟的

以 Beta 節(jié)點(diǎn)為例围辙，evaluate 就是基于左右內(nèi)存進(jìn)行匹配，找到所有配對(duì)成功的數(shù)據(jù)放入一個(gè)集合放案，將這個(gè)集合繼續(xù)帶入到下一個(gè)節(jié)點(diǎn)姚建，下個(gè)節(jié)點(diǎn)又可能是 Beta 節(jié)點(diǎn)或者 Terminal 節(jié)點(diǎn)。

• 如果是 Beta 節(jié)點(diǎn)的話吱殉，則繼續(xù)進(jìn)行匹配掸冤，配對(duì)成功的集合帶入到下一個(gè)節(jié)點(diǎn)...
• 如果是 Terminal 節(jié)點(diǎn)的話，會(huì)將數(shù)據(jù)插入到 RuleExecutor 的 tupleList 中友雳。這步又是啥意思呢稿湿，tupleList 的數(shù)據(jù)代表，這些數(shù)據(jù)會(huì)真正的代入到規(guī)則執(zhí)行當(dāng)中去（Alpha Terminal 也會(huì)執(zhí)行這個(gè)操作）

Beta 節(jié)點(diǎn)這里還有一個(gè)細(xì)節(jié)押赊，就是在進(jìn)行左右配對(duì)的時(shí)候误澳，并不只是遍歷查找礼殊，而是在條件允許的情況下斥杜，Drools 在存儲(chǔ)這些數(shù)據(jù)的時(shí)候會(huì)建立索引。上述示例的話罗丰，并沒(méi)有建立索引，隨便把條件改成 xx.a = yy.b 這種條件的話咽袜，就會(huì)建立索引丸卷。具體索引的實(shí)現(xiàn)也很簡(jiǎn)單，Drools 實(shí)現(xiàn)了一個(gè)類似 HashMap 的結(jié)構(gòu)來(lái)管理索引询刹，感興趣的同學(xué)可以自己打個(gè)斷點(diǎn) debug 下谜嫉。

斷點(diǎn) Class：PhreakJoinNode

注：上圖中兩個(gè)位置，只有一處會(huì)被執(zhí)行

fire

這里會(huì)遍歷 RuleExecutor 的 tupleList 執(zhí)行這些規(guī)則凹联。我們的規(guī)則文件在 Drools 運(yùn)行時(shí)會(huì)被編譯成字節(jié)碼動(dòng)態(tài)執(zhí)行沐兰，具體這塊具體用啥實(shí)現(xiàn)的沒(méi)研究。

fire 階段還有一個(gè)細(xì)節(jié)就是蔽挠，我們的規(guī)則文件內(nèi)部是可以調(diào)用 insert modify 這些函數(shù)的住闯，這些 fact 同樣會(huì)被插入到 PropagationList 中，內(nèi)部也會(huì)再執(zhí)行一次 PropagationList flush 操作澳淑。整個(gè) fireAllRules 方法內(nèi)部是一個(gè)循環(huán)比原，如果 fire 內(nèi)部的 fact 命中了規(guī)則的話，在 fire 結(jié)束后還會(huì)繼續(xù)執(zhí)行 evaluateAndFire 直到全部觸發(fā)完為止（所以在規(guī)則編寫(xiě)錯(cuò)誤的情況下杠巡，Drools 可能進(jìn)入死循環(huán)）

Conflict resolution

沖突解決簡(jiǎn)單來(lái)說(shuō)就是量窘，當(dāng)我們知道了要執(zhí)行的規(guī)則都有哪些時(shí)，還需要明確這些規(guī)則執(zhí)行的順序氢拥。

Drools 這里如何解決順序問(wèn)題的呢蚌铜？回顧一下上面提到的 flush 階段。RuleAgendaItem 插入到 InternalAgendaGroup 中這一步嫩海，InternalAgendaGroup 的默認(rèn)實(shí)現(xiàn)為 AgendaGroupQueueImpl冬殃，AgendaGroupQueueImpl 中使用了 BinaryHeapQueue（二叉堆隊(duì)列）來(lái)存儲(chǔ)元素

通過(guò)二叉堆算法保證每次隊(duì)列彈出優(yōu)先級(jí)最高的規(guī)則，優(yōu)先級(jí)的計(jì)算通過(guò) PhreakConflictResolver 來(lái)完成

PhreakConflictResolver 從兩個(gè)方面來(lái)判斷優(yōu)先級(jí)

1. 規(guī)則是否聲明 salience（salience 越大叁怪，優(yōu)先級(jí)越高）
2. 無(wú)法通過(guò) salience 來(lái)計(jì)算的話审葬，則通過(guò)規(guī)則 loadOrder 來(lái)決定優(yōu)先級(jí)（規(guī)則在文件中越靠前則 loadOrder 就越高）

總結(jié)下

Drools 這種算法邏輯有什么好處呢？下述結(jié)論參考了 https://en.wikipedia.org/wiki/Rete_algorithm

1. 通過(guò)共享節(jié)點(diǎn)來(lái)減少節(jié)點(diǎn)的冗余（如果多個(gè) Rule 中有相同的條件奕谭，不會(huì)重復(fù)計(jì)算）

2. fact 的變化耳璧，不需要完全重新評(píng)估，只需要進(jìn)行增量評(píng)估（只需要對(duì) fact 對(duì)應(yīng)的 OTN 重新評(píng)估就可以）

3. 支持高效的刪除 fact （從 Drools 的角度來(lái)看這句話展箱，fact 存儲(chǔ)時(shí)會(huì)建立一個(gè)雙向關(guān)聯(lián)，也就是 fact 知道自己被哪些節(jié)點(diǎn)存儲(chǔ)了蹬昌，所以可以高效的刪除）

本文介紹了 Drools 的執(zhí)行流程混驰，由于網(wǎng)上沒(méi)有找到太多參考資料，大多數(shù)結(jié)論都是我自己總結(jié)出來(lái)的，如果有寫(xiě)錯(cuò)的地方歡迎各位指正栖榨。

最后

如果覺(jué)得我的文章對(duì)你有幫助昆汹，歡迎點(diǎn)贊，關(guān)注婴栽，轉(zhuǎn)發(fā)满粗。你的支持是對(duì)我最大的幫助