[rabbitmq-discuss] topix

[David R. MacIver]

On Mon, Feb 22, 2010 at 12:43:14PM +0100, Martin Sustrik wrote:
> Hi David,
> 
> > One thing that would help us to make these decisions as to the
> best approach would
> > be some feedback on how people are using topic exchanges in the
> real world: e.g.
> > if it turns out that basically all bindings are short then the
> space explosion isn't really an issue. If bindings are created
> rarely, or typically in big blocks,
> > then we could optimise for that. There's not going to be a
> universally "best" solution, so while the objective is of course to
> make everything as fast as possible
> > it always helps to know which operations we need to worry about the most.
> > Hope that helps clarify some of our thoughts so far.
> 
> Very often the only subsciption type needed is subsciption for a
> specific sub-tree within the topic hierarchy, in other words
> subscription with literal prefix and # at the end, e.g. "x.y.z.#".

Ah, that makes sense. Thanks. 

> If that's the case, all three fundamental operations can be
> implemented in O(1) time where n is number of topics and/or bindings

Well, O(log(branching rate for the tree)) (you need to do key lookups at
each level), but near enough. 

> and O(n) time where n is length of the longest subscription.
> Such an algorithm can be turned on by a specific hint passed to
> Exchange.Create 'arguments' parameter, or, more transparently, it
> can be used as long as subscriptions adhere to "x.y.z.#" pattern and
> once there's a non-compliant subscription, matching algorithm can
> switch dynamically to a more generic one.

I'm not sure this actually needs quite such specific logic. It should be possible
to add rules which means this behaviour falls out naturally rather than having a 
sharp transition between the two behaviours e.g. in the NFA approach suggested 
the only special handling needed would be to make sure that binding the pattern 
# was sensibly implemented as a "go straight to queue, do not pass go, do not 
collect O(key length) operations" node rather than doing a full scan of the rest
 of the key.

'though I guess that sparks another question: How long are the keys people are
actually using with this?