Cilium 依赖的 BART 路由表三节点深度解析BartNode / LiteNode / FastNode 的内存与查找性能全对比【免费下载链接】ciliumeBPF-based Networking, Security, and Observability项目地址: https://gitcode.com/GitHub_Trending/ci/cilium导读本文围绕当前仓库 vendor 目录中 bart 库 的核心文档 NODETYPES.md完整剖析 BARTBalanced Routing Tables路由表实现的三种 trie 节点类型——动态稀疏的BartNode、纯 bitset 前缀的LiteNode、定长数组的FastNode。你将掌握每种节点的内存占用计算模型、路径压缩Leaf/Fringe机制、逐层 O(1) 最长前缀匹配原理以及如何结合 64 位系统下的实测尺寸数据为路由表场景选型。文中所有结构体、算法与尺寸说明均与 vendor/github.com/gaissmai/bart 内的 Go 源码一一对应。背景BART 与三种节点类型的定位BART 是一个用于 IP 到 CIDR 前缀快速查找的 Go 库面向 ACL海量 CIDR 规则匹配、RIB大路由表低内存占用与 FIB数据面恒定时间的 LPM 查找三类场景。其底层数据结构是一个8 位定长 stride 的多比特 trie并借助源自 Donald E. Knuth Allotment Routing TableART算法的映射函数把每个 trie 层上可能出现的 256 个前缀位置组织成一棵完全二叉树Complete Binary Tree, CBT。围绕这套多比特 trieNODETYPES.md 明确说明 BART 实现了三种不同的节点类型各自针对特定使用场景做了取舍节点类型前缀表存储方式值存储内存特征对应顶层路由表BartNode[V]popcount 压缩的稀疏数组有内联V内存高效bart.TableLiteNode仅BitSet256只有存在性无内存最省bart.LiteFastNode[V]定长[256]数组有指针内存固定、速度最快bart.Fast上层实现可以验证这种一一对应关系bart.go 中Table[V]的root4/root6类型为nodes.BartNode[V]lite.go 中liteTable[V]的根节点是nodes.LiteNode[V]fast.go 中Fast[V]的根节点是nodes.FastNode[V]。三种节点类型的结构定义与内存模型NODETYPES.md 给出了全部三种节点在 64 位系统上的精确内存占用量。这些尺寸均建立在以下两个基础组件之上BitSet256[4]uint6432 字节见 bitset256.gosparse.Array256[T]BitSet256 []T56 字节 n×sizeof(T)见 array256.go64 位下切片头 24 字节 32 字节 bitset。此外还有一个统一约束子节点引用childRef为 8 字节*node指针或 16 字节interface{}值存储。三种节点在存储子节点时实际都使用了sparse.Array256[any]BartNode/LiteNode或[256]*anyFastNode因此按 16 字节的 interface 值存储口径计算。BartNode[V] —— 动态稀疏节点NODETYPES.md 中的定义与源码 bart.go 完全一致type BartNode[V any] struct { Prefixes sparse.Array256[V] // 56 n×sizeof(V) Children sparse.Array256[any] // 56 m×sizeof(childRef) }内存占用112 字节 n×sizeof(V) m×sizeof(childRef)其中Prefixes存前缀prefix → valueChildren存 256 个可能的下跳路径对应的子 trie 或路径压缩节点。源码注释bart.go指出Children 槽位中的条目只可能是三种类型*BartNode[V]内部子节点、*LeafNode[V]路径压缩叶深度 maxDepth-1、*FringeNode[V]路径压缩 fringe深度 maxDepth-1且与 stride 边界对齐。插入、查询、删除均委托给sparse.Array256的InsertAt/Get/DeleteAt位存在性测试 Rank 重映射负责把 256 个逻辑槽压缩到紧凑的Items切片中。LiteNode —— 前缀仅用 Bitset 的动态稀疏节点源码定义见 lite.go其Prefixes不再保存任何值仅用一个BitSet256记录哪些前缀下标被占用并额外维护Count uint16缓存活跃条目数type LiteNode[V any] struct { Children sparse.Array256[any] // 56 m×sizeof(childRef) Prefixes struct { bitset.BitSet256 // 32 字节仅存在性 Count uint16 // 2 字节 padding } }内存占用96 字节 m×sizeof(childRef)不存任何值注意这里的类型参数V是一个幻影类型phantom type——源码注释lite.go明确说明它仅用于统一方法生成LiteNode 本身不存储任何值。因此InsertPrefix(idx, _ V)只做 bitset 置位与计数GetPrefix/MustGetPrefix永远返回零值。FastNode —— 定长数组节点源码定义见 fast.go与 NODETYPES.md 给出的结构体一致type FastNode[V any] struct { Prefixes struct { bitset.BitSet256 Items [256]*V // 2,048 32 字节 } Children struct { bitset.BitSet256 Items [256]*any // 2,048 32 字节*any 对 nil 槽仅占 1 个字 } PfxCount uint16 CldCount uint16 // padding }内存占用4,168 字节固定与占用率无关这里有一个值得注意的实现细节Children.Items的类型是*any指向 interface 的指针而非any。fast.go 的注释解释了原因——大量槽位是 nil*any对 nil 只占 1 个字8 字节而any接口值需 2 个字16 字节因此整体内存可降低约 30%。PfxCount/CldCount两个 uint16 计数器用于替代昂贵的BitSet256.Size()调用在InsertPrefix/DeletePrefix、InsertChild/DeleteChild时自动维护fast.go。真实场景内存对比同一节点 10 前缀 5 子节点NODETYPES.md 给出一个直接的对比场景——某节点含 10 个前缀、5 个子节点假定 childRef 16 字节、载荷指针 8 字节节点类型BasePayloadChildren总计Bytes/PrefixLiteNode9605×1680176 字节17BartNode[int]11210×8805×1680272 字节27FastNode[int]4,168004,168 字节417结论非常直观LiteNode 最省内存、FastNode 固定成本最高。LiteNode 比 BartNode 节省了整块值存储96 vs 112 基座 80 字节 payloadFastNode 则因为每个节点都要为 256 个前缀槽和 256 个子节点槽预留定长数组而承担恒定开销。路径压缩LeafNode 与 FringeNode 的深度优化NODETYPES.md 强调在真实场景中值类型V通常是指向载荷结构体的指针如*RouteInfo、*Metadata因此下文的计算假定V 8 字节指针引用的真实载荷不计入每节点开销。路径压缩产生的两类终止条目定义在 nodebasics.gotype LeafNode[V any] struct { Value V Prefix netip.Prefix } type FringeNode[V any] struct { Value V }LeafNodeLeafNode[V]Value (8B) Prefix (32B)40 字节。用于前缀不与 stride 边界对齐、需要记录完整netip.Prefix的路径压缩条目在 LiteNode 中由于不存值LeafNode 只占32 字节。FringeNodeFringeNode[V]8 字节仅值指针。前缀与 stride 边界恰好对齐/8、/16、/24 … /128时使用前缀隐含在 trie 中的位置里无需存储在 LiteNode 中则为0 字节。判定逻辑在IsFringe(depth, pfx)nodebasics.go当depth lastOctetPlusOne-1 lastBits 0时即视为 fringe。LastOctetPlusOneAndLastBitsnodebasics.go通过bits3与bits7快速拆出完整 stride 数与末 stride 剩余位数其中/32、/128这类最长前缀永远作为路径压缩 fringe 插入不会新建子节点。两类条目的特殊性质nodebasics.goleaf 在任意中间层depth lastOctet插入若再无后续 stride 边界匹配fringe 插在最后一个 stride 层depth lastOctet并作为其下游所有位模式更具体子网的默认路由depth lastOctet1时则退化为普通前缀octet/pfx 0/0idx 1即 stride 层的默认路由。混合子节点场景的完整计算NODETYPES.md 给出了更贴近真实路由表的混合场景节点含 10 个前缀 5 个普通子节点 5 个 LeafNode 5 个 FringeNode总前缀条目数 10 5 5 20 个。节点类型BasePrefixes¹Children²SubtotalLeaves³Fringes⁴Bytes/Prefix⁵LiteNode96 B015×16240 B336 B160 B0 B16.8BartNode[V]112 B10×880 B15×16240 B432 B200 B40 B21.6FastNode[V]4,168 B004,168 B200 B40 B208.4Notes来自原文档前缀LiteNode 不存值0BBartNode/FastNode 存 10 个指向载荷结构体的 8B 指针子节点共 15 个5 节点 5 叶 5 fringe每个以interface{}存 16 字节叶节点LiteNode 存 5×32B LeafNodeValue 字段未用BartNode/FastNode 存 5×40B LeafNode[V]各含 8B 指针FringeLiteNode 存 0B前缀隐含、Value 未用BartNode/FastNode 存 5×8B FringeNode[V]计算方式为Subtotal / 20仅计节点本身不含引用的子节点与外部载荷结构体。内存效率洞察LiteNode 的优势来自原文档LeafNode 中不存值每个叶省 8 字节32B vs 40BFringeNode 中不存值每个 fringe 省 8 字节0B vs 8B节点内前缀不存值10 个前缀相比 BartNode 省 80 字节对典型路由表而言总体比 BartNode小约 22%。路径压缩的收益LeafNode消除孤立前缀的中间节点FringeNode压缩 /8、/16、/24 边界无节点额外开销trie 深度下降层数更少 每条路由的查找层数更少。重要说明原文档真实的载荷结构体路由信息、元数据等存放在节点外部由 8 字节指针引用因其可被共享或与应用强相关故未计入上述每节点计算。查找性能深入剖析NODETYPES.md 的核心结论是三种节点类型都实现逐层 O(1) 查找但都必须沿 trie 层逐级下钻整体复杂度为O(trie_depth) 而非 O(路由条数)。Trie 结构与性能特征每层 8 位 stride每层 trie 处理 IP 地址的 8 个比特IPv4 遍历最坏 4 层32÷8/24 路由实际通常 3 层IPv6 遍历最坏 16 层128÷8/48 路由实际通常 6 层性能特征O(trie_depth)与路由条数无关IPv6 vs IPv4由于树更深IPv6 固有约 2 倍慢于 IPv4。代码层面对应常量定义在 nodebasics.go——strideLen 8、MaxItems 256、MaxTreeDepth 16IPv6 最多 16 字节深度、DepthMask MaxTreeDepth - 1用于查找热路径上的边界检查消除BCE。Table.Lookup的下钻循环bart.go在每个 octet 处先检查Children.Test(octet)命中 FringeNode 直接返回其值fringe 即下游默认路由命中 LeafNode 则校验kid.Prefix.Contains(ip)后返回随后进入回溯阶段bart.go沿路径栈逐层用IntersectionTop(lpm.LookupTbl[idx])做最长前缀匹配。BartNode[V] 与 LiteNode —— 优化的逐层操作预计算查找表lpm.LookupTbl[idx]消除每层内部的逐位搜索查找表由 lookuptblgenerated.go 生成BitSet256 交集IntersectionTop()实现瞬时前缀匹配bitset256.go基于 Rank 的间接寻址bitset 到 slice 的映射使用预计算的 Rank 掩码rankMaskbitset256.go约 8KB 静态内存换取零分配、无分支、缓存友好的常数时间 Rank见 array256.go 的Get/MustGet管线友好每层仅 4 次 bitset 操作4×uint64利于 CPU 流水线FirstSet甚至一次性并行计算 4 个字的 trailing-zeros 以避免分支预测失败bitset256.go无回溯传统 LPM 的逐步回溯被直接查表替代——严格说是将回溯转移到了 bitset 交集操作中Contains/LookupIdx用Intersects/IntersectionTop与lpm.LookupTbl[idx]相交见 bart.go。FastNode[V] —— 每层直接数组访问每层零间接prefixes[idx]与children[idx]直接数组下标缓存最优每层内连续内存布局性能优势尽管有稀疏优化每层仍约快 40%。值得留意的是 FastNode 采用经典 ART 的allot配给算法fast.go插入前缀时为每个唯一前缀分配独立*V指针并把其祖先子树中指向同一旧指针的槽位批量改写为新指针从而让Contains/Lookup退化为一次数组判空Items[idx] ! nilfast.go——这是其逐层速度最快的原因。代价是InsertPrefix需要逐层分配new(V)并在子树中扩散指针写入路径明显重于 BartNode/LiteNode 的纯 bitset 操作。选型建议与适用场景综合 NODETYPES.md 与 README.md 的对比表三种节点面向的场景非常清晰场景推荐节点理由ACL 白/黑名单只关心 IP 是否命中 CIDR无需值LiteNodebart.Lite内存最低约 17 B/前缀查找时间与 BartNode 相同RIB/大型路由表前缀需关联下一跳、路由信息等载荷BartNodebart.Table稀疏压缩 路径/边界压缩内存效率与查找速度均衡FIB/数据面追求逐层极致速度路由规模可控FastNodebart.Fast定长数组 allot每层零间接、最快查找但节点内存固定 4,168 B顶层 API 的对应关系也可以在 lite.go、bart.go 与 fast.go 中直接查阅。需要强调的是LiteNode 是 BartNode 的无载荷特化因此bart.Lite的 API 同样提供Insert/Contains/Get等操作只是语义上只记录前缀存在性README.md 中的 ACL 示例可验证而三者的Lookup底层遍历模式下钻 回溯栈 IntersectionTop保持一致对比 bart.go、lite.go 与 fast.go 中的同名方法保证了同一套 trie 结构在不同节点实现间的行为等价。总结NODETYPES.md 完整揭示了 BART 在内存与速度之间的三道分水岭存储骨架相同三种节点都是 8 位 stride 多比特 trie 的一层256 槽位全部经由BitSet256[4]uint64驱动内存差异来自前缀表的表示稀疏数组BartNode→ 纯 bitsetLiteNode→ 定长数组FastNode对应 112 字节级、96 字节级与 4,168 字节级的基座成本路径压缩Leaf/Fringe是共同基石它让前缀数量与节点数量解耦将典型路由表的每前缀开销压低到 17–22 字节量级同时通过削减 trie 深度提升查找性能。无论是面向内存受限的 ACL 场景选择 LiteNode还是面向数据面热路径选择 FastNode理解这三种节点的结构、尺寸与查找路径都是正确使用 BART 路由表的前提。【免费下载链接】ciliumeBPF-based Networking, Security, and Observability项目地址: https://gitcode.com/GitHub_Trending/ci/cilium创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/15 22:59:12 · 阅读 1.2k Cilium 依赖的 BART 路由表三节点深度解析：BartNode / LiteNode / FastNode 的内存与查找性能全对比
Cilium 依赖的 BART 路由表三节点深度解析BartNode / LiteNode / FastNode 的内存与查找性能全对比【免费下载链接】ciliumeBPF-based Networking, Security, and Observability项目地址: https://gitcode.com/GitHub_Trending/ci/cilium导读本文围绕当前仓库 vendor 目录中 bart 库 的核心文档 NODETYPES.md完整剖析 BARTBalanced Routing Tables路由表实现的三种 trie 节点类型——动态稀疏的BartNode、纯 bitset 前缀的LiteNode、定长数组的FastNode。你将掌握每种节点的内存占用计算模型、路径压缩Leaf/Fringe机制、逐层 O(1) 最长前缀匹配原理以及如何结合 64 位系统下的实测尺寸数据为路由表场景选型。文中所有结构体、算法与尺寸说明均与 vendor/github.com/gaissmai/bart 内的 Go 源码一一对应。背景BART 与三种节点类型的定位BART 是一个用于 IP 到 CIDR 前缀快速查找的 Go 库面向 ACL海量 CIDR 规则匹配、RIB大路由表低内存占用与 FIB数据面恒定时间的 LPM 查找三类场景。其底层数据结构是一个8 位定长 stride 的多比特 trie并借助源自 Donald E. Knuth Allotment Routing TableART算法的映射函数把每个 trie 层上可能出现的 256 个前缀位置组织成一棵完全二叉树Complete Binary Tree, CBT。围绕这套多比特 trieNODETYPES.md 明确说明 BART 实现了三种不同的节点类型各自针对特定使用场景做了取舍节点类型前缀表存储方式值存储内存特征对应顶层路由表BartNode[V]popcount 压缩的稀疏数组有内联V内存高效bart.TableLiteNode仅BitSet256只有存在性无内存最省bart.LiteFastNode[V]定长[256]数组有指针内存固定、速度最快bart.Fast上层实现可以验证这种一一对应关系bart.go 中Table[V]的root4/root6类型为nodes.BartNode[V]lite.go 中liteTable[V]的根节点是nodes.LiteNode[V]fast.go 中Fast[V]的根节点是nodes.FastNode[V]。三种节点类型的结构定义与内存模型NODETYPES.md 给出了全部三种节点在 64 位系统上的精确内存占用量。这些尺寸均建立在以下两个基础组件之上BitSet256[4]uint6432 字节见 bitset256.gosparse.Array256[T]BitSet256 []T56 字节 n×sizeof(T)见 array256.go64 位下切片头 24 字节 32 字节 bitset。此外还有一个统一约束子节点引用childRef为 8 字节*node指针或 16 字节interface{}值存储。三种节点在存储子节点时实际都使用了sparse.Array256[any]BartNode/LiteNode或[256]*anyFastNode因此按 16 字节的 interface 值存储口径计算。BartNode[V] —— 动态稀疏节点NODETYPES.md 中的定义与源码 bart.go 完全一致type BartNode[V any] struct { Prefixes sparse.Array256[V] // 56 n×sizeof(V) Children sparse.Array256[any] // 56 m×sizeof(childRef) }内存占用112 字节 n×sizeof(V) m×sizeof(childRef)其中Prefixes存前缀prefix → valueChildren存 256 个可能的下跳路径对应的子 trie 或路径压缩节点。源码注释bart.go指出Children 槽位中的条目只可能是三种类型*BartNode[V]内部子节点、*LeafNode[V]路径压缩叶深度 maxDepth-1、*FringeNode[V]路径压缩 fringe深度 maxDepth-1且与 stride 边界对齐。插入、查询、删除均委托给sparse.Array256的InsertAt/Get/DeleteAt位存在性测试 Rank 重映射负责把 256 个逻辑槽压缩到紧凑的Items切片中。LiteNode —— 前缀仅用 Bitset 的动态稀疏节点源码定义见 lite.go其Prefixes不再保存任何值仅用一个BitSet256记录哪些前缀下标被占用并额外维护Count uint16缓存活跃条目数type LiteNode[V any] struct { Children sparse.Array256[any] // 56 m×sizeof(childRef) Prefixes struct { bitset.BitSet256 // 32 字节仅存在性 Count uint16 // 2 字节 padding } }内存占用96 字节 m×sizeof(childRef)不存任何值注意这里的类型参数V是一个幻影类型phantom type——源码注释lite.go明确说明它仅用于统一方法生成LiteNode 本身不存储任何值。因此InsertPrefix(idx, _ V)只做 bitset 置位与计数GetPrefix/MustGetPrefix永远返回零值。FastNode —— 定长数组节点源码定义见 fast.go与 NODETYPES.md 给出的结构体一致type FastNode[V any] struct { Prefixes struct { bitset.BitSet256 Items [256]*V // 2,048 32 字节 } Children struct { bitset.BitSet256 Items [256]*any // 2,048 32 字节*any 对 nil 槽仅占 1 个字 } PfxCount uint16 CldCount uint16 // padding }内存占用4,168 字节固定与占用率无关这里有一个值得注意的实现细节Children.Items的类型是*any指向 interface 的指针而非any。fast.go 的注释解释了原因——大量槽位是 nil*any对 nil 只占 1 个字8 字节而any接口值需 2 个字16 字节因此整体内存可降低约 30%。PfxCount/CldCount两个 uint16 计数器用于替代昂贵的BitSet256.Size()调用在InsertPrefix/DeletePrefix、InsertChild/DeleteChild时自动维护fast.go。真实场景内存对比同一节点 10 前缀 5 子节点NODETYPES.md 给出一个直接的对比场景——某节点含 10 个前缀、5 个子节点假定 childRef 16 字节、载荷指针 8 字节节点类型BasePayloadChildren总计Bytes/PrefixLiteNode9605×1680176 字节17BartNode[int]11210×8805×1680272 字节27FastNode[int]4,168004,168 字节417结论非常直观LiteNode 最省内存、FastNode 固定成本最高。LiteNode 比 BartNode 节省了整块值存储96 vs 112 基座 80 字节 payloadFastNode 则因为每个节点都要为 256 个前缀槽和 256 个子节点槽预留定长数组而承担恒定开销。路径压缩LeafNode 与 FringeNode 的深度优化NODETYPES.md 强调在真实场景中值类型V通常是指向载荷结构体的指针如*RouteInfo、*Metadata因此下文的计算假定V 8 字节指针引用的真实载荷不计入每节点开销。路径压缩产生的两类终止条目定义在 nodebasics.gotype LeafNode[V any] struct { Value V Prefix netip.Prefix } type FringeNode[V any] struct { Value V }LeafNodeLeafNode[V]Value (8B) Prefix (32B)40 字节。用于前缀不与 stride 边界对齐、需要记录完整netip.Prefix的路径压缩条目在 LiteNode 中由于不存值LeafNode 只占32 字节。FringeNodeFringeNode[V]8 字节仅值指针。前缀与 stride 边界恰好对齐/8、/16、/24 … /128时使用前缀隐含在 trie 中的位置里无需存储在 LiteNode 中则为0 字节。判定逻辑在IsFringe(depth, pfx)nodebasics.go当depth lastOctetPlusOne-1 lastBits 0时即视为 fringe。LastOctetPlusOneAndLastBitsnodebasics.go通过bits3与bits7快速拆出完整 stride 数与末 stride 剩余位数其中/32、/128这类最长前缀永远作为路径压缩 fringe 插入不会新建子节点。两类条目的特殊性质nodebasics.goleaf 在任意中间层depth lastOctet插入若再无后续 stride 边界匹配fringe 插在最后一个 stride 层depth lastOctet并作为其下游所有位模式更具体子网的默认路由depth lastOctet1时则退化为普通前缀octet/pfx 0/0idx 1即 stride 层的默认路由。混合子节点场景的完整计算NODETYPES.md 给出了更贴近真实路由表的混合场景节点含 10 个前缀 5 个普通子节点 5 个 LeafNode 5 个 FringeNode总前缀条目数 10 5 5 20 个。节点类型BasePrefixes¹Children²SubtotalLeaves³Fringes⁴Bytes/Prefix⁵LiteNode96 B015×16240 B336 B160 B0 B16.8BartNode[V]112 B10×880 B15×16240 B432 B200 B40 B21.6FastNode[V]4,168 B004,168 B200 B40 B208.4Notes来自原文档前缀LiteNode 不存值0BBartNode/FastNode 存 10 个指向载荷结构体的 8B 指针子节点共 15 个5 节点 5 叶 5 fringe每个以interface{}存 16 字节叶节点LiteNode 存 5×32B LeafNodeValue 字段未用BartNode/FastNode 存 5×40B LeafNode[V]各含 8B 指针FringeLiteNode 存 0B前缀隐含、Value 未用BartNode/FastNode 存 5×8B FringeNode[V]计算方式为Subtotal / 20仅计节点本身不含引用的子节点与外部载荷结构体。内存效率洞察LiteNode 的优势来自原文档LeafNode 中不存值每个叶省 8 字节32B vs 40BFringeNode 中不存值每个 fringe 省 8 字节0B vs 8B节点内前缀不存值10 个前缀相比 BartNode 省 80 字节对典型路由表而言总体比 BartNode小约 22%。路径压缩的收益LeafNode消除孤立前缀的中间节点FringeNode压缩 /8、/16、/24 边界无节点额外开销trie 深度下降层数更少 每条路由的查找层数更少。重要说明原文档真实的载荷结构体路由信息、元数据等存放在节点外部由 8 字节指针引用因其可被共享或与应用强相关故未计入上述每节点计算。查找性能深入剖析NODETYPES.md 的核心结论是三种节点类型都实现逐层 O(1) 查找但都必须沿 trie 层逐级下钻整体复杂度为O(trie_depth) 而非 O(路由条数)。Trie 结构与性能特征每层 8 位 stride每层 trie 处理 IP 地址的 8 个比特IPv4 遍历最坏 4 层32÷8/24 路由实际通常 3 层IPv6 遍历最坏 16 层128÷8/48 路由实际通常 6 层性能特征O(trie_depth)与路由条数无关IPv6 vs IPv4由于树更深IPv6 固有约 2 倍慢于 IPv4。代码层面对应常量定义在 nodebasics.go——strideLen 8、MaxItems 256、MaxTreeDepth 16IPv6 最多 16 字节深度、DepthMask MaxTreeDepth - 1用于查找热路径上的边界检查消除BCE。Table.Lookup的下钻循环bart.go在每个 octet 处先检查Children.Test(octet)命中 FringeNode 直接返回其值fringe 即下游默认路由命中 LeafNode 则校验kid.Prefix.Contains(ip)后返回随后进入回溯阶段bart.go沿路径栈逐层用IntersectionTop(lpm.LookupTbl[idx])做最长前缀匹配。BartNode[V] 与 LiteNode —— 优化的逐层操作预计算查找表lpm.LookupTbl[idx]消除每层内部的逐位搜索查找表由 lookuptblgenerated.go 生成BitSet256 交集IntersectionTop()实现瞬时前缀匹配bitset256.go基于 Rank 的间接寻址bitset 到 slice 的映射使用预计算的 Rank 掩码rankMaskbitset256.go约 8KB 静态内存换取零分配、无分支、缓存友好的常数时间 Rank见 array256.go 的Get/MustGet管线友好每层仅 4 次 bitset 操作4×uint64利于 CPU 流水线FirstSet甚至一次性并行计算 4 个字的 trailing-zeros 以避免分支预测失败bitset256.go无回溯传统 LPM 的逐步回溯被直接查表替代——严格说是将回溯转移到了 bitset 交集操作中Contains/LookupIdx用Intersects/IntersectionTop与lpm.LookupTbl[idx]相交见 bart.go。FastNode[V] —— 每层直接数组访问每层零间接prefixes[idx]与children[idx]直接数组下标缓存最优每层内连续内存布局性能优势尽管有稀疏优化每层仍约快 40%。值得留意的是 FastNode 采用经典 ART 的allot配给算法fast.go插入前缀时为每个唯一前缀分配独立*V指针并把其祖先子树中指向同一旧指针的槽位批量改写为新指针从而让Contains/Lookup退化为一次数组判空Items[idx] ! nilfast.go——这是其逐层速度最快的原因。代价是InsertPrefix需要逐层分配new(V)并在子树中扩散指针写入路径明显重于 BartNode/LiteNode 的纯 bitset 操作。选型建议与适用场景综合 NODETYPES.md 与 README.md 的对比表三种节点面向的场景非常清晰场景推荐节点理由ACL 白/黑名单只关心 IP 是否命中 CIDR无需值LiteNodebart.Lite内存最低约 17 B/前缀查找时间与 BartNode 相同RIB/大型路由表前缀需关联下一跳、路由信息等载荷BartNodebart.Table稀疏压缩 路径/边界压缩内存效率与查找速度均衡FIB/数据面追求逐层极致速度路由规模可控FastNodebart.Fast定长数组 allot每层零间接、最快查找但节点内存固定 4,168 B顶层 API 的对应关系也可以在 lite.go、bart.go 与 fast.go 中直接查阅。需要强调的是LiteNode 是 BartNode 的无载荷特化因此bart.Lite的 API 同样提供Insert/Contains/Get等操作只是语义上只记录前缀存在性README.md 中的 ACL 示例可验证而三者的Lookup底层遍历模式下钻 回溯栈 IntersectionTop保持一致对比 bart.go、lite.go 与 fast.go 中的同名方法保证了同一套 trie 结构在不同节点实现间的行为等价。总结NODETYPES.md 完整揭示了 BART 在内存与速度之间的三道分水岭存储骨架相同三种节点都是 8 位 stride 多比特 trie 的一层256 槽位全部经由BitSet256[4]uint64驱动内存差异来自前缀表的表示稀疏数组BartNode→ 纯 bitsetLiteNode→ 定长数组FastNode对应 112 字节级、96 字节级与 4,168 字节级的基座成本路径压缩Leaf/Fringe是共同基石它让前缀数量与节点数量解耦将典型路由表的每前缀开销压低到 17–22 字节量级同时通过削减 trie 深度提升查找性能。无论是面向内存受限的 ACL 场景选择 LiteNode还是面向数据面热路径选择 FastNode理解这三种节点的结构、尺寸与查找路径都是正确使用 BART 路由表的前提。【免费下载链接】ciliumeBPF-based Networking, Security, and Observability项目地址: https://gitcode.com/GitHub_Trending/ci/cilium创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考