负载均衡是什么？

负载均衡（Load Balance），意思是将负载（如前端的访问请求）进行平衡、（通过负载均衡算法）分摊到多个操作单元（服务器，中间件）上进行执行。是解决高性能，单点故障（高可用），扩展性（水平伸缩）的终极解决方案。可以理解为，负载均衡是高可用和高并发共同使用的一种技术。

负载均衡的作用：

1、增加吞吐量，解决并发压力（高性能）；

2、提供故障转移（高可用）；

3、通过添加或减少服务器数量，提供网站伸缩性（扩展性）；

4、安全防护（负载均衡设备上做一些过滤，黑白名单等处理）。

常见负载均衡软件

Nginx

rr：轮叫，轮流分配到后端服务器；
wrr：权重轮叫，根据后端服务器负载情况来分配；
lc：最小连接，分配已建立连接最少的服务器上；
wlc：权重最小连接，根据后端服务器处理能力来分配。

Dubbo

支持4种算法（随机、轮询、活跃度、Hash一致性），而且算法里面引入权重的概念。

SpringCloud Feign

支持很多种算法，包括：轮询、随机、最小连接、区域加权、重试以及ResponseTime加权。也可以自己实现负载均衡算法

负载均衡算法是什么？

负载均衡服务器在决定将请求转发到具体哪台真实服务器时，是通过负载均衡算法来实现的。负载均衡算法可以分为两类：静态负载均衡算法和动态负载均衡算法。

静态负载均衡算法包括：轮询、比率、优先权等

比率（Ratio）
给每个服务器分配一个加权值为比例，根椐这个比例，把用户的请求分配到每个服务器。

优先权（Priority）
给所有服务器分组，给每个组定义优先权。当最高优先级中所有服务器出现故障，将请求送给次优先级的服务器组。这种方式，实际为用户提供一种热备份的方式。

常见的负载均衡算法

1、轮询法

轮询（Round Robin）：顺序循环将请求一次顺序循环地连接每个服务器。以轮询的方式依次请求调度不同的服务器；实现时，一般为服务器带上权重。

优点：服务器请求数目相同；实现简单、高效；易水平扩展。

缺点：服务器压力不一样，不适合服务器配置不同的情况；请求到目的结点的不确定，造成其无法适用于有写操作的场景。

应用场景：数据库或应用服务层中只有读的场景。

轮询法

2、随机法

将请求随机分配到各个节点。由概率统计理论得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于平均分配，也就是轮询的结果。

优缺点和轮询相似。

3、源地址哈希法

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

优点：相同的IP每次落在同一个节点，可以人为干预客户端请求方向，例如灰度发布；

缺点：如果某个节点出现故障，会导致这个节点上的客户端无法使用，无法保证高可用。当某一用户成为热点用户，那么会有巨大的流量涌向这个节点，导致冷热分布不均衡，无法有效利用起集群的性能。所以当热点事件出现时，一般会将源地址哈希法切换成轮询法。

源地址哈希法

4、加权轮询法

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

加权轮询算法要生成一个服务器序列，该序列中包含n个服务器。n是所有服务器的权重之和。在该序列中，每个服务器的出现的次数，等于其权重值。并且，生成的序列中，服务器的分布应该尽可能的均匀。比如序列{a, a, a, a, a, b, c}中，前五个请求都会分配给服务器a，这就是一种不均匀的分配方法，更好的序列应该是：{a, a, b, a, c, a, a}。

优点：可以将不同机器的性能问题纳入到考量范围，集群性能最优最大化；

缺点：生产环境复杂多变，服务器抗压能力也无法精确估算，静态算法导致无法实时动态调整节点权重，只能粗糙优化。

5、加权随机法

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

6、键值范围法

根据键的范围进行负债，比如0到10万的用户请求走第一个节点服务器，10万到20万的用户请求走第二个节点服务器……以此类推。

优点：容易水平扩展，随着用户量增加，可以增加节点而不影响旧数据；

缺点：容易负债不均衡，比如新注册的用户活跃度高，旧用户活跃度低，那么压力就全在新增的服务节点上，旧服务节点性能浪费。而且也容易单点故障，无法满足高可用。

动态负载均衡算法包括：最少连接数、最快响应速度、观察方法、预测法、动态性能分配、动态服务器补充、服务质量、服务类型、规则模式等

最少连接
将请求分配到连接数最少的服务器（目前处理请求最少的服务器）。

优点：根据服务器当前的请求处理情况，动态分配；

缺点：算法实现相对复杂，需要监控服务器请求连接数；

最快模式（Fastest）
传递连接给那些响应最快的服务器。
观察模式（Observed）
连接数目和响应时间这两项的最佳平衡为依据为新的请求选择服务器。
预测模式（Predictive）
利用收集到的服务器当前的性能指标，进行预测分析，选择一台服务器在下一个时间片内，其性能将达到最佳的服务器相应用户的请求。
动态性能分配(Dynamic Ratio-APM)
根据收集到的应用程序和应用服务器的各项性能参数，动态调整流量分配。
动态服务器补充(Dynamic Server Act)
当主服务器群中因故障导致数量减少时，动态地将备份服务器补充至主服务器群。
服务质量(QoS）
按不同的优先级对数据流进行分配。
服务类型(ToS)
按不同的服务类型（在 Type of Field 中标识）负载均衡对数据流进行分配。
规则模式
针对不同的数据流设置导向规则，用户可自行设置。

1、最小连接数法

根据每个节点当前的连接情况，动态地选取其中当前积压连接数最少的一个节点处理当前请求，尽可能地提高后端服务的利用效率，将请求合理地分流到每一台服务器。俗称闲的人不能闲着，大家一起动起来。

优点：动态，根据节点状况实时变化；

缺点：提高了复杂度，每次连接断开需要进行计数；

实现：将连接数的倒数当权重值。

2、最快响应速度法

根据请求的响应时间，来动态调整每个节点的权重，将响应速度快的服务节点分配更多的请求，响应速度慢的服务节点分配更少的请求，俗称能者多劳，扶贫救弱。

优点：动态，实时变化，控制的粒度更细，跟灵敏；

缺点：复杂度更高，每次需要计算请求的响应速度；

实现：可以根据响应时间进行打分，计算权重。

3、观察模式法

观察者模式是综合了最小连接数和最快响应度，同时考量这两个指标数，进行一个权重的分配。

手写随机算法

随机算法和随机加权算法是比较简单的,接下来我们用代码实现一下

完全随机算法

首先我们把服务器ip储存下来,再调用random就可以随机获得一个服务器ip

//服务器IP
public class ServerIps {
    public static final List<String> LIST = Arrays.asList(
            "A",
            "B",
            "C"
    );
}

随机的方法

//随机
public class RandomSelect {
    public static String getServer(){
        Random random = new Random();
        int rand = random.nextInt(ServerIps.LIST.size());
        return ServerIps.LIST.get(rand);
    }
}

我们用一个测试类来测试随机算法,size越大的话,测出来的数据也就也越接近真实情况

public class Test {
    public static void main(String[] args) {
                //三台服务器IP的调用概率
                double a = 0, b = 0, c = 0;
                int size = 100000;
                String ip = "";
                for (int i = 0; i < size; i++) {
                    ip = RandomSelect2.getServer();
                    if (ip.equals("A")) {
                        a++;
                    }
                    if (ip.equals("B")) {
                        b++;
                    }
                    if (ip.equals("C")) {
                        c++;
                    }
                }
                System.out.println(a / size + "\n" + b / size + "\n" + c / size + "");
    }
}

测试完全随机算法

可以看到结果很接近1：1：1 ,比较符合我们的结论：将请求随机分配到各个节点。由概率统计理论得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于平均分配，也就是轮询的结果。

加权随机算法

由于访问概率大致相同，所以如果部分服务器性能不一致的话，容易导致性能差的服务器压力过大，所以要根据服务器性能不一致的情况，给性能好的服务器多处理请求，给差的少分配请求（能者多劳）所以就需要在随机算法的基础上给每台服务器设置权重，延伸为加权随机算法

1、将应用服务器集群的IP存到Map里,每个IP对应有一个权重
2、创建一个List,来将所有权重下的IP存到list里面如：A 权重为3，则需要加入3个IP，B 权重为4，则需要加入4个IP
3、在0~所有权重之和的范围中选出一个随机数，这个随机数对应List的位置即是当前选取出来的IP地址
4、在调用量越大的情况下，每台服务器的流量分配处理概率越均衡（性能好的能分配较多的流量）

接下来我们来实现一个加权随机算法,首先还是把我们的服务器储存一下

     /**
      * 服务器列表<服务器地址,权重>
      */
public static Map<String, Integer> map = new HashMap<String, Integer>() {
         {
             put("A", 2);
             put("B", 3);
             put("C", 5);
         }
     };

我们分配的权重 A:2 B:3 C:5

public class RandomSelect2 {
         /**
         * 获取IP
         * @return
         */
        public static String getServer() {
            List<String> ipList = new ArrayList<String>();
            for (Map.Entry<String, Integer> item : map.entrySet()) {
                //将每个权重W 下的IP添加 W次，来满足随机权重
                for (int i = 0; i < item.getValue(); i++) {
                    ipList.add(item.getKey());
                }
            }
            //当前服务器IP地址的权重之和
            int allWeight = map.values().stream().mapToInt(a -> a).sum();
            System.out.println(allWeight + "");
            //随机选取一个IP
            int number = random.nextInt(allWeight);
            System.out.println(Arrays.toString(ipList.toArray()));
            return ipList.get(number);
        }
}

我们继续用测试类来测试随机加权算法,size越大的话,测出来的数据也就也越接近真实情况

public class Test {
    public static void main(String[] args) {
                //三台服务器IP的调用概率
                double a = 0, b = 0, c = 0;
                int size = 100000;
                String ip = "";
                for (int i = 0; i < size; i++) {
                    ip = RandomSelect2.getServer();
                    if (ip.equals("A")) {
                        a++;
                    }
                    if (ip.equals("B")) {
                        b++;
                    }
                    if (ip.equals("C")) {
                        c++;
                    }
                }
                System.out.println(a / size + "\n" + b / size + "\n" + c / size + "");
    }
}

测试随机加权算法

可以看到结果很接近 A:2 B:3 C:5 ,这就是随机加权算法啦 , 给性能好的服务器多处理请求，给差的少分配请求（能者多劳）

轮询算法

假设有 N 台服务器 S = {S0, S1, S2, …, Sn}，算法可以描述为：
1、从 S0 开始依次调度 S1, S2, …, Sn；
2、若所有服务器都已被调度过，则从头开始调度；

轮询算法与服务器权重没有关系，每个服务器有序的会被轮询到。

//轮询算法
public class RoundRobin {
    static int index = 0;
    public static String getServer() {
         if (index == ServerIps.LIST.size()) {
            index = 0;
        }
        return ServerIps.LIST.get(index++);
    }
}

用测试类来测试轮询算法,size越大的话,测出来的数据也就也越接近真实情况

public class Test {
    public static void main(String[] args) {
                //三台服务器IP的调用概率
                double a = 0, b = 0, c = 0;
                int size = 100000;
                String ip = "";
                for (int i = 0; i < size; i++) {
                    ip = RandomSelect2.getServer();
                    if (ip.equals("A")) {
                        a++;
                    }
                    if (ip.equals("B")) {
                        b++;
                    }
                    if (ip.equals("C")) {
                        c++;
                    }
                }
                System.out.println(a / size + "\n" + b / size + "\n" + c / size + "");
    }
}

测试轮询算法

加权轮询算法

其实和加权随机本质上差不多,都是把按照权重去添加再从头到尾的遍历,代码如下

//服务器IP
public class ServerIps {
    //带权重
    public static final Map<String,Integer> WEIGHT_LIST = new LinkedHashMap<>();
    static {
        WEIGHT_LIST.put("A",2);
        WEIGHT_LIST.put("B",3);
        WEIGHT_LIST.put("C",5);
    }

}

//缺点 权重大 ips越大 占内存 带权重随机
public class WeightRandom {
    public static String getServer(){
        //生成随机数作为list下标
        List<String> ips = new ArrayList<>();

        for(String ip : ServerIps.WEIGHT_LIST.keySet()){
            Integer weight = ServerIps.WEIGHT_LIST.get(ip);
            //weight 多少 再ips里面存多少 例如A 权重2 就在ips里存2个A
            for(int i = 0;i < weight;i++){
                ips.add(ip);
            }
        }
        Random random = new Random();
        int randomPos = random.nextInt(ips.size());
        return ips.get(randomPos);
    }
}

这个就不进行测试了最后结果也是符合结论

下面有另外一种更高级的算法来实现加权轮询

实现加权轮询的优化

讲解1

假设我们以10次请求来作为一个单位,我们可以发现，请求次数小于权重,就可以放到响应的区域里,比如0,权重小于2,我们就可以放到第一个位置,
可以得到一个公式,请求的次数-权重值,如果小于0 说明次数在权重值的范围内如果不小于0（大于等于）说明没在这个区间内就要往后面去找
比如 6 先减去2 发现大于0 说明不在这个权重范围 ,去找下一个权重,再减去3,发现还大于0,就找到了5这个权重.

//服务器IP
public class ServerIps {
    public static final List<String> LIST = Arrays.asList(
            "A",
            "B",
            "C"
    );
    //带权重
    public static final Map<String,Integer> WEIGHT_LIST = new LinkedHashMap<>();
    static {
        WEIGHT_LIST.put("A",2);
        WEIGHT_LIST.put("B",3);
        WEIGHT_LIST.put("C",5);
    }
}

//轮询优化
public class WeightRoundRobin {
    public static String getServer(Integer num){
        //计算总权重
        int totalWeights = ServerIps.WEIGHT_LIST.values().stream().mapToInt(w -> w).sum();

        Integer pos = num % totalWeights;

        for(String ip:ServerIps.WEIGHT_LIST.keySet()){
            Integer weight = ServerIps.WEIGHT_LIST.get(ip);
            if(pos < weight){
                return ip;
            }
            pos = pos - weight;
        }
        return "";
    }
    public static void main(String[] args){
        for (int i = 0;i < 10;i++){
            System.out.println(getServer(i));
        }
    }

}

轮询优化

运行之后我们发现轮询了2次A 3次B 5次C 但是这个加权轮询算法是有缺点的
这个算法是先轮询A服务器,在轮询B服务器,在轮询C服务器,所以他在一段时间内去请求的服务器永远是一个,当某个服务器权重过大会造成某一个服务器压力比较大
所以产生了平滑加权轮询,接下来我们手写一个平滑加权轮询

平滑加权轮询

平滑加权轮询会把轮询的请求打散让每个服务器都比较均衡的获得请求避免了同一个时刻大量请求打入,更加平衡

假设有 N 台服务器 S = {S0, S1, S2, …, Sn}，默认权重为 W = {W0, W1, W2, …, Wn}，当前权重为 CW = {CW0, CW1, CW2, …, CWn}。在该算法中有两个权重，默认权重表示服务器的原始权重，当前权重表示每次访问后重新计算的权重，当前权重的出初始值为默认权重值，当前权重值最大的服务器为 maxWeightServer，所有默认权重之和为 weightSum，服务器列表为 serverList，算法可以描述为：
1、找出当前权重值最大的服务器 maxWeightServer；
2、计算 {W0, W1, W2, …, Wn} 之和 weightSum；
3、将 maxWeightServer.CW = maxWeightServer.CW - weightSum；
4、重新计算 {S0, S1, S2, …, Sn} 的当前权重 CW，计算公式为 Sn.CW = Sn.CW + Sn.Wn
5、返回 maxWeightServer

平滑加权轮询
(第三行返回的服务器应该是A)

固定权重为 2,3,5 动态权重第一次设置为 0,0,0
我们是这样使用这个公式的 , 举个例子 2,3,5 当前的最大权重 max(currWeight) 是5, 5 定位到C服务器就返回一个C服务器 ,此时我们把C的权重减去总权重得到 -5;其他2个权重不变,我们就得到了动态变化的权重

第二次 ,我们把上一次的动态权重加上我们的固定权重得到新的权重得到新的权重 4,6,0 当前最大权重是6 权重变化后对应的服务器是B 返回一个B服务器,重复上一步骤,B的权重减去总权重得到新的动态权重 4,-4,0 以此类推10次便会发现动态权重又变回了 0,0,0

接下来我们来看看代码 ,

//平滑加权轮询
public class Weight {
    private String ip;
    private Integer weight;
    private Integer currentWeight;

    public Weight(String ip, Integer weight, Integer currentWeight) {
        this.ip = ip;
        this.weight = weight;
        this.currentWeight = currentWeight;
    }

    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }

    public Integer getCurrentWeight() {
        return currentWeight;
    }

    public void setCurrentWeight(Integer currentWeight) {
        this.currentWeight = currentWeight;
    }
}

然后是算法的具体实现

public class WeightRoundRobin2 {
    public static Map<String,Weight> currWeights = new HashMap<>();

    public static String getServer() {

        int totalWeights = ServerIps.WEIGHT_LIST.values().stream().mapToInt(w -> w).sum();

        //currentWeight 默认值 0
        if(currWeights.isEmpty()) {
            ServerIps.WEIGHT_LIST.forEach((ip,weight)->
            {
                currWeights.put(ip,new Weight(ip,weight,0));
            });
        }

        for(Weight weight: currWeights.values()) {
            weight.setCurrentWeight(weight.getCurrentWeight() + weight.getWeight());
        }

        //找最大值
        Weight maxCurrentWeight = null;
        for(Weight weight: currWeights.values()) {
            if(maxCurrentWeight == null || weight.getCurrentWeight() > maxCurrentWeight.getCurrentWeight()) {
                maxCurrentWeight = weight;
            }
        }

        maxCurrentWeight.setCurrentWeight( maxCurrentWeight.getCurrentWeight() - totalWeights);

        return maxCurrentWeight.getIp();
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(getServer());
        }
    }
}

接下来我们看看测试代码,我们可以发现轮询的请求已经被打散了不会在同一个时刻不断的访问同一个服务器了,
平滑加权轮询

一致性哈希环算法

一致性哈希算法在1997年由MIT的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题。

算法原理
虚拟一个环的概念，在环上构造一个0～232
将N台服务器节点计算Hash值，映射到这个环上
可以用节点的IP或者主机名来计算hash值

我们可以看到这里有一个环,环上面有4个哈希值,p1,p2,p3,p4 这四个哈希值对应四个服务器,用户可以访问其中的任何一台,我们通过哈希运算,把四个服务器的哈希值放到哈希环上去,这个哈希环是一个有序的哈希环 P1 < P2 < P3 < P4

一致性哈希环算法图例2
假如我们有一个userid的哈希值在P1和P4之间空白的位置,因为P4比P1大很多,这个点会去找比他大的最近的一个节点也就是P1,

一致性哈希环算法图例3
假如是这个的话,那么比他大的最近的一个节点就是P3, 那么根据这个哈希环的特点,我们发现我们需要一个能自动排列的数据结构,那么我们可以使用TreeMap来实现这个哈希环。

优化
我们可以思考一下,如果单纯使用这样的算法的话,那么只要落在P4和P1之间的userid都会去找P1主机,这样就会造成大量请求落在同一个主机上，会对主机造成大量的请求,我们可以用虚拟节点的方法来进行优化

我们可以看到有一些椭圆形的节点,这些就是我们虚拟出来的节点,映射的虚拟节点越多，哈希环就会越散列，流量就会分散的越小,处理的请求也会变的很均匀

这就是一致性哈希环算法的一种变种

TreeMap的讲解

TreeMap是一种红黑树,我们可以依靠他的特点来完成一致性哈希环算法,那我们是如何用TreeMap来实现呢？
我们可以来测试一下,我们先插入6个数据,

红黑树

我们通过tailMap()这个方法可以得到大于某个值后面的所有值

TreeMap<Integer,String> virtualNodes = new TreeMap<>();
       virtualNodes.put(1,"A");
       virtualNodes.put(2,"B");
       virtualNodes.put(3,"C");
       virtualNodes.put(4,"D");
       virtualNodes.put(5,"E");
       virtualNodes.put(6,"F");
       SortedMap<Integer, String> sortedMap = virtualNodes.tailMap(2);


       for (Map.Entry<Integer,String> entry : sortedMap.entrySet()){
           System.out.println(entry.getKey());
           System.out.println(entry.getValue());
           System.out.println("=========================");
       }

测试TreeMap的tailMap方法
我们可以看到,我们返回的值是大于2后面的所有值,我们可以使用另一个方法,TreeMap.FirstKey();

TreeMap<Integer,String> virtualNodes = new TreeMap<>();
       virtualNodes.put(1,"A");
       virtualNodes.put(2,"B");
       virtualNodes.put(3,"C");
       virtualNodes.put(4,"D");
       virtualNodes.put(5,"E");
       virtualNodes.put(6,"F");
       SortedMap<Integer, String> sortedMap = virtualNodes.tailMap(2);

       Integer integer = sortedMap.firstKey();
       System.out.println(integer);

测试TreeMap的firstKey方法
可以看到返回的是2,也就是大于该值的第一个节点,我们通过TreeMap就可以实现一致性哈希环算法.

这里有个关键点提示,假如你寻找的值比整个环上最大的值都大,就放到比P4大的那一段上面去就好了，也就是返回P1就行了

代码实现

//一致性hash 利用treemap实现
public class ConsistentHash {
    private static TreeMap<Integer,String> virtualNodes = new TreeMap();
    private static final int VIRTUAL_NODES = 160;//虚拟节点个数

    //预处理 哈希环
    static {
        //对每个真实节点添加虚拟节点 根据hash算法进行散列
        for(String ip: ServerIps.LIST) {
            for(int i = 0; i < VIRTUAL_NODES; i++) {
                int hash = getHash(ip+"VN"+i);
                virtualNodes.put(hash,ip);
            }
        }
    }

    public static String getServer(String clientInfo) {
        int hash = getHash(clientInfo);
        //得到大于该Hash值的子红黑树
        SortedMap<Integer,String> subMap = virtualNodes.tailMap(hash);
        //获取该子树最小元素
        Integer nodeIndex = subMap.firstKey();

        //没有大于该元素的子树 取整树的第一个元素
        if (nodeIndex == null) {
            nodeIndex = virtualNodes.firstKey();
        }
        return virtualNodes.get(nodeIndex);
    }


    //hash算法
    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< 20;i++){
            System.out.println(getServer("userid"+i));
        }
    }
}

测试一致性哈希环算法
这样我们就实现了一致性哈希环算法！

个人学习

负载均衡

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

设计模式学习（设计模式原则和单例模式）上一篇

Mysql索引底层结构和算法下一篇

手写负载均衡算法（随机,轮询，加权随机,加权轮询,平滑加权轮询,一致性哈希算法）