Event system filter mechanism refinement

[MiJaGourlay]

Event systems aim to mediate communcation between software components
while facilitating decoupling those components. Event systems avoid
message senders from needing to know message recipients. They
establish one-to-many relationships. Event systems tend to build upon
the design patterns of "observer" and "mediator". The book
"Distributed Event-Based 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.]