引言
许多业务应用程序必须应对市场经济的动态变化。例如,用于保险和银行业的应用程序必须能够适应在设计过程中没有人能够预测或计划的不可避免的市场变化。一个解决方案是拥有一个规则引擎,它本质上是一组工具,使业务分析师和开发人员能够根据组织的数据构建决策逻辑。
规则引擎的实现包括 Drools、Fair Isaac Blaze Advisor、ILOG JRules 和 Jess,仅举几例。然而,缺乏标准可能是阻止企业使用基于规则的应用程序的主要因素。大多数规则引擎都有专有的 API,这使得它们很难与应用程序集成。如果不再支持某个规则引擎,而业务决定采用其他规则引擎,则需要重写大部分应用程序代码。JSR 94 尝试标准化 Java 技术的规则引擎实现。前面提到的四个规则引擎都支持 JSR 94。
JSR 94 为规则管理和规则运行时 API 提供了指南,但它没有定义用于定义规则和操作的语言的指南。正在努力标准化通用规则语言,包括 规则标记语言 (RuleML)。
Rule Engine
规则引擎的基本思想是将业务或应用程序逻辑外部化。 规则引擎可以被视为一个复杂的 if-then 语句解释器。if-then 语句是规则。规则由条件和动作两部分组成:当条件满足时,动作被执行。if 部分包含条件(例如金额 >=$100),then 部分包含操作(例如优惠折扣 5%)。规则引擎的输入是称为规则执行集和数据对象的规则集合。输出由输入决定,可能包括经过修改的原始输入数据对象、新数据对象和可能的副作用(例如向客户发送电子邮件)。
规则引擎应该用于具有高度动态业务逻辑的应用程序以及允许最终用户编写业务规则的应用程序。规则引擎是高效决策的绝佳工具,因为它可以快速、可靠和重复地根据数以千计的事实做出决策。
规则引擎允许对于在开发周期外的人制定的规则能够快速响应,快速部署。
术语
规则 - Rule:一组条件(condition),然后是一组动作(action)。它代表了系统的逻辑。规则主要以 if-then 形式表示。它主要包含条件和动作两部分。规则有时也被称为作业(production)。
Rule = Condition + Action
条件也称为事实(fact)或前因(antecedents)或模式(pattern)。动作也被称为结果(consequent)。
规则在以下原则上工作:
- 它们是相互独立的
- 很容易变更(修改、移除、增加)
- 每个规则控制最小数量的所需信息,原子性
- 可以允许不同背景的人协作
人类专家:相应业务领域的专家。这个人以规则的形式提供知识(Knowledge)。
规则形式的知识:
Rule 1: 一个人是否有资格获得住房贷款? if: 1. 他的月薪超过 7K。 2. 他的征信评分超过 80。 then: 1. 获批房屋贷款。 2. 获批房屋贷款总额的 30%。 Rule 2: 一个人是否有资格获得住房贷款? if: 1. 他的月薪超过 15K。 2. 他的征信评分超过 70。 then: 1. 获批房屋贷款。 2. 获批房屋贷款总额的 60%。
专家系统 - Expert System:它是一个使用人类专家的知识来解决问题并给出解决方案的程序。它也被称为基于规则的系统或者作业系统。
推理引擎 - Inference Engine:它是专家系统的大脑,管理专家系统内部的大量规则和事实。它的工作是挑选规则并应用数据并生成解决方案。我们将详细讨论它。
规则引擎,也是一个专家系统程序,它对数据运行规则,如果有任何条件匹配,则执行相应的动作。
在上图中,表明我们以规则(if-then 形式)的形式收集知识并将它们放置在任意的存储系统中,如文件或数据库。现在推理引擎根据需求选择规则并在输入数据或查询上运行它们。如果任何模式/条件匹配,则它执行相应的操作并返回结果或解决方案。
推理引擎
推理引擎是专家系统的核心组成部分,它将逻辑规则应用于知识库,从已知事实中推断出新信息。推理引擎通常以两种模式运行,它们是:
数据驱动,其基本思想是:从问题已有的事实(初始证据)出发,正向使用规则,当规则的条件部分与已有的事实匹配时,就把该规则作为可用规则放入候选规则队列中,然后通过冲突消解,在候选队列中选择一条规则作为启用规则进行推理,并将其结论放入数据库中,作为下一步推理时的证据。如此重复这个过程,直到再无可用规则可被选用或者求得了所要求的解为止。
例如:假如我们想根据给定的规则和数据知道名字为 Fritz 宠物的肤色。
Rules:
1. if X 呱呱叫 and X 吃苍蝇 - then X 是一只青蛙
2. if X 啁啾叫 - then X 是金丝雀
3. if X 是一只青蛙 - then X 是绿色的
4. if X 是金丝雀 - then X 是黄色的
Data:
1. Fritz 呱呱叫
2. Fritz 吃苍蝇
根据给定的规则和数据我们可以提取到以下信息:
Fritz 是青蛙。
Fritz 是绿色的。
目标驱动,它是首先提出某个假设,然后寻找支持该假设的证据,若所需的证据都能找到,说明原假设是正确的;若无论如何都找不到所需要的证据,则说明原假设不成立,此时需要另做新的假设。
还有一类称为 双向推理 - Hybrid chaining,它是正向和反向推理的组合。
阶段
推理引擎的程序分三个阶段工作,以对给定数据执行规则。
阶段 1 — 匹配 Match:在此阶段,推理引擎将事实和数据与规则集进行匹配。这个过程称为模式匹配。
我们可以用于模式匹配的算法有:
- Linear
- Rete
- Treat
- Leaps
Drools 是规则引擎的实现之一,使用 Rete 算法变种 Phreak 算法 进行模式匹配。它是模式匹配的最佳算法之一。
第一阶段的输出是一个冲突集(Conflict Set)。冲突集意味着,对于相同的事实或条件,可能满足不止一个规则。所以它返回冲突规则集。
阶段 2 — 解决 Resolve:在此阶段,推理引擎管理冲突规则的顺序。它解决了冲突并给出了选定的规则。为了解决冲突,它可以使用以下任何算法。
- Lex
- Recency
- MEA
- Refactor
- Priority wise
阶段 3 — 执行 Execute:在此阶段,推理引擎仅对给定数据运行所选规则的动作,并将输出/结果返回给客户端。
使用规则引擎的时间、地点和原因
规则引擎在应用程序中用于替换和管理一些业务逻辑。它们最适用于业务逻辑过于动态而无法在源代码级别进行管理的应用程序——也就是说,业务策略的更改需要立即反映在应用程序中。保险(例如保险评级)、金融服务(贷款、欺诈检测、索赔路由和管理)、政府(申请流程和税收计算)、电信客户服务和计费(需要的长途电话促销)等领域的应用集成到计费系统中)、电子商务(个性化用户体验)等都可以从使用规则引擎中受益匪浅。
基于规则的应用程序通过传入要执行的规则集来与规则引擎进行通信。然后,应用程序可以检查结果并将其显示给最终用户或执行进一步处理。规则引擎根据规则所需的输入以及从先前规则的评估中获得的结果来确定何时评估每个规则。您不需要指定规则的顺序或依赖关系。
例如,在 Java EE 企业应用程序中,规则可以适合如下应用程序:
- 在应用层管理动态业务逻辑和任务流
- 在表现层自定义页面流程和工作流程,以及根据会话状态构建自定义页面
为您的应用程序采用基于规则的方法具有以下优势:
- 代表策略的规则很容易传达和理解。
- 规则比传统的编程语言保持更高级别的独立性。
- 规则将知识与其实现逻辑分开。
- 无需更改源代码即可更改规则;因此,无需重新编译应用程序的代码。
然而,这些好处并非没有代价。与任何工具一样,将规则引擎集成到您的应用程序中的决定应基于成本与收益。成本包括学习曲线以及在应用程序和规则引擎之间构建接口所涉及的工作。此外,不同的规则引擎使用不同的格式和语法来定义规则。因此,如果组织决定从一种规则引擎转移到另一种规则引擎,业务分析师和开发人员必须学习和了解另一种工具的操作。
JSR 94
Java 规则引擎 API (JSR 94) 规范是通过 Java Community Process (JCP) 项目开发的,它通过提供一个简单的 API 来访问来自 Java 平台标准版的规则引擎,从而为规则引擎定义了 Java 运行时 API。
JSR 94 定义了一个简单的 API,用于从 Java SE 或 Java EE 客户端访问规则引擎。它提供 API
- 注册和注销规则
- 解析规则
- 检查规则元数据
- 执行规则
- 检索结果
- 过滤结果
请注意,JSR 94 未对以下内容进行标准化:
- 规则引擎本身
- 规则的执行流程
- 用于描述规则的语言
- Java EE 技术的部署机制
换句话说,它没有标准化规则执行的语义。
JSR 94 架构
API 定义在两个主要包中:
- 规则管理员 API:这个 API 在
javax.rules.admin
包中定义 ,提供可用于加载规则和关联动作来作为执行集的类。一个 rule execution set - 规则执行集是规则的集合。规则可以从外部资源加载,例如 URI、一个InpuTStream
、一个 XMLElement
、一个二元抽象语法树或一个Reader
。它还提供了注册和取消注册规则执行集的方法。此包还可用于定义对执行集的权限以提供访问授权。 - 运行时客户端 API:此 API 在
javax.rules
包中定义 ,提供客户端使用的类来运行规则并获取结果。只能访问使用规则管理器 API 注册的规则。此 API 使客户端能够获取规则会话并在该会话中执行规则。
JSR 94 专家组决定使用两个单独的包来加强以下区别:
(1) 运行时客户端 API 只能使用规则管理员 API 加载并注册到运行时环境中的规则执行集
(2) 规则管理员 API 可以执行动态加载和执行外部资源以及发布规则集
此外,分离允许对用户群进行更细粒度的控制,允许一些用户执行规则但不能管理它们。
规则管理员 API
此 API 使用 RuleServiceProvider
该类获取 RuleAdministrator
接口的实例,该实例提供注册和取消注册执行集的方法。管理员 API 的高级功能如下:
- 它通过
RuleServiceProvider
类获取接口RuleAdministrator
的实例 - 它从外部可序列化或不可序列化的资源创建一个
RuleExecutionSet
,包括org.w3c.dom.Element
用于从 XML 子文档中读取java.io.InputStream
用于从二进制流中读取java.lang.Object
用于从特定于供应商的抽象语法树中读取java.io.Reader
用于从字符流中读取java.lang.String
用于从 URI 中读取
- 它根据 URI 注册
RuleExecutionSet
对象以供RuleRuntime
使用。 - 它根据 URI 取消注册
RuleExecutionSet
对象,因此不再可以从RuleRuntime
访问它。 - 它通过从
RuleExecutionSet
检索Rule
对象列表来查询规则执行集的结构元数据。 - 它在规则执行集和规则上设置和获取应用程序或供应商特定的属性。
运行时客户端 API
此 API 以类似于 Java 数据库连接 (JDBC) 软件的方式提供对规则引擎 API 的供应商实现的访问。供应商通过 RuleServiceProvider
类向客户公开他们的规则引擎实现。此类提供对运行时和管理 API 的访问。供应商提供唯一标识实现的规则服务提供程序 URL。所有规则服务提供者都应该注册一个 RuleServiceProviderManager
对象,以便客户端可以访问。
这个 API 的核心是 RuleRuntime
接口,它提供了允许客户端创建 RuleSession
用于运行规则的方法。RuleSession
是客户端和规则引擎之间的运行时连接;它与单个规则执行集相关联,可能会消耗规则引擎资源,但当客户端不再需要规则会话时,必须明确释放规则会话。因此,规则会话做了两件事:
- 它提供了一种机制来访问向规则服务提供者注册的所有规则执行集的列表。
- 它定义了客户端希望建立的会话类型:有状态或无状态。
statelessRuleSession
无状态规则会话提供了高性能和简单的 API,该 API 执行具有输入对象列表的规则执行集。无状态规则会话方法是幂等的。statefulRuleSession
有状态规则会话允许客户端与规则执行集合进行长时间的交互。输入对象可以逐步添加到会话中,输出对象也可以被重复查询。
Runtime Client API 的高级功能如下:
- 它通过
RuleServiceManager
类获取规则引擎供应商的规则服务提供者的实例 。 - 它通过
RuleServiceProvider
类获取接口RuleRuntime
的实例 。 - 它通过
RuleRuntime
创建一个RuleSession
。 - 它获取已注册 URI 的
java.util.List
。 - 它与获取的
RuleSession
交互。 - 它通过
RuleExecutionSetMetadata
接口检索RuleSession
的元数据。 - 它提供了一个
ObjectFilter
接口来过滤执行RuleExecutionSet
的结果。 - 它使用
Handle
实例来访问添加到statefulRuleSession
的对象。
参考实现 - Drools
Drools 是一个业务规则管理系统,具有基于正向推理和反向推理的规则引擎,允许快速可靠地评估业务规则和复杂事件处理。规则引擎也是创建专家系统的基本构件,在人工智能中,专家系统是模拟人类专家决策能力的计算机系统。
Drools 支持多种类型资产,您可以使用这些资产为决策服务定义业务决策规则。每个决策创作资产都有不同的优势,您可能更喜欢使用一种资产或多种资产的组合,具体取决于您的目标和需求。
这些资产类型包括:决策模型和符号 (DMN) 模型、引导决策表、电子表格决策表、引导规则、引导规则模版、DRL 规则、预测模型标记语言 (PMML) 模型。
一个简单的 DRL 规则文件结构如下,它由条件和动作组成:
rule "name"
when
(Conditions) - also called Left Hand Side of the Rule (LHS)
then
(Actions/Consequence) - also called Right Hand Side of the Rule (RHS)
end
Drools engine
Drools 引擎的基本功能是将传入的数据或事实与规则的条件进行匹配,并确定是否以及如何执行规则。
Drools 引擎使用以下基本组件运行:
- Rules:规则,您定义的业务规则或 DMN 决策。所有规则必须至少包含触发规则的条件和规则规定的动作。
- Facts:事实,在 Drools 引擎中输入或更改的数据,Drools 引擎与规则条件匹配以执行适用的规则。
- Production memory:作业内存,Rules 存储在 Drools 引擎中的位置。
- Working memory:工作内存,Facts 存储在 Drools 引擎中的位置。
- Agenda:议程,激活的规则被注册和排序(如果适用)以准备执行的位置。
当业务用户或自动化系统在 Drools 中添加或更新与规则相关的信息时,该信息以一个或多个事实的形式插入到 Drools 引擎的工作内存中。Drools 引擎将这些事实与存储在作业内存中的规则条件进行匹配,以确定符合条件的规则执行。 (这种将事实与规则匹配的过程通常称为模式匹配 - pattern matching。)当满足规则条件时,Drools 引擎在议程中激活并注册规则,然后 Drools 引擎对优先或冲突的规则进行排序以准备执行。
下图说明了 Drools 引擎的这些基本组件:
Drools 规则引擎会将规则转换成执行树,每个规则条件都被拆分为小块,在树结构中连接并重用。每当数据被传送到规则引擎,它将在此类似的树中进行评估并最终到达动作节点,这些规则将会标记为该数据特定的执行规则集。
会话 KIE Session
同样的 Drools 中的会话也分为有状态和无状态:
Stateless Session 无状态会话,无状态会话是不使用推理来随时间对事实进行迭代更改的会话。在无状态会话中,来自先前会话调用(先前会话状态)的数据在会话调用之间被丢弃,而在有状态会话中,该数据被保留。无状态会话的行为类似于函数,因为它产生的结果由 KIE 基础的内容和传递到会话以在特定时间点执行的数据确定。该 KIE 会话不存储之前传入 KIE 会话的任何数据。
无状态 KIE 会话通常用于以下用例:
验证,例如验证某人是否有资格获得抵押贷款
计算,例如计算抵押贷款溢价
路由和过滤,例如将收到的电子邮件分类到文件夹中或将收到的电子邮件发送到目的地
Stateful Session 有状态会话,它使用推理随着时间的推移对事实进行迭代更改。在有状态的会话中,来自会话的先前调用(先前的会话状态)的数据在会话调用之间保留,而在无状态会话中,该数据被丢弃。有状态会话会保留之前输入的 Facts 的 Working memory 和当前输入的 Facts 来做联合评判、推理。
有状态的 KIE 会话通常用于以下用例:
监控,例如监控股票市场和自动化购买过程
诊断,例如运行故障查找过程或医疗诊断过程
物流,例如包裹跟踪和交付配置
确保合规,例如验证市场交易的合法性
推理和真相维护
Drools 引擎的基本功能是将数据与业务规则进行匹配,并确定是否以及如何执行规则。为确保将相关数据应用于适当的规则,Drools 引擎根据现有知识进行推断,并根据推断信息执行操作。
在很多情况下,规则系统中的新数据是其他规则执行的结果,而这些新数据会影响其他规则的执行。如果 Drools 引擎将执行规则的结果作为断言数据,则将推断信息应用于其他规则时使用真相维护来证明断言的合理性和真实性。真相维护还有助于识别不一致和处理矛盾。例如,如果两个规则被执行并导致一个矛盾的动作,Drools 引擎会根据先前计算的结论的假设来选择动作。
Drools 引擎使用声明(stated)或逻辑(logical)插入来插入事实:
- 声明插入:用
insert()
定义。在声明插入之后,事实通常会被明确撤回。 (术语插入,当一般使用时,指的是声明插入。) - 逻辑插入:用
insertLogical()
定义。在逻辑插入之后,当插入事实的规则中的条件不再为真时,插入的事实会自动收回。当没有条件支持逻辑插入时,事实将被撤回。 Drools 引擎认为逻辑插入的事实是合理的。
执行控制
当新的规则数据进入 Drools 引擎的工作内存时,规则可能会变得完全匹配并可以执行。单个工作内存的动作(insert、update、retract)可能导致多个符合条件的规则执行。当规则完全匹配时,Drools 引擎创建一个激活实例,引用规则和匹配的事实,并将激活添加到 Drools 引擎议程中。议程使用冲突解决策略控制这些规则激活的执行顺序。
在 Java 应用程序中第一次调用 fireAllRules()
之后,Drools 引擎反复循环通过两个阶段:
- Agenda Evaluation - 议程评估。在这个阶段,Drools 引擎选择所有可以执行的规则。如果不存在可执行规则,则执行周期结束。如果找到可执行规则,Drools 引擎会在议程中注册激活,然后进入工作内存动作阶段以执行规则结果动作。
- Working Memory Action - 工作内存动作。在这个阶段,Drools 引擎为之前在议程中注册的所有激活规则执行规则结果动作(每个规则的 then 部分)。在所有结果动作完成或主 Java 应用程序进程再次调用
fireAllRules()
后,Drools 引擎返回议程评估阶段以重新评估规则。
当议程上存在多个规则时,执行一个规则可能会导致另一个规则从议程中删除。为避免这种情况,您可以定义规则在 Drools 引擎中执行的方式和时间。定义规则执行顺序的一些常用方法是使用规则显着性(Salience)、议程分组(Agenda group)或激活组(Activation group)。
规则的显着性 - Salience
每个规则都有一个用来确定执行顺序的整数 salience
属性。当在激活队列中排序时,具有较高显着性值的规则具有较高的优先级。规则的默认显着性值为零,但显着性可以是负数或正数。
规则议程组 - Agenda group
议程组是由相同的 agenda-group
规则属性绑定在一起的一组规则。议程将 Drools 引擎议程上的规则分组。在任何时候,只有一个组有焦点,该焦点将该组规则优先于其他议程组中的规则执行。您可以通过 setFocus()
调用议程组来确定焦点。也可以定义具有 auto-focus
属性的规则,以便下次激活该规则时,焦点会自动分配给该规则所分配到的议程组。
每次在 Java 应用程序中调用 setFocus()
时,Drools 引擎都会将指定的议程组添加到规则堆栈的顶部。如果规则未指定任何分组,则包含在默认议程组 “MAIN” 中,并且在堆栈中首先执行,除非另一个组具有焦点。
激活分组 - Activation group
激活组是由相同的 activation-group
规则属性绑定在一起的一组规则。在该组中,只有一个规则能被执行。在满足该组中要执行的规则的条件后,该激活组中的所有其他等待执行的规则将从议程中移除。
规则流程分组 - Ruleflow group
流程分组使用 ruleflow-group
规则属性标识规则流组。在规则流组中,规则只能被关联的规则流组激活时触发。Ruleflow 允许我们使用流程图来指定评估规则集的顺序。这允许我们定义应按顺序或并行评估哪些规则集,指定应评估规则集的条件等。
复杂事件处理 CEP
在 Drools 中,事件是应用程序域在某个时间点的状态发生重大变化的记录。根据域的建模方式,状态变化可以由单个事件、多个原子事件或相关事件的层次结构表示。从复杂事件处理 (CEP) 的角度来看,事件是在特定时间点发生的一种事实或对象,而业务规则是关于如何对来自该事实或对象的数据做出反应的定义。
Drools 中的 Drools 引擎使用复杂事件处理 (CEP) 来检测和处理事件集合中的多个事件,发现事件之间存在的关系,并从事件及其关系中推断出新数据。
CEP 场景具有以下关键特征:
- 场景通常处理大量事件,但只有一小部分事件是相关的。
- 事件通常是不可变的,代表状态变化的记录。
- 规则和查询针对事件运行,并且必须对检测到的事件模式做出反应。
- 相关事件通常具有很强的时间关系。
- 个别事件没有优先级。CEP 系统优先考虑相关事件的模式以及它们之间的关系。
- 事件通常需要组合和聚合。
鉴于这些常见的 CEP 场景特征,Drools 中的 CEP 系统支持以下特性和功能来优化事件处理:
- 具有适当语义的事件处理
- 事件检测、关联、聚合和组合
- 事件流处理
- 用于对事件之间的时间关系进行建模的时间约束
- 重大事件的滑动窗口
- 会话范围的统一时钟
- CEP 用例所需的事件量
- Reactive 响应式规则
- 用于将事件输入到 Drools 引擎的适配器(pipeline)
其它功能
引擎查询和实时查询
可以使用带有 Drools 引擎的查询来检索基于在规则中定义的事实模式(fact pattern)的事实集。
事件监听
Drools 引擎在执行诸如事实插入和规则执行之类的活动时会生成事件。如果我们注册事件侦听器,则 Drools 引擎会在执行活动时调用每个侦听器。
规则匹配算法
Rete
Rete 算法是一种用于实现基于规则系统的模式匹配算法。该算法旨在有效地将许多规则或模式应用于知识库中的许多对象或事实。它用于根据系统的数据存储和事实来确定应该触发哪个系统规则。“Rete”这个词在拉丁语中是“网”或“梳子”的意思。
Rete 算法具有以下主要特点:
- 它通过使用节点共享来减少或消除某些类型的冗余。
- 它在执行不同事实类型之间的连接时存储部分匹配。这反过来又允许作业系统避免在每次对作业系统的工作内存进行更改时对所有事实进行完全重新评估。相反,作业系统只需要评估工作记忆的变化(增量)。
- 当事实从工作内存中撤回时,它允许有效地删除内存元素。
Rete 算法被广泛用于在模式匹配引擎中实现匹配功能。
- 它提供了一种多对多匹配的方法,当必须在搜索网络中找到许多或所有可能的解决方案时,这是一个重要特征。
Retes 是表示更高级别规则集的有向无环图。它们通常在运行时使用内存对象网络来表示。这些网络将规则条件(模式)与事实(关系数据元组)相匹配。Rete 网络充当一种关系查询处理器,对任意数量的数据元组有条件地执行投影、选择和连接。
规则通常由分析师、领域专家和开发人员使用一些高级规则语言捕获和定义。它们被收集到规则集中,然后通常在运行时被翻译成可执行的 Rete。
当事实被“断言”到工作内存时,引擎会为每个事实创建工作内存元素 - working memory elements (WME)。事实是 n 元组-Tuple,因此可能包含任意数量的数据项。每个 WME 可以保存一个完整的 n 元组,或者,每个事实可以由一组 WME 表示,其中每个 WME 包含一个固定长度的元组。在这种情况下,元组通常是三元组(3 元组)。
每个 WME 在单个根节点处进入 Rete 网络。根节点将每个 WME 传递给它的子节点,然后每个 WME 可以通过网络传播,可能存储在中间存储器中,直到它到达终端节点。
Alpha 网络
节点图的“左”( alpha ) 侧形成一个判别网络,负责根据简单的条件测试来选择单个 WME,这些条件测试将 WME 属性与常数值进行匹配。判别网络中的节点还可以执行比较同一 WME 的两个或多个属性的测试。如果 WME 与一个节点表示的条件成功匹配,则将其传递到下一个节点。在大多数引擎中,根节点的直接子节点用于测试每个 WME 的实体标识符或事实类型(Fact Type)。因此,所有代表相同实体类型的 WME 通常会遍历判别网络中给定的节点分支。
在判别网络中,alpha 节点(也称为 1 输入节点)的每个分支都终止于一个内存,称为 alpha memory。这些内存存储与给定节点分支中每个节点中的每个条件匹配的 WME 集合。无法匹配分支中至少一个条件的 WME 不会在相应的 alpha 内存中实现。Alpha 节点分支可能会分叉以最小化条件冗余。
Beta 网络
图的“右”(beta)侧主要执行不同 WME 之间的连接。它是可选的,仅在需要时才包括在内。它由 2 个输入节点组成,每个节点都有一个“左”和一个“右”输入。每个 beta 节点将其输出发送到 beta memory。
在 Rete 的描述中,通常指令牌 token 在 beta 网络中的传递。然而,在本文中,我们将根据 WME 列表而不是令牌来描述数据传播,以识别不同的实现选项以及令牌的基本用途和用途。当任何一个 WME 列表通过 beta 网络时,新的 WME 可能会添加到其中,并且该列表可以存储在 beta 内存中。Beta 内存中的 WME 列表表示给定作业中条件的部分匹配。
到达 beta 节点分支末尾的 WME 列表代表单个产品的完全匹配,并被传递到终端节点。这些节点有时称为 p-nodes,其中“p”代表 production-作业。每个终端节点代表一个单一的作业,到达终端节点的每个 WME 列表代表该作业中条件匹配 WME 的完整集合。对于它收到的每个 WME 列表,作业节点将在“议程”上“激活”一个新的生产实例。议程通常被实现为优先队列。
Beta 节点通常在存储在 beta 内存中的 WME 列表和存储在 alpha 内存中的单个 WME 之间执行连接。每个 beta 节点与两个输入存储器相关联。alpha 内存保存 WM 并在每次存储新的 WME 时在 beta 节点上执行“右”激活。Beta 内存保存 WME 列表并在每次存储新的 WME 列表时在 beta 节点上执行“左”激活。当一个连接节点被右激活时,它会将来自其输入 alpha 内存的新存储的 WME 的一个或多个属性与包含在输入 beta 内存中的每个 WME 列表中的特定 WME 的给定属性进行比较。当一个连接节点被左激活时,它会遍历 beta 内存中一个新存储的 WME 列表,检索给定 WME 的特定属性值。
每个 beta 节点输出 WME 列表,这些列表要么存储在 beta 内存中,要么直接发送到终端节点。每当引擎将在后续 beta 节点上执行额外的左激活时,WME 列表都会存储在 beta 内存中。
从逻辑上讲,位于 beta 节点分支头部的 beta 节点是一种特殊情况,因为它不从网络中任何更高的 beta 内存中获取输入。不同的引擎以不同的方式处理这个问题。一些引擎使用专门的适配器节点将 alpha 内存连接到 beta 节点的左侧输入。其他引擎允许 beta 节点直接从两个 alpha 存储器中获取输入,将一个视为“左”输入,另一个视为“右”输入。在这两种情况下,“头”beta 节点都从两个 alpha 存储器中获取输入。
为了消除节点冗余,任何一个 alpha 或 beta 内存都可以用于在多个 beta 节点上执行激活。除了加入节点之外,beta 网络还可能包含其他节点类型。如果 Rete 不包含 beta 网络,则 alpha 节点将令牌直接提供给 p 节点,每个令牌都包含一个 WME。在这种情况下,可能不需要将 WME 存储在 alpha 内存中。
Phreak
Drools 规则引擎使用 Phreak
算法进行规则评估。Phreak 是从 Rete 算法演变而来的,包括增强的 Rete 算法 ReteOO
,该算法在 Drools 的先前版本中针对面向对象系统引入。总体而言,Phreak 比 Rete 和 ReteOO 更具可扩展性,并且在大型系统中速度更快。
Rete 被认为是急切的(即时规则评估)和面向数据的,而 Phreak 被认为是惰性的(延迟规则评估)和面向目标的。Rete 算法在插入、更新和删除操作期间执行许多操作,以便找到所有规则的部分匹配。Rete 算法在规则匹配过程中的这种急切需要在最终执行规则之前需要大量时间,尤其是在大型系统中。使用 Phreak,这种规则的部分匹配被故意延迟以更有效地处理大量数据。
Phreak 算法对以前的 Rete 算法添加了以下增强功能:
- 三层上下文内存:节点(Node)、段(Segment)和规则内存类型(rule memory type)
- 基于规则、基于段和基于节点的链接
- 惰性(延迟)规则评估
- 带有暂停和恢复的基于堆栈的评估
- 隔离的规则评估
- 面向集合的传播
当规则引擎启动时,所有规则都被认为与可以触发规则的模式匹配数据是 unlinked 断开链接的。在这个阶段,决策引擎中的 Phreak 算法不会评估规则。insert
、 update
和 delete
动作放入队列,并且 Phreak 使用启发式算法,根据最有可能导致执行的规则,计算并选择下一个评估规则。当为规则填充所有必需的输入值时,该规则被视为 linked 到相关的模式匹配数据。然后,Phreak 创建一个代表该规则的目标,并将该目标放入按规则显着性排序的优先级队列中。仅评估为其创建目标的规则,而延迟其他潜在的规则评估。在评估单个规则时,仍然通过分段过程实现节点共享。
与面向元组的 Rete 不同,Phreak 传播是面向集合的。对于正在评估的规则,规则引擎访问第一个节点并处理所有排队的insert
、 update
和 delete
动作。结果被添加到一个集合中,并将该集合传播到子节点。在子节点中,处理所有排队的插入、更新和删除操作,将结果添加到同一个集合中。然后将该集合传播到下一个子节点,并重复相同的过程,直到它到达终端节点。此循环创建批处理效果,可为某些规则构造提供性能优势。
规则的链接和取消链接是通过基于网络分段的分层位掩码系统进行的。构建规则网络时,会为由同一组规则共享的规则网络节点创建段(Segment)。规则由段路径组成。如果一条规则不与任何其他规则共享任何节点,则它成为一个单独的段。
为段中的每个节点分配一个位掩码偏移量。根据这些要求,为规则路径中的每个段分配另一个位掩码:
- 如果存在至少一个节点的输入,则将节点位设置为
on
状态。 - 如果段中的每个节点都将位设置为
on
状态,则段也设置为on
状态。 - 如果任何节点位被设置为
off
状态,则段也被设置为off
状态。 - 如果规则路径中的每个段都设置为
on
状态,则认为该规则已链接,并创建一个目标来安排该规则进行评估。
相同的位掩码技术用于跟踪修改的节点、段和规则。如果自创建评估目标以来已对其进行了修改,则此跟踪功能使已链接的规则能够从评估中取消调度。因此,没有任何规则可以评估部分匹配。
这种规则评估过程在 Phreak 中是可能的,因为与 Rete 中的单个内存单元相比,Phreak 具有三层上下文内存,包括节点、段和规则内存类型。这种分层可以在评估规则期间实现更多的上下文理解。
以下示例说明了如何在 Phreak 的三层内存系统中组织和评估规则。
**示例 1:**具有三个模式的单个规则 (R1):A、B 和 C。该规则形成单个段,其中节点的位掩码为 1、2 和 4。单个段的位偏移量为 1。
**示例 2:**添加规则 R2 并共享模式 A。
模式 A 放置在其自己的段中,从而为每个规则生成两个段。这两个部分形成了各自规则的路径。第一段由两条路径共享。当模式 A 链接时,该段变为链接。然后,该段遍历该段共享的每个路径,将位 1 设置为 on
。如果模式 B 和 C 稍后打开,则路径 R1 的第二段被链接,这会导致 R1 的位 2 被打开。R1 打开位 1 和位 2 后,规则变为已链接,并创建了一个目标来安排规则以供以后评估和执行。
评估规则时,段使匹配的结果能够被共享。每个段都有一个暂存内存,用于对该段的所有插入、更新和删除进行排队。当评估 R1 时,规则处理模式 A,这会产生一组元组。该算法检测分段拆分,为集合中的每个插入、更新和删除创建对等元组,并将它们添加到 R2 暂存内存。然后将这些元组与任何现有的分阶段元组合并,并在最终评估 R2 时执行。
**示例 3:**添加规则 R3 和 R4 并共享模式 A 和 B。
规则 R3 和 R4 有三个段,R1 有两个段。模式 A 和 B 由 R1、R3 和 R4 共享,而模式 D 由 R3 和 R4 共享。
**示例 4:**具有子网且没有模式共享的单个规则 (R1)。
当 Not
、Exists
或 Accumulate
节点包含多个元素时,就会形成子网。在本例中,元素 B not( C )
构成子网。该元素 not( C )
是单个元素,不需要子网,因此在 Not
节点内部合并。子网使用专用网段。规则 R1 仍然有一条由两段组成的路径,子网形成另一个内部路径。当子网被链接时,它也在外部网段中被链接。
**示例 5:**具有由规则 R2 共享的子网的规则 R1。
一个规则中的子网节点可以由另一个没有子网的规则共享。这种共享导致子网段被分成两个段。
受约束的 Not
节点和 Accumulate
节点永远不能取消链接段,并且始终被认为已打开其位。
Phreak 评估算法是基于堆栈的,而不是基于方法递归的。当使用 StackEntry
表示当前正在评估的节点时,可以随时暂停和恢复规则评估。
当规则评估到达子网时,StackEntry
会为外部路径段和子网段创建一个对象。首先评估子网段,当集合到达子网路径的末端时,该段被合并到该段外部节点的暂存列表中。然后恢复之前的 StackEntry
对象,现在可以处理子网的结果。这个过程有一个额外的好处,特别是对于 Accumulate
节点,所有工作都是在一个批次中完成的,然后再传播到子节点。
相同的堆栈系统用于有效的反向链接。当规则评估到达查询节点时,评估将暂停并将查询添加到堆栈中。然后评估查询以生成结果集,该结果集保存在内存位置中,以供恢复的 StackEntry
对象拾取并传播到子节点。如果查询本身调用了其他查询,则重复该过程,同时暂停当前查询并为当前查询节点设置新的评估。
⚠️ 从算法的实现也可以看出,算法在构建网络时会依据模式的顺序进行分段,Rete 算法也是如此,所以如果我们想最大化模式匹配的效率,在编写多个规则时也尽量保证模式类型和约束的一致顺序。例如:
保证模式类型顺序的一致:
//内连 `and`: Color( colorType : type ) and Person( favoriteColor == colorType ) //内连 `and` 带分组: Color( colorType : type ) and (Person( favoriteColor == colorType ) or Person( favoriteColor == colorType )) // 默认隐式的 `and`: Color( colorType : type ) Person( favoriteColor == colorType )
保证模式内部约束的顺序一致:
Person( age > 50, weight > 80 ) Person( age > 50, weight > 80, height > 2 )