前言

在很多企業(yè)的 IT 業(yè)務(wù)系統(tǒng)中，經(jīng)常會有大量的業(yè)務(wù)規(guī)則配置，而且隨著企業(yè)管理者的決策變化，這些業(yè)務(wù)規(guī)則也會隨之發(fā)生更改。為了適應(yīng)這樣的需求，我們的 IT 業(yè)務(wù)系統(tǒng)應(yīng)該能快速且低成本的更新。適應(yīng)這樣的需求，一般的作法是將業(yè)務(wù)規(guī)則的配置單獨拿出來，使之與業(yè)務(wù)系統(tǒng)保持低耦合。目前，實現(xiàn)這樣的功能的程序，已經(jīng)被開發(fā)成為規(guī)則引擎。

規(guī)則引擎是一種推理引擎，它是根據(jù)已有的事實，從規(guī)則知識庫中匹配規(guī)則，并處理存在沖突的規(guī)則，執(zhí)行最后篩選通過的規(guī)則。因此，規(guī)則引擎是人工智能（AI）研究領(lǐng)域的一部分，具有一定的選擇判斷性、人工智能性和富含知識性。目前，比較流行的規(guī)則引擎有商業(yè)規(guī)則引擎 iLog 和開源規(guī)則引擎 drools。本文將對開源規(guī)則引擎 drools 做詳細(xì)介紹，并通過分析一個在汽車保險行業(yè)中的實際應(yīng)用案例，讓讀者對開源規(guī)則流引擎有一個更深刻的理解。

1. 基于 rete 算法的規(guī)則引擎

在 AI 領(lǐng)域，產(chǎn)生式系統(tǒng)是一個很重要的理論，產(chǎn)生式推理分為正向推理和逆向推理產(chǎn)生式，其規(guī)則的一般形式是：IF 條件 THEN 操作。rete 算法是實現(xiàn)產(chǎn)生式系統(tǒng)中正向推理的高效模式匹配算法，通過形成一個 rete 網(wǎng)絡(luò)進(jìn)行模式匹配，利用基于規(guī)則的系統(tǒng)的時間冗余性和結(jié)構(gòu)相似性特征 [8]，提高系統(tǒng)模式匹配效率。本文將介紹的 Drools 引擎就是利用 rete 算法對規(guī)則進(jìn)行分析，形成 rete 網(wǎng)絡(luò)，對模式進(jìn)行匹配。

1.1 rete 算法研究

1.1.1 rete 算法概述

Rete 算法最初是由卡內(nèi)基梅隆大學(xué)的 Charles L.Forgy 博士在 1974 年發(fā)表的論文中所闡述的算法 , 該算法提供了專家系統(tǒng)的一個高效實現(xiàn)。自 Rete 算法提出以后 , 它就被用到一些大型的規(guī)則系統(tǒng)中 , 像 ILog、Jess、JBoss Rules 等都是基于 RETE 算法的規(guī)則引擎 [7]。

Rete 在拉丁語中譯為”net”，即網(wǎng)絡(luò)。Rete 匹配算法是一種進(jìn)行大量模式集合和大量對象集合間比較的高效方法，通過網(wǎng)絡(luò)篩選的方法找出所有匹配各個模式的對象和規(guī)則。

其核心思想是將分離的匹配項根據(jù)內(nèi)容動態(tài)構(gòu)造匹配樹，以達(dá)到顯著降低計算量的效果。Rete 算法可以被分為兩個部分：規(guī)則編譯和規(guī)則執(zhí)行 [7]。當(dāng) Rete 算法進(jìn)行事實的斷言時，包含三個階段：匹配、選擇和執(zhí)行，稱做 match-select-act cycle。

1.1.2 rete 算法相關(guān)概念

Rete 算法規(guī)則相關(guān)的概念有如下幾個：

Fact：已經(jīng)存在的事實，它是指對象之間及對象屬性之間的多元關(guān)系，為簡單起見，事實用一個三元組來表示：（標(biāo)識符 ^ 屬性 值）[1]，例如如下事實：

Rule：規(guī)則，包含條件和行為兩部分，條件部分又叫左手元（LHS），行為部分又叫右手元（RHS）。條件部分可以有多條條件，并且可以用 and 或 or 連接 [1]。其一般形式如下：

RootNode：Rete 網(wǎng)絡(luò)的根節(jié)點，所有對象通過 Root 節(jié)點進(jìn)入網(wǎng)絡(luò)。

ObjectTypeNode：對象類型節(jié)點，保證所傳入的對象只會進(jìn)入自己類型所在的網(wǎng)絡(luò)，提高了工作效率。

AlphaNode：Alpha 節(jié)點是規(guī)則的條件部分的一個模式，一個對象只有和本節(jié)點匹配成功后，才能繼續(xù)向下傳播。

JoinNode：用作連接（jion）操作的節(jié)點，相當(dāng)于 and，相當(dāng)于數(shù)據(jù)庫的表連接操作，屬于 betaNode 類型的節(jié)點。BetaNode 節(jié)點用于比較兩個對象和它們的字段。兩個對象可能是相同或不同的類型。我們將這兩個輸入稱為左和右。BetaNode 的左輸入通常是一組對象的數(shù)組。BetaNode 具有記憶功能。左邊的輸入被稱為 Beta Memory，會記住所有到達(dá)過的語義。右邊的輸入成為 Alpha Memory，會記住所有到達(dá)過的對象。

NotNode：根據(jù)右邊輸入對左邊輸入的對象數(shù)組進(jìn)行過濾，兩個 NotNode 可以完成‘ exists ’檢查。

LeftInputAdapterNodes：將單個對象轉(zhuǎn)化成對象數(shù)組。

Terminal Nodes 被用來表明一條規(guī)則已經(jīng)匹配了它的所有條件（conditions）。

圖 1 展示的是一個簡單的 rete 網(wǎng)絡(luò)：

圖 1. RETE 網(wǎng)絡(luò)

1.1.3 創(chuàng)建 rete 網(wǎng)絡(luò)

Rete 算法的編譯結(jié)果是創(chuàng)建了規(guī)則集對應(yīng)的 Rete 網(wǎng)絡(luò) , 它是一個事實可以在其中流動的圖。創(chuàng)建 rete 網(wǎng)絡(luò)的過程 [1]如下： 1) 創(chuàng)建根節(jié)點； 2) 加入一條規(guī)則 1 (Alpha 節(jié)點從 1 開始，Beta 節(jié)點從 2 開始 )； a. 取出規(guī)則中的一個模式 1，檢查模式中的參數(shù)類型，如果是新類型，則加入一個類型節(jié)點； b. 檢查模式 1 對應(yīng)的 Alpha 節(jié)點是否已存在，如果存在則記錄下節(jié)點位置，如果沒有則將模式 1 作為一個 Alpha 節(jié)點加入到網(wǎng)絡(luò)中，同時根據(jù) Alpha 節(jié)點的模式建立 Alpha 內(nèi)存表； c. 重復(fù) b 直到所有的模式處理完畢； d. 組合 Beta 節(jié)點，按照如下方式： Beta(2) 左輸入節(jié)點為 Alpha(1)，右輸入節(jié)點為 Alpha(2) Beta(i) 左輸入節(jié)點為 Beta(i-1)，右輸入節(jié)點為 Alpha(i) i>2 并將兩個父節(jié)點的內(nèi)存表內(nèi)聯(lián)成為自己的內(nèi)存表； e. 重復(fù) d 直到所有的 Beta 節(jié)點處理完畢； f. 將動作（Then 部分）封裝成葉節(jié)點（Action 節(jié)點）作為 Beta(n) 的輸出節(jié)點； 3) 重復(fù) 2) 直到所有規(guī)則處理完畢； 執(zhí)行完上述步驟，建立的 rete 網(wǎng)絡(luò)如下圖 2 (a 圖為含有 3 個規(guī)則的 rete 網(wǎng)絡(luò)，b 圖為含有一個規(guī)則的 rete 網(wǎng)絡(luò) )：

圖 2. beta-network and alpha-network

上圖（a 圖和 b 圖），他們的左邊的部分都是 beta-network, 右邊都是 alpha-network, 圓圈是 join-node。右邊的 alpha-network 是根據(jù)事實庫和規(guī)則條件構(gòu)建的，其中除 alpha-network 節(jié)點的節(jié)點都是根據(jù)每一條規(guī)則條件的模式 , 從事實庫中 match 過來的，即在編譯構(gòu)建網(wǎng)絡(luò)的過程中靜態(tài)建立的。只要事實庫是穩(wěn)定的，RETE 算法的執(zhí)行效率應(yīng)該是非常高的，其原因就是已經(jīng)通過靜態(tài)的編譯，構(gòu)建了 alpha-network。左邊的 beta-network 表現(xiàn)出了 rules 的內(nèi)容，其中 p1,p2,p3 共享了許多 BetaMemory 和 join-node, 這樣能加快匹配速度。

1.1.4 Rete 算法的匹配過程

匹配過程如下： 1) 對于每個事實，通過 select 操作進(jìn)行過濾，使事實沿著 rete 網(wǎng)達(dá)到合適的 alpha 節(jié)點。2) 對于收到的每一個事實的 alpha 節(jié)點，用 Project( 投影操作 ) 將那些適當(dāng)?shù)淖兞拷壎ǚ蛛x出來。使各個新的變量綁定集沿 rete 網(wǎng)到達(dá)適當(dāng)?shù)?bete 節(jié)點。3) 對于收到新的變量綁定的 beta 節(jié)點，使用 Project 操作產(chǎn)生新的綁定集，使這些新的變量綁定沿 rete 網(wǎng)絡(luò)至下一個 beta 節(jié)點以至最后的 Project。4) 對于每條規(guī)則，用 project 操作將結(jié)論實例化所需的綁定分離出來。

如果把 rete 算法類比到關(guān)系型數(shù)據(jù)庫操作，則事實集合就是一個關(guān)系，每條規(guī)則就是一個查詢，再將每個事實綁定到每個模式上的操作看作一個 Select 操作，記一條規(guī)則為 P，規(guī)則中的模式為 c1,c2,…,ci, Select 操作的結(jié)果記為 r(ci), 則規(guī)則 P 的匹配即為 r(c1)◇r(c2)◇…◇(rci)。其中◇表示關(guān)系的連接（Join）操作。

Rete 網(wǎng)絡(luò)的連接（Join）和投影 (Project) 和對數(shù)據(jù)庫的操作形象對比如圖 3 所示：

圖 3. join and project

1.1.5 Rete 算法的特點、不足和建議 Rete 算法有如下特點：

a． Rete 算法是一種啟發(fā)式算法，不同規(guī)則之間往往含有相同的模式，因此在 beta-network 中可以共享 BetaMemory 和 betanode。如果某個 betanode 被 N 條規(guī)則共享，則算法在此節(jié)點上效率會提高 N 倍。

b. Rete 算法由于采用 AlphaMemory 和 BetaMemory 來存儲事實，當(dāng)事實集合變化不大時，保存在 alpha 和 beta 節(jié)點中的狀態(tài)不需要太多變化，避免了大量的重復(fù)計算，提高了匹配效率。

c. 從 Rete 網(wǎng)絡(luò)可以看出，Rete 匹配速度與規(guī)則數(shù)目無關(guān)，這是因為事實只有滿足本節(jié)點才會繼續(xù)向下沿網(wǎng)絡(luò)傳遞。

Rete 算法的不足：

a. 事實的刪除與事實的添加順序相同, 除了要執(zhí)行與事實添加相同的計算外, 還需要執(zhí)行查找, 開銷很高 [3]。

b. RETE 算法使用了β存儲區(qū)存儲已計算的中間結(jié)果, 以犧牲空間換取時間, 從而加快系統(tǒng)的速度。然而β存儲區(qū)根據(jù)規(guī)則的條件與事實的數(shù)目而成指數(shù)級增長, 所以當(dāng)規(guī)則與事實很多時, 會耗盡系統(tǒng)資源 [3]。

針對 Rete 算法的特點和不足，在應(yīng)用或者開發(fā)基于 Rete 算法的規(guī)則引擎時，提出如下建議：

a. 容易變化的規(guī)則盡量置后匹配，可以減少規(guī)則的變化帶來規(guī)則庫的變化。

b. 約束性較為通用或較強的模式盡量置前匹配，可以避免不必要的匹配。

c. 針對 Rete 算法內(nèi)存開銷大和事實增加刪除影響效率的問題，技術(shù)上應(yīng)該在 alpha 內(nèi)存和 beata 內(nèi)存中，只存儲指向內(nèi)存的指針，并對指針建里索引（可用 hash 表或者非平衡二叉樹）。

d. Rete 算法 JoinNode 可以擴展為 AndJoinNode 和 OrJoinNode，兩種節(jié)點可以再進(jìn)行組合 [5]。

1.2 基于 Rete 算法的 drools 開源規(guī)則引擎

1.2.1 Drools 規(guī)則引擎簡介

Drools 具有一個易于訪問企業(yè)策略、易于調(diào)整以及易于管理的開源業(yè)務(wù) 規(guī)則引擎，符合業(yè)內(nèi)標(biāo)準(zhǔn)，速度快、效率高。業(yè)務(wù)分析師或?qū)徍巳藛T可以利用它輕松查看業(yè)務(wù)規(guī)則，從而檢驗已編碼的規(guī)則是否執(zhí)行了所需的業(yè)務(wù)規(guī)則。其前身是 Codehaus 的一個開源項目叫 Drools，最近被納入 JBoss 門下，更名為 JBoss Rules，成為了 JBoss 應(yīng)用服務(wù)器的規(guī)則引擎。

Drools 被分為兩個主要的部分：編譯和運行時。編譯是將規(guī)則描述文件按 ANTLR 3 語法進(jìn)行解析，對語法進(jìn)行正確性的檢查，然后產(chǎn)生一種中間結(jié)構(gòu)“descr”，descr 用 AST 來描述規(guī)則。目前，Drools 支持四種規(guī)則描述文件，分別是：drl 文件、 xls 文件、brl 文件和 dsl 文件，其中，常用的描述文件是 drl 文件和 xls 文件，而 xls 文件更易于維護(hù)，更直觀，更為被業(yè)務(wù)人員所理解。運行時是將 AST傳到 PackageBuilder，由 PackagBuilder來產(chǎn)生 RuleBase，它包含了一個或多個 Package 對象。

Drools 的語法規(guī)則將在實踐中介紹，下面分析 drools 的原理。

1.2.2 Drools 規(guī)則引擎原理

Drools 中的 Rete 算法被稱為 ReteOO，表示 Drools 為面向?qū)ο笙到y(tǒng)（Object Oriented systems）增強并優(yōu)化了 Rete 算法。

在 Drools 中，規(guī)則被存 放在 Production Memory（規(guī)則庫）中，推理機要匹配的 facts（事實）被存在 Working Memory（工作內(nèi)存）中。當(dāng)時事實被插入到工作內(nèi)存中后，規(guī)則引擎會把事實和規(guī)則庫里的模式進(jìn)行匹配，對于匹配成功的規(guī)則再由 Agenda 負(fù)責(zé)具體執(zhí)行推理算法中被激發(fā)規(guī)則的結(jié)論部分，同時 Agenda 通過沖突決策策略管理這些沖突規(guī)則的執(zhí)行順序，Drools 中規(guī)則沖突決策策略有：(1) 優(yōu)先級策略 (2) 復(fù)雜度優(yōu)先策略 (3) 簡單性優(yōu)先策略 (4) 廣度策略 (5) 深度策略 (6) 裝載序號策略 (7) 隨機策略 [5][6]。

圖 4. Drools 的原理示意圖

2. 應(yīng)用實踐

2.1 需求描述

在汽車保險行業(yè)中，每個地區(qū)都會有自己的車險投保規(guī)則，而且這些投保規(guī)則會經(jīng)常變動，為適應(yīng)這樣的業(yè)務(wù)需求，可以采用 drools 開源規(guī)則引擎。 在本文介紹的例子中，具體業(yè)務(wù)需求是：應(yīng)用應(yīng)該能夠根據(jù)前臺傳入的車輛信息和地區(qū)信息，從車輛和套餐的關(guān)系配置中匹配這輛車可用的套餐；然后，根據(jù)從套餐配置中獲取套餐信息，套餐信息中包含了該套餐可用的險別（如車損險、乘客責(zé)任和盜搶險諸如之類的稱之為險別）；最后從險別配置中獲取險別信息。

2.2 需求分析

由于每個地區(qū)的規(guī)則不一樣，所以要對規(guī)則進(jìn)行分組，每個地區(qū)的車輛和套餐的關(guān)系配置和套餐配置要分別在不同的文件中，而險別是不變信息，各個地區(qū)用同一個險別配置。車輛和套餐的關(guān)系配置放在一個 RuelTable 中，套餐配置放在另一個 RuelTable 中，這兩個 RuelTable 在用一個 xls 文件中描述即可。

這樣配置后，每次引擎先根據(jù)地區(qū)代碼執(zhí)行相應(yīng)的規(guī)則文件；進(jìn)入規(guī)則文件后，再根據(jù)車輛信息過濾套餐找出適合這輛車的套餐，然后更新傳入的對象，這時會重新匹配規(guī)則（已經(jīng)匹配過的不應(yīng)該再匹配，后面代碼中會介紹）；然后再匹配套餐，匹配后，更新對象；最后進(jìn)入險別對應(yīng)的文件匹配險別。

2.3 代碼實踐

首先，建立 Drools BRMS 應(yīng)用。Drools BRMS 是一個管理和編譯規(guī)則和規(guī)則流的 Web 應(yīng)用程序，可以部署在大部分的支持 J2SE 1.5 的 Web 容器下，如 Tomcat6。Drools BRMS 架構(gòu)體系分為三大部分，第一部分是 UI 層，提供了一個基于 Ajax 技術(shù)的業(yè)務(wù)規(guī)則編輯、管理工具。第二部分是規(guī)則文件倉庫層，將規(guī)則文件統(tǒng)一保持在文件系統(tǒng)或關(guān)系數(shù)據(jù)庫。最后一個是 Drools 的核心引擎，用來對用戶提交的規(guī)則文件進(jìn)行驗證、編譯和部署。開發(fā)人員通過規(guī)則文件的編輯部署，生成了包含 rule 的 package 對象，這是引擎可直接操作的內(nèi)存對象。BRMS 通過一個 URL 提供對這個對象的 HTTP 訪問。第三方可以通過 Agent 相關(guān) API 來訪問這個 URL，程序自動下載這個 Package 對象就直接可以在規(guī)則引擎運行，得到規(guī)則執(zhí)行的結(jié)果。

然后，將 BOM(Business Object Model 業(yè)務(wù)規(guī)則引擎所要操作的對象 )、規(guī)則流文件（圖 2-2 所對應(yīng)的文件）和規(guī)則文件（圖 2-3 和圖 2-4 所對應(yīng)的文件）上傳到 BRMS 中。下面對各個文件進(jìn)行介紹。

圖 5 描述的是 BOM 對象，分別是 GeProposalInfo、GeCar、GeComboArea、GeCombo 和 GeKind，他們的關(guān)系從圖中可以很明顯的看出，這里不再贅述。

圖 5. BOM 類

圖 6 中，開始節(jié)點是表示流程的開始。在 diverge 分枝節(jié)點處按 GeComboArea 里的 AreaCode 屬性值有四個分枝，這四個分枝按優(yōu)先級只要有一個滿足條件就繼續(xù)向下執(zhí)行。diverge 分枝節(jié)點有 And、Xor 和 Or 三種類型，其含義分別是執(zhí)行所有分枝、執(zhí)行按優(yōu)先級首先符合條件的分枝、執(zhí)行所有符合條件的分枝。RuleTask 規(guī)則任務(wù)節(jié)點對應(yīng)的是這個 RuleGroup 規(guī)則組里的規(guī)則。執(zhí)行完地區(qū)層次的規(guī)則后，進(jìn)入 converge 聚合節(jié)點，此節(jié)點等待分枝節(jié)點中任何一個節(jié)點執(zhí)行完畢后執(zhí)行。converge 分枝節(jié)點有 And、Xor、n-of-m 和 Discriminator 四種類型，其含義分別是等待所有分枝執(zhí)行完畢、按優(yōu)先級只等待一個分枝執(zhí)行完、等待一個分枝執(zhí)行完，但每個分枝執(zhí)行完后會導(dǎo)致繼續(xù)等待下一個分枝執(zhí)行和等待在 m 個分枝中有 n 個分枝執(zhí)行完畢。規(guī)則任務(wù)節(jié)點 Rule_Kind 是執(zhí)行 Rule_Kind 規(guī)則組里的規(guī)則。結(jié)束節(jié)點標(biāo)志著規(guī)則流執(zhí)行完畢。

圖 6. 規(guī)則流

圖 7 和圖 8 分別是 beijing.xls 和 kind.xls 的截圖。在決策表中，不同作用的表格用不同顏色區(qū)分。在黑色區(qū)中，有一個 RuleTable 關(guān)鍵詞，它表示本決策表從這開始，解析的時候也就是從這按從上到下和從左到右的順序開始解析，其后是表名稱。CONDITION 是表明此列為條件的關(guān)鍵詞。和并列中 pi:GeProposalInfo 的意思是從 workmemory 中選取類型為 GeProposalInfo 的一個對象賦值給 pi。car.carType matches ".*$param.*"的含義是查看 pi 中對象 car 中的 carType 屬性值是否包含此列單元格中的值。".*$param.*"為正則表達(dá)式，$param 為對單元格中值的引用。Matches 是一個操作。RULEFLOW-GROUP 是對規(guī)則分組的關(guān)鍵字，它和規(guī)則任務(wù)節(jié)點對應(yīng)。PRIORITY 設(shè)置規(guī)則執(zhí)行優(yōu)先級，數(shù)值越大越先被執(zhí)行。ACTION 是規(guī)則的行為部分，可以在單元格中寫 java 代碼。另外，單元格中有內(nèi)容表示執(zhí)行匹配或執(zhí)行 java 代碼，沒有內(nèi)容表示什么都不做，跳過。

圖 7. 規(guī)則表定義一

圖 8. 規(guī)則表定義二

圖 9 是 beijing.xls 和 kind.xls 里的規(guī)則生成的 rete 網(wǎng)絡(luò)。在編寫規(guī)則中，我們采用了本文的建議 a（將容易變化的規(guī)則盡量放后）和 b（將強約束條件放前），這樣產(chǎn)生的 rete 網(wǎng)絡(luò)匹配效率會更高。如圖 2-5 中，在紅色節(jié)點（類型節(jié)點）下會有對 updateFlag 的三個分枝，updateFlag 是強約束條件且不會變化太大，僅在此節(jié)點上，匹配效率就提高了三分之一。

圖 9. 生成的 Rete 網(wǎng)絡(luò)

?

最后，我們對我們的應(yīng)用程序端的調(diào)用做一下闡述。

第一步：創(chuàng)建規(guī)則庫

第二步：創(chuàng)建 workmemory 并插入對象

第三步：執(zhí)行規(guī)則流和規(guī)則

第四步：釋放資源

3. 總結(jié)

本文通過深入剖析 rete 算法和基于 rete 算法的規(guī)則引擎，發(fā)現(xiàn)了算法中存在的問題，提出了算法改進(jìn)的意見，同時也闡述了在應(yīng)用規(guī)則引擎時應(yīng)該注意的問題，并通過實例對規(guī)則引擎進(jìn)行了實踐。