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

来源:互联网
更新时间:2016/12/9 11:29:26
责任编辑:李志喜
字体:

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路径,简直气死人!
www.xue163.com true /5/55168.html report 1806 Linux协议栈查找算法优化随想,Linux的网络协议栈实现可谓精确却不失精巧,不必说Netfilter,单单说TC就够了,但是有几处硬伤,本文做一个不完备的记录,就当是随笔,不必当真。0.查找的种类Linux协议栈作为一个纯软件实现,保留了硬件接口,但是本文不涉及硬件。在Linux...
最近关注
首页推荐
热门图片
最新添加资讯
24小时热门资讯
linux网络协议栈linux协议栈linuxtcp/ip协议栈linux内核协议栈linux内核栈linux栈大小linux栈栈的算法
精彩资讯
精彩推荐
热点推荐
真视界
精彩图片
社区精粹
关于本站 | 广告服务 | 手机版 | 商务合作 | 免责申明 | 招聘信息 | 联系我们
Copyright © 2004-2016 Xue163.com All Rights Reserved. 中国学网 版权所有
京ICP备10044368号-1 京公网安备11010802011102号
荐闻 | 学网头条知识问答 | 装修 | 作业 | 荐闻 | 学网头条精彩微信 | 新闻中心 | 软件教室 | 设计大全 | 网络相关 | 英语学习 | 开发编程 | 考试中心 | 参考范文 | 管理文库 | 营销中心 | 站长之家 | IT信息中心 | 商学院 | 数码大全 | 硬件DIY | 企业服务 | 网吧在线 | 问吧 | 百科 | 硬件知识 | 本网视点 | 文库 | 手机 | 平板 | 汽车 | 游戏 | 家电 | 精彩摄影 | 时尚科技 | 现代家居 | IT女人 | 经验 | 每日新闻 | 健康养生 | 图书馆 | 猎奇 | 精彩看点 | 图库 | 新闻中心 | 软件教室 | 设计大全 | 网络相关 | 英语学习 | 开发编程 | 考试中心 | 参考范文 | 管理文库 | 营销中心 | 站长之家 | IT信息中心 | 商学院 | 数码大全 | 硬件DIY | 企业服务 | 网吧在线 | 问吧 | 百科 | 硬件知识 | 本网视点 | 文库 | 手机 | 平板 | 汽车 | 游戏 | 家电 | 精彩摄影 | 时尚科技 | 现代家居 | IT女人 | 经验 | 每日新闻 | 健康养生 | 图书馆 | 精彩微信 | 猎奇 | 精彩看点 | 图库编程 方案 信息windows方案windows answer文档机构教育文档问答中心IT编程数码信息解决方案信息中心IT科技