轮询算法
轮询算法就是通过一个算法，对提供的一组列表进行计算，按照一定规则取出列表中的元素，常见的有顺序模式、随机模式、加权模式，加权平滑模式。
定义轮询算法的接口：
/**
* 轮询算法接口
*/
public interface Balance<T> {
T chooseOne(List<T> list);
}
1、随机模式轮询
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));
}
}
}
2、顺序轮询模式
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));
}
}
}
3、加权模式
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
4、平滑加权模式
/**
* 权重模式均匀轮询
*
* 通俗语概述---摘抄网络
* 平滑加权轮询那个算法可以这样想：（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!
