手写分布式负载均衡算法（一）
负载均衡在实际工作项目中是很普遍的，主要分为硬件负载均衡和软件负载均衡。硬件负载均衡主要有F5、Array等。都是一些商用的负载均衡器。软件负载均衡主要包括耳熟能详的Nginx、LVS、Tengine等，使用起来成本比较低，但是也要去维护。
今天讨论的是常用的负载均衡算法。
随机算法：顾名思义 根据服务器列表大小值随机选取一台服务器访问。
带权重的随机算法实现：
通过生成的随机数，计算这个随机数所落入的区间，即可知道选中哪台服务器，比如如果随机数3，则在区间[0,5)选中服务器A，随机数为7则选中B服务器。
import java.util.HashMap;import java.util.Map;public class IpMap {static Map<String,Integer> ipAddrs = new HashMap();static {ipAddrs.put("A",5);ipAddrs.put("B",3);ipAddrs.put("C",2);}}
import java.util.*;public class Random01 {//不考虑权重public static String getIpNoWeight(){Set ipSet = new HashSet();for(String ip:IpMap.ipAddrs.keySet()){ipSet.add(ip);}List<String> ipList = new ArrayList<>();ipList.addAll(ipSet);Integer random = new Random().nextInt(ipList.size());return ipList.get(random);}//考虑权重public static String getIpWithWeight01(){List<String> ipList = new ArrayList<>();for(String ip:IpMap.ipAddrs.keySet()){Integer weight = IpMap.ipAddrs.get(ip);for(int i=0;i<weight;i++){ipList.add(ip);}}Integer random = new Random().nextInt(ipList.size());return ipList.get(random);}public static String getIpWithWeight02(){int totalweight = 0;boolean sameweight = true;Object[] weights = IpMap.ipAddrs.values().toArray();for(int i=0;i<weights.length;i++){totalweight +=(int) weights[i];if(sameweight && i>0 && !weights[i].equals(weights[i-1])){sameweight = false;}}Integer random = new Random().nextInt(totalweight);if(!sameweight){for(String ip:IpMap.ipAddrs.keySet()){Integer value = IpMap.ipAddrs.get(ip);if(random<value){return ip;}random = random - value;}}//权重相同，相当于不考虑权重完全随机return getIpNoWeight();}public static void main(String[] args) {for(int i=0;i<10;i++){//System.out.println(getIpNoWeight());System.out.println(getIpWithWeight02());}}}
轮询算法：
有一种方法，调用编号，比如第1次调用为1，第2次调用为2，第100次调用为100，调用的编号是递增的，所以可以根据调用的编号推算出服务器。
Server=[]A,B,C]对应权重weights=[2,3,5]权重和为10；
如果调用10次，调用顺序为AABBBCCCCC
可以对权重和取余。
1号调用，1%10=1；2号调用，2%10=2......100号调用，100%10=0。可以发现编号在0-9之间。可以根据这10个数字找到对应的服务器。方法与上面类似，可以把权重想象为坐标轴“0-2-5-10”。
上面的方法，其实有一个弊端，如果一台服务器的权重特别大，他就会连续处理请求，此时可以使用平滑加权轮询。
每个服务器对应两个权重，分别为weight和currentWeight。weight固定，currentWeight动态变化，初始值为0。有新的请求进来时，遍历服务器列表，让它的currentWeight加上自身权重，遍历完后，找到最大的currentWeight，将其减去权重，然后返回对应服务器。
请求编号1中，初始值为[5, 1, 1]，数组中最大的值5，那么选择结果为A，选择后最大的值5减去权重和7，变成了[-2, 1, 1]；
请求编号2来的时候，[-2, 1, 1]加上[5, 1, 1]，那么就变成编号2中的初始值为[3, 2, 2]，数组中最大的值3，那么选择结果为A，最大的值3减去权重和7，变成了[-4, 2, 2]；
请求编号3来的时候，[-4, 2, 2]加上[5, 1, 1]，那么就变成编号2中的初始值为[1, 3, 3]，数组中最大的值3，那么选择结果为B，最大的值3减去权重和7，变成了[1, -4, 3]；
以此类推。。。。。。。。
package fuzaijunheng;import java.util.*;public class Round02 {private static Integer pos =0;//不考虑权重public static String getIpNoWeight(){String serverIp = null;synchronized (pos){if(pos>=IpMap.ipAddrs.size()){pos=0;}HashSet<String> ipSet = new HashSet<>();for(String ip:IpMap.ipAddrs.keySet()){ipSet.add(ip);}ArrayList<String> ipList = new ArrayList<>();ipList.addAll(ipSet);serverIp = ipList.get(pos);pos++;}return serverIp;}//考虑权重（简单的就不演示了）static int num=0;public static String getIpWithWeight(){int totalWeight=0;boolean sameWeight=true;Object[] weights = IpMap.ipAddrs.values().toArray();for(int i=0;i<weights.length;i++){Integer weight=(Integer)weights[i];totalWeight +=weight;if(sameWeight&&i>0&& !weight.equals(weights[i-1])){sameWeight=false;}}Integer sequenceNum = ++num;Integer offset = sequenceNum % totalWeight;offset = offset==0?totalWeight: offset;if(!sameWeight){for(String ip:IpMap.ipAddrs.keySet()){Integer weight = IpMap.ipAddrs.get(ip);if(offset<=weight){return ip;}offset = offset - weight;}}return null;}//平滑加权private static Map<String,Weight> weightMap = new HashMap<>();public static String getIpwithCurrentWeight(){int totalWeight = 0;for(int weigh: IpMap.ipAddrs.values()){totalWeight+=weigh;}//初始化weightMap,初始化currentWeight复制为weightif(weightMap.isEmpty()){IpMap.ipAddrs.forEach((key, value)->{weightMap.put(key,new Weight(key,value,value));});}//找出currentWeight最大值Weight maxCurrentWeight = null;for(Weight weight:weightMap.values()){if(maxCurrentWeight==null || weight.getCurrentWeight()>maxCurrentWeight.getCurrentWeight()){maxCurrentWeight = weight;}}//将maxcurrentWeight减去权重和maxCurrentWeight.setCurrentWeight(maxCurrentWeight.getCurrentWeight() -totalWeight);//所有ip的currentWeight统一加上权重for(Weight weight1:weightMap.values()){weight1.setCurrentWeight(weight1.getCurrentWeight()+weight1.getWeight());}return maxCurrentWeight.getIp();}public static void main(String[] args) {for(int i=0;i<10;i++){System.out.println(getIpwithCurrentWeight());}}}class Weight{private String ip;private Integer weight;private Integer currentWeight;public Weight(String ip, Integer weight, Integer currentWeight) {this.ip = ip;this.weight = weight;this.currentWeight = currentWeight;}public String getIp() {return ip;}public void setIp(String ip) {this.ip = ip;}public Integer getWeight() {return weight;}public void setWeight(Integer weight) {this.weight = weight;}public Integer getCurrentWeight() {return currentWeight;}public void setCurrentWeight(Integer currentWeight) {this.currentWeight = currentWeight;}}