极速可扩展的主题路由 - 第 2 部分

在我们的上一篇博文中，我们讨论了几种主题路由优化的方案，并简要介绍了其中两种更重要的方案。在本篇文章中，我们将讨论在实现 DFA 时尝试过的一些方法，以及对 trie 和 DFA 进行的一些性能基准测试。

实现 DFA

为了能够构建 DFA，我们首先需要从模式中构建 NFA。DFA 和 NFA 之间的主要区别在于，在 DFA 中，在任何时候，你都不需要选择（回溯）；你只有一条精确的路线可以沿着图向下走。例如，以下是如何将模式“a.b”和“*.b”转换为 DFA

我们可以看到，在 NFA 中，状态 0 有一个选择，如果主题以“a”开头。它可以经过 1 或 3。这会导致回溯。在 DFA 中，当主题以“a”开头时，两个分支合并在一起，将“任何”变成“其他”，为每种情况只留下一个清晰的选择。

在将 NFA 转换为 DFA 时，有几个选择

• **使用幂集构造算法**。这种方法通常用于从一开始就构造整个 DFA。
• **使用 NFA 算法**。这与回溯的复杂度相同，但它以集合操作的方式进行建模。
• **纯回溯**。基本上与上一篇文章中提到的 trie 方法相同。

转换的主要问题是 DFA 的大小和算法的复杂度。虽然不明显，但在上面的例子中，当使用“#”在模式中时，DFA 的大小会比 NFA 大得多。在某些情况下，“#”会导致一个节点链接到图中的所有其他节点。因此，试图从一开始就构建整个 DFA，然后在添加新绑定时完全重建它将毫无意义。

为了克服这个问题，我们想出了一种在创建新绑定时用新模式修补 DFA 的方法。如何？构建新模式的 NFA，并像这样将其链接到现有的 DFA

其中 0 是现有 DFA 的起始节点，X 是要添加的新模式的起始节点。

结果将是一个新的 NFA。然后，我们将使用幂集构造方法重建 DFA，但在遇到包含单元素集合的节点时，该元素属于之前的 DFA，我们可以停止并将其链接到之前的 DFA 中。

对于不包含“#”的模式，在大多数情况下，你几乎不会触碰现有的 DFA 并完全保留它，同时附加新的模式。在这些情况下，添加新绑定的成本非常低。

问题是......“#”。如果新的模式在开头包含一个“#”，最终会导致再次遍历整个 DFA 并更新所有节点以重建它。出于这个原因，并且因为 DFA 本身就具有很大的大小复杂度，我们最终认为构建整个 DFA 然后修补它不是一个好主意。

如今，优秀的正则表达式编译器不会完全存储 DFA，因为 DFA 可能非常庞大。相反，它们会根据需要，使用 NFA 算法即时构建它，并将其缓存起来。你可以将其视为一种惰性求值的形式 - 只有在需要时才会生成新节点。当缓存变得太大时，它们会完全丢弃它并重新开始。我们最终在我们的问题中采用了这种方法。

测试 trie 和 DFA 以及改进 DFA 的尝试

我们编写了一个基准测试，用于比较两者之间的性能。我们试图让测试尽可能地模拟主题交换的常用方式。在下文中，“快 x 倍”指的是基准测试时间，通常与朴素实现相比，朴素实现没有进行上一篇文章中提到的不必要的拆分。基准测试包括将 100 万个主题与 2000 个模式匹配。我们在一台 2.3 GHz 的机器上运行它。模式包含 0.1 的“*”和 0.01 的“#”。

trie 在我们的基准测试中用了11.7 秒完成，这使其比朴素实现快了15 倍。

然后我们对 NFA 算法进行了基准测试，但没有缓存 DFA，使用 Erlang 的 digraph 模块来表示图。它的复杂度与 trie 相当，所以我们预计时间会相似。结果呢？非常慢！大约需要数百秒。

我们需要编写自己的图实现，因为 digraph 的性能真的很差。因此，我们编写了一个基于 Erlang 字典的专门的有限自动机图。我们只用了37 秒就完成了 NFA（没有缓存 DFA）。比 trie 慢了四倍。仍然不够快。但可能是由于遍历图而不是树以及执行一些额外的集合操作所带来的成本。

然后我们实现了 DFA 的缓存。结果？比 trie 更慢！在我们的基准测试中，我们得到了26.7 秒。我们尝试了更多的消息（也许 DFA 没有完全构建）。仍然...更慢。

以下是在改变消息数量时测试的图表（2000 个模式，数百万个消息与时间微秒 - 越低越好）

这相当出乎意料。我们应该看到 DFA 在某个时间点呈对数方式增长。出了什么问题？也许我们需要一个更快的图。众所周知，Erlang 中的字典实现并不快。我们的图实现是基于 Erlang 的字典。我们需要一种优化它的方法。

我们想出了一个想法，即为字典即时生成源代码。例如，如果你有一个带有条目[{k1, v1}, {k2, v2}, {k3, v3}]的字典，我们将生成一个函数

mydict(k1) -> {ok, v1};

mydict(k2) -> {ok, v2};

mydict(k3) -> {ok, v3};

mydict(_) -> error.

因此它将像字典一样运行:find/2 函数，除了它只接受一个参数。我们使用了 Yariv Sadan 的 smerl 模块来完成这项工作。

我们首先测试了新的图，只使用 NFA，不缓存 DFA。在我们的基准测试中，我们得到了21.9 秒。太棒了！几乎是之前 37 秒结果的两倍快。

现在让我们尝试缓存 DFA，并每 5 秒将字典编译为函数。完全失败！生成的函数有数十万个子句，因为图中的边数非常多。编译这样的东西需要花费很长时间！这是没有用的。

只对 NFA 使用编译字典，而不对缓存的 DFA 使用，我们在基准测试中得到了15.2 秒 - 我们最快的 DFA 尝试。

进一步测试

让我们仔细看看 trie 和 DFA 的复杂度。也许我们可以找到 DFA 出问题的线索。以下是在改变模式数量时测试的图表（300 万个消息，模式数量与时间微秒）

令人惊讶的是！DFA 具有相当的指数/二次复杂度，而 trie 保持相当的线性或对数复杂度。

解释是什么呢？DFA 使用了大量的内存。DFA 慢得多的原因可能是处理器需要非常频繁地从内存中获取 DFA 的位，而不是能够将 DFA 保留在处理器的缓存中。trie 使用的内存明显少得多，可能更适合缓存。

让我们看看在改变消息数量时的内存使用情况（2000 个模式，数百万个消息与使用的单词）

显然，trie 在消息流时大小不会改变。我们可以看到，在这种情况下，DFA 使用的内存是 trie 的40 倍。事实上，DFA 不适合缓存的理论得到了证实。trie 使用 1-2MB，而 DFA 使用了近 50MB。

现在让我们改变模式的数量，并保持消息数量不变（300 万个消息，模式数量与使用的单词）

我们可以看到，DFA 具有指数空间复杂度。

因此...

缓存消息主题和按级别对模式进行索引明显不如 trie 和 DFA 方法。

DFA 使用的内存多得多，优化它的方法受到许多障碍的限制。即使使用专门的图实现，由于内存使用量很大，DFA 也无法达到线性时间复杂度，而是趋向于指数空间和时间复杂度。它明显比 trie 方法更糟糕，即使 trie 会回溯，如果每个模式中单词的数量在常用情况下更多，trie 也会具有指数复杂度。

trie 方法更简单，因此比 DFA 更易于实现和维护；它使用的内存少得多，因此能够放入处理器的缓存中；并且在空间和时间上都表现出线性对数复杂度，使其成为最适合的方法。

我们在新的 RabbitMQ 2.4.0 版本中实现了 trie 方法。以下是在我们测试 Rabbit 本身时使用新实现的结果（绑定数量与时间微秒）

最后，以下是 2.3.1 版本和 2.4.0 版本之间的性能比较（绑定数量与时间微秒） - 此图表中的性能改进从快 25 倍到快 145 倍不等