跳到主要内容

超快速且可扩展的主题路由 - 第 2 部分

·9 分钟阅读
Vlad Alexandru Ionescu

在我们之前的博文中，我们讨论了几种主题路由优化的方法，并简要描述了其中最重要的两种。在这篇文章中，我们将讨论我们在实现 DFA 时尝试的一些事情，以及我们在 trie 和 DFA 上进行的一些性能基准测试。

实现 DFA​

为了能够构建 DFA，我们首先需要从模式构建 NFA。DFA 和 NFA 之间的主要区别在于，在 DFA 中，在任何时候，您都不必选择（回溯）；您只能获得一条精确的路径，沿着该路径向下遍历图。例如，以下是我们如何将模式 "a.b" 和 "*.b" 转换为 DFA 的方法

我们可以看到，在 NFA 中，如果主题以 "a" 开头，则状态 0 有一个选择。它可以穿过 1 或穿过 3。这会导致回溯。在 DFA 中，当主题以 "a" 开头时，两个分支合并在一起，并将 "any" 变为 "other"，为每种情况只留下一个明确的选择。

将 NFA 转换为 DFA 有几种选择

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

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

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

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

结果将是一个新的 NFA。然后，我们将使用幂集构造方法重建 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 字典的专用有限自动机图。我们仅针对 NFA（没有缓存 DFA）获得了 37 秒。比 trie 慢四倍。仍然不够快。但这可能是由于遍历图而不是树以及进行一些额外的集合运算的成本造成的。

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

这是一个测试图表，当改变消息数量时（2000 个模式，数百万条消息 vs 时间微秒 - 越低越好）

这非常出乎意料。我们应该在某个时候看到 DFA 以对数方式增长。哪里出错了？也许我们需要更快的图形。众所周知，Erlang 中的 dict 实现不是很快速。我们的图形实现基于 Erlang 的 dict。我们需要一种优化它的方法。

我们想出了动态生成字典源代码的想法。例如，如果您有一个字典，其中包含条目 [{k1, v1}, {k2, v2}, {k3, v3}]，我们将生成一个函数

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

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

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

mydict(_) -> error.

因此，它的行为类似于 dict:find/2 函数，除了它只接受一个参数。我们使用了 Yariv Sadan 的 smerl 模块来完成这项工作。

我们首先仅使用 NFA 测试了新图形，而没有缓存 DFA。在我们的基准测试中，我们获得了 21.9 秒。太棒了！几乎比之前的 37 秒结果快两倍。

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

仅将编译后的 dict 用于 NFA 而不用于缓存的 DFA，我们在基准测试中获得了 15.2 秒 - 我们最快的 DFA 尝试。

进一步测试​

让我们仔细看看 trie 和 DFA 的复杂度。也许我们能找到 DFA 哪里出错的线索。这是一个测试图表，如果改变模式数量（300 万条消息，模式数量 vs 时间，单位为微秒）

惊喜！DFA 具有相当指数/二次的复杂度，而 trie 保持相当线性或更确切地说对数。

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

让我们看看内存使用情况，当改变消息数量时（2000 个模式，数百万条消息 vs 使用的字数）

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

现在让我们改变模式数量并保持消息数量恒定（300 万条消息，模式数量 vs 使用的字数）

我们可以在这里看到 DFA 具有指数级的空间复杂度。

所以...​

缓存消息主题并在每个级别上索引模式显然不如 trie 和 DFA 方法。

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

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

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

最后，这是版本 2.3.1 和版本 2.4.0 之间的性能比较（绑定数量 vs 时间，单位为微秒） - 此图中的性能提升从快 25 倍到快 145 倍不等

© . All rights reserved.