当前位置:   article > 正文

java常见轮询算法

java常见轮询算法

轮询算法

轮询算法就是通过一个算法,对提供的一组列表进行计算,按照一定规则取出列表中的元素,常见的有顺序模式、随机模式、加权模式,加权平滑模式。

定义轮询算法的接口:

  1. /**
  2. * 轮询算法接口
  3. */
  4. public interface Balance<T> {
  5. T chooseOne(List<T> list);
  6. }

1、随机模式轮询

  1. public class RandomBalance<T> implements Balance<T> {
  2. private Random random = new Random();
  3. @Override
  4. public T chooseOne(List<T> list) {
  5. int sum = list.size();
  6. return list.get(random.nextInt(sum));
  7. }
  8. /**
  9. * 测试
  10. **/
  11. public static void main(String[] args) {
  12. List<Service> services = new ArrayList<>();
  13. for (int i = 0; i < 5; i++) {
  14. Service e = new Service();
  15. e.setIp("address:"+i);
  16. e.setWeight(1);
  17. services.add(e);
  18. }
  19. RandomBalance<Service> bl = new RandomBalance<>();
  20. for (int i = 0; i < services.size(); i++) {
  21. System.out.println(bl.chooseOne(services));
  22. }
  23. }
  24. }

2、顺序轮询模式

  1. public class QueueBalance<T> implements Balance<T> {
  2. private volatile int index = 0;
  3. public synchronized T chooseOne(List<T> list) {
  4. if(list==null||list.size()==0) return null;
  5. int sum = list.size();
  6. int temp = index % sum;
  7. T t = list.get(temp);
  8. index++;
  9. return t;
  10. }
  11. /**
  12. * 测试
  13. **/
  14. public static void main(String[] args) {
  15. List<Service> services = new ArrayList<>();
  16. for (int i = 0; i < 20; i++) {
  17. Service e = new Service();
  18. e.setIp("address:"+i);
  19. e.setWeight(1);
  20. services.add(e);
  21. }
  22. QueueBalance<Service> bl = new QueueBalance<>();
  23. for (int i = 0; i < services.size(); i++) {
  24. System.out.println(bl.chooseOne(services));
  25. }
  26. }
  27. }

3、加权模式

  1. public class WeightBalance implements Balance<Service> {
  2. private volatile static int index;
  3. @Override
  4. public synchronized Service chooseOne(List<Service> list) {
  5. int sum = list.stream().mapToInt(Service::getWeight).sum();
  6. int temp = 0;
  7. int cur = (index++) % sum;
  8. for (Service service : list) {
  9. temp = temp + service.getWeight();
  10. if(cur < temp) {
  11. return service;
  12. }
  13. }
  14. return null;
  15. }
  16. public static void main(String[] args) {
  17. List<Service> services = new ArrayList<>();
  18. Service server1 = new Service();
  19. server1.setIp("address1");
  20. server1.setWeight(1);
  21. Service server2 = new Service();
  22. server2.setIp("address2");
  23. server2.setWeight(3);
  24. Service server3 = new Service();
  25. server3.setIp("address3");
  26. server3.setWeight(5);
  27. services.add(server1);
  28. services.add(server2);
  29. services.add(server3);
  30. WeightBalance loadBalance = new WeightBalance();
  31. for (int i = 0; i < 20; i++) {
  32. System.out.println("第"+i+"次请求服务ip为:"+loadBalance.chooseOne(services).getIp());
  33. }
  34. }
  35. }

加权模式存在的问题就是,轮询是以权重值累加第一个小于当前index取模值,最后的结果就是Aserivde N次,Bservice N次,Cservice N次,我们要实现的效果的在总次数内,每个service调用的次数是自身权重在总权重的比例*总调用次数,并且这些调用次数是平滑分布的。这个效果就要看下面的SmoothWeightBalance

4、平滑加权模式

  1. /**
  2. * 权重模式均匀轮询
  3. *
  4. * 通俗语概述---摘抄网络
  5. * 平滑加权轮询那个算法可以这样想:(total是不变的,因为每次有一个节点减掉total后,每个节点都会加一次
  6. * 自身权重,所以总共又增加了一个total)每次选出节点后,都是减掉这个节点权重一个total;自身权重越大的节
  7. * 点增长越快,那么比其他节点大的几率就越高,被选中的机会就越多;而自身权重比较低的,自身current_weight
  8. * 增长比较慢,所以比其他大的几率小,被选中的机会就少。(挨的刀子是一样大的,但是哪棵韭菜长得快,哪棵就
  9. * 更容易挨刀子;东北大米年收1次,海南能收3次)
  10. */
  11. public class SmoothWeightBalance implements Balance<Service> {
  12. /**
  13. * 存储当前weight
  14. */
  15. private Map<String, Integer> map = new HashMap<>();
  16. /**
  17. * 加权平滑轮询
  18. * 实现原理:将请求为key,权重值初始为value,每一轮取最大的weight,然后将最大的weight-总数,再将每个递增自身weight。
  19. * 解析: 每一轮所有server的当前weight递增总数等于最大weight的server减少的总数,从而保证持续取值时减少不会将权重越减
  20. * 越少。而权重值越大,那么增长时抢占最大权重值的机会越大,这个几率值和初始weight成正比。就好比草长的越快,那么被割的机会越大。
  21. */
  22. public Service chooseOne(List<Service> services) {
  23. // 给予每个service的在map中的权重值为自身初始weight
  24. services.forEach(service ->
  25. map.computeIfAbsent(service.toString(), key -> service.getWeight())
  26. );
  27. int sum = services.stream().mapToInt(Service::getWeight).sum(); // 权重总数
  28. // 找当前weight值最大的server
  29. Service maxService = null;
  30. for (Service service : services) {
  31. Integer currentWeight = map.get(service.toString());
  32. if (maxService == null || currentWeight > map.get(maxService.toString())) {
  33. maxService = service; // 找当前weight最大的server
  34. }
  35. }
  36. // 将最大的 - total总数 (备注:默认weight获取:server.getWeight , 当前weight获取 : map.get(server.toString))
  37. map.put(maxService.toString(), map.get(maxService.toString()) - sum);
  38. // 递增所有server的weight值 (总递增数等于total)
  39. for (Service service : services) {
  40. Integer oldweight = map.get(service.toString());
  41. map.put(service.toString(), oldweight + service.getWeight());
  42. }
  43. return maxService;
  44. }
  45. /**
  46. * 测试
  47. */
  48. public static void main(String[] args) {
  49. List<Service> services = new ArrayList<>();
  50. Service server1 = new Service();
  51. server1.setIp("address1");
  52. server1.setWeight(1);
  53. Service server2 = new Service();
  54. server2.setIp("address2");
  55. server2.setWeight(3);
  56. Service server3 = new Service();
  57. server3.setIp("address3");
  58. server3.setWeight(5);
  59. services.add(server1);
  60. services.add(server2);
  61. services.add(server3);
  62. SmoothWeightBalance loadBalance = new SmoothWeightBalance();
  63. for (int i = 0; i < 20; i++) {
  64. System.out.println("第" + i + "次请求服务ip为:" + loadBalance.chooseOne(services).getIp());
  65. }
  66. }
  67. }

 

end!

 

 

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/289114
推荐阅读
相关标签
  

闽ICP备14008679号