通过分片扩展 Akvorado BMP 路由信息库

# 通过分片扩展 Akvorado BMP RIB 来源：https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding 为了将路由信息（如 AS 路径或 BGP 团体属性）与流量关联，[Akvorado](https://github.com/akvorado/akvorado) 可以通过 [BGP 监控协议（BMP）](https://www.rfc-editor.org/rfc/rfc7854) 导入路由。由于互联网路由表包含超过 100 万条路由（[参考](https://bgp.potaroo.net/)），Akvorado 需要**扩展到数千万条路由**。¹（注释：优化方向）这是一个长期存在的挑战，²（注释：过往问题）但我期望这个问题现在通过使用 **RIB 分片** 得到解决，这是一种将路由数据库拆分为多个部分以实现并发更新的方法。 - [之前的实现](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#previous-implementation) - [在地图中存储路由](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#storing-routes-in-a-map) - [驻留路由](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#interning-routes) - [为什么不能扩展？](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#why-does-it-not-scale) - [RIB 分片](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#rib-sharding) - [第一步：基本分片](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#first-step-basic-sharding) - [第二步：无锁读取](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#second-step-lock-free-reads) ## 之前的实现 Akvorado 构建其 RIB 时连接了两个元素： 1. 一个**前缀树**，以及 2. 每个前缀附带的**路由列表**。 分片前 Akvorado BMP RIB 实现的内存布局示意图，每个结构体共用一个锁。 无分片的 Akvorado BMP RIB 实现。单个读写锁。在上图中，RIB 存储了五个 IPv4 前缀和两个 IPv6 前缀。其中 `2001:db8:1::/48` 包含三条路由： - 来自对等体 3，下一跳 `2001:db8::3:1`，AS 65402，AS 路径 `65402`，团体属性 `65402:31`， - 来自对等体 4，下一跳 `2001:db8::4:1`，相同 ASN、AS 路径和团体属性， - 来自对等体 5，下一跳 `2001:db8::5:1`，AS 65402，AS 路径 `65401 65402`，团体属性 `65402:31`。 `rib` 结构体在 Go 中定义如下： ```go type rib struct { tree *bart.Table[prefixIndex] routes map[routeKey]route nlris *intern.Pool[nlri] nextHops *intern.Pool[nextHop] rtas *intern.Pool[routeAttributes] nextPrefixID prefixIndex freePrefixIDs []prefixIndex } ``` 前缀树使用了 [bart](https://github.com/gaissmai/bart/) 包，该包是 Donald Knuth 的 [ART 算法](https://www.hariguchi.org/art/art.pdf) 的改编版。基准测试 [iprbench](https://github.com/gaissmai/iprbench) 显示其在查找、插入和内存使用方面优于其他包。³（注释：性能）而且作者非常乐于助人。 ## 在地图中存储路由 每个前缀的路由列表并非直接存储在前缀树中：这样会分配每个前缀的数组，给垃圾回收器带来过大压力。 相反，RIB 为每个前缀分配一个唯一的 32 位前缀标识符：要么从 `freePrefixIDs` 数组中取最后一个可用的前缀标识符（如果有），要么使用 `nextPrefixID` 值并递增它。然后，路由存储在 `routes` 映射中，利用了 Go 中优化的 [Swiss Table](https://go.dev/blog/swisstable)。为了检索附着在前缀上的路由，我们使用一个 64 位键在 `routes` 映射中逐条查找，该键由 32 位前缀索引和 32 位路由索引（对应路由在列表中的位置）组合而成。Akvorado 从第一条到最后一条扫描路由，找到最佳的那条。⁴（注释：扫描）如果路由键返回空结果，就表示没有更多路由了。 ```go type prefixIndex uint32 type routeIndex uint32 type routeKey uint64 ``` ## 驻留路由 一条路由包含 BGP 对等体标识符、部分 NLRI⁵（注释：NLRI）、下一跳和属性。 ```go type route struct { peer uint32 nlri intern.Reference[nlri] nextHop intern.Reference[nextHop] attributes intern.Reference[routeAttributes] prefixLen uint8 } type nlri struct { family bgp.Family path uint32 rd RD } type nextHop netip.Addr type routeAttributes struct { asn uint32 asPath []uint32 communities []uint32 largeCommunities []bgp.LargeCommunity } ``` 为了节省内存和分配，NLRI、下一跳和路由属性被“驻留”：用 32 位整数替换真实值。该机制早于 Go 1.23 引入的 `unique` 包（[参考](https://go.dev/blog/unique)）。我们保留它是因为它有不同权衡： - 它使用**显式引用计数**，而不是依赖弱指针。 - 它支持实现 `Hash()` 和 `Equal()` 方法的**不可比较值**。⁶（注释：哈希） - 它使用**显式池实例**。这对分片将很有用。 - 它具有**更好的性能**。例如参见此[基准测试](https://github.com/akvorado/akvorado/pull/2244/changes/682b6063af50780dcd64e46b39d5e66c5074d9ab)。 - 由于使用无符号 32 位引用而非指针，它消耗**一半内存**。 - 但**不适用于并发**。 ## 为什么不能扩展？ 在此实现中，全局读写锁是一个瓶颈。但具体如何？RIB 有几个使用者，每个都有自己的一组约束： - **Kafka 工作进程**通过 RIB 查找路由信息以丰富流量。它们受 Kafka 分区数限制。⁸（注释：KIP-932）Akvorado 还会调整它们数量，以确保向 ClickHouse 高效批量写入。在我们的设置中，工作进程数量在 8 到 16 之间波动。由于我们希望观察最新数据，不能承受 Kafka 工作进程严重滞后。 - **受监控的路由器**通过 BMP 协议发送路由更新。连接时，它们可能发送数百万条路由。⁹（注释：BMP 配置）初始同步后，更新会持续发送，并可能不时出现峰值。路由器在其 TCP 窗口满时会检测到 BMP 站卡住，并在这种情况下重置会话。虽然 Akvorado 实现了大型输入缓冲区，但仍需要足够快地持写锁更新接收到的路由，以避免被检测为卡住。 - 当**远程 BGP 对等体**宕机时，Akvorado 会在持写锁的情况下遍历 RIB 以刷新相关路由。当**受监控路由器**宕机时，Akvorado 会等待一段时间，但最终会刷新所有相关路由。 简而言之：在繁忙的设置中，读写锁的争用都很高，并且双方都不能滞后太多。 ## RIB 分片 ### 第一步：基本分片 为了移除全局锁，RIB 被拆分为多个“分片”，每个分片处理前缀的一个子集： 分片后 Akvorado BMP RIB 实现的内存布局示意图，每个结构体有自己的锁。 带分片的 Akvorado BMP RIB 实现。前缀树保持全局，并由单个锁保护。每个分片有自己的读写锁、自己的路由映射和用于存储 NLRI、下一跳和路由属性的驻留池——这在使用 Go 的 `unique` 包（[参考](https://go.dev/blog/unique)）时是不可能的。前缀索引也被分片：高 8 位是分片索引，剩余 24 位是本地前缀索引。 Gerhard 确认（[讨论](https://github.com/akvorado/akvorado/discussions/2287#discussioncomment-16020731)），在此[盲改](http://github.com/akvorado/akvorado/commit/7e6bbf2210fdf7116d2ee168b307b9906cc223c0)之后，BMP 接收器稳定运行。🎉 后来，我编写了一个[并发基准测试](https://github.com/akvorado/akvorado/blob/0811c40cc2065380e3a6230c2796312838e57850/outlet/routing/provider/bmp/concurrent_test.go)，包含超过 50 万条合成但合理的路由，¹⁰（注释：合理）分为 0 到 8 个写入者，尽可能快地处理路由，同时 1 到 16 个读取者持续查找一组 10,000 条路由。我不知道这个基准测试是否真实，但它证实了读写延迟的改进： 两张热力图。一张是读取延迟比率，另一张是写入延迟比率。两者都通过彩色方块比较分片前后的加速比。大多数方块为绿色。 分片后读写延迟性能的提升。它还显示，写入者数量较多会降低读取延迟。 ### 第二步：无锁读取 保护前缀树的单个读写锁是下一个目标。[bart](https://github.com/gaissmai/bart/) 包提供了使用写时复制返回更新树的替代变异方法。读取者不再需要全局锁，只留下它来同步写入者。前缀树被封装在一个原子指针中。 用于分片的 Akvorado BMP RIB 实现，带无锁读取。显示了每个结构体的内存布局。 带分片和无锁读取的 Akvorado BMP RIB 实现。没有锁的情况下，如果并发写入者移除了附着在此前缀索引上的最后一条路由并回收该索引用于其他前缀，读取者在遍历其树副本时可能获取到过时的前缀索引。为了避免这个问题，我们将前缀索引与代数（generation number）结合并存储在树中： ```go type generation uint32 type prefixRef struct { idx prefixIndex gen generation } type rib struct { mu sync.Mutex tree atomic.Pointer[bart.Table[prefixRef]] shards []*ribShard } ``` 每个分片存储每个本地前缀索引的代数。如果关联的前缀索引被释放，代数加 1。当查找附着在前缀索引上的路由时，读取者检查代数是否匹配。否则，它假定索引已被回收，路由列表为空。¹¹（注释：重试）你可以在上图中看到这种情况：前缀索引 5 存储的代数索引为 3，而 `[]generations` 数组中的当前值为 4。代数可能溢出，但由于查找很快，这不是问题。 针对这个新实现运行并发基准测试，显示了读取延迟的改进（一旦写时复制前缀树的成本被摊销）。 六张热力图。三张是读取延迟比率，另外三张是写入延迟比率。它们成对比较无分片、有分片和有锁自由读取的数据。对于读取延迟，大多数方块为绿色，显示第二步有改进。对于写入延迟，当读取者数量较少时加速比为负值。 无锁读取后读写延迟性能的提升。中间列显示了两步的累积改进。 --- 在优化 BMP 组件的多次尝试中，RIB 分片是更令人满意的方法之一。[Akvorado 2.2](https://github.com/akvorado/akvorado/releases/tag/v2.2.0) 实现了第一步。[PR #2433](https://github.com/akvorado/akvorado/pull/2433)（在撰写本文时起草）实现了第二步，并将随 Akvorado 2.4 发布。🪓