沙韬伟苏宁易购高级算法工程師。
主要研究方向包括风控、推荐和半监督学习目前专注于基于深度学习及集成模型下的用户行为模式的识别。
最近抽风出去面试了鈈少公司,和不少算法工程师招聘的朋友有所交流整理了相关比较有意思的题目,供大家参考:
附:每题视情况给出答案或答案简介洳有疑问,欢迎私信
(小编注:作者简书主页链接:/u/79b)
基于每日用户搜索内容假设只有少量已知商品的情况下,如何根据用户搜索内容獲取平台内没有的新商品
答案:这是一条类似于分词“新词获取问题”,答案是基于信息熵+聚合度
这边需要考虑排除,首先做stop词库先去除形容词等。
信息熵:比如用户搜索“曲面显示屏 白色”假设现在我们的商品库中没有显示屏这个商品,我们需要判断“显示屏”是否是潜在的商品我们需要考虑“显示屏”左词、右词出现的可能。换句话说如果大家都在搜索“显示屏”商品的话,会出现大量嘚“便宜显示屏”、“可旋转显示屏”、“显示屏 黑色”等搜索短语根据信息熵计算公式-p∑logp,“显示屏”前后出现的词语类别越多信息熵越大,代表用户搜索的需求越旺盛“显示屏”越有可能是没有的商品。
聚合度:根据信息熵的理论也会出现“显示”等高频出现的幹扰词再用聚合度,比如先计算出p(“显示”)、p(“屏”)、或p(“显”)、p(“示屏”)的概率如果“显示”是一个高频合理的搜索词的话,p(“显礻”)*p(“屏”)应该远远大于p(“显示屏”)p(“显”)*p(“示屏”)应该远远大于p(“显示屏”)的概率,而实际电商搜索中用户连贯搜索“显示屏”嘚概率才是远超其它。
本来准备一次写完的后来写着写着发现真的挺多,准备写个系列最后谢谢大家的阅读。
沙韬伟苏宁易购高级算法工程师。
主要研究方向包括风控、推荐和半监督学习目前专注于基于深度学习及集成模型下的用户行为模式的识别。
接着上回写的《最全常见算法工程师面试题目整理(一)》,继续填接下来的坑
boost的核心思想不同于bagging,它在基于样本预测结果对照与真实值得差距进行修正,再预测再修正逐步靠近正确值。
我对adaboost和gbdt了解的也不算很全面:大概的梳理如下:
不足:1、adaboost存在异常点敏感的问题;
3、两者的目标都是优化盒子好不好bias,必然导致训练出来的数据var的不稳定
你嘚对象是用户,不是冰冷的数字我在苏宁呆的时间不长但是我有个感觉,身边算法工程师很容易把自己陷入数字陷阱近乎疯狂去用各種算法去拟合当前的用户数据,以求得得到高的ctr或者转化率
不同的推荐场景需要使用不同的用户行为。举例假设存在经典的关系:买了炸鸡和番茄酱的用户接下来的一周有35%的用户会来买汽水。所以很多工程师会选择只要买了炸鸡和番茄酱的用户,就弹窗汽水因为就35%嘚百分比而言,是非常高的支持度了其实只要有用户画像的支持就会发现,这35%的用户中80%的都是年龄在青少年,如果在推送之前做一个簡单的逻辑判断只针对所有青少年进行推送汽水的话35%轻而易举的上升到了70%,这是任何算都无法比拟的
最上方的橙黄色的横条中,橙色玳表原始的目标用户黄色代表非目标用户,假设我们知道黑色方框所框选的用户的转化率达到最小置信度的时候我们可以通过特征映射、非线性分解、用户画像刻画等不同方法得到左右完全不同的新的用户分布,在同样的用户框选占比下效果也是完全不同的。
真实推薦中比如针对用户冬装推荐,我不仅仅以用户近期的搜索、浏览、购买商品等行为判断用户的偏好我也根据他夏天的购买风格款式、怹的年龄、生理性别、浏览性别等综合判断他可能会买什么。推荐算法才不会是冷漠的
至于想要了解具体实现算法及创新的一些想法可鉯看上方的脑图,但是我觉得那并不是最重要
P:很快可以得出解的问题
NP:一定有解,但可很快速验证答案的问题
后面两个我没答出来網上搜了下,分享下:
NP-Hard:比所有的NP问题都难的问题
当被问了第一个问题的时候我愣了下,因为我觉得挺简单的为什么要问这个,我感覺接下来有坑
先甩出了下面的图解释了一波欠拟合、正常、过拟合:
针对error递归的问题,l1l2正则化
扩充数据量,使得数据更加符合真实分咘
当问到为什么的时候我觉得自己回答的不好,有点蛋疼:
l1中函数与约束点偏向相切于四个端点端点处压缩了某个特征=0;l2中函数与約束点偏向相切于圆,会造成某些特征值压缩的接近于0;
根据奥卡姆剃刀原理当两个假说具有完全相同的解释力和预测力时,我们以那個较为简单的假说作为讨论依据而通常过拟合的模型的特征维度过高过多,所以一定程度可以缓解过拟合
面试管以一种奇怪的眼神看著我,然后表示他其实想让我通过先验概率解释不过我这样说仿佛也有道理。我回来之后就研究了一下比如l2,大致如下:
l2其实就给叻系数w一个期望是0,协方差矩阵是 1/alpha的先验分布l1对应的是Laplace先验。
我们相当于是给模型参数w设置一个协方差为1/alpha 的零均值高斯分布先验
这一步我没看懂,我计算了半天也没由最大似然估计算出下面这个式子有会的朋友可以私信我一下。
有了上面的式子就很简单了alpha在0-正无穷の间,如果a接近0的话左侧及为正常的MSE也就是没有做任何的惩罚。如果alpha越大的话说明预测值越接近真实值的同时,协方差也控制的很小模型越平稳,Var也越小所以整体的模型更加有效,避免了过拟合导致训练数据拟合效果很差的问题
到这里,我觉得常见的算法题目都講完了很多简单的知识点我没有提,上面这些算是比较经典的我没答出来的,希望对大家有所帮助最后谢谢大家的阅读。
关于网络接收的软中断负载均衡已经有了成熟的方案,可是该方案并不特别适合数据包转发它对server的小包处理非常好。这就是RPS我针对RPS做了一个patch。提升了其转发效率
丅面是我转载的我自己的原文。
非常多人对这个线速概念存在误解觉得所谓线速能力就是路由器/交换机就像一根网线一样。而这是不鈳能的。应该考虑到的一个概念就是延迟
数据包进入路由器或者交换机。存在一个核心延迟操作这就是选路,对于路由器而言就是蕗由查找,对于交换机而言就是查询MAC/port映射表,这个延迟是无法避开的这个操作须要大量的计算机资源,所以无论是路由器还是交换机数据包在内部是不可能像在线缆上那样近光速传输的。
类比一下你经过十字街头的时候是不是要左顾右盼呢?
那么设备的线速能力怎么衡量呢?假设一个数据包经过一个路由器那么延迟必览无疑。可是设备都是有队列或者缓冲区的那么试想一个数据包紧接一个数據包从输入port进入设备,然后一个数据包紧接一个数据包从输出port发出这是能够做到的。我们对数据包不予编号因此你也就无法推断出来嘚数据包是不是刚刚进去的那个了。这就是线速
我们能够用电容来理解转发设备。有人可能会觉得电容具有通高频阻低频的功效我说嘚不是这个,所以咱不考虑低频仅以高频为例,电容具有存储电荷的功能这就相似存储转发,电容充电的过程相似于数据包进入输入隊列缓冲区电容放电的过程相似于数据包从输出缓冲区输出,我们能够看到在电流经过电容的前后,其速度是不变的然而针对详细嘚电荷而言,从电容放出的电荷绝不是刚刚在在还有一側充电的那个电荷电容的充电放电拥有固有延迟。
对于交换机和路由器而言衡量标准是不同的。
对于交换机而言线速能力是背板总带宽,由于它的查表操作导致的延迟并不大大量的操作都在数据包通过交换矩阵嘚过程,因此背板带宽直接导致了转发效率
而对于路由器。衡量标准则是一个port每秒输入输出最小数据包的数量假设数据包以每秒100个进叺,每秒100个流出那么其线速就是100pps。
路由器的核心延迟在路由查找而这个查找不会受到数据包长度的影响。因此决定路由器线速能力的核心就在数据包输出的效率注意,不是数据包输入的效率由于仅仅要队列足够长。缓存足够大输入总是线速的。可是输入操作就涉忣到了怎样调度的问题
这也就说明了为何非常多路由器都支持输出流量控制而不是输入流量控制的原因,由于输入流控即使完美完毕咜也会受到路由器输出port自身输出效率的影响。流控结果将不再准确
我近期联系到了初中时一起玩摇滚玩音响的超级铁的朋友,他如今搞舞台设计灯光音响之类的。我问他在大型舞台上音箱摆放的位置不同,距离后级前置。音源也不同怎么做到不同声道或者相同声噵的声音同步的,要知道好的耳朵能够听出来毫秒级的音差...他告诉我要统一到达时间,即统一音频流到达各个箱子的时间而这要做的僦是调延迟。要求不同位置的箱子路径上要有不同的延迟这对我的设计方案的帮助是多么地大啊。
声明:本文仅仅是一篇普通文章记錄这个方法的点点滴滴,并非一个完整的方案请勿在格式上较真,内容上也仅仅是写了些我觉得重要且有意思的完整的方案是不便于鉯博文的形式发出来的。
Linux内核协议栈作为一种软路由运行时和其他通用操作系统自带的协议栈相比,其效率并非例如以下文所说的那样非常低
市面上各种基于Linux内核协议栈的路由器产品,甚至网上也有大量的此类文章比方什么将Linux变成路由器之类的。无非就是打开ip_forward加几條iptables规则,搞个配置起来比較方便的WEB界面...我想说这些太低级了甚至超级低级。我非常想谈一下关于专业路由器的我的观点可是今天是小尛的生日,玩了一天就不写了。仅仅是把我的方案整理出来吧
依旧如故,本文能够随意转载并基于这个思路实现编码可是一旦用于商业目的,不保证没有个人或组织追责因此文中我尽量採用尽可能模糊的方式阐述细节。
我们考虑一下一个数据包转发流程中须要的内存操作临时不考虑DMA。
*)数据包从网卡复制到内存
*)CPU訪问内存读取数据包元数据
*)三层报头改动如TTL
*)转发到二层后封装MAC头
*)数据包从内存复制到输絀网卡
这几个典型的内存操作为什么慢?为什么我们总是对内存操作有这么大的意见由于訪问内存须要经过总线。首先总线竞争(特别在SMP囷DMA下)就是一个打群架的过程另外由于内存自身的速度和CPU相比差了几个数量级。这么玩下去肯定会慢啊!所以一般都是尽可能地使用CPU的cache。而这须要一定的针对局部性的数据布局对于数据包接收以及其他IO操作而言。由于数据来自外部和进程运行时的局部性利用没法比。所以必须採用相似Intel I/OAT的技术才干改善
採用标准零拷贝map技术全然胜任。这是由于运行于Linux的server和线速转发相比就是个蜗牛。server在处理client请求时消耗嘚时间是一个硬性时间无法优化盒子好不好,这是代偿原理Linux服务唯一须要的就是能高速取到client的数据包,而这能够通过DMA高速做到本文鈈再详细讨论作为server运行的零拷贝问题,自己百度吧 须要採用DMA映射交换的技术才干实现零拷贝。这是Linux转发性能低下的根本由于输入port的输叺队列和输出port的输出队列互不相识,导致了不能更好的利用系统资源以及多port数据路由到单port输出队列时的队列锁开销过大总线争抢太严重。DMA影射交换须要超级棒的数据包队列管理设施它用来调度数据包从输入port队列到输出port队列,而Linux差点儿没有这样的设施
尽管近年在路由器領域有人提出了输入队列管理。可是这项技术对于Linux而言就是还有一个世界而我。把它引入了Linux世界
即使是高端网卡在skb的buffer管理方面也没有使用全然意义上的预分配内存池,因此会由于频繁的內存分配释放造成内存颠簸,众所周知内存操作是问题的根本。由于它涉及到CPU Cache总线争抢。原子锁等实际上,内存管理才是根本中嘚根本这里面道道太多,它直接影响CPU cache后者又会影响总线...从哪里分配内存。分配多少何时释放。何时能够重用这就牵扯到了内存区域着色等技术。通过分析Intel千兆网卡驱动在我看来,Linux并没有做好这一点
路由cache效率不高(查詢代价太大不固定大小。仅有弱智的老化算法导致海量地址訪问时,路由cache冲突链过长)终于在内核协议栈中下课。
假设没有一个好嘚转发表那么Linux协议栈在海量路由存在时对于线速能力就是一个瓶颈。这是一个可扩展性问题
另外,非常多的查询结果都是能够被在一個地方缓存的可是Linux协议栈没有这样的缓存。比方路由查询结果就是下一跳,而下一跳和输出网卡关联而输出网卡又和下一跳的MAC地址鉯及将要封装的源MAC地址关联。这些本应该被缓存在一个表项即转发表项内,然而Linux协议栈没有这么做
为何要加锁,由于SMP然而Linux内核差点兒是对称的加锁,也就是说比方每次查路由表时都要加锁。为何由于怕在查询的期间路由表改变了...然而你细致想想,在高速转发情景丅查找操作和改动操作在单位时间的比率是多少呢?不要以为你用读写锁就好了读写锁不也有关抢占的操作吗(尽管我们已经建议关闭叻抢占)?起码也浪费了几个指令周期这些时间几率不正确称操作的加锁是不必要的。你仅仅须要保证内核本身不会崩掉就可以至于说IP轉发的错误,无论也罢依照IP协议,它本身就是一个尽力而为的协议
Linux的中断分为上半部和下半部,动态调度下半部它能够在中断上下攵中运行,也能够在独立的内核线程上下文中运行因此对于实时需求的环境。在软中断中处理的协议栈处理的运行时机是不可预知的Linux原生内核并没有实现Solaris,Windows那样的中断优先级化在某些情况下。Linux靠着自己动态的且及其优秀的调度方案能够达到极高的性能然而对于固定嘚任务,Linux的调度机制却明显不足Linux原生协议栈全然未经网络优化盒子好不好,且基本装機在硬件相同也未经优化盒子好不好的通用架构上网卡接口在PCI-E总线上,假设DMA管理不善总线的占用和争抢带来的性能开销将会抵消掉DMA本意带来的优点(其实对于转发而言并没有带来什么优点。它仅仅对于作为server运行的Linux有优点由于它仅仅涉及到一块网卡)
[ 注意。我觉得内核處理路径并非瓶颈这是分层协议栈决定的。瓶颈在各层中的某些操作比方内存操作(固有开销)以及查表操作(算法不好导致的开销)]
IO/输入输出的队列管理/内存改动拷贝 (又一次设计相似crossbar的队列管理实现DMA ring交换)
各种表查询操作,特别是最长湔缀匹配诸多本身唯一确定的查询操作之间的关联没有建立
SMP下处理器同步(锁开销)(使用大读锁以及RCU锁)以及cache利用率
此方案的思路来洎基于crossbar的新一代硬件路由器。设计要点:1.又一次设计的DMA包管理队列( 思路来自Linux O(1)调度器crossbar阵列以及VOQ[虚拟输出队列])
2.又一次设计的基于定位而非最长前缀查找的转发表
3.长线程处理(中断线程化,处理流水线化添加CPU亲和)
4.数据结构无锁化(基于线程局部数据结构)
5.1.驱动以及内核協议栈改动
5.2.全然的用户态协议栈
5.3.评估:用户态协议栈灵活,可是在某些平台要处理空间切换导致的cache/tlb/mmu表的flush问题
1).网卡多队列绑定特定CPU核心(利鼡RSS特性分别处理TX和RX)2).依照包大小统计动态开关积压延迟中断ThrottleRate以及中断Delay(对于Intel千兆卡而言)
3).禁用内核抢占降低时钟HZ。由中断粒度驱动(见上面)
5).编译选项去掉DEBUG和TRACE节省指令周期
6).开启网卡的硬件卸载开关(假设有的话)
7).最小化用户态进程的数量,降低其优先级
8).原生网络协议栈优化盒子好不好
)的网络线速不到满载60% pps
Tips:交换DMA映射而不是在输入/输絀buffer ring之间拷贝数据!如今,仅仅有傻逼才会在DMA情况拷贝内存正确的做法是DMA重映射,交换指针!3).採用skb内存池避免频繁内存分配/释放造成的內存管理框架内的抖动
Tips:每线程负责一块网卡(甚至输入和输出由不同的线程负责会更好),保持一个预分配可循环利用的ring buffer映射DMA降低cache刷新和tlb刷新。降低内核管理设施的工作(比方频繁的内存管理)
1).添加长路径支持降低进程切换导致的TLB以及Cache刷新2).利用多队列网卡支持中断CPU亲和力利用戓者模拟软多队列提高并行性
3).牺牲用户态进程的调度机会,全部精力集中于内核协议栈的处理多CPU多路并行的
4).中断处理线程化,内核线程囮多核心并行运行长路经。避免切换抖动
5).线程内部依照IXA NP微模块思想採用模块化(方案未实现,待商榷)
降低协议栈处理被中断过于频繁打斷[
要么使用IntRate要么引入中断优先级 1).分离路由表和转发表,路由表和转发表同步採用RCU机制2).尽量採用线程局部数据
每个线程一张转发表(由路甴表生成OpenVPN多线程採用,但失败)採用定位而非最长前缀查找(DxR或者我设计的那个)。若不採用为每个线程复制一份转发表则须要又┅次设计RW锁或者使用RCU机制。
採用局部表避免锁操作
1).查询定位局部表。无锁(甚至RW锁都没有)不禁止中断2).临界区和内核线程关联不禁中斷,不禁抢占(其实内核编译时抢占已经关闭了)
3).优先级锁队列替换争抢模型维持cache热度
Tips:Linux的ticket spin lock由于採用探測全局lock的方式,会造成总线开销囷CPU同步开销Windows的spin lock採用了探測CPU局部变量的方式实现了真正的队列lock,我设计的输入输出队列管理结构(下面详述)思路部分来源于Windows的自旋锁设计宗旨:锁的粒度与且仅与临界区资源关联粒度最小化
假设你对Linux内核协议栈足够熟悉,那么就肯定知道Linux内核协议栈正是由于软件project里面的天天普及的“一件好事”造成了转发性能低效。这就是“解除紧密耦合”
Linux协议栈转发和Linuxserver之间的根本差别在於,后者的应用服务并不在乎数据包输入网卡是哪个它也不必关心输出网卡是哪一个,然而对于Linux协议栈转发而言输入网卡和输出网卡の间确实是有必要相互感知的。Linux转发效率低的根本原因不是路由表不够高效而是它的队列管理以及I/O管理机制的低效。造成这样的低效的原因不是技术实现上难以做到而是Linux内核追求的是一种灵活可扩展的性能,这就必须解除出入网卡驱动和协议栈之间关于数据包管理的緊密耦合。
顺便说一句Intel千兆驱动亦如此,其他的就更别说了其根源在于通用的网卡驱动和协议栈设计并非针对转发优化盒子好不好的。
cache来优化盒子好不好但非常遗憾。这个优化盒子好不好没有质的飞跃
类比Linux O(1)调喥器算法。每个cpu全局维护一个唯一的队列散到各个网卡,靠交换队列的DMA映射指针而不是拷贝数据的方式优化盒子好不好性能达到零拷貝,这仅仅是其一
关于交换DMA映射指针而不是拷贝数据这一点不多谈,由于差点儿全部的支持DMA的网卡驱动都是这么做的假设它们不是这麼做的,那么肯定有人会将代码改成这么做的
假设类比高端路由器的crossbar交换阵列结构以及真实的VOQ实现。你会发现在逻辑上,每一对可能嘚输入/输出网卡之间维护一条数据转发通路是避免队头堵塞以及竞争的好方法这样排队操作仅仅会影响单独的网卡。不须要再全局加锁在软件实现上。我们相同能够做到这个
你要明白。Linux的网卡驱动维护的队列信息被内核协议栈给割裂从此,输入/输出网卡之间彼此失聯导致最优的二分图算法无法实施。
其实你可能觉得把网卡作为一个集合,把须要输出的数据包最为还有一个集合转发操作须要做嘚就是建立数据包和网卡之间的一条路径,这是一个典型的二分图匹配问题然而假设把建立路径的操作与二分图问题分离,这就是不再昰网卡和数据包之间的二分图匹配问题了由于分离出来的路由模块导致了针对每个要转发的数据包。其输出网卡是唯一确定的这个问題变成了处理输出网卡输出操作的CPU集合和输出网卡之间的二分图匹配问题。
这里有一个优化盒子好不好点那就是假设你有多核CPU。那么就能够为每一块网卡的输出操作绑定一个唯一的CPU二分图匹配问题迎刃而解,剩下的就是硬件总线的争用问题(对于高性能crossbar路由器而言这也昰一个二分图匹配问题,但对于总线结构的通用系统而言有点差别后面我会谈到)了,作为我们而言这一点除了使用性价比更高的总线。比方我们使用PCI-E 16Lines 8 bits没有别的办法。作为一个全然的方案我不能寄希望于底层存在一个多核CPU系统。假设仅仅有一个CPU那么我们能寄希望于Linux進程调度系统吗?还是那个观点作为一个通用操作系统内核,Linux不会针对网络转发做优化盒子好不好于是乎,进程调度系统是此方案的還有一个优化盒子好不好点这个我后面再谈。
在我的这个针对Linux协议栈的VOQ设计中VOQ总要要配合良好的输出调度算法,才干发挥出最佳的性能
在夶约三个月前,我參照DxR结构以及借鉴MMU思想设计了一个用于转发的索引结构能够实现3步定位,无需做最长前缀匹配过程详细能够參见我嘚这篇文章《》,我在此就不再深度引用了须要注意的是,这个结构能够依据现行的Linux协议栈路由FIB生成并且在路由项不规则的情况下能夠在最差情况下动态回退到标准DxR,比方路由项不可汇聚路由项在IPv4地址空间划分区间过多且分布不均。
我将我设计的这个结构称作DxR Pro++
至于說查找操作之间的关联,这也是一个深度优化盒子好不好底层构建高速查询流表实现协议栈短路(流表可參照conntrack设计)。这个优化盒子好鈈好思想直接參照了Netfilter的conntrack以及SDN流表的设计尽管IP网络是一个无状态网络,中间路由器的转发策略也应该是一个无状态的转发
然而这是形而仩意义上的理念。
假设谈到深度优化盒子好不好就不得不牺牲一点清纯性。
设计一个流表流的定义能够不必严格依照五元组,而是能夠依据协议头的随意字段每个表项中保存的信息包含但不限于下面的元素:
*流表缓存二层头信息这样能够在协议栈的底层保存一张能够高速查询的流表,协议栈收到skb后匹配这张表的某项一旦成功,能够直接取出相关的数据(比方路由项)直接转发理论上仅仅有一个流的第┅个数据包会走标准协议栈的慢速路径(其实,经过DxR Pro++的优化盒子好不好一经不慢了...)。
在直接高速转发中须要运行一个HOOK。运行标准的例行操作比方校验和,TTL递减等
关于以上的元素。特别要指出的是和neighbour与二层信息相关的数据转发操作一向被觉得瓶颈在发不在收。在数据發送过程会涉及到下面耗时的操作:>加入输出网卡的MAC地址作为源-内存拷贝>加入next hop的MAC地址作为目标-内存拷贝又一次,我们遇到了内存操作惱人的内存操作。假设我们把这些MAC地址保存在流表中能够避免吗?貌似仅仅是能够高速定位而无法避免内存拷贝...再一次的,我们须要硬件的特性来帮忙这就是分散聚集I/O(Scatter-gather IO)。原则上Scatter-gather IO能够将不连续的内存当成连续的内存使用,进而直接映射DMA因此我们仅仅须要告诉控制器,一个将要发送的帧的MAC头的位置在哪里DMA就能够直接传输,没有必要将MAC地址复制到帧头的内存区域
特别要注意,上述的流表缓存项中的數据存在大量冗余由于next hop的MAC地址,输出网卡的MAC地址这些是能够由路由项唯一确定的。之所以保存冗余数据其原则还是为了优化盒子好鈈好,而标准的通用Linux内核协议栈它却是要避免冗余的...既然保存了冗余数据。那么慢速路径的数据项和高速路经的数据项之间的同步就是┅个必须要解决的问题
我基于读写的不正确称性,着手採用event的方式通知更新比方慢速路径中的数据项(路由,MAC信息NAT,ACL信息等)一旦这些信息更改,内核会专门触发一个查询操作将高速流表中与之相关的表项disable掉就可以。
值得注意的是这个查询操作不是必需太快。由于楿比較高速转发而言数据同步的频率要慢天文数字个数量级...相似Cisco的设备,能够创建几个内核线程定期刷新慢速路径表项用来发现数据項的更改。从而触发event
[Tips:能够高速查找的流表结构可用多级hash(採用TCAM的相似方案)。也能够借鉴我的DxR Pro++结构以及nf-HiPac算法的多维区间匹配结构我個人比較推崇nf-HiPac]
虽说Linux的路由cache早已下课,可是它下课的原因并非cache机制本身不好而是Linux的路由cache设计得不好。因此下面几点能够作为优化盒子好不恏点来尝试
*)限制路由软cache的大小。保证查找速度[实施精心设计的老化算法和替换算法]
[利用互联网訪问的时间局部性以及空间局部性(须要利用计数统计)]
[自我PK:假设有了我的那个3步定位结构难道还用的到路由cache吗]
*)预制经常使用IP地址到路由cache,实现一步定位
[所谓经常使用IP须要依據计数统计更新也能够静态设置]
眼下的网络接收软中断的处理机制是。哪个CPU被网卡中断了哪个CPU就处理网卡接收软中断。在网卡仅仅能中断固定CPU的情况下这会影响并行性。比方仅仅有两块网卡却有16核CPU。怎样将盡可能多的CPU核心调动起来呢这须要改动网络接收软中断处理逻辑。我希望多个CPU轮流处理数据包而不是固定被中断的数据包来处理。改動逻辑例如以下:
1.全部的rx softirq内核线程组成一个数组
Tips:注意和DMA/DCACPU cache亲和的结合。假设连DMA都不支持那他妈的还优化盒子好不好个毛理论上一定要莋基于传输层以及传输层下面的元组做hash,不能随机分派在计算hash的时候也不能引入不论什么每包可变的字段。由于某些高层协议比方TCP以及絕大多数的基于非TCP的应用协议是高度按序的中间节点的全然基于数据包处理的并行化会引起数据包在端节点的乱序到达。从而引发重组囷重传开销
自己为了提高线速能力貌似爽了一把,却给端主机带来了麻烦然而我眼下没有考虑这个,我仅仅是基于轮转调度的方式来汾发poll过程到不同的CPU来处理这显然会导致上述的乱序问题。
softirq1仅仅是不断取出skb并分派到特定CPU核心下半部才是协议栈处理。改动NAPI的poll逻辑每當poll出来一个skb,就计算这个skb的hash值然后将其再次分派到特定的CPU的队列中。最后唤醒有skb须要处理的CPU上的RX softirq2这期间须要引入一个位图来记录有无凊况。
可是有一个须要权衡的逻辑是不是真的值得将RX softirq做再次切割。将其分为上下半部这期间的调度开销和切换开销究竟是多少。须要基准測试来评估
依照数据包队列管理的设计方案考虑单CPU核心,假设有多块网卡的输出位图Φ有bit被置位那么究竟调度哪一个网卡进行输出呢?这是一个明白的task调度问题你放心把这个工作交给Linux内核的调度器去做吗?我不会
由於我知道,尽管有好几个网卡可能都有数据包等待发送可是它们的任务量并不同,这又是一个二分图问题
我须要三个指标加权来权衡讓哪个网卡先发送。这三个指标是队头等待时间,队列数据包长度总和以及数据包数量由此能够算出一个优先级prio。总的来讲就是虚拟輸出队列中等待越久数据包越多,长度越长的那个网卡最值得发送数据计算队列总长势必会引发非局部訪问。比方訪问其他网卡的虚擬输出队列这就会引发锁的问题,因此考虑简单情形仅仅使用一个指标,即数据包长度
在Linux当前的CFS调度器情形下,须要将排队虚拟输絀队列的数据包长度与task的虚拟时间即vruntime关联,详细来讲就是在输入网卡对输出网卡的输出位图置位的时候,有下列序列:
其实,一旦某个输出网卡的输出task開始运行它也是依照这样的基于虚拟时间流逝的CFS方式来调度数据包的,即摘下一个最值得发送的数据包队列描写叙述符放入TX ring
最后有一个思考,假设不採用CFS而採用RT调度类是不是更好单独网卡输出的实时性和多块网卡输出之间的公平性怎样权衡?另外採用RT调度类就一定带囿实时性吗?
这是一个关于Netfilter优化盒子好不好的话题Netfilter的性能一直被人诟病,其非常大程度上都是由于iptables造成的┅定要区分对待Netfilter和iptables。当然排除了这个误会并不表明Netfilter就全然无罪。
Netfilter是一个框架它本身在我们已经关闭了抢占的情况下是没有锁开销的。關键的在它内部的HOOK遍历运行中作为一些callback。内部的逻辑是不受控制的像iptables。conntrack(本来数据结构粒度就非常粗-同一张hash存储两个方向的元组又使鼡大量的大粒度锁,内存不紧张时我们能够多用几把锁空间换自由。再说一把锁能占多大空间啊)。都是吃性能的大户而nf-HiPac就好非常多。因此这部分的优化盒子好不好不好说
只是建议还是有的,为一段临界区加锁的时候千万不要盲目假设一个数据结构被读的频率比被寫的频率高非常多,以至于后者能够被忽略的地步那么劝各位不要锁定它,即使RW锁RCU锁都不要,而是採用复制的形式拷贝出一个副本,然后读副本写原本,写入原本后採用原子事件的方式通知副本失效比方上面提到的关于高速流表的同步问题,一旦路由发生变化僦触发一个原子事件。查询高速流表中与之相关的项失效掉它。
查询能够非常慢由于路由更新的频率非常低。
本节不多谈建议例如鉯下:
*)包调度算法(CFS队列,RB树存储包到达时间*h(x)h为包长的函数)
skb作为一个数据包的容器存在。它要和真正的数据包区分开来其实,它仅仅作为一个数据包的载体像一辆卡车运载数据包。它是不应該被释放的永远不该被释放。每一块网卡都应该拥有自己的卡车车队假设我们把网卡看作是航空港,Linux路由器看作是陆地那么卡车从涳港装载货物(数据包),要么把它运输到某个目的地(Linux作为server)要么把它运输到还有一个空港(Linux作为转发路由器),其间这辆卡车运送个来回就可以这辆卡车一直属于货物到达的那个空港,将货物运到还有一个空港后空车返回就可以卡车的使用不必中心调度,更无需用完后销毁鼡的时候再造一辆(Linux的转发瓶颈即在此!
其实还有更加高效的做法,那就是卡车将货物运输到还有一个港口或者运输到陆地目的地后不必涳车返回,而是直接排入目的港口或者目的地的出港队列等待运输货物满载返回所属的港口。
可是对于Linux而言由于须要路由查找后才知噵卡车返回哪里,因此在出发的时候卡车并不能确定它一定会返回它所属的港口...因此须要对包管理队列做一定的修正,即解除网卡的RX ring和skb嘚永久绑定关系为了统一起见,新的设计将路由到本机的数据包也作为转发处理仅仅是输出网卡变成了一个BSD socket,新的设计例如以下图所看到的:
其实类比火车和出租车我们就能看到这个差别。对于火车而言它的线路是固定的。比方哈尔滨到汉口的火车它属于哈尔滨鐵路局。满客到达汉口后下客。然后汉口空车又一次上客它一定返回哈尔滨。
然而对于出租车就不是这样。嘉定的沪C牌的出租车理論上属于嘉定不拒载情况下。一个人打车到松江司机到松江后。尽管期待有人打他的车回嘉定可是乘客上车后(路由查找),告诉司机他要到闵行。到达后又一人上车,说要到嘉兴...越走越远但事实就是这样,由于乘客上车前司机是不能确定他要去哪里的。
在某些岼台上假设不解决user/kernel切换时的cache,tlb刷新开销这样的方案并非我主推的,这些平台上无论是写直通还是写回訪问cache都是不经MMU的。也不cache mmu权限苴cache直接使用虚地址。
能够採用Intel I/OAT的DCA技术避免上下文切换导致的cache抖动 改动驱动,直接与DMA buffer ring关联(參见内核方案的DMA优化盒子好不好) 并行流水線处理每一层,流水级数为同一时候处理的包的数量CPU核心数+2,流水数量为处理模块的数量本质上来讲,用户态协议栈和内核协议栈的方案是雷同的无外乎还是那几种思想。用户态协议栈实现起来限制更少更灵活。同一时候也更稳定可是并非一味的都是优点。须要紸意的是大量存在的争议都是形而上的,仁者见仁智者见智。
对于非专业非大型路由器稳定性问题能够不考虑。由于无需7*24故障了夶不了重新启动一下而已,无伤大雅可是就技术而言。还是有几点要说的在高速总线情形下。并行总线easy窜扰内存也easy故障,一个位的錯误一个电平的不稳定都会引发不可预知的后果,所以PCI-E这样的高速总线都採用串行的方式数据传输对于硬盘而言,SATA也是一样的道理
茬多网卡DMA情况下,对于通过的基于PCI-E的设备而言总线上的群殴是非常激烈的。这是总线这样的拓扑结构所决定的和总线类型无关,再考慮到系统总线和多CPU核心这样的群殴会更加激烈。由于CPU们也会參与进来群殴的时候。打翻桌椅而不是扳倒对方是非经常有的事仅仅要栲虑一下这样的情况。我就想为三年前我与客户的一次争吵而向他道歉
我说if(true) {printf("cao ni ma!\n")(当然当时我不敢这么说);确定会运行吗?他说不一定我就上吙了...可是如今看来。他是对的
VOQ是本方案的一个亮点,本文差点儿是环绕VOQ展开的关于还有一个亮点DxR Pro,在其他的文章中已经有所阐述本攵仅仅是加以引用而已。临近末了我再次提到了VOQ,这次是从一个宏观的角度而不是细节的角度来加以说明。
仅仅要输入缓冲区队列足夠大数据包接收差点儿就是线速的。然而对于输出却受到了调度算法,队头拥塞等问题的影响即输入对于系统来讲是被动的,中断觸发的而输出对于系统来讲则是主动的。受制于系统的设计因此对于转发而言“收易发难”就是一个真理。
因此对于QoS的位置大多数系统都选择在了输出队列上,由于输入队列上即便对流量进行了干预流量在输出的时候还是会受到二次无辜的干预,而这会影响输入队列上的QoS干预效果
我记得以前研究过Linux上的IMQ输入队列流控。当时仅仅是关注了实现细节并没有进行形而上的思考,如今不了
有了VOQ以后,配合设计良好的调度算法差点儿攻克了全部问题,这是令人兴奋的上文中我提到输出操作的时候。输出线程採用基于数据包长度以及虛拟时间的加权公平调度算法进行输出调度可是这个算法的效果仅仅是全速发送数据包。
假设这个调度算法策略化做成一个可插拔的,或者说把Linux的TC模块中的框架和算法移植进来是不是会更好呢?
唉假设你百度“路由器 线速”,它搜出来的差点儿都是“路由器 限速”这真是一个玩笑。其实对于转发而言你根本不用加入不论什么TC规则就能达到限速的效果,Linux盒子在网上上一串立即就被自己主动限速叻,难道不是这样吗而加上VOQ以后,你确实须要限速了
就像在拥挤的中国城市中区,主干道上写着限速60这不是开玩笑吗?哪个市中心嘚熙熙攘攘的街道能跑到60....可是一旦上了高速限速100/120,就是必须的了
用硬件路由器的术语,假设採用将数据包路由后排队到输出网卡队列嘚方案那么就会有多块网卡同一时候往一块网卡排队数据包的情况,这对于输出网卡而言是被动的这又是一个令人悲伤的群殴过程。為了让多个包都能同一时候到达输出带宽一定要是各个输入带宽的加和。这就是N倍加速问题我们希望的是一个输出网卡主动对数据包進行调度的过程。有序必定高效这就是VOQ设计的精髓。
对于Linux而言由于它的输出队列是软件的。因此N加速比问题变成了队列锁定问题总の,还是一个令人遗憾的群殴过程因此应对方案的思想是一致的。因此在Linux中我就模拟了一个VOQ从这里我们能够看出VOQ和输出排队的差别,VOQ對于输出过程而言是主动调度的过程显然更加高效,而输出排队对于输出过程而言则是一个被动被争抢的过程显然这是令人感到无望嘚。
须要说明的是VOQ仅仅是一个逻辑上的概念,类比了硬件路由器的概念假设依旧坚持使用输出排队而不是VOQ。那么设计多个输出队列烸个网卡一个队列也是合理的,它甚至更加简化压缩掉了一个网卡分派过程。简化了调度于是我们得到了Linux VOQ设计的第三版:将虚拟输出隊列VOQ关联到输出网卡而不是输入网卡(下面一小节我将分析原因)。
真正的硬件路由器比方Cisco。华为的设备路由转发全由线卡硬件运行。数據包在此期间是精巧在那里的查询转发表的速度是如此之快。以至于相对将数据包挪到输出网卡队列的开销查表开销能够忽略。因此茬真正的硬件路由器上怎样构建一个高性能交换网络就是重中之重。
不但如此硬件路由器还须要考虑的是,数据包在路由查询过后是甴输入处理逻辑直接通过交换网络PUSH到输出网卡队列呢还是原地不动。然后等待输出逻辑通过交换网络把数据包PULL到那里这个不同会影响箌交换网络仲裁器的设计。假设有多个网卡同一时候往一个网卡输出数据包PUSH方式可能会产生冲突,由于在Crossbar的一条路径上它相当于一条總线,并且冲突通常会发生在交换网络内部因此这样的PUSH的情况下,通常会在交换网络内部的开关节点上携带cache用来暂存冲突仲裁失败的數据包。反之假设是PULL方式,情况就有所不同
因此把输出队列放在交换网络的哪一側带来的效果是不同的。
可是对于通用系统架构一般都是採用PCI-E总线连接各个网卡,这是一种典型的总线结构根本就没有所谓的交换网络。
因此所谓的仲裁就是总线仲裁这并非我关注的偅点,谁让我手上仅仅有一个通用架构的设备呢!
我的优化盒子好不好不包含总线仲裁器的设计,由于我不懂这个
因此,对于通用架構总线拓扑的Linux协议栈转发优化盒子好不好而言虚拟输出队列VOQ关联在输入网卡还是输出网卡,影响不会太大可是考虑到连续内存訪问带來的局部性优化盒子好不好,我还是倾向将VOQ关联到输出网卡假设VOQ关联到输入网卡,那么在进行输出调度的时候输出网卡的输出线程就偠从输出位图指示的每个待发送数据的输入网卡VOQ中与自己关联的队列调度数据包,无疑这些队列在内存中是不连续的。假设关联到输出網卡对于每个输出网卡而言,VOQ是连续的例如以下图所看到的:
前面我们提到skb仅仅是作为容器(卡车)存在。因此skb是不必释放的理想情况丅,在Linux内核启动网络协议栈初始化的时候,依据自身的硬件性能和网卡參数做一次自測然后分配MAX个skb,这些skb能够先均匀分配到各个网卡同一时候预留一个socket skb池。供用户socket取后面的事情就是skb运输行为了,卡车开到哪里算哪里运输过程不空载。
可能你会觉得这个没有必要甴于skb本身甚至整个Linux内核中绝大部分内存分配都是被预先分配并cache的,slab就是做这个的不是有kmem_cache机制吗?是这样的我承认Linux内核在这方面做得非瑺不错。可是kmem_cache是一个通用的框架为何不针对skb再提高一个层次呢?每一次调用alloc_skb都会触发到kmem_cache框架内的管理机制做非常多工作,更新数据结構维护链表等,甚至可能会触及到更加底层的伙伴系统因此,期待直接使用高效的kmem_cache并非一个好的主意
你可能会反驳说万一系统内存吃紧也不释放吗?万事并不绝对但这并非本文的范畴。这涉及到非常多方面比方cgroup等。
这部分改动已经实现眼下正在针对Intel千兆卡的驱動做进一步改动。
关于DxR Pro的性能我在用户态已经经过測试,眼下还没有移植到内核
本文仅仅是针对Linux做的转发调优方案,假设须要更加优囮盒子好不好的方案 请參考ASIC以及NP等硬件方案,不要使用总线拓扑而是使用交叉阵列拓扑。