非常快速和可扩展的主题路由 - 第 1 部分
最近，我们一直致力于改进 RabbitMQ 的路由性能，尤其关注通过使用一些著名的算法和其他技巧来加速主题交换。我们找到了比当前实现快很多倍的解决方案。
首先，简单介绍一下我们尝试解决的问题。以下是 AMQP 0-9-1 规范中的一段引述
主题交换类型的工作方式如下
- 消息队列使用路由模式 P 绑定到交换机。
- 发布者使用路由键 R 向交换机发送消息。
- 如果 R 与 P 匹配，则消息将传递到消息队列。
用于主题交换的路由键必须由零个或多个以点分隔的单词组成。每个单词可以包含字母 A-Z 和 a-z 以及数字 0-9。
*路由模式遵循与路由键相同的规则，但添加了 * 匹配单个单词，而 # 匹配零个或多个单词。因此，路由模式 *.stock.# 匹配路由键 usd.stock 和 eur.stock.db，但不匹配 stock.nasdaq.* 我们的目标是以快速且可扩展的方式将消息（路由键）与绑定（模式）进行匹配。
以下是我们尝试过的方法列表
- 在每个单词的基础上缓存消息的主题。这是 AMQP 规范建议的，并且已经有一些相关的研究。
- 在每个单词的基础上索引模式。这与第 1 点类似，不同之处在于我们预先准备模式，而不是为先前发送的主题键做准备。
- Trie 树实现。将模式中的单词排列在 Trie 树结构中，并沿着 Trie 树向下查找路由，以查看特定主题是否匹配。
- 确定性有限自动机 (DFA) 实现。这是一种通用的、用于字符串匹配的众所周知的方法。
这些方法各有优缺点。我们通常的目标是
- 在空间和时间上都具有良好的复杂度，以使其可扩展
- 易于实现
- 在常用情况下具有良好的性能
- 良好的最坏情况性能
- 在简单情况下快速（在绑定数量的可扩展性不是问题的情况下）
从一开始，仅仅通过在将键拆分为单词时更加小心（不重复为每个模式同时拆分模式和主题），我们就能够在所有情况下将当前实现的速度提高 3 倍。
我们发现方法 1 和方法 2 特别不适合需求。它们最慢，复杂度不高，因为它们涉及每个级别的集合相交，并且无法适应包含“#”的功能。因此，我们将注意力集中在方法 3 和方法 4 上。
Trie 树
这是一个 Trie 树结构的示例，如果我们添加模式 "a.b.c"、"a.*.b.c"、"a.#.c"、"b.b.c"
为了匹配一个模式（例如 "a.d.d.d.c"），我们从根节点开始，并逐字逐句地沿着树向下遍历主题字符串。我们可以通过完全匹配、“*”或“#”来深入。对于“#”的情况，我们可以使用主题尾部的所有版本来深入。对于我们的示例，我们将使用 “d.d.d.c”、“d.d.c”、“d.c”、“c” 和 "" 来遍历“#”。
Trie 树实现有许多优点：良好的空间复杂度；添加新绑定成本低；并且最容易实现；但是，缺点是它会为“*”和“#”回溯，以便找到所有可能的匹配项。
DFA
这种方法基于构造一个接受绑定模式的 NFA，并从中构造等效的 DFA 并使用它。由于我们还对哪个模式匹配感兴趣，而不仅仅是是否匹配，因此我们无法合并 NFA 中模式的尾部。
为了构造 DFA，我们像这样模拟了“#”的行为
例如，模式 "a.b.c"、"a.*.b.c"、"a.#.c"、"b.b.c" 将在 NFA 中表示为这样
节点 11、4、6 和 8 将附加信息，这些信息将指向各自的绑定。
为了将 NFA 转换为 DFA，我们尝试了各种方法，甚至为图表背后的结构生成了源代码，以使其尽可能快。我们最终找到的最佳解决方案是动态构建 DFA，就像在优秀的正则表达式编译器中构建 DFA 一样（例如，请参阅这篇文章）。
DFA 方法的优点是，一旦构建了 DFA，就不需要回溯。另一方面，它也有相当多的缺点：它比 Trie 树占用更多的内存；添加新绑定的成本很高，因为必须删除并重建整个 DFA；而且它更复杂，因此更难实现和维护。
在后续文章中，我们将更详细地介绍这两种结构、它们在基准测试中的表现、它们的空间和时间复杂度，以及我们尝试过的 DFA 优化的细节。
未完待续。