开发者社区> 科技小能手> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介:
+关注继续查看

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核心时代,传统的基于时间复杂度计算分析性能的方式可能已经过时。



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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
linux中cat、more、less命令区别详解
众所周知linux中命令cat、more、less均可用来查看文件内容,主要区别有:cat是一次性显示整个文件的内容,还可以将多个文件连接起来显示,它常与重定向符号配合使用,适用于文件内容少的情况;more和less一般用于显示文件内容超过一屏的内容,并且提供翻页的功能。
1947 0
linux命令之 ifconfig
<p style="margin: 0pt auto; padding-top: 0px; padding-bottom: 0px; text-indent: 21pt; color: rgb(51, 51, 51); font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 13px; line-height: 23px;"
1883 0
linux date命令
date +%Y   四位数年    %y   两位数年 ${date}   变量引用
951 0
Linux tree命令
Linux tree命令用于以树状图列出目录的内容。 执行tree指令,它会列出指定目录下的所有文件,包括子目录里的文件。 语法 tree [-aACdDfFgilnNpqstux][-I ][-P ][目录...] 参数说明: -a 显示所有文件和目录。
800 0
23703
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载