负载均衡算法

负载均衡算法

简介

负载均衡的职责是将网络请求或者其他形式的负载均摊到不同的机器上，避免集群中部分服务器压力过大而另一些服务器空闲的情况。通过负载均衡，可以让每台服务器获取到适合自己处理能力的负载，为高负载服务器分流的同时，也可以避免资源浪费。以下将分析几种不同的负载均衡算法。

随机选择算法

随机选择算法的核心思想是基于服务器权重（权重来源于部署配置，可根据服务器的资源和配置设置权重）分配负载，权重高的机器获得负载的机会更大。举例来说，假设有三台主机a,b,c，其权重分别为2,5,1，那么一个负载抵达集群后，a获得该负载的概率为2/8，b获得的概率的5/8，c获得的概率为1/8，在这种情况下，当有足够多的负载抵达集群时，a,b,c三台机器处理负载的比例也约为2:5:1

算法实现

假设服务器数组为host[]，其对应的权重数组为weight[]

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
public String selectHostRandom(String[] hosts, int[] weights) {
        Random random = new Random();
        int length = hosts.length;
        int totalWeight = 0;
        boolean sameWeight = true;
        //计算服务器总权重并判断每个服务器的权重是否相同
        for (int i = 0; i < length; i++) {
            int weight = weights[i];
            totalWeight += weight;
            if (sameWeight && i > 0 && weight != weights[i - 1]) {
                sameWeight = false;
            }
        }
        if (totalWeight > 0 && !sameWeight) {
            //随机获取一个[0,weight)区间内的数
            int offset = random.nextInt(totalWeight);
            //offset循环减去服务器权重，当offset小于0时，返回当前服务器
            for (int i = 0; i < length; i++) {
                offset -= weights[i];
                if (offset < 0) {
                    return hosts[i];
                }
            }
        }
        //若所有服务器的权重都相同，则随机选择一个
        return hosts[random.nextInt(length)];
    }

算法分析

该算法思想简单，多次请求后负载基本均衡，但是当请求数较少时，由于依赖random函数，可能会出现随机数集中导致请求分配不均衡的情况。

简单轮询算法

该算法的主要思想是以轮询的形式将请求平均分配到每台服务器上，即将负载轮流分配给每台服务器。举例来说，若有三台服务器a,b,c，5次请求分别落在服务器a,b,c,a,b上。

算法实现

假设服务器数组为host[]，其对应的权重数组为weight[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String selectHostRoundRobin(String[] hosts, int[] weight) {
        int length = hosts.length;
  			//保存当前服务器的总权重，在具体的算法中，该数组应该为全局变量保存服务器当前的权重
        int[] currentWeight = new int[length];
        int totalWeight = 0;
        int lowWeight = 0;
        //当前权重最小的服务器下标
  			int index = 0;
        for (int i = 0; i < length; i++) {
            totalWeight += weight[i];
            currentWeight[i] += weight[i];
            if (i == 0 || lowWeight > currentWeight[i]) {
                lowWeight = currentWeight[i];
                index = i;
            }
        }
        currentWeight[index] = currentWeight[index] + totalWeight;
        return hosts[index];
    }

算法分析

该算法思想简单，容易实现，每次选择当前权重最小的服务器，然后将当前权重更新为当前权重与总权重之和，此时该服务器的当前权重成为最大，保证了下一次的选择中不会被选中。但是这种算法只适用于机器配置或性能完全相同的集群中，否则性能差的机器与性能好的机器处理相同数据量的负载，造成机器负载过大或资源浪费。

加权轮询算法

加权轮询算法在简单轮询算法的基础上，对轮询过程进行加权，加权后使每台服务器能够得到的请求数比例，接近或者等于其权重比。举例来说，若三台服务器a,b,c的权重分别为5,1,1，那么在7次请求中，a将收到其中的5次，b将收到其中的1次，c将收到其中的1次，且请求抵达的顺序类似于a,a,b,a,c,a,a这种乱序，而非a,a,a,a,a,b,c这种在短时间内抵达同一服务器的情况。

以下算法摘自dubbo(负载均衡)

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

如服务器a,b,c对应的权重分别为5,1,1，7次请求依次进入负载均衡的选择过程如下：

请求编号 currentWeight数组 选择结果 最大值减去权重和
0 [0, 0, 0] / /
1 [5, 1, 1] a [-2, 1, 1]
2 [3, 2, 2] a [-4, 2, 2]
3 [1, 3, 3] b [1, -4, 3]
4 [6, -3, 4] a [-1, -3, 4]
5 [4, -2, 5] c [4, -2, -2]
6 [9, -1, -1] a [2, -1, -1]
7 [7, 0 , 0] a [0, 0, 0]

为何上述过程可以达到加权轮询的目的？

条件：

  1. 显然，currentWeight的总和总是为7，即totalWeight。则减去最大权重后的currntWeight数组和为0。（因为currentWeight中的最大元素减去totalWeight，然后每个元素分别再加上weight，而weigth的总和就是totalWeight，即减去totalWeight后又加了回来，总和维持不变）
  2. 减去最大权重和之后的currentWeight中元素的值总在(-7， +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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
public class RoundRobinLoadBalance extends AbstractLoadBalance {
    public static final String NAME = "roundrobin";
    
    private static int RECYCLE_PERIOD = 60000;
    
    protected static class WeightedRoundRobin {
        // 服务提供者权重
        private int weight;
        // 当前权重
        private AtomicLong current = new AtomicLong(0);
        // 最后一次更新时间
        private long lastUpdate;
        
        public void setWeight(int weight) {
            this.weight = weight;
            // 初始情况下，current = 0
            current.set(0);
        }
        public long increaseCurrent() {
            // current = current + weight；
            return current.addAndGet(weight);
        }
        public void sel(int total) {
            // current = current - total;
            current.addAndGet(-1 * total);
        }
    }

    // 嵌套 Map 结构，存储的数据结构示例如下：
    // {
    //     "UserService.query": {
    //         "url1": WeightedRoundRobin@123, 
    //         "url2": WeightedRoundRobin@456, 
    //     },
    //     "UserService.update": {
    //         "url1": WeightedRoundRobin@123, 
    //         "url2": WeightedRoundRobin@456,
    //     }
    // }
    // 最外层为服务类名 + 方法名，第二层为 url 到 WeightedRoundRobin 的映射关系。
    // 这里我们可以将 url 看成是服务提供者的 id
    private ConcurrentMap<String, ConcurrentMap<String, WeightedRoundRobin>> methodWeightMap = new ConcurrentHashMap<String, ConcurrentMap<String, WeightedRoundRobin>>();
    
    // 原子更新锁
    private AtomicBoolean updateLock = new AtomicBoolean();
    
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
        // 获取 url 到 WeightedRoundRobin 映射表，如果为空，则创建一个新的
        ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.get(key);
        if (map == null) {
            methodWeightMap.putIfAbsent(key, new ConcurrentHashMap<String, WeightedRoundRobin>());
            map = methodWeightMap.get(key);
        }
        int totalWeight = 0;
        long maxCurrent = Long.MIN_VALUE;
        
        // 获取当前时间
        long now = System.currentTimeMillis();
        Invoker<T> selectedInvoker = null;
        WeightedRoundRobin selectedWRR = null;

        // 下面这个循环主要做了这样几件事情：
        //   1. 遍历 Invoker 列表，检测当前 Invoker 是否有
        //      相应的 WeightedRoundRobin，没有则创建
        //   2. 检测 Invoker 权重是否发生了变化，若变化了，
        //      则更新 WeightedRoundRobin 的 weight 字段
        //   3. 让 current 字段加上自身权重，等价于 current += weight
        //   4. 设置 lastUpdate 字段，即 lastUpdate = now
        //   5. 寻找具有最大 current 的 Invoker，以及 Invoker 对应的 WeightedRoundRobin，
        //      暂存起来，留作后用
        //   6. 计算权重总和
        for (Invoker<T> invoker : invokers) {
            String identifyString = invoker.getUrl().toIdentityString();
            WeightedRoundRobin weightedRoundRobin = map.get(identifyString);
            int weight = getWeight(invoker, invocation);
            if (weight < 0) {
                weight = 0;
            }
            
            // 检测当前 Invoker 是否有对应的 WeightedRoundRobin，没有则创建
            if (weightedRoundRobin == null) {
                weightedRoundRobin = new WeightedRoundRobin();
                // 设置 Invoker 权重
                weightedRoundRobin.setWeight(weight);
                // 存储 url 唯一标识 identifyString 到 weightedRoundRobin 的映射关系
                map.putIfAbsent(identifyString, weightedRoundRobin);
                weightedRoundRobin = map.get(identifyString);
            }
            // Invoker 权重不等于 WeightedRoundRobin 中保存的权重，说明权重变化了，此时进行更新
            if (weight != weightedRoundRobin.getWeight()) {
                weightedRoundRobin.setWeight(weight);
            }
            
            // 让 current 加上自身权重，等价于 current += weight
            long cur = weightedRoundRobin.increaseCurrent();
            // 设置 lastUpdate，表示近期更新过
            weightedRoundRobin.setLastUpdate(now);
            // 找出最大的 current 
            if (cur > maxCurrent) {
                maxCurrent = cur;
                // 将具有最大 current 权重的 Invoker 赋值给 selectedInvoker
                selectedInvoker = invoker;
                // 将 Invoker 对应的 weightedRoundRobin 赋值给 selectedWRR，留作后用
                selectedWRR = weightedRoundRobin;
            }
            
            // 计算权重总和
            totalWeight += weight;
        }

        // 对 <identifyString, WeightedRoundRobin> 进行检查，过滤掉长时间未被更新的节点。
        // 该节点可能挂了，invokers 中不包含该节点，所以该节点的 lastUpdate 长时间无法被更新。
        // 若未更新时长超过阈值后，就会被移除掉，默认阈值为60秒。
        if (!updateLock.get() && invokers.size() != map.size()) {
            if (updateLock.compareAndSet(false, true)) {
                try {
                    ConcurrentMap<String, WeightedRoundRobin> newMap = new ConcurrentHashMap<String, WeightedRoundRobin>();
                    // 拷贝
                    newMap.putAll(map);
                    
                    // 遍历修改，即移除过期记录
                    Iterator<Entry<String, WeightedRoundRobin>> it = newMap.entrySet().iterator();
                    while (it.hasNext()) {
                        Entry<String, WeightedRoundRobin> item = it.next();
                        if (now - item.getValue().getLastUpdate() > RECYCLE_PERIOD) {
                            it.remove();
                        }
                    }
                    
                    // 更新引用
                    methodWeightMap.put(key, newMap);
                } finally {
                    updateLock.set(false);
                }
            }
        }

        if (selectedInvoker != null) {
            // 让 current 减去权重总和，等价于 current -= totalWeight
            selectedWRR.sel(totalWeight);
            // 返回具有最大 current 的 Invoker
            return selectedInvoker;
        }
        
        // should not happen here
        return invokers.get(0);
    }
}

一致性Hash算法

根据请求信息为缓存节点生成一个hash，并将这个hash投射到[0, 2^32 - 1]​的圆环上。当有请求进来时，则为缓存项的key生成一个hash值，然后查找第一个大于或等于该hash值的缓存节点，并到这个节点中写入缓存项，如果当前节点挂了，则在下一次请求时为缓存项查找另一个大于其hash值的缓存节点。为了防止数据倾斜问题，一般会引入虚拟节点进行处理。

发布于