负载均衡算法WeightedRoundRobin(加权轮询)简介及算法实现

Nginx的负载均衡默认算法是加权轮询算法，本文简单介绍算法的逻辑，并给出算法的Java实现版本。

本文参考了Nginx的负载均衡 - 加权轮询 (Weighted Round Robin)。

算法简介

有三个节点{a, b, c}，他们的权重分别是{a=5, b=1, c=1}。发送7次请求，a会被分配5次，b会被分配1次，c会被分配1次。

一般的算法可能是：

1、轮训所有节点，找到一个最大权重节点；

2、选中的节点权重-1；

3、直到减到0，恢复该节点原始权重，继续轮询；

这样的算法看起来简单，最终效果是：{a, a, a, a, a, b, c}，即前5次可能选中的都是a，这可能造成权重大的服务器造成过大压力的同时，小权重服务器还很闲。

Nginx的加权轮询算法将保持选择的平滑性，希望达到的效果可能是{a, b, a, a, c, a, a}，即尽可能均匀的分摊节点，节点分配不再是连续的。

Nginx加权轮询算法

1、概念解释，每个节点有三个权重变量，分别是：

(1) weight: 约定权重，即在配置文件或初始化时约定好的每个节点的权重。

(2) effectiveWeight: 有效权重，初始化为weight。

在通讯过程中发现节点异常，则-1；

之后再次选取本节点，调用成功一次则+1，直达恢复到weight；

此变量的作用主要是节点异常，降低其权重。

(3) currentWeight: 节点当前权重，初始化为0。

2、算法逻辑

(1) 轮询所有节点，计算当前状态下所有节点的effectiveWeight之和totalWeight；

(2) currentWeight = currentWeight + effectiveWeight; 选出所有节点中currentWeight中最大的一个节点作为选中节点；

(3) 选中节点的currentWeight = currentWeight - totalWeight；

基于以上算法，我们看一个例子：

这时有三个节点{a, b, c}，权重分别是{a=4, b=2, c=1}，共7次请求，初始currentWeight值为{0, 0, 0}，每次分配后的结果如下：

请求序号	请求前currentWeight值	选中节点	请求后currentWeight值
1	{c=1,b=2,a=4}	a	{c=1,b=2,a=-3}
2	{c=2,b=4,a=1}	b	{c=2,b=-3,a=1}
3	{c=3,b=-1,a=5}	a	{c=3,b=-1,a=-2}
4	{c=4,b=1,a=2}	c	{c=-3,b=1,a=2}
5	{c=-2,b=3,a=6}	a	{c=-2,b=3,a=-1}
6	{c=-1,b=5,a=3}	b	{c=-1,b=-2,a=3}
7	{c=0,b=0,a=7}	a	{c=0,b=0,a=0}

观察到七次调用选中的节点顺序为{a, b, a, c, a, b, a}，a节点选中4次，b节点选中2次，c节点选中1次，算法保持了currentWeight值从初始值{c=0,b=0,a=0}到7次调用后又回到{c=0,b=0,a=0}。

算法实现

下面附上笔者自己的Java版算法实现：

 package com.example.demo.arithmetic;

 import java.util.ArrayList;

 import java.util.HashMap;

 import java.util.List;

 import java.util.Map;

 /**

  * Created by caojun on 2018/2/20.

  *

  * 基本概念：

  * weight: 配置文件中指定的该后端的权重，这个值是固定不变的。

  * effective_weight: 后端的有效权重，初始值为weight。

  * 在释放后端时，如果发现和后端的通信过程中发生了错误，就减小effective_weight。

  * 此后有新的请求过来时，在选取后端的过程中，再逐步增加effective_weight，最终又恢复到weight。

  * 之所以增加这个字段，是为了当后端发生错误时，降低其权重。

  * current_weight:

  * 后端目前的权重，一开始为0，之后会动态调整。那么是怎么个动态调整呢？

  * 每次选取后端时，会遍历集群中所有后端，对于每个后端，让它的current_weight增加它的effective_weight，

  * 同时累加所有后端的effective_weight，保存为total。

  * 如果该后端的current_weight是最大的，就选定这个后端，然后把它的current_weight减去total。

  * 如果该后端没有被选定，那么current_weight不用减小。

  *

  * 算法逻辑：

  * 1. 对于每个请求，遍历集群中的所有可用后端，对于每个后端peer执行：

  *     peer->current_weight += peer->effecitve_weight。

  *     同时累加所有peer的effective_weight，保存为total。

  * 2. 从集群中选出current_weight最大的peer，作为本次选定的后端。

  * 3. 对于本次选定的后端，执行：peer->current_weight -= total。

  *

  */

 public class RoundRobinByWeightLoadBalance {

     //约定的invoker和权重的键值对

     final private List<Node> nodes;

     public RoundRobinByWeightLoadBalance(Map<Invoker, Integer> invokersWeight){

         if (invokersWeight != null && !invokersWeight.isEmpty()) {

             nodes = new ArrayList<>(invokersWeight.size());

             invokersWeight.forEach((invoker, weight)->nodes.add(new Node(invoker, weight)));

         }else

             nodes = null;

     }

     /**

      * 算法逻辑：

      * 1. 对于每个请求，遍历集群中的所有可用后端，对于每个后端peer执行：

      *     peer->current_weight += peer->effecitve_weight。

      *     同时累加所有peer的effective_weight，保存为total。

      * 2. 从集群中选出current_weight最大的peer，作为本次选定的后端。

      * 3. 对于本次选定的后端，执行：peer->current_weight -= total。

      *

      * @Return ivoker

      */

     public Invoker select(){

         if (! checkNodes())

             return null;

         else if (nodes.size() == 1) {

             if (nodes.get(0).invoker.isAvalable())

                 return nodes.get(0).invoker;

             else

                 return null;

         }

         Integer total = 0;

         Node nodeOfMaxWeight = null;

         for (Node node : nodes) {

             total += node.effectiveWeight;

             node.currentWeight += node.effectiveWeight;

             if (nodeOfMaxWeight == null) {

                 nodeOfMaxWeight = node;

             }else{

                 nodeOfMaxWeight = nodeOfMaxWeight.compareTo(node) > 0 ? nodeOfMaxWeight : node;

             }

         }

         nodeOfMaxWeight.currentWeight -= total;

         return nodeOfMaxWeight.invoker;

     }

     public void onInvokeSuccess(Invoker invoker){

         if (checkNodes()){

             nodes.stream()

                     .filter((Node node)->invoker.id().equals(node.invoker.id()))

                     .findFirst()

                     .get()

                     .onInvokeSuccess();

         }

     }

     public void onInvokeFail(Invoker invoker){

         if (checkNodes()){

             nodes.stream()

                     .filter((Node node)->invoker.id().equals(node.invoker.id()))

                     .findFirst()

                     .get()

                     .onInvokeFail();

         }

     }

     private boolean checkNodes(){

         return (nodes != null && nodes.size() > 0);

     }

     public void printCurrenctWeightBeforeSelect(){

         if (checkNodes()) {

             final StringBuffer out = new StringBuffer("{");

             nodes.forEach(node->out.append(node.invoker.id())

                     .append("=")

                     .append(node.currentWeight+node.effectiveWeight)

                     .append(","));

             out.append("}");

             System.out.print(out);

         }

     }

     public void printCurrenctWeight(){

         if (checkNodes()) {

             final StringBuffer out = new StringBuffer("{");

             nodes.forEach(node->out.append(node.invoker.id())

                     .append("=")

                     .append(node.currentWeight)

                     .append(","));

             out.append("}");

             System.out.print(out);

         }

     }

     public interface Invoker{

         Boolean isAvalable();

         String id();

     }

     private static class Node implements Comparable<Node>{

         final Invoker invoker;

         final Integer weight;

         Integer effectiveWeight;

         Integer currentWeight;

         Node(Invoker invoker, Integer weight){

             this.invoker = invoker;

             this.weight = weight;

             this.effectiveWeight = weight;

             this.currentWeight = 0;

         }

         @Override

         public int compareTo(Node o) {

             return currentWeight > o.currentWeight ? 1 : (currentWeight.equals(o.currentWeight) ? 0 : -1);

         }

         public void onInvokeSuccess(){

             if (effectiveWeight < this.weight)

                 effectiveWeight++;

         }

         public void onInvokeFail(){

             effectiveWeight--;

         }

     }

     public static void main(String[] args){

         Map<Invoker, Integer> invokersWeight = new HashMap<>(3);

         Integer aWeight = 4;

         Integer bWeight = 2;

         Integer cWeight = 1;

         invokersWeight.put(new Invoker() {

             @Override

             public Boolean isAvalable() {

                 return true;

             }

             @Override

             public String id() {

                 return "a";

             }

         }, aWeight);

         invokersWeight.put(new Invoker() {

             @Override

             public Boolean isAvalable() {

                 return true;

             }

             @Override

             public String id() {

                 return "b";

             }

         }, bWeight);

         invokersWeight.put(new Invoker() {

             @Override

             public Boolean isAvalable() {

                 return true;

             }

             @Override

             public String id() {

                 return "c";

             }

         }, cWeight);

         Integer times = 7;

         RoundRobinByWeightLoadBalance roundRobin = new RoundRobinByWeightLoadBalance(invokersWeight);

         for(int i=1; i<=times; i++){

             System.out.print(new StringBuffer(i+"").append("    "));

             roundRobin.printCurrenctWeightBeforeSelect();

             Invoker invoker = roundRobin.select();

             System.out.print(new StringBuffer("    ").append(invoker.id()).append("    "));

             roundRobin.printCurrenctWeight();

             System.out.println();

         }

     }

 }

巴特西

负载均衡算法WeightedRoundRobin(加权轮询)简介及算法实现

最新文章

热门文章