分布式负载均衡算法的实现
程序员文章站
2022-06-25 15:54:26
在分布式项目中，为了提高系统的可用性，服务提供者一般都会做集群处理，当其中一个服务出现宕机的时候，集群的其他服务仍然能够提供服务，从而提高系统的可靠性。 常用的负载均衡算法有： 随机算法 加权随机算*询算法 加权轮询算法 最小时延算法 一致性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算法
先构造一个长度为232的整数环（这个环被称为一致性hash环），根据节点名称的hash值（其分布为[0, 232-1]）将服务器节点放置在这个hash环上，
然后根据数据的key值计算得到其hash值（其分布也为[0, 232-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算法和增加虚拟节点解决分布不均的问题。
后话
以上的实现仅提供一种思路，实际使用时应该根据实际情况进行性能测试和优化。
上一篇： java-上转型对象&抽象类-学习记录