深入探究BPF LPM Trie性能与优化

一切始于生产环境中出现的神秘软锁定消息。这一行神秘的代码将我们带入了我们使用的最基本数据结构之一——BPF LPM Trie的性能研究之旅。

BPF Trie映射（BPF_MAP_TYPE_LPM_TRIE）在网络数据包路由中广泛用于IP和IP+端口匹配，确保请求在返回结果前通过正确的服务。这种数据结构的性能对我们的客户服务至关重要，但当前实现的性能表现仍有很大改进空间。

Trie数据结构回顾

Trie（字典树）是一种树形数据结构，允许您存储和搜索给定键的数据，每个节点存储一定数量的键位。搜索通过遍历路径执行，这实际上从遍历路径重建键，意味着节点不需要存储其完整键。

与需要每个节点存储完整键的传统二叉搜索树（BST）不同，Trie在数据具有冗余时（例如键中常见前缀）非常内存高效，因为共享数据只需要一组节点。这就是为什么Trie通常用于高效存储字符串，例如单词字典。

Trie的设计使其非常适合执行最长前缀匹配和使用CIDR处理IP路由。CIDR是为了更有效地利用IP地址空间而引入的，但带来了额外的复杂性，因为IP地址的网络部分现在可以出现在任何位置。

在AMD EPYC 9684X 96核机器上运行BPF自测基准测试的结果显示：

释放具有10K条目的BPF LPM Trie的时间明显很长。我们最近遇到了一个问题，这个过程耗时过长，导致生产环境中出现软锁定消息。

内核中的LPM Trie实现（kernel/bpf/lpm_trie.c）具有我们在介绍中讨论的一些优化。它能够在叶节点执行多比特比较，但由于每个内部节点只有两个子指针，如果树密集填充了大量仅相差一位的数据，这些多比特比较会退化为单比特比较。

这种双孩子设计影响了Trie的高度。在最坏情况下，完全满的Trie基本上变成了高度为log2(nr_entries)的二叉搜索树，而Trie的高度会影响搜索键所需的比较次数。

BPF LPM Trie还不实现级别压缩。这同样源于Trie中的节点只能有2个子节点的事实。IP路由表往往有许多共同的前缀，通常在上层看到密集打包的Trie，这使得级别压缩对包含IP路由的Trie非常有效。

随着条目数量从1个增加到100K个，LPM Trie的查找吞吐量（以百万操作/秒计）逐渐下降。当达到100万个条目时，吞吐量约为150万操作/秒，并随着条目数量增加而继续下降。

最初，这是由于L1 dcache未命中率。Trie中需要遍历的所有节点都是潜在的缓存未命中机会。在大约80K条目时，dTLB未命中率成为瓶颈。

因为BPF LPM Trie尝试从内核内存的自由列表中动态分配单个节点，这些节点可以位于任意地址。这意味着遍历Trie路径几乎肯定会引起缓存未命中，并可能引起dTLB未命中。随着条目数量和Trie高度的增加，这种情况会变得更糟。

通过了解BPF LPM Trie的当前限制，我们现在可以为互联网的未来构建更高性能、更高效的解决方案。

我们已经将这些基准测试贡献给上游Linux内核——但这只是开始。我们计划改进BPM LPM Trie的性能，特别是对我们工作负载大量使用的查找函数。本文涵盖了net/ipv4/fib_trie.c代码已经使用的许多优化，因此自然的第一个步骤是重构该代码，以便可以使用通用的级别压缩Trie实现。