阿里云算法服务器(阿里算法面试)

 cbzntkk   2021-11-25 09:00   17 人阅读  0 条评论

2.jpg

1.jpg










前言。在阿里七层流量入口接入层()场景下,官方的-()负载均衡算法已经无法再完美施展它的技能。通过实现新的负载均衡算法-()不仅优雅的解决了算法的缺陷,而且处理能力相对于官方的算法提升了60%左右。问题。接入层通过自研的动态模块实现动态服务发现,即运行时动态感知后端应用机器扩缩容、权重调整和健康检查等信息。同时该功能可以做很多事情,比如用户可通过调整后端应用某台机器的权重从而达到线上真实引流压测目的。然而,这些操作在原生算法下却可能引起不可逆转的血案。在接入层()场景下,的负载均衡算法会导致权重被调机器的瞬间暴涨,如上图2--机器当权重调整为2时,某一时刻流量会集中转发到该机器;的算法的处理时间复杂度是(),在大规模后端场景下的处理能力将线下降;综上所述,对接入层的负载均衡转发策略的改造及能优化已迫在眉睫。

原生算法分析。在介绍案列之前,我们先简单介绍下的负载均衡算法转发策略及特点:算法全称是-,顾名思义该算法相比于其它加权轮询()算法多一个(平滑)的特。下面我们就一个简单的列子来描述下该算法:假设有3台机器、、权重分别为5、1、1,其中数组代表机器列表、代表机器数量,每个机器的初始化为0、初始化为机器权重、代表本轮选择中所有机器的之和、表示本轮被选中的机器。简单的描述就是每次选择机器列表中值最大的机器,被选中机器的将会减去,从而降低下次被选中的机会,简单的伪代码描述如下:=;=0;(=()%;=||;=(+1)%){=0;.。+=.。+=.。(==||.。

;-;){=;}}-;-=;请求编号选择前的权重值被选中的选择后的权重值。0{5,1,1}{-2,1,1}。1{3,2,2}{-4,2,2}。2{1,3,3}{1,-4,3}。3{6,-3,4}{-1,-3,4}。4{4,-2,5}{4,-2,-2}。

5{9,-1,-1}{2,-1,-1}。6{7,0,0}{0,0,0}。其算法选择的顺序为:{,}。

而普通算法选择的顺序可能为:{,}。相比于普通的算法特点:平滑、分散。调权重引发的血案。从上面的描述来看,算法似乎已经比较完美了,但是在某些场景下还是有一定的缺陷,下面我们就一个真实的案列来看看它都有哪些缺陷:一天早上,流量调度的同学匆忙的跑到我的工位,当时看他神是尤为的紧张,心想肯定是出啥问题了。果不其然:为啥我把中心机房某台机器的权重从1调整为2的时候,接入层并不是按照这个权重比例转发流量恩。当时被调机器变化趋势如下图所示:注:其中深蓝曲线表示权重被调机器的变化,浅绿曲线表示该集群单机的平均。当时看到这个流量趋势变化图的时候也是一脸茫然,不过好在有图有数据,那就可以先分析一下这个图的几个特征数字;由于分数据敏感,详细数据分析就不在此处展开。直接描述其现象和原因:被调权重的机器当时被分发到的流量基本上是该应用机房总流量的12,一段时间后该机器的流量才恢复到预期的权重比例。

其原因就是由于接入层对后端机器信息的变化是动态感知热生效的,而官方的算法策略第一次会选择当前机器列表中权重最大的机器转发流量。从而进一步导致已感知到后端机器权重变化的接入层都会将第一个请求转发到权重被调的机器上。大规模下能骤降。

如下是在里面配置2000个后端,在反向代理场景下压测的函数热点图如下所示。其中____函数消耗占比达39%,其原因是因为算法的选取机器的时间复杂度为()(其中代表后端机器数量),这就相当于每个请求都要接近2000次循环才能找到对应本次转发的后端机器。压测环境。型号:()()5-26824@2.50。压测工具:-25-5-500''。核心配置:配置2个进程,压力源--长连接--;--短连接--;后端。下面我们做个试验,控制变量是里面配置的数量,观不同场景下的处理能力以及响应时间变化情况。从图中可以发现当后端里面的数量每增加500台则的处理能力下降10%左右,响应增长1左右。

从上面的分析基本上已经确认是算法存在如上两个缺陷,下面就开始解决;改进的算法。虽然经典的算法(如随机数方式实现)可以在时间复杂度上达到(1),而且也可以避免算法调权重的选取缺陷。但是在某些场景下(如小流量)可能造成后端的流量不均等问题,尤其是在流量瞬间暴涨的场景下有太多不可确定。

于是就构思是否有一种算法即能拥有算法的平滑、分散特点,又能具备(1)的时间复杂度。所以就有了-()算法。此处拿个列子来说明此算法:3台机器、、权重分别为1、2、3,代表后端机器数、代表后端机器权重总和。算法关键点。

虚拟节点初始化顺序严格按照算法选取,保证初始化列表里的机器能够分布足够散列;虚拟节点运行时分批初始化,避免密集型计算集中。每批次虚拟节点使用完后再进行下一批次虚拟节点列表初始化,每次只初始化(,)个虚拟节点;算法描述。程序启动或者运行时感知后端机器信息变化时,则构建个虚拟节点且第一次只初始化个节点(注:代表后端机器权重之和,代表后端机器数);各个进程设置随机起点轮询位置,如上图的1对应的列表其起点位置指向;当请求到达后从设置的随机起点位置轮询虚拟节点列表,若轮询到已经初始化的虚拟节点数组的末尾(如上图的2红箭头指向的位置),则初始化第二批虚拟节点(如上图2对应的红节点),当所有虚拟节点初始化完后将不再做初始化工作(如上图的3对应的状态);此方案不仅将算法时间复杂度从()优化到(1),而且也避免了权重调场景下带来的问题。如下图所示后端某台机器权重从1调整为2后,其平滑的增长到预期比列。

算法效果比较。在同等压测环境下(压测工具、500并发、长连接场景、配置2000个),官方的算法消耗占比达39%(____函数)。而算法在同等条件下消耗占比只有0.27%左右(____函数),显而易见消耗要出一个数量级。在上述压测环境下,官方的和改进的算法下的处理能力如下图所示:其中的处理能力相对于算法提升60%左右。下面我们来做个试验,在里配置数量变化的场景下,对比和算法观的处理能力以及响应时间变化。

<=_=640_=270=0=提升60%,阿里巴巴轻量级开源服务器负载均衡算法=:.。

本文地址:http://www.tpm-china.org/post/23440.html
版权声明:本文为原创文章,版权归 cbzntkk 所有,欢迎分享本文,转载请保留出处!

 发表评论


表情

还没有留言,还不快点抢沙发?