Pattern matching events with arbitrary structure

Question

My team implemented an alert broker system. The way it works is this:

1. Event sources generate events, with mostly arbitrary structure, and the broker listens to them.
2. Users go to the broker and use an expression language to create alerts for the events. The expressions can reference arbitrary attributes of the events.
3. The broker dispatches alerts accordingly. This involves searching for the event subscriptions that users create in step 2 above.

I'd like some help in understanding my options for the subscription search as I need to scale it out.

Right now we're just doing linear search because the number of events and subscriptions is low. That won't last long at all.

The plan for the next step is to use indexing on the small number of known fields in the event (e.g. sourceId, type, name, etc.). Once we prune the search space that way we could do linear search. That should carry us for a while, and maybe indefinitely.

But if we hit a wall there, what are the standard approaches? I know RETE is good at this sort of thing, but it seems that RETE implementations appear in the context of rules engines, and those involve conflict resolution to a single rule. In our case there would be multiple subscriptions (rules) we want to match, so just doing a straight rules engine doesn't seem to work. If there are standalone RETE implementations, I haven't seen them.

I guess finding or implementing standalone RETE is one option.

Other options?

(Also--to be clear, this isn't a case of premature optimization. I don't plan to implement anything optimized unless it looks like I actually need it. But I'd like to know that there's some plausible game plan should that occur.)

Answer 1

To circle back on this, we ended up using Elasticsearch Percolator. See https://stackoverflow.com/questions/21536599/what-does-percolator-mean-do-in-elasticsearch for more information.

There are also some papers that describe algorithms for solving this, be we haven't tried them. Example:

• https://theory.stanford.edu/~sergei/papers/vldb09-indexing.pdf
• http://msrg.org/publications/pdf_files/2011/moSIGMOD11-BE-Tree:_An_Index_Structure_to_Eff.pdf (this is more for ranged numerical attributes rather than categorical labels, but same general problem)