在Rust中构建速度更快的解释器

在Cloudflare，我们一直在努力提高我们的优势表现-这正是我今年夏天实习所需要的。我很高兴能与大家分享我们在过去几个月里对我们广受欢迎的防火墙规则产品所做的一些改进。

防火墙规则允许客户过滤到达其站点的流量。它是使用我们的引擎Wirefilter构建的，它接受客户编写的强大的布尔表达式，并将传入的请求与它们进行匹配。然后，客户可以选择如何响应符合这些规则的流量。我们将讨论我们最近对Wirefilter所做的一些深入优化，所以如果您还没有熟悉它的工作原理，那么您可能希望熟悉一下它的工作原理。

作为防火墙团队的新成员，我很快了解到性能很重要-即使在我们的安全产品中也是如此。我们寻找机会，让我们的客户在安全的地方更快地使用互联网，最大限度地提高安全性和性能。

我们的引擎已经大量使用，为所有防火墙规则提供动力。但我们有更大的计划。越来越多的产品，如我们的Web应用防火墙(WAF)，将运行在我们基于Wirefilter的引擎后面，不久之后，它将占据我们总CPU使用量的相当大一部分。

测量性能是出了名的棘手任务，正如您可能想象的那样，在高度分布式的环境(也就是Cloudflare的EDGE)中尝试测量性能不会有什么帮助。过去，我们对纸面上看起来不错的优化感到惊讶，但是，当在生产中测试时，似乎并没有起到多大作用。

我们的解决方案？性能测量即服务-针对我们的防火墙引擎的孤立且可重复的基准测试，以及工程师轻松请求运行和查看结果的框架。值得注意的是，我们从神奇的铁锈编译器基准测试中获得了很多灵感来构建它。

我们的下一个挑战是找到一些有意义的性能指标。一些实验很快发现，时间太不稳定，无法进行有意义的比较，因此我们求助于硬件计数器[2]。不难找到工具来测量这些(Perf和VTune就是两个这样的例子)，尽管它们(主要)不允许控制录制程序的哪些部分。在我们的示例中，我们希望分别记录过滤器处理的不同阶段-解析、编译、分析和执行的度量。

我们再一次从Rust编译器及其自评测选项中获得灵感，使用perf_event_open API从我们的二进制文件内部记录计数器。然后，我们输出类似以下内容的内容，我们的框架可以很容易地接收和存储这些内容，以便以后进行可视化。

虽然我们主要关注与CPU使用率相关的指标，但我们还结合使用getruse和clear_refs来查找最大驻留集大小(RSS)。这对于了解除CPU之外的特定算法对内存的影响非常有用。

但挑战还没有结束。出于安全性和便利性的考虑，CloudFlare的标准CI代理使用虚拟化和沙箱，但这使得访问硬件计数器几乎是不可能的。在专用机器上运行我们的基准测试使我们能够访问这些计数器，并确保结果更具重复性。

我们的基准从一开始就是为了在我们的发展过程中占据重要地位而设计的。例如，我们现在在发布每个新版本之前执行完整的基准测试运行，以检测性能倒退。

但随着我们的基准就位，很快就变得很明显，我们遇到了一个问题。我们的基准测试根本不够快-至少如果我们想在不到几个小时内完成它们的话！问题是我们有非常大量的过滤器。由于我们的引擎通常不会同时对这么多过滤器执行请求，因此它的成本非常高。我们想出了几个小窍门来减少这个，…。

重复数据删除。事实证明，只有大约三分之一的过滤器在结构上是唯一的(这一点很容易检查，因为Wirefilter可以很有帮助地序列化到JSON)。通过忽略基准测试中的重复过滤器，我们设法缩短了大量时间。

取样。尽管如此，我们有太多的过滤器和随机抽样提供了一个简单的解决方案。一个更微妙的挑战是确保随机样本总是相同的，以保持重复性。

分区。我们担心重复数据删除和采样会导致我们错过对优化有用的重要案例。通过首先根据Wirefilter语言功能对过滤器进行分区，我们可以确保我们得到了一系列良好的过滤器。它还有助于我们更详细地了解性能更改的具体影响在哪里。

其中大多数都是权衡，但非常必要，允许我们运行连续的基准测试，而不会使开发速度停滞不前。在撰写本文时，使用这些想法，我们已经设法将基准运行时间缩短到20分钟左右。

有了基准测试框架，我们就可以开始测试优化了。但是如何优化像Wirefilter这样的解释器呢？即时(JIT)编译、选择性内联和复制是口译员口中流传的一些似乎很有吸引力的想法。毕竟，我们之前曾在Wirefilter中写过动态分派的成本。所有这些技术都旨在减少这种影响。

然而，通过分析器运行一些真正的过滤器则是另一回事。大部分执行时间(约65%)不用于解析动态分派调用，而是用于执行比较和搜索等操作。目前生产中的筛选器往往功能很少，但是再加上几个这样的筛选器，在动态调度上花费的时间就更少了。我们怀疑，即使剩余的35%中的相当一部分实际上也花在了读取请求字段的内存上。

到目前为止，您不应该对CONTAINS操作符是最先进行优化的操作符感到惊讶。如果您曾经编写过防火墙规则，那么您可能已经熟悉了它的作用-它检查您要匹配的字段中是否存在子字符串。例如，当主机为“example.com”或“www.example.net”时，以下表达式将匹配，但当主机为“cloudflare.com”时，则不匹配。在字符串搜索算法中，这通常被称为在“大海捞针”(“example.com”)中查找“针”(“示例”)。

这是怎么在引擎盖下工作的？通常，我们可能使用了Rust的`String：：Contains`函数，但是Wirefilter也允许不一定符合UTF-8的原始字节表达式。

因此，我们使用了memmcrate，它在原始字节上执行双向子字符串搜索算法。

听起来不错，对吧？是的，而且运行得很好，尽管我们注意到使用正则表达式重写“包含”过滤器通常会让它们变得更快，这一点很奇怪。

正则表达式很棒，但是因为它们比“包含”运算符强大得多，所以在这种简单的情况下，它们不应该比专门的算法快。

肯定有什么不对劲。结果是，Rust的regex库配备了一整套专门的匹配器，用于它认为是这样的简单表达式。显而易见的问题是，我们是否因此可以简单地使用regex库。有趣的是，您可能没有意识到流行的Ripgrep工具在搜索固定字符串模式时正是这样做的。

但是，我们的用例略有不同。因为我们正在构建一个解释器(并且我们在任何情况下都使用动态分派)，所以当执行过滤器时，我们更愿意分派给“包含”表达式的特殊用例，而不是匹配正则表达式箱内深处的某个枚举。更重要的是，在利用SIMD指令集执行子字符串搜索时，有一些非常酷的事情正在做。所以我们把我们的引擎连接到Wojciech Muła之前的一些工作上，结果非常棒。

我鼓励您阅读更多关于我们使用的“算法1”的内容，但它的工作原理是这样的(我稍微更改了一下顺序以使其更清晰)。如果您不熟悉SIMD指令，那么阅读SIMD指令是值得的-它们是使该算法变得快速的根本原因。

我们用要搜索的指针的第一个字节填充一个SIMD寄存器，简单地重复一遍又一遍。

我们将尽可能多的干草堆装载到另一个SIMD寄存器中，并与前一个寄存器执行逐位相等操作。

现在，结果寄存器中任何为0的位置都不能作为匹配的开始，因为它不是以针的相同字节开始的。

现在，我们对针的最后一个字节重复此过程，以偏移大海捞针，以排除任何不以与针相同的字节结束的位置。

将这两个结果加在一起，我们(希望)现在已经大大减少了我们潜在的对手。

可以使用memcmp操作手动检查剩余的每个潜在匹配。如果我们找到匹配的，我们就完了。

如果没有，我们继续大海捞针的下一部分，重复进行，直到我们检查完整个过程。

你可能想知道，如果我们的干草堆不能整齐地放入登记簿，会发生什么。在最初的算法中，什么都没有。它只是在干草堆结束后继续向遗忘中读取，直到最后一个寄存器已满，并使用位掩码忽略来自该附加内存区域的潜在误报。

正如我们提到的，当涉及到优化时，安全性是我们的首要任务，因此我们永远不能部署具有这种行为的东西。我们最终将Muła的库移植到了Rust(我们还开源了箱子！)。并执行了ARM博客中找到的重叠寄存器修改。

最好的例子说明了这一点-注意我们如何用4字节寄存器填充虚构的SIMD指令集上的寄存器之间的差异。

在我们的例子中，在两个不同的寄存器中重复一些字节永远不会改变最终结果，因此这种修改是允许的。然而，在现实中，我们发现最好使用位掩码来排除最终寄存器的重复部分，并最小化memcmp调用的数量。

如果干草堆太小，甚至不能填满一个登记簿怎么办？在这种情况下，我们不能使用重叠的技巧，因为没有什么可以重叠的。我们的解决方案很简单：虽然我们的主要目标是AVX2，它可以在一个通道中存储32字节，但我们可以很容易地向下移动到另一个寄存器较小的指令集，这个干草堆可以容纳这些寄存器。实际上，我们目前并不比SSE2更小。除此之外，我们改为使用Rabin-Karp搜索算法的实现，该算法似乎执行得很好。

选择针的第一个和最后一个字节来排除潜在的匹配是一个很好的想法。这意味着当执行memcmp时，我们可以忽略它们，因为我们知道它们已经匹配。不幸的是，正如Muła指出的那样，这也使得算法在某些情况下容易受到最坏情况的攻击。

如果我们试图在非常长的‘/’序列中搜索它，我们将在每个位置找到一个潜在的匹配项，并对memcmp进行大量调用-本质上是执行缓慢的强制子字符串搜索。

显然，我们需要从指针中选择不同的字节。但是我们应该选择哪一个呢？对于每一个选择，对手总会发现一个略有不同，但同样麻烦的最坏情况。相反，我们使用随机性来摆脱我们的潜在对手，像以前一样选择针的第一个字节，但然后选择另一个随机字节来使用。

我们的新版本不出所料地比Muła的慢，但它仍然显示出比Mememm和regex板条箱都有很大的改进。性能，但不牺牲安全性。

这只是我们一直在做的表演工作的一小部分，我们还会有更多的工作要做。然而，如果没有我的经理理查德和我的导师埃利的支持，这一切都不可能实现，他们贡献了很多这些想法。在过去的几个月里，我学到了很多，但最重要的是，对于实习生来说，Cloudflare是一个令人惊叹的地方！

[1]由于我们的基准测试不是在生产环境中运行，因此本文中的结果并不代表我们边缘的流量。

[2]我们发现指令计数是一种特别稳定的度量，而CPU周期是一种特别不稳定的度量。

[3]请注意，从技术上讲，SWAR不是指令集，而是使用常规寄存器，如矢量寄存器。

防火墙性能锈蚀SIMD晶片