What algorithm does RabbitmQ use for pattern matching on topic exchanges

Question

RabbitMQ's topic exchanges (as explained here http://www.rabbitmq.com/tutorials/tutorial-five-python.html) allow routing using a key such as weather.US.newyorkor weather.US.* with * for wild card selections. What kind of algorithm and data structure does it use internally to do the pattern matching on incoming messages keys.

What data structure does it use to store the binding keys for queues? And how does it compare it with the incoming routing keys.

Answer 1

There are a couple of blog posts written by the RabbitMQ guys covering in detail how they do topic routing:

• http://www.rabbitmq.com/blog/2010/09/14/very-fast-and-scalable-topic-routing-part-1/
• http://www.rabbitmq.com/blog/2011/03/28/very-fast-and-scalable-topic-routing-part-2/

In summary though - it seems that (as of version 2.4 at least), they use a trie - a tree data structure, storing each segment of the binding key at the next node.

Although they're not explicit about the algorithm used to traverse the trie, in order to cope with * and # for wildcard selections, it's necessary to backtrack through the trie to capture all the possible matches. However, this overhead can be low, in particular in the simplest cases, and benchmarks on the second article above show that the trie is faster even than other data structures optimised to avoid backtracking.