Systems" (Muehl et al.) provides a taxonomy of cooperation models which illustrates the relationships between message senders and receivers, based on who initiates the transaction (consumer or producer) and whether the initial message recipient (addressee) is direct or indirect. Event systems are categorized as systems where the producer initiates communication and the recipient is indirect (i.e. sender does not know or care about the recipient).Event systems work well when a single message can be used by multiple unrelated subsystems. Consider a simulation of a bunch of moving billiard balls which can collide, rebound from walls, and fall into pockets. An audio subsystem could subscribe to collision events to play a "click" sound when balls collide. Each ball can respond to collision events to apply an impulse to rebound from other balls and from walls. A gameplay system can monitor when balls fall into pockets to tally score and to remove balls from play.
Unfortunately, simple forms of event systems can distribute events to recipients who do not need every message of a given type. The problem of deciding what messages go to what recipients is called “filtering” and that’s the area where a simple event system needs refinement.
Reconsider the example problem. Each subsystem (physics, sound, gameplay) receives all collision events, but sometimes particular events are irrelevant to certain subsystems: A collision between a ball and a pocket should emit no sound. A collision between a ball and another ball should not cause any scoring change or remove balls from play. Also, all balls could receive all collision events between all ball pairs even if the ball is not involved in the pair. Such spurious, irrelevant events can be rejected by recipients after delivery but "post-delivery filtering" introduces avoidable overhead. If the number of billiard balls is large, the overhead can be larger than the legitimate processing time.
How can we augment an event system so that it has enough information to filter which recipients get which messages, in such a way that the event system remains generic and preserves desirable properties, e.g. that the sender does not know nor care about the receipients?
Several filter mechanisms have been implemented for event systems, including type-based, channels, subject-based and content-based.
The "observer" design patterns uses a subscription model tantamount to type-based filtering, where subscribers implement an interface which allows them to be notified of messages and they subscribe to the publisher via a subscription method. Each publisher object keeps a list of subscribers and notifies all subscribers when the appropriate event occurs. An event system built upon the "observer" and "mediator" design patterns therefore effectively uses type-based filtering. As revealed in the example above, type-based filtering still delivers all collision messages to all subsystems who care about particular subsets of collision messages, so we want to refine the system to use a better filtration mechanism.
Channels encompass sets of message types, and subscribers can subscribe to a channel, so they receive any message in the channel. Such a mechanism actually worsens the problem at hand in that we want to narrow the flow of communication, not widen it. Furthermore, the type-based system can already facilitate channels (although somewhat awkwardly) by subscribing a single object to multiple publishers. If it became useful, introducing the notion of channels would require only cosmetic changes to the event system; it would simply wrap the existing subscription interface with a sugar coating. At best, channels solve a different problem -- one not currently under consideration.
Subject-based filtering entails describing events and filters using keywords and filtration entails pattern matching. There are many problems with string-based approaches, including poor performance, ambiguity and rigidity. Read up on the subject if you want to know more, but for the immediate conversation I summarily dismiss this option.
Content-based filtering entails operating on the contents of the message itself. To be generic, the event messages have to be structured in a way that the event system can query, e.g. using name/value pairs. Furthermore, the filter itself has to be in a form the event system mediator can interpret, e.g. an expression language. This technique is quite powerful but also complicated and it's not clear that implementing a powerful, general mechanism like this provides any performance advantage over simply passing all recipients all messages of a given type, then letting the recipients decide whether each particular message is pertinent or not. (In the context where content-based filtering is employed -- distributed systems -- the message data and filtration expressions often reside on a different machine than the recipients, in which case the cost of distributing the messages is potentially much higher than for the present example, which runs within a single machine.)
Consider an extremely limited form of content-based filtering where each event message provides an integer (perhaps with arbitrary length) which we could call its "digest". The meaning of this value is unknown to the event mediator; only the publisher and subscribers assign meaning to this value. For example, it could be a unique identifier (e.g. each billiard ball could have an id), a bit field indicating various information (e.g. subtypes), a combination of these -- whatever. Meanwhile, each subscriber would provide a pair of integers: a mask and a value. When processing an event for delivery, the event mediator would apply the mask to the digest using bitwise-and, then compare the results to the value provided by the subscriber. Using this mechanism, the subscriber can state whether specific bits must be high or low, or whether some bits are irrelevant. Furthermore, the "identifier" and "subtype bit field" approaches can be merged together because, e.g., the upper N bits of the "digest" could correspond to "id" and the lower M bits could be the "subtype bit field". The important idea here is that the event mediator does not know or care what the bits mean -- only how to apply them as a filter. This system constitues an extremely simplified form of content-based filtering because it reduces the set of name/value pairs to bits (where names correspond to bit index ranges and values correspond to the bit values at those indices), and it reduces the filtration expression "language" to a single integer with a bitwise-and operator.
Sounds fast and simple -- elegant. Will it work? Is it sufficiently powerful to justify the addition?
[We'll discuss this at lunch on Friday, September 19, at Crispers in Winter Park Village.]
Update 2008sep19: Summary of lunch discussion:
Gabe, Dan, Aaron, Paul, Nathan and I attended. Everybody contributed to the discussion. Paul and Nathan reported their experiences with other event systems.
Paul described a channel-based system that he was not happy with, for reasons resembling those I pointed out in the blog -- insufficient filtering. The system he uses also has other issues, like massive switch-case filters within subscribers -- which misses one of the major points of using type-based filtering and one of the major benefits of event systems. He described an augmentation he implemented that took some inspiration from C# "delegates". His scheme uses C++ method pointers and uses the special and arcane .* and ->* method pointer invocation syntax. I have often thought about situations where that could be used but rarely (never?) seen it exploited, so this might be a good example of it. Paul also described a hypothetical system which involved layers of subscribers, each of which filter and selectively redistribute messages.
Nathan said his team evaluated Insomniac's Event/Delegate system but decided to write their own which uses type-based filtering, because their needs are simple. Their system suffers from the same problem described in the original post, that multiple subscriber objects receive messages of the proper type but not intended for that particular object. This situation apparently arises when the event system is used to postpone delivery -- i.e. where the publisher knows the subscriber. So to some extent one could claim this was out-of-domain usage for an event system, which is supposedly intended to decouple depencencies between systems, but in practice we all also use event systems to exploit the asynchronous nature, even with tight coupling between publisher and subscriber.
