Friday, July 06, 2007

Sequential Rete

Stateless and Stateful Sessions

With Rete you have a stateful session where objects can be asserted and modified over time, rules can also be added and removed. Now what happens if we assume a stateless session, where after the initial data set no more data can be asserted or modified (no rule re-evaluations) and rules cannot be added or removed? This means we can start to make assumptions to minimise what work the engine has to do.

Algorithm
  1. Order the Rules by salience and position in the ruleset (just sets a sequence attribute on the rule terminal node).
  2. Create an array, one element for each possible rule activation; element position indicates firing order.
  3. Turn off all node memories, except the right-input Object memory.
  4. Disconnect the LeftInputAdapterNode propagation, and have the Object plus the Node referenced in a Command object, which is added to a list on the WorkingMemory for later execution.
  5. Assert all objects, when all assertions are finished and thus right-input node memories are populated check the Command list and execute each in turn.
  6. All resulting Activations should be placed in the array, based upon the determined sequence number of the Rule. Record the first and last populated elements, to reduce the iteration range.
  7. Iterate the array of Activations, executing populated element in turn.
  8. If we have a maximum number of allowed rule executions, we can exit our network evaluations early to fire all the rules in the array.
The LeftInputAdapterNode no longer creates a Tuple, adding the Object, and then propagate the Tuple – instead a Command Object is created and added to a list in the Working Memory. This Command Object holds a reference to the LeftInputAdapterNode and the propagated Object. This stops any left-input propagations at assertion time, so that we know that a right-input propagation will never need to attempt a join with the left-inputs (removing the need for left-input memory). All nodes have their memory turned off, including the left-input Tuple memory but excluding the right-input Object memory – i.e. The only node that remembers an assertion propagation is the right-input Object memory. Once all the assertions are finished, and all right-input memories populated, we can then iterate the list of LeftInputAdatperNode Command objects calling each in turn; they will propagate down the network attempting to join with the right-input objects; not being remembered in the left input, as we know there will be no further object assertions and thus propagations into the right-input memory.

There is no longer an Agenda, with a priority queue to schedule the Tuples, instead there is simply an array for the number of rules. The sequence number of the RuleTerminalNode indicates the element with the array to place the Activation. Once all Command Objects have finished we can iterate our array checking each element in turn and firing the Activations if they exist. To improve performance in the array we remember record the first and last populated cells.

The network is constructed where each RuleTerminalNode is given a sequence number, based on a salience number and its order of being added to the network.

Data Structures
Typically the right-input node memories are HashMaps, for fast Object retraction, as we know there will be no Object retractions, we can use a list when the values of the Object are not indexed. For larger numbers of Objects indexed HashMaps provide a performance increase; if we know an Object type has a low number of instances then indexing is probably not of an advantage and an Object list can be used.

Everything to the above paragraph is in JBoss Rules 4.0, the following sections are idea for the future, and thus still a bit vague at the moment.

If there is a huge number of rules a indexed paged direct address table can be used in place of the array that holds the resulting Activations. Here we create pages of arrays, we create further index points to pages at regular points in the range. The page can indicate if any of its elements are populated or not, allow us to skip iterations of those elements.

Collapsing Nodes, Code Generation and Node Ordering
Stateful Rete can have nodes added and removed, for this reason to maximum node sharing we tend to have an AlphaNode per literal constraint. However as we know we will not have any more rules added we can collapse shared nodes into a single evaluation. If we have a chain of 3 AlphaNodes A, B and C. where A and B are shared and C isn't. We can collapse A and B into a single node and generate code to do the multiple evaluations natively. Node ordering can be changed to maximise sharing and thus the impact of Collapsing them. There may also be some level of beta node collapsing we can do, but I have'nt given that side much thought yet.

Exploiting Multi-Threading
In normal Rete exploiting multiple threads is hard, as you never know if a Tuple is going to enter the left-input or an Object is going to enter the right-input – i.e. reads and writes can happy simultaneously, the effect of adding locks to control this is expensive and past research has shown the costs are more than using lock free single thread approach. However with our sequential approach we know that the writes will always happen at different time to the reads. All writes happen during the first stage where objects are propagated to the right input nodes. All reads happen during Tuple propagation from the LeftInputAdapterNode. We can exploit this to execute parallel threads for each stage; using concurrent collection structures. We only have handle the synchronisation of the two stages – i.e. knowing when the all the Object propagations are finished and knowing when all the Tuple propagations are finished. Executing the actual rules in parallel is a little harder as we cannot easily know the user intention of the sequence. An attribute can be used to execute groups of rules that can be executed in parallel; those rules and groups must be specified in chronological order. i.e. If group A is to fire before group B, then all the rules for group A must be specified first. Or the execution order for the groups can be specified seperately, allowing rules to be more free formly tagged with the attributes.

14 comments:

  1. So far performance increases, compared to our standard Rete, is 30% to 350%, depending on the complexity and quantity of rules and data. Node collapsing should really help give that another boost too. In a point release we will be adding a fire Limit to the engine, an integer saying the number of allowed rule executions, we can use this to exit network evaluation early - so users can say if the current ruleset results in 1, 3 or 10 firing rules.

    ReplyDelete
  2. Oh and ofcourse the best thing is it still obeys all the complex Conditional Elements, like 'not', 'exists', 'accumulate', 'collect' etc.

    ReplyDelete
  3. good work. now if only I had enough time to write all the rules in the benchmark suite. if only I could go without sleep, it would get done sooner than later :)

    ReplyDelete
  4. At the moment we are finding the best scenarios are those involving large numbers of facts - say 50K - which gave us 350% increase over our standard Rete. As I understand it sequential only scales well for large numbers of rules, not facts? Small number of facts and large rules for our sequential has less dramatic increases, but it is still better than our standard Rete 30%+, suspect that's where node collapsing and more code generation will help.

    ReplyDelete
  5. Hi Mark,

    I am using a stateless session and using the following drl

    package a

    import test.QuoteType;

    rule "a1"
    no-loop true
    salience 999999
    when
    QuoteType:QuoteType()
    eval(
    (
    (QuoteType.getQuoteNumber().equals("abc"))
    )
    )
    then
    QuoteType.setVendorName(String.valueOf("vendor1"));
    System.out.println("a1");

    update(QuoteType);
    end
    rule "a2"
    no-loop true
    salience 999998
    when
    QuoteType:QuoteType()
    eval (
    (
    (QuoteType.getVendorName().equals("vendor1"))
    )
    )
    then
    QuoteType.setDealerName(String.valueOf("dealer1"));
    System.out.println("a2");
    update(QuoteType);
    end


    I am still facing the recursion problem, its not executing in a sequential manner.

    Thoughts!!!

    ReplyDelete
  6. Hi Mark,

    I also tried drl in the following way

    package a

    import test.QuoteType;

    rule "a1"
    no-loop true
    salience 999999
    when
    QuoteType:QuoteType()
    eval(
    (
    (QuoteType.getQuoteNumber().equals("abc"))
    )
    )
    then
    QuoteType.setVendorName(String.valueOf("vendor1"));
    System.out.println("a1");

    update(QuoteType);
    end
    rule "a2"
    no-loop true
    salience 999998
    when
    QuoteType:QuoteType()
    eval (
    (
    (QuoteType.getVendorName().equals("vendor1"))
    )
    )
    then
    QuoteType.setDealerName(String.valueOf("dealer1"));
    System.out.println("a2");
    #update(QuoteType);
    end

    It worked this way

    Thoughts!!!

    ReplyDelete
  7. Hi Mark,

    Just a last thought. My last requirement is i want modified object to be propagated to the next rule but do not re firing of the rules.

    Your thoughts!!

    cheers,
    Gaurav

    ReplyDelete
  8. StatelessSessions are not sequential as default, you must turn them on. Either by the use of a property or a setter.

    RuleBaseConfiguration conf = new RuleBaseConfiguration();
    conf.setSequential(true);

    RuleBase ruleBase = RuleBaseFactory.newRuleBase( conf );

    Or in a rulebase.conf properties file in a META-INF directory somewhere, or a System property, you can add the property:
    drools.sequential = true.

    In sequential mode all rules are first evaluated, it does not evaluate each rule in turn. So it doesn't evaluate the first rule, modify the data and then evaluate the second rule. If you modify some data the next rule in the sequence will execute with that modified data, even if it's LHS is no longer true.

    Why are you writing rules like this:
    QuoteType:QuoteType()
    eval(((QuoteType.getQuoteNumber().equals("abc"))))

    this is much better, eval should be avoided, unless it's really needed:
    when
    $quoteType : QuoteType( quoteNumber == "abc" )
    then
    ...

    For further help please use the mailing lists:
    http://labs.jboss.com/drools/lists.html

    ReplyDelete
  9. hi mark,
    thanks for you help. I have been researching on your work for the last year.
    The reason I am using eval is, I am working on rule generation, and evaivalent ui to support it. UI is designed in way, a guy who is non technical i.e. business analyst can work on it with ease. I do have an idea to avoid, but i enter in trouble water when list comes into picture (while generation of rule automatically)

    I have not used BRXML approach as you have used in the BRMS

    Your thoughts will be source of inspiration for me.

    Regards,
    Gaurav Malhotra

    ReplyDelete
  10. This comment has been removed by the author.

    ReplyDelete
  11. This comment has been removed by the author.

    ReplyDelete
  12. If you use eval your rules are neither declarative or able to execute in a performant manner. The Pattern field constraint I showed you is orders of magnitudes faster than what you are trying. With the correct approach there should be no reason why you have to resort to evals.

    ReplyDelete
  13. As in Drools version 4.0, we could use eval in Pattern Descriptor itself.
    Here is the sample drl.


    package discounts
    import com.test.Customer
    import com.test.Employee

    rule "NestedEval"
    when
    Employee:Employee()
    Customer:Customer(eval(Employee.getName().equals(name + Employee.getCompanyName())))
    then
    Customer.setDiscountAvail(10);
    end

    rule "Eval"
    when
    Customer:Customer()
    Employee:Employee()
    eval(!Employee.getName().equals(Customer.getName() + Employee.getCompanyName()))
    then
    Customer.setDiscountAvail(5);
    end

    Would you please put your thoughts on the difference of these two rules?
    And what is best way if we want to do calculation in WHEN part of RULE.

    -Regards
    Tarun Kumar Singh

    ReplyDelete
  14. Please use the mailing list for these types of questions, especially when they are not related to the blog article in question. the answer to your Q is one happens before the join data and one after, thus the inline-eval is slightly more efficient, also data must be time constant in inline-eval but not for eval.

    ReplyDelete