前言

在阿里七层流量入口接入层（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 算法下却可能引起不可逆转的血案。

在接入层（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;

其 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。

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

被调高权重的机器当时被分发到的流量基本上是该应用机房总流量的 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 – 短连接 --> 后端

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

从上面的分析基本上已经确认是 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) 个虚拟节点；

算法描述

Tengine 程序启动或者运行时感知后端机器信息变化时，则构建 TW 个虚拟节点且第一次只初始化 N 个节点（注：TW 代表后端机器权重之和，N 代表后端机器数）；
各个进程设置随机起点轮询位置，如上图的 Step 1 对应的列表其起点位置指向 B；
当请求到达后从设置的随机起点 B 位置轮询虚拟节点列表，若轮询到已经初始化的虚拟节点数组的末尾（如上图的 Step2 红色箭头指向的位置），则初始化第二批虚拟节点（如上图 Step2 对应的红色节点），当所有虚拟节点初始化完后将不再做初始化工作（如上图的 Step3 对应的状态）；

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

算法效果比较

在同等压测环境下（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 消耗要高出一个数量级。

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

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

从图中可以发现在 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 统一接入层的开发及维护。

创作场景

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