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

什么是規(guī)則引擎

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

Drools 簡介

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 算法

編寫一個簡單的規(guī)則

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

首先我們先來編寫一個簡單的 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 部分）和動作（then 部分）
// 當(dāng)滿足 when 時，會執(zhí)行 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>
  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 的使用看起來還是比較簡單的，但是實(shí)際上真正落地使用還是需要詳讀官方文檔的，不是本文重點(diǎn)，就不多贅述了。接下來我們進(jìn)入正題，分析下執(zhí)行流程

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

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

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

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

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

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

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


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

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

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

實(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)多個 rule 中包含相同條件時也會共用分支。改圖和編 demo 實(shí)在太麻煩了

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

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

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

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

fireAllRules

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

flush 階段

傳播 PropagationList 中所有 fact，對照上圖中 flush，OTN 下游的所有分支都會遍歷訪問

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

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

Beta 節(jié)點(diǎn)的邏輯是，當(dāng)所有的分支入口都存儲了數(shù)據(jù)時，插入 InternalAgendaGroup（這句話可能不太好理解，當(dāng)僅有一個 Beta 節(jié)點(diǎn)時，左右都存儲了數(shù)據(jù)，就會插入 InternalAgendaGroup。如果是多個 Beta 節(jié)點(diǎn)相連的話，必須要滿足第一個 Beta 的左右，以及下游所有 Beta 的右節(jié)點(diǎn)都有數(shù)據(jù)時才會插入 InternalAgendaGroup）。

evaluate（評估）

純 Alpha 節(jié)點(diǎn)的分支，是沒有這個步驟的

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

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

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

斷點(diǎn) Class：PhreakJoinNode

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

fire

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

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

Conflict resolution

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

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

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

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

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

總結(jié)下

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

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

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

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

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

最后

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

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

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

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