非常快且可扩展的主题路由 - 第 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
如果我们要添加模式 "a.b.c"、"a.*.b.c"、"a.#.c" 和 "b.b.c"，则这是一个 Trie 结构的示例：
为了匹配模式（例如 "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 建立，就无需回溯。另一方面，它也有一些缺点：它比 Trie 占用更多的内存；添加新绑定存在显著的成本，因为整个 DFA 需要被丢弃并重建；并且它更加复杂，因此更难实现和维护。
在接下来的文章中，我们将详细介绍这两个结构，它们在基准测试中的表现，它们的空间和时间复杂度，以及我们尝试过的 DFA 优化的细节。
待续。