资讯专栏INFORMATION COLUMN

Linux路由缓存的前世今生

jonh_felix / 1219人阅读

摘要:本文就来谈谈路由缓存的前世今生。路由缓存就是基于这种思想的软件实现。总结起来就是,版本以前的这种路由缓存在地址稳定时的确可能提高性能。总结版本将查询之前的路由缓存移除了,取而代之的是下一跳缓存。

3.6版本一定算得上是Linux网络子系统中一个特别的版本, 这个版本(补丁patch)移除了查找FIB之前的缓存查找。本文就来谈谈路由缓存的前世今生。

几个基本概念

为了让本文的阅读曲线更加平缓我决定还是将本文涉及的一些术语作个说明。

路由:将skb按照规则送到该去的地方,这个地方可能是本机,也可能是局域网中的其他主机,或者更远的主机。从这个角度来说,它一个动词。那么路由发生在哪个时候呢? 我们知道路由是网络层(L3)的概念,接收方向,它需要决定收到的skb是应该上送本机还是转发,发送方向,它需要决定skb从哪个网络接口发出。下图原本是描述Netfilter在内核中的钩子位置的,但我觉得用来说明路由的位置也是比较合适的。

与此同时,路由也可以特指上面所说的规则,这是名词的用法。路由从哪来? 一般来说有三个来源:1. 用户主动配置;2.内核生成; 3. 其他一些路由协议进程(OSPFBGP)生成。普通主机上可能没有最后一种,所以,为了理解方便,你可以将路由就理解为你用route命令看到的内容。

[root@tristan]# route -n
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
192.168.99.0    0.0.0.0         255.255.255.0   U     0      0        0 eth0
192.168.98.42   192.168.99.1    255.255.255.255 UGH   0      0        0 eth0
127.0.0.0       0.0.0.0         255.0.0.0       U     0      0        0 lo
0.0.0.0         192.168.99.254  0.0.0.0         UG    0      0        0 eth0

FIB:全称是(Forwarding Information Base),翻译过来就是转发信息表FIB是内核skb路由过程的数据库,或者说内核会将路由翻译成FIB中的表项。我们习惯说的查询路由,对于内核来说,应该叫查询FIB

3.6版本以前的路由缓存

缓存无处不在。现代计算机系统中,CacheCPU与内存间存在一种容量较小但速度很高的存储器,用来存放CPU刚使用过或最近使用的数据。路由缓存就是基于这种思想的软件实现。内核查询FIB前,固定先查询cache中的记录,如果cache命中(hit),那就直接用就好了,不必查询FIB。如果没有命中(miss), 就回过头来查询FIB,最终将结果保存到cache,以便下次不再需要需要查询FIB

缓存是精确匹配的, 每一条缓存表项记录了匹配的源地址和目的地址、接收发送的dev,以及与内核邻居系统(L2层)的联系(negghbour)
FIB中存储的也就是路由信息,它常常是范围匹配的,比如像ip route 1.2.3.0/24 dev eth0这样的网段路由。

下图是3.6版本以前的本机发送skb的路由过程....

看上去的确可能能提高性能! 只要cache命中率足够高。要获得高的cache命中率有以下两个途径:1. 存储更多的表项; 2.存储更容易命中的表项

缓存中存放的表项越多,那么目标报文与表项匹配的可能性越大。但是cache又不能无限制地增大,cache本身占用内存是一回事,更重要的是越多的表项会导致查询cache本身变慢。使用cache的目的是为了加速,如果不能加速,那要这劳什子有有什么用呢?

前面说了,cache的特点决定了它只能做精确匹配。也就是说,只有目标数据报文与cache中的表项完全一致,才算匹配成功。最简单的cache查找过程应该是下面这样:遍历cache中的所有表项,直到遇到匹配的表项跳出循环。

foreach entry in cache:
then
    if entry match skb
    then
        /* 条件匹配,将缓存表项中记录的结果设置到skb上 */
        skb->dst <= entry->dst
        return
    endif
end

显然,cache表项的数目越多,那么查找的过程就越长! 当然,内核不会这么蠢地将所有cache拉成一个线,而是使用hash桶,看上去应该是这么一个结构。

内核首先根据目标报文的一些特征计算hash,找到对应的hash冲突链表。在链表上一个一个地进行比较遍历。

为了避免cache表项过多,内核还会在一定时机下清除过期的表项。有两个这样的时机,其一是添加新的表项时,如果冲突链的表项过多,就删除一条已有的表项;其二是内核会启动一个专门的定时器周期性地老化一些表项.

获得更高的cache命中率的第二个途径是存储更容易命中的表项,什么是更容易命中的呢? 那就是真正有效的报文。遗憾的是,内核一点也不聪明:只要输入路由系统的报文不来离谱,它就会生成新的缓存表项。坏人正好可以利用这一点,不停地向主机发送垃圾报文,内核因此会不停地刷新cache。这样每个skb都会先在cache表中进行搜索,再查询FIB表,最后再创建新的cache表项,插入到cache表。这个过程中还会涉及为每一个新创建的cache表项绑定邻居,这又要查询一次ARP表。

要知道,一台主机上的路由表项可能有很多,特别是对于网络交换设备,由OSPF*BGP等路由协议动态下发的表项有上万条是很正常的事。而邻居节点却不可能达到这个数量。对于转发或者本机发送的skb来说,路由系统能帮它们找到下一跳邻居*就足够了。

总结起来就是,3.6版本以前的这种路由缓存在skb地址稳定时的确可能提高性能。但这种根据skb内容决定的性能却是不可预测和不稳定的。

3.6版本以后的下一跳缓存

正如前面所说,3.6版本移除了FIB查找前的路由缓存。这意味着每一个接收发送的skb现在都必须要进行FIB查找了。这样的好处是现在查找路由的代价变得稳定(consistent)了。

路由缓存完全消失了吗? 并没有!在3.6以后的版本, 你还可以在内核代码中看到dst_entry。这是因为,3.6版本实际上是将FIB查找缓存到了下一跳(fib_nh)结构上,也就是下一跳缓存

为什么需要缓存下一跳呢? 我们可以先来看下没有下一跳缓存的情况。以转发过程为例,相关的伪代码如下:

FORWARD:

fib_result = fib_lookup(skb)
dst_entry  = alloc_dst_entry(fib_result)
skb->dst = dst_entry;

skb->dst.output(skb)   
nexthop = rt_nexthop(skb->dst, ip_hdr(skb)->daddr)
neigh = ipv4_neigh_lookup(dev, nexthop)
dst_neigh_output(neigh,skb)
release_dst_entry(skb->dst)

内核利用FIB查询的结果申请dst_entry, 并设置到skb上,然后在发送过程中找到下一跳地址,继而查找到邻居结构(查询ARP),然后邻居系统将报文发送出去,最后释放dst_entry

下一跳缓存的作用就是尽量减少最初和最后的申请释放dst_entry,它将dst_entry缓存在下一跳结构(fib_nh)上。这和之前的路由缓存有什么区别吗? 很大的区别!之前的路由缓存是以源IP和目的IP为KEY,有千万种可能性,而现在是和下一跳绑定在一起,一台设备没有那么多下一跳的可能。这就是下一跳缓存的意义!

early demux

early demux是在skb接收方向的加速方案。如前面所说,在取消了FIB查询前的路由缓存后,每个skb应该都需要查询FIB。而early demux是基于一种思想:如果一个skb是本机某个应用程序的套接字需要的,那么我们可以将路由的结果缓存在内核套接字结构上,这样下次同样的报文(四元组)到达后,我们可以在FIB查询前就将报文提交给上层,也就是提前分流(early demux)

总结

3.6版本将FIB查询之前的路由缓存移除了,取而代之的是下一跳缓存。

REF

Route cache removed
IPV4 route cache removed from >= 3.6 linux kernel
remove routing cache
Linux3.5内核以后的路由下一跳缓存

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/110630.html

相关文章

  • Web技术前世今生(三)

    摘要:前言我是,如果你还不认识我,不妨先看看技术的前世今生一,以及技术的前世今生二前面我提过,我的大哥有一个叫的死党,这家伙有事没事经常上我们家串门。时间来到了年,在那前后发生了两件事让我印象深刻。传送门技术的前世今生一技术的前世今生二 前言:我是JavaScript,如果你还不认识我,不妨先看看《Web技术的前世今生(一)》,以及《Web技术的前世今生(二)》 前面我提过,我的大哥HTML...

    Wuv1Up 评论0 收藏0
  • Docker Swarm前世今生

    摘要:当然此时的局限性较大,比如没有副本和负载均衡的概念,这导致服务无法高可用当然也更不存在什么服务网络管理和跨节点数据存储这些东西没有服务模型集群中服务间关系和启动顺序编排也很复杂于是就有了下面的的诞生。 showImg(https://segmentfault.com/img/remote/1460000015317037?w=1885&h=1153); 概述 在我的《Docker S...

    lemon 评论0 收藏0
  • kube-dns前世今生

    摘要:通过监视资源的变化,并根据的信息生成记录写入到中。是唯一保留的容器,依然提供健康检查。操作会获取最新的全量资源与本地状态进行比较来产生通知,可以避免网络原因导致的丢失通知的情况。最后一个参数用来设置处理事件的回调。 上一期我们以1.2版本为背景,介绍了K8S的服务发现和kube-dns插件的相关内容。有了上一期内容作为基础,这期了解最新版本的kube-dns就会容易很多。 本文主要对比...

    Lin_R 评论0 收藏0
  • HTTP 前世今生:一次性搞懂 HTTP、HTTPS、SPDY、HTTP2

    摘要:的最早版本诞生在年,这个最早版本和现在比起来极其简单,没有头,没有状态码,甚至版本号也没有,后来它的版本号才被定为来和其他版本的区分。由于没有状态码和错误代码,如果服务器处理的时候发生错误,只会传回一个特殊的包含问题描述信息的文件。 作为互联网通信协议的一员老将,HTTP 协议走到今天已经经历了三次版本的变动,现在最新的版本是 HTTP2.0,相信大家早已耳熟能详。今天就给大家好好介绍...

    avwu 评论0 收藏0
  • Web技术前世今生(二)

    摘要:前言我是,如果你还不认识我,不妨先看看技术的前世今生一平静的生活已经有一段日子了。传送门技术的前世今生一技术的前世今生三 前言:我是JavaScript,如果你还不认识我,不妨先看看《Web技术的前世今生(一)》 平静的生活已经有一段日子了。 这一天,HTML大哥面露不悦地走过来问我: Js,你是打算和我们分家吗? 大哥,您这说的哪里话,我什么地方做的不对么?我一脸茫然地回答道。 哼,...

    Stardustsky 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<