nginx轮询算法
首先声明，写这个主要是因为最近同事面试的时候，面试官题了一个问题，是关于负载均衡的。以及负载均衡中轮询算法的具体实现。所以就查了下网上的大神，结果有所收获。这里找到一篇不错的文章。但是里面的算法实现不是使用的java。所以我是搬运工。这里只是贴出了自己的代码，具体思路可以参考传送门：负载均衡之轮询算法 - CSDN博客
自己的具体实现。
1.轮询算法(Round-Robin)
package com.jiyx.test.nginx;
/**
* nginx的轮询算法，这个是没有权重的轮询，也可以是所有的权重相同，ng配置类似下面：
* upstream cluster {
* server a ;
* server b ;
* server c ;
* }
* 这个算法没什么好说的，很简单的轮询
* auther: jiyx
* date: 2018/5/31.
*/
public class Loop {
private static int index =0;
/**
* 选择服务器
* @param servers 服务器列表
* @return
*/
public static String choice(String... servers) {
if (index == servers.length) {
index =0;
}
return servers[index++ % servers.length];
}
}
2.加权轮询算法(WeightedRound-Robin)
2.1普通的加权轮询
package com.jiyx.test.nginx;
/**
* nginx的轮询算法，这个是有权重的轮询，ng配置如下：
* upstream cluster {
* server a weight=1;
* server b weight=2;
* server c weight=4;
* }
* 这里轮询算法为何要如此复杂呢，是因为要做到均匀，如上的服务器配置。
* 当有访问时我们不能让访问的顺序是{a,b,b,c,c,c,c},这样就算c的服务器性能优越，
* 也可能会降低c服务器的性能。最好能达到{c,b,c,a,c,b,c}的类似效果，不让某一台
* 的压力过大
* auther: jiyx
* date: 2018/5/31.
*/
public class LoopWeight {
private static int currentWeight =0;
/**
* 计算最小公倍数,贼喜欢这个算法，简便的一批
* @param fnum 求取最小公倍数的第一个数
* @param snum 求取最小公倍数的第二个数
* @return
*/
private static int gcd(int fnum,int snum) {
if (fnum ==0 || snum ==0) {
return 0;
}
int temp;
while (snum !=0) {
temp = snum;
snum = fnum % snum;
fnum = temp;
}
return fnum;
}
/**
* 对数组元素求和
* @param arr 待求和数组
* @param size 需要求和的长度
* @return
*/
private static int getSum(Server[] arr,int size) {
if (size > arr.length) {
throw new IllegalArgumentException("请在数组长度范围内求和");
}
if (arr ==null || arr.length <1) {
throw new IllegalArgumentException("请传入合适长度的数组");
}
int sum =0;
for (int i =0; i < size; i++) {
sum += arr[i].getWeight();
}
return sum;
}
/**
* 求取数组元素的最小公倍数
* @param arr 数组
* @param size 长度
* @return
*/
private static int getGcd(Server[] arr,int size) {
if (size > arr.length) {
throw new IllegalArgumentException("请在数组长度范围内求和");
}
if (arr ==null || arr.length <1) {
throw new IllegalArgumentException("请传入合适长度的数组");
}
int gcd = arr[0].getWeight();
if (arr.length ==1 || size ==1) {
return gcd;
}
for (int i =0; i < size; i++) {
gcd =gcd(gcd, arr[i].getWeight());
}
return gcd;
}
/**
* 获取指定长度下的最大值
* @param arr 数组
* @param size 指定长度
* @return
*/
private static int getMax(Server[] arr,int size) {
if (size > arr.length) {
throw new IllegalArgumentException("请在数组长度范围内求和");
}
if (arr ==null || arr.length <1) {
throw new IllegalArgumentException("请传入合适长度的数组");
}
int max = arr[0].getWeight();
if (arr.length ==1 || size ==1) {
return max;
}
for (int i =0; i < size; i++) {
max = max > arr[i].getWeight() ? max : arr[i].getWeight();
}
return max;
}
private static int getIndex(Server[] servers,int size,int gcd,int max,int index) {
while (true) {
index = (index +1) % size;
if (index ==0) {
currentWeight =currentWeight - gcd;
if (currentWeight <=0) {
currentWeight = max;
if (currentWeight ==0) {
return -1;
}
}
}
if (servers[index].getWeight() >=currentWeight) {
return index;
}
}
}
/**
* 选择服务器
* @param servers
* @param size
*/
public static void choice(Server[] servers,int size) {
int gcd =getGcd(servers, size);
int max =getMax(servers, size);
int sum =getSum(servers, size);
int index = -1;
for (int i =0; i < sum; i++) {
index =getIndex(servers, size, gcd, max, index);
System.out.println(servers[index].toString());
}
}
}
2.2.平滑的加权轮询
这个算是删减版的，自己根据思路直接实现，没有模仿了
package com.jiyx.test.nginx;
/**
* LoopWeight的有权重的轮询算法，算出来的分布可能会不均匀，如：
* upstream cluster {
* server a weight=5;
* server b weight=1;
* server c weight=1;
* }
* upstream cluster {
* server a weight=4;
* server b weight=2;
* server c weight=1;
* }
* 登这类的。
* 所以这里做一个改进，思路如下：
* 每次当请求到来，选取服务器时，会遍历数组中所有服务器。
* 对于每个服务器，让它的current_weight增加它的weight；
* 同时累加所有服务器的weight，并保存为total。
* 遍历完所有服务器之后，如果该服务器的current_weight是最大的，
* 就选择这个服务器处理本次请求。最后把该服务器的current_weight减去total。
* auther: jiyx
* date: 2018/5/31.
*/
public class LoopWeightAndCurrWeight {
private static int getMaxWeightIndex(Server[] servers) {
int maxCurrentWeight =0;
int index = -1;
for (int i =0; i < servers.length; i++) {
if (maxCurrentWeight < servers[i].getCurrent_weight()) {
maxCurrentWeight = servers[i].getCurrent_weight();
index = i;
}
}
return index;
}
public static void choice(Server[] servers) {
int total =0;
for (Server server : servers) {
total += server.getWeight();
server.setCurrent_weight(server.getCurrent_weight() + server.getWeight());
}
int index =getMaxWeightIndex(servers);
servers[index].setCurrent_weight(servers[index].getCurrent_weight() - total);
System.out.println(servers[index]);
}
}
Server类：
package com.jiyx.test.nginx;
/**
* 因为这里有了权重，所以定义一个pojo
* auther: jiyx
* date: 2018/5/31.
*/
public class Server {
private Stringname;
private int weight;
private int current_weight;
public Server() {
}
public Server(String name,int weight,int current_weight) {
this.name = name;
this.weight = weight;
this.current_weight = current_weight;
}
public Server(String name,int weight) {
this.name = name;
this.weight = weight;
}
@Override
public String toString() {
return "Server{" +
"name='" +name +'\'' +
", weight=" +weight +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getCurrent_weight() {
return current_weight;
}
public void setCurrent_weight(int current_weight) {
this.current_weight = current_weight;
}
}
