Chapter 84. Phreak rule algorithm in the decision engine

The decision engine in Red Hat Decision Manager uses the Phreak algorithm for rule evaluation. Phreak evolved from the Rete algorithm, including the enhanced Rete algorithm ReteOO that was introduced in previous versions of Red Hat Decision Manager for object-oriented systems. Overall, Phreak is more scalable than Rete and ReteOO, and is faster in large systems.

While Rete is considered eager (immediate rule evaluation) and data oriented, Phreak is considered lazy (delayed rule evaluation) and goal oriented. The Rete algorithm performs many actions during the insert, update, and delete actions in order to find partial matches for all rules. This eagerness of the Rete algorithm during rule matching requires a lot of time before eventually executing rules, especially in large systems. With Phreak, this partial matching of rules is delayed deliberately to handle large amounts of data more efficiently.

The Phreak algorithm adds the following set of enhancements to previous Rete algorithms:

  • Three layers of contextual memory: Node, segment, and rule memory types
  • Rule-based, segment-based, and node-based linking
  • Lazy (delayed) rule evaluation
  • Stack-based evaluations with pause and resume
  • Isolated rule evaluation
  • Set-oriented propagations

84.1. Rule evaluation in Phreak

When the decision engine starts, all rules are considered to be unlinked from pattern-matching data that can trigger the rules. At this stage, the Phreak algorithm in the decision engine does not evaluate the rules. The insert, update, and delete actions are queued, and Phreak uses a heuristic, based on the rule most likely to result in execution, to calculate and select the next rule for evaluation. When all the required input values are populated for a rule, the rule is considered to be linked to the relevant pattern-matching data. Phreak then creates a goal that represents this rule and places the goal into a priority queue that is ordered by rule salience. Only the rule for which the goal was created is evaluated, and other potential rule evaluations are delayed. While individual rules are evaluated, node sharing is still achieved through the process of segmentation.

Unlike the tuple-oriented Rete, the Phreak propagation is collection oriented. For the rule that is being evaluated, the decision engine accesses the first node and processes all queued insert, update, and delete actions. The results are added to a set, and the set is propagated to the child node. In the child node, all queued insert, update, and delete actions are processed, adding the results to the same set. The set is then propagated to the next child node and the same process repeats until it reaches the terminal node. This cycle creates a batch process effect that can provide performance advantages for certain rule constructs.

The linking and unlinking of rules happens through a layered bit-mask system, based on network segmentation. When the rule network is built, segments are created for rule network nodes that are shared by the same set of rules. A rule is composed of a path of segments. In case a rule does not share any node with any other rule, it becomes a single segment.

A bit-mask offset is assigned to each node in the segment. Another bit mask is assigned to each segment in the path of the rule according to these requirements:

  • If at least one input for a node exists, the node bit is set to the on state.
  • If each node in a segment has the bit set to the on state, the segment bit is also set to the on state.
  • If any node bit is set to the off state, the segment is also set to the off state.
  • If each segment in the path of the rule is set to the on state, the rule is considered linked, and a goal is created to schedule the rule for evaluation.

The same bit-mask technique is used to track modified nodes, segments, and rules. This tracking ability enables an already linked rule to be unscheduled from evaluation if it has been modified since the evaluation goal for it was created. As a result, no rules can ever evaluate partial matches.

This process of rule evaluation is possible in Phreak because, as opposed to a single unit of memory in Rete, Phreak has three layers of contextual memory with node, segment, and rule memory types. This layering enables much more contextual understanding during the evaluation of a rule.

Figure 84.1. Phreak three-layered memory system

LayeredMemory enterprise

The following examples illustrate how rules are organized and evaluated in this three-layered memory system in Phreak.

Example 1: A single rule (R1) with three patterns: A, B and C. The rule forms a single segment, with bits 1, 2, and 4 for the nodes. The single segment has a bit offset of 1.

Figure 84.2. Example 1: Single rule

segment1 enterprise

Example 2: Rule R2 is added and shares pattern A.

Figure 84.3. Example 2: Two rules with pattern sharing

segment2 enterprise

Pattern A is placed in its own segment, resulting in two segments for each rule. Those two segments form a path for their respective rules. The first segment is shared by both paths. When pattern A is linked, the segment becomes linked. The segment then iterates over each path that the segment is shared by, setting the bit 1 to on. If patterns B and C are later turned on, the second segment for path R1 is linked, and this causes bit 2 to be turned on for R1. With bit 1 and bit 2 turned on for R1, the rule is now linked and a goal is created to schedule the rule for later evaluation and execution.

When a rule is evaluated, the segments enable the results of the matching to be shared. Each segment has a staging memory to queue all inserts, updates, and deletes for that segment. When R1 is evaluated, the rule processes pattern A, and this results in a set of tuples. The algorithm detects a segmentation split, creates peered tuples for each insert, update, and delete in the set, and adds them to the R2 staging memory. Those tuples are then merged with any existing staged tuples and are executed when R2 is eventually evaluated.

Example 3: Rules R3 and R4 are added and share patterns A and B.

Figure 84.4. Example 3: Three rules with pattern sharing

segment3 enterprise

Rules R3 and R4 have three segments and R1 has two segments. Patterns A and B are shared by R1, R3, and R4, while pattern D is shared by R3 and R4.

Example 4: A single rule (R1) with a subnetwork and no pattern sharing.

Figure 84.5. Example 4: Single rule with a subnetwork and no pattern sharing

segment4 enterprise

Subnetworks are formed when a Not, Exists, or Accumulate node contains more than one element. In this example, the element B not( C ) forms the subnetwork. The element not( C ) is a single element that does not require a subnetwork and is therefore merged inside of the Not node. The subnetwork uses a dedicated segment. Rule R1 still has a path of two segments and the subnetwork forms another inner path. When the subnetwork is linked, it is also linked in the outer segment.

Example 5: Rule R1 with a subnetwork that is shared by rule R2.

Figure 84.6. Example 5: Two rules, one with a subnetwork and pattern sharing

segment5 enterprise

The subnetwork nodes in a rule can be shared by another rule that does not have a subnetwork. This sharing causes the subnetwork segment to be split into two segments.

Constrained Not nodes and Accumulate nodes can never unlink a segment, and are always considered to have their bits turned on.

The Phreak evaluation algorithm is stack based instead of method-recursion based. Rule evaluation can be paused and resumed at any time when a StackEntry is used to represent the node currently being evaluated.

When a rule evaluation reaches a subnetwork, a StackEntry object is created for the outer path segment and the subnetwork segment. The subnetwork segment is evaluated first, and when the set reaches the end of the subnetwork path, the segment is merged into a staging list for the outer node that the segment feeds into. The previous StackEntry object is then resumed and can now process the results of the subnetwork. This process has the added benefit, especially for Accumulate nodes, that all work is completed in a batch, before propagating to the child node.

The same stack system is used for efficient backward chaining. When a rule evaluation reaches a query node, the evaluation is paused and the query is added to the stack. The query is then evaluated to produce a result set, which is saved in a memory location for the resumed StackEntry object to pick up and propagate to the child node. If the query itself called other queries, the process repeats, while the current query is paused and a new evaluation is set up for the current query node.

84.1.1. Rule evaluation with forward and backward chaining

The decision engine in Red Hat Decision Manager is a hybrid reasoning system that uses both forward chaining and backward chaining to evaluate rules. A forward-chaining rule system is a data-driven system that starts with a fact in the working memory of the decision engine and reacts to changes to that fact. When objects are inserted into working memory, any rule conditions that become true as a result of the change are scheduled for execution by the agenda.

In contrast, a backward-chaining rule system is a goal-driven system that starts with a conclusion that the decision engine attempts to satisfy, often using recursion. If the system cannot reach the conclusion or goal, it searches for subgoals, which are conclusions that complete part of the current goal. The system continues this process until either the initial conclusion is satisfied or all subgoals are satisfied.

The following diagram illustrates how the decision engine evaluates rules using forward chaining overall with a backward-chaining segment in the logic flow:

Figure 84.7. Rule evaluation logic using forward and backward chaining

RuleEvaluation Enterprise

84.2. Rule base configuration

Red Hat Decision Manager contains a RuleBaseConfiguration.java object that you can use to configure exception handler settings, multithreaded execution, and sequential mode in the decision engine.

For the rule base configuration options, download the Red Hat Decision Manager 7.11.0 Source Distribution ZIP file from the Red Hat Customer Portal and navigate to ~/rhdm-7.11.0-sources/src/drools-$VERSION/drools-core/src/main/java/org/drools/core/RuleBaseConfiguration.java.

The following rule base configuration options are available for the decision engine:

drools.consequenceExceptionHandler

When configured, this system property defines the class that manages the exceptions thrown by rule consequences. You can use this property to specify a custom exception handler for rule evaluation in the decision engine.

Default value: org.drools.core.runtime.rule.impl.DefaultConsequenceExceptionHandler

You can specify the custom exception handler using one of the following options:

  • Specify the exception handler in a system property:

    drools.consequenceExceptionHandler=org.drools.core.runtime.rule.impl.MyCustomConsequenceExceptionHandler
  • Specify the exception handler while creating the KIE base programmatically:

    KieServices ks = KieServices.Factory.get();
    KieBaseConfiguration kieBaseConf = ks.newKieBaseConfiguration(); kieBaseConf.setOption(ConsequenceExceptionHandlerOption.get(MyCustomConsequenceExceptionHandler.class));
    KieBase kieBase = kieContainer.newKieBase(kieBaseConf);
drools.multithreadEvaluation

When enabled, this system property enables the decision engine to evaluate rules in parallel by dividing the Phreak rule network into independent partitions. You can use this property to increase the speed of rule evaluation for specific rule bases.

Default value: false

You can enable multithreaded evaluation using one of the following options:

  • Enable the multithreaded evaluation system property:

    drools.multithreadEvaluation=true
  • Enable multithreaded evaluation while creating the KIE base programmatically:

    KieServices ks = KieServices.Factory.get();
    KieBaseConfiguration kieBaseConf = ks.newKieBaseConfiguration();
    kieBaseConf.setOption(MultithreadEvaluationOption.YES);
    KieBase kieBase = kieContainer.newKieBase(kieBaseConf);
Warning

Rules that use queries, salience, or agenda groups are currently not supported by the parallel decision engine. If these rule elements are present in the KIE base, the compiler emits a warning and automatically switches back to single-threaded evaluation. However, in some cases, the decision engine might not detect the unsupported rule elements and rules might be evaluated incorrectly. For example, the decision engine might not detect when rules rely on implicit salience given by rule ordering inside the DRL file, resulting in incorrect evaluation due to the unsupported salience attribute.

drools.sequential

When enabled, this system property enables sequential mode in the decision engine. In sequential mode, the decision engine evaluates rules one time in the order that they are listed in the decision engine agenda without regard to changes in the working memory. This means that the decision engine ignores any insert, modify, or update statements in rules and executes rules in a single sequence. As a result, rule execution may be faster in sequential mode, but important updates may not be applied to your rules. You can use this property if you use stateless KIE sessions and you do not want the execution of rules to influence subsequent rules in the agenda. Sequential mode applies to stateless KIE sessions only.

Default value: false

You can enable sequential mode using one of the following options:

  • Enable the sequential mode system property:

    drools.sequential=true
  • Enable sequential mode while creating the KIE base programmatically:

    KieServices ks = KieServices.Factory.get();
    KieBaseConfiguration kieBaseConf = ks.newKieBaseConfiguration();
    kieBaseConf.setOption(SequentialOption.YES);
    KieBase kieBase = kieContainer.newKieBase(kieBaseConf);
  • Enable sequential mode in the KIE module descriptor file (kmodule.xml) for a specific Red Hat Decision Manager project:

    <kmodule>
      ...
      <kbase name="KBase2" default="false" sequential="true" packages="org.domain.pkg2, org.domain.pkg3" includes="KBase1">
        ...
      </kbase>
      ...
    </kmodule>

84.3. Sequential mode in Phreak

Sequential mode is an advanced rule base configuration in the decision engine, supported by Phreak, that enables the decision engine to evaluate rules one time in the order that they are listed in the decision engine agenda without regard to changes in the working memory. In sequential mode, the decision engine ignores any insert, modify, or update statements in rules and executes rules in a single sequence. As a result, rule execution may be faster in sequential mode, but important updates may not be applied to your rules.

Sequential mode applies to only stateless KIE sessions because stateful KIE sessions inherently use data from previously invoked KIE sessions. If you use a stateless KIE session and you want the execution of rules to influence subsequent rules in the agenda, then do not enable sequential mode. Sequential mode is disabled by default in the decision engine.

To enable sequential mode, use one of the following options:

  • Set the system property drools.sequential to true.
  • Enable sequential mode while creating the KIE base programmatically:

    KieServices ks = KieServices.Factory.get();
    KieBaseConfiguration kieBaseConf = ks.newKieBaseConfiguration();
    kieBaseConf.setOption(SequentialOption.YES);
    KieBase kieBase = kieContainer.newKieBase(kieBaseConf);
  • Enable sequential mode in the KIE module descriptor file (kmodule.xml) for a specific Red Hat Decision Manager project:

    <kmodule>
      ...
      <kbase name="KBase2" default="false" sequential="true" packages="org.domain.pkg2, org.domain.pkg3" includes="KBase1">
        ...
      </kbase>
      ...
    </kmodule>

To configure sequential mode to use a dynamic agenda, use one of the following options:

  • Set the system property drools.sequential.agenda to dynamic.
  • Set the sequential agenda option while creating the KIE base programmatically:

    KieServices ks = KieServices.Factory.get();
    KieBaseConfiguration kieBaseConf = ks.newKieBaseConfiguration();
    kieBaseConf.setOption(SequentialAgendaOption.DYNAMIC);
    KieBase kieBase = kieContainer.newKieBase(kieBaseConf);

When you enable sequential mode, the decision engine evaluates rules in the following way:

  1. Rules are ordered by salience and position in the rule set.
  2. An element for each possible rule match is created. The element position indicates the execution order.
  3. Node memory is disabled, with the exception of the right-input object memory.
  4. The left-input adapter node propagation is disconnected and the object with the node is referenced in a Command object. The Command object is added to a list in the working memory for later execution.
  5. All objects are asserted, and then the list of Command objects is checked and executed.
  6. All matches that result from executing the list are added to elements based on the sequence number of the rule.
  7. The elements that contain matches are executed in a sequence. If you set a maximum number of rule executions, the decision engine activates no more than that number of rules in the agenda for execution.

In sequential mode, the LeftInputAdapterNode node creates a Command object and adds it to a list in the working memory of the decision engine. This Command object contains references to the LeftInputAdapterNode node and the propagated object. These references stop any left-input propagations at insertion time so that the right-input propagation never needs to attempt to join the left inputs. The references also avoid the need for the left-input memory.

All nodes have their memory turned off, including the left-input tuple memory, but excluding the right-input object memory. After all the assertions are finished and the right-input memory of all the objects is populated, the decision engine iterates over the list of LeftInputAdatperNode Command objects. The objects propagate down the network, attempting to join the right-input objects, but they are not retained in the left input.

The agenda with a priority queue to schedule the tuples is replaced by an element for each rule. The sequence number of the RuleTerminalNode node indicates the element where to place the match. After all Command objects have finished, the elements are checked and existing matches are executed. To improve performance, the first and the last populated cell in the elements are retained.

When the network is constructed, each RuleTerminalNode node receives a sequence number based on its salience number and the order in which it was added to the network.

The right-input node memories are typically hash maps for fast object deletion. Because object deletions are not supported, Phreak uses an object list when the values of the object are not indexed. For a large number of objects, indexed hash maps provide a performance increase. If an object has only a few instances, Phreak uses an object list instead of an index.