[rabbitmq-discuss] topix

[David R. MacIver]

For those just joining us, the discussion is on the implementation of topic 
exchanges.

On Sat, Feb 20, 2010 at 02:52:41AM -0800, Yurii Rashkovskii wrote:
> Matthias,
> 
> On 2010-02-20, at 2:49 AM, Matthias Radestock wrote:
> 
> > Yurii,
> > 
> > Yurii Rashkovskii wrote:
> >> Out of curiosity, how this finite state machine would work?
> > 
> > Let me hand you over to my colleagues Matthew Sackman and David MacIver, who have been discussing this recently.
> 
> Thanks!

Hi, 

There's still a bunch of discussion to be resolved about this (and will no doubt 
be more when we actually find time to implement it).

A couple points to consideri:

We essentially have three operations we need to optimise:

1. adding a binding
2. removing a binding
3. looking up a key against a set of bindings

Currently the first two are fast (probably O(log(n)). Depends what mnesia is doing)
but the third is O(length of key * number of bindings). This is sub-optimal.

The naive solution would be to recompile the bindings to a finite automaton every
time they change, but this is an O(number of bindings) operation, so this would
result in creating O(n) bindings being O(n^2), which isn't great. So the objective
is to build the tree incrementally in a way makes each operation relatively cheap.

The version I proposed (which is almost certainly not how it will look in the end)
is that we'd implement it as a mostly-optimized NFA (only mostly because it makes
 the cost of all binding modification operations way cheaper to do it this way 
while not hurting binding lookup that much). This actually ends up being relatively
close to the tree of topics you proposed in your earlier email. 

Essentially the way it would look is that you'd have the obvious NFA corresponding
to any given binding and then merge prefixes for these.

So e.g. the binding foo.bar.baz to queue 1 would simply look like:

1 -(foo)-> 2 -(bar)-> 3 -(baz)-> [queue-1]

while foo.#.baz to queue-2 would give

1 -(foo)-> 2 -(.)-> 2
            -(epsilon)-> 3 -(baz)-> [queue-2]

(where an epsilon transition is as usual one that doesn't consume any tokens)

And adding both would result in:

1 -(foo)-> 2 -(epsilon)-> 3 -(bar)-> 4 -(baz)-> [queue-1]
             -(epsilon)-> 5 -(.)-> 5
                            -(epsilon)-> 6 -(baz)-> [queue-2]

It's worth noting that although in principle if both bindings were to queue-1 we
would be able to merge nodes 6 and 7, we probably wouldn't do so: Because we want
these machines to be incrementally editable there will definitely be some redundant
nodes.

One thing we've discussed is the choice between an NFA and a DFA. On the one hand,
the DFA will be a lot faster on lookup for the cases it's well suited to (as well 
as constant factors, the DFA will be O(length of key) while the NFA will be more
like O(length of key * number of _matching_ bindings)), on the other hand it will 
be slower for binding deletion (because you have to scan multiplea branches of 
the tree to delete a single binding). 

Additionally there are pathological cases where a DFA ends up with an exponentially 
larger number of nodes than the equivalent DFA. For example:

#.foo{".*" k times} 

takes O(2^k) nodes to represent with a DFA but O(k) nodes with an NFA.

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.

Regards,
David