负载均衡算法原理解析（一）

我会带着你远行 2022-04-23 05:28 200阅读 0赞

最近在学习Spring Cloud的Ribbon组件，里面用到了一些负载均衡算法。下面就来研究下当前常规的一些负载均衡算法实现，像权重随机、加权轮询、一致性哈希、最少活跃调用数等。

### 负载均衡介绍 ###

负载均衡，英文名称为LoadBalance，它的职责是将网络请求，或者其他形式的负载“均摊”到不同的机器上。避免集群中部分服务器压力过大，而另一些服务器比较空闲的情况。负载均衡能够解决大量并发访问服务问题，这种集群技术可以用最少的投资获得接近于大型主机的性能。

负载均衡可分为软件负载均衡和硬件负载均衡。硬件负载均衡有F5、Array，软件负载均衡有Nginx、LVS、HAProxy等。

### 算法实现 ###

#### 初始准备 ####

定义一个服务器列表，每个负载均衡算法会从中挑出一个服务器作为算法的结果。

public class ServerIps {
    
        // 服务器清单
        public static final List<String> LIST = new ArrayList<>();
        // 带有权重值的服务器清单
        public static final Map<String, Integer> WEIGHT_LIST = new HashMap<>();
        // 带有当前服务器活跃数的服务器清单
        public static final Map<String, Integer> ACTIVITY_LIST = new LinkedHashMap<>();
    
        static {
            LIST.add("192.168.1.1");
            LIST.add("192.168.1.2");
            LIST.add("192.168.1.3");
            LIST.add("192.168.1.4");
            LIST.add("192.168.1.5");
            LIST.add("192.168.1.6");
            LIST.add("192.168.1.7");
            LIST.add("192.168.1.8");
            LIST.add("192.168.1.9");
            LIST.add("192.168.1.10");
    
            WEIGHT_LIST.put("192.168.1.1", 9);
            WEIGHT_LIST.put("192.168.1.2", 1);
            WEIGHT_LIST.put("192.168.1.3", 8);
            WEIGHT_LIST.put("192.168.1.4", 2);
            WEIGHT_LIST.put("192.168.1.5", 7);
            WEIGHT_LIST.put("192.168.1.6", 3);
            WEIGHT_LIST.put("192.168.1.7", 6);
            WEIGHT_LIST.put("192.168.1.8", 4);
            WEIGHT_LIST.put("192.168.1.9", 5);
            WEIGHT_LIST.put("192.168.1.10", 5);
    		
    	    ACTIVITY_LIST.put("192.168.1.1", 2);
            ACTIVITY_LIST.put("192.168.1.2", 0);
            ACTIVITY_LIST.put("192.168.1.3", 1);
            ACTIVITY_LIST.put("192.168.1.4", 3);
            ACTIVITY_LIST.put("192.168.1.5", 0);
            ACTIVITY_LIST.put("192.168.1.6", 1);
            ACTIVITY_LIST.put("192.168.1.7", 4);
            ACTIVITY_LIST.put("192.168.1.8", 2);
            ACTIVITY_LIST.put("192.168.1.9", 7);
            ACTIVITY_LIST.put("192.168.1.10", 3);
        }
    }

#### 加权随机-RandoomLoadBalance ####

先来个简单的随机实现：

public static String getServer() {
    	Random random = new Random();
    	int pos = random.nextInt(ServerIps.LIST.size());
    	return ServerIps.LIST.get(pos);
    }

Ribbon中的`RandomRule`的实现原理就是就是这种方式，有兴趣的可以去看下。这种算法适用于每台机器的性能差不多的时候，而实际生产中经常会存在某些机器的性能更好，它可以处理更多的请求，所以，我们可以对每台机器设置一个权重。

**实现思路：**  
假设我们有一组服务器servers=\[A,B,C\]，它们对应的权重为weights=\[5,3,2\]，权重总和为10。现在把这些权值平铺在一维坐标上，\[0，5)区间属于服务器A，\[5,8)区间属于服务B，\[8,10)区间属于服务器C。接下来通过随机数生成器生成一个范围在\[0,10)之间的随机数，然后计算这个随机数回落到哪个区间上。比如数字3会落到服务器A对应的区间上，此时返回服务器A即可。

> 权重越大的机器，在坐标轴上对应的区间范围越大，因此随机数生成器生成的数字就会有更大的概率落到此区间内。只要随机数生成器产生的随机分布性很好，在经过多次选择后，每个服务器被选中的次数比例接近其权重比例。

假设现在随机数offset=7:

*  1.offset<5 is false，所以不再\[0,5)区间，将offset=offset-5（offset=2）
 *  2.offset<3 is true，所以处于\[5,8)区间，应选用B服务器

**实现如下：**

// 加权随机
    public class RandomLoadBalance {
    
        public static String getServer() {
            boolean sameWeight = true; // 是否所有权重都相等
            int totalWeight = 0; // 总权重
            
            Object[] weightArray =  ServerIps.WEIGHT_LIST.values().toArray();
            for (int i = 0; i < weightArray.length; i++) {
                Integer weight = (Integer) weightArray[i];
                totalWeight += weight;
                if (sameWeight && i > 0 && weight != weightArray[i - 1]) {
                    sameWeight = false;
                }
            }
    
            Random rand = new Random();
            int pos = rand.nextInt(totalWeight);
            
            if (!sameWeight) {
                for (String key : ServerIps.WEIGHT_LIST.keySet()) {
                    if (pos < ServerIps.WEIGHT_LIST.get(key)) {
                        return key;
                    }
                    pos = pos - ServerIps.WEIGHT_LIST.get(key);
                }
            }
    
            // 如果所有权重都相等，随机一个IP
            return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[rand.nextInt(ServerIps.WEIGHT_LIST.size())];
        }
    }

#### 加权轮询-RoundRobinLoadBalance ####

先来一个简单的轮询算法：

public static String getServer() {
    	String ip = null;
    	synchronized (pos) {
    		if (pos >= ServerIps.LIST.size()) {
    			pos = 0;
    		}
    		ip = ServerIps.LIST.get(pos);
    		pos++;
    	}
    	
    	return ip;
    }

Robbion中的`RoundRobinRule`是通过`next = (current + 1) % modulo;`取余来实现轮询，和上面的实现原理类似。这种算法很简单，也很公平，每台服务轮流来进行服务，但是就像前面说的，生产环境中机器的性能分配不均，所以需要加上一个权重来重新实现该算法。

**实现思路：**

> **调用编号:** 通过这个编号来模拟请求，比如第1次调用为1，第2次调用为2，第100次调用为100，调用编号是递增的。

假设我们有三台服务器servers=\[A,B,C\]，对应的权重为weights=\[2,5,1\]，总权重为8，我们可以理解为有8台服务器，其中两台为A，5台为B，1台为C。一次调用过来时，需要按顺序访问，比如有10次访问，那么调用顺序为AABBBBBCAA，调用编号会越来越大，而服务器是固定的，所以需要把调用编号“缩小”，我们可以借鉴Robbion中`RoundRobinRule`的方式，通过取余，除数为总权重和。通过取余，调用编号会被缩小为0-7之间的8个数字。

和权重随机算法类似，可以把权重想象为一个一维坐标轴“0–2-----7-8”

*  1号调用，1%8=1，offset=1，offset<=2 is true，取A；
 *  2号调用，2%8=2，offset=2，offset<=2 is true，取A；
 *  3号调用，3%8=3，offset=3，offset<=2 is false，offset=offset-2，offset=1，offset<=5，取B；
 *  8号调用，8%8=0，offset=0，特殊情况，offset = 8，offset <= 2 is false, offset = offset - 2, offset = 6，offset <= 5 is false, offset = offset - 5, offset = 1, offset <= 1 is true, 取C;  
    …
 *  100号调用，100%8=4，offset=4 …

**实现如下：**  
模拟调用编号生成

public class Sequence {
        private static Integer sequenceNum = 0;
        public static Integer getAndIncrement() {
            return sequenceNum++;
        }
    }

// 加权轮询
    public class RoundRobinLoadBalance {
    
        private static Integer offset = 0;
    
        public static String getServer() {
            boolean sameWeight = true; // 是否所有权重都相等
            int totalWeight = 0; // 总权重
            
            Object[] weightArray = ServerIps.WEIGHT_LIST.values().toArray();
            for (int i = 0; i < weightArray.length; i++) {
                Integer weight = (Integer) weightArray[i];
                totalWeight += weight;
                if (sameWeight && i > 0 && weight != weightArray[i - 1]) {
                    sameWeight = false;
                }
            }
    
            Integer sequenceNum = Sequence.getAndIncrement();
            offset = sequenceNum % totalWeight;
            if (offset == 0) {
                offset = totalWeight;
            }
    
            if (!sameWeight) {
                for (String key : ServerIps.WEIGHT_LIST.keySet()) {
                    if (offset <= ServerIps.WEIGHT_LIST.get(key)) {
                        return key;
                    }
                    offset = offset - ServerIps.WEIGHT_LIST.get(key);
                }
            }
    
            // 如果权重都相等，则按照简单轮询策略
            String serverIp = "";
            synchronized (offset) {
                if (offset >= ServerIps.WEIGHT_LIST.size()) {
                    offset = 0;
                }
                serverIp = (String) ServerIps.WEIGHT_LIST.keySet().toArray()[offset];
                offset++;
            }
    
            return serverIp;
        }
    }

循环调用执行后，就会发现这种算法有一个缺点：一台服务器的权重特别大的时候，它需要连续的处理请求。但是实际上我们想达到的效果是: 对于权重为8的服务器IP，总权重为50，100次请求中，该服务只要有100\*8/50=16次访问就够了，而且这16次不一定要连续访问。比如假设有三台服务器servers=\[A,B,C\]，对应的权重为weights=\[5,1,1\]，总权重为7，那么上述这个算法的结果是：AAAAABC。我们希望是这样一个结果：AABACAA，把B和C平均插入到5个A中间，这样就比较均衡了。

**下面再来介绍下升级版的算法，平滑加权轮询：**  
**实现思路：**

每个服务器对应两个权重，分别为weight和currentWeight。其中weight是固定的，currentWeight会动态调整，初始值为0。当有新的请求进来时，遍历服务器列表，让它的currentWeight加上自身权重。遍历完成后，找到最大的currentWeight，并将其减去权重总和，然后返回相应的服务器即可。

<table> 
 <thead> 
  <tr> 
   <th>请求编号</th> 
   <th>currentWeight数组(current_Weight += weight)</th> 
   <th>选择结果(max(currentWeight))</th> 
   <th>减去权重总和后的currentWeight数组(max(currentWeight)-=sum(weight))</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>[5,1,1]</td> 
   <td>A</td> 
   <td>[-2,1,1]</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>[3,2,2]</td> 
   <td>A</td> 
   <td>[-4,2,2]</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>[1,3,3]</td> 
   <td>B</td> 
   <td>[1,-4,3]</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>[6,-3,4]</td> 
   <td>A</td> 
   <td>[-1,-3,4]</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>[4,-2,5]</td> 
   <td>C</td> 
   <td>[4,-2,-2]</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>[9,-1,-1]</td> 
   <td>A</td> 
   <td>[2,-1,-1]</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>[7,0,0]</td> 
   <td>A</td> 
   <td>[0,0,0]</td> 
  </tr> 
 </tbody> 
</table>

如上，经过平滑性处理后，得到的服务器序列为\[A,A,B,A,C,A,A\]。初始情况下currentWeight=\[0,0,0\]，第7个请求处理完后，currentWeight再次变为\[0,0,0\]  
。

**实现如下：**  
为了演示方便，这里将ServerIps.WEIGHT\_LIST中的值改为：

WEIGHT_LIST.put("A",5);
    WEIGHT_LIST.put("B",1);
    WEIGHT_LIST.put("C",1);

// 该类用来保存ip，weight(固定不变的原始权重)，currentWeight(动态变化的权重)。
    public class Weight {
        private Integer weight;
        private Integer currentWeight;
        private String ip;
    
        public Weight(Integer weight, Integer currentWeight, String ip) {
            this.weight = weight;
            this.currentWeight = currentWeight;
            this.ip = ip;
        }
    	...省略getter/setter方法
    }

// 平滑加权轮询
    public class RoundRobinLoadBalanceV1 {
        private static Map<String, Weight> weightMap = new HashMap<>();
        private static Weight currentWeight;
    
        public static String getServer() {
        	// 获取总权重
            int totalWeight = ServerIps.WEIGHT_LIST.values().stream().reduce(0, (w1, w2) -> w1 + w2);
    
            // 初始化weightMap，初始时将currentWeight赋值为weight
            if (weightMap.isEmpty()) {
                for (String ip : ServerIps.WEIGHT_LIST.keySet()) {
                    Integer weight = ServerIps.WEIGHT_LIST.get(ip);
                    weightMap.put(ip, new Weight(weight, weight, ip));
                }
            }
    
            // 找出currentWeight的最大值
            Weight maxCurrentWeight = null;
            for (Weight weight : weightMap.values()) {
                if (maxCurrentWeight == null || weight.getCurrentWeight() > maxCurrentWeight.getCurrentWeight()) {
                    maxCurrentWeight = weight;
                }
            }
    
            // 将maxCurrentWeight减去总权重和
            maxCurrentWeight.setCurrentWeight(maxCurrentWeight.getCurrentWeight() - totalWeight);
    
            // 所有的ip的currenntWeight统一加上原始权重
            for (Weight weight : weightMap.values()) {
                weight.setCurrentWeight(weight.getCurrentWeight() + weight.getWeight());
            }
    
            return maxCurrentWeight.getIp();
    
        }
    
        public static void main(String[] args) {
            for (int i = 0; i < 7; i++) {
                System.out.println(getServer());
            }
        }
    }

**执行结果：**  
![平滑轮询][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6eWdjcw_size_16_color_FFFFFF_t_70]  
看到这里是不是很Surprise，第一次看到这个结果的时候，感觉算法是如此的有魅力。

[负载均衡算法原理解析（二）][Link 1]  
**注意**  
本文提到的算法以理解实现思想为主，实际生产环境要复杂很多，还需要做更多的处理。

**参考资料**  
[http://dubbo.apache.org/zh-cn/docs/source\_code\_guide/loadbalance.html][http_dubbo.apache.org_zh-cn_docs_source_code_guide_loadbalance.html]

--------------------

\------------本文结束感谢您的阅读------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6eWdjcw_size_16_color_FFFFFF_t_70]: /images/20220323/5493541e4bfa42529c5da508305e9a0f.png
[Link 1]: https://blog.csdn.net/hzygcs/article/details/86629707
[http_dubbo.apache.org_zh-cn_docs_source_code_guide_loadbalance.html]: http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html