来源：自学PHP网 时间：2015-04-14 10:17 作者： 阅读:次
[导读] Linux的网络协议栈实现可谓精确却不失精巧，不必说Netfilter，单单说TC就够了，但是有几处硬伤，本文做一个不完备的记录，就当是随笔，不必当真。...
|
Linux的网络协议栈实现可谓精确却不失精巧，不必说Netfilter，单单说TC就够了，但是有几处硬伤，本文做一个不完备的记录，就当是随笔，不必当真。
0.查找的种类Linux协议栈作为一个纯软件实现，保留了硬件接口，但是本文不涉及硬件。
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中没有一个匹配它”。如果能快速说明这一点该多好啊。
接下来我将不那么详细分析几种Linux内核协议栈中的查找方法。
2.nf_conntrack查找Linux nf_conntrack优化的空间很大很大，测试表明，加入conntrack的内核协议栈在满载情况下PPS(Packet Per Second)会下降一半，长连接最大连接数下降一半。对于短连接，即使将各个timeout时间设置很短，性能下降也很明显。
3.路由cache查找对于类似cache的查找，也是同样的，比如路由cache的查找，我们知道，路由cache有一个过期时间，如果一台路由器的过境流量过多，将会有大量的路由项被cache，查找cache本身就是一笔很大的开销，hash冲突的可能性很大，费了这么大的劲还没有查到，不得不进入slow路径，简直气死人！
4.ipset查找对于ipset中的表项查找也类似，今天在医院给小小看病的间隙，突然发现6.23版本的ipset拥有了timeout参数，支持了超时时间本身能做很多事，逻辑处理自动化了不少，但是协议栈并不知道一个表项是否已经因为过期而被删除，个人觉得，像ipset查找这类，即使不携带timeout参数，如果能快速确定“不在set”中也是很好的，当然不能明确确定“不在set中”的时候，再进行特定数据结构的查找，比如hash，tree查找。
5.Bloom过滤器在上文中，我最终都表达了一种渴望，那就是尽快发现查找失败，这样就可以直接去干正事，而不必将时间花在一件必然失败的事上，这代价也许对于OpenWRT这样的烟囱垃圾能付得起，但是对于登上大雅之堂的Linux而言，绝对付不起。当然，几乎所有的操作系统实现的协议栈，都和Linux一样。
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加冲突链表遍历。
|
自学PHP网专注网站建设学习,PHP程序学习,平面设计学习，以及操作系统学习
京ICP备14009008号-1@版权所有www.zixuephp.com
网站声明：本站所有视频，教程都由网友上传，站长收集和分享给大家学习使用，如由牵扯版权问题请联系站长邮箱904561283@qq.com
