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

阿里巴巴采用Tengine实现整个集团的统一接入层。Tengine最初使用Nginx官方的SWRR（Smooth Weighted Round-Robin）负载均衡算法时，发现在工程实践中其均衡效果并不好。Tengine 团队创新地实现了 VNSWRR（Virtual Node Smooth Weighted Round-Robin）算法，不仅达到了完美均衡的效果，还实现了 QPS 处理能力较 SWRR 算法有60%左右的提升。

• 对应算法代码 PR：

  https://github.com/alibaba/tengine/pull/1306

• Tengine 已被正式列入云原生软件基金会（CNCF）全景图（Landscape）

问题描述

---

Tengine 通过自研的动态 upstream 模块实现动态服务发现，即运行时动态感知后端应用机器扩缩容、权重调整和健康检查等信息。借助这些功能，用户可动态调整后端某台机器的权重而实现线上真实引流做压测的目的。然而，这类操作在 SWRR 算法下却可能引发意想不到的效果甚至出现线上故障。主要表现是：

• 导致权重被调高机器的 QPS 瞬间暴涨。比如，下图 App2-host-A 机器的权重调整为2时，流量会超出预期地集中转发到该机器。

• 在后端机器的规模相当大的场景下会出现 Tengine 对请求的处理能力线性下降。

SWRR 算法原理

---

SWRR 算法顾名思义，相比于加权轮询（WRR）算法多了一个 smooth（平滑）的特性。下面我们就一个简单的例子来描述该算法的效果。

假设有3台机器A、B、C权重分别为5、1、1，其中数组s代表机器列表、n代表机器数量，每个机器的 cw（current weight）初始化为0、ew（effective weight）初始化为机器权重、tw（total weight）代表本轮选择中所有机器的 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;

请求编号	选择前的权重值	被选中的server	选择后的权重值
0	{5,1,1}	A	{-2,1,1}
1	{3,2,2}	A	{-4,2,2}
2	{1,3,3}	B	{1,-4,3}
3	{6,-3,4}	A	{-1,-3,4}
4	{4,-2,5}	C	{4,-2,-2}
5	{9,-1,-1}	A	{2,-1,-1}
6	{7,0,0}	A	{0,0,0}

采用 SWRR 算法所选择的机器顺序为｛A, A, B, A, C, A, A｝，而 WRR 算法所选择的机器顺序是｛C, B, A, A, A, A, A｝。显然，相比之下 SWRR 算法下所选择的机器顺序将使得流量更加平滑、分散 。

调高权重引发的血案

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

一天早上，流量调度的同学匆忙的跑到我的工位，当时看他神色是尤为的紧张，心想肯定是出什么问题了。果不其然："为啥我把中心机房某台机器的权重从1调整为2的时候，Tengine 并不是按照该权重比例转发流量恩？"，如下图所示，权重被调高机器的 QPS 量瞬间冲高50倍。

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

当时看到该流量趋势变化图的时候也是一脸茫然，不过欣慰的是有图有数据，便可先分析下图中的几个特征数字。由于部分数据敏感，下面直接描述其现象和原因。

被调高权重的机器，其分发到的流量是该应用机房总流量的一半，一段时间后流量才恢复到预期的权重比例。其原因是由于 Tengine 对后端机器信息的变化是动态感知热生效的，而官方的SWRR 算法在初始状态下会选择当前机器列表中权重最大的机器进行转发流量。从而导致已感知到后端机器权重变化的 Tengine 都会将第一个请求转发到权重被调高的机器上。

大规模下性能骤降

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

压测环境

CPU型号：Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz

压测工具：./wrk -t25  -d5m -c500  'http://ip/t2000'

请求链路：压力源 --keepalive--> Tengine --no keepalive--> 后端

Tengine核心配置：

worker_processes 2;
keepalive_timeout 65;
http {
   upstream endpoint {server0; …… server1999;}  # 2000 back-end.
   server {
       listen 80;
       location / {proxy_pass http://endpoint;}
   }
}

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

上面的分析结果来看，已经确认是 SWRR 算法在特定场景下存在弊端。然而在阿里巴巴双11大规模场景下这绝对是一场灾难，下面一起来看看阿里巴巴 Tengine 团队是如何通过算法优化的方式保证双11流量如丝般顺滑。

改进的 VNSWRR 算法

---

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

此处拿个列子来描述下新算法实现原理，比如有3台机器A、B、C，其权重分别为1、2、3，n代表后端机器数 、tw 代表后端机器权重总和。

算法关键点

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

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

算法描述

• 在 Tengine 程序启动或运行时感知后端机器信息变化时，则构建 tw 个虚拟节点且第一次只初始化 n 个节点（tw 代表后端机器权重之和，n 代表后端机器数）；

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

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

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

算法效果比较

---

在同等压测环境下，SWRR 算法的 CPU 消耗占比高达39%（ngx_http_upstream_get_peer函数），而VNSWRR算法在同等条件下CPU消耗占比只有0.27%（ngx_http_upstream_get_vnswrr函数）。显而易见，SWRR CPU 消耗要高出一个数量级。

上述压测环境下，VNSWRR 的 QPS 处理能力相对于 SWRR 算法提升60%左右，如下图所示。

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

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

总结

---

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

 本文作者：

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

本文缩略图：icon by 王_云_飞，来源阿里中间件。

活动推荐：

21CTO学院PHP全栈工程师训练营第六届（秋季班）热招中

21CTO学院PHP全栈开发训练营正在招生，由21CTO创始人洛逸以及技术大牛授课，课程以程序员学习曲线为出发点，以高真实的项目实践为核心，以学员能够高薪就业为目标。此次招生名额有限，报名就有机会进入一线互联网公司。