释放双眼，带上耳机，听听看~！
负载均衡算法入门
-
随机算法
-
普通随机算法
- 权重随机算法
-
轮询算法
-
随机轮询算法
- 加权轮询算法
- 平滑加权轮询
-
一致性Hash算法
-
最小活跃数算法
随机算法
既然稍微了解了一下spring-cloud IRule的算法，那我就去找那些大佬稍微学习了一下基础的几个负载均衡算法，现在来做一个记录，可能写的不是很好，毕竟算法这个东西有一种只可意会不可言传的感觉。
先来一个入门级算法吧
普通随机算法
这个没啥好说的就只是简单随机一下就可以了。我们先编写一个ServerIps类来存放ip集合：
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
2
3 public static final List<String> IP_LIST = Arrays.asList(
4 "192.168.0.1",
5 "192.168.0.2",
6 "192.168.0.3",
7 "192.168.0.4",
8 "192.168.0.5",
9 "192.168.0.6",
10 "192.168.0.7",
11 "192.168.0.8",
12 "192.168.0.9",
13 "192.168.0.10"
14 );
15
16 /**
17 * key = ip
18 * value = 权重占比
19 */
20 public static final Map<String,Integer> IP_MAP = new HashMap<String,Integer>();
21
22 static {
23 IP_MAP.put("192.168.0.1",1);
24 IP_MAP.put("192.168.0.2",8);
25 IP_MAP.put("192.168.0.3",3);
26 IP_MAP.put("192.168.0.4",6);
27 IP_MAP.put("192.168.0.5",5);
28 IP_MAP.put("192.168.0.6",5);
29 IP_MAP.put("192.168.0.7",6);
30 IP_MAP.put("192.168.0.8",7);
31 IP_MAP.put("192.168.0.9",2);
32 IP_MAP.put("192.168.0.10",9);
33 }
34}
35
36
新建一个RandomTest类
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2/**
3 * 随机算法
4 * @return
5 */
6 public static String getRandomIp(){
7 int ipAddres = new Random().nextInt(ServerIps.IP_LIST.size());
8 return ServerIps.IP_LIST.get(ipAddres);
9 }
10
11 public static void main(String[] args) {
12 for(int i=0;i<10;i++){
13 System.out.println(getRandomIp());
14 }
15 }
16
17
运行一下main方法。简单是随机算法就完成了，是不是太简单了。不过呢，不要慌，这个只是最最最最简单的一个了，感觉都算不上算法，接下来我们稍微加一点难度吧。
权重随机算法
我们正式环境的服务器可不一定是每一台都一致的，总有性能好的和性能稍微差一点，所以这就会涉及到一个服务器权重，所以接下来我们做一下权重随机算法：
先讲一下这里的思路,如图：
画图这个真不会，所以就简单的意思意思了一下，我们还是继续来写代码吧。看一下代码就知道咋回事儿了：
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
2
3 /**
4 * 随机算法
5 * @return
6 */
7 public static String getRandomIp(){
8 int ipAddres = new Random().nextInt(ServerIps.IP_LIST.size());
9 return ServerIps.IP_LIST.get(ipAddres);
10 }
11 /**
12 * 加权随机算法
13 * @return
14 */
15 public static String getWeightId(){
16
17 //将ip占比转换为对象数组，用于循环计算权重总数
18 Object[] ips = ServerIps.IP_MAP.values().toArray();
19
20 int ipTotal = 0;//权重总数
21 boolean flag=true;//用于判断权重是不是一样的
22
23 for(int i=0;i<ips.length;i++){
24 //计算权重总数
25 Integer ipWeight = (Integer) ips[i];
26 ipTotal += ipWeight;
27
28 //判断所有ip权重是否一致
29 if(flag && i>0 && !ipWeight.equals(ips[i-1])){
30 flag = false;
31 }
32 }
33 //权重不一致，就随机一个数来判断一下这个树落在哪里
34 if(!flag){
35 //产生一个随机数
36 int ipAddres = new Random().nextInt(ipTotal);
37 for(String ipKey : ServerIps.IP_MAP.keySet()){
38 Integer ipValue = ServerIps.IP_MAP.get(ipKey);
39 if(ipAddres<=ipValue){
40 return ipKey;
41 }
42 ipAddres = ipAddres - ipValue;
43 }
44 }
45 //所有权重都一致，那就随机好啦
46 return getRandomIp();
47 }
48
49 public static void main(String[] args) {
50 for(int i=0;i<10;i++){
51 System.out.println(getWeightId());
52 }
53 }
54
55
运行一下，其实少量数据也看不出啥结果，这个还是一个概率问题，需要大量数据来统计分析的，但你数据越大就越会发现某个Ip出现的概率绝对跟他的权重占比相近。
轮询算法
随机轮询算法
一样的，我们先来一个简单的轮询算法，怎么理解这个轮询呢，就是一个接着一个，跟学生在食堂打饭一样，一个接一个（千万别说插队，那个你可以假装不知道）。还是来撸代码吧
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
2
3 //定义一个全局参数，轮询依据
4 private static Integer address = 0;
5
6 /**
7 * 简单轮询算法
8 * @return
9 */
10 public static String getPollingIp(){
11 String ip = null;
12 //这里加一个锁，防止并发影响轮询结果
13 synchronized (address){
14 if(address>= ServerIps.IP_LIST.size()){
15 address = 0;
16 }
17 ip = ServerIps.IP_LIST.get(address);
18 address++;
19 }
20 return ip;
21 }
22
23
24 public static void main(String[] args) {
25 for(int i=0;i<10;i++){
26 System.out.println(getPollingIp());
27 }
28 }
29
30}
31
32
运行结果，不用猜也知道了…
是吧，一个接着一个，故意加了一个锁，就是怕你们来插队。
加权轮询算法
好了，我们接下来在来看一下权重轮询算法吧，这里大概讲一下意思就不画图了，跟上面个随机权重有点像，不过一个是随机一个是轮询而已。
我们需要一个计数器，每次使用后就加1，然后我们根据计数器来除以权重总数得到余数，然后判断余数落在哪个点上就返回这个点上对应的IP就好。代码如下：
新建一个Sequence类来当计数器：
2
3
4
5
6
7
8
9
10
11
2
3 public static Integer num = 0;
4
5 public static Integer getIncrement(){
6 return ++num;
7 }
8}
9
10
11
改一下 PollingAlgorithm类：
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
2
3 //定义一个全局参数，轮询依据
4 private static Integer address = 0;
5
6 /**
7 * 简单轮询算法
8 * @return
9 */
10 public static String getPollingIp(){
11 String ip = null;
12 //这里加一个锁，防止并发影响轮询结果
13 synchronized (address){
14 if(address>= ServerIps.IP_LIST.size()){
15 address = 0;
16 }
17 ip = ServerIps.IP_LIST.get(address);
18 address++;
19 }
20 return ip;
21 }
22
23 public static String getWeightPollingIp(){
24 //将ip占比转换为对象数组，用于循环计算权重总数
25 Object[] ips = ServerIps.IP_MAP.values().toArray();
26
27 int ipTotal = 0;//权重总数
28 boolean flag=true;//用于判断权重是不是一样的
29
30 for(int i=0;i<ips.length;i++){
31 //计算权重总数
32 Integer ipWeight = (Integer) ips[i];
33 ipTotal += ipWeight;
34
35 //判断所有ip权重是否一致
36 if(flag && i>0 && !ipWeight.equals(ips[i-1])){
37 flag = false;
38 }
39 }
40 //取得计数器
41 Integer sequenceNum = Sequence.getIncrement();
42
43 //取余数
44 Integer resultNum = sequenceNum%ipTotal;
45 if(resultNum == 0){
46 resultNum = ipTotal;
47 }
48 if(!flag){
49 //循环判断当前这个点落在哪里
50 for(String ipKey : ServerIps.IP_MAP.keySet()){
51 Integer ipValue = ServerIps.IP_MAP.get(ipKey);
52 if(resultNum <= ipValue){
53 return ipKey;
54 }
55 resultNum = resultNum - ipValue;
56 }
57 }
58 //如果权重都相同，那就简单的轮询就行
59 return getPollingIp();
60 }
61
62 public static void main(String[] args) {
63 for(int i=0;i<10;i++){
64 System.out.println(getWeightPollingIp());
65 }
66 }
67
68}
69
70
运行一下，这个就会根据你定义的权重来一个一个的走了。举一个例子，你定义了ABC三个IP地址，然后A占5，B占1，C占1那么这里打印的就会是
这个算是完成了吧，是不是很开心哈哈哈哈。但是呢，你有没有想过，一周七天，作为老大哥的A也不能连续上七天的班呀，那样超级累的，那我们能不能做成AABACAA，这样老大哥A也能中途出去玩一玩放松一下，毕竟劳逸结合才能做出更好的事情嘛。好吧，还能真能做出这种效果。接着看吧！
平滑加权轮询
首先我们来看一下大概的代码思想
好吧，不知道为啥这样做？或则不懂上面图片的意思？那就看这个吧：
现在是不是大概知道咋回事儿了？但是你不要问我为什么要这么操作。这个就像1+1为什么等于2不等于3。这个具体谁做出来的算法我也还没有找到根源，但是nginx的负载均衡算法好像就是这个，当然啦，比这个应该要复杂很多的。如果你还是不太懂呢，那就把下面代码多写几遍，这样你就知道是啥意思了。
新建一个IpWeight类
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
2 * ip就是保存ip咯
3 * weight 保存 初始权重（固定不变的）
4 * crrentWeight 当前权重，随时改变
5 */
6public class IpWeight {
7
8 private String ip;
9
10 private Integer weight;
11
12 private Integer currentWeight;
13
14 public String getIp() {
15 return ip;
16 }
17
18 public void setIp(String ip) {
19 this.ip = ip;
20 }
21
22 public Integer getWeight() {
23 return weight;
24 }
25
26 public void setWeight(Integer weight) {
27 this.weight = weight;
28 }
29
30 public Integer getCurrentWeight() {
31 return currentWeight;
32 }
33
34 public void setCurrentWeight(Integer currentWeight) {
35 this.currentWeight = currentWeight;
36 }
37
38 public IpWeight(String ip, Integer weight, Integer currentWeight) {
39 this.ip = ip;
40 this.weight = weight;
41 this.currentWeight = currentWeight;
42 }
43}
44
45
再新建一个SmoothPollingAlgorithm类
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
2
3 private static Map<String,IpWeight> weightMap = new HashMap<String,IpWeight>();
4
5 public static String getIp(){
6 //将ip占比转换为对象数组，用于循环计算权重总数
7 Object[] ips = ServerIps.IP_MAP.values().toArray();
8 int ipTotal = 0;//权重总数
9
10 for(int i=0;i<ips.length;i++){
11 //计算权重总数
12 Integer ipWeight = (Integer) ips[i];
13 ipTotal += ipWeight;
14 }
15 //初始化 weightMap
16 if(weightMap.isEmpty()){
17 for(String ip:ServerIps.IP_MAP.keySet()){
18 weightMap.put(ip,new IpWeight(ip,ServerIps.IP_MAP.get(ip),ServerIps.IP_MAP.get(ip)));
19 }
20 }
21
22 //找出最大的IpWeight对象 根据currentWeight寻找
23 IpWeight maxWeight = null;
24 for (IpWeight weight:weightMap.values()){
25 if(maxWeight == null || weight.getCurrentWeight()>maxWeight.getCurrentWeight()){
26 maxWeight = weight;
27 }
28 }
29
30 //将最大的IpWeight对象减去总权重
31 maxWeight.setCurrentWeight(maxWeight.getCurrentWeight()- ipTotal);
32
33 for (IpWeight weight:weightMap.values()){
34 weight.setCurrentWeight(weight.getCurrentWeight()+weight.getWeight());
35 }
36
37 return maxWeight.getIp();
38 }
39
40 public static void main(String[] args) {
41 for(int i=0;i<10;i++){
42 System.out.println(getIp());
43 }
44 }
45}
46
47
运行一下，结果如下：
这个呢就叫做平滑加权轮询算法。是不是有点意思。
一致性Hash算法
一致性hash算法通过一个叫作一致性hash环的数据结构实现。这个环的起点是0，终点是2^32 – 1，并且起点与终点连接，环的中间的整数按逆时针分布，故这个环的整数分布范围是[0, 2^32-1]。
我们用这个能干啥？
服务器集群接收到一次请求调用时，可以根据请求的信息，比如客户端Ip地址，或则请求路径以及请求参数等信息进行哈希，可以得出一个哈希值，特点是对于相同的ip地址，或请求路径和参数哈希出来的值是一样的。只要再增加一个算法，能够把这个哈希值映射成一个服务端ip地址，就可以相同的请求（相同的ip地址，或请求路径和请求参数）落到同一台服务器上。
因为客户端的请求情况是无穷尽的（ip不同，地址不同，参数不同），所以对于哈希值也是无穷尽的，所以我们不可能把所有的哈希值都进行映射到服务器ip上，所以这里需要一个哈希环，如下：
但是这种情况要是挂掉一个就不公平了，比如ip2服务器挂了，然后ip3的压力就会增大，所以我们需要加入虚拟节点。大概如下：
就是添加很多虚拟节点，然后大家均分，这样就比较平均了，既重男也重女是吧！
那我们要来看一下代码了：
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
2
3 //定义一个TreeMap，基于红黑树的一个map
4 private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
5 //每个真实节点对应的虚拟节点
6 private static final int VIRTUAL_NODES = 160;
7 //给每个真实节点添加虚拟节点
8 static {
9 for(String ip: ServerIps.IP_LIST){
10 for(int i=0;i<VIRTUAL_NODES;i++){
11 int hash = getHash(ip+"TE"+i);
12 virtualNodes.put(hash,ip);
13 }
14 }
15 }
16
17 public static String getIp(String clint){
18 //获取hash值
19 int hash = getHash(clint);
20 //得到大于这个hash值的map
21 SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
22 //大于该hash值的第一个元素位置
23 Integer resultIndex = subMap.firstKey();
24 //这是一个hash环，最后一个值就不能获取到了，需要给根节点
25 if(resultIndex == null){
26 resultIndex = virtualNodes.firstKey();
27 }
28
29 return virtualNodes.get(resultIndex);
30 }
31
32 private static int getHash(String str) {
33 final int p = 16777619;
34 int hash = (int) 2166136261L;
35 for (int i = 0; i < str.length(); i++)
36 hash = (hash ^ str.charAt(i)) * p;
37 hash += hash << 13;
38 hash ^= hash >> 7;
39 hash += hash << 3;
40 hash ^= hash >> 17;
41 hash += hash << 5;
42 //取出来的值为负数就取绝对值
43 if (hash < 0)
44 hash = Math.abs(hash);
45 return hash;
46 }
47
48 public static void main(String[] args) {
49 for (int i = 0; i < 10; i++) {
50 System.out.println(getIp("client" + i));
51 }
52 }
53}
54
55
这里可能有一个TreeMap是一个比较生疏的技术点，这个还请大家各自自己去了解一下这里我就不讲解了，他是基于红黑树实现的。
好了 运行一下，其实你就会发现分散还比较平均（我前面拿了好多数据来测做了统计看的）。
前面几种方法主要目的是使服务器分配到的调用次数尽量均衡。但实际情况呢，还需要根据调用活跃度来进行计算的。
最小活跃数算法
这里呢稍微讲一下，就是首先获取服务器活跃度，拿到最小的活跃度的ip。如果只有一个，那么就直接调用这个ip。但是有多个咋办？那我们就来判断权重啦。权重大的优先，权重相同的就随机咯。哎，实在是不知道怎么说了，还是来看代码吧：
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
2
3 public static final List<String> IP_LIST = Arrays.asList(
4 "192.168.0.1",
5 "192.168.0.2",
6 "192.168.0.3",
7 "192.168.0.4",
8 "192.168.0.5",
9 "192.168.0.6",
10 "192.168.0.7",
11 "192.168.0.8",
12 "192.168.0.9",
13 "192.168.0.10"
14 );
15
16 /**
17 * key = ip
18 * value = 权重占比
19 */
20 public static final Map<String,Integer> IP_MAP = new HashMap<String,Integer>();
21
22 static {
23 IP_MAP.put("192.168.0.1",1);
24 IP_MAP.put("192.168.0.2",8);
25 IP_MAP.put("192.168.0.3",3);
26 IP_MAP.put("192.168.0.4",6);
27 IP_MAP.put("192.168.0.5",5);
28 IP_MAP.put("192.168.0.6",5);
29 IP_MAP.put("192.168.0.7",6);
30 IP_MAP.put("192.168.0.8",7);
31 IP_MAP.put("192.168.0.9",2);
32 IP_MAP.put("192.168.0.10",9);
33 /* IP_MAP.put("A",5);
34 IP_MAP.put("B",1);
35 IP_MAP.put("C",1);*/
36 }
37
38 public static final Map<String,Integer>IP_ACTIVE = new HashMap<String,Integer>();
39
40 static{
41 IP_ACTIVE.put("192.168.0.1",2);
42 IP_ACTIVE.put("192.168.0.2",0);
43 IP_ACTIVE.put("192.168.0.3",1);
44 IP_ACTIVE.put("192.168.0.4",3);
45 IP_ACTIVE.put("192.168.0.5",0);
46 IP_ACTIVE.put("192.168.0.6",1);
47 IP_ACTIVE.put("192.168.0.7",4);
48 IP_ACTIVE.put("192.168.0.8",2);
49 IP_ACTIVE.put("192.168.0.9",7);
50 IP_ACTIVE.put("192.168.0.10",0);
51 }
52}
53
54
55
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
2
3 private static String getServer() {
4 //找出数最小的服务器
5 Optional<Integer> minValue =
6 ServerIps.IP_ACTIVE.values().stream().min(Comparator.naturalOrder());
7 if (minValue.isPresent()) {
8 List<String> minActivityIps = new ArrayList<>();
9 ServerIps.IP_ACTIVE.forEach((ip, activity) -> {
10 if (activity.equals(minValue.get())) {
11 minActivityIps.add(ip);
12 }
13 });
14 //最下活跃数有多个的时候，根据权重来选择，权重大的优先
15 if (minActivityIps.size() > 1) {Map<String, Integer> weightList = new LinkedHashMap<String, Integer>
16 ();
17 //过滤出对应ip和权重
18 ServerIps.IP_MAP.forEach((ip, weight) -> {
19 if (minActivityIps.contains(ip)) {
20 weightList.put(ip, ServerIps.IP_MAP.get(ip));
21 }
22 });
23 int totalWeight = 0;//权重总数
24 boolean sameWeight = true;//用于判断权重是不是一样的
25 //将ip占比转换为对象数组，用于循环计算权重总数
26 Object[] weights = weightList.values().toArray();
27 for (int i = 0; i < weights.length; i++) {
28 Integer weight = (Integer) weights[i];
29 totalWeight += weight;
30 //判断所有ip权重是否一致
31 if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
32 sameWeight = false;
33 }
34 }
35 java.util.Random random = new java.util.Random();
36 int randomPos = random.nextInt(totalWeight);
37 if (!sameWeight) {
38 //循环判断当前这个点落在哪里
39 for (String ip : weightList.keySet()) {
40 Integer value = weightList.get(ip);
41 if (randomPos < value) {
42 return ip;
43 }
44 randomPos = randomPos - value;
45 }
46 }
47 return (String) weightList.keySet().toArray()[new
48 java.util.Random().nextInt(weightList.size())];
49 } else {
50 return minActivityIps.get(0);
51 }
52 } else {
53 return (String) ServerIps.IP_MAP.keySet().toArray()[new
54 java.util.Random().nextInt(ServerIps.IP_MAP.size())];
55 }
56 }
57
58 public static void main(String[] args) {
59 for(int i=0;i<10;i++){
60 System.out.println(getServer());
61 }
62 }
63
64
65
好吧，这里是有问题的，就是正常情况呢是在调用的时候将活跃度加1，返回成功后再减1的。但是今天实在是太累了，就忘记写了。不过只要知道有这个就行了，如果后面我还记得我一定来改掉。
运行结果就会发现192.168.0.10这个调用的次数稍微多一点咯。
