互联网向 IPv6 的全面迁移正在加速，全球 IPv6 用户已突破数十亿，路由表规模预计在 2030 年前超过 30 万条前缀。与 IPv4 相比，IPv6 地址长度从 32 位扩展到 128 位，前缀长度分布更加分散（从 /32 到 /64 不等），这使得传统的最长前缀匹配（Longest Prefix Match，LPM）算法面临严重的性能瓶颈。商品服务器上的软件路由器在 IPv6 场景下的查找速度通常比 IPv4 下降 3 到 10 倍，内存占用增加 10 到 50 倍。阿里云团队提出的 PlanB 框架通过将二维 LPM 问题转化为一维区间搜索，并结合缓存友好的线性化 B+ 树与 AVX-512 向量化加速，在商品 CPU 上实现了单核 390 MLPS（百万次查找每秒）、12 核 3.4 BLPS（十亿次查找每秒）的吞吐量，较现有最优软件方案提升 1.6 倍到 14 倍，同时将内存开销降低 56% 到 92%。
二维转一维：LPM 的数学变换
IPv6 路由查找的核心挑战在于 LPM 本身是一个二维搜索问题：需要同时匹配目标地址的数值和前缀长度。传统方案将这两维分离处理 —— 先按前缀长度二分查找，再在对应长度的前缀集合中进行精确匹配 —— 这种分离设计导致大量冗余的内存访问和条件分支。PlanB 的核心创新在于对整个问题进行数学变换：把每个前缀（prefix, prefix_length）转换为一个闭区间 [start, end]，其中 start 就是前缀本身，end = prefix + 2^{128 - prefix_length} - 1。例如，前缀 2001:0db8::/32 对应的区间是 [2001:0db8::, 2001:0db8:ffff:ffff:ffff:ffff:ffff:ffff]。转换后，所有前缀的起始地址和结束地址构成一组边界点，对这些边界点排序即可将整个 128 位地址空间划分为若干互不重叠的基本区间（elementary intervals）。这个变换的本质是将二维搜索等价转化为一维前驱搜索：给定目标地址 D，只需在排好序的基本区间起始地址数组中找到小于等于 D 的最大元素，其对应的下一跳即为最长匹配前缀。
这种变换的关键优势在于其与前缀分布无关的确定性：无论实际路由表的前缀长度分布如何，区间划分只取决于边界点集合本身。PlanB 将每个基本区间与一个预计算好的下一跳关联 —— 因为同一区间内的所有地址都被同一组前缀覆盖，根据 LPM 规则，区间内必然存在一个最长前缀，这个最长前缀的下一跳可以直接作为区间的属性存储。查找过程因此简化为在排好序的区间起始地址数组上做一次二分查找（或更高效的向量化搜索），完全消除了对前缀长度维度的显式处理。
线性化 B+ 树：指针无关的缓存对齐布局
为了高效支撑上述一维搜索，PlanB 提出了线性化 B+ 树（linearized B+ tree）数据结构。传统 B+ 树使用指针在节点之间跳转，这种指针追踪（pointer chasing）在深度遍历时会引发大量缓存未命中，尤其对于需要 6 到 8 层遍历的 IPv6 场景性能影响显著。线性化 B+ 树将整个树结构映射到一个扁平的连续数组中，完全消除指针：父节点与子节点之间的关系通过数组索引的算术运算直接计算。
具体实现时，PlanB 将每个节点设计为恰好 64 字节，精确对齐 x86 CPU 的缓存行。由于使用 64 位关键字（IPv6 区间起始地址的高 64 位），每个节点可以容纳 8 个有序关键字，形成一个 9 叉树（8 个关键字 + 9 个子节点指针）。这种设计的数学基础如下：设树的深度为 d，度为 b = k + 1 = 9，每层第一个节点的起始索引可以通过几何级数公式 level_start (d+1) = k × (b^{(d+1)} - 1) / (b - 1) 计算得出。第 d 层的内部节点后面紧接着第 d 层的叶子节点，整个布局呈现出完美的广度优先遍历顺序。假设使用 5 层内部节点（深度 d = 5），该结构可以索引超过 47 万个基本区间，足以容纳当前主流的 IPv6 路由表（通常在 20 万到 25 万条前缀）；若扩展到 6 层内部节点，则可支持超过 420 万个区间，对应超过 100 万条前缀的路由表，内存占用约 36 MB，仍完全落在现代服务器 CPU 的 L3 缓存范围内。
树的遍历过程是确定性的：始终从根节点向下走到叶子节点，不存在中间提前终止的情况。最坏情况下的查找成本严格等于树的高度加上一次叶子节点的二分搜索，对于典型配置（6 层内部节点）仅需 7 次内存访问。这种确定性遍历是 PlanB 能够实现极低尾延迟的关键 —— 无论流量模式如何（随机、突发或恶意），查找延迟始终保持稳定，不会出现传统 trie 或哈希方案中因缓存未命中导致的性能剧烈抖动。
AVX-512 向量化：单指令并行比较八个关键字
线性化 B+ 树的节点恰好容纳 8 个 64 位关键字这一特性与 AVX-512 指令集的 512 位向量宽度完美契合。AVX-512 指令集每条向量指令可以同时处理 8 个 64 位数据 lanes，PlanB 利用这一点实现了节点内搜索的完全向量化。查找算法首先使用 vpbroadcastq 指令将目标 IPv6 地址（取其高 64 位）广播到向量寄存器的全部 8 个槽位，然后用 vpcmpnltuq 指令将目标地址与节点中的 8 个关键字同时比较，产生一个 8 位掩码（mask），其中每一位对应一对比较结果。最后通过 popcnt 指令对该掩码执行人口计数，计数结果直接作为子节点索引进行下一层遍历。
这个向量化搜索过程的汇编层面只包含四条核心指令：向量广播、向量加载、向量比较、计数。整个节点遍历在极少数周期内完成，与传统的标量循环（可能需要 8 次比较和 8 次条件跳转）形成鲜明对比。向量化不仅大幅降低了指令数，更重要的是消除了条件分支 ——vpcmpnltuq 和 popcnt 的组合是完完全全的无分支代码，CPU 的分支预测器无需介入，彻底避免了分支预测失败带来的流水线清空惩罚。对于不支持 AVX-512 的平台（如只有 AVX2 的较旧服务器或 ARM NEON 环境），相同的算法可以分解为两次 256 位操作或四次 128 位操作，原理完全一致，代码具备良好的可移植性。
批量处理与无分支遍历：隐藏指令延迟
除了向量化之外，PlanB 的高性能还得益于两项互补的优化技术：批量处理（batching）和无分支遍历（branch-free traversal）。现代 CPU 的 SIMD 指令具有多周期延迟（例如 vpcmpnltuq 的延迟约为 3 到 4 个周期），在单次查找模型下，CPU 在发射比较指令后必须 stall 等待结果才能执行后续指令，SIMD 单元的利用率极低。PlanB 将数十个乃至上百个目标地址组成一个批次（batch）批量发送：CPU 首先对批次中的所有地址执行第一层的向量比较，生成第一层的结果掩码；随后在等待这些结果可用期间，CPU 已经开始并行执行第二批地址的第一层比较。这种流水线化的执行方式使得不同地址的查找指令在时间维度上交错重叠，SIMD 单元在每个周期都有工作可做，指令级并行度（ILP）得到充分释放，宏观上实现对单次查找延迟的摊销。
无分支遍历则是对节点内搜索逻辑的彻底重写。传统 B+ 树遍历需要在每个节点内部执行一个二分搜索，通常使用一系列 if-else 条件判断来定位正确的子节点。当输入流量不可预测时，这些条件分支的预测准确率显著下降，每次分支失败可能导致 10 到 20 个周期的性能损失。PlanB 用向量比较 + popcnt 取代所有条件分支：比较结果直接生成数值化的掩码，掩码的人口计数直接产生子节点索引，整个过程没有任何条件跳转。代码层面的循环也通过编译器选项进行完全展开（full unrolling），因为树的深度固定且较浅（典型值 6 到 7 层），展开后的指令序列是一条笔直的执行路径，CPU 的乱序执行引擎可以在此路径上自由调度指令，最大限度隐藏内存访问延迟。
动态路由更新：批量重建与原子切换
实际网络中的路由表并非静态，边界网关协议（BGP）持续更新路由信息。PlanB 采用批量重建与原子切换（rebuild-and-swap）策略处理动态更新：当收到一批前缀变更（插入、删除或修改）时，系统不在原地修改已有的线性化 B+ 树，而是基于更新后的完整前缀集合重新执行一次全量构建 —— 包括区间转换、区间划分和树结构构造 —— 生成一个全新的树结构。新树构建完成后，通过一次原子指针交换将查找操作指向新树，正在进行中的查找继续使用旧树直至完成，之后旧树可被安全释放。这种设计保证了查找路径上完全无需加锁，没有任何同步原语成为性能瓶颈，查找吞吐量不受任何更新活动的影响。代价是更新期间需要额外的内存空间来同时容纳新旧两棵树，但由于 PlanB 的树结构极其紧凑（每条前缀约 18 字节），这一开销在实践中完全可接受。
性能验证与工程部署要点
根据 PlanB 论文在两套硬件平台上的实测数据，在配备 24 核 Intel Xeon 8331C（3.0 GHz，36 MB L3 缓存）的服务器上，单核查找速度为 191 到 197 MLPS，12 核聚合达到 4.6 BLPS；在 AMD Ryzen 9 370HX（Zen5 架构）移动处理器上，单核峰值达到 374 到 393 MLPS，12 核聚合达到 3.4 BLPS。相较于当前最先进的软件方案 PopTrie、CP-Trie、Neurotrie 和 HBS，PlanB 在真实 IPv6 路由表（RIPE 和 RouteViews 数据集）上的提速比为 1.6 倍到 14 倍，内存占用降低 56% 到 92%。特别值得注意的是，即使在完全随机的流量模式下，PlanB 的性能几乎保持不变，尾延迟始终被严格控制在树深度决定的固定范围内，这对于应对突发流量和潜在的安全威胁具有重要意义。
对于希望在自有软件路由器中复现这一成果的团队，以下工程参数值得关注：节点大小应固定为缓存行倍数（64 字节或 128 字节），关键字数量按 (cache_line_size /key_size) - 1 计算；向量化搜索务必使用编译器 intrinsic（而非内联汇编），以保证编译器能够进行跨函数的优化和调度；批量大小的选择应在 32 到 128 之间调优，具体取决于 CPU 的微架构和 L3 缓存带宽；多核部署时应将 LPM 线程固定在同一 CCX/CCD 共享 L3 缓存的核组内，避免跨 NUMA 节点的缓存一致性流量。路由表加载后的首次查找前应主动执行一次硬件预取（_mm_prefetch），将根节点和第一层节点加载到 L1 缓存，避免冷启动时的抖动。
资料来源：PlanB 论文（arXiv:2604.14650）及阿里巴巴 NICE 实验室开源实现（https://github.com/nicexlab/planb）。