Linux3.5内核以后的路由下一跳缓存

简介:

在Linux3.5版本(包括)之前,存在一个路由cache,这个路由cache的初衷是美好的,但是现实往往是令人遗憾的。以下是陈列得出的两个问题:
1.面临针对hash算法的ddos问题(描述该问题的文章已经汗牛充栋,不再赘述);
2.缓存出口设备是p2p设备的路由项会降低性能。
这 些问题本质上是由于路由cache的查找方式和路由表的查找方式互不相容引起的。路由cache必须是精确的元组匹配,因此它必须设计成一维的hash 表,而路由表查找算法是最前前缀匹配,因此它可以是多维的。路由查找最终会找到路由项,在不考虑策略路由的前提下,我们来看一下把出口设备为p2p设备的 路由项塞进路由cache是多么的没有意义。

        p2p设备的邻居集合里只有一个下一跳,那就是它的对端,因此对于p2p设备,甚至都不需要进行邻居绑定的过程!然而如果将这类路由塞进路由cache的 话,将会占据巨量的内存,试想如果有10w个IP地址需要通信,源IP集合中同样有10w个IP地址,将有可能会建立100w条路由cache项,极端一 点,如果此时系统中只有不多的几条路由表项的话,查找路由表的开销可能会反而低于查找路由cache的开销,特别地,如果路由结果是p2p设备,事实上只 要想办法cache这唯一的一个条目即可。这就是一和多的区别,这次,我们发现不光零到一有意义,一到多也同样不可小觑。

        如果系统中有一块以太网卡eth0,由于同一网段会有多个邻居,不同的目标IP地址,其下一跳可能会有所不同,我们不得不cache每一个与eth0相关 的路由项,然后针对每一个数据包进行精确匹配,然而如果系统中有一块p2p网卡,它的邻居只有一个,对于点对点设备而言,其对端逻辑上只有一个设备,它是 唯一的且确定的,它是该点对点设备的邻居集合中的唯一一个邻居,因此事实上无需进行邻居绑定过程,只要从点对点设备将数据包发出,该数据包就一定会到达唯 一的对端,在这种情况下,如果我们还cache每一个与该p2p网卡相关的路由项,意义就不大了,然而,对于Linux的路由cache机制而言,这是无 法做的的,因为在查找路由cache以及查找路由表之前,我们无从知道这个数据包就是最终要从一个p2p网卡发送出去的。

        一个解决方案是,如果查找路由表的结果表明其出口设备是p2p设备,则设置一个NOCACHE标志,表示不cache它,待到数据包发送完毕即释放,我想 这个实现是简单而明了的,本来去年9月份想实现掉它,也是为了我们的一个网关产品可以提高性能,但是后面我离职了,此事也就不了了之,直到最近,我再次面 临了此问题。然而我有了更好的建议,那就是升级内核到3.6+,不过这是后话,事实上,如果你必须维护基于低版本内核的老产品的话,修改代码就是避不开 的,幸运的是,不管是老公司,还是新公司,我与2.6.32版本的代码打交道已经6年了。

        扩大点说,路由查找这东西确实很尴尬,可以肯定,一台设备上可能会有数十万条的路由,然而与其相连的邻居集合内的节点数却可以用一个字节来表示,而且大多 数节点的邻居可能只有不超过10个!我们消耗了大量的精力,什么cache查询,什么最长前缀匹配,最终就是为了在数十万数量级的大海中捞出几根针,所以 说,这一直都是一个比较有挑战性的领域,与TCP加速相比,这个领域更加闭环,它不受其它影响,只有算法本身影响它!事实上,不光p2p设备,就连 ethX设备,结局也是悲哀的,配置几十条路由,最终的下一跳可能只有五六个,p2p设备只是更加极端一些罢了,对于p2p设备,我们一般这么写路由即 可:
route add -host/net a.b.c.d/e dev tunlX
然而对于ethX设备而言,一般来说我们必须写路由:
route add -host/net a.b.c.d/e gw A.B.C.D 
也 就是说,p2p设备直接告知了数据包从设备发出去即可,然而对于ethX设备(或者所有的广播网络设备以及NBMA设备),必须进行地址解析或者下一跳解 析才会知道从哪里发出去。不光如此,路由cache还会对邻居子系统造成影响,简单的说,就是路由项引用邻居,路由项释放之前,邻居不能被释放,即便 p2p设备不需要邻居解析,在代码层面也必须特殊处理,不幸的是,Linux内核中并没有看到这种特殊处理,p2p设备的路由项依然会塞进路由 cache。

        以上就是路由查找的困境。困境在于多对一或者多对少的映射过程,这种情况下,营造一个精确匹配的cache可能使结局更加悲哀,因此,用一种统一的方式进 行调优可能更加符合人之常情。Linux3.6以后,去除了路由cache的支持,所有的数据包要想发送出去,必须查找路由表!如今的过程可能会变成以下 的逻辑:

dst=lookup_fib_table(skb);
dst_nexthop=alloc_entry(dst);
neigh=bind_neigh(dst_nexthop);
neigh.output(skb);
release_entry(dst_nexthop);

这是一个完美的过程,然而在协议栈的实现层面,出现了新的问题,即 alloc/release会带来巨大的内存抖动,我们知道,内存分配与释放是一个必须要在CPU外部完成的事务,它的开销是巨大的,虽然在Linux中 有slab cache,但是我们同样也知道,cache是分层的。事实上,Linux在3.6以后,实现了新的路由cache,不再缓存一个路由项,因为那需要 skb的元组精确匹配,而是缓存下一跳,找到这个cache必须经过lookup_fib_table这个例程。

        这是个创举,因为缓存的东西是唯一的,除非发生一些例外!这就破解了解决多对一以及多对少的问题,在找到缓存之前,你必须先查找路由表,而查找完毕之后, 理论上你已经知道了下一跳,除非一些例外(再次重申!)这个新的下一跳缓存只是为了避免内存的分配/释放!伪代码如下:

dst=lookup_fib_table(skb);
dst_nexthop=lookup_nh_cache(dst);
if dst_nexthop == NULL;
then
    dst_nexthop=alloc_entry(dst);
    if dst_nexthop.cache == true;
    then
        insert_into_nh_cache(dst_nexthop);
    endif
endif
neigh=bind_neigh(dst_nexthop);
neigh.output(skb);
if dst_nexthop.cache == false
then
    release_entry(dst_nexthop);
endif

就这样,路由cache不再缓存整个路由项,而是缓存路由表查找结果的下一跳。

        鉴于一般而言,一个路由项只有一个下一跳,因此这个缓存是极其有意义的。这意味着,在大多数时候,当路由查找的结果是一个确定的dst时,其下一跳缓存会 命中,此时便不再需要重新分配新的dst_nexthop结构体,而是直接使用缓存中的即可,如果很不幸,没有命中,那么重新分配一个 dst_nexthop,将其尽可能地插入到下一跳缓存,如果再次很不幸,没有成功插入,那么设置NOCACHE标志,这意味着该dst_nexthop 使用完毕后将会被直接释放。

        上述段落说明的是下一跳缓存命中的情况,那么在什么情况下会不命中呢,这很简单,无非就是在上述的lookup_nh_cache例程中返回NULL的时 候,有不多的几种情况会导致其发生,比如某种原因将既有的路由项删除或者更新等。这个我随后会通过一个p2p虚拟网卡mtu问题给予说明,在此之前,我还 要阐述另外一种常见的情形,那就是重定向路由。

        所谓的重定向路由,它会更新本节点路由表的一个路由项条目,要注意的是,这个更新并不是永久的,而是临时的,所以Linux的做法并不是直接修改路由表,而是修改下一跳缓存!这个过程是异步的,伪代码如下:

# IP_OUT例程执行IP发送逻辑,它首先会查找标准路由表,然后在下一跳缓存中查找下一跳dst_nexthop,以决定是否重新分配一个新的dst_nexthop,除非你一开始指定NOCACHE标志,否则几乎都会在查找下一跳缓存失败进而创建新的dst_nexthop之后将其插入到下一跳缓存,以留给后续的数据包发送时使用,这样就避免了每次重新分配/释放新的内存空间。
func IP_OUT:
    dst=lookup_fib_table(skb);
    dst_nexthop = loopup_redirect_nh(skb.daddr, dst);
    if dst_nexthop == NULL;
    then
        dst_nexthop=lookup_nh_cache(dst);
    endif
    if dst_nexthop == NULL;
    then
        dst_nexthop=alloc_entry(dst);
        if dst_nexthop.cache == true;
        then
            insert_into_nh_cache(dst_nexthop);
        endif
    endif
    neigh=bind_neigh(dst_nexthop);
    neigh.output(skb);
    if dst_nexthop.cache == false
    then
        release_entry(dst_nexthop);
    endif
endfunc

# IP_ROUTE_REDIRECT例程将创建或者更新一个dst_nexthop,并将其插入到一个链表中,该链表由数据包的目标地址作为查找键。
func IP_ROUTE_REDIRECT:
    dst=lookup_fib_table(icmp.redirect.daddr);
    dst_nexthop = new_dst_nexthop(dst, icmp.redirect.newnexthop);
    insert_into_redirect_nh(dst_nexthop);
endfunc


以上就是3.6以后内核的下一跳缓存逻辑,值得注意,它并没有减少路由查找的开销,而是减少了内存分配/释放的开销!路由查找是绕不过去的,但是路由查找结果是路由项,它和下一跳结构体以及邻居结构体之间还有层次关系,其关系如下:
路由项-下一跳结构体-邻居项
一 个数据包在发送过程中,必须在路由查找结束后绑定一个下一跳结构体,然后绑定一个邻居,路由表只是一个静态表,数据通道没有权限修改它,它只是用来查找, 协议栈必须用查找到的路由项信息来构造一个下一跳结构体,这个时候就体现了缓存下一跳的重要性,因为它减少了构造的开销!

        最后,我们可以看一下效果,如果你只是看代码,那么当你看到input或者output路径中的rt_dst_alloc调用时,你可能会很灰心丧气,但是如果你使用下面的命令看一下实际结果:
watch -d -n 1 “cat /proc/net/stat/rt_cache”
的 时候,你就会发现,in_slow_tot和out_slow_tot两个字段的计数器增加十分缓慢,甚至停滞!这意味着绝大多数的数据包在接收和发送过 程中都命中了下一跳cache!如果你发现了异常,也就是说不是这种情况,它们中的其一或者两者增长的很快,那么可能是两方面的原因:
1.你的内核可能没有升级到足够高的版本
这意味着你的内核有bug,在3.10的最初版本中,RT_CACHE_STAT_INC(in_slow_tot);的调用是发生在下列代码之前的:

if (res.fi) {
    if (!itag) {
        rth = rcu_dereference(FIB_RES_NH(res).nh_rth_input);
        if (rt_cache_valid(rth)) {
            skb_dst_set_noref(skb, &rth->dst);
            err = 0;
            goto out;
        }
        do_cache = true;
    }
}

rth = rt_dst_alloc(net->loopback_dev,
           IN_DEV_CONF_GET(in_dev, NOPOLICY), false, do_cache);
...

也就是说它遗留了路由cache存在的年代的代码,错误的将下一跳缓存当成了路由cache!只需要将RT_CACHE_STAT_INC(in_slow_tot)移植到rt_dst_alloc之后即可。
2.你可能使用了p2p设备,但是并没有正确的设置MTU
我 们知道ipip隧道设备在Linux上是一个虚拟网卡设备,数据包要真正发送出去要经过重新封装一个IP头部的过程,如果最终是经由ethX发送数据,其 MTU默认是1500,如果ipip隧道设备的MTU也是1500或者小于1500减去必要头部开销的话,就到导致重新更新MTU的操作,而一个下一跳缓 存中包含MTU信息,如果MTU需要重新更新,就意味着下一跳缓存需要更新。

        在一般的物理设备中,这不是问题,因为往往在IP层发送数据前,MTU就是已经确知的,但是对于ipip隧道设备而言,在数据发送的时候,协议栈在实际往 隧道发送数据前并不知道最终数据包需要再次封装,因此也就对MTU过大导致数据无法发送这件事不知情,特别是遇到gso,tso这种情况,事情会更加复 杂。此时我们有两个解决方案:
1).适当调低ipip隧道的MTU值,保证即使经过再次封装,也不过长度过载。这样就不会导致重新更新MTU进而释放更新下一跳cache。
2).从代码入手!
根 据代码的rt_cache_valid来看,不要让下一跳缓存的标志变成DST_OBSOLETE_KILL即可,而这也是和MTU相关的,而在 __ip_rt_update_pmtu中,只要保证下一跳缓存的初始mtu不为0即可,这可以加入一个判断,在rt_dst_alloc之后,初始化 rth字段的时候:

if (dev_out->flags&(IFF_LOOPBACK|IFF_POINTOPOINT))
    rth->mtu = dev_out->mtu;
else
    rth->mtu = 0;

经过测试,效果良好!

BTW,和很多的安全协议一样,路由表项以及下一跳缓存也使用了版本号来管理其有效性,只有表项的ID和全局ID一致的时候,才代表该表项有效,这简化了刷新操作,当刷新发生的时候,只需要递增全局版本号ID即可。

        现在,可以总结一下了。在Linux3.6以后,路由cache被去除了,取而代之的是下一跳缓存,这里面有很多的蹊跷,比如有重定向路由的处理等... 这主要是有效减少了内存管理的开销而不是查找本身的开销。在此要说一下内存的开销和查找的开销。二者并不是一个层次的,内存的开销主要跟内存管理数据结构 以及体系结构有关,这是一个复杂的范畴,而查找的开销相对简单,只是跟算法的时间空间复杂度以及体系结构相关,然而为什么用查找的开销换内存的开销,这永 远是一个无解的哲学问题!


 本文转自 dog250 51CTO博客,原文链接:http://blog.51cto.com/dog250/1747887


相关文章
|
1月前
|
存储 Linux 数据处理
探索Linux操作系统的内核与文件系统
本文深入探讨了Linux操作系统的核心组件,包括其独特的内核结构和灵活的文件系统。文章首先概述了Linux内核的主要功能和架构,接着详细分析了文件系统的工作原理以及它如何支持数据存储和检索。通过比较不同的文件系统类型,本文旨在为读者提供一个关于如何根据特定需求选择合适文件系统的参考框架。
|
21天前
|
Linux API 调度
技术笔记:Linux内核跟踪和性能分析
技术笔记:Linux内核跟踪和性能分析
|
2月前
|
安全 算法 网络协议
探索Linux操作系统的内核管理
【5月更文挑战第31天】本文将深入探讨Linux操作系统的内核管理机制,包括其设计原则、主要组件以及它们如何协同工作以提供高效的系统性能。通过分析Linux内核的关键特性和功能,我们将揭示这一开源操作系统如何在各种计算环境中保持其稳定性和灵活性。
|
2月前
|
机器学习/深度学习 人工智能 负载均衡
深度解析:Linux内核调度策略的演变与优化
【5月更文挑战第30天】 随着计算技术的不断进步,操作系统的性能调优成为了提升计算机系统效率的关键。在众多操作系统中,Linux因其开源和高度可定制性而备受青睐。本文将深入剖析Linux操作系统的内核调度策略,追溯其历史演变过程,并重点探讨近年来为适应多核处理器和实时性要求而产生的调度策略优化。通过分析比较不同的调度算法,如CFS(完全公平调度器)、实时调度类和批处理作业的调度需求,本文旨在为系统管理员和开发者提供对Linux调度机制深层次理解,同时指出未来可能的发展趋势。
|
3天前
|
存储 缓存 网络协议
如何在 Linux 上刷新 DNS 缓存?
【7月更文挑战第14天】
8 0
如何在 Linux 上刷新 DNS 缓存?
|
7天前
|
Linux
查看linux内核版本
在Linux中查看内核版本可使用`uname -r`、`cat /proc/version`、`lsb_release -a`、`cat /etc/*release`、`dmesg | grep Linux`、`hostnamectl`、`kernrelease`(部分系统)、`rpm -q kernel`(RPM系统)或`dpkg -l linux-image-*`(Debian系)。
9 2
|
29天前
|
Linux
查看linux内核版本
在Linux中查看内核版本可使用`uname -r`、`cat /proc/version`、`lsb_release -a`(若安装LSB)、`/etc/*release`或`/etc/*version`文件、`dmesg | grep Linux`、`cat /sys/class/dmi/id/product_name`、`hostnamectl`、`kernrelease`(如果支持)、`rpm -q kernel`(RPM系统)和`dpkg -l linux-image-*`(Debian系统)。
32 4
|
1月前
|
安全 Linux 数据处理
探索Linux的kmod命令:管理内核模块的利器
`kmod`是Linux下管理内核模块的工具,用于加载、卸载和管理模块及其依赖。使用`kmod load`来加载模块,`kmod remove`卸载模块,`kmod list`查看已加载模块,`kmod alias`显示模块别名。注意需有root权限,且要考虑依赖关系和版本兼容性。最佳实践包括备份、查阅文档和使用额外的管理工具。
|
13天前
|
Linux 调度
部署03---Linux操作系统的诞生,Linux操作系统由系统的内核和系统的操作系统所组成
部署03---Linux操作系统的诞生,Linux操作系统由系统的内核和系统的操作系统所组成
|
17天前
|
缓存 JavaScript
vue 页面缓存 keep-alive(含配置清除页面缓存 exclude,局部缓存,动态缓存,路由控制缓存 $route.meta.keepAlive)
vue 页面缓存 keep-alive(含配置清除页面缓存 exclude,局部缓存,动态缓存,路由控制缓存 $route.meta.keepAlive)
15 0