data-structures - RabbitmQ 在主题交换中使用什么算法进行模式匹配

Question

RabbitMQ 的主题交换（如此处解释的http://www.rabbitmq.com/tutorials/tutorial-five-python.html）允许使用诸如weather.US.newyork或weather.US.*with的键*进行通配符选择。它在内部使用什么样的算法和数据结构来对传入消息键进行模式匹配。

它使用什么数据结构来存储队列的绑定键？以及它如何与传入的路由键进行比较。

Answer 1

RabbitMQ 人员写了几篇博客文章，详细介绍了他们如何进行主题路由：

• 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/

总而言之 - 似乎（至少从 2.4 版开始），他们使用 trie - 一种树数据结构，将绑定键的每个段存储在下一个节点。

尽管它们没有明确说明用于遍历 trie 的算法，但为了处理通配符选择的 * 和 # ，有必要通过 trie 回溯以捕获所有可能的匹配项。但是，这种开销可能很低，尤其是在最简单的情况下，上面第二篇文章的基准测试表明，trie 甚至比其他优化以避免回溯的数据结构更快。