Scaling Akvorado BMP RIB with Sharding：通过分片技术扩展 BGP 路由表性能

背景

Akvorado 是一款网络流量分析工具，为了将路由信息（如 AS 路径或 BGP 社区属性）与网络流量关联起来，它通过 BGP 监控协议（BMP）导入路由数据。随着互联网路由表规模的增长，包含超过 100 万条路由，Akvorado 需要能够扩展到处理数千万条路由。这长期以来是一个巨大的挑战，但作者 Vincent Bernat 表示，通过引入 RIB（路由信息库）分片技术，这一问题已得到解决。

RIB 分片的核心思想是将路由数据库拆分为多个部分，从而支持并发更新，解决全局锁带来的性能瓶颈。

核心内容

之前的实现架构

Akvorado 的 RIB 由两个主要元素构建：

1. 前缀树（Prefix Tree）：用于高效存储和查找 IP 前缀。
2. 附着在每个前缀上的路由列表：存储具体的路由条目。

例如，前缀 2001:db8:1::/48 可能包含来自不同对等体（Peer）的多条路由，每条路由具有不同的下一跳、AS 路径和社区属性。

在 Go 语言中，rib 结构体定义如下：

type rib struct {
    tree       *bart.Table[prefixIndex] // 前缀树
    routes     map[routeKey]route       // 路由映射表
    nlris      *intern.Pool[nlri]       // NLRI 对象池
    nextHops   *intern.Pool[nextHop]    // 下一跳对象池
    rtas       *intern.Pool[routeAttributes] // 路由属性对象池
    nextPrefixID prefixIndex             // 下一个可用的前缀 ID
    freePrefixIDs []prefixIndex         // 空闲的前缀 ID 列表
}

• 前缀树：使用 bart 包，这是 Donald Knuth 的 ART 算法的一种适配实现。基准测试显示，它在查找、插入和内存使用方面优于其他包。
• 路由存储：为了避免为每个前缀分配数组给垃圾回收器带来过大压力，Akvorado 没有直接将路由列表存储在前缀树中。相反，它为每个前缀分配一个唯一的 32 位前缀标识符（Prefix ID）。路由存储在 routes 映射表中，利用 Go 优化的 Swiss Table。查找时，通过组合 32 位前缀索引和 32 位路由索引生成的 64 位键来检索路由。

路由的内部化（Interning）

为了节省内存和分配开销，NLRI（网络层可达性信息）、下一跳和路由属性被“内部化”：用一个 32 位整数替换实际值。这种机制早于 Go 1.23 引入的 unique 包，但作者选择保留它，因为其在权衡上具有优势：

• 使用显式引用计数，而非依赖弱指针。
• 支持实现 Hash() 和 Equal() 方法的非可比值。
• 使用显式的池实例，这对分片至关重要。
• 性能更好。
• 由于使用无符号 32 位引用而非指针，内存消耗减半。
• 缺点：不支持并发使用。

为什么之前的实现无法扩展？

主要瓶颈在于全局读写锁（Global Read/Write Lock）。RIB 有多个用户，各自有不同的约束：

1. Kafka 工作者：查找 RIB 以用路由信息丰富流量数据。它们受 Kafka 分区数量限制，且不能滞后太多，因为需要观察最新数据。
2. 受监控的路由器：通过 BMP 协议发送路由更新。连接时可能发送数百万条路由，之后持续发送更新。如果 Akvorado 处理太慢，TCP 窗口满会导致路由器重置会话。因此，更新必须在持有写锁的情况下快速完成。
3. 对等体故障处理：当远程 BGP 对等体或受监控路由器宕机时，Akvorado 需要持有写锁遍历 RIB 以清除相关路由。

在繁忙的系统中，读写锁竞争激烈，且读写双方都不能滞后。

RIB 分片方案

为了解决全局锁问题，RIB 被拆分为多个“分片（Shards）”，每个分片处理一部分前缀。

第一步：基本分片

• 前缀树：保持全局，由单个锁保护。
• 分片：每个分片拥有自己的读写锁、路由映射表以及用于存储 NLRI、下一跳和属性的内部化对象池。
• 前缀索引分片：32 位前缀索引的高 8 位作为分片索引，低 24 位作为局部前缀索引。

这一改动显著改善了 BMP 接收器的稳定性。基准测试显示，读写延迟均有改善，但写入者数量过多会降低读取延迟。

第二步：无锁读取

全局读写锁仍然是瓶颈。bart 包提供了替代的变异方法，使用**写时复制（Copy-on-Write）**返回更新后的树。

• 原子指针：前缀树被包装在原子指针中。
• 无锁读取：读者不再需要全局锁，锁仅用于同步写入者。
• 生成号（Generation Number）：由于没有锁，读者在遍历树的副本时可能会获取到过时的前缀索引（例如，当写入者删除了最后一个路由并回收了该索引用于新前缀时）。为了解决这个问题，前缀索引与生成号结合存储。
  • 每个分片存储每个局部前缀索引的生成号。
  • 当关联的前缀索引被释放时，生成号加 1。
  • 查找时，读者检查生成号是否匹配。如果不匹配，则认为索引已被回收，路由列表为空。

基准测试显示，一旦写时复制前缀树的成本被摊销，读取延迟会有显著提升。

Akvorado 2.2 实现了第一步，而 PR #2433（随 Akvorado 2.4 发布）实现了第二步。

关键要点

• 性能瓶颈根源：早期 Akvorado 实现中，全局读写锁在处理高并发 BMP 路由更新和 Kafka 流量丰富请求时成为严重瓶颈，导致锁竞争和高延迟。
• 分片策略：通过将 RIB 拆分为多个分片，每个分片独立管理一部分前缀及其路由数据，实现了并发更新。前缀索引的高位用于定位分片，低位用于局部查找。
• 内存优化：采用“内部化”技术，用 32 位整数引用替换复杂的 NLRI、下一跳和属性对象，显著降低内存占用和 GC 压力，同时保持高性能。
• 无锁读取优化：在基本分片基础上，利用 bart 包的写时复制特性，将前缀树置于原子指针中，使读取操作无需持有全局锁，仅写入者需要锁同步，进一步提升了读取性能。
• 数据一致性保障：引入“生成号”机制解决无锁读取下的数据竞争问题。通过检查前缀索引对应的生成号，读者可以判断索引是否被回收，从而避免读取过期或错误的数据。
• 版本演进：Akvorado 2.2 引入了基本分片，Akvorado 2.4 引入了无锁读取优化，逐步解决了大规模路由表扩展问题。

意义与影响

• 可扩展性突破：该方案使 Akvorado 能够稳定处理数千万条路由，满足了现代互联网大规模路由监控的需求。
• 实时性提升：通过减少锁竞争和无锁读取，显著降低了路由更新的延迟，确保 BMP 会话不会因处理超时而被重置，提高了网络监控的实时性和可靠性。
• 资源效率：内部化和分片技术有效控制了内存使用和 CPU 开销，使得在资源受限的环境中也能高效运行大规模路由分析。
• 技术借鉴：