Geeks With Blogs

News
Charles Young

I have had some fun in the last couple of weeks debating the Microsoft Rules Engine with Peter Lin.   Many people in the BizTalk community will know that Peter used Amazon and The ServerSide site early this year to launch an attack on Microsoft's representation of their rules engine.  You can read the original thread here.  Based on a BizTalk performance whitepaper, the latest version of which is here, and on the documentation of the Rules Engine on MSDN, he deduced that that the engine does not implement the Rete algorithm correctly, does not support forward chaining inferencing and does not scale.   For the uninitiated reader, the Rete (Latin for 'Net', pronounced "Ray-tee" according to my Latin-English dictionary, or "Ree-tee" if you believe everything you read on the Internet).algorithm is the most commonly used algorithm within inferencing rules engines, and implements a number of important optimisations by establishing, at runtime, a directed acyclic graph of memory nodes to represent a rule set, and retaining information about matches as data ('facts') pass through the nodes.  

At the time, Scott Woodgate had some involvement in the debate, and confirmed that the Microsoft Business Rules Engine does indeed implement the Rete algorithm (see his comments here).   I regretted, at the time, not challenging Peter's assertions, and over the months have had it in mind to tackle the issue at some point.   My opportunity came a few weeks ago when the issue arose again on the TSS site.   There has followed a debate in which I have chiefly aimed at showing that Peter has no grounds whatsoever for the claims he makes.  You can read the thread here.   I cannot (and really don't need to) 'prove' that Microsoft has implemented their engine correctly, but I can and do show that the performance figures published by Microsoft provide no evidence of an incorrect implementation.    To this end, I have published the results of some simple tests here.   Peter has also raised a number of concerns based on the documentation of the rules framework API, and has also highlighted the "side effects" feature.   I do admit the the "side effects" feature is 'impure', although I consider it a very practical feature, but I contest that it somehow invalidates Microsoft's implementation.   Other API issues, such as Peter's recent comments about the Assert class (see here), are based on a fundamental misunderstanding of what he is reading on MSDN.

If you enjoy this sort of stuff, do please feel free to read and join in the fun!!

Posted on Saturday, September 17, 2005 3:25 PM Microsoft Business Rule Framework | Back to top


Comments on this post: BizTalk Server 2004: The great MS Business Rule Engine Debate

# Debating Our Rules Engine
Requesting Gravatar...

If you're someone deeply interested in rule engine algorithms, and specifically Microsoft's implementation...
Left by Richard Seroter - SoCal BPI Musi on Sep 17, 2005 12:48 PM

# re: BizTalk Server 2004: The great MS Business Rule Engine Debate
Requesting Gravatar...
yeah I have been reading Peter's battle with the Biztalk over at TSS alot. He sends my head spinning
Left by David Li on Sep 19, 2005 3:41 PM

# re: BizTalk Server 2004: The great MS Business Rule Engine Debate
Requesting Gravatar...
Charles,

It is surely a very interesting read, but I honestly never encountered a real world scenario where the client actually had more than 500 rules in a single policy (ruleset).

Honestly if you have even that many rules in one rule policy, you might want to consider some different rule formats like Lookup tables, Decision Tables, or Decision Trees. These formats will combine a group of rules with the same structure.

Although I never seen very large rulesets, I do encounter very large datasets (many objects). Your test was about scalibility of the rules, do you have any idea how it scales with many facts active in working memory?




Left by Marco Ensing on Sep 20, 2005 1:14 PM

# re: BizTalk Server 2004: The great MS Business Rule Engine Debate
Requesting Gravatar...
I think you may be missing the point :-) The issue is that since late last year, claims have been circulating that the Microsoft Business Rule Engine mis-implements the Rete algorithm, which is the most widely used, and arguably the most scalable, algorithm for inferencing engines. The point of this article was to show that the claims were groundless. The claims were, in part, based on a set of performance results published by Microsoft which used large, simple, rulesets. The tests Microsoft did were so simplistic that they completely failed to expolit the various optimisations offered by Rete, and hence the apparantly 'nice' linear scale result they published sent the wrong message to those who are acquainted with how the Rete algorithm operates. It actually seemed to suggest there may be something wrong with their implementation. The point of the test results I've published is to show that any Rete engine will give the same results when operating with such simple rules.

The issues you raise are, neverthless, very interesting. I worked on a BizTalk proof-of- concept a few months ago which, in the production version, would process rulesets with hundreds, or even thousands, of rules, and this is, perhaps, not an unusual as you might think. Certainly, if the rules are very basic (e.g., something like 'if x = 1 then DoSomething()'), then the Rete algorithm may indeed have little or nothing to offer, and you may be better off using another technique. Even here, though, you should not jump to conclusions too readily. If the ratio of discrete fact types to rule conditions is high, then you could be hard-pressed to come up with a more efficient algorithm. Again, if common terms are used across multiple rules, or if your rules perform joins between facts (e.g., 'if x = y then DoSomething() ), then the Rete algorithm quickly becomes much more interesting as its various optimisations kick in. Of course, the real power comes in inferencing scenarios where, starting with a set of initial facts, the engine cycles through a match-resolve-act loop and infers new data. This is where the Rete algorithm really comes to the fore, especially in its efficiency in managing changes to the working memory in terms of deltas, rather than performing huge amount of re-evaluation.

What I do agree with (and what I have often tried to communicate in the work I do) is that you should never assume that all business rules should be processed through a business rule engine. There are many scenarios where either for technical or business reasons, the use of the MS-BRE, or an equivalent engine, would be inappropriate. There are many other scenarios where it would be the most appropriate approach tool to use. One day, when I get back to blogging, I might have a go at trying to distil some thoughts and see if I can get a productive discussion going.
Left by Charles Young on Sep 20, 2005 6:23 PM

# re: BizTalk Server 2004: The great MS Business Rule Engine Debate
Requesting Gravatar...
I constantly have the problem these days that colleagues think I am going to champion Rete to the detriment of all other approaches. Actually, in over two years of BizTalk programming, I have only worked on one project that really, really needed a Rete-based inferencing engine - and we didn't realise until it was too late!! I strongly agree with Jurgen Willis of Microsoft who has been working on a sequential engine for Windows Workflow Foundation. He argues that a sequential approach is generally easier to understand and implement, and will cater for the vast number of scenarios that workflow developers will face. I think he is right. I also think that, in real-world programming, having a good toolset for capturing, refining, versioning and publishing rule sets is often of greater worth than having the most highly performant engine on the planet, which is an argument I have made to Jurgen. We have often ended up using MS BRE for this one reason, rather than its pattern matching, inferencing features. I believe we will need a WF rules repository and accompanying toolset, although I don't think that is planned for the forthcoming release.

Rete engines are pattern matching machines that are good at solving combinatorial problems (problems where you have to repeatedly do a lot of joins on different data), and where repeated cycles are required to infer new data from existing data. Sequential engines (even engines, like WF's which support a form of forward chaining) have very different characteristics, and are good for step management and simple (lightweight) decision logic.

As regards product comparison, I agree with what you say. A year ago I implemented a variant of the Miss Manners benchmark for the MS BRE. It had to be a variant because MS BRE does not support negated conjunction :-(, making it impossible to implement that particular benchmark 'correctly'. I learned a lot about the MS BRE, and I also learned a lot about the Miss Manners benchmark, which is so often used by vendors to provide dubious 'proof' of the performance of their engines. I learned nothing really about the performance of the MS BRE, save a rather general observation that it seems to perform reasonably. I did learn that Miss Manners is heavily weighted towards testing negated conjunction (the majority of the work done in the test centres on just two negated join nodes), and that it therefore mainly tells you if a vendor has optimised this one aspect of their engine. this is worth knowing, but what about simple rule sets that don't use negated conjunction? Miss Manners tells you little about engine performance in these scenarios. And it's so easy to cheat the benchmark (you can add one condition to a rule, and get the 128 guest test to complete correctly in a second or so, rather than the 40 seconds to several minutes typical for a range of engines). I had an excuse when implementing a mere variant of Miss Manners for MS BRE, but vendors have sometimes been unscrupulous in their use of, and claims in regard to, Miss Manners. Don't believe a word they say.

We are considering publishing a whitepaper about the lessons learned from our Miss Manners variant for MS BRE (indeed, I have drafted the paper already). There are some commercial considerations, and it may never by published, but I will post here if we decide to go ahead.

Oh, and I repeat what I said before. The issue (this is now ancient history) is that claims were being made that Microsoft had mis-implemented the Rete algorithm. I know of at least one case where this had a negative impact on BizTalk commercially (people understandably link the MS BRE to BizTalk in their thinking), and I wanted to combat the mis-information. Microsoft should implement negated conjunction, for sure. And their approach to conflict resolution is, er..., debatable. Peter has questions about their approach to truth maintenance, though I have come to consider this a reasonably sensible design when understood against the backdrop of MS BRE's great strength, which is its agility in applying rules directly over business data in 'native' formats (.NET objects, XML, data rows and tables, and live database connections). However, their core implementation of the Rete algorithm is classic, 'text-book', and altogether correct.
Left by Charles Young on Apr 20, 2006 8:25 PM

Your comment:
 (will show your gravatar)


Copyright © Charles Young | Powered by: GeeksWithBlogs.net