On Event Processing Patterns

This is an illustration that has been created by my of my former colleagues to the AMiT team, Tali Yatzkar, when she attended a "presentation course" as an excercise in the course to explain what is an event processing pattern (we did not use this term at that time), this is the original picture, it is animated (the animation is not presevered when copying from file to picture) and the geometric shapes in the left-hand side of the picture are moving. The idea is simple, there are patterns that designate the relationship between a set of events, e.g. a conjuction: event E1 and event E2 both hoccur in the same context (e.g. relate to the same person within 2 hours). This rather simple idea is the jewel of the crown in event processing systems, and the basis of what David Luckham called: Complex Event Processing. It is also what makes a composite event in active database terminology (I have discussed in the past the subtle differences between those term definition). This illustration in some variations has a life of its own, and we saw it in presentations of some other companies and people, I even once had to comment on a Slideshare presentation when it was attributed to (see my comment to this presentation). Anyway, besides giving Tali her due credit, I am writing about event processing patterns, since one of the chapters we complete now for the second-third review of the EPIA book deals with the notion of event processing pattern as a major abstraction. As all abstractions in our meta-language, a specific languages may implement a certain pattern as a language primitive, or implement it through a combination of language primitives. Those interested in the formal definition will need to read the book since the formal definition require definitions of several terms, so I'll give some a less formal definition here -- pattern is really a function that takes a collection (or stream) of input events that satisfy some filtering assertions (e.g. they have to be within context, and have certain other patterns) and returns zero or more "matching sets", which include a collection of individual events that collectively satisfy the pattern. Let's take a couple of examples:

The first example: Bid example: There is a bid for some auction that has been provided on an auction site. The idea is to select a single winner. The input events are acution offering events and bid events. The bid events are partitioned according to the auction offering they are refering to, and are also filterred out according to time (each auction is open for a certain amount of time only) and according to threshold condition (has to be no less than a minimal price).The matching set in this case consists of a single bid event per auction offering. The matching pattern here is - "relative max", which means that any event that we are looking for the event with the relative (to the other input events) maximal value of some attribute (in this case the bid amount). Note that the "relative max" pattern does not necessarily provide a single bidder, thus we also need a "synonyms policy" to determine what happens when we have multiple events of the same type that match the criteria. In this case we take the fairness criterion of FCFS, and the synonyms policy will be -"first", meaning the first bidder that offerred the maximal price. In our meta-language this looks like:
Pattern name = Bidder selection; Pattern type = relative max; Input events = (Auction offering, Bid); Context = (segment = by auction offering, temporal = auction offering is open); Filtering assertion = (Bid.Price >= Auction Offering.Minimal Price); policies = (cardinality = single, synonyms = first)

Note that in these three and a quarter lines we have expressed logic that is quite complex, and this is the magic of patterns. As an exercise to the reader, write the equivalent logic in Java, and then change it so that it will chose all bidders that have provided the relative maximum for a second round of bids.

The second example is a sequence example, this figure is being taken from the EPIA book; the example is looking at the case in which a patient is released from the hospital and then admitted again within 48 hours with the same complain that brought this patient to the hospital in the first time.


Here we are looking for a sequence (the order is important, of course), of the patient release event, and the patient admission event for the same patient with the same complain within 48 hours. The definition in our meta-language will be roughly:

Pattern name = Repeating admission, Filter type = sequence, input events = (Patient Release, Patient Admission), Context = (segment = by patient and complain) temporal = Patient release + 48 hours).

This pattern creates a matching set which consists of a pair of events of types patient release and patient admission).

Note that the pattern return the selected events, and the EPA can derive new events as the function of these selected event.

Here we saw two type of patterns: relative max, which is a set oriented pattern, and sequence which is event oriented patterns. I'll provide the list of patterns collected so far in one of the future postings.

More on authors' dilemmas

One of the authors' dilemmas about the right way to write ab event processing book is about - whether the book should concentrate around an "event processing language". One of the reviewers indeed suggested that the language will be centered about a specific executable language, and describe the concepts using the language, for the concepts that are not supported in the language, the reviewer proposed to include them in advanced topics section.

The idea is not new to us, when we discussed with the publisher about the book's structure, we considered such "bottom up" approach, however, we decided that it is methodically better to take "top down" approach. There are two reasons for it: the first -- we are building the book in a methodical way, and talking about the building blocks that are required to build applications, since different languages took different approaches and often the implementation blurs the concept, we thought the the bottom up approach will be a good way to teach a particular language but not the concept; the second -- the current languages follow various programming styles. We neither want to concentrate on a single programming style, nor to do a comparison, as this is not the goal of this book.

So - how are we approaching this issue:

• We have constructed a descriptive meta-language that follows the concepts we are defining. We may also provide some visualization of this language (checking this issue now), and enable to play with this language on the future book's website.
• We have asked all language owners (and some have responded positively) to provide their own implementations of the use case we are using in the book. We shall put code samples in all relevant chapters as provided to demonstrate the different attitudes. I'll write soon some comments on the use case, following some questions from language owners.
  

Some footnotes to the forthcoming book "Event Processing in Action" - Take One

Last night, I went to see a movie (a rare event for me) -- and chose to see "Slumdog Millionaire", my daughter told me later that people who have not read the book enjoyed it more, the movie is OK, even cute, however -- for a movie who won 8 academy awards, I have somewhat bigger expectations (comparing for example to "Gone with the wind" who also had 8 academy awards. Well -- the movie industry is probably not peaking these days...


Today, together with (most of) my tribe, we have done some hiking in a place called "Judge River", well, river in the local terms, with a modest amount of water, but bridge, a lot of trees, some flowers, and since it is a holiday, a lot of people.

Now back home and like any Sunday morning I plan to go to one of the coffee shops (I am rotating between the coffee shops in Haifa, well, to be exact, those who have free parking nearby) to work on revisions to the draft of chapter four of the "Event Processing in Action" book.


From time to time I'll blog about giving some footnote from behind the scenes of the book-being-written. Today I'll blog about several issues: scope, language and exercises.

Scope: The idea is to focus about teaching the event processing concepts step-by-step using a use case which will accompany the book throughout, so the question is -- what is the scope of event processing. We define this scope by defining the "event processing network", and thus the question, that I started discussing in my precious posting is -- whether pre-processing and post-processing to the event processing network is part of the event processing network. While we have a chapter that is dedicated to event producers (and pre-processing) and another chapter that is dedicated to event consumers (and post-processing), the scope of what we discuss as part of the specification of the event processing part do not include what is done by the producers and consumers, whose projection on the EPN is the events they produce and consume. However, there is a case in which a consumer is also a producer, and this is important since there is a possible causality relationship between the event it consumes and consumer and event it produces. As an example: the use case is talking about "fast flower delivery" and one of its functions is choosing the driver that will get the delivery among the drivers that has issued a bid. Some of the stored prefer automatic assignment by the system, and some want to get the bids and do the assignment on their own. The automatic assignment is definitely an EPA (Event Processing Action), since this is a software that performs some operation on events, however the manual assignment can be either manual, or the store is using some external software to do it, however, this is not really part of the EPN, thus it is not modelled by the system. We are of course interested to trace the assignment to the bid which is the input to the store. This is also a good example to show that the same event type can include both raw events (the manual assignment are raw events from the EPN POV) and derived events (the automatic assignment).

Language: We decided neither to use any single language to explain the concepts, nor to invent a new language. However, we believe that just a theoretical discussion will not be enough. What we have decided to do is to take a "building block" approach, in which the different parts of the systems (event types, event processing agents etc..) are specified using "definition elements" which are platform independent concepts, or in other words, meta language. In each section we'll provide the full part of the application using this meta language, in order to connect it to the "ground", we'll also make samples of these definitions using variety of languages in various style. Thus, chapter 4 that I am writing now talks about defining the event schema. We define the schema using our "event type" building block, and will also show definitions in various schema languages (XML, positional relational-schema-like etc..), the same will go for all types of event processing agents. We intend to ask owners of existing languages (from those who will agree to get their languages analyzed by the EPTS event processing languages analysis -- taking on another hat) to provide language definition of our use case, and will check the possibility of posting them all.

Last but not least are the exercises, as we want the book to be a textbook for academic course on event processing, as one of its targets, we have decided to put exercises at the end of each chapter for the benefit of the students and instructors (we also plan to provide slides in the future), one of the questions we agreed with the publisher to ask the reviewers (there is a formal review for each 1/3 of the book) is whether this is the right way or it can make other readers uncomfortable. The options are now: leave as is (exercises at the end of each chapter, make all exercises as appendix or remove them completely from the book, and have them available on a website).

That's all for now -- more footnotes - later.

On Event Processing Research Challenges

This picture has been taken a year ago on the stairs to the old church in Schloss Dagstuhl, in that meeting we had people both from academia and from industry discussing the state of the art and future of event processing. I have returned to the conclusion of the Dagstuhl Seminar done by my colleague Peter Niblett from IBM recently, after my return to the IBM Research Division from spending several years in the product organization, I was asked about challenges to the research community, as seen by the product development community (or the industry in general), since we had a session about it in Dagstuhl, in which people from the industry expressed their opinions about the same questions, I just had to take it as a basis of a presentation in this area.

In Dagstuhl four major areas has been put as challenge to the Research community (adding my own interpretation and comments)

1. Event Processing Algebra and Meta-Language: Like the database area in the pre-relational era, the first (and probably second) generations of event processing are "engineering based", various vendors are building implementations based on the use cases they see and their innovative ideas, bringing to the table, not only a variety of languages, but also a variety of (typically - implicit) conceptual models behind this implementation. One of the indication for a maturity of an area is the existence of an agreed upon conceptual model. The relational model has done it for databases, the browser concept has done it for the internet, now we need the same for event processing. David Luckham's concept of EPN/EPA is a possible starting point, but more work is needed on this - the challenge is still there; after constructing the "relational model" for event processing we also need the "SQL" (not necessarily SQL extension - but this is a possibility) for it - in term of meta-language that describes the model and can be mapped to various implementation.

2. Software Engineering issues: This is a challenge from a different perspective. Event processing and Event Driven Architectures impose different thinking about computing. We are programmed to think in a certain way in all programming language, and the event based programming is somewhat different paradigm. Even the basic principle of decoupled asynchronous processing is something that is not easy to digest f0r people. We need software engineering tools, methodologies and best practices.

3. Implementation optimization: If we have done the analog of SQL, another analog come to mind - database tuning and query optimization. There are many optimization issues especially when the event processing applications are distributed and may have various QOS requirements - parallel processing, acceleration of hardware, inter-operability, support in illites in general - all are challenges. The goal function in this optimization is not unique, while in some systems it is maximal throughput, in other it may be scalability in number of rules/queries/patterns (there are applications in which the throughput is measured in millions, and others in which the number of rules, the number of producers, or the number of consumers is measured in millions...), the goal function can be a combination of multiple criteria.

4. Variety of "small issues" - examples: uncertain events, out-of-order events, retention and vacuuming of events etc....

It will be interested to look at recent research project to see how much progress has been done on these, and if the list should be modified after a year that has passed. The major research event of the EP community this year is DEBS 2008 , the program has not been published yet, and it will be interesting to compare the accepted papers with this list (I'll do it when surveying the conference itself in July). We also intend to do in the EPTS event processing symposium in September a session with academic people about it - stay tuned for further notice. I am also thinking about a follow-up Dagstuhl Seminar, may be in 2009 or 2010 - to re-discuss event processing in perspective. More - later.