前言在阿里七层流量入口接入层（应用网关）场景下，Nginx官方的SmoothWeightedRound-Robin（SWRR）负载均衡算法已经无法完美使用它的技能。通过实现一种新的负载均衡算法VirtualNodeSmoothedRound-Robin(VNSWRR)，Tengine不仅优雅地解决了SWRR算法的缺陷，而且相比Nginx官方的SWRR算法，QPS处理能力提升了约60%。问题接入层Tengine通过自研的动态upstream模块实现动态服务发现，即在运行时动态感知后端应用机器扩缩容、权重调整、健康检查等信息。同时，这个函数可以做很多事情。例如，用户可以在后台应用中调整某台机器的权重，达到真正在线引流和压力测试的目的。但是这些操作在Nginx原生的SWRR算法下可能会造成不可逆的流血。在接入层（应用网关）场景下，Nginx的负载均衡算法SWRR会导致权重提升的机器QPS瞬间暴涨。如上图，当App2-host-A机器的权重调整为2时，流量会在某个时刻集中转发到这台机器；Nginx的SWRR算法的处理时间复杂度为O(N)，在后端大规模场景下Nginx的处理能力会线性下降；系统的改造和性能优化迫在眉睫。NativeSWRR算法分析在介绍案例之前，先简单介绍一下Nginx的负载均衡算法SWRR的转发策略和特点：SWRR算法的全称是SmoothWeightedRound-RobinBalancing。顾名思义，这个算法比起其他加权循环（WRR）算法多了一个平滑（smooth）的特性。下面用一个简单的例子来描述一下算法：假设有3台机器A、B、C，权重分别为5、1、1，其中数组s代表机器列表，n代表机器数量，初始化每台机器的cw为0，ew初始化为机器的权重，tw代表本轮选出的所有机器的ew之和，最能代表本轮选出的机器。简单的描述就是每次选中机器列表中cw值最大的机器时，tw都会减去选中机器的cw，从而减少下次被选中的几率。简单的伪代码描述如下：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;returnbest;requestnumberselection之前的权重值由服务器选择。选择后的权重值为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}与普通WRR算法相比，SWRR的特点是平滑、分散。从上面的描述来看，SWRR算法似乎是比较完善的，但是在某些场景下还是存在一定的缺陷。我们举一个真实的案例，看看它有什么缺陷：一天早上，交通调度员匆匆来到我的车站。他当时看起来很紧张，我想一定是出什么问题了。果然：“为什么我把中心机房某台机器的权重从1调整为2，接入层Tengine没有按照这个权重比例转发流量？”，被调整的机器的QPS变化趋势此时如下图所示：注：深蓝色曲线表示权重增加后机器的QPS变化，浅绿色曲线表示集群中单机的平均QPS。当时看到这张流量趋势变化图我是一头雾水，好在有图有数据，可以先分析一下这张图的几个特征数；由于部分数据比较敏感，这里不进行详细的数据分析。直接描述现象和原因：分配给增加权重的机器的流量基本是申请房间总流量的1/2，一段时间后机器的流量又恢复到预期的权重比例。原因是接入层的Tengine动态感知后端机器信息的变化，Nginx官方的SWRR算法策略会选择当前机器列表中权重最高的机器进行第一次转发。因此，感知到后端机器权重变化的接入层Tengine会将第一个请求转发给权重增加的机器。大规模性能下降如下：上游配置2000个后端，反向代理场景下Nginx压测功能热图如下图。其中ngx_http_upstream_get_peer函数的CPU消耗占比高达39%。原因是SWRR算法选择机器的时间复杂度为O(N)（其中N代表后端机器数），相当于每次请求。需要2000个周期才能找到本次转发对应的后端机器。压测环境CPU型号：Intel(R)Xeon(R)CPUE5-2682v4@2.50GHz压测工具：./wrk-t25-d5m-c500'http://ip/t2000'Tengine核心配置：Configuration2一个worker进程，压力源--长连接-->Tengine/Nginx--短连接-->后端下面做个实验，控制变量是上游配置的服务器数量，观察QPS处理能力Nginx在不同场景下响应时间RT的变化。从图中可以看出，当后端upstream服务器数量增加500台时，Nginx的QPS处理能力会下降10%左右，响应RT会增加1ms左右。从上面的分析，基本可以确定SWRR算法存在以上两个缺陷，下面开始解决；改进的VNSWRR算法虽然经典的WRR算法（如随机数实现）在时间复杂度上可以达到O(1)，并且也可以避免SWRR算法增加权重的选择缺陷。但是在某些场景下（比如小流量），可能会造成后端流量不均匀，尤其是在流量瞬时暴增，不确定因素太多的场景下。于是我构思是否有一种算法，既能具有SWRR算法的平滑和离散特性，又能具有O(1)的时间复杂度。于是就有了虚拟节点平滑加权循环（VNSWRR）算法。下面举个例子来说明这个算法：A、B、C三台机器的权重分别为1、2、3，N代表后端机器的数量，TW代表后端机器的权重之和后端机器。算法要点虚拟节点的初始化顺序严格按照SWRR算法选择，保证初始化列表中的机器能够分发足够的哈希值；虚拟节点运行时，分批初始化，避免密集计算。每一批虚拟节点用完后，进行下一批虚拟节点列表初始化，每次只初始化min(n,max)个虚拟节点；算法说明当Tengine程序启动或运行时感知到后端机器信息发生变化，则构造TW个虚拟节点，第一次只初始化N个节点（注：TW表示后端机器权重之和，N表示后端机器数量）；每个进程设置一个随机的起始点轮询位置，如上图中第1步列表的起始点指向B；当请求到达时，从设定的随机起点B开始轮询虚拟节点列表，如果轮询到已初始化的虚拟节点数组的末尾（如上文步骤2中红色箭头所示），则初始化第二批虚拟节点（如上图中Step2对应的红色节点）在所有虚拟节点都初始化完成后（如上图中Step3对应的状态）不会进行初始化工作；该方案不仅将算法时间复杂度从O(N)优化为O(1)，也避免了权重增加场景带来的问题。如下图所示，后端某台机器的权重从1调整为2后，其QPS平滑提升至预期比例。算法效果对比在相同的压测环境下（wrk压测工具，500并发，长连接场景，upstream配置2000台服务器），Nginx官方的SWRR算法消耗CPU高达39%（ngx_http_upstream_get_peer函数）。而VNSWRR算法在相同条件下（ngx_http_upstream_get_VNSWRR函数）CPU消耗仅为0.27%左右，可见SWRRCPU消耗要高出一个数量级。在上述压测环境下，Nginx官方SWRR和改进后的VNSWRR算法的QPS处理能力如下图所示：VNSWRR的QPS处理能力比SWRR算法提升了60%左右。接下来我们做一个实验，对比一下VNSWRR和SWRR算法，观察在上游配置的服务器数量发生变化的场景下，Nginx的QPS处理能力和响应时间RT的变化。从图中可以看出，在SWRR算法下，当上游服务器数量增加500台时，Nginx的QPS处理能力下降约10%，响应RT增加约1ms，而在VNSWRR下算法，Tengine的QPS处理能力和RT基本变化不大。综上所述，就是在这种大流量的场景下，暴露了Nginx的一些问题。所谓业务与技术相辅相成，业务可以促进新技术的诞生，新技术可以创造新的业务。VNSWRR算法既具有SWRR算法的平滑和离散特性，又避免了其缺陷。同时，在新算法下，时间复杂度也从O(N)调整为O(1)。在大规模场景下，VNSWRR的QPS处理能力比Nginx官方的SWRR算法提升了60%左右。本文作者：王发康（花名：一松），GitHubID@wangfakang，Tengine开源项目维护者，阿里巴巴技术专家，负责阿里巴巴WEB统一接入层的开发和维护。
