分布式负载均衡算法的实现

程序员文章站 2022-03-20 12:28:56

在分布式项目中，为了提高系统的可用性，服务提供者一般都会做集群处理，当其中一个服务出现宕机的时候，集群的其他服务仍然能够提供服务，从而提高系统的可靠性。常用的负载均衡算法有：随机算法加权随机算*询算法加权轮询算法最小时延算法一致性hash算法负载均衡追求的是每个服务提供者的负载一致 ......

在分布式项目中，为了提高系统的可用性，服务提供者一般都会做集群处理，当其中一个服务出现宕机的时候，集群的其他服务仍然能够提供服务，从而提高系统的可靠性。

常用的负载均衡算法有：

随机算法
加权随机算法
轮询算法
加权轮询算法
最小时延算法
一致性hash算法

负载均衡追求的是每个服务提供者的负载一致，不会出现负载不均衡的情况。

以下所有的代码见github：　测试代码

准备

这是一个服务提供者的pojo,包含了服务的host和port等信息

@slf4j
@data
@allargsconstructor
@noargsconstructor
public class providerconfig implements serializable{

    private static final long serialversionuid = 1;
    //通信host
    private string host;
    //通信端口
    private integer port;

    //请求接口名称
    private string interfacename;
    //请求方法
    private string[] methods;
    //应用名称
    private string application;
    //权重
    private int weight;
    //调用时间
    private int calltime;

}

定义负载均衡策略接口

public interface loadbalancestrategy {
　　//object为扩展参数
    public providerconfig select(list<providerconfig> configs, object object);
}

随机算法

随机算法，也就是从服务列表中随机选择一个，如果随机数产生算法不好，那么就会导致出现偏向性，导致有些服务命中概率高，有的服务命中概率低，甚至有的服务命中率为0。最后会导致命中率高的时延很严重。

随机算法的优点是其实现简单。

实现

也就是产生一个随机数，从服务list选择一个，很简单的算法。

public class randomloadbalancestrategy  implements loadbalancestrategy{

    @override
    public providerconfig select(list<providerconfig> configs, object object) {
        int index = new random().nextint(configs.size());
        return configs.get(index);
    }
}

测试

注：后面多处会使用这个方法进行测试

//strategy 　　负载均衡策略：随机，加权随机，轮询，加权轮询
//confignum　　生产者个数
//testcount　　测试次数

public void loadbalace(loadbalancestrategy strategy ,int confignum,int testcount ){

    list<providerconfig> configs = new arraylist<>();
    int[] counts = new int[confignum];


    for(int i = 0; i< confignum; i++){
        providerconfig config = new providerconfig();
        config.setinterfacename("com.serviceimpl");
        config.sethost("127.0.0.1");
        config.setport(i);
        config.setweight(new random().nextint(100));
        configs.add(config);
    }

    //system.out.println(configs);

    for(int i = 0; i< testcount ; i++){
        providerconfig config = strategy.select(configs,null);
       // system.out.println("选中的:"+config);
        integer count = counts[config.getport()];
        counts[config.getport()] = ++count;

    }

    for(int i = 0; i< confignum; i++){
        system.out.println("序号:" + i + " 权重：" + configs.get(i).getweight() + "--次数：" + counts[i]);
    }

}

执行测试

loadbalancestrategy strategy1 = new randomloadbalancestrategy();
loadbalace(strategy1,10,1000);

输出

随机负载均衡....
序号:0--次数：98
序号:1--次数：97
序号:2--次数：86
序号:3--次数：99
序号:4--次数：116
序号:5--次数：98
序号:6--次数：96
序号:7--次数：102
序号:8--次数：101
序号:9--次数：107

从测试结果来看，jdk的随机算法还是比较均匀的。

加权随机算法

加权随机就是在随机算法的基础上，给每个服务增加一个权重，权重越大，概率越大。

在应用进行分布式部署时，机器硬件性能和环境的差异会导致服务性能出现不一致。

为了解决这个问题，可以给性能差的服务降低权重，给性能好的服务增加权重，以尽可能达到负载均衡的效果。

加权随机算法

实现

分布式负载均衡算法的实现


public class weightrandomloadbalancestrategy implements loadbalancestrategy{

    @override
    public providerconfig select(list<providerconfig> configs, object object) {

        list<providerconfig> newconfigs = new arraylist<>();

        for(providerconfig config:configs){

            for(int i = 0; i< config.getweight(); i++){
                newconfigs.add(config);
            }
        }

        int index = new random().nextint(newconfigs.size()-1);
        return newconfigs.get(index);
    }
}

还是使用上面的测试代码loadbalace(loadbalancestrategy strategy ,int confignum,int testcount )进行测试。

system.out.println("加权随机负载均衡....");
loadbalancestrategy strategy2 = new weightrandomloadbalancestrategy();
loadbalace(strategy1,10,1000);

测试结果：

加权随机负载均衡....
序号:0 权重：44--次数：101
序号:1 权重：27--次数：63
序号:2 权重：22--次数：47
序号:3 权重：61--次数：134
序号:4 权重：97--次数：214
序号:5 权重：38--次数：72
序号:6 权重：42--次数：79
序号:7 权重：51--次数：113
序号:8 权重：16--次数：28
序号:9 权重：67--次数：149

可以看到，权重越大，命中概率页越大。

轮询算法

轮询算法就是，轮询所有的服务，每个服务命中的概率都是一样的，缺点还是和随机算法一样，还是无法解决机器性能差异的问题。

实现

public class pollingloadbalancestrategy implements loadbalancestrategy {

    //使用一个ｍap来缓存每类应用的轮询索引
    private map<string,integer> indexmap = new concurrenthashmap<>();

    public providerconfig select(list<providerconfig> configs, object object){

        integer index = indexmap.get(getkey(configs.get(0)));
        if(index == null){
            indexmap.put(getkey(configs.get(0)),0);
            return configs.get(0);
        }
        else {
            index++;
            if(index >= configs.size()){
                index = 0;
            }
            indexmap.put(getkey(configs.get(0)),index);
            return configs.get(index);
        }
    }

    public string getkey(providerconfig config){

        return  config.getinterfacename();
    }
}

测试

还是使用上面的方法

system.out.println("\r\n轮询负载均衡.....");
loadbalancestrategy strategy3 = new pollingloadbalancestrategy();
 loadbalace(strategy3,10,1000);

测试结果

轮询负载均衡.....
序号:0 权重：88--次数：100
序号:1 权重：82--次数：100
序号:2 权重：58--次数：100
序号:3 权重：68--次数：100
序号:4 权重：67--次数：100
序号:5 权重：57--次数：100
序号:6 权重：19--次数：100
序号:7 权重：43--次数：100
序号:8 权重：4--次数：100
序号:9 权重：35--次数：100

可以看到，测试1000次，每个应用命中的概率都是一样的。

加权轮询算法

原理和上面的加权随机算法一样

实现

public class weightpollingloadbalancestrategy implements loadbalancestrategy {

    private map<string,integer> indexmap = new concurrenthashmap<>();

    public providerconfig select(list<providerconfig> configs, object object){

        integer index = indexmap.get(getkey(configs.get(0)));
        if(index == null){
            indexmap.put(getkey(configs.get(0)),0);
            return configs.get(0);
        }
        else {

            list<providerconfig> newconfigs = new arraylist<>();

            for(providerconfig config:configs){

                for(int i = 0; i< config.getweight(); i++){
                    newconfigs.add(config);
                }
            }
            index++;
            if(index >= newconfigs.size()){
                index = 0;
            }
            indexmap.put(getkey(configs.get(0)),index);
            return newconfigs.get(index);

        }
    }

    public string getkey(providerconfig config){

        return  config.getinterfacename();
    }
}

测试

system.out.println("\r\n加权轮询负载均衡.....");
loadbalancestrategy strategy4 = new weightpollingloadbalancestrategy();
loadbalace(strategy4,10,1000);

输出

加权轮询负载均衡.....
序号:0 权重：77--次数：182
序号:1 权重：75--次数：150
序号:2 权重：22--次数：44
序号:3 权重：43--次数：86
序号:4 权重：59--次数：118
序号:5 权重：10--次数：20
序号:6 权重：1--次数：2
序号:7 权重：25--次数：50
序号:8 权重：85--次数：170
序号:9 权重：89--次数：178

可以看到，权重越大，命中的概率越大。

最小时延算法

由于机器性能的差异以及网络传输等原因，会导致集群中不同的应用调用时长不一样。

如果能降低调用耗时长的应用的命中率，提高调用耗时短的命中率，达到动态调整，从而实现最终的负载均衡，那么便可以解决以上性能差异的问题。

缺点是实现起来比较复杂，因为要计算启动之后平均调用耗时。

实现

public class leastactiveloadbalancestrategy implements  loadbalancestrategy{

    public providerconfig select(list<providerconfig> configs, object object){

        providerconfig[] registryconfigs= new providerconfig[configs.size()];
        configs.toarray(registryconfigs);

        arrays.sort(registryconfigs, new comparator<providerconfig>() {
            @override
            public int compare(providerconfig o1, providerconfig o2) {

                if(o1.getcalltime() < o2.getcalltime()){
                    return -1;
                }

                else  if(o1.getcalltime() == o2.getcalltime()){
                    return 0;
                }
                else {
                    return 1;
                }
            }
        });

        return registryconfigs[0];
    }
}

这里使用arrays.sort()来实现耗时排序。

测试

public void leastactiveloadbalance(loadbalancestrategy strategy ,int confignum){

        list<providerconfig> configs = new arraylist<>();

        for(int i = 0; i< confignum; i++){
            providerconfig config = new providerconfig();
            config.setinterfacename("com.serviceimpl");
            config.sethost("127.0.0.1");
            config.setport(i);
            config.setweight(i);
　　　　　　　//这里使用随机数来模拟调用耗时。
            config.setcalltime(new random().nextint(100));
            configs.add(config);
        }

        for(providerconfig c:configs){
            system.out.println("序号:" + c.getport()  +"--时延:" + c.getcalltime() );
        }
        system.out.println("--------------");
        providerconfig config = strategy.select(configs,null);
        system.out.println("最终选择　序号:" + config.getport()  +"--时延:" + config.getcalltime() );


 }

这里使用随机数来模拟调用耗时。

system.out.println("\r\n最小时延负载均衡.....");
loadbalancestrategy strategy5 = new leastactiveloadbalancestrategy();
leastactiveloadbalance(strategy5,10);

测试结果

最小时延负载均衡.....
序号:0--时延:83
序号:1--时延:3
序号:2--时延:60
序号:3--时延:52
序号:4--时延:73
序号:5--时延:74
序号:6--时延:37
序号:7--时延:59
序号:8--时延:83
序号:9--时延:2
--------------
最终选择　序号:9--时延:2

可以看到命中了耗时最小的应用。

一致性hash算法

先构造一个长度为2³²的整数环（这个环被称为一致性hash环），根据节点名称的hash值（其分布为[0, 2³²-1]）将服务器节点放置在这个hash环上，

然后根据数据的key值计算得到其hash值（其分布也为[0, 2³²-1]），接着在hash环上顺时针查找距离这个key值的hash值最近的服务器节点，完成key到服务器的映射查找。

一致性hash算法还可以实现一个消费者一直命中一个服务提供者。

如下图，一共有四个服务提供者

provider-1: 127.0.0.1:8001

provider-2: 127.0.5.2:8145

provider-3: 127.0.1.2:8123

provider-4: 127.1.3.2:8256

通过hash计算后，四个节点分布在hash环的不同位置上

当有一个消费者(127.0.0.1:8011)通过hash计算后，定位到如图中所示位置，它会顺时针查找下一个节点，选择第一个查找到的节点。

分布式负载均衡算法的实现

这里存在几个关键问题：

１.　hash算法的影响

如果hash算法计算结果过于集中，如下图，节点分布再很小的范围内，如果消费者大部分命中范围之外，就会导致node1负载异常的大，出现负载不均衡的问题。

所以需要一个比较好的hash算法。

分布式负载均衡算法的实现

解决这个问题的办法是需要选择一个好的hashcode算法,

２. 增加或者删除节点时会导致负载不均衡

如下图：

正常情况下每个节点都是25%的命中概率

节点node2失效时，之前节点2的所有命中全部加到节点３,导致节点3的负载变大

当增加节点5时，之前节点３的命中全部给了节点５,也还是出现了负载不均衡。

分布式负载均衡算法的实现

解决这个问题的办法是增加虚拟节点

如下图，为每个节点都增加了虚拟节点，增加虚拟节点，可以使整个hash环分布的更加均匀，但有个问题是，节点越多，维护的性能越大，因此，需要增加多少个虚拟节点，需要根据实际需要进行测试。

分布式负载均衡算法的实现

实现

虚拟节点的格式为　127.0.0.1:8001&&node1

分别使用jdk 的hashcode算法和fnv1_32_hash算法进行比较。　.

public class uniformityhashloadbalancestrategy  implements  loadbalancestrategy{

    private static final int virtual_nodes = 5;

　　　//object为消费者的　host:port　
    public providerconfig select(list<providerconfig> configs, object object){

        sortedmap<integer, providerconfig> sortedmap = new treemap();

        for(providerconfig config:configs){
            for(int j = 0; j < virtual_nodes; j++){
                sortedmap.put(caculhash(getkey(config.gethost(),config.getport(),"&&node"+j)),config);
            }
        }

        system.out.println(sortedmap);
        integer requesthashccode = caculhash((string)object);
        sortedmap.foreach((k,v)->{
            system.out.println("hashcode: " + k + "  " + v.gethost()+":"+v.getport());
        });
        system.out.println("------------------请求的hashcode:"+requesthashccode);

        sortedmap<integer, providerconfig> submap = sortedmap.tailmap(requesthashccode);
        integer index = submap.firstkey();
        return  submap.get(index);
    }
    private string getkey(string host,int port,string node){
        return new stringbuilder().append(host).append(":").append(port).append(node).tostring();
    }

　　//计算hash值
    private int caculhash(string str){
　　　　　//jdk 的　hashcode 
        /*int hashcode =  str.hashcode();
        hashcode = (hashcode<0)?(-hashcode):hashcode;
        return hashcode;*/

　　　　 //fnv1_32_hash　算法
        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 void uniformityhashloadbalancestrategytest(loadbalancestrategy strategy ,int confignum){

        list<providerconfig> configs = new arraylist<>();
        for(int i = 0; i< confignum; i++){
            providerconfig config = new providerconfig();
            config.setinterfacename("com.serviceimpl");
            config.sethost("127.0.0.1");
            config.setport(new random().nextint(9999));
            config.setweight(i);
            config.setcalltime(new random().nextint(100));
            configs.add(config);
        }

        providerconfig config = strategy.select(configs,"127.0.0.1:1234");
        system.out.println("选择结果:" + config.gethost() + ":" + config.getport());
    }

 system.out.println("\r\n一致性hash负载均衡.....");
uniformityhashloadbalancestrategytest(new uniformityhashloadbalancestrategy(),10);

１. jdk 的　hashcode 算法

hashcode: 441720772  127.0.0.1:1280
hashcode: 441720773  127.0.0.1:1280
hashcode: 441720774  127.0.0.1:1280
hashcode: 441720775  127.0.0.1:1280
hashcode: 441720776  127.0.0.1:1280
hashcode: 1307619854  127.0.0.1:3501
hashcode: 1307619855  127.0.0.1:3501
hashcode: 1307619856  127.0.0.1:3501
hashcode: 1307619857  127.0.0.1:3501
hashcode: 1307619858  127.0.0.1:3501
hashcode: 1363372970  127.0.0.1:779
hashcode: 1363372971  127.0.0.1:779
hashcode: 1363372972  127.0.0.1:779
hashcode: 1363372973  127.0.0.1:779
hashcode: 1363372974  127.0.0.1:779
hashcode: 1397780469  127.0.0.1:5928
hashcode: 1397780470  127.0.0.1:5928
hashcode: 1397780471  127.0.0.1:5928
hashcode: 1397780472  127.0.0.1:5928
hashcode: 1397780473  127.0.0.1:5928
hashcode: 1700521830  127.0.0.1:4065
hashcode: 1700521831  127.0.0.1:4065
hashcode: 1700521832  127.0.0.1:4065
hashcode: 1700521833  127.0.0.1:4065
hashcode: 1700521834  127.0.0.1:4065
hashcode: 1774961903  127.0.0.1:5931
hashcode: 1774961904  127.0.0.1:5931
hashcode: 1774961905  127.0.0.1:5931
hashcode: 1774961906  127.0.0.1:5931
hashcode: 1774961907  127.0.0.1:5931
hashcode: 1814135809  127.0.0.1:5050
hashcode: 1814135810  127.0.0.1:5050
hashcode: 1814135811  127.0.0.1:5050
hashcode: 1814135812  127.0.0.1:5050
hashcode: 1814135813  127.0.0.1:5050
hashcode: 1881959435  127.0.0.1:1991
hashcode: 1881959436  127.0.0.1:1991
hashcode: 1881959437  127.0.0.1:1991
hashcode: 1881959438  127.0.0.1:1991
hashcode: 1881959439  127.0.0.1:1991
hashcode: 1889283041  127.0.0.1:4071
hashcode: 1889283042  127.0.0.1:4071
hashcode: 1889283043  127.0.0.1:4071
hashcode: 1889283044  127.0.0.1:4071
hashcode: 1889283045  127.0.0.1:4071
hashcode: 2118931362  127.0.0.1:7152
hashcode: 2118931363  127.0.0.1:7152
hashcode: 2118931364  127.0.0.1:7152
hashcode: 2118931365  127.0.0.1:7152
hashcode: 2118931366  127.0.0.1:7152
------------------请求的hashcode:35943393
选择结果:127.0.0.1:1280

可以看到ｊｄｋ默认的hashcode方法的问题，各个虚拟节点都是比较集中，会出现很严重的负载不均衡问题。

２.使用　fnv1_32_hash算法

hashcode: 23525275  127.0.0.1:1340
hashcode: 28411340  127.0.0.1:2589
hashcode: 43226263  127.0.0.1:1340
hashcode: 117776908  127.0.0.1:2848
hashcode: 190736195  127.0.0.1:6316
hashcode: 193232709  127.0.0.1:2848
hashcode: 238271827  127.0.0.1:1340
hashcode: 304277099  127.0.0.1:1245
hashcode: 323839980  127.0.0.1:1340
hashcode: 527125849  127.0.0.1:1704
hashcode: 571281671  127.0.0.1:1704
hashcode: 575621854  127.0.0.1:3295
hashcode: 595383578  127.0.0.1:8294
hashcode: 611098804  127.0.0.1:6316
hashcode: 635348472  127.0.0.1:1245
hashcode: 645589927  127.0.0.1:2923
hashcode: 724716685  127.0.0.1:2589
hashcode: 751044093  127.0.0.1:6316
hashcode: 770120156  127.0.0.1:6316
hashcode: 826884147  127.0.0.1:1340
hashcode: 828747447  127.0.0.1:3295
hashcode: 845151891  127.0.0.1:2923
hashcode: 1009576302  127.0.0.1:8294
hashcode: 1012854319  127.0.0.1:3295
hashcode: 1128338730  127.0.0.1:2848
hashcode: 1193699998  127.0.0.1:1245
hashcode: 1256565279  127.0.0.1:5227
hashcode: 1262478155  127.0.0.1:2848
hashcode: 1313976900  127.0.0.1:1704
hashcode: 1316234142  127.0.0.1:8294
hashcode: 1329044824  127.0.0.1:2589
hashcode: 1338628917  127.0.0.1:8294
hashcode: 1376780501  127.0.0.1:2923
hashcode: 1400591219  127.0.0.1:8294
hashcode: 1464238680  127.0.0.1:1704
hashcode: 1477774526  127.0.0.1:3295
hashcode: 1508307156  127.0.0.1:5227
hashcode: 1519292522  127.0.0.1:1245
hashcode: 1624736872  127.0.0.1:1704
hashcode: 1734567634  127.0.0.1:5227
hashcode: 1742088861  127.0.0.1:6316
hashcode: 1786711526  127.0.0.1:2923
hashcode: 1799136540  127.0.0.1:3295
hashcode: 1871586245  127.0.0.1:2589
hashcode: 1879550454  127.0.0.1:2923
hashcode: 1882602635  127.0.0.1:5227
hashcode: 1921744078  127.0.0.1:2848
hashcode: 1925433450  127.0.0.1:2589
hashcode: 2087729269  127.0.0.1:5227
hashcode: 2138998633  127.0.0.1:1245
------------------请求的hashcode:2064286659
选择结果:127.0.0.1:5227

可以看到，各个虚拟节点分布相对较散，能够达到较好的效果。

总结

以上给了各个负载均衡算法的实现思路和代码实现，测试结果。

现总结如下：

随机算法：

好的随机算法可以使选择比较均衡，但还是会出现机器性能差异导致的调用耗时不一样。优点是实现简单。

加权随机算法：

可以根据不同的机器性能调整不同的权重比，从而降低机器性能差异带来的问题。

轮询算法：

可以使每个节点的选中概率一致，但也会出现随机算法的问题。

加权轮询：

可以根据不同的机器性能调整不同的权重比，从而降低机器性能差异带来的问题。

最小时延算法：

根据服务调用耗时动态调整，可以达到比较好的负载均衡。缺点是实现比较复杂。

一致性hash算法：

可以使消费者始终对应一个服务提供者。缺点是实现相对复杂。同时通过优化hashcode算法和增加虚拟节点解决分布不均的问题。

后话

以上的实现仅提供一种思路，实际使用时应该根据实际情况进行性能测试和优化。

上一篇： .NET Framework 4.8发布

下一篇： [转载]DevExpress GridControl 使用方法技巧总结收录整理

分布式负载均衡算法的实现

准备

随机算法

实现

测试

加权随机算法

实现

轮询算法

实现

测试

加权轮询算法

实现

测试

最小时延算法

实现

测试

一致性hash算法

实现

测试：

总结

后话

Python实现的最近最少使用算法

Python实现的redis分布式锁功能示例

Python实现快速排序算法及去重的快速排序的简单示例

K均值聚类算法的Java版实现代码示例

基于Java实现的一层简单人工神经网络算法示例

详解利用nginx和docker实现一个简易的负载均衡

在OneProxy的基础上实行MySQL读写分离与负载均衡

Python实现的序列化和反序列化二叉树算法示例

[PHP] 算法-统计一个数字在排序数组中出现的次数的PHP实现

[PHP] 算法-数组归并排序并计算逆序对的个数的PHP实现