QPS 比 Nginx 提升 60%,阿里 Tengine 负载均衡算法揭秘

阅读数:5482 2019 年 7 月 8 日 10:30

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

前言

在阿里七层流量入口接入层(Application Gateway)场景下, Nginx 官方的 Smooth Weighted Round-Robin(SWRR)负载均衡算法已经遭遇瓶颈。阿里自研 Tengine 通过实现新的负载均衡算法 Virtual Node Smooth Weighted Round-Robin(VNSWRR)解决了 SWRR 算法在阿里业务场景下的缺陷,而且 QPS 处理能力相对于 Nginx 官方的 SWRR 算法也提升了 60% 左右。

问题

接入层 Tengine 通过自研的动态 upstream 模块实现动态服务发现,即运行时动态感知后端应用机器扩缩容、权重调整和健康检查等信息。同时该功能可以做很多事情,比如用户可通过调整后端应用某台机器的权重从而达到线上真实引流压测目的。然而,这些操作在 Nginx 原生 SWRR 算法下却可能引起不可逆转的血案。

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

  • 在接入层(Application Gateway)场景下,Nginx 的负载均衡算法 SWRR 会导致权重被调高机器的 QPS 瞬间暴涨,如上图 App2-host-A 机器当权重调整为 2 时,某一时刻流量会集中转发到该机器;

  • Nginx 的 SWRR 算法的处理时间复杂度是 O(N),在大规模后端场景下 Nginx 的处理能力将线性下降;

综上所述,对接入层 Tengine 的负载均衡转发策略的改造及性能优化已迫在眉睫。

原生 SWRR 算法分析

在介绍案列之前,我们先简单介绍下 Nginx 的负载均衡算法 SWRR 转发策略及特点:

SWRR 算法全称是 Smooth Weighted Round-Robin Balancing,顾名思义该算法相比于其它加权轮询(WRR)算法多一个 smooth(平滑)的特性。

下面我们就一个简单的列子来描述下该算法:

假设有 3 台机器 A、B、C 权重分别为 5、1、1,其中数组 s 代表机器列表、n 代表机器数量,每个机器的 cw 初始化为 0、ew 初始化为机器权重、tw 代表本轮选择中所有机器的 ew 之和、best 表示本轮被选中的机器。简单的描述就是每次选择机器列表中 cw 值最大的机器,被选中机器的 cw 将会减去 tw,从而降低下次被选中的机会,简单的伪代码描述如下:

复制代码
best = NULL;
tw = 0;
for(i = random() % n; i != i || falg; i = (i + 1) % n) {
flag = 0;
s[i].cw += s[i].ew;
tw += s[i].ew;
if (best == NULL || s[i].cw > best->cw) {
best = &s[i];
}
}
best->cw -= tw;
return best;

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

其 SWRR 算法选择的顺序为:{ A, A, B, A, C, A, A }

而普通 WRR 算法选择的顺序可能为:{ C, B, A, A, A, A, A }

SWRR 相比于普通的 WRR 算法特点:平滑、分散 。

调高权重引发的血案

从上面的描述来看,SWRR 算法似乎已经比较完美了,但是在某些场景下还是有一定的缺陷,下面我们就一个真实的案列来看看它都有哪些缺陷:

一天早上,流量调度的同学匆忙的跑到我的工位,当时看他神色是尤为的紧张,心想肯定是出啥问题了。果不其然:“为啥我把中心机房某台机器的权重从 1 调整为 2 的时候,接入层 Tengine 并不是按照这个权重比例转发流量恩?”,当时被调高机器 QPS 变化趋势如下图所示:

注:其中深蓝色曲线表示权重被调高机器的 QPS 变化,浅绿色曲线表示该集群单机的平均 QPS。

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

当时看到这个流量趋势变化图的时候也是一脸茫然,不过好在有图有数据,那就可以先分析一下这个图的几个特征数字;由于部分数据敏感,详细数据分析就不在此处展开。直接描述其现象和原因:

被调高权重的机器当时被分发到的流量基本上是该应用机房总流量的 1/2,一段时间后该机器的流量才恢复到预期的权重比例。其原因就是由于接入层 Tengine 对后端机器信息的变化是动态感知热生效的,而 Nginx 官方的 SWRR 算法策略第一次会选择当前机器列表中权重最大的机器转发流量。从而进一步导致已感知到后端机器权重变化的接入层 Tengine 都会将第一个请求转发到权重被调高的机器上。

大规模下性能骤降

如下是在 upstream 里面配置 2000 个后端,在反向代理场景下压测 Nginx 的函数热点图如下所示。其中 ngx_http_upstream_get_peer 函数 CPU 消耗占比高达 39%,其原因是因为 SWRR 算法的选取机器的时间复杂度为 O(N) (其中 N 代表后端机器数量),这就相当于每个请求都要执行接近 2000 次循环才能找到对应本次转发的后端机器。

压测环境

  • CPU 型号:Intel® Xeon® CPU E5-2682 v4 @ 2.50GHz

  • 压测工具:./wrk -t25 -d5m -c500 ‘ http://ip/t2000

  • Tengine 核心配置:配置 2 个 worker 进程,压力源 – 长连接 --> Tengine/Nginx – 短连接 --> 后端

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

下面我们做个试验,控制变量是 upstream 里面配置的 server 数量,观察不同场景下 Nginx 的 QPS 处理能力以及响应时间 RT 变化情况。从图中可以发现当后端 upstream 里面的 server 数量每增加 500 台则 Nginx 的 QPS 处理能力下降 10% 左右,响应 RT 增长 1ms 左右。

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

从上面的分析基本上已经确认是 SWRR 算法存在如上两个缺陷,下面就开始解决;

改进的 VNSWRR 算法

虽然经典的 WRR 算法(如随机数方式实现)可以在时间复杂度上达到 O(1) ,而且也可以避免 SWRR 算法调高权重的选取缺陷。但是在某些场景下(如小流量)可能造成后端的流量不均等问题,尤其是在流量瞬间暴涨的场景下有太多不可确定性。于是就构思是否有一种算法即能拥有 SWRR 算法的平滑、分散特点,又能具备 O(1) 的时间复杂度。所以就有了 Virtual Node Smooth Weighted Round-Robin(VNSWRR)算法。

此处拿个列子来说明此算法:3 台机器 A、B、C 权重分别为 1、2、3,N 代表后端机器数 、TW 代表后端机器权重总和。

算法关键点

  • 虚拟节点初始化顺序严格按照 SWRR 算法选取,保证初始化列表里的机器能够分布足够散列;

  • 虚拟节点运行时分批初始化,避免密集型计算集中。每批次虚拟节点使用完后再进行下一批次虚拟节点列表初始化,每次只初始化 min(n, max) 个虚拟节点;

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

算法描述

  • Tengine 程序启动或者运行时感知后端机器信息变化时,则构建 TW 个虚拟节点且第一次只初始化 N 个节点(注:TW 代表后端机器权重之和,N 代表后端机器数);

  • 各个进程设置随机起点轮询位置,如上图的 Step 1 对应的列表其起点位置指向 B;

  • 当请求到达后从设置的随机起点 B 位置轮询虚拟节点列表,若轮询到已经初始化的虚拟节点数组的末尾(如上图的 Step2 红色箭头指向的位置),则初始化第二批虚拟节点(如上图 Step2 对应的红色节点),当所有虚拟节点初始化完后将不再做初始化工作(如上图的 Step3 对应的状态);

此方案不仅将算法时间复杂度从 O(N) 优化到 O(1) ,而且也避免了权重调高场景下带来的问题。如下图所示后端某台机器权重从 1 调整为 2 后,其 QPS 平滑的增长到预期比列。

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

算法效果比较

在同等压测环境下(wrk 压测工具、500 并发、长连接场景、upstream 配置 2000 个 server),Nginx 官方的 SWRR 算法 CPU 消耗占比高达 39%(ngx_http_upstream_get_peer 函数)。而 VNSWRR 算法在同等条件下 CPU 消耗占比只有 0.27% 左右(ngx_http_upstream_get_vnswrr 函数),显而易见 SWRR CPU 消耗要高出一个数量级。

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

在上述压测环境下,Nginx 官方的 SWRR 和改进的 VNSWRR 算法下的 QPS 处理能力如下图所示:其中 VNSWRR 的 QPS 处理能力相对于 SWRR 算法提升 60% 左右。

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

下面我们来做个试验,在 upstream 里配置 server 数量变化的场景下,对比 VNSWRR 和 SWRR 算法观察 Nginx 的 QPS 处理能力以及响应时间 RT 变化。

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

QPS比Nginx提升60%,阿里Tengine负载均衡算法揭秘

从图中可以发现在 SWRR 算法下当 upstream 里面的 server 数量每增加 500 台,则 Nginx 的 QPS 处理能力下降 10% 左右、响应 RT 增长 1ms 左右,而在 VNSWRR 算法下 Tengine 的 QPS 处理能力及 RT 基本上变化不大。

总结

正是这种大流量场景下才暴露出 Nginx 的一些问题,所谓业务与技术相辅相成,业务可促使新的技术诞生、新的技术赋能创造新的业务。VNSWRR 算法既拥有 SWRR 算法的平滑、分散特点,也避免了其缺陷。同时在新算法下时间复杂度也从 O(N) 调整为 O(1) ,在大规模场景下 VNSWRR 的 QPS 处理能力相对于 Nginx 官方的 SWRR 算法提升 60% 左右。

Tengine 已在 GitHub 开源,项目地址:

https://github.com/alibaba/tengine

作者简介

王发康(花名:毅松),GitHub ID @wangfakang ,Tengine 开源项目 maintainer,阿里巴巴技术专家,负责阿里巴巴 WEB 统一接入层的开发及维护。

收藏

评论

微博

用户头像
发表评论

注册/登录 InfoQ 发表评论

最新评论

用户头像
Geek_259d5a 2019 年 07 月 10 日 16:02 0 回复
这个场景,使用随机的wrr就行了,这么多nginx实例,每个实例的pv都不高,一个周期内可能只有1个请求,多nginx实例之间随机的结果一定符合期望分布,会足够分散,因为每个实例的pv不高,对于单实例来说,即使在某几个周期拿到相同的endpoint,于全局而言,还是期望分布,时间复杂度还是O(1)
用户头像
晨光影 2019 年 07 月 08 日 14:48 0 回复
基本上看懂了,但是仍然存在疑惑待解: 1.单机权重从1调到2,出现一段持续时间的1/2机房流量分配到权重调高的机器???但是从伪代码其实看不出来这一点。 2.复杂度降低:这个仍然存疑,原有算法因为使用了随机数,事实上虽然统计复杂度是O(N),但是这个评估没有考虑随机选取及找到首个符合要求的服务器的情况,所以此处说服性不够。至于O(1)复杂度也就是不用去检索,每次直接获取,并没有充分的说明(我看出来了意思,也就是列表初始化时权重和VN是正相关的,并且排列也是循环并基于权重的),所以这个应该需要明确的给出说明。
用户头像
感谢你的阅读,就你的疑惑下面一一做了说明: 1、首先只有权重调整的那一瞬间,被调高权重的机器的流量才会暴涨。原因:在SWRR算法初始状态下会选择机器列表中权重最大的机器转发流量。而Nginx是多进程模型,其中每个worker进程都是独立的按照SWRR算法选取后端机器转发流量的,这就会导致整个机器的流量都会转发到权重被提高的后端机器上。 2、Nginx原生的SWRR算法未使用随机数机制实现,其原因文中也有描述(可能导致流量不均等问题)。另外文章开始对SWRR算法已做过描述,其时间复杂度是O(N)。 0 回复
用户头像
InfoQ_d3ad733026c9 2019 年 07 月 08 日 12:30 0 回复
这篇文章显然只适用于部分场景,nginx原生的wrr算法,适用于权重upstream servers和proxy动态upstream,这篇文章提到的算法显然只适用于前者。即使对于前者,这个VNSWRR算法也没有考虑到访问fail的情况,一次访问fail可能会影响到原生wrr算法的选取权重。再说个极端的情况,在VNSWRR算法的初始化过程中,如果某个endpoint挂了,那么在这个序列中,这个endpoint将不会出现,即使该endpoint恢复了,也无法选取到,除非重新构建此序列 至于该算法所说的性能问题,当endpoint数量过多时,比如超过500,此时首先应该调整的是结构问题,比如使用多层代理,至多2层就可以支持500*500的endpoint
展开全部
用户头像
1、Nginx原生的算法使用的是SWRR,详细见: https://github.com/nginx/nginx/commit/52327e0627f49dbda1e8db695e63a4b0af4448b1 。 2、VNSWRR算法是适用于“权重upstream servers和proxy动态upstream”你说的这两种场景的,即使不带权重VNSWRR也是一样支持的,而且时间复杂度也是O(1)。另外VNSWRR和upstream的动静实现方式无关的。 3、VNSWRR初始化虚拟节点列表的时候是不会过滤掉down掉的机器,即虚拟列表里面是有全量的机器的,另外在get_peer的过程中会判断peer的状态进行来保证访问机器可用。所以不会出现你说的这种问题。 4、你描述的 “当endpoint数量过多时,比如超过500,此时首先应该调整的是结构问题,比如使用多层代理” 没有理解是怎么解决的。文中所述架构是这样的: 用户 ----> Nginx接入网关 ----> endpoind ,其中endpoint数量对应Nginx中upstream里server的个数,由于原生SWRR算法时间复杂度是O(N),所以会伴随单个upstream里面的server数量增加导致Nginx处理能力下降。 0 回复
用户头像
1、我的意思是,这个优化算法只是特定场景下有效果 2、proxy动态upstream是指,proxy后面配置变量,这个变量可能是某个域名,当执行到proxy handler时调用ngx_http_upstream_create_round_robin_peer去创建rr数组和链表,这个VNSWRR算法即使可以用,也没什么意义,它只对某一时间段固定的endpoint列表有意义 3、初始化的时候,即使不关心endpoint的状态,也做不到根据访问情况去动态调整weight,而nginx原生的wrr是可以的 4、你的数据也说明了,500个endpoint的时候,二者性能差距不大,是因为这点消耗比起其他操作来说不算大,如果endpoint太多,首先得考虑架构的问题;否则就算nginx没有性能问题,更新这么大的一个endpoint列表,下发压力也不小 5、当fail的endpoint比较多时,特别是占用的权重比较多时,这个VNSWRR算法的时间复杂度也会退化成O(M) 6、如果是流量倾斜问题,第一次random就可以解决问题,其实完全可以不用重新实现nginx的rr,endpoint序列注入的时候,在单进程上做随机化即可 0 回复
用户头像
您说的对,算法优化肯定是在某些场景下才会有效果的(比如时间复杂对是O(N)和O(N*N*N), 当N=1的时候,效果都一样)。同样第2-5几个疑问基本上也是和上面一样理解。针对问题6,VNSWRR就是通过类似这种方式来解决流量倾斜的问题,只是顺带优化了原算法的时间复杂度从O(N)到O(1)。 0 回复
查看更多
用户头像
Mark 马鑫 2019 年 07 月 08 日 12:18 0 回复
算法简单,同时能够很好地解决问题
没有更多了