4、路由表与转发性能：路由查找算法（哈希、Trie树）、硬件卸载（DPU/智能网卡）
路由转发，说白了就是查表。查得快，转发就快；查得慢，整个网络都在等你。
我早年调过一台核心路由器，CPU 跑满 100%，转发却只有线速的 30%。查了半天，问题就出在路由表查找上——表太大，算法又没选对。从那以后，我对路由查找算法就特别敏感。
这一节，咱们就聊聊路由表怎么查最快，以及硬件怎么帮你把这事儿卸掉。
4.1 路由查找的核心矛盾
路由表里存的是啥？说白了就是一堆「前缀 + 下一跳」的映射。比如：
192.168.1.0/24 → 下一跳 10.0.0.1
192.168.0.0/16 → 下一跳 10.0.0.2
0.0.0.0/0 → 下一跳 10.0.0.254查表时，你得拿目标 IP 去匹配这些前缀。注意，是最长前缀匹配——不是随便匹配一个就行，得找最精确的那个。
举个例子：目标 IP 是 192.168.1.55，它既匹配 /24 也匹配 /16，但 /24 更精确，所以走 10.0.0.1。
这个「最长前缀匹配」就是性能瓶颈的根源。你想想看，如果只是精确匹配，哈希表一把梭就完了。但前缀匹配不行，你得在树里一层层往下找。
核心矛盾：路由表越大，前缀越长，查找耗时就越长。高并发下，这个耗时会被放大成千上万倍。
4.2 哈希算法：最快，但有条件
哈希表查找是 O(1) 的，理论上最快。但路由查找里，哈希只能解决精确匹配的场景。
什么时候用？比如 MPLS 标签交换、VXLAN 隧道端点，这些场景下查的是固定长度的标签或 IP，不需要前缀匹配。
我见过一个数据中心网关，内部用哈希表做 VXLAN 解封装，每秒处理 2000 万条流，CPU 占用不到 5%。哈希表在这里就是神器。
但哈希表有个坑——冲突。冲突多了，O(1) 就退化成 O(n)。
避坑指南：我曾经在一个项目里用简单的取模哈希，结果流量一上来，冲突率飙到 30%，转发延迟直接翻倍。后来换成 CRC16 哈希 + 链式扩展，冲突率降到 1% 以下。记住，哈希函数选不好，性能全白搞。
哈希表的适用场景总结一下：
| 场景 | 是否适合哈希 | 原因 |
|---|---|---|
| MPLS 标签查找 | ✅ 非常适合 | 固定长度，精确匹配 |
| VXLAN VNI 查找 | ✅ 非常适合 | 固定长度，精确匹配 |
| IPv4 最长前缀匹配 | ❌ 不适合 | 需要前缀匹配，哈希搞不定 |
| IPv6 路由查找 | ❌ 不适合 | 前缀长度可变，哈希无法处理 |
4.3 Trie 树：最长前缀匹配的经典解法
哈希搞不定的前缀匹配，Trie 树（字典树）来搞定。
Trie 树的基本思路很简单：把 IP 地址看成二进制串，每一位决定走左子树还是右子树。从根节点一路走到叶子节点，路径上经过的节点就是匹配到的前缀。
但普通的 Trie 树有个问题——太占内存。IPv4 地址 32 位，如果每个位都建一个节点，那内存开销是天文数字。
所以实际工程里用的是压缩 Trie 树，比如：
- PATRICIA 树：跳过连续的相同位，只存分叉点。
- LC-Trie：层级压缩，把多级合并成一级。
- Tree Bitmap：用位图表示子节点是否存在，内存更紧凑。
我调过一台老牌路由器的转发面，它用的就是 Tree Bitmap。当时表项 50 万条，查找延迟稳定在 200ns 以内。说实话，这个表现让我挺意外的——软件能做到这个水平，已经很接近硬件了。
个人经验：选 Trie 树变体时，别光看查找速度，还得看更新性能。路由表是动态的，每秒可能有几千条更新。有些 Trie 树查找快，但更新时要重建整棵树，那就完蛋了。我建议优先选 支持增量更新 的变体，比如 Tree Bitmap 或 LC-Trie。
几种常见 Trie 树变体的对比：
| 算法 | 查找速度 | 内存占用 | 更新性能 | 适用场景 |
|---|---|---|---|---|
| 普通 Trie | 慢 | 极高 | 差 | 教学演示 |
| PATRICIA | 中等 | 低 | 中等 | 小型路由表 |
| LC-Trie | 快 | 中等 | 好 | 中等规模路由表 |
| Tree Bitmap | 很快 | 低 | 好 | 大规模路由表（50万+） |
4.4 硬件卸载：把查找交给专用芯片
软件再快，也快不过硬件。当路由表超过 100 万条，或者转发速率要求 100Gbps 以上时，CPU 就扛不住了。
这时候就得硬件卸载——把路由查找从 CPU 搬到专用硬件上。
4.4.1 DPU（数据处理单元）
DPU 是最近几年火起来的东西。它本质上是一个专门处理网络数据的 SoC，里面集成了多核 ARM CPU、硬件加速引擎、高速网络接口。
DPU 怎么优化路由查找？
- 硬件哈希表：DPU 内部有专用的哈希引擎，冲突处理由硬件完成，延迟极低。
- TCAM（三态内容寻址存储器）：这是路由查找的终极武器。TCAM 可以在一个时钟周期内完成最长前缀匹配。但 TCAM 贵、功耗高、容量有限。
- 流水线架构：DPU 把路由查找拆成多级流水线，每个时钟周期处理一个查找请求，吞吐量极高。
我记得有个客户做 5G 用户面网关，流量峰值 400Gbps。他们用了一款 DPU，把 GTP-U 隧道查找和路由转发全卸载到硬件上，CPU 占用从 80% 降到了 5%。
关键点：DPU 不是万能的。它适合规则明确、重复性高的查找任务。如果路由表频繁变化，或者查找逻辑很复杂，DPU 的灵活性就不如 CPU。
4.4.2 智能网卡
智能网卡是 DPU 的「轻量版」。它通常插在服务器 PCIe 槽上，内置 FPGA 或 ASIC，可以卸载部分网络处理。
智能网卡在路由查找上的典型用法：
- 流表卸载：把常用的路由条目缓存到网卡硬件表中，大部分流量直接在网卡上转发，不经过 CPU。
- 隧道封装/解封装：VXLAN、GRE 等隧道处理，智能网卡可以硬件加速。
- 负载均衡：基于哈希的负载均衡算法，智能网卡可以在线速下完成。
我建议你在选型时注意一点：智能网卡的表项容量。有些卡只能存几千条流表，超过这个数就会回退到 CPU 处理，性能直接崩掉。
避坑指南：我曾经在一个云平台项目里用了某款智能网卡，标称支持 10 万条流表。结果上线后发现，实际稳定运行的条目数只有 3 万条——超过这个数，网卡内部哈希冲突率飙升，转发延迟从 5μs 涨到 50μs。所以，永远不要相信标称值，一定要做压力测试。
4.5 知识体系总览
下面这张图把路由查找的几种方案和它们的关系梳理了一下。你可以看到，从软件到硬件，从哈希到 Trie 树，再到 DPU 和智能网卡，每个方案都有自己的位置。
4.6 选型建议
说了这么多，到底怎么选？我个人的经验是：
- 路由表 < 1 万条：软件 Trie 树就够了，Tree Bitmap 或 LC-Trie 都行。
- 路由表 1 万 ~ 50 万条：可以考虑智能网卡做流表卸载，把热条目卸载到硬件。
- 路由表 > 50 万条：上 DPU 或专用路由器芯片，TCAM 或硬件哈希是必须的。
- 转发速率 > 200Gbps：别想了，直接上硬件卸载。软件不可能做到。
嗯，这里要注意：选型不是一锤子买卖。网络流量是动态的，路由表会增长，业务模型会变化。我建议你预留 30% 的性能余量，别把硬件跑到极限。
路由查找这块，说白了就是「空间换时间，硬件换性能」。没有银弹，只有最适合你场景的方案。