Linux协议栈查找算法优化随想

mal 2014-11-10

Linux的网络协议栈实现可谓精确却不失精巧,不必说Netfilter,单单说TC就够了,但是有几处硬伤,本文做一个不完备的记录,就当是随笔,不必当真。

0.查找的种类

Linux协议栈作为一个纯软件实现,保留了硬件接口,但是本文不涉及硬件。

在Linux的协议栈实现中,由于没有硬件电路的固化,查找算法是难免的,比如路由查找,邻居查找,conntrack查找,socket查找,不一而足。事实上,协议栈作为一个公共组织,为所有的数据包服务,如果一个数据包到达协议栈,处理逻辑必须帮它找到和它相关的数据结构,因此查找是必然的,即使在硬件中,也是这样。但是查找分为两种类型,这两种类型的查找对性能的影响是不一致的。

0.1.查不到不创建

像路由查找这类,如果查找不到路由项,那么就直接返回失败,数据包就此丢弃。对于这类查找,表项的创建和删除是特定事件(比如人为配置,网卡up/down等)触发的,不是自动的。查找结果的成功与失败所消耗的性能是一致的,所不同的协议栈对待成功与失败的方式不同,因此本文不关注这类查找。

0.2.查不到即创建

像conntrack查找,邻居查找这类,如果查找失败,将会建立一个新的表项,因此查找结果的成功与失败对性能的影响是完全不对称的。如果查找失败,性能损耗是巨大的,即使对于高效的hash算法,起码你要遍历完特定hash值指定的冲突链表才能发现失败,这在平均看来已经是一笔很大的开销了,然后发现失败,这才是一个开始,接下来要分配内存,创建表项,这又是一笔很大的花费,既消耗了时间又消耗了空间。虽然空间损耗不可避免,但是我希望在必须分配内存创建表项之前,用最快的速度发现查找失败。

0.3.介于0.1与0.2的查找

TCP socket查找介于0.1和0.2之间,对于Listen状态socket的查找,它的目标是创建一个客户socket,但是首先它要确保特定的TCP四元组不在ESTABLISHED状态或者TW状态的socket中被找到,如果存在大量的TW套接字,将会消耗大量的时间来证明“这么多TW socket中没有一个匹配它”。如果能快速说明这一点该多好啊。

而对于连Listen套接字都不匹配的元组,将会直接报告查找失败。

接下来我将不那么详细分析几种Linux内核协议栈中的查找方法。

2.nf_conntrack查找

Linux nf_conntrack优化的空间很大很大,测试表明,加入conntrack的内核协议栈在满载情况下PPS(Packet Per Second)会下降一半,长连接最大连接数下降一半。对于短连接,即使将各个timeout时间设置很短,性能下降也很明显。

新建conntrack表项的速度限制了新建连接的速度,而conntrack所能占用的内存大小以及一个conntrack表项持续的时间限制了最大的连接数量。在同时保持大量conntrack表项的情况下,如果HASHSIZE不够大,那么hash冲突链表将会很长,新建连接,即NEW conntrack的创建将会极其损耗资源,因为它必须在经过极大消耗后才会发现查找失败,接下来才是干正事。如果在创建之前,快速发现查找失败,将是一件好事。

3.路由cache查找

对于类似cache的查找,也是同样的,比如路由cache的查找,我们知道,路由cache有一个过期时间,如果一台路由器的过境流量过多,将会有大量的路由项被cache,查找cache本身就是一笔很大的开销,hash冲突的可能性很大,费了这么大的劲还没有查到,不得不进入slow路径,简直气死人!

事实上,在存在大量过境流量时,路由cache的查找开销将远远大于正规路由表查找的slow路径开销,也许正是因为这样,Linux终于还是取消了路由cache。

4.ipset查找

对于ipset中的表项查找也类似,今天在医院给小小看病的间隙,突然发现6.23版本的ipset拥有了timeout参数,支持了超时时间本身能做很多事,逻辑处理自动化了不少,但是协议栈并不知道一个表项是否已经因为过期而被删除,个人觉得,像ipset查找这类,即使不携带timeout参数,如果能快速确定“不在set”中也是很好的,当然不能明确确定“不在set中”的时候,再进行特定数据结构的查找,比如hash,tree查找。

5.Bloom过滤器

在上文中,我最终都表达了一种渴望,那就是尽快发现查找失败,这样就可以直接去干正事,而不必将时间花在一件必然失败的事上,这代价也许对于OpenWRT这样的烟囱垃圾能付得起,但是对于登上大雅之堂的Linux而言,绝对付不起。当然,几乎所有的操作系统实现的协议栈,都和Linux一样。

如何能快速发现查找失败,这是一个根本问题,但是再抽象一点,那就是如何确定“一个元素一定不在一个集合中”。这件事有一个专门的理论去处理,那就是Bloom过滤器,它事实上在时间复杂度和空间复杂度上的效率都很高,但是天下没有免费的午餐,代价是什么?代价就是可能误判!虽然可能误判,但是这个算法还是可以确定一些事实的,如果它对每一个判断的回答都是”可能“,那么它就是不可用的,我们总是希望确定一些事实,100%地确定一些事实!为了更好的说明,我将其写成一个函数r=B(x),如果返回0,那么就说明x不在集合中,如果返回1,那么就说明一个”可能“的事实,即x有y%的可能性不在集合中,具体y是多少,背后的数学其实也不复杂,但并不是本文的重点。

正规的hash表是用一个hash算法将搜索范围缩小,然后在冲突链表中进行精确匹配,因此结果无疑是确定的。然而Bloom过滤算法并不维护冲突链表,它只是逐步用多个不同的hash算法将搜索范围一步步缩小,即使这个范围再小,也还是有冲突的可能,而这种可能就是误判。Bloom过滤算法在数据结构上设计地十分精巧,如果使用N个hash算法,那么只需维护一个N位的位图,为集合添加一个元素的时候,为该元素应用每一个hash算法计算N个范围从0到N-1的hash值Si,并在位图中置位Si为1。现在判断元素x是否在集合中,为x计算N个hash值Xi,将位图上位于Xi上的所有值做与运算,结果为0的话,说明元素x一定不在集合中,如果它在的话,一定在添加的时候会将所有相关位设置为1。

6.应用Bloom过滤器

我在上述2-5小节所描述的查找算法开始之前部署一个Bloom过滤器,是不是更好呢?如果这个Bloom算法设计地足够好,对于大多数情况,如果返回0,我就可以直接跳到创建操作的逻辑,省去了大量的遍历时间。如果返回1,那么仍然需要进行精确匹配,这相当于在我本来就觉得不好的算法基础上又平添了一个Bloom过滤,情形恶化了。但是这就是代价!这就是冒险!我可以将责任推到”这个Bloom算法设计地不够好“!另一方面,需要权衡计算N个hash的开销和计算1个hash加上遍历的开销哪个大,此时不应该简单分析时间复杂度,因为对于Bloom,如果N确定了,那么时间复杂度无疑是O(1),难道一定比hash表的效率更好吗?事实上我们应该取加权统计值,而这个值依赖于严格的性能压力测试。

还是那句话,没有免费的午餐,要么使用硬件加速,此时你花费的是钱,要么设计一个良好的算法,此时你付出的冒险以及算法失败后的补偿!

7.分级hash查找

像MMU中的页表查找思想一样,也和BSD中的路由查找算法的思想一样,采用多层hash查找而不是单一hash加冲突链表遍历。

我以conntrack查找为例,我可以将conntrack简化为一个{IP1,IP2}对,第一个元素为键,第二个为值,这样就可以将conntrack的查找做成BSD系统的路由查找的样子,其中IP2可以被看成下一跳。或者别的......

我并不是说多级的hash算法要比单独的hash算法更高效,而是说多级的hash表可以在多个CPU核心分别计算,多级hash表可以将每一个hash计算视为一个维度,每一个CPU核心计算一个维度的hash值,定位该维度的坐标,反观单一hash表就不能利用多CPU核心优势,你必须先计算好hash值才能定位hash桶从而遍历冲突链表。在多CPU核心时代,传统的基于时间复杂度计算分析性能的方式可能已经过时。

相关推荐