常见的轮询算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class ServerIps {
public static final Map<String, Integer> WEIGHT_LIST = new HashMap<>();
static {
WEIGHT_LIST.put("192.168.0.1", 2);
WEIGHT_LIST.put("192.168.0.2", 8);
WEIGHT_LIST.put("192.168.0.3", 3);
WEIGHT_LIST.put("192.168.0.4", 6);
WEIGHT_LIST.put("192.168.0.5", 5);
WEIGHT_LIST.put("192.168.0.6", 5);
WEIGHT_LIST.put("192.168.0.7", 4);
WEIGHT_LIST.put("192.168.0.8", 7);
WEIGHT_LIST.put("192.168.0.9", 2);
WEIGHT_LIST.put("192.168.0.10", 9);
}
}
|
Random–完全随机算法
缺点：所有服务器的访问概率都是相同的。
1
2
3
4
5
6
7
8
9
10
11
12
| public class RandomLoadBalancing {
public static String getServer() {
int randomPos = ThreadLocalRandom.current().nextInt(ServerIps.LIST.size());
return ServerIps.LIST.get(randomPos);
}
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
System.out.println(getServer());
}
}
}
|
WeightedRandom–加权随机算法
缺点：权重低的服务器可能很长一段时间都访问不到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class WeightRandomLoadBalancing {
private static String getServer() {
ArrayList<String> iplist = new ArrayList<>();
ServerIps.WEIGHT_LIST.forEach((k, v) -> {
while (v != 0) {
iplist.add(k);
v--;
}
});
return iplist.get(ThreadLocalRandom.current().nextInt(iplist.size()));
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(getServer());
}
}
}
|
累加
平时，经常会遇到权重随机算法，从不同权重的N个元素中随机选择一个，并使得总体选择结果是按照权重分布的。如广告投放、负载均衡等。如有4个元素A、B、C、D，权重分别为1、2、3、4，随机结果中A:B:C:D的比例要为1:2:3:4。
总体思路：累加每个元素的权重A(1)-B(3)-C(6)-D(10)，则4个元素的的权重管辖区间分别为[0,1)、[1,3)、[3,6)、[6,10)。然后随机出一个[0,10)之间的随机数。落在哪个区间，则该区间之后的元素即为按权重命中的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class WeightRandomLoadBalancingV2 {
public static String getServer() {
Map<String, Integer> map = ServerIps.WEIGHT_LIST;
int totalWeight = map.values().stream().mapToInt(p -> p).sum();
int index = ThreadLocalRandom.current().nextInt(totalWeight);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() >= index) {
return entry.getKey();
}
index = index - entry.getValue();
}
return "";
}
|
RoundRobin–完全轮询算法
缺点：从头到尾轮询一遍，不能根据服务器性能设置权重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class RandomRobin {
public static String[] ipList = (String[]) ServerIps.WEIGHT_LIST.keySet().toArray();
static int index;
public static String getServer() {
if (index == ipList.length) {
index = 0;
}
return ipList[index++];
}
}
|
WeightedRoundRobin-加权轮询算法
优点：可以根据服务器性能设置访问权重
缺点：可能某个服务器权重大，长时间执行，遇到耗时大的请求，压力会很大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class ServerIps {
private static int index;
public static String getServer() {
int totalweigth = WEIGHT_LIST.values().stream().mapToInt(v -> v).sum();
int number = (index++) % totalweigth;
for (Map.Entry<String, Integer> ip : WEIGHT_LIST.entrySet()) {
if (ip.getValue() >= number) {
return ip.getKey();
}
number -= ip.getValue();
}
return "";
}
public static void main(String[] args) {
Stream.iterate(0, x -> x + 1).limit(20).forEach(x -> {
System.out.println(getServer());
});
}
}
|
但是这种算法有⼀个缺点: -台服务器的权重特别⼤的时候，他需要连续的的处理请求，但是实际.上我们想达 到的效果是，对于100次请求，只要有100*8/50=16次就够了，这16次不⼀定要连续的访问，⽐如假设我们有三 台服务器servers= [A, B, C],对应的权重为weights=[5, 1, 1] ,总权重为7,那么上述这个算法的结果是: AAAAABC，那么如果能够是这么⼀个结果呢: AABACAA，把B和C平均插⼊到5个A中间，这样是⽐较均衡的 了。
SmoothWeightedRoundRobin–平滑加权轮询算法
参考文章
优点：根据权重分配服务，同时又保证权重低的服务可以被访问到
缺点：集群环境下，同一个用户访问无法分流到固定一台机器
每个服务器对应两个权重，分别为weight 和currentWeight。其中weight是固定的，currentWeight 会动态 调整，初始值为0。当有新的请求进来时，遍历服务器列表,让它的currentWeight加上⾃身权重。遍历完 成后，找到最⼤的currentWeight,并将其减去权重总和，然后返回相应的服务器即可。 服务器servers= [A, B, C],对应的权重为weights=[5, 1, 1] ,总权重为7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| @Data
class SmoothWeight {
private int weight;
private int currentWeight;
private String address;
public SmoothWeight(int weight, int currentWeight, String address) {
this.weight = weight;
this.currentWeight = currentWeight;
this.address = address;
}
}
class ServerIps {
public static Map<String, SmoothWeight> map = new HashMap<>();
static {
map.put("10.180.11.126:8888", new SmoothWeight(5, 5, "10.180.11.126:8888"));
map.put("10.180.11.128:8888", new SmoothWeight(2, 2, "10.180.11.128:8888"));
map.put("10.180.11.130:8888", new SmoothWeight(9, 9, "10.180.11.130:8888"));
}
public static String getServer() {
SmoothWeight maxSmoothWeight = null;
int totalWeigth = map.values().stream().mapToInt(SmoothWeight::getWeight).sum();
for (Map.Entry<String, SmoothWeight> entry : map.entrySet()) {
SmoothWeight currentSmoothWeight = entry.getValue();
if (maxSmoothWeight == null || currentSmoothWeight.getCurrentWeight() > maxSmoothWeight.getCurrentWeight()) {
maxSmoothWeight = currentSmoothWeight;
}
}
assert maxSmoothWeight != null;
maxSmoothWeight.setCurrentWeight(maxSmoothWeight.getCurrentWeight() - totalWeigth);
for (Map.Entry<String, SmoothWeight> entry : map.entrySet()) {
SmoothWeight currentSmoothWeight = entry.getValue();
currentSmoothWeight.setCurrentWeight(currentSmoothWeight.getCurrentWeight() + currentSmoothWeight.getWeight());
}
return maxSmoothWeight.getAddress();
}
public static void main(String[] args) {
Stream.iterate(0, x -> x + 1).limit(15).forEach(v -> {
System.out.println(getServer());
});
}
}
|
ConsistentHash–⼀致性哈希算法
服务器集群接收到⼀次请求调⽤时，可以根据根据请求的信息，⽐如客户端的ip地址，或请求路径与请求参数 等信息进⾏哈希，可以得出⼀个哈希值，特点是对于相同的ip地址，或请求路径和请求参数哈希出来的值是样的，只要能再增加⼀个算法，能够把这个哈希值映射成⼀个服务端ip地址，就可以使相同的请求(相同 的ip 地址，或请求路径和请求参数)落到同⼀服务器上。 因为客户端发起的请求情况是⽆穷⽆尽的(客户端地址不同，请求参数不同等等)，所以对于的哈希值也是⽆ 穷⼤的，所以我们不可能把所有的哈希值都进⾏映射到服务端ip上，所以这⾥需要⽤到哈希环。如下图
哈希值如果需要ip1和ip2之间的，则应该选择ip2作为结果;
哈希值如果需要ip2和ip3之间的，则应该选择ip3作为结果;
哈希值如果需要ip3和ip4之间的，则应该选择ip4作为结果;
哈希值如果需要ip4和ip1之间的，则应该选择ip1作为结果;
上⾯这情况是⽐较均匀情况，如果出现ip4服务器不存在，那就是这样了:
会发现，ip3和ip1 直接的范围是⽐较⼤的，会有更多的请求落在ip1上，这是不“公平的”，解决这个问题需要加 ⼊虚拟节点，⽐如:
其中ip2-1, ip3-1就是虚拟结点，并不能处理节点，⽽是等同于对应的ip2和ip3服务器。 实际上，这只是处理这种不均衡性的⼀种思路，实际上就算哈希环本身是均衡的，你也可以增加更多的虚拟节 点来使这个环更加平滑，⽐如:
这个彩环也是“公平的”，并且只有ip1,2,3,4是实际的服务器ip,其他的都是虚拟ip。 那么我们怎么来实现呢? 对于我们的服务端ip地址，我们肯定知道总共有多少个，需要多少个虚拟节点也有我们⾃⼰控制，虚拟节点越 多则流量越均衡，另外哈希算法也是很关键的，哈希算法越散列流量也将越均衡。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| class ServerIps {
public static final List<String> LIST = Arrays.asList(
"192.168.0.1",
"192.168.0.2",
"192.168.0.3",
"192.168.0.4",
"192.168.0.5",
"192.168.0.6",
"192.168.0.7",
"192.168.0.8",
"192.168.0.9",
"192.168.0.10");
}
class ConsistentHash {
private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
private static final int VIRTUAL_NODES = 160;
static {
for (String ip : ServerIps.LIST) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
int hash = getHash(ip + "VN" + i);
virtualNodes.put(hash, ip);
}
}
}
private static String getServer(String client) {
int hash = getHash(client);
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
Integer nodeIndex = subMap.firstKey();
if (nodeIndex == null) {
nodeIndex = virtualNodes.firstKey();
}
return subMap.get(nodeIndex);
}
private static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++) {
hash = (hash ^ str.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
System.out.println(getServer("client" + i));
}
}
}
|
LeastActive–最⼩活跃算法
前⾯⼏种⽅法主要⽬标是使服务端分配到的调⽤次数尽量均衡，但是实际情况是这样吗?调⽤次数相同，服务器的 负载就均衡吗?当然不是，这⾥还要考虑每次调⽤的时间，⽽最⼩活跃数算法则是解决这种问题的。 活跃调⽤数越⼩，表明该服务提供者效率越⾼，单位时间内可处理更多的请求。此时应优先将请求分配给该服务提 供者。在具体实现中，每个服务提供者对应⼀个活跃数。初始情况下，所有服务提供者活跃数均为0。每收到⼀个 请求，活跃数加1，完成请求后则将活跃数减1。在服务运⾏⼀段时间后，性能好的服务提供者处理请求的速度更 快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求、这就是最⼩活跃数负载均衡 算法的基本思想。除了最⼩活跃数，最⼩活跃数算法在实现上还引⼊了权重值。所以准确的来说，最⼩活跃数算 法是基于加权最⼩活跃数算法实现的。举个例⼦说明⼀下，在⼀个服务提供者集中，有两个性能优异的服务提供 者。某⼀时刻它们的活跃数相同，则会根据它们的权重去分配请求，权重越⼤，获取到新请求的概率就越⼤。如果 两个服务提供者权重相同，此时随机选择-个即可。 实现: 因为活跃数是需要服务器请求处理相关逻辑配合的，⼀次调⽤开始时活跃数+1,结束时活跃数-1，所以这⾥就不对 这部分逻辑进⾏模拟了，直接使⽤⼀个map来进⾏模拟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| class ServerIps {
public static final Map<String, Integer> ACTIVITY_LIST = new LinkedHashMap<>();
static {
ACTIVITY_LIST.put("192.168.0.1", 2);
ACTIVITY_LIST.put("192.168.0.2", 0);
ACTIVITY_LIST.put("192.168.0.3", 1);
ACTIVITY_LIST.put("192.168.0.4", 3);
ACTIVITY_LIST.put("192.168.0.5", 0);
ACTIVITY_LIST.put("192.168.0.6", 1);
ACTIVITY_LIST.put("192.168.0.7", 4);
ACTIVITY_LIST.put("192.168.0.8", 2);
ACTIVITY_LIST.put("192.168.0.9", 7);
ACTIVITY_LIST.put("192.168.0.10", 3);
}
}
public class LeastActive {
private static String getServer() {
Optional<Integer> minValue =
ServerIps.ACTIVITY_LIST.values().stream().min(Comparator.naturalOrder());
if (minValue.isPresent()) {
List<String> minActivityIps = new ArrayList<>();
ServerIps.ACTIVITY_LIST.forEach((ip, activity) -> {
if (activity.equals(minValue.get())) {
minActivityIps.add(ip);
}
});
if (minActivityIps.size() > 1) {
Map<String, Integer> weightList = new LinkedHashMap<String, Integer>();
ServerIps.WEIGHT_LIST.forEach((ip, weight) -> {
if (minActivityIps.contains(ip)) {
weightList.put(ip, ServerIps.WEIGHT_LIST.get(ip));
}
});
int totalWeight = 0;
boolean sameWeight = true;
Object[] weights = weightList.values().toArray();
for (int i = 0; i < weights.length; i++) {
Integer weight = (Integer) weights[i];
totalWeight += weight;
if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
sameWeight = false;
}
}
int randomPos = ThreadLocalRandom.current().nextInt(totalWeight);
if (!sameWeight) {
for (String ip : weightList.keySet()) {
Integer value = weightList.get(ip);
if (randomPos < value) {
return ip;
}
randomPos = randomPos - value;
}
}
return (String) weightList.keySet().toArray()
[ThreadLocalRandom.current().nextInt(weightList.size())];
} else {
return minActivityIps.get(0);
}
} else {
return (String) ServerIps.WEIGHT_LIST.keySet().toArray()
[ThreadLocalRandom.current().nextInt(ServerIps.WEIGHT_LIST.size())];
}
}
public static void main(String[] args) {
for (int i = 0; i < 130; i++) {
System.out.println(getServer());
}
}
}
|
主流框架负载均衡
| 算法 |
特性 |
备注 |
| RandomLoadBalance |
加权随机 |
默认算法，默认权重相同 |
| RoundRobinLoadBalance |
加权轮询 |
借鉴于 Nginx 的平滑加权轮询算法，默认权重相 同， |
| LeastActiveLoadBalance |
最少活跃优先 + 加权 随机 |
背后是能者多劳的思想 |
| ShortestResponseLoadBalance |
最短响应优先 + 加权 随机 |
更加关注响应速度 |
| ConsistentHashLoadBalance |
⼀致性 Hash |
确定的⼊参，确定的提供者，适⽤于有状态请 求 |
Random
RoundRobin
LeastActive
ShortestResponse
ConsistentHash
- ⼀致性 Hash，相同参数的请求总是发到同⼀提供者。
- 当某⼀台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
- 算法参⻅：Consistent Hashing | WIKIPEDIA 缺省只对第⼀个参数 Hash，如果要修改，请配置 <dubbo:parameter key=”hash.arguments” value=”0,1” />
- 缺省⽤ 160 份虚拟节点，如果要修改，请配置 <dubbo:parameter key=”hash.nodes” value=”320” />
