Alexandre Alves wrote an interesting article on CEP extensions for Logic Programming (see http://adcalves.wordpress.com/2009/10/30/logic-programming-lp-extensions-for-cep/) in which he discusses the use of Rete-based rules engines. I gave a presentation at a conference last week (October Rules Fest 2009) on the differences and similarities between various event stream processing (ESP) approaches and the Rete algorithm. I had a slide that is not very different in intent to Alexandre's post. I also touched on performance issues, which is something he talks about briefly. I don't know of any solid, well thought out, comparative benchmarking between any of the major ESP and CEP-enabled Rete engines, so I can only hazard informed guesses with regard to likely performance issues. I thought it would be useful to summarise some of my thinking in this area.
Rete is a well-defined approach which results in most of the modern inference engines exhibiting broadly similar characteristics. Things are far more varied in the event stream processing world, and vendors often claim that their 'secret sauce' is superior to their competitors. Most ESP and virtually all Rete engines use explicit dataflow networks consisting of nodes that perform different operations on streams of events/facts. Many commercial ESP engines use a fair degree of set-based processing internally. They materialise views of data and operate on those views. They may also utilise stream-orientated approaches. A few engines (mainly in the academic and research worlds at present) major on stream-orientated approaches that largely avoid materialised views. A Rete dataflow combines set-based and stream-orientated processing side-by-side. I won't go into the details here, but essentially most ESP and Rete engines are really quite similar internally, which is why CEP has become such a live issue in the Rete world.
Rete engines make a very specific set of trade-offs, and these are often a little different to ESP engines. Rete majors on reduction of certain types of redundancy. The idea is to compile a set of rules into a single network. Rules are reactive, but their left-hand-side is essentially much the same as a query. Traditionally, Rete engines have only supported continuous forms of rule evaluation as a secondary feature, if at all. Obviously, continuous evaluation is now becoming more important in the Rete world as several engines are extended with CEP features. So, a rule set is broadly synonymous to a set of continuous queries in an ESP engine. Rete compiles each rule set into a single dataflow network in order to reduce redundant processing as much as possible. If the same condition appears in multiple rules, it is represented at just one single node in the network, however many rules there are in the rule set. In order to reduce redundancy as much as possible, Rete takes a fine-grained approach to data storage. Join nodes (equivalent to a join operator is an ESP engine) take a stream of data as an input and compare each event/fact in that stream to data previously stored in a memory. A memory is simply a materialised view of data. In traditional Rete, a single join node never performs joins on multiple memories. The results of each join are materialised in another memory. So, Rete maximises redundant node elimination at the cost of maximising the number of memories within the network. Is this better or worse than an ESP engine? I really don't know. ESP engines tend to implement far less aggressive redundancy elimination, and may create a separate dataflow for each continuous query. So, that is bad, compared to Rete. However, they may not naturally create as many materialised views along a given branch of the dataflow, which is better than Rete. I suspect that comparison using multiple benchmarks would probably yield mixed results in terms of work undertaken across multiple queries/rules, and resulting memory usage.
Rete's 'holistic' approach (creating a single network over multiple rules) is great in heavy-duty inferencing scenarios, and indeed, Rete, in the context of a production system, offers much stronger inferencing features than today's ESP engines. This is because of its use of an agenda (with conflict resolution) coupled with forward chaining and, in some cases, backward chaining. The redundancy elimination in Rete is vital in chaining scenarios, and aggressively minimises the amount of work required to re-compute the agenda. This is an area where ESP engines don't generally compete.
The 'holistic' approach, coupled with the agenda, is very powerful, but again represents a set of trade-offs. Specifically, it relies heavily on careful synchronisation within the Rete network and across the engine as a whole. The details get a little complex, but are well understood. Inevitably, this means that Rete is not the best of candidates for multi-threading and parallelism. Indeed, many Rete engines execute their Rete networks in a single-threaded fashion, and rely on the use of multiple engine instances and rule sets to exploit multi- threading. The benefit of parallelisation and multi-threading is therefore rather limited in Rete engines, though advances are still being made. By contrast, ESP engines generally employ a different set of trade-offs in which they can potentially benefit more from parallelisation.
Unfortunately, issues are still not quite as simple as we might wish. When vendors claim that their engines can process hundreds of thousands, or even millions of events a second, they are often using example queries which merely filter event streams, or which at most implement the most basic of pattern matching across, say, a couple of event types. If you look at Rete rules that only filter events/facts, there is no obvious reason why a well-optimised Rete engine should not be able to achieve similar latency and throughput characteristics. This is especially true if you create multiple rule sets, each containing a single rule, and then execute each one on a different thread. There really is no discernable difference that would lead you to claim that one class of engine is naturally more performant than another. If you create single-rule rule sets, however, you effectively undermine the distinctive reasons for using Rete. You might as well use an ESP engine. It makes little or no difference.
As queries become more complex, and perform more joins, my expectation would be that well-optimised ESP engines will generally outperform Rete engines for the types of query they are running because of synchronisation issues and the normal Rete practice of placing several rules in a single rule set. I am not, however, at all convinced that CEP-enabled Rete will always prove more memory-intensive than an ESP engine doing the same work - there are some myths about this, and I would expect a mixed picture to emerge. Moving on to the next level of complexity, Rete offers inferencing capabilities that ESP engines can only dream of. Hence, no direct comparison is possible. It is this area where Rete comes to the fore.
My conclusions from all this are fairly straight-forward. It is absolutely sensible to extend todays Rete engines with continuous processing modes, temporal logic and event semantics. However, Rete-based CEP agents are generally better used further downstream than ESP engines within event processing networks (EPNs). They are unlikely to compete with ESP engines in terms of ultra-low latency requirements, though they are perfectly capable of supporting reasonably low latency, and may exhibit indistinguishable performance characteristics to ESP engines in certain scenarios. They are natural tools to use in creating multiple levels of event abstraction hierarchies, and they are natural technologies to use at the boundary between EPNs and the rest of an event-driven architecture. They are well suited to combining ESP pattern-matching with contextual, non-event, data. Hence, they should be considered as a useful agent type within distributed EPNs to be used alongside other types of agent.
There has been a lot of discussion both in the CEP and Rete communities, about event semantics. Most of today's Rete engines do not support strong event semantics. There is no reason why such semantics should not be supported over Rete, but event immutability reduces the need for chaining because events are not generally modified. Hence, the distinctive characteristics of Rete are less important in a pure event-processing scenario. However, this argument, again, is not as straightforward as it first appears. Not only do some people (myself included) argue that events may legitimately exhibit a degree of mutability in some scenarios, modification is only one reason for chaining. Consider that in a Rete engine, a natural approach would be to assert one level of complex events in order to detect a more abstract level of complex events. This is why I stated above that Rete engines are natural tools for creating multiple levels of event abstraction hierarchies. Coupled with agenda focus approaches supported by most engines, they offer a powerful way of implementing this much-neglected aspect of CEP.
The 'holistic' nature of a Rete network is great for redundancy elimination, but makes operational maintenance of ESP applications harder. To change one rule is to change an entire network that represent multiple rules. If those rules are continuous queries, a single change to a rule can prove very disruptive in a live environment. As a general observation, ESP engines appear to handle these issues rather better.
One last observation. We are beginning to see the advent of 'hybrid' rules engines that combine separate ESP and Rete dataflows. Alexandre mentions the Drools engine (JBoss Rules) which is a good example. There are various ways of combining multiple dataflows, each with its own set of characteristics and trade-offs. It is still early days in the evolution of these hybrid engines, and we shall have to wait to see what evolves over time. Interestingly, the work (both commercial and research) undertaken so far has concentrated on the use of true stream-orientated approaches in the CEP dataflows, rather than set-based processing. One concern I have is that hybrid engines could lead to more complex higher-level languages, making these engines harder to understand and use. As I say, time will tell.
The slide ware and accompanying papers (I wrote two!) for the presentation at last week's conference are currently available only to conference attendees, but will be made public at some point. I provide a more detailed survey there of various different models for combining different CEP agents and dataflows, together with pros and cons of each approach.