360内部业务线提出需要整合公司的nat网关，因为这个网关功能和虚拟化的snat网关功能大部分重叠，再加上netops对网络流量的调整使得原来的nat网关不再需要考虑bypass流量，这就使得原有对bypass流量的优化全部落空，剩下的正常nat转发功能在数据平面和虚拟化的snat网关功能高度重叠，因此我们需要把这两个网关合并为一个。

nat网关最核心的就是规则匹配，根据五元组判断流量需不需要做nat，替换的地址是什么，所以规则匹配效率从很大程度上会影响到网关的转发性能。虚拟化snat网关和ops的nat网关有一个比较重要的区别，虚拟化snat网关面对的是vpc网络，它需要处理的规则量是可预估的，规模也是有限的，但ops的nat网关面对的是整个公司所有的流量，它需要配置的放行规则是不可预估的，规模也是不可预期的。这就使得在虚拟化网络下的snat性能没问题的算法在ops的环境下会出现质的降低。除此之外，vpc的流量镜像也面临相同的问题，流量镜像的匹配规则也是这样通过五元组的网段范围来进行匹配，这个算法同样重要。因此我们需要有更好的方案。

二、方案

云上流量镜像是2024年开发的最后一个完整的功能模块，它分为数据平面和控制平面的处理，其中控制平面由neutron，ultron分别负责处理。数据平面由计算节点和snat网关共同处理。

控制平面由于是人工手动操作级别，因此它只需要正确，基本不关注性能问题，但是数据平面是和数据转发相关，性能问题尤其重要，所以我们优化主要关注于怎么做数据平面的优化。

首先我们需要明确数据平面的处理流程是如何的，这样才能看出哪里最为关键。（引用一下流量镜像的流程图如下图）

neutron以及左侧部分都属于控制平面的流程，负责下发规则配置信息，计算节点以及nat网关属于数据平面，负责数据报文的过滤和转发，整体其实流程逻辑并不复杂。

我们可以认为计算节点侧的配置，也就是neutron agent下发的这个配置，它的作用相当于一个开关，常规流量从计算节点上经过封装以后都是用udp的4789端口进行传输，只有agent下发配置以后才会开始把计算节点源的流量做一个镜像流量并且通过4790端口进行传输，这一步在整个流程中是必须，并且属于开关类控制，不会影响数据平面的处理性能。

因为vpc内转发overlay的流量全部都是通过4789端口进行的，所以网关侧处理流量的时候只会处理4789端口的流量，所有转发的策略规则也是针对的4789端口，那么对流量镜像的4790端口的数据就需要进行特别处理了。也就是下图中的这一小块：

这里面的vni提取，封装vxlan都属于内存访问动作，并且是必须的，没有可优化点，剩下的就是策略查找了。流量镜像的策略是基于五元组的规则，并且源IP和目的IP全部都参与匹配，并且支持网段，这样就使得哈希表失去作用了，因为没办法通过一次哈希就确定出一个IP地址是属于哪个网段，最简单的比如192.168.0.20，就没办法知道它属于192.168.0.0/16还是192.168.0.0/24。因此，对于这样的规则，我们目前是采用线性表进行顺序查找的，大部分的防火墙规则也都是采用顺序查找。顺序查找有个最大的优点就是实现简单，并且在规则数量不多的情况下性能还挺高，但如果规则数量多的话，我们都知道线性表的查找长度是N/2，查找算法的时间复杂度是O(n)，属于比较低效的查找算法。所以基本可以确定这个规则匹配算法就是最有价值的优化点了。

当我们看到一个这样子的规则：192.168.0.0/24 action: forward，我们会联想到什么？

172.16.0.0/18 dev eth0 proto kernel scope link src 172.16.12.7 metric 100

跟这个看起来是不是觉得很亲切？对，咱们内核的路由表查找就是面对这样的规则，每一个路由规则都是网段对应的下一跳地址，跟我们的过滤规则是一样的，那么内核是怎么查找路由的呢？两种：

1. 3.10之前的内核普遍用的是hash表，不过它的哈希表有个特点，它是根据掩码位数进行的网段哈希，即根据掩码位数用网络地址进行哈希，匹配的时候按照掩码从大到小的顺序，先把目的地址根据掩码算出网络地址，然后查找哈希表。

2. 3.10之后的内核引入了trie树（前缀匹配树）

算法这里就不专门展开了，我这里就根据这两种思路提出两个优化方案：

第一个：使用哈希表分级搜索

基于内核路由的哈希查找算法而来，由于地址掩码有32种可能，极端情况下（不命中）一个IP地址需要做32次哈希查找，显然有点儿多了，实际使用中其实掩码长度可能不需要那么多（大量的使用应该集中在22-26这些），因此可以将其限定为某些特定的掩码位数，比如采用16，18，22，24，25，26，这样在不命中规则的情况下只需要查找6次。

这个方案的优点就是实现简单，但因为限定了掩码位数，失去了一定的灵活性。

插入规则的时候按照网络地址的哈希作为key去插入到对应的哈希表，当得到一个需要匹配的IP地址，先用这个IP地址与掩码位数计算出网络地址再计算哈希，掩码长度按照从长到短的顺序进行，这样一旦出现比如192.168.1.0/22和192.168.1.0/24这样的规则同时存在的话能保证后一个先命中。

在使用中可以优化一下掩码长度，比如31，30这个长度的掩码实际上可用IP地址分别是2个和4个，如果除去网关和广播地址的话总共实际上就2个（当然有的场景是不需要去掉网关和广播地址的），这种我们可以直接把他们并入32位掩码的哈希表中；低于8位的基本不会被用到，尽可能减少哈希表的数量。

第二个：使用前缀匹配算法

内核使用的trie是一个前缀匹配树，这提醒我们可以使用前缀匹配算法来进行查找。

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。对于“inner”来说，在这个前缀匹配树中将会匹配上i，in，inn三个规则，如果限定为只要最长的（最长前缀匹配），那就只会匹配上inn这一个了。对于一个IP地址来说比如：192.168.0.7，它在内存中存储为0xc0a80007，假如看作二进制那它就是：1100 0000 1010 1000 0000 0000 0000 0111，如果有两个规则是192.168.0.0/24以及192.168.0.0/22，那么这两个规则对应的二进制就是：1100 0000 1010 1000 0000 0000和1100 0000 1010 1000 0000 00，那么192.168.0.7将会命中1100 0000 1010 1000 0000 00000000 0111，也就是192.168.0.0/24这个规则，这正是我们想要的。

从原理上看，这个算法理论上同时具有最好的查找效率和空间效率，是我们这个场景下的最优选择，但是由于树型结构（还不是二叉树）是一个较为复杂的数据结构，设计稍有不慎就会产生反效果，所以要用好这个算法难度也是最大的。

由于我们网关是基于dpdk进行开发的，dpdk自身就有支持前缀匹配算法的库LPM（Longest Prefix Match，最长前缀匹配），比较适合网关的架构。不过dpdk的LPM并不能直接拿来用，因为dpdk的LPM查找是根据目的地址找到下一跳，它的叶子节点是固定的u32字节的IP地址，而我们的过滤规则是需要通过源地址和目的地址同时来查找，并且找到的不是IP地址，而是一组目标信息，这就需要对如何利用这个算法进行一番设计了。

三、总结

归纳以上我们倾向于使用前缀匹配这个方案，它的优点就是可以支持规则中源网段和目的网段的掩码长度不受限制，灵活性很强，并且前缀匹配查找理论上具有最少的内存访问次数，属于高性能的查找算法，再加上dpdk性能优化的加持，理论上应该可以得到最高的查找性能。缺点是dpdk提供的原有最长前缀匹配是用来进行路由查找的，并不能直接用于当前规则匹配，所以要想应用到nat的规则查找实现起来会比较复杂。

而使用分级hash的方案实现简单，尤其在规则数量比较少的场景下哈希冲突可能性减小，查找长度就会更加降低，性能会更有优势。缺点是使用起来有限制。

这两种方案哪个更优，需要更多的实践案例。