奈学：传授“带权重的负载均衡实现算法”独家设计思路

分布式系统中，大部分系统调用都会涉及到负载均衡，例如：客户端发往服务端的请求首先到达反向代理，然后反向代理再通过负载均衡算法将请求转发到业务系统；或者后端业务系统各模块间的调用前，也需要通过负载均衡算法选择到一个目标节点。

一般情况下，我们对负载均衡的要求就是均匀，确保调用方的请求流量能够均匀的发送到我们冗余部署的N个服务节点上，所以负载均衡的算法一般使用随机或轮询都可以保证被调用结点流量的均匀。

真实情况下，往往由于部署服务的服务器性能或资源分配等原因需要我们为服务结点设置不同的权重，权重高的结点可以分配多一些的流量，同时降低权重低的结点的流量比例。

这时负载均衡就不能简单的使用随机或者轮询了，需要添加对权重的支持。接下来我们分析几种带权重的负载均衡算法，并分析一下他们的优缺点：

一、使用随机数 

设计思路如下：首先经过负载均衡后选择到一个结点，然后我们根据权重值再做一道拦截，按权重按比例放行，实现按降低结点流量的效果。例如我们规定权重的范围从0到10之间，0拒绝，10放行。权重值越高，分配的流量就越多。

最简单的实现方案，可以使用随机值，假设设置目标结点的权重值为7，当结点被负载均衡选中后，我们生成一个0到10之间的随机数，小于7放行，大于7则不向目标结点发送请求，需要从新做负载均衡计算，由此实现了将目标结点的流量降低到原来的70%。

方案实现起来很简单，但问题也很明显，我们都知道生成随机数的计算会造成CPU的开销，计算权重又发生在RPC调用过程中，所以每次RPC请求都会额外的增加一次随机数计算，累积起来对CPU额外的开销就很大了。我们可以进一步优化一下。

二、随机数组

我们可以使用一个随机数组代替上文描述的生成随机数的策略，实现同样效果的同时能够减少CPU的计算量。接下来描述下随机数组算法，同样权重设计为0~10。

我们为每个被调用的结点都生成一个随机数组，数组长度为10。空间分配好后用0和1填充数组，0的个数与结点的权重值一样，同时要保证0在数组中出现的位置是随机的。

我们生成一个代表权重为“4”的随机数组（4个0），如下图所示：



和随机数方案类似，我们在完成负载均衡计算后，进行权重拦截。这个时候我们可以通过访问随机数组代替生成随机数的计算，方案描述如下：记录上一次访问随机数组的位置，取数组下一位置元素值，取到0则放行，1则拒绝，重新进行负载均衡计算。方案的思路是，轮询访问随机数组，到达随机效果。因为数组的内容是随机的。

这两种方案思路是一致的，都是在负载均衡计算后再加一道权重拦截。但这样的问题是流量控制不精确，无法实现精确个节点按权重比例分配流量。我们可以换个思路，实现精确的流量控制。

三、 轮询加权重负载策略

设计思路如下，设计一个权重因子，初始值为所有被调用的结点中最大权重值。负载均衡使用轮询算法，被选中结点权重值大于等于权重因子则可以调用，否则用下一结点的权重值与权重因子比较，一轮循环结束后如果没有选中结点，则降低权重因子，继续通过与权重因子比较进行选择，直到选中为止。权重因子降为0后，恢复为最大权重值。伪代码如下：



上述伪代码中几个变量意义如下：

• i：当前轮询的结点；

• n：可选择结点数量；

• cw：权重因子；

• gcd(s)：权重因子每次降低的步长；

• max(s)：所有结点中最大的权重值；

• W(si)：结点Si的权重值；

• Si：服务结点（S0~Sn-1，共n个）

权重因子的降低步长为所有结点权重值的最大公约数。

假设有4个结点，A，B，C，D，权重值分别为，8，6，4，2，各结点权重值得最大公约数为2，所以权重降低步长为2，通过上面的伪代码，我们推演下负载均衡的流量分配结果。

初始条件：

• 1、i从0开始循环；

• 2、权重因子为8（伪代码中初始化为0，减权重因子后小于0，被恢复为最大值）

第一次调用：i=0，A权重大于等于权重因子（8），可以调用A；

第二次调用：i=1，B权重小于8，不可以调用，继续循环；

......

第二次调用会选择哪个结点呢，以及后面的调用如何选择的，欢迎大家在评留言给出自己的推演结果。

扫码下方二维码领取更多免费课程及学习资料