Dubbo-负载均衡原理解析(1),一个本科渣渣是怎么逆袭从咸鱼到Offer收割机的

简介: Dubbo-负载均衡原理解析(1),一个本科渣渣是怎么逆袭从咸鱼到Offer收割机的
System.out.println(getServer());
}
}
}

执行结果如下

192.168.0.6

192.168.0.10

192.168.0.10

192.168.0.6

192.168.0.4

192.168.0.2

192.168.0.6

192.168.0.2

192.168.0.4

192.168.0.6

这种实现方法在遇到权重之和特别大的时候就会比较消耗内存,因为需要对ip地址进行复制,权重之和越大,那么上文中的ips就需要越多的内存。

方式二:区间范围实现

假设我们有一组服务器servers=[A,B,C],他们对应的权重为weights=[5,3,2],权重总和为10。现在把这些权重值平铺在一维坐标值上,[0, 5) 区间属于服务器 A,[5, 8) 区间属于服务器 B,[8, 10) 区间属于服务器 C。接下来通过随机数生成器生成一个范围 [0, 10) 之间的随机数,然后计算在这个随机数会落在哪个区间上。比如数字3会落在服务器A对应的区间上,此时返回服务器A即可。权重越大的机器,在坐标轴上对应的区间范围就越大,因此随机数生成器生成的数字就会有更大的概率落在此区间内。只要随机数生成器产生的随机数分布性很好,在经过多次选择后,每个服务器被选中的次数比例接近其权重比例。

比如,经过一万次选择后,服务器A被选中的次数大约为5000次,服务器B被选中的次数约为3000次,服务器C被选中的次数约为2000次。

假设现在随机数offset=7;

  1. offset<5 is false,所以不在[0, 5)区间,将offset = offset - 5(offset=2)
  2. offset<3 is true,所以处于[5, 8)区间,所以应该选用B服务器
public class WeightRandomV2 {
public static String getServer() {
int totalWeight = 0;
boolean sameWeight = true; //如果所有权重都相等,随机一个ip即可
Object[] weights = ServerIps.WEIGHT_LIST.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;
}
}
Random random = new Random();
int randomPos = random.nextInt(totalWeight);
//权重值不相等
if (!sameWeight) {
for (String ip : ServerIps.WEIGHT_LIST.keySet()) {
Integer value = ServerIps.WEIGHT_LIST.get(ip);
if (randomPos < value) {
return ip;
}
randomPos = randomPos - value;
}
}
return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[new Random().nextInt(ServerIps.WEIGHT_LIST.size())];
}
public static void main(String[] args) {
//连续调用10次
for (int i = 0; i < 10; i++) {
System.out.println(getServer());
}
}
}

轮询算法-RoundRobinLoadBalance


特点

  • 加权轮询,按公约后的权重设置轮询比率,循环调用节点
  • 缺点:同样存在慢的提供者累积请求的问题。

代码实现(简单的轮询算法)

public class RoundRobin {
private static Integer pos = 0;
public static String getServer() {
String ip = “”;
//pos同步
synchronized (pos) {
if (pos >= ServerIps.LIST.size()) {
pos = 0;
}
ip = ServerIps.LIST.get(pos);
pos++;
}
return ip;
}
public static void main(String[] args) {
//连续调用10次
for (int i = 0; i < 11; i++) {
System.out.println(getServer());
}
}
}

执行结果如下:

192.168.0.1

192.168.0.2

192.168.0.3

192.168.0.4

192.168.0.5

192.168.0.6

192.168.0.7

192.168.0.8

192.168.0.9

192.168.0.10

192.168.0.1

这种算法很简单,也很公平,每台服务轮流来进行服务,但是有的机器性能好,所以能者多劳,和随机算法一样,加上权重维度以后,其中一种实现方法就是复制法,复制法的缺点是,比较消耗内存。

介绍另外一种算法:这种算法引入一个概念:调用编号,比如第1次调用为1,第2次调用为2,第100次调用为100,调用编号是递增的,所以我们可以根据这个调用编号推算出服务器。

假设我们有三台服务器servers = [A, B, C],对应的权重为 weights = [ 2, 5, 1], 总权重为8,我们可以理解为有8台“服务器”,这是8台“不具有并发功能”,其中有2台为A,5台为B,1台为C,一次调用过来的时候,需要按顺序访问,比如有10次调用,那么服务器调用顺序为AABBBBBCAA,调用编号会越来越大,而服务器是固定的,所以需要把调用编号“缩小”,这里对调用编号进行取余,除数为总权重和

比如:

  1. 1号调用,1%8=1;
  2. 2号调用,2%8=2;
  3. 3号调用,3%8=3;
  4. 8号调用,8%8=0;
  5. 9号调用,9%8=1;
  6. 100号调用,100%8=4;

我们发现调用编号可以被缩小为0-7之间的8个数字,问题是怎么根据这个8个数字找到对应的服务器呢?和我们随机算法类似,这里也可以把权重想象为一个坐标轴“0-----2-----7-----8”

  1. 1号调用,1%8=1,offset = 1, offset <= 2 is true,取A;
  2. 2号调用,2%8=2;offset = 2,offset <= 2 is true, 取A;
  3. 3号调用,3%8=3;offset = 3, offset <= 2 is false, offset = offset - 2, offset = 1, offset <= 5,取B
  4. 8号调用,8%8=0;offset = 0, 特殊情况,offset = 8,offset <= 2 is false, offset = offset - 2, offset = 6, offset <= 5 is false, offset = offset - 5, offset = 1, offset <= 1 is true, 取C;
  5. 9号调用,9%8=1;// …
  6. 100号调用,100%8=4; //…

模拟调用编号获取工具:

public class Sequence {
public static Integer num=0;
public static Integer getAndIncrement(){
return ++num;
}
}
public class WeightRoundRobin {
private static Integer pos = 0;
public static String getServer() {
int totalWeight = 0;
boolean sameWeight = true;
Object[] weights = ServerIps.WEIGHT_LIST.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 = Sequence.getAndIncrement();
Integer offset = sequenceNum % totalWeight;
offset = offset == 0 ? totalWeight : offset;
if (!sameWeight) {
for (String ip : ServerIps.WEIGHT_LIST.keySet()) {
Integer weight = ServerIps.WEIGHT_LIST.get(ip);
if (offset <= weight) {
return ip;
}
offset = offset - weight;
}
}
String ip = “”;
synchronized (pos) {
if (pos >= ServerIps.LIST.size()) {
pos = 0;
}
ip = ServerIps.LIST.get(pos);
pos++;
}
return ip;
}
public static void main(String[] args) {
// 连续调用11次
for (int i = 0; i < 11; i++) {
System.out.println(getServer());
}
}
}

执行结果如下

192.168.0.2

192.168.0.2

192.168.0.2

192.168.0.2

192.168.0.2

192.168.0.2

192.168.0.2

192.168.0.2

192.168.0.1

192.168.0.4

192.168.0.4

但是这种算法有一个缺点:一台服务器的权重特别大的时候,他需要连续的的处理请求,但是实际上我们想达到的效果是,对于100次请求,只要有100*8/50=16次就够了,这16次不一定要连续的访问,比如假设我们有三台服务器 servers = [A, B, C],对应的权重为 weights = [5, 1, 1] , 总权重为7,那么上述这个算法的结果是:AAAAABC,那么如果能够是这么一个结果呢:AABACAA,把B和C平均插入到5个A中间,这样是比较均衡的了。

我们这里可以改成平滑加权轮询。

平滑加权轮询


特点

思路:每个服务器对应两个权重,分别为weight 和currentWeight.其中weight是固定的,currentWeight会动态调整,初始值为0.当有新的请求进来时,遍历服务器列表,让它的currentWeight加上自身权重。遍历完成后,找到最大的 currentWeight,并将其减去权重总和,然后返回相应的服务器即可。

假设我们有三台服务器 servers = [A, B, C],对应的权重为 weights = [5, 1, 1] , 总权重为7

| 请求编号 | currentWeight 数组 (current_weight += weight) | 选择结果(max(currentWeight)) | 减去权重总和后的currentWeight 数组(max(currentWeight) -= sum(weight)) |
| — | — | — | — |
| 1 | [5, 1, 1] | A | [-2, 1, 1] |
| 2 | [3, 2, 2] | A | [-4, 2, 2] |
| 3 | [1, 3, 3] | B | [1, -4, 3] |
| 4 | [6, -3, 4] | A | [-1, -3, 4] |
| 5 | [4, -2, 5] | C | [4, -2, -2] |
| 6 | [9, -1, -1] | A | [2, -1, -1] |
| 7 | [7, 0, 0] | A | [0, 0, 0] |

如上,经过平滑性处理后,得到的服务器序列为 [A, A, B, A, C, A, A],相比之前的序列 [A, A, A, A, A, B, C],分布性要好一些。初始情况下 currentWeight = [0, 0, 0],第7个请求处理完后,currentWeight 再次变为 [0, 0, 0]。

代码实现

// 增加一个Weight类,用来保存ip, weight(固定不变的原始权重), currentweight(当前会变化的权重)
public 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;
}
}
public class WeightRoundRobinV2 {
private static Map weightMap = new HashMap();
public static String getServer() {
// 获取权重之和
int totalWeight = ServerIps.WEIGHT_LIST1.values().stream().reduce(0, (w1, w2) -> w1 + w2);
//初始化weightMap,初始时将currentWeight赋值为weight
if (weightMap.isEmpty()) {
ServerIps.WEIGHT_LIST1.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 weight : weightMap.values()) {
weight.setCurrentWeight(weight.getCurrentWeight() + weight.getWeight());
}
//返回maxCurrentWeight所对应的ip
return maxCurrentWeight.getIp();
}
public static void main(String[] args) {
// 连续调用10次
for (int i = 0; i < 10; i++) {
System.out.println(getServer());
}
}
}

ServerIps里添加数据WEIGHT_LIST1:

public static final Map WEIGHT_LIST1 = new HashMap();
static {
// 权重之和为50
WEIGHT_LIST1.put(“A”, 5);
WEIGHT_LIST1.put(“B”, 1);
WEIGHT_LIST1.put(“C”, 1);
}

执行结果如下:

A

A

B

A

C

A

A

A

A

B

一致性哈希算法-ConsistentHashLoadBalance


服务器集群接收到一次请求调用时,可以根据请求的信息,比如客户端的Ip地址,或请求路径与请求参数等信息进行哈希,可以得到一个哈希值,特点是对于相同的ip地址,或请求路径和请求参数哈希出来的值是不一样的,只要能再增加一个算法,能够把这个哈希值映射成一个服务端ip地址,就可以使相同的请求(相同的ip地址,或请求路径和请求参数)落到同一服务器上。

因为客户端发起的请求情况是无穷无尽的(客户端地址不同,请求参数不同等),所以对于的哈希值是无穷大的,所以我们不可能把所有的哈希值都进行映射到服务端ip上。所以这里用到了哈希环。

  • 哈希值如果需要ip1和ip2之间的,则应该选择ip2作为结果;


相关文章
|
3天前
|
机器学习/深度学习 算法 计算机视觉
卷积神经网络(CNN)的工作原理深度解析
【6月更文挑战第14天】本文深度解析卷积神经网络(CNN)的工作原理。CNN由输入层、卷积层、激活函数、池化层、全连接层和输出层构成。卷积层通过滤波器提取特征,激活函数增加非线性,池化层降低维度。全连接层整合特征,输出层根据任务产生预测。CNN通过特征提取、整合、反向传播和优化进行学习。尽管存在计算量大、参数多等问题,但随着技术发展,CNN在计算机视觉领域的潜力将持续增长。
|
3天前
|
存储 SQL 数据管理
数据库技术深度解析:原理、应用与未来展望
一、引言 数据库技术作为现代信息技术的基石,承载着数据存储、管理、检索和分析的重任
|
3天前
|
存储 安全 Java
深入理解Java中的ThreadLocal机制:原理、方法与使用场景解析
深入理解Java中的ThreadLocal机制:原理、方法与使用场景解析
13 2
|
3天前
|
存储 前端开发 Java
深入解析Java类加载机制:原理、过程与实践
深入解析Java类加载机制:原理、过程与实践
10 2
|
3天前
|
缓存 算法 Java
深入解析线程上下文切换的原理与优化策略
深入解析线程上下文切换的原理与优化策略
10 0
|
3天前
|
存储 安全 Java
深入解析 Java 中的 Synchronized:原理、实现与性能优化
深入解析 Java 中的 Synchronized:原理、实现与性能优化
9 1
|
4天前
|
安全 Java 数据安全/隐私保护
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
14 0
|
4天前
|
JSON 安全 Java
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
13 0
|
5天前
|
网络协议 网络架构
RPC原理解析
RPC原理解析
11 0
|
7天前
|
存储 Cloud Native NoSQL
深度解析数据库技术:核心原理、应用实践及未来展望
一、引言 在信息化高速发展的今天,数据库技术作为数据管理的基石,承载着企业运营、决策支持、大数据分析等核心功能

热门文章

最新文章

推荐镜像

更多