3.6版本的Linux路由缓存，不得不说是Linux网络子系统的一个特殊版本。该版本（补丁）移除了FIB查找之前的缓存查找。这篇文章将谈谈路由缓存的前世今生。几个基本概念为了让本文的阅读曲线更加顺畅，我决定对本文涉及的一些术语进行解释。路由：将skb按照规则发送到它应该去的地方。这个地方可能是本机，也可能是局域网中的其他主机，或者更远的主机。从这个意义上说，它是一个动词。那么路由何时发生？我们知道路由是网络层（L3）的概念，接收方向，需要决定接收到的skb是发送给本机还是转发，发送方向，需要决定接收到哪个网络接口skb发送自。下图本来描述的是Netfilter在内核中的hook位置，但我觉得用route的位置来说明更合适。同时路由也可以具体参考上面说的规则，就是名词的用法。路由从哪里来？一般来说，来源有3个：1.用户主动配置；2.内核生成；3.其他路由协议进程（OSPF、BGP）的生成。最后一个在普通主机上可能是没有的，所以，为了方便理解，你可以把路由理解为你看到的route命令。[root@tristan]#route-nKernelIProutingtableDestinationGatewayGenmaskFlagsMetricRefUseIface192.168.99.00.0.0.0255.255.255.0U000eth0192.168.98.42192.168.99.1255.255.255.255UGH01200.0.00.0.0.0255.0.0.0U000lo0.0.0.0192.168.99.2540.0.0.0UG000eth0FIB：全称（ForwardingInformationBase），译为转发信息表。FIB是内核skb路由进程的数据库，或者内核会把路由翻译成FIB中的条目。我们习惯说的queryrouting，对于kernel来说，应该叫做queryFIB。3.6之前的路由缓存到处都有缓存。在现代计算机系统中，Cache是??介于CPU和内存之间的一种小型但高速的内存，用于存放CPU刚刚使用过或最近使用过的数据。路由缓存就是基于这种思想的软件实现。内核在查询FIB之前，总是先检查缓存中的记录。如果缓存命中（hit），可以直接使用，不需要查询FIB。如果没有命中（miss），则返回查询FIB，最后将结果保存到缓存中，这样下次就不用再查询FIB了。缓存是精确匹配的，每个缓存条目都记录了匹配的源地址和目的地址，dev的接收和发送，以及与内核邻居系统（L2层）的连接（negghbour）。FIB存放的是路由信息，通常是范围匹配，比如iproute1.2.3.0/24deveth0这样的网段路由。下图是3.6版本之前本机发送skb的路由流程。看来确实可以提升性能！只要缓存命中率足够高。有两种方法可以获得高缓存命中率：1.存储更多条目；2.存储更容易命中的条目。缓存中存储的条目越多，目标数据包匹配该条目的可能性就越大。性越大。但是，缓存不能无限增加。缓存本身占用内存是一回事。更重要的是，更多条目会减慢查询缓存本身的速度。使用缓存的目的是为了加快速度。如果不能加速，那么麻烦有什么用呢？前面说过，缓存的特性决定了它只能做精确匹配。也就是说，只有当目标数据包与缓存中的表项完全一致时，匹配才算成功。最简单的缓存查找过程应该是这样的：遍历缓存中的所有条目，直到遇到匹配的条目，然后跳出循环。foreachentryincache:thenifentrymatchskbthen/*条件匹配，将缓存项中记录的结果设置为skb*/skb->dst<=entry->dstreturnendifend显然缓存项越多越多，那么搜索过程会更长！当然内核不会那么傻的把所有的缓存都拉到一行，而是使用hashbuckets，看起来应该是这样的结构。内核首先根据目标消息的一些特征计算哈希值，找到对应的哈希冲突列表。在链表上逐一比较遍历。为了避免缓存项过多，内核也会在一定时间清除过期的项。这样的机会有两种，一种是在添加新条目时，如果冲突链中的条目太多，则删除一个现有的条目；另一种是内核会启动一个特殊的定时器来周期性老化一些条目。获得更高缓存命中率的第二种方法是存储更容易命中的条目。打什么比较容易？那才是真正有效的信息。不幸的是，内核一点也不聪明：只要进入路由系统的数据包不是离谱的，它就会生成新的缓存条目。坏人可以利用这一点并不断向主机发送垃圾消息，因此内核将不断刷新缓存。这样每个skb都会先在cache表中查找，然后查询FIB表，最后创建一个新的cacheentry插入到cache表中。这个过程还涉及为每个新创建的缓存条目绑定邻居，这需要再次查询ARP表。要知道一台主机上的路由表项可能很多，尤其是网络交换设备，通过OSPF*BGP等路由协议动态下发几万条路由表项是很正常的。但是邻居节点不可能达到这个数字。对于本地转发或发送的skbs，路由系统帮他们找到下一跳邻居*就够了。综上所述，这种3.6版本之前的路由缓存，在skb地址稳定的情况下，确实有可能提升性能。但是这种由skb内容决定的性能是不可预测的，不稳定的。Next-hopcache3.6版本后如前所述，3.6版本在FIB查找之前去除了路由缓存。这意味着每个接收和发送的skb现在都必须执行FIB查找。这样做的好处是现在寻找路线的成本是一致的。路由缓存完全没有了吗？没有！3.6以后的版本，在内核代码中也可以看到dst_entry。这是因为3.6版本实际上是缓存了FIB查找到下一跳（fib_nh）结构，也就是为什么下一跳缓存需要缓存下一跳？我们先来看下没有下一跳缓存的情况。以转发过程为例，相关伪代码如下：->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，有成千上万种可能，而现在是绑定下一跳，一个设备没有那么多下一跳的可能。这就是下一跳缓存的意义所在！earlydemuxearlydemux是skb接收方向的一种加速方案。上面说到FIB查询前取消路由缓存后，每个skb都需要查询FIB。早期的demux是基于一个想法：如果机器上某个应用的socket需要一个skb，那么我们可以把路由结果缓存到内核socket结构中，这样下次同样的消息（四次之后）tuple)到达，我们可以在FIB查询之前将消息提交给上层，即earlydemux。总结3.6版去掉了FIB查询前的路由缓存，取而代之的是下一跳缓存。REFRoutecacheremovedIPV4routecacheremovedfrom>=3.6linuxkernelremoveroutingcacheRoutingnext-hopcacheafterLinux3.5内核
