規(guī)則引擎 Drools 執(zhí)行流程淺析

什么是規(guī)則引擎

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

Drools 簡(jiǎn)介

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

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

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

首先我們先來編寫一個(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>
  1. 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>
  1. 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;
    }

}
  1. 執(zhí)行結(jié)果如下
username:taven, order price:58.0
previous point:10.0, present point:39.0
user age > 18
fireRuleCount:3

Drools 執(zhí)行流程淺析

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

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

我們先來了解一下上圖中的所有節(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)有超過兩個(gè)條件約束時(shí)，會(huì)構(gòu)建為多個(gè) Beta 節(jié)點(diǎn)相連

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

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


  • LeftInputAdapterNode：左輸入節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的作用我最開始也很迷惑。后來在反復(fù) Debug 后終于頓悟了，Beta 節(jié)點(diǎn)被設(shè)計(jì)成只存儲(chǔ)右側(cè)進(jìn)入的 fact，左側(cè)的數(shù)據(jù)來自 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 算法不太一樣，我也沒有太仔細(xì)的研究這塊，上圖中只是把會(huì)存儲(chǔ) fact 的位置標(biāo)識(shí)了出來

實(shí)際上 Drools 的源碼非常復(fù)雜，其中包含的節(jié)點(diǎn)遠(yuǎn)不止提到的這些，我這里僅是基于 RETE 算法的核心內(nè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è)具體源碼沒有閱讀）

  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ì)遍歷訪問

  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)的分支，是沒有這個(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ì)建立索引。上述示例的話，并沒有建立索引，隨便把條件改成 xx.a = yy.b 這種條件的話，就會(huì)建立索引。具體索引的實(shí)現(xiàn)也很簡(jiǎn)單，Drools 實(shí)現(xiàn)了一個(gè)類似 HashMap 的結(jié)構(gòu)來管理索引，感興趣的同學(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)的沒研究。

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ī)則編寫錯(cuò)誤的情況下，Drools 可能進(jìn)入死循環(huán)）

Conflict resolution

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

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

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

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

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

總結(jié)下

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

  1. 通過共享節(jié)點(diǎn)來減少節(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 的角度來看這句話，fact 存儲(chǔ)時(shí)會(huì)建立一個(gè)雙向關(guān)聯(lián)，也就是 fact 知道自己被哪些節(jié)點(diǎn)存儲(chǔ)了，所以可以高效的刪除）

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

最后

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容