- 一.什么是负载均衡（Load Balance）
- 二.简单的负责均衡思路
- 1.随机（Random）
- 1.1.思路
- 1.2.实现方式
- 2.轮询（Round Robin、RR）
- 1.1.思路
- 1.2.实现方式1
- 1.3.实现方式2
- 3.加权轮询（WeightedRound-Robin、WRR）
- 3.1.思路
- 3.2.实现方式1
- 3.3.实现方式2
- 3.4.实现方式3
- 4.加权随机（Weight Random、WR）
- 4.1.思路
- 4.2.实现方式
- 5.IPHash
- 5.1.思路
- 5.2.实现方式
- 三.可拓展的负载均衡实现
- 1.准备工作
- 负载节点类
- 负载抽象类
- 2.负载算法
- 1.完全随机
- 2.加权随机
- 2.1.节点复制
- 2.2.权重区间
- 3.简单轮询
- 4.加权轮询
- 4.1.节点复制
- 4.2.权重区间
- 4.3.平滑加权轮询
- 5.哈希
- 6.负载最低优先（仅了解）
使用N个服务器平均分担负载，不会因为某个服务器节点负载高宕机而某个节点闲置的情况。那么负载均衡的前提就是要有多个服务器才能实现，也就是两个以上即可。
- 优点： 减少服务器的压力，将原本一台服务器索要承受的访问量分给多台，并提高项目的可用性，当一台服务器挂掉的时候不会导致项目瘫痪。
- 利用随机数从所有服务器中随机选取一台，可以用服务器数组下标获取。
public class RandomLoadBalance {
@Data
@AllArgsConstructor
@NoArgsConstructor
public static class Server {
private int serverId;
private String name;
}
public static Server selectServer(List serverList) {
Random selector = new Random();
int next = selector.nextInt(serverList.size());
return serverList.get(next);
}
public static void main(String[] args) {
List serverList = new ArrayList<>();
serverList.add(new Server(1, "服务器1"));
serverList.add(new Server(2, "服务器2"));
serverList.add(new Server(3, "服务器3"));
for (int i = 0; i < 10; i++) {
Server selectedServer = selectServer(serverList);
System.out.format("第%d次请求，选择服务器%sn", i + 1, selectedServer.toString());
}
}
}
执行结果
2.轮询（Round Robin、RR） 1.1.思路- 依次将用户的访问请求，按循环顺序分配到web服务节点上，从1开始到最后一台服务器节点结束，然后再开始新一轮的循环。这种算法简单，但是没有考虑到每台节点服务器的具体性能，请求分发往往不均衡。
已知服务器
| 服务器 | 权重 |
|---|---|
| s1 | 1 |
| s2 | 2 |
| s3 | 3 |
请求1 -> s1 请求2 -> s2 请求3 -> s3 请求4 -> s1 请求5 -> s2 请求6 -> s3
优点：
- 实现简单，无需记录各种服务的状态，是一种无状态的负载均衡策略。
缺点：
- 实现绝对公平，当各个服务器性能不一致的情况，无法根据服务器性能去分配，无法合理利用服务器资源。
- 通过synchronized加锁 及 下标自增的方式从节点集合中竞选节点
public class RoundRobin {
//当前下标
private static Integer index = 0;
//节点列表
private static List nodes = new ArrayList<>();
//模拟数据
static {
nodes.add("192.168.1.101");
nodes.add("192.168.1.103");
nodes.add("192.168.1.102");
System.out.println("普通轮询算法的所有节点：" + nodes);//打印所有节点
}
// 关键代码
public String selectNode() {
String ip = null;
synchronized (index) {
//如果当前下标 >= 节点数,将下标复位
if (index >= nodes.size()) {
index = 0;
}
//获取当前下标节点
ip = nodes.get(index);
//当前下标自增
index++;
}
return ip;
}
// 并发测试：两个线程循环获取节点
public static void main(String[] args) {
RoundRobin r = new RoundRobin();
new Thread(() -> {
for (int i = 1; i <= 5; i++) {
String serverIp = r.selectNode();
System.out.println(Thread.currentThread().getName() + "==第" + i + "次获取节点：" + serverIp);
}
}).start();
new Thread(() -> {
for (int i = 1; i <= 5; i++) {
String serverIp = r.selectNode();
System.out.println(Thread.currentThread().getName() + "==第" + i + "次获取节点：" + serverIp);
}
}).start();
}
}
执行结果
- 不同线程访问，结果依旧是按顺序循环分配节点
public class RoundRobin {
//计数器：每次轮询一个节点自增1
private static AtomicInteger NEXT_SERVER_COUNTER = new AtomicInteger(0);
@Data
@AllArgsConstructor
@NoArgsConstructor
public static class Server {
private int serverId;
private String name;
}
private static int select(int modulo) {
for (; ; ) {
int current = NEXT_SERVER_COUNTER.get();
//NEXT_SERVER_COUNTER + 1 % 节点总数
int next = (current + 1) % modulo;
//如果当前NEXT_SERVER_COUNTER为current,CAS更新为next
boolean compareAndSet = NEXT_SERVER_COUNTER.compareAndSet(current, next);
//CAS更新成功直接返回,否则自旋到当前线程CAS操作成功
if (compareAndSet) {
return next;
}
}
}
public static Server selectServer(List serverList) {
return serverList.get(select(serverList.size()));
}
public static void main(String[] args) {
List serverList = new ArrayList<>();
serverList.add(new Server(1, "服务器1"));
serverList.add(new Server(2, "服务器2"));
serverList.add(new Server(3, "服务器3"));
for (int i = 0; i < 10; i++) {
Server selectedServer = selectServer(serverList);
System.out.format("第%d次请求，选择服务器%sn", i + 1, selectedServer.toString());
}
}
}
执行结果
- 根据设定的权重值来分配访问请求，权重值越大的，被分到的请求数也就越多。一般根据每台节点服务器的具体性能来分配权重。
已知服务器
| 服务器 | 权重 |
|---|---|
| s1 | 1 |
| s2 | 2 |
| s3 | 3 |
- 可以根据权重我们创建数组{s1,s2,s2,s3,s3,s3}，然后再按照轮询的方式选择相应的服务器。
缺点：
- 请求被分配到3台服务器上机会不够平滑。前3次请求都不会落在s3上。
将需要轮询的所有节点按权重数循环生成一个List 集合，然后就跟普通轮询算法一样，来一个、分配一个、下标进1位。
如： 所有节点信息：{{"192.168.1.100",5},{"192.168.1.101",1},{"192.168.1.102",3}}
生成的List集合为：
{
"192.168.1.100",
"192.168.1.100",
"192.168.1.100",
"192.168.1.100",
"192.168.1.100",
"192.168.1.101",
"192.168.1.102",
"192.168.1.102",
"192.168.1.102"
}
public class WeightedRoundRobinSimple {
//当前下标
private static Integer index = 0;
//节点以及对应权值
private static Map mapNodes = new HashMap<>();
//节点的权值列表
private static List nodes = new ArrayList<>();
// 准备模拟数据
static {
mapNodes.put("192.168.1.101", 1);
mapNodes.put("192.168.1.102", 3);
mapNodes.put("192.168.1.103", 2);
// 关键代码：类似于二维数组 降维成 一维数组，然后使用普通轮询
for (Map.Entry entry : mapNodes.entrySet()) {
String key = entry.getKey();
for (int i = 0; i < entry.getValue(); i++) {
nodes.add(key);
}
}
System.out.println("简单版的加权轮询：" + JSON.toJSONString(nodes));//打印所有节点
}
public String selectNode() {
String ip = null;
synchronized (index) {
//如果当前下标 >= 节点数,将下标复位
if (index >= nodes.size()) {
index = 0;
}
//获取当前下标节点
ip = nodes.get(index);
//当前下标自增
index++;
}
return ip;
}
// 并发测试：两个线程循环获取节点
public static void main(String[] args) {
WeightedRoundRobinSimple r = new WeightedRoundRobinSimple();
new Thread(() -> {
for (int i = 1; i <= 6; i++) {
String serverIp = r.selectNode();
System.out.println(Thread.currentThread().getName() + "==第" + i + "次获取节点：" + serverIp);
}
}).start();
new Thread(() -> {
for (int i = 1; i <= 6; i++) {
String serverIp = r.selectNode();
System.out.println(Thread.currentThread().getName() + "==第" + i + "次获取节点：" + serverIp);
}
}).start();
}
}
执行结果：
- 2个线程循环调用，输出结果会出现交替分配到不同的IP，但最终的效果都是一个个按顺序分配，类似于普通轮询算法。
在实现1中可以很明显的看到，同权重的节点会被连续分配，也就是说同一个节点在短时间内收到不同的请求，过了这个连续点，就要等到下一轮才会被分配到，并没有做到均匀分配节点。
- 该实现将尽可能地均匀分配每个节点，节点分配不再是连续的，但最终的权重比和上一个方式一样，这种加权轮询又被称为平滑加权轮询。
关键参数
ip：负载IP weight：权重，只保存配置时的权重参数值，不做任何修改。 currentWeight：当前权重，比对该值大小获取节点，通过循环所有节点比对该值大小来分配权重最大的节点，初始值等于weight。 effectiveWeight 有效权重，在整个过程可能会变化，初始值等于weight，主要用于当节点出现分配失败时降低权重值，成功时提高权重值（但不能大于weight值），本案例为了简化算法，并未加入这功能，因此本案例中effectiveWeight始终等于weight。
3个权重参数的变化情况
仅仅针对本案例，因为本案例为了简化算法，并未加入[节点出现分配失败时降低权重值，成功时提高权重值（但不能大于weight值）的功能]，所以有效权重effectiveWeight 不会发生变化。 第一次加权轮询时：currentWeight = weight = effectiveWeight； 后面每次加权轮询时：currentWeight 的值都会不断变化，weight 和effectiveWeight 的值不变； 被分配的节点的currentWeight = currentWeight - 权重之和 所有节点的currentWeight = currentWeight + effectiveWeight
举个例子理解算法
假设三个瓶子A、B、C，分别装有1L、3L、2L水。 第一轮分配情况：B多，所以把B瓶子的3L水，分1L给A，分2L给C（按权重分），分完之后：A、B、C分别为：2L、0L、4L 第二轮分配情况：C多，所以把C瓶子的4L水，分1L给A，分3L给B（按权重分），分完之后：A、B、C分别为：3L、3L、0L 第三轮分配情况：A和B一样多，那么拿谁去分呢？拿谁其实都一样（算法中写了A大于B才选A，现在等于，所以不选A），所以把B瓶子的3L水， 分1L给A，分2L给C（按权重分），分完之后：A、B、C分别为：4L、0L、2L 然后不断的进行下去……
简化成数学逻辑（代码实现）的关键2步
被分配的节点的currentWeight = currentWeight - 权重之和 所有节点的currentWeight = currentWeight + effectiveWeight
public class WeightedRoundRobin {
//节点集合
private static List nodeList = new ArrayList<>();
// 权重之和
private static Integer totalWeight = 0;
// 准备模拟数据
static {
nodeList.add(new Node("192.168.1.101", 1));
nodeList.add(new Node("192.168.1.102", 3));
nodeList.add(new Node("192.168.1.103", 2));
//累加总权重
nodeList.forEach(node -> totalWeight += node.getEffectiveWeight());
}
public Node selectNode() {
if (nodeList == null || nodeList.size() <= 0) {
return null;
}
if (nodeList.size() == 1) {
return nodeList.get(0);
}
// 保存轮询选中的节点信息
Node selectWeightNode = null;
synchronized (nodeList) {
// 打印信息对象：避免并发时打印出来的信息太乱，不利于观看结果
StringBuilder sb = new StringBuilder();
sb.append(Thread.currentThread().getName()).append("==加权轮询--[当前权重]值的变化：").append(printCurrentWeight(nodeList));
// 选出当前权重最大的节点
Node maxWeightNode = null;
for (Node node : nodeList) {
if (maxWeightNode == null) {
maxWeightNode = node;
}
else {
//当前最大节点
maxWeightNode = maxWeightNode.compareTo(node) > 0 ? maxWeightNode : node;
}
}
// 必须new个新的节点实例来保存信息，否则引用指向同一个堆实例，后面的set操作将会修改节点信息
selectWeightNode = new Node(maxWeightNode.getIp(), maxWeightNode.getWeight(), maxWeightNode.getEffectiveWeight(), maxWeightNode.getCurrentWeight());
// 调整当前权重比：按权重（effectiveWeight）的比例进行调整，确保请求分发合理。
maxWeightNode.setCurrentWeight(maxWeightNode.getCurrentWeight() - totalWeight);
sb.append(" -> ").append(printCurrentWeight(nodeList));
nodeList.forEach(node -> node.setCurrentWeight(node.getCurrentWeight() + node.getEffectiveWeight()));
sb.append(" -> ").append(printCurrentWeight(nodeList));
System.out.println(sb); //打印权重变化过程
}
return selectWeightNode;
}
// 格式化打印信息
private String printCurrentWeight(List nodes) {
StringBuilder sb = new StringBuilder("[");
nodes.forEach(node -> sb.append(node.getCurrentWeight()).append(","));
return sb.substring(0, sb.length() - 1) + "]";
}
@Data
@ToString
public static class Node implements Comparable {
//权重，保存配置的权重
private final Integer weight;
//负载IP
private String ip;
//有效权重，轮询的过程权重可能变化
private Integer effectiveWeight;
//当前权重，比对该值大小获取节点
//第一次加权轮询时：currentWeight = weight = effectiveWeight
//后面每次加权轮询时：currentWeight 的值都会不断变化，其他权重不变
private Integer currentWeight;
public Node(String ip, Integer weight) {
this.ip = ip;
this.weight = weight;
this.effectiveWeight = weight;
this.currentWeight = weight;
}
public Node(String ip, Integer weight, Integer effectiveWeight, Integer currentWeight) {
this.ip = ip;
this.weight = weight;
this.effectiveWeight = effectiveWeight;
this.currentWeight = currentWeight;
}
@Override
public int compareTo(Node node) {
return this.currentWeight > node.currentWeight ? 1 : (this.currentWeight.equals(node.currentWeight) ? 0 : -1);
}
}
// 并发测试：两个线程循环获取节点
public static void main(String[] args) {
new Thread(() -> {
WeightedRoundRobin w = new WeightedRoundRobin();
for (int i = 1; i <= totalWeight; i++) {
Node node = w.selectNode();
System.out.println(Thread.currentThread().getName() + "==第" + i + "次轮询选中[当前权重最大]的节点：" + node + "n");
}
}).start();
new Thread(() -> {
WeightedRoundRobin w = new WeightedRoundRobin();
for (int i = 1; i <= totalWeight; i++) {
Node node = w.selectNode();
System.out.println(Thread.currentThread().getName() + "==第" + i + "次轮询选中[当前权重最大]的节点：" + node + "n");
}
}).start();
}
}
执行结果
Thread-0==加权轮询--[当前权重]值的变化：[1,3,2] -> [1,-3,2] -> [2,0,4] Thread-0==第1次轮询选中[当前权重最大]的节点：Node(weight=3, ip=192.168.1.102, effectiveWeight=3, currentWeight=3) Thread-1==加权轮询--[当前权重]值的变化：[2,0,4] -> [2,0,-2] -> [3,3,0] Thread-1==第1次轮询选中[当前权重最大]的节点：Node(weight=2, ip=192.168.1.103, effectiveWeight=2, currentWeight=4) Thread-0==加权轮询--[当前权重]值的变化：[3,3,0] -> [3,-3,0] -> [4,0,2] Thread-0==第2次轮询选中[当前权重最大]的节点：Node(weight=3, ip=192.168.1.102, effectiveWeight=3, currentWeight=3) Thread-1==加权轮询--[当前权重]值的变化：[4,0,2] -> [-2,0,2] -> [-1,3,4] Thread-1==第2次轮询选中[当前权重最大]的节点：Node(weight=1, ip=192.168.1.101, effectiveWeight=1, currentWeight=4) Thread-0==加权轮询--[当前权重]值的变化：[-1,3,4] -> [-1,3,-2] -> [0,6,0] Thread-0==第3次轮询选中[当前权重最大]的节点：Node(weight=2, ip=192.168.1.103, effectiveWeight=2, currentWeight=4) Thread-1==加权轮询--[当前权重]值的变化：[0,6,0] -> [0,0,0] -> [1,3,2] Thread-1==第3次轮询选中[当前权重最大]的节点：Node(weight=3, ip=192.168.1.102, effectiveWeight=3, currentWeight=6) Thread-0==加权轮询--[当前权重]值的变化：[1,3,2] -> [1,-3,2] -> [2,0,4] Thread-0==第4次轮询选中[当前权重最大]的节点：Node(weight=3, ip=192.168.1.102, effectiveWeight=3, currentWeight=3) Thread-1==加权轮询--[当前权重]值的变化：[2,0,4] -> [2,0,-2] -> [3,3,0] Thread-1==第4次轮询选中[当前权重最大]的节点：Node(weight=2, ip=192.168.1.103, effectiveWeight=2, currentWeight=4) Thread-0==加权轮询--[当前权重]值的变化：[3,3,0] -> [3,-3,0] -> [4,0,2] Thread-0==第5次轮询选中[当前权重最大]的节点：Node(weight=3, ip=192.168.1.102, effectiveWeight=3, currentWeight=3) Thread-1==加权轮询--[当前权重]值的变化：[4,0,2] -> [-2,0,2] -> [-1,3,4] Thread-1==第5次轮询选中[当前权重最大]的节点：Node(weight=1, ip=192.168.1.101, effectiveWeight=1, currentWeight=4) Thread-0==加权轮询--[当前权重]值的变化：[-1,3,4] -> [-1,3,-2] -> [0,6,0] Thread-0==第6次轮询选中[当前权重最大]的节点：Node(weight=2, ip=192.168.1.103, effectiveWeight=2, currentWeight=4) Thread-1==加权轮询--[当前权重]值的变化：[0,6,0] -> [0,0,0] -> [1,3,2] Thread-1==第6次轮询选中[当前权重最大]的节点：Node(weight=3, ip=192.168.1.102, effectiveWeight=3, currentWeight=6)
为了方便分析，简化两线程执行后的结果
Thread-0==[当前权重]值的变化：[1,3,2] -> [1,-3,2] -> [2,0,4] Thread-1==[当前权重]值的变化：[2,0,4] -> [2,0,-2] -> [3,3,0] Thread-0==[当前权重]值的变化：[3,3,0] -> [3,-3,0] -> [4,0,2] Thread-1==[当前权重]值的变化：[4,0,2] -> [-2,0,2] -> [-1,3,4] Thread-0==[当前权重]值的变化：[-1,3,4] -> [-1,3,-2] -> [0,6,0] Thread-1==[当前权重]值的变化：[0,6,0] -> [0,0,0] -> [1,3,2] Thread-0==[当前权重]值的变化：[1,3,2] -> [1,-3,2] -> [2,0,4] Thread-1==[当前权重]值的变化：[2,0,4] -> [2,0,-2] -> [3,3,0] Thread-0==[当前权重]值的变化：[3,3,0] -> [3,-3,0] -> [4,0,2] Thread-1==[当前权重]值的变化：[4,0,2] -> [-2,0,2] -> [-1,3,4] Thread-0==[当前权重]值的变化：[-1,3,4] -> [-1,3,-2] -> [0,6,0] Thread-1==[当前权重]值的变化：[0,6,0] -> [0,0,0] -> [1,3,2]
- 因为整个过程只有当前权重发生变化，所以分析清楚它就明白了整个过程。
结论：
-
分配完成后当前权重发生变化，但权重之和还是等于最初值；
-
每6轮（1+3+2权重）就出现权重全部为0，所以会出现重新循环，6正好等于权重之和，权重比等于1/6 : 3/6 : 2/6
-
a=1，b=3，c=2 ，那么权重变化的6次（a+b+c)中，分配情况为：b c b a c b，很明显，每个节点均匀按权重分配，节点分配不再是连续的。
-
该算法在权重比相差很大时，比如：A=1，B=5，那这个算法的结果就跟思路1没啥区别了，分配结果就变成了：{A,B,B,B,B,B}，既然没区别，那根据算法复杂情况，那肯定方式1更好了，所以思路1和思路2可以互补，可以根据权重比选择不同的算法。
留下悬念
- 节点出现分配失败时降低有效权重值，成功时提高有效权重值（但不能大于weight值）的功能。理解了思路2，后面再加这块功能进去就很好理解了；
解决办法： Nginx了一种平滑的加权轮询算法，可以将请求平滑（均匀）的分配到各个节点上。
思路：以当前节点权重作为被选中的概率
public void incrCurrentWeight() {
this.currentWeight += weight;
}
为了避免权重大的被连续选中，采用 当前权重 = 当前权重 - 总权重方式，使节点再次被选中的时让其的当前权重变小。
1-6 =-5 2-6 =-4 3-6 =-3
可得权重越大下次当前权重变成最大的可能性也越大
public void selected(int total) {
this.currentWeight -= total;
}
完整代码
public class WeightRoundRobin {
@Data
public static class Server {
private int serverId;
private String name;
private int weight;//节点权重
private int currentWeight;//节点当前权重
public Server(int serverId, String name, int weight) {
this.serverId = serverId;
this.name = name;
this.weight = weight;
}
public void selected(int total) {
///为了避免权重大的节点被连续选中，所以再被选中的时让其的当前权重变小。。采用 `当前权重 = 当前权重 - 总权重`方式
// 1-6 =-5
// 2-6 =-4
// 3-6 =-3
this.currentWeight -= total;
}
public void incrCurrentWeight() {
//以当前节点权重作为被选中的概率
this.currentWeight += weight;
}
}
public static Server selectServer(List serverList) {
//前面节点权重累加总和
int total = 0;
//选举的最大权重节点
Server selectedServer = null;
//被选举的的权重值
int maxWeight = 0;
for (Server server : serverList) {
//累加当前节点权重
total += server.getWeight();
//初始当前节点权重 currentWeight = currentWeight+weight;
server.incrCurrentWeight();
//选取当前权重最大的一个节点
if (selectedServer == null || maxWeight < server.getCurrentWeight()) {
selectedServer = server;
maxWeight = server.getCurrentWeight();
}
}
//没有选举到节点,随机选举
if (selectedServer == null) {
Random random = new Random();
int next = random.nextInt(serverList.size());
return serverList.get(next);
}
//为了避免权重大的节点被连续选中，所以再被选中的时让其的当前权重变小。采用 `当前权重 = 当前权重 - 前面节点权重累加总和`方式
selectedServer.selected(total);
return selectedServer;
}
public static void main(String[] args) {
List serverList = new ArrayList<>();
serverList.add(new Server(1, "服务器1", 1));
serverList.add(new Server(2, "服务器2", 3));
serverList.add(new Server(3, "服务器3", 10));
for (int i = 0; i < 10; i++) {
Server server = selectServer(serverList);
System.out.format("第%d次请求，选择服务器%sn", i + 1, server.toString());
}
}
执行结果
- 利用区间的思想，通过一个小于在此区间范围内的一个随机数，选中对应的区间（服务器），区间越大被选中的概率就越大。
| 服务器 | 权重 |
|---|---|
| s1 | 1 |
| s2 | 2 |
| s3 | 3 |
s1：[0,1] s2：(1,3] s3 （3,6]4.2.实现方式
public class WeightRandom {
@Data
@AllArgsConstructor
@NoArgsConstructor
public static class Server {
private int serverId;
private String name;
private int weight;
}
private static Server selectServer(List serverList) {
//总权重
int sumWeight = 0;
//选中的服务器
Server selectedServer = null;
//统计总权重
for (Server server : serverList) {
sumWeight += server.getWeight();
}
//根据总权重大小生成指定范围随机数
int nextRange = new Random().nextInt(sumWeight);
//当前节点的最小区间
int sum = 0;
for (Server server : serverList) {
//当前随机数 >= 前面节点总区间(最小区间) && 当前随机数< 当前节点+前面节点总区间(最大区间)
//即当前随机数位于当前节点区间内，则选中当前节点
if (nextRange >= sum && nextRange < server.getWeight() + sum) {
selectedServer = server;
break;
}
//如果当前随机数不在当前节点区间内,则累加节点权重作为最小区间
sum += server.getWeight();
}
return selectedServer;
}
public static void main(String[] args) {
List serverList = new ArrayList<>();
serverList.add(new Server(1, "服务器1", 1));
serverList.add(new Server(2, "服务器2", 5));
serverList.add(new Server(3, "服务器3", 10));
for (int i = 0; i < 10; i++) {
Server selectedServer = selectServer(serverList);
System.out.format("第%d次请求，选择服务器%sn", i + 1, selectedServer.toString());
}
}
}
执行结果
- 根据每个每个请求ip（也可以是某个标识）ip.hash() % server.size()
public class IpHash {
@Data
@AllArgsConstructor
@NoArgsConstructor
public static class Server {
private int serverId;
private String name;
}
public static Server selectServer(List serverList, String ip) {
int ipHash = ip.hashCode();
return serverList.get(ipHash % serverList.size());
}
public static void main(String[] args) {
List serverList = new ArrayList<>();
serverList.add(new Server(1, "服务器1"));
serverList.add(new Server(2, "服务器2"));
serverList.add(new Server(3, "服务器3"));
List ips = Arrays.asList("192.168.9.5", "192.168.9.2", "192.168.9.3");
for (int i = 0; i < 10; i++) {
for (String ip : ips) {
Server selectedServer = selectServer(serverList, ip);
System.out.format("请求ip:%s，选择服务器%sn", ip, selectedServer.toString());
}
}
}
}
执行结果
- 结果：同一ip肯定会命中同一台机器。
定义 Node类，存储一些节点基本的信息，一般来说这个类会抽象处理：
@NoArgsConstructor
@Getter
@Setter
@ToString
@EqualsAndHashCode(of = "url")
public class Node {
//节点路径
private String url;
//权重
private int weight = 1;
//当前权重
private int currentWeight = 0;
public Node(String url) {
this.url = url;
}
public Node(String url, int weight) {
this.url = url;
this.weight = weight;
}
}
负载抽象类
public abstract class AbstractLoadBalance {
//存储结构
protected final Multiset results = HashMultiset.create();
//存储节点集合
protected List nodes;
public AbstractLoadBalance(List nodes) {
this.nodes = nodes;
}
public Node selectHost() {
List list = getNodes();
if (CollectionUtils.isEmpty(list)) {
return null;
}
if (list.size() == 1) {
return list.get(0);
}
return doSelect();
}
public Node selectHost(Object client) {
List list = getNodes();
if (CollectionUtils.isEmpty(list)) {
return null;
}
if (list.size() == 1) {
return list.get(0);
}
return doSelect(client);
}
protected Node doSelect() {
return null;
}
protected Node doSelect(Object client) {
return null;
}
protected boolean addNode(Node node) {
if (getNodes() != null) {
return nodes.add(node);
}
return false;
}
protected boolean removeNode(Node node) {
if (getNodes() != null) {
return nodes.remove(node);
}
return false;
}
protected List getNodes() {
return nodes;
}
public void result(int loop) {
results.clear();
if (loop < 1) {
throw new IllegalArgumentException();
}
IntStream.range(0, loop).forEach(i -> results.add(selectHost()));
Set> entrySet = results.entrySet();
entrySet.stream().sorted(Comparator.comparingInt(Multiset.Entry::getCount)).forEach(System.out::println);
}
}
2.负载算法
1.完全随机
- 随机算法是用得比较多，也是比较简单的一种算法，属于任务数量的绝对平分。在调用次数比较多的时候会相对平均分布到每个节点上。
具体实现
public class SimpleRandomLoadBalance extends AbstractLoadBalance {
public SimpleRandomLoadBalance(List nodes) {
super(nodes);
}
@Override
protected Node doSelect() {
return getNodes().get(new Random().nextInt(getNodes().size()));
}
@Override
public List getNodes() {
return nodes;
}
}
测试方法
@Test
public void testSimpleRandomLoadBalance(){
List nodes = Lists.newArrayList(
new Node("176.170.209.1"),
new Node("176.170.209.2"),
new Node("176.170.209.3"),
new Node("176.170.209.4"),
new Node("176.170.209.5"),
new Node("176.170.209.6"),
new Node("176.170.209.7"),
new Node("176.170.209.8"),
new Node("176.170.209.9"),
new Node("176.170.209.10"));
AbstractLoadBalance randomLoadBalance = new SimpleRandomLoadBalance(nodes);
randomLoadBalance.result(20000);
//结论：样本数量越大，越平均。
}
执行结果
Node(url=176.170.209.8, weight=1, currentWeight=0) x 1940 Node(url=176.170.209.3, weight=1, currentWeight=0) x 1948 Node(url=176.170.209.1, weight=1, currentWeight=0) x 1952 Node(url=176.170.209.9, weight=1, currentWeight=0) x 1966 Node(url=176.170.209.4, weight=1, currentWeight=0) x 1969 Node(url=176.170.209.6, weight=1, currentWeight=0) x 2017 Node(url=176.170.209.2, weight=1, currentWeight=0) x 2038 Node(url=176.170.209.10, weight=1, currentWeight=0) x 2054 Node(url=176.170.209.7, weight=1, currentWeight=0) x 2056 Node(url=176.170.209.5, weight=1, currentWeight=0) x 2060
- 数量越大，越平均
实际线上可能节点的性能各不相同，为了让性能更好的节点分配更多的流量，可以为每个节点设置一个权重，按照一定的比例进行任务的均分。
- 权重一般是一个整型，最简单的思路就是机器的权重是多少，那么在集合列表中创建多少个节点
具体实现
public class CopyWeightRandomLoadBalance extends SimpleRandomLoadBalance {
private List weightNodes = new ArrayList<>();
public CopyWeightRandomLoadBalance(List nodes) {
super(nodes);
if (!CollectionUtils.isEmpty(nodes)) {
nodes.forEach(node -> {
if (node.getWeight() < 2) {
weightNodes.add(node);
return;
}
IntStream.range(0, node.getWeight()).forEach(i -> weightNodes.add(node));
});
}
}
@Override
public final List getNodes() {
return weightNodes;
}
}
测试方法
@Test
public void testCopyWeightRandomLoadBalance(){
List nodes = Lists.newArrayList(
new Node("176.170.209.1",1),
new Node("176.170.209.2",9),
new Node("176.170.209.3",1),
new Node("176.170.209.4",9),
new Node("176.170.209.5",4),
new Node("176.170.209.6",6),
new Node("176.170.209.7",1),
new Node("176.170.209.8",9),
new Node("176.170.209.9",1),
new Node("176.170.209.10",9));
AbstractLoadBalance simpleWeightRandomLoadBalance1 = new CopyWeightRandomLoadBalance(nodes);
simpleWeightRandomLoadBalance1.result(20000);
//结论：样本数量越大，越平均。
//可以发现是按照权重比例进行分配。
//但是这种算法需要对调用信息进行复制，当数量较大时对内存的消耗相对是比较大的，所以一般会使用另外一种方式实现。
}
执行结果
Node(url=176.170.209.1, weight=1, currentWeight=0) x 395 Node(url=176.170.209.9, weight=1, currentWeight=0) x 396 Node(url=176.170.209.7, weight=1, currentWeight=0) x 401 Node(url=176.170.209.3, weight=1, currentWeight=0) x 430 Node(url=176.170.209.5, weight=4, currentWeight=0) x 1587 Node(url=176.170.209.6, weight=6, currentWeight=0) x 2353 Node(url=176.170.209.10, weight=9, currentWeight=0) x 3528 Node(url=176.170.209.8, weight=9, currentWeight=0) x 3611 Node(url=176.170.209.2, weight=9, currentWeight=0) x 3640 Node(url=176.170.209.4, weight=9, currentWeight=0) x 36592.2.权重区间
上面加权随机-节点复制 方式是按照权重比例进行对象创建的。当节点数量较大时对内存的消耗相对是比较大的，所以一般会使用权重区间实现
还是以这个权重为例： Listnodes = Lists.newArrayList( new Node("176.170.209.1",1), new Node("176.170.209.2",9), new Node("176.170.209.3",1), new Node("176.170.209.4",9), new Node("176.170.209.5",4), new Node("176.170.209.6",6), new Node("176.170.209.7",1), new Node("176.170.209.8",9), new Node("176.170.209.9",1), new Node("176.170.209.10",9)) 首先计算出总的权重，这里是 50，生成 [0,50) 的随机数 n；根据这个权重为每一个 Node 分配一个区间： 0，1，10，11，20，24，30，31，40，41，50 这个区间包左不包右，比如生成的随机数 0<= n <1，那么就是"176.170.209.1"这个机器，以此类推。
具体实现
public class SectionWeightRandomLoadBalance extends SimpleRandomLoadBalance {
private boolean averageWeight = true;
//总权重
private int totalWeight;
public SectionWeightRandomLoadBalance(List nodes) {
super(nodes);
for (int i = 0; i < nodes.size(); i++) {
Node node = nodes.get(i);
if (averageWeight && i > 0 && node.getWeight() != nodes.get(i - 1).getWeight()) {
averageWeight = false;
}
totalWeight += node.getWeight();
}
}
@Override
protected Node doSelect() {
if (averageWeight || totalWeight < 1) {
return super.doSelect();
}
int index = new Random().nextInt(totalWeight);
for (Node node : nodes) {
if (index < node.getWeight()) {
return node;
}
index -= node.getWeight();
}
return super.doSelect();
}
}
测试方法
@Test
public void testWeightRandomLoadBalance(){
List nodes = Lists.newArrayList(
new Node("176.170.209.1",1),
new Node("176.170.209.2",9),
new Node("176.170.209.3",1),
new Node("176.170.209.4",9),
new Node("176.170.209.5",4),
new Node("176.170.209.6",6),
new Node("176.170.209.7",1),
new Node("176.170.209.8",9),
new Node("176.170.209.9",1),
new Node("176.170.209.10",9));
AbstractLoadBalance simpleWeightRandomLoadBalance1 = new SectionWeightRandomLoadBalance(nodes);
simpleWeightRandomLoadBalance1.result(20000);
}
执行结果
Node(url=176.170.209.3, weight=1, currentWeight=0) x 381 Node(url=176.170.209.9, weight=1, currentWeight=0) x 382 Node(url=176.170.209.1, weight=1, currentWeight=0) x 393 Node(url=176.170.209.7, weight=1, currentWeight=0) x 411 Node(url=176.170.209.5, weight=4, currentWeight=0) x 1624 Node(url=176.170.209.6, weight=6, currentWeight=0) x 2376 Node(url=176.170.209.10, weight=9, currentWeight=0) x 3592 Node(url=176.170.209.8, weight=9, currentWeight=0) x 3599 Node(url=176.170.209.4, weight=9, currentWeight=0) x 3600 Node(url=176.170.209.2, weight=9, currentWeight=0) x 36423.简单轮询
- 轮询算法也很好理解，就是轮流执行每台服务器，所以有一个请求序号的概念。
具体实现
public class SimpleRoundRobinLoadBalance extends AbstractLoadBalance {
//偏移量
protected AtomicInteger offset = new AtomicInteger(-1);
public SimpleRoundRobinLoadBalance(List nodes) {
super(nodes);
}
@Override
protected Node doSelect() {
return getNodes().get(offset.addAndGet(1) % getNodes().size());
}
}
测试方法
@Test
public void testSimpleRoundRobinLoadBalance(){
List nodes = Lists.newArrayList(
new Node("176.170.209.1"),
new Node("176.170.209.2"),
new Node("176.170.209.3"),
new Node("176.170.209.4"),
new Node("176.170.209.5"),
new Node("176.170.209.6"),
new Node("176.170.209.7"),
new Node("176.170.209.8"),
new Node("176.170.209.9"),
new Node("176.170.209.10"));
AbstractLoadBalance roundRobinLoadBalance = new SimpleRoundRobinLoadBalance(nodes);
IntStream.range(0,22).parallel().forEach(i-> System.out.println(roundRobinLoadBalance.selectHost()));
}
执行结果
Node(url=176.170.209.10, weight=1, currentWeight=0) Node(url=176.170.209.7, weight=1, currentWeight=0) Node(url=176.170.209.2, weight=1, currentWeight=0) Node(url=176.170.209.9, weight=1, currentWeight=0) Node(url=176.170.209.6, weight=1, currentWeight=0) Node(url=176.170.209.6, weight=1, currentWeight=0) Node(url=176.170.209.3, weight=1, currentWeight=0) Node(url=176.170.209.1, weight=1, currentWeight=0) Node(url=176.170.209.2, weight=1, currentWeight=0) Node(url=176.170.209.1, weight=1, currentWeight=0) Node(url=176.170.209.4, weight=1, currentWeight=0) Node(url=176.170.209.5, weight=1, currentWeight=0) Node(url=176.170.209.8, weight=1, currentWeight=0) Node(url=176.170.209.2, weight=1, currentWeight=0) Node(url=176.170.209.1, weight=1, currentWeight=0) Node(url=176.170.209.10, weight=1, currentWeight=0) Node(url=176.170.209.9, weight=1, currentWeight=0) Node(url=176.170.209.8, weight=1, currentWeight=0) Node(url=176.170.209.7, weight=1, currentWeight=0) Node(url=176.170.209.5, weight=1, currentWeight=0) Node(url=176.170.209.4, weight=1, currentWeight=0) Node(url=176.170.209.3, weight=1, currentWeight=0)4.加权轮询 4.1.节点复制
- 同上文介绍的加权随机-节点复制的实现思路
具体实现
public class CopyWeightRoundRobinLoadBalance extends SimpleRoundRobinLoadBalance {
private List weightNodes = new ArrayList<>();
public CopyWeightRoundRobinLoadBalance(List nodes) {
super(nodes);
if (!CollectionUtils.isEmpty(nodes)) {
nodes.forEach(invoker -> {
if (invoker.getWeight() < 2) {
weightNodes.add(invoker);
return;
}
IntStream.range(0, invoker.getWeight()).forEach(i -> weightNodes.add(invoker));
});
}
}
@Override
public final List getNodes() {
return weightNodes;
}
}
测试方法
@Test
public void testCopyWeightRoundRobinLoadBalance(){
List nodes = Lists.newArrayList(
new Node("176.170.209.1",1),
new Node("176.170.209.2",9),
new Node("176.170.209.3",1),
new Node("176.170.209.4",9),
new Node("176.170.209.5",4),
new Node("176.170.209.6",6),
new Node("176.170.209.7",1),
new Node("176.170.209.8",9),
new Node("176.170.209.9",1),
new Node("176.170.209.10",9));
AbstractLoadBalance copyWeightRoundRobinLoadBalance = new CopyWeightRoundRobinLoadBalance(nodes);
IntStream.range(0,50).forEach(i-> System.out.println(copyWeightRoundRobinLoadBalance.selectHost()));
// copyWeightRoundRobinLoadBalance.result(20000);
}
执行结果
Node(url=176.170.209.1, weight=1, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.3, weight=1, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.7, weight=1, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.9, weight=1, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0)4.2.权重区间
还有一种实现方式同加权随机-权重区间通过权重区间进行轮询。
public class SectionWeightRoundRobinLoadBalance extends SimpleRoundRobinLoadBalance {
private boolean averageWeight = true;
//总权重
private int totalWeight;
public SectionWeightRoundRobinLoadBalance(List nodes) {
super(nodes);
for (int i = 0; i < nodes.size(); i++) {
Node node = nodes.get(i);
if (averageWeight && i > 0 && node.getWeight() != nodes.get(i - 1).getWeight()) {
averageWeight = false;
}
totalWeight += node.getWeight();
}
}
@Override
protected Node doSelect() {
if (averageWeight || totalWeight < 1) {
return super.doSelect();
}
int index = offset.addAndGet(1) % totalWeight;
for (Node node : nodes) {
if (index < node.getWeight()) {
return node;
}
index -= node.getWeight();
}
return super.doSelect();
}
}
测试方法
@Test
public void testSectionWeightRoundRobinLoadBalance(){
List nodes = Lists.newArrayList(
new Node("176.170.209.1",1),
new Node("176.170.209.2",9),
new Node("176.170.209.3",1),
new Node("176.170.209.4",9),
new Node("176.170.209.5",4),
new Node("176.170.209.6",6),
new Node("176.170.209.7",1),
new Node("176.170.209.8",9),
new Node("176.170.209.9",1),
new Node("176.170.209.10",9));
AbstractLoadBalance sectionWeightRoundRobinLoadBalance = new SectionWeightRoundRobinLoadBalance(nodes);
IntStream.range(0,50).forEach(i-> System.out.println(sectionWeightRoundRobinLoadBalance.selectHost()));
}
执行结果
Node(url=176.170.209.1, weight=1, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.2, weight=9, currentWeight=0) Node(url=176.170.209.3, weight=1, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.4, weight=9, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.5, weight=4, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.6, weight=6, currentWeight=0) Node(url=176.170.209.7, weight=1, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.8, weight=9, currentWeight=0) Node(url=176.170.209.9, weight=1, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0) Node(url=176.170.209.10, weight=9, currentWeight=0)4.3.平滑加权轮询
上面2种轮询方式都会造成某台权重较高的节点在短时间内负载较高，其实轮询我们希望的是，比如 A(1),B(2),C(3) 三台节点我们希望的是每 6 次调用，有 1 次是 A，2 次是 B，3 次是 C 即可。当然也可以进行改动，比如复制法可以将复制后的机器列表打乱。
- Nginx有一种平滑加权的轮询算法。在上面的其他权重算法中，每台机器会有一个权重 weight 属性，这个属性是配置好之后就不变的，在平滑加权轮询中每台机器还有一个当前权重的属性 currentWeight，这个属性是会变化的。
- 比如 A(1),B(2),C(3) 三台机节点，它们的 currentWeight 初始值都是 0，发生调用的时候，就会每台节点的 currentWeight += weight，然后选择所有节点中最大currentWeight的节点（如果出现相同，则按照顺序选择第一个），随后这台节点的 currentWeight - 总weight权重之和 totalWeight 后返回。
| 调用序号 | 选择前当前权重 | Max（currentWeight） | 选择机器 | 选择后当前权重 |
|---|---|---|---|---|
| 1 | 1，2，3 | 3 | C | 1，2，-3 |
| 2 | 2，4，0 | 4 | B | 2，-2，0 |
| 3 | 3，0，3 | 3 | A | -3，0，3 |
| 4 | -2，2，6 | 6 | C | -2，2，0 |
| 5 | -1，4，3 | 4 | B | -1，-2，3 |
| 6 | 0，0，6 | 6 | C | 0，0，0 |
- 可以看到经过 6 次调用，每台机器被调用的次数与权重的占比是一致的。
- 这个算法中 currentWeight 总和是不变的，因为被选择的节点的currentWeight - totalWeight后每个节点的 currentWeight 又会分别加上自身的 weight，即 weight 越大的机器被选择的次数就会越多。这个算法的数学证明可以参见链接
public class SmoothWeightRoundRobinLoadBalance extends SimpleRoundRobinLoadBalance {
//加锁
private final Object lock = new Object();
//是否为平均权值
private boolean averageWeight = true;
//总权值
private int totalWeight;
public SmoothWeightRoundRobinLoadBalance(List nodes) {
super(nodes);
for (int i = 0; i < nodes.size(); i++) {
Node node = nodes.get(i);
//当前节点权值 不等于上一节点权值
if (averageWeight && i > 0 && node.getWeight() != nodes.get(i - 1).getWeight()) {
averageWeight = false;
}
//总权值
totalWeight += node.getWeight();
}
}
@Override
protected Node doSelect() {
//只有一个节点时
if (averageWeight || totalWeight < 1) {
return super.doSelect();
}
//加锁处理节点选举
synchronized (lock) {
//选举最大节点
Node doNode = selectNode(nodes);
//最大节点返回前的预处理
before(doNode);
return doNode;
}
}
private Node selectNode(List nodes) {
//初始化最大节点为首节点
Node maxCurrentNode = nodes.get(0);
for (Node node : nodes) {
//设置当前节点权重值为 初始权值+当前权值
node.setCurrentWeight(node.getWeight() + node.getCurrentWeight());
//如果最大节点当前权值 < 当前节点当前权值,将当前节点更新为最大节点
if (maxCurrentNode.getCurrentWeight() < node.getCurrentWeight()) {
maxCurrentNode = node;
}
}
return maxCurrentNode;
}
private void before(Node doNode) {
//更新节点的当前权值为 当前权值 - 总权值
doNode.setCurrentWeight(doNode.getCurrentWeight() - totalWeight);
}
}
测试方法
@Test
public void testSmoothWeightRoundRobinLoadBalance(){
List nodes = Lists.newArrayList(
new Node("A",1),
new Node("B",2),
new Node("C",3));
AbstractLoadBalance smoothWeightRoundRobinLoadBalance = new SmoothWeightRoundRobinLoadBalance(nodes);
IntStream.range(0,6).forEach(i-> System.out.println(smoothWeightRoundRobinLoadBalance.selectHost()));
}
执行结果
Node(url=C, weight=3, currentWeight=-3) Node(url=B, weight=2, currentWeight=-2) Node(url=A, weight=1, currentWeight=-3) Node(url=C, weight=3, currentWeight=0) Node(url=B, weight=2, currentWeight=-2) Node(url=C, weight=3, currentWeight=0)5.哈希
哈希算法在分布式中的应用场景是很多的，如分布式的数据存储负载均衡等，如 Redis Cluster 中的Hash Slot算法。在负载均衡中就是根据一些请求信息进行哈希运算，将相同的哈希值分配到同一台机器上。如源地址 Hash、SessionId Hash，用户信息 Hash 等，也能顺带解决了 分布式 Session 的问题。
一个最简单的想法是直接用哈希来计算， 对机器数取模。在请求信息足够分散的情况下，是可以满足均衡性的，但一旦有机器加入或者宕机时，所有的原有机器都会受到影响。无法保证稳定性。
- 这时候就有了 *一致性哈希算法。一致性哈希算法会将哈希值空间组织成一个虚拟的圆环，即哈希环，普通哈希算法仅仅只针对请求信息进行哈希运算，但是一致性哈希会对服务器也进行哈希运算，从而将两者的哈希值映射在一个圆环上，即哈希环：
当请求哈希后落在 Node1 和 Node2 之间，就会根据顺时针选择到 Node2机器上。这样保证了稳定性，机器的增加或者退出不会影响所有的机器，但是还是会存在一个问题，假如Node3机器宕机，那么 Node1 到 Node4 的请求都会落在 Node1 机器上，这样 Node1 机器的压力就会变大。
- 又有了虚拟节点，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，通过这种方式将机器节点分散开来，通过虚拟节点均衡各个机器的请求量。
@NoArgsConstructor(access = AccessLevel.PRIVATE)
public class HashUtils {
public static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++) {
hash = (hash ^ str.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
}
一致性哈希算法实现，这里是不关心权重的：
public class ConsistentHashLoadBalance extends AbstractLoadBalance {
private static final int VIRTUAL_NODE_NUM = 1000;
private SortedMap virtualNodesMap = new TreeMap<>();
public ConsistentHashLoadBalance(List nodes) {
super(nodes);
putVirtualNodes(nodes);
}
private void putVirtualNodes(List nodes) {
for (Node node : nodes) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
int hash = HashUtils.getHash(node.getUrl() + "-" + i);
virtualNodesMap.put(hash, node);
}
}
}
public Node getNode(Object client) {
if (client == null) {
return null;
}
//获取大于等于 hash 的第一个 Node
SortedMap subMap = virtualNodesMap.tailMap(HashUtils.getHash(client.toString()));
if (subMap.isEmpty()) {
// hash值在最尾部，映射到第一个Node上
return virtualNodesMap.get(virtualNodesMap.firstKey());
}
return subMap.get(subMap.firstKey());
}
@Override
public void result(int loop) {
results.clear();
if (loop < 1) {
throw new IllegalArgumentException();
}
IntStream.range(0, loop).forEach(i -> results.add(selectHost("test-client-" + i)));
Set> entrySet = results.entrySet();
entrySet.stream().sorted(Comparator.comparingInt(Multiset.Entry::getCount)).forEach(System.out::println);
}
@Override
protected boolean addNode(Node node) {
if (super.addNode(node)) {
List nodes = getNodes();
virtualNodesMap.clear();
putVirtualNodes(nodes);
return true;
}
return false;
}
@Override
protected boolean removeNode(Node node) {
if (super.removeNode(node)) {
List nodes = getNodes();
virtualNodesMap.clear();
putVirtualNodes(nodes);
return true;
}
return false;
}
@Override
protected Node doSelect(Object client) {
return getNode(client);
}
}
测试方法
@Test
public void testConsistentHashLoadBalance(){
List nodes = Lists.newArrayList(
new Node("176.170.209.1",1),
new Node("176.170.209.2",9),
new Node("176.170.209.3",1),
new Node("176.170.209.4",9),
new Node("176.170.209.5",4),
new Node("176.170.209.6",6),
new Node("176.170.209.7",1),
new Node("176.170.209.8",9),
new Node("176.170.209.9",1),
new Node("176.1709.10",9));
AbstractLoadBalance consistentHashLoadBalance = new ConsistentHashLoadBalance(nodes);
consistentHashLoadBalance.result(1000000);
Node changeNode = new Node("176.1709.11", 1);
System.out.println("add......");
consistentHashLoadBalance.addNode(changeNode);
consistentHashLoadBalance.result(1000000);
System.out.println("remove.....");
consistentHashLoadBalance.removeNode(changeNode);
consistentHashLoadBalance.result(1000000);
}
执行结果
Node(url=176.170.209.8, weight=9, currentWeight=0) x 93728 Node(url=176.1709.10, weight=9, currentWeight=0) x 95566 Node(url=176.170.209.1, weight=1, currentWeight=0) x 98669 Node(url=176.170.209.5, weight=4, currentWeight=0) x 99376 Node(url=176.170.209.4, weight=9, currentWeight=0) x 99596 Node(url=176.170.209.6, weight=6, currentWeight=0) x 101373 Node(url=176.170.209.7, weight=1, currentWeight=0) x 101706 Node(url=176.170.209.3, weight=1, currentWeight=0) x 102884 Node(url=176.170.209.9, weight=1, currentWeight=0) x 103137 Node(url=176.170.209.2, weight=9, currentWeight=0) x 103965 add...... Node(url=176.1709.10, weight=9, currentWeight=0) x 85667 Node(url=176.170.209.8, weight=9, currentWeight=0) x 86560 Node(url=176.170.209.1, weight=1, currentWeight=0) x 90289 Node(url=176.170.209.7, weight=1, currentWeight=0) x 90905 Node(url=176.170.209.4, weight=9, currentWeight=0) x 90932 Node(url=176.1709.11, weight=1, currentWeight=0) x 91236 Node(url=176.170.209.5, weight=4, currentWeight=0) x 92081 Node(url=176.170.209.9, weight=1, currentWeight=0) x 92808 Node(url=176.170.209.2, weight=9, currentWeight=0) x 92847 Node(url=176.170.209.6, weight=6, currentWeight=0) x 93085 Node(url=176.170.209.3, weight=1, currentWeight=0) x 93590 remove..... Node(url=176.170.209.8, weight=9, currentWeight=0) x 93728 Node(url=176.1709.10, weight=9, currentWeight=0) x 95566 Node(url=176.170.209.1, weight=1, currentWeight=0) x 98669 Node(url=176.170.209.5, weight=4, currentWeight=0) x 99376 Node(url=176.170.209.4, weight=9, currentWeight=0) x 99596 Node(url=176.170.209.6, weight=6, currentWeight=0) x 101373 Node(url=176.170.209.7, weight=1, currentWeight=0) x 101706 Node(url=176.170.209.3, weight=1, currentWeight=0) x 102884 Node(url=176.170.209.9, weight=1, currentWeight=0) x 103137 Node(url=176.170.209.2, weight=9, currentWeight=0) x 103965
-
可以看到增加或者减少节点也是可以保证负载均衡的。
-
负载均衡中的一致性hash算法
前面几种算法主要是站在负载均衡服务的角度，保证每个机器节点获得的调用次数均衡或者相对均衡，但是实际生产环境调用次数相同并不一定真的能够让每台机器真的实现均衡，于是就有了负载最低优先的策略，负载最低优先可以使用如最小连接数、CPU/IO 负载，这里引入《从零开始学架构》中的介绍：
负载最低优先算法基本上能够比较完美地解决轮询算法的缺点，因为采用这种算法后，负载均衡系统需要感知服务器当前的运行状态。当然，其代价是复杂度大幅上升。通俗来讲，轮询可能是 5 行代码就能实现的算法，而负载最低优先算法可能要 1000 行才能实现，甚至需要负载均衡系统和服务器都要开发代码。负载最低优先算法如果本身没有设计好，或者不适合业务的运行特点，算法本身就可能成为性能的瓶颈，或者引发很多莫名其妙的问题。所以负载最低优先算法虽然效果看起来很美好，但实际上真正应用的场景反而没有轮询（包括加权轮询）那么多。
