分布式负载均衡算法的实现
2019-04-18 08:56:40来源:博客园 阅读 ()
在分布式项目中,为了提高系统的可用性,服务提供者一般都会做集群处理,当其中一个服务出现宕机的时候,集群的其他服务仍然能够提供服务,从而提高系统的可靠性。
常用的负载均衡算法有:
- 随机算法
- 加权随机算法
- 轮询算法
- 加权轮询算法
- 最小时延算法
- 一致性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 { //使用一个Map来缓存每类应用的轮询索引 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计算后,定位到如图中所示位置,它会顺时针查找下一个节点,选择第一个查找到的节点。
这里存在几个关键问题:
1. hash算法的影响
如果hash算法计算结果过于集中,如下图,节点分布再很小的范围内,如果消费者大部分命中范围之外,就会导致node1负载异常的大,出现负载不均衡的问题。
所以需要一个比较好的hash算法。
解决这个问题的办法是需要选择一个好的hashcode算法,hash算法比较
2. 增加或者删除节点时会导致负载不均衡
如下图:
正常情况下每个节点都是25%的命中概率
节点node2失效时,之前节点2的所有命中全部加到节点3,导致节点3的负载变大
当增加节点5时,之前节点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;
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<Integer, ProviderConfig> subMap = sortedMap.subMap(requestHashcCode,Integer.MAX_VALUE);
ProviderConfig result= null;
if(subMap.size() != 0){
Integer index = subMap.firstKey();
result = subMap.get(index);
}
else{
result = sortedMap.get(0);
}
//// 打印测试数据
new PrintResult(sortedMap,requestHashcCode).print();
/////
return result;
}
private String getKey(String host,int port,String node){
return new StringBuilder().append(host).append(":").append(port).append(node).toString();
}
private int caculHash(String str){
/* int hashCode = str.hashCode();
hashCode = (hashCode<0)?(-hashCode):hashCode;
return hashCode;*/
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;
}
}
//用于打印测试数据
@Data
class PrintResult{
private boolean flag =false;
private SortedMap<Integer, ProviderConfig> sortedMap;
private int requestHashcCode;
public PrintResult(SortedMap<Integer, ProviderConfig> sortedMap, int requestHashcCode) {
this.sortedMap = sortedMap;
this.requestHashcCode = requestHashcCode;
}
public void print(){
sortedMap.forEach((k,v)->{
if( (false == flag) && ( k > requestHashcCode)){
System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
}
System.out.println("hashcode: " + k + " " + v.getHost()+":"+v.getPort());
if( (false == flag) && ( k > requestHashcCode)){
System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
flag = true;
}
});
System.out.println("------------------请求的hashcode:"+requestHashcCode);
}
}
测试:
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);
1. 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
可以看到JDK默认的hashcode方法的问题,各个虚拟节点都是比较集中,会出现很严重的负载不均衡问题。
2.使用 FNV1_32_HASH算法
hashcode: 87760808 127.0.0.1:1926
hashcode: 127858684 127.0.0.1:2285
hashcode: 137207685 127.0.0.1:4429
hashcode: 189558739 127.0.0.1:4429
hashcode: 345597173 127.0.0.1:1926
hashcode: 411873143 127.0.0.1:5844
hashcode: 427733007 127.0.0.1:4429
hashcode: 429935214 127.0.0.1:5844
hashcode: 471059330 127.0.0.1:6013
hashcode: 508134701 127.0.0.1:6141
hashcode: 537200659 127.0.0.1:4429
hashcode: 572740331 127.0.0.1:9615
hashcode: 584730561 127.0.0.1:4429
hashcode: 586630909 127.0.0.1:6013
hashcode: 588198036 127.0.0.1:6297
hashcode: 601750027 127.0.0.1:6013
hashcode: 670864146 127.0.0.1:6297
hashcode: 823792818 127.0.0.1:9615
hashcode: 832758991 127.0.0.1:2285
hashcode: 847195135 127.0.0.1:1926
hashcode: 852642706 127.0.0.1:92
hashcode: 855431312 127.0.0.1:1926
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
hashcode: 1008339891 127.0.0.1:6430
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
hashcode: 1126143483 127.0.0.1:9615
hashcode: 1127241369 127.0.0.1:9615
hashcode: 1169946536 127.0.0.1:6297
hashcode: 1184995718 127.0.0.1:92
hashcode: 1204728048 127.0.0.1:5844
hashcode: 1218277576 127.0.0.1:2285
hashcode: 1253667665 127.0.0.1:92
hashcode: 1294893013 127.0.0.1:9615
hashcode: 1334096245 127.0.0.1:2285
hashcode: 1591823392 127.0.0.1:92
hashcode: 1597482385 127.0.0.1:6141
hashcode: 1647613853 127.0.0.1:6430
hashcode: 1653621871 127.0.0.1:6013
hashcode: 1749432497 127.0.0.1:6297
hashcode: 1765516223 127.0.0.1:92
hashcode: 1860173617 127.0.0.1:6430
hashcode: 1883591368 127.0.0.1:2285
hashcode: 1941022162 127.0.0.1:6430
hashcode: 1952262824 127.0.0.1:6141
hashcode: 1991871891 127.0.0.1:1926
hashcode: 2009814649 127.0.0.1:5844
hashcode: 2011432907 127.0.0.1:6297
hashcode: 2020508878 127.0.0.1:6141
hashcode: 2083262842 127.0.0.1:6013
hashcode: 2086348077 127.0.0.1:6141
hashcode: 2107422149 127.0.0.1:6430
hashcode: 2117355968 127.0.0.1:5844
------------------请求的hashcode:986344464
选择结果:127.0.0.1:6430
可以看到,各个虚拟节点分布相对较散,能够达到较好的效果。
总结
以上给了各个负载均衡算法的实现思路和代码实现,测试结果。
现总结如下:
随机算法:
好的随机算法可以使选择比较均衡,但还是会出现机器性能差异导致的调用耗时不一样。优点是实现简单。
加权随机算法:
可以根据不同的机器性能调整不同的权重比,从而降低机器性能差异带来的问题。
轮询算法:
可以使每个节点的选中概率一致,但也会出现随机算法的问题。
加权轮询:
可以根据不同的机器性能调整不同的权重比,从而降低机器性能差异带来的问题。
最小时延算法:
根据服务调用耗时动态调整,可以达到比较好的负载均衡。缺点是实现比较复杂。
一致性hash算法:
可以使消费者始终对应一个服务提供者。缺点是实现相对复杂。同时通过优化hashcode算法和增加虚拟节点解决分布不均的问题。
后话
以上的实现仅提供一种思路,实际使用时应该根据实际情况进行性能测试和优化。
原文链接:https://www.cnblogs.com/lgjlife/p/10727245.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:如何正确使用Java序列化?
- 聊聊微服务架构及分布式事务解决方案! 2020-06-10
- 作为一个面试官,我想问问你Redis分布式锁怎么搞? 2020-06-10
- 分布式锁没那么难,手把手教你实现 Redis 分布锁!|保姆级教 2020-06-08
- 【从单体架构到分布式架构】(二)请求增多,单点变集群(1) 2020-06-07
- Spring Cloud Ribbon 客户端负载均衡 2020-06-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash