再谈 TCP 连接的源端口选择

TCP 源端口的选择有两个场景:

  • 主机场景
  • SNAT 场景

先看主机场景,其中又区分了两类互斥的场景:

  • bind 时选端口:如果 bind 的端口被某条 established 连接使用,则无法 bind;
  • connect 时选端口:如果端口已经被 bind,则无法在 connect 时被选中。

因此必须在 bind 和 connect 之间以及 bind,connect 彼此之间做互斥,遍历某端口的使用链表(bind 只涉及 2 元组,因此只涉及 port hash list)时需要 lock,由于一台主机可能有多个进程同时进行 bind 和 connect,为提高并发能力,Linux 整了个花活儿:

  • bind 先遍历奇数端口,再遍历偶数端口;
  • connect 先遍历偶数端口,再遍历奇数端口。

这样就巧妙地将 bind 和 connect 的遍历路径错开,沿着这个思路继续,还可以更花,比如在奇数或偶数的遍历空间内,根据进程 pid 再次区分奇偶跨度,比如奇数跨度按 1,5,9,13,… 顺序遍历,而偶数跨度按 3,7,11,… 顺序遍历,诸如此类。

本着 “及时停止优化” 的哲学,审视一下花活的代价是高尚的。

在奇数(或偶数)端口号都已经用尽情况下,花活儿不但发挥不了作用,还平添遍历一边奇数空间的开销,因为在遍历一遍之前,进程并不知道奇数空间已经用尽,虽然可以记录一个 anchor 来记录 “奇数空间已经用尽” 的事实,但本质上这个问题的原因是 16bit 的端口空间在 TCP 看来太少,但对实现时需要遍历时又太大,而之所以搞这些精致的花活儿,还是 16bit 空间太小。

所以不要觉得内核妹忒内儿提的任何派驰都是优化,相当大一部分是在恶心人,它们只是针对了场景,而在这些假设之外,性能反而劣化。这类似抛硬币猜正反,但凡做任何假设,总的成功率都会下降。

再看 SNAT 场景。先看一个没有花活儿的实现(约等于但不等于 Linux 内核 nf_conntrack SNAT 实现):

uint16 tcp_get_port(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{struct entry *ent;int anchor = random16();int begin = PORT_BASE;retry:// 4 元组 hash 而不是 3 元组,防止访问局部性导致 bucket 链表过长hash = jhash(sip, sport, dip, dport, 2);uniq = true;list_for_each_from(ent, bucket[hash]) {if (ent->sip == sip && ent->dip == dip && ent->sport == sport && ent->dport == dport) {uniq = false;;break;}}if (uniq) {ent = malloc(sizeof(*ent));ent->sip = sip;ent->dip = dip;ent->sport = sport;ent->dport = dport;hash_insert(ent, hash);return sport;}if (sport - begin < K && retried ++ > MAX_RETRIES) {// 列维长跳if (retried % (MAX_RETRIES/N) == 0)anchor = random16(;sport = anchor;anchor ++;goto retry;}return -1;
}

要整花活儿炫点技巧,一步一步来。

首先,递增 anchor 和列维长跳已够合理,人类文明的轨迹就是列维长跳的结果,典型的大杂居,小聚居对资源利用的合理分布非常有效,正因为此,中原文明才能在几千年时间同化掉整个东亚大陆。然而这太直观了,以至于不够 “厉害”。

如果不使用列维长跳来搜索可用端口,可以用时间戳(精确到 us),进程 pid 一起组成候选 sport。使用时间戳可以自然跨过同时竞争同一端口的进程,从而减少互斥开销,但还有更好的。

如果系统中已经没有可用端口,在遍历一遍前,进程并不知晓这个事实,因此要引入 “快速失败” 机制。这并不难,只需要提供一些积累信息。于是有以下的算法:

uint16 get_port_new(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{struct entry3 *ent3;uint hash3;hash3 = jhash(sip, dip, dport, 2);list_for_each_from(ent3, bucket3[hash3]) {if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {if (ent3->free = ent3->end) // 已经满了,无空闲端口可用return -1;sport = ent3->free + 1;ent3->free ++;break;}}if (ent3 == NULL) {ent3 = malloc(sizeof(*ent3));free_port_init(ent3);sport = ent3->free + 1;hash3_insert(ent3, hash3);}return sport;
}

魔鬼在细节,太复杂必然是错的,太简单也可能不对。

随机释放端口意味着端口分配并非连续可得,因此还是要一个一个尝试,于是代码又恢复成了冗杂,3 元组 hash 只是提高了运算复杂度降低的概率,所有的重试依然还要进行:

uint16 tcp_get_port_new(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{struct entry3 *ent3;struct entry4 *ent4;int anchor = -1;int begin = PORT_BASE;int find = false;hash3 = jhash(sip, dip, dport, 2);list_for_each_from(ent3, bucket3[hash3]) {if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {find = true;uniq = false;;if (ent3->full)return -1;anchor = ent3->free;break;}}// 有了以上 3 元组 hash 辅助,下面的过程将省去遍历过程,几乎直接找到端口if (anchor == -1)anchor = 1;
retry:// 4 元组 hash 而不是 3 元组,防止访问局部性导致 bucket 链表过长hash4 = jhash(sip, sport, dip, dport, 2);uniq = true;list_for_each_from(ent4, bucket4[hash4]) {if (ent4->sip == sip && ent4->dip == dip && ent4->sport == sport && ent4->dport == dport) {uniq = false;;break;}}if (uniq) {ent4 = malloc(sizeof(*ent4));ent4->sip = sip;ent4->dip = dip;ent4->sport = sport;ent4->dport = dport;if (find == false) {ent3 = malloc(sizeof(*ent3));ent3->full = false;ent3->end = 65535;hash3_insert(ent3, hash3);}ent3->free = sport + 1;hash4_insert(ent4, hash4);return sport;}if (sport - begin < K && retried ++ > MAX_RETRIES) {// 列维长跳if (retried % (MAX_RETRIES/N) == 0)anchor = random16(;sport = anchor;anchor ++;goto retry;}return -1;
}

合适的数据结构上场比算法更能解决大部分问题,就像设置一个 anchor 的威力一样,如果用 stack 或 queue 组织空闲端口,事情就会高尚。

使用 stack 会倾向于使用最近被释放的 port,而使用 queue 则相反,使用最早被释放的 port,以 stack 为例,意思如下:

void free_port(uint16 port, uint32 sip, unit32 dip, uint16 dport)
{hash3 = jhash(sip, dip, dport, 2);list_for_each_from(ent3, bucket3[hash3]) {if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {sport = ent3->free.push(ent3.port);break;}}
}
uint16 get_port(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{struct entry3 *ent3;struct port_entry *port;uint hash3;hash3 = jhash(sip, dip, dport, 2);list_for_each_from(ent3, bucket3[hash3]) {if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {if (ent3->stack.num == 0) // 已经满了,无空闲端口可用return -1;port = ent3->free.pop();break;}}if (port == NULL) {ent3 = malloc(sizeof(*ent3));free_port_init(ent3);hash3_insert(ent3, hash3);port = ent3->free.pop();} return port.num;
}

只要 hash 足够好,源端口几乎可以在 O(1) 时间获得。值得注意的是,stack,queue 与 bitmap 相比具有优势,因为 bitmap 强依赖于实现,可以利用硬件高速实现,也可以使用 for-for 嵌套实现。

这些基本技巧已经谈不上是什么花活,malloc 库函数以及文件系统空闲块管理都会用类似机制管理空闲资源,没什么大不了,但 Linux 内核为什么没有使用这种技巧而遍历端口一个一个尝试呢?

首先是简单性,可维护性,这个不必多说,其次是资源占用,无论 bitmap,stack 还是 queue,动用的数据结构都对内存空间有不同需求,而通用操作系统不能假设空间需求的满足,但却可以用时间换空间。换句话说,内存不足就跑不起来了,而时间复杂度就算再高顶多就是慢,通用系统的可用性指标即程序可以完成。

想要程序运行快,除了算法分析外,局部性一定要利用:

  • 时间局部性:针对目标,访问过的网站接下来还会被访问;
  • 空间局部性:针对源,相邻 IP 地址会接连发起访问。

正如大约 10 年前我在 nf_conntrack 中加了一个不到 10 行代码的 recent cache 就获得 30%+ 的吞吐性能提升一样,局部性原理几乎控制着一切。

该总结一下了。

不管多么 trick 的算法,不管它多么高效,“及时停止优化” 永远是对的。沉迷于优美的算法将设计一个不优美的传输协议,因为你迫不及待希望用上这个算法,就很容易复制缺陷,在新协议里将 port(or channel,whatever) 继续设置为 16bit,因为只有这样你的算法才能表现出最优解。

但只要把 port(or channel,whatever) 设置成 32bit,一切问题将迎刃而解,但优美算法永远也用不上了。结构决定行为,而不是算法决定行为。

当审视本文描述的所有这一切,如果有人问你到底什么是正确的,他的目的并非要获取一个真正有价值的方案,而是要获得一个和他的想法一致的方案,因为人们总想听到自己想听到的,这是人们成功或失败的根源。

浙江温州皮鞋湿,下雨进水不会胖。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/8561.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Springboot项目报错记录

SpringBoot测试报错&#xff1a;Unable to find a SpringBootConfiguration, you need to use Context 该测试类所在测试包test下的包名和类路径java下的包名不一致导致的 引发以下报错 java.lang.IllegalStateException: Unable to find a SpringBootConfiguration, you need…

VTK知识学习(3)-显示圆柱

1、添加显示控件 前台界面 <WindowsFormsHost x:Name"windowHost" Grid.Row"1"/> 构造函数中添加。 private RenderWindowControl renderWindowControl new RenderWindowControl();public MainWindow(){InitializeComponent();windowHost.Child …

《FreeRTOS的配置与临界段》

目录 1.FreeRTOS配置的重要性 2.初学者使用FreeRTOSConfig.h 文件 3.“INCLUDE_”开始的宏 4.FreeRTOS 中断配置和临界段 4.1 中断简介 4.2 中断优先级分组定义 4.3优先级设置 4.4 重要的中断屏蔽寄存器 一、PRIMASK 和 FAULTMASK 寄存器 二、BASEPRI 寄存器 4.5 F…

Vue:模板 MVVM

Vue&#xff1a;模板 & MVVM 模板插值语法指令语法 MVVMdefineProperty数据代理 模板 Vue实例绑定一个容器&#xff0c;想要向容器中填入动态的值&#xff0c;就需要使用模板语法。模板语法分为插值语法和指令语法。 插值语法 插值语法很简单&#xff0c;使用{{}}包含一…

极简实现酷炫动效:Flutter隐式动画指南第三篇自定义Flutter隐式动画

目录 前言 一、TweenAnimationBuilder 二、使用TweenAnimationBuilder实现的一些动画效果 1.调整透明度的动画 2.稍微复杂点的组合动画 3.数字跳动的动画效果 前言 上两节博客分别介绍了Flutter中的隐式动画的基础知识以及使用隐式动画实现的一些动画效果。当系统提供的隐…

熵基ZKTeco考勤机门禁如何重置密码(适用于大多数彩屏门禁机)

公司的一台门禁忘记密码了打不开&#xff0c;找了很久终于找到了密码重置的方法。 1、断电拆机(机器底部的螺丝,将机器从墙上拿下来) 2、插电重启&#xff08;或者杵下底部reset小孔&#xff09; 3、机器屏幕显示被拆除&#xff08;或右上角红色小感叹号闪烁&#xff0c;后者启…

​基于学习的地铁客流动态预测智能调度方法

1 文章信息 文章题为“A Learning Based Intelligent Train RegulationMethod With Dynamic Prediction forthe Metro Passenger Flow”&#xff0c;该文于2023年发表至“IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS”。文章的核心观点是提出了一种基于学习的智…

RNA-seq 差异分析的点点滴滴(1)

引言 本系列[1])将开展全新的转录组分析专栏&#xff0c;主要针对使用DESeq2时可能出现的问题和方法进行展开。 为何使用未经标准化的计数数据&#xff1f; DESeq2 工具包在接收输入时&#xff0c;期望得到的是未经处理的原始计数数据&#xff0c;比如从 RNA-seq 或其他高通量测…

Python初始环境搭建和Pycharm的安装

Python和PyCharm安装步骤 刚学习Python编程&#xff0c;按照书上的方法安装了Python和PyCharm&#xff0c;并做练习。但是今天PyCharm软件忽然不能使用了&#xff0c;不知道什么原因。于是&#xff0c;将这两个软件全部卸载&#xff0c;在网上查找软件安装方法&#xff0c;重新…

云上拼团GO指南——腾讯云博客部署案例,双11欢乐GO

知孤云出岫-CSDN博客 目录 腾讯云双11活动介绍 一.双十一活动入口 二.活动亮点 &#xff08;一&#xff09;双十一上云拼团Go (二&#xff09;省钱攻略 &#xff08;三&#xff09;上云&#xff0c;多类型服务器供您选择 三.会员双十一冲榜活动 (一)活动内容 &#x…

[ 常用工具篇 ] 使用 kali 实现 ARP 攻击 -- arpspoof 实战详解(ARP欺骗-断网攻击中间人攻击)

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…

无人机之飞行管控平台篇

无人机的飞行管控平台是一种基于互联网和物联网技术的智能管理系统&#xff0c;旨在实现对无人机飞行任务的全自动化、全过程化管理。 一、主要功能 飞行计划管理&#xff1a;用户可以通过平台提前设置好无人机的飞行计划&#xff0c;包括起飞时间、航线、飞行高度等信息。平…

C++ 继承

一. 继承的概念与定义 1.1. 继承的概念 继承 (inheritance) 机制是面向对象程序设计 使代码可以复用 的最重要的手段&#xff0c;它允许程序员在 保 持原有类特性的基础上进行扩展 &#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。继承 呈现了面向对象…

【启程Golang之旅】深入理解 Protocol Buffers 及其应用

如果你是 Go 语言的开发者&#xff0c;理解如何在 Go 中使用 Protobuf&#xff0c;将帮助你大幅提升数据传输的效率&#xff0c;并实现更高性能的系统设计。 本篇文章将深入探讨 Go 语言中使用 Protobuf 的基础知识、常见应用以及最佳实践&#xff0c;带你一步步了解如何在项目…

vue3.5+版本 defineProps响应式解构,保留数据响应式

正确写法&#xff1a;直接通过 defineProps 结构可以保留响应式 let {num:numNew} defineProps({num: {} }) console.log(具有响应式,numNew); 错误写法&#xff1a;这样会丢失响应式 const props defineProps({num: {} }) let {num:numNew} props console.log(会丢失响…

直播 鸿蒙5.0面试必修技能之鸿蒙性能优化技术

一&#xff1a;行业分析&#xff1a; PC时代---互联网---移动互联网---大数据/人工智能---物联网 c/c/java/php--- andorid/ios/前端/hadoop(存储)/spark/flink【12-14年】 --- ArkTS 李兴平 hao123.com/ 网站:6w/day 06年 5000w卖给了百度 盛大传奇/ 腾讯 互联…

怎么能更好的通过驾考呢?

充分准备&#xff1a; 提前了解驾考内容和要求&#xff0c;包括理论知识、场地驾驶技能、道路驾驶技能和安全文明驾驶常识等。合理安排学习时间&#xff0c;确保有足够的时间进行学习和练习。理论学习&#xff1a; 认真阅读和理解驾考相关书籍和资料&#xff0c;特别是交通法规…

Notion + Python + scholarly = 超强文献管理助手

摘要&#xff1a;在科研文献管理中&#xff0c;研究人员常常需要维护自己的文献数据库&#xff0c;我使用 Notion-database 作为的文献数据库管理工具&#xff08;开源模板&#xff09;。Notion-based 的方法无法实时更新文章的引用量信息。我结合了 Notion Integration 和 sch…

Git遇到“fatal: bad object refs/heads/master - 副本”问题的解决办法

Git遇到“fatal: bad object refs/heads/master - 副本”问题的解决办法 起源 让我们从一个常见的Git错误开始&#xff1a; fatal: bad object refs/heads/master - 副本这个错误提示通常意味着Git在引用&#xff08;ref&#xff09;中发现了不一致或损坏的数据。引用是Git用…

LinkedIn怎么养号:2024最新养号技巧揭秘

LinkedIn领英作为全球最大的职场社交平台&#xff0c;是跨境外贸企业与潜在客户、业务伙伴和同事进行交流的重要平台。然而&#xff0c;许多人在注册和使用LinkedIn时&#xff0c;常常会遇到账户受限甚至被封的困扰。想要拥有一个安全稳定的LinkedIn账户&#xff0c;养号是必不…