赞
踩
轮询算法
轮询算法就是通过一个算法,对提供的一组列表进行计算,按照一定规则取出列表中的元素,常见的有顺序模式、随机模式、加权模式,加权平滑模式。
定义轮询算法的接口:
- /**
- * 轮询算法接口
- */
- public interface Balance<T> {
-
- T chooseOne(List<T> list);
- }
-
- public class RandomBalance<T> implements Balance<T> {
-
- private Random random = new Random();
-
- @Override
- public T chooseOne(List<T> list) {
- int sum = list.size();
- return list.get(random.nextInt(sum));
- }
-
- /**
- * 测试
- **/
- public static void main(String[] args) {
- List<Service> services = new ArrayList<>();
- for (int i = 0; i < 5; i++) {
- Service e = new Service();
- e.setIp("address:"+i);
- e.setWeight(1);
- services.add(e);
- }
- RandomBalance<Service> bl = new RandomBalance<>();
- for (int i = 0; i < services.size(); i++) {
- System.out.println(bl.chooseOne(services));
- }
- }
- }

- public class QueueBalance<T> implements Balance<T> {
-
- private volatile int index = 0;
-
- public synchronized T chooseOne(List<T> list) {
- if(list==null||list.size()==0) return null;
- int sum = list.size();
- int temp = index % sum;
- T t = list.get(temp);
- index++;
- return t;
- }
-
- /**
- * 测试
- **/
- public static void main(String[] args) {
- List<Service> services = new ArrayList<>();
- for (int i = 0; i < 20; i++) {
- Service e = new Service();
- e.setIp("address:"+i);
- e.setWeight(1);
- services.add(e);
- }
- QueueBalance<Service> bl = new QueueBalance<>();
- for (int i = 0; i < services.size(); i++) {
- System.out.println(bl.chooseOne(services));
- }
- }
-
- }

- public class WeightBalance implements Balance<Service> {
-
- private volatile static int index;
-
- @Override
- public synchronized Service chooseOne(List<Service> list) {
- int sum = list.stream().mapToInt(Service::getWeight).sum();
- int temp = 0;
- int cur = (index++) % sum;
- for (Service service : list) {
- temp = temp + service.getWeight();
- if(cur < temp) {
- return service;
- }
- }
- return null;
- }
-
- public static void main(String[] args) {
- List<Service> services = new ArrayList<>();
-
- Service server1 = new Service();
- server1.setIp("address1");
- server1.setWeight(1);
-
- Service server2 = new Service();
- server2.setIp("address2");
- server2.setWeight(3);
-
- Service server3 = new Service();
- server3.setIp("address3");
- server3.setWeight(5);
-
- services.add(server1);
- services.add(server2);
- services.add(server3);
-
- WeightBalance loadBalance = new WeightBalance();
-
- for (int i = 0; i < 20; i++) {
- System.out.println("第"+i+"次请求服务ip为:"+loadBalance.chooseOne(services).getIp());
- }
- }
-
- }

加权模式存在的问题就是,轮询是以权重值累加第一个小于当前index取模值,最后的结果就是Aserivde N次,Bservice N次,Cservice N次,我们要实现的效果的在总次数内,每个service调用的次数是自身权重在总权重的比例*总调用次数,并且这些调用次数是平滑分布的。这个效果就要看下面的SmoothWeightBalance
- /**
- * 权重模式均匀轮询
- *
- * 通俗语概述---摘抄网络
- * 平滑加权轮询那个算法可以这样想:(total是不变的,因为每次有一个节点减掉total后,每个节点都会加一次
- * 自身权重,所以总共又增加了一个total)每次选出节点后,都是减掉这个节点权重一个total;自身权重越大的节
- * 点增长越快,那么比其他节点大的几率就越高,被选中的机会就越多;而自身权重比较低的,自身current_weight
- * 增长比较慢,所以比其他大的几率小,被选中的机会就少。(挨的刀子是一样大的,但是哪棵韭菜长得快,哪棵就
- * 更容易挨刀子;东北大米年收1次,海南能收3次)
- */
- public class SmoothWeightBalance implements Balance<Service> {
-
- /**
- * 存储当前weight
- */
- private Map<String, Integer> map = new HashMap<>();
-
- /**
- * 加权平滑轮询
- * 实现原理:将请求为key,权重值初始为value,每一轮取最大的weight,然后将最大的weight-总数,再将每个递增自身weight。
- * 解析: 每一轮所有server的当前weight递增总数等于最大weight的server减少的总数,从而保证持续取值时减少不会将权重越减
- * 越少。而权重值越大,那么增长时抢占最大权重值的机会越大,这个几率值和初始weight成正比。就好比草长的越快,那么被割的机会越大。
- */
- public Service chooseOne(List<Service> services) {
- // 给予每个service的在map中的权重值为自身初始weight
- services.forEach(service ->
- map.computeIfAbsent(service.toString(), key -> service.getWeight())
- );
- int sum = services.stream().mapToInt(Service::getWeight).sum(); // 权重总数
-
- // 找当前weight值最大的server
- Service maxService = null;
- for (Service service : services) {
- Integer currentWeight = map.get(service.toString());
- if (maxService == null || currentWeight > map.get(maxService.toString())) {
- maxService = service; // 找当前weight最大的server
- }
- }
-
- // 将最大的 - total总数 (备注:默认weight获取:server.getWeight , 当前weight获取 : map.get(server.toString))
- map.put(maxService.toString(), map.get(maxService.toString()) - sum);
-
- // 递增所有server的weight值 (总递增数等于total)
- for (Service service : services) {
- Integer oldweight = map.get(service.toString());
- map.put(service.toString(), oldweight + service.getWeight());
- }
-
- return maxService;
- }
-
- /**
- * 测试
- */
- public static void main(String[] args) {
- List<Service> services = new ArrayList<>();
- Service server1 = new Service();
- server1.setIp("address1");
- server1.setWeight(1);
-
- Service server2 = new Service();
- server2.setIp("address2");
- server2.setWeight(3);
-
- Service server3 = new Service();
- server3.setIp("address3");
- server3.setWeight(5);
-
- services.add(server1);
- services.add(server2);
- services.add(server3);
-
- SmoothWeightBalance loadBalance = new SmoothWeightBalance();
-
- for (int i = 0; i < 20; i++) {
- System.out.println("第" + i + "次请求服务ip为:" + loadBalance.chooseOne(services).getIp());
- }
- }
- }

end!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。