分布式系统 - 负载均衡算法

作者: HRocky | 来源:发表于2019-04-21 01:56 被阅读0次

一、负载均衡算法理论

以下理论知识为互联网资源的整理，若有侵权，请私信联系删除

1. 轮询算法(Round Robin)

轮询法的原理是把来自用户的请求轮流分配给内部的服务器：从服务器1开始，直到服务器N，然后重新开始循环。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。

轮询算法假设所有服务器的处理性能都相同，不关心每台服务器的当前连接数和响应速度。当请求服务间隔时间变化比较大时，轮询算法容易导致服务器间的负载不平衡。所以此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。

2. 加权轮询算法(Weight Round Robin)

不同的后端服务器可能机器的配置和当前系统的负载并不相同，所以它们的抗压能力也不同。给配置高、负载低的机器配置更高的权重，让其处理更多的请求；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好得处理这一问题，并将请求顺序且按照权重分配到后端。

3. 随机算法(Random)

通过系统的随机算法，根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问。有概率统计理论可以得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于平均分配调用量到后端的每一台服务器，也就是轮询的结果。

4. 加权随机算法(Weight Random)

与加权轮询法一样，加权随机法也根据后端机器的配置，系统的负载分配不同的权重。不同的是，它按照权重随机请求后端服务器，而非顺序。

5. 源地址哈希算法(Source Hashing )

源地址哈希的思想是根据获取客户端的IP地址，通过哈希函数计算得到一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是客户端要访问的服务器的序号。采用源地址哈希法进行负载均衡，统一IP地址的客户端，当后端服务器列表不变时，它每次都会映射到同一台后端服务器进行访问。

6. 一致性Hash负载均衡算法(Consistent Hash)

在HashMap中有一种操作就是扩容，当进行扩容后意味着哈希表的长度发生了变化，那么在转移旧表内容的时候就要进行重新hash操作确定key在新的哈希表中的索引。类似的，在源地址哈希算法中，如果某台服务器宕机后，那么意味着服务器列表的长度发生了变化，某个ip的服务器指向就要重新确定，同样的当增加服务器数量的时候也要重新确定服务器指向。

当集群为有状态时，比如说缓存集群的应用场景，这种普通的Hash负载均衡算法会存在问题。对这个算法的描述需要比较大的篇幅，请移步到此文章：

分布式系统 - 一致性Hash(Consistent Hash)负载均衡

7. 最少活跃数负载均衡法(Least Active)

参考Dubbo的最少活跃数负载均衡法，规则如下：

最少活跃调用数，相同活跃数的随机，活跃数指调用前后计数差；
使慢的提供者收到更少请求，因为越慢的提供者调用前后计数差会越大。

例如：每个服务维护一个活跃数计数器。当A机器开始处理请求，该计数器加1，此时A还未处理完成。若处理完毕则计数器减1。而B机器接受到请求后很快处理完毕。那么A,B的活跃数分别是1，0。当又产生了一个新的请求，则选择B机器去执行(B活跃数最小)，这样使慢的机器A收到少的请求。

8. 最小连接数负载均衡法(Least Connections)

最小连接调度(Least-Connection Scheduling)算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法，它通过服务器当前所活跃的连接数来估计服务器的负载情况。

在实际实现过程中，一般会为每台服务器设定一个权重值，这就是加权最小连接调度(Weighted Least-Connection Scheduling)

二、负载均衡算法实现

1. RoundRobinLoadBalancer

分析：假设有N台服务器，则有这样的服务器集合：S = {S1, S2, …, Sn}，根据轮询算法的描述，算法的逻辑即是依次顺序并且可循环得从集合S中获取元素。选择的元素操作类似这样：S1,S2,...,Sn,S1,S2,...Sn,S1...

LoadBalancerStrategy.java

public interface LoadBalancerStrategy<T> {
    T choose(List<T> candidates);
}

RoundRobinLoadBalancer.java

此类为https://github.com/Netflix/ocelli项目源码的分析和整理

public class RoundRobinLoadBalancer<T> implements LoadBalancerStrategy<T> {

    private AtomicInteger position;

    public RoundRobinLoadBalancer() {
        position = new AtomicInteger(new Random().nextInt(1000));
    }

    public RoundRobinLoadBalancer(int seedPosition) {
        this.position = new AtomicInteger(seedPosition);
    }

    @Override
    public T choose(List<T> candidates) {
        int pos = Math.abs(position.incrementAndGet());
        return candidates.get(pos % candidates.size());
    }

}

上面的代码有几个注意点：

使用原子操作类AtomicInteger来定义position，保证并发情况下值增长的原子性
通过取模的方式来获取列表索引
使用Math.abs函数来处理递增后的值

通过取模的方式得到索引：这个和HashMap中确定key在哈希表中的索引操作类似。假设初始position为0，服务器集合数为11，则获取索引的操作效果如下：

0 % 11 = 0
1 % 11 = 1
2 % 11 = 2
...
10 % 11 = 10
11 % 11 = 0
12 % 11 = 1
....

从上面可以看到可以达到依次并且循环分配服务器的效果。

使用Math.abs函数来处理递增后的值：我们知道AtomicInteger是有最大值限制的，最大值为2147483647(Integer.MAX_VALUE)，当position达到最大值后，继续执行incrementAndGet会出现值溢出，通过下面的代码进行测试：

AtomicInteger ai = new AtomicInteger(Integer.MAX_VALUE);
System.out.println(ai.getAndIncrement());
System.out.println(ai.getAndIncrement());
System.out.println(ai.getAndIncrement());
System.out.println(ai.getAndIncrement());
System.out.println(ai.getAndIncrement());

结果如下：

2147483647
-2147483648
-2147483647
-2147483646
-2147483645

从结果输出可以看到，当position达到最大值后，继续加1，会变长Integer的最小值即-2147483648，继续加1为次小值。当我们只看数的绝对值，我们发现当达到Integer的最大值后，继续执行增加操作，从绝对值看数是递减的，递减到0后，又重新递增。这个是个循环，这种规律正是我们轮询方式需要的。RoundRobinLoadBalancer采用了绝对值的处理方式，这就是为什么position值的获取使用了Math.abs函数的原因。

2. WeightedRoundRobinLoadBalancer

以下内容参考Nginx的平滑的加权轮询（smooth weighted round-robin balancing）和 Dubbo的RoundRobinLoadBalance的代码。以及以下两篇文章：
https://www.kancloud.cn/digest/sknginx/130030
https://www.fanhaobai.com/2018/11/load-balance-smooth-weighted-round-robin.html

分析：上面轮询法不会关注服务器的性能和负载承受能力，所以在此基础上提出了加权轮询来解决平均分配请求带来的问题。主要的思想就是权重分配高的服务器处理更多的请求。

假设服务器加上了权重配置：

cluster {
    server a weight=5;
    server b weight=1;
    server c weight=1;
}

每收到7个客户端的请求，会把其中的5个转发给后端a，把其中的1个转发给后端b，把其中的1个转发给后端c。这就是所谓的加权轮询，看起来很简单，但是最早使用的加权轮询算法有个问题，就是7个请求对应的后端序列是这样的：{ c, b, a, a, a, a, a }，会有5个连续的请求落在后端a上，分布不太均匀，造成对a服务器的集中访问。所以又提出了平滑的加权轮询（smooth weighted round-robin balancing）的概念，它和前者的区别是：每7个请求对应的后端序列为 { a, a, b, a, c, a, a }，转发给后端a的5个请求现在分散开来，不再是连续的。

平滑的加权轮询算法中节点3个变量：

weight：配置文件中指定的该节点的权重，这个值是固定不变的；
effective_weight：节点的有效权重，初始值为weight。这个变量的引入主要是处理节点异常，当节点出现异常时需要降低其权重；
currentWeight：节点目前的权重，一开始为0，之后会动态调整。
动态调整规则：每次选取后端时，会遍历集群中所有后端，对于每个后端，让它的current_weight增加它的effective_weight，同时累加所有后端的effective_weight，保存为total。如果该后端current_weight是最大的，就选定这个后端，然后把它的current_weight减去total。如果该后端没有被选定，那么current_weight不用减小。

算法逻辑：

1）对于每个请求，遍历集群中的所有可用节点，对于每个节点执行：

peer.current_weight += peer.effecitve_weight

同时累加所有peer的effective_weight，保存为totalWeight。

2）从集群中选出current_weight最大的peer，作为本次选定的节点。

3）对于本次选定的节点，执行：

peer.current_weight -= totalWeight

代码示例：

Peer.java

public class Peer {

    /** 权重 */
    private int weight;
    /** 当前权重 */
    private AtomicLong current = new AtomicLong(0);

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
        current.set(0);
    }

    public long increaseCurrent() {
        return current.addAndGet(weight);
    }

    public void sel(int total) {
        current.addAndGet(-1 * total);
    }

}

WeightedRoundRobinLoadBalancer.java

import java.util.List;

/**
 * 加权轮询负载均衡法
 *
 * @Author rocky.hu
 * @Date 2019/4/18 16:28
 */
public class WeightedRoundRobinLoadBalancer implements LoadBalancerStrategy<T> {

    @Override
    public Peer choose(List<Peer> candidates) {

        int totalWeight = 0;
        long maxCurrent = Long.MIN_VALUE;

        Peer selectedPeer = null;

        for (Peer peer : candidates) {

            // 获取节点的权重
            int weight = peer.getWeight();
            
            // 选择当前权重最大的节点
            long current = peer.increaseCurrent();
            if (current > maxCurrent) {
                maxCurrent = current;
                selectedPeer = peer;
            }

            // 计算集群中节点的总权重
            totalWeight += weight;
        }

        if (selectedPeer != null) {
            // 被选择的节点的当前权重做减totalWeight操作
            selectedPeer.sel(totalWeight);
            return selectedPeer;
        }

        return candidates.get(0);
    }
}

上面的代码是算法的简化实现版本，没有涉及到effective_weight。effective_weight关系到节点的状态，还是有些复杂的，这里不做阐述。

更详细的描述可以查阅本小节开始提到的那两篇文章，这两篇文章对这个算法有更详细的描述，包括算法的数学证明等。

3. RandomLoadBalancer

这个算法的实现比较简单，示例代码如下：

RandomLoadBalancer.java

import java.util.List;
import java.util.Random;

/**
 * @Author rocky.hu
 * @Date 2019-04-18 23:03
 */
public class RandomLoadBalancer<T> implements LoadBalancerStrategy<T> {

    @Override
    public T choose(List<T> candidates) {
        Random random = new Random();
        int i = random.nextInt(candidates.size());
        return candidates.get(i);
    }

}

4. WeightedRandomLoadBalancer

分析：上面的随机算法中节点完全被随机选取。考虑到节点的性能和负载能力，给每个节点设置一个权重，权重大的节点被选择的概率就大。

这里的描述就是加权随机抽样，有一些实际的应用场景，比如说优惠券的发放，优惠券的发放是随机的，但是又不完全是随机的，规定了优惠券的发放总量，但是从运营商的角度来说，当然是希望面额较小的优惠券发放的数量多点，面额较大的发放少点，这里优惠券的面额就是权重。

现在来分析一下加权随机如何实现：

假设现在有集合S = {A,B,C}，现在需要进行随机抽样，我们先不加权，来描述这个场景，将A,B,C放置到数轴中，如下所示：

非加权数轴.jpg

数轴中有3个点，随机选择3个点即可选择点对应的元素即A、B、C中任意的一个。而点的选择是完全随机的，这就是非加权随机抽样。

现在来看看给集合中的元素加上权值，设A的权重为5，B的权重为2，C的权重为3。在数轴中的表示如下：

加权抽样.jpg

如上图所示，集合中的元素不再用数轴中的点表示，而是用区间表示，权重大的元素所占的区间的长度就大，当选择的点落在对应的元素的区间中，那么就表示选中的这个元素，因为权重大的元素对应的数轴的点比较多，随机获取的点落在此元素对应的区间内的概率就相应较大，通过这种加权随机取样的方式就可以保证权重大的元素被选中的概率相应较大。

依照上面区间的图示，算法的逻辑可以为：
1）计算权重总和sum
上面的例子这个sum就是10；
2）在0到sum之间随机选择一个数R
不包括sum，R的取值为[0,9]
3）确定R点所在的区间
比如说R=3，那么它就落在了A区间，这样就可以确定选择A节点。这里是因为有图示可以直观的看到，程序逻辑应该怎样书写呢？从图示可以看到节点表示的区间的长度即为节点的权重，比如说A的权重为5，那么A区间就有5个点，A的区间长度我们可记为5。算法逻辑可以这样书写：遍历集合中的元素，累加节点的权重得到总的区间长度L，然后判断R-L是否小于0，如果小于0，则停止遍历，当前遍历到的元素就为该选择的元素。

比如R=5，遍历集合：
第一次：遍历到的集合元素为A，区间总长度为L = A的权重 = 5，R-L=0，继续遍历；
第二次：遍历到的集合元素为B，区间总长度L = 5 + B的权重 = 7，R - L = -2 < 0，停止遍历，B为该选择的节点。

上面的算法可以进一步优化一下，假如我们的集合是这样的：S = {B，A，C}，区间表示如下：

带权区间.jpg

当R=3时，根据上面的描述要遍历二次集合才能确定R在A区间，而"加权抽样.jpg"这种区间只需要遍历一次，这是因为权重大的元素区间相应地在前面，为了使得权重高的项可以很快遇到，减少遍历的项，S = {B，A，C}集合就要根据权重大小进行排序，也就是排序得到集合S = {A，B，C}。对集合按权重排序是对上面算法的一个优化。

代码实现：

下面为Dubbo的RandomLoadBalance类的整理

WeightedRandomLoadBalancer.java

public class WeightedRandomLoadBalancer implements LoadBalancerStrategy<Peer> {

    @Override
    public Peer choose(List<Peer> candidates) {

        int length = candidates.size();
        boolean sameWeight = true;
        int[] weights = new int[length];
        int firstWeight = candidates.get(0).getWeight();
        weights[0] = firstWeight;
        int totalWeight = firstWeight;
        for (int i=1; i<length; i++) {
            int weight = candidates.get(i).getWeight();
            weights[i] = weight;
            totalWeight += weight;
            if (sameWeight && weight != firstWeight) {
                sameWeight = false;
            }
        }

        if (totalWeight >0 && !sameWeight) {
            int offset = ThreadLocalRandom.current().nextInt(totalWeight);
            for (int i=0; i<length; i++) {
                offset -= weights[i];
                if (offset < 0) {
                    return candidates.get(i);
                }
            }
        }

        return candidates.get(ThreadLocalRandom.current().nextInt(length));
    }

}

5. SourceHashingLoadBalancer

分析：源地址哈希算法比较简单，相当于HashMap中Key在哈希表中的索引值的确定，逻辑就是获取客户端访问的ip地址,通过hash函数计算出一个hash值,用该hash值对服务器列表的大小进行取模运算,得到的值就是要访问的服务器的序号。

代码实现：

SourceHashingLoadBalancer.java

import java.util.List;

/**
 * 源地址Hash负载均衡法
 *
 * @Author rocky.hu
 * @Date 2019/4/19 15:16
 */
public class SourceHashingLoadBalancer<T> implements LoadBalancerStrategy<T> {

    @Override
    public T choose(List<T> candidates) {
        return null;
    }

    public T choose(List<T> candidates, String ip) {
        int hashCode = ip.hashCode();
        int pos = hashCode % candidates.size();
        return candidates.get(pos);
    }

}

6. ConsistentHashLoadBalancer

移步到：分布式系统 - 一致性Hash(Consistent Hash)负载均衡