负载均衡算法WeightedRoundRobin（加权轮询）简介及算法实
现
Nginx的负载均衡默认算法是加权轮询算法，本⽂简单介绍算法的逻辑，并给出算法的Java实现版本。
本⽂参考了。
算法简介
有三个节点{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}
始值{c=0,b=0,a=0}到7次调⽤后⼜回到{c=0,b=0,a=0}。
算法实现
下⾯附上笔者⾃⼰的Java版算法实现：
ample.demo.arithmetic;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.List;
6import java.util.Map;
7
8/**
9 * Created by caojun on 2018/2/20.
10 *
11 * 基本概念：
12 * weight: 配置⽂件中指定的该后端的权重，这个值是固定不变的。
13 * effective_weight: 后端的有效权重，初始值为weight。
14 * 在释放后端时，如果发现和后端的通信过程中发⽣了错误，就减⼩effective_weight。
15 * 此后有新的请求过来时，在选取后端的过程中，再逐步增加effective_weight，最终⼜恢复到weight。
16 * 之所以增加这个字段，是为了当后端发⽣错误时，降低其权重。
17 * current_weight:
18 * 后端⽬前的权重，⼀开始为0，之后会动态调整。那么是怎么个动态调整呢？
19 * 每次选取后端时，会遍历集中所有后端，对于每个后端，让它的current_weight增加它的effective_weight，
20 * 同时累加所有后端的effective_weight，保存为total。
21 * 如果该后端的current_weight是最⼤的，就选定这个后端，然后把它的current_weight减去total。
22 * 如果该后端没有被选定，那么current_weight不⽤减⼩。
23 *
24 * 算法逻辑：
25 * 1. 对于每个请求，遍历集中的所有可⽤后端，对于每个后端peer执⾏：
26 *    peer->current_weight += peer->effecitve_weight。
27 *    同时累加所有peer的effective_weight，保存为total。
28 * 2. 从集中选出current_weight最⼤的peer，作为本次选定的后端。
29 * 3. 对于本次选定的后端，执⾏：peer->current_weight -= total。
30 *
31*/
32public class RoundRobinByWeightLoadBalance {
33
34//约定的invoker和权重的键值对
35final private List<Node> nodes;
36
37public RoundRobinByWeightLoadBalance(Map<Invoker, Integer> invokersWeight){
38if (invokersWeight != null && !invokersWeight.isEmpty()) {
39            nodes = new ArrayList<>(invokersWeight.size());
40            invokersWeight.forEach((invoker, weight)->nodes.add(new Node(invoker, weight)));
41        }else
42            nodes = null;
43    }
44
45/**
46    * 算法逻辑：
47    * 1. 对于每个请求，遍历集中的所有可⽤后端，对于每个后端peer执⾏：
48    *    peer->current_weight += peer->effecitve_weight。
49    *    同时累加所有peer的effective_weight，保存为total。
50    * 2. 从集中选出current_weight最⼤的peer，作为本次选定的后端。
51    * 3. 对于本次选定的后端，执⾏：peer->current_weight -= total。
52    *
53    * @Return ivoker
54*/
55public Invoker select(){
56if (! checkNodes())
57return null;
58else if (nodes.size() == 1) {
59if ((0).invoker.isAvalable())
(0).invoker;
61else
62return null;
63        }
64        Integer total = 0;
65        Node nodeOfMaxWeight = null;
66for (Node node : nodes) {
67            total += node.effectiveWeight;
68            node.currentWeight += node.effectiveWeight;
69
70if (nodeOfMaxWeight == null) {
71                nodeOfMaxWeight = node;
72            }else{
73                nodeOfMaxWeight = nodeOfMaxWeightpareTo(node) > 0 ? nodeOfMaxWeight : node;
74            }
77        nodeOfMaxWeight.currentWeight -= total;
78return nodeOfMaxWeight.invoker;
79    }
80
81public void onInvokeSuccess(Invoker invoker){
82if (checkNodes()){
83            nodes.stream()
84                    .filter((Node node)->invoker.id().equals(node.invoker.id()))
85                    .findFirst()
86                    .get()
87                    .onInvokeSuccess();
88        }
89    }
90
91public void onInvokeFail(Invoker invoker){
92if (checkNodes()){
93            nodes.stream()
94                    .filter((Node node)->invoker.id().equals(node.invoker.id()))
95                    .findFirst()
96                    .get()
97                    .onInvokeFail();
98        }
99    }
100
101private boolean checkNodes(){
102return (nodes != null && nodes.size() > 0);
103    }
104
105public void printCurrenctWeightBeforeSelect(){
106if (checkNodes()) {
107final StringBuffer out = new StringBuffer("{");
108            nodes.forEach(node->out.append(node.invoker.id())
109                    .append("=")
110                    .append(node.currentWeight+node.effectiveWeight)
111                    .append(","));
112            out.append("}");
113            System.out.print(out);
114        }
115    }
116
117public void printCurrenctWeight(){
118if (checkNodes()) {
119final StringBuffer out = new StringBuffer("{");
120            nodes.forEach(node->out.append(node.invoker.id())
121                    .append("=")
122                    .append(node.currentWeight)
123                    .append(","));
124            out.append("}");
125            System.out.print(out);
126        }
127    }
weight的所有形式
128
129public interface Invoker{
130        Boolean isAvalable();
131        String id();
132    }
133
134private static class Node implements Comparable<Node>{
135final Invoker invoker;
136final Integer weight;
137        Integer effectiveWeight;
138        Integer currentWeight;
139
140        Node(Invoker invoker, Integer weight){
141this.invoker = invoker;
142this.weight = weight;
143this.effectiveWeight = weight;
144this.currentWeight = 0;
145        }
146
147        @Override
148public int compareTo(Node o) {
149return currentWeight > o.currentWeight ? 1 : (currentWeight.equals(o.currentWeight) ? 0 : -1); 150        }
151
152public void onInvokeSuccess(){
153if (effectiveWeight < this.weight)
154                effectiveWeight++;
155        }
156
157public void onInvokeFail(){
158            effectiveWeight--;
161
162public static void main(String[] args){
163        Map<Invoker, Integer> invokersWeight = new HashMap<>(3);
164        Integer aWeight = 4;
165        Integer bWeight = 2;
166        Integer cWeight = 1;
167
168        invokersWeight.put(new Invoker() {
169            @Override
170public Boolean isAvalable() {
171return true;
172            }
173            @Override
174public String id() {
175return "a";
176            }
177        }, aWeight);
178
179        invokersWeight.put(new Invoker() {
180            @Override
181public Boolean isAvalable() {
182return true;
183            }
184            @Override
185public String id() {
186return "b";
187            }
188        }, bWeight);
189
190        invokersWeight.put(new Invoker() {
191            @Override
192public Boolean isAvalable() {
193return true;
194            }
195            @Override
196public String id() {
197return "c";
198            }
199        }, cWeight);
200
201        Integer times = 7;
202        RoundRobinByWeightLoadBalance roundRobin = new RoundRobinByWeightLoadBalance(invokersWeight); 203for(int i=1; i<=times; i++){
204            System.out.print(new StringBuffer(i+"").append("    "));
205            roundRobin.printCurrenctWeightBeforeSelect();
206            Invoker invoker = roundRobin.select();
207            System.out.print(new StringBuffer("    ").append(invoker.id()).append("    "));
208            roundRobin.printCurrenctWeight();
209            System.out.println();
210        }
211    }
212 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。