数据结构和算法专题---7、负载均衡算法与应用
2023-12-15 13:08:42
本章我们会对负载均衡算法做个简单介绍，包括常用的负载均衡算法（轮询、随机、哈希等）的概述、实现方式、典型场景做个说明。
概述
负载均衡，英文名称为Load Balance，其含义就是指将负载（工作任务）进行平衡、分摊到多个操作单元上进行运行，例如FTP服务器、Web服务器、企业核心应用服务器和其它主要任务服务器等，从而协同完成工作任务。既然涉及到多个机器，就涉及到任务如何分发，这就是负载均衡算法问题。
轮询（RoundRobin）
概述
轮询即排好队，一个接一个。前面调度算法中用到的时间片轮转，就是一种典型的轮询。但是前面使用数组和下标轮询实现。这里尝试手动写一个双向链表形式实现服务器列表的请求轮询算法。
实现
package com.ls.cloud.sys.alg.balance;
import java.util.LinkedList;
public class RR {
//当前服务节点
Server current;
//初始化轮询类，多个服务器ip用逗号隔开
public RR(String serverName){
System.out.println("init server list : "+serverName);
String[] names = serverName.split(",");
for (int i = 0; i < names.length; i++) {
Server server = new Server(names[i]);
if (current == null){
//如果当前服务器为空，说明是第一台机器，current就指向新创建的server
this.current = server;
//同时，server的前后均指向自己。
current.prev = current;
current.next = current;
}else {
//否则说明已经有机器了，按新加处理。
addServer(names[i]);
}
}
}
//添加机器
void addServer(String serverName){
System.out.println("add server : "+serverName);
Server server = new Server(serverName);
Server next = this.current.next;
//在当前节点后插入新节点
this.current.next = server;
server.prev = this.current;
//修改下一节点的prev指针
server.next = next;
next.prev=server;
}
//将当前服务器移除，同时修改前后节点的指针，让其直接关联
//移除的current会被回收期回收掉
void remove(){
System.out.println("remove current = "+current.name);
this.current.prev.next = this.current.next;
this.current.next.prev = this.current.prev;
this.current = current.next;
}
//请求。由当前节点处理即可
//注意：处理完成后，current指针后移
void request(){
System.out.println(this.current.name);
this.current = current.next;
}
public static void main(String[] args) throws InterruptedException {
//初始化两台机器
RR rr = new RR("192.168.0.1,192.168.0.2");
//启动一个额外线程，模拟不停的请求
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
rr.request();
}
}
}).start();
//3s后，3号机器加入清单
Thread.currentThread().sleep(3000);
rr.addServer("192.168.0.3");
//3s后，当前服务节点被移除
Thread.currentThread().sleep(3000);
rr.remove();
}
class Server{
Server prev;
Server next;
String name;
public Server(String name){
this.name = name;
}
}
}
结果分析
init server list : 192.168.0.1,192.168.0.2
add server : 192.168.0.2
192.168.0.1
192.168.0.2
192.168.0.1
192.168.0.2
192.168.0.1
add server : 192.168.0.3
192.168.0.2
192.168.0.3
192.168.0.1
192.168.0.2
192.168.0.3
192.168.0.1
remove current = 192.168.0.2
192.168.0.3
192.168.0.1
192.168.0.3
192.168.0.1
- 初始化后，只有1，2，两者轮询
- 3加入后，1，2，3，三者轮询
- 移除2后，只剩1和3轮询
优缺点
- 实现简单，机器列表可以自由加减，且时间复杂度为o(1)
- 无法针对节点做偏向性定制，节点处理能力的强弱无法区分对待
随机
概述
从可服务的列表中随机取一个提供响应。随机存取的场景下，适合使用数组更高效的实现下标随机读取。
实现
定义一个数组，在数组长度内取随机数，作为其下标即可。非常简单
package com.ls.cloud.sys.alg.balance;
import java.util.ArrayList;
import java.util.Random;
public class Rand {
ArrayList<String> ips ;
public Rand(String nodeNames){
System.out.println("init list : "+nodeNames);
String[] nodes = nodeNames.split(",");
//初始化服务器列表，长度取机器数
ips = new ArrayList<>(nodes.length);
for (String node : nodes) {
ips.add(node);
}
}
//请求
void request(){
//下标，随机数，注意因子
int i = new Random().nextInt(ips.size());
System.out.println(ips.get(i));
}
//添加节点，注意，添加节点会造成内部数组扩容
//可以根据实际情况初始化时预留一定空间
void addnode(String nodeName){
System.out.println("add node : "+nodeName);
ips.add(nodeName);
}
//移除
void remove(String nodeName){
System.out.println("remove node : "+nodeName);
ips.remove(nodeName);
}
public static void main(String[] args) throws InterruptedException {
Rand rd = new Rand("192.168.0.1,192.168.0.2");
//启动一个额外线程，模拟不停的请求
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
rd.request();
}
}
}).start();
//3s后，3号机器加入清单
Thread.currentThread().sleep(3000);
rd.addnode("192.168.0.3");
//3s后，当前服务节点被移除
Thread.currentThread().sleep(3000);
rd.remove("192.168.0.2");
}
}
结果分析
init list : 192.168.0.1,192.168.0.2
192.168.0.2
192.168.0.2
192.168.0.1
192.168.0.2
192.168.0.2
add node : 192.168.0.3
192.168.0.1
192.168.0.3
192.168.0.1
192.168.0.1
192.168.0.3
192.168.0.1
remove node : 192.168.0.2
192.168.0.3
192.168.0.1
192.168.0.1
192.168.0.3
- 初始化为1，2，两者不按顺序轮询，而是随机出现
- 3加入服务节点列表
- 移除2后，只剩1，3，依然是两者随机，无序
源地址哈希（Hash）
概述
对当前访问的ip地址做一个hash值，相同的key被路由到同一台机器去。场景常见于分布式集群环境下，用户登录时的请求路由和会话保持。
实现
使用HashMap可以实现请求值到对应节点的服务，其查找时的时间复杂度为o(1)。固定一种算法，将请求映射到key上即可。举例，将请求的来源ip末尾，按机器数取余作为key：
package com.ls.cloud.sys.alg.balance;
import java.util.ArrayList;
import java.util.Random;
public class Hash {
ArrayList<String> ips ;
public Hash(String nodeNames){
System.out.println("init list : "+nodeNames);
String[] nodes = nodeNames.split(",");
//初始化服务器列表，长度取机器数
ips = new ArrayList<>(nodes.length);
for (String node : nodes) {
ips.add(node);
}
}
//添加节点，注意，添加节点会造成内部Hash重排，思考为什么呢？？？
//这是个问题！在一致性hash中会进入详细探讨
void addnode(String nodeName){
System.out.println("add node : "+nodeName);
ips.add(nodeName);
}
//移除
void remove(String nodeName){
System.out.println("remove node : "+nodeName);
ips.remove(nodeName);
}
//映射到key的算法，这里取余数做下标
private int hash(String ip){
int last = Integer.valueOf(ip.substring(ip.lastIndexOf(".")+1,ip.length()));
return last % ips.size();
}
//请求
//注意，这里和来访ip是有关系的，采用一个参数，表示当前的来访ip
void request(String ip){
//下标
int i = hash(ip);
System.out.println(ip+"-->"+ips.get(i));
}
public static void main(String[] args) {
Hash hash = new Hash("192.168.0.1,192.168.0.2");
for (int i = 1; i < 10; i++) {
//模拟请求的来源ip
String ip = "192.168.0."+ i;
hash.request(ip);
}
hash.addnode("192.168.0.3");
for (int i = 1; i < 10; i++) {
//模拟请求的来源ip
String ip = "192.168.0."+ i;
hash.request(ip);
}
hash.remove("192.168.0.2");
for (int i = 1; i < 10; i++) {
//模拟请求的来源ip
String ip = "192.168.0."+ i;
hash.request(ip);
}
}
}
结果分析
init list : 192.168.0.1,192.168.0.2
192.168.0.1-->192.168.0.2
192.168.0.2-->192.168.0.1
192.168.0.3-->192.168.0.2
192.168.0.4-->192.168.0.1
192.168.0.5-->192.168.0.2
192.168.0.6-->192.168.0.1
192.168.0.7-->192.168.0.2
192.168.0.8-->192.168.0.1
192.168.0.9-->192.168.0.2
add node : 192.168.0.3
192.168.0.1-->192.168.0.2
192.168.0.2-->192.168.0.3
192.168.0.3-->192.168.0.1
192.168.0.4-->192.168.0.2
192.168.0.5-->192.168.0.3
192.168.0.6-->192.168.0.1
192.168.0.7-->192.168.0.2
192.168.0.8-->192.168.0.3
192.168.0.9-->192.168.0.1
remove node : 192.168.0.2
192.168.0.1-->192.168.0.3
192.168.0.2-->192.168.0.1
192.168.0.3-->192.168.0.3
192.168.0.4-->192.168.0.1
192.168.0.5-->192.168.0.3
192.168.0.6-->192.168.0.1
192.168.0.7-->192.168.0.3
192.168.0.8-->192.168.0.1
192.168.0.9-->192.168.0.3
- 初始化后，只有1，2，下标为末尾ip取余数，多次运行，响应的机器不变，实现了会话保持
- 3加入后，重新hash，机器分布发生变化
- 2被移除后，原来hash到2的请求被重新定位给3响应
最小连接数（LC）
概述
LeastConnections，即统计当前机器的连接数，选最少的去响应新的请求。前面的算法是站在请求维度，而最小连接数是站在机器的维度。
实现
定义一个链接表记录机器的节点id和机器连接数量的计数器。内部采用最小堆做排序处理，响应时取堆顶节点即是最小连接数。
结果分析
package com.ls.cloud.sys.alg.balance;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.atomic.AtomicInteger;
public class LC {
//节点列表
Node[] nodes;
//初始化节点，创建堆
// 因为开始时各节点连接数都为0，所以直接填充数组即可
LC(String ns){
String[] ns1 = ns.split(",");
nodes = new Node[ns1.length+1];
for (int i = 0; i < ns1.length; i++) {
nodes[i+1] = new Node(ns1[i]);
}
}
//节点下沉，与左右子节点比对，选里面最小的交换
//目的是始终保持最小堆的顶点元素值最小
//i:要下沉的顶点序号
void down(int i) {
//顶点序号遍历，只要到1半即可，时间复杂度为O(log2n)
while ( i << 1 < nodes.length){
//左子，为何左移1位？回顾一下二叉树序号
int left = i<<1;
//右子，左+1即可
int right = left+1;
//标记，指向 本节点，左、右子节点里最小的，一开始取i自己
int flag = i;
//判断左子是否小于本节点
if (nodes[left].get() < nodes[i].get()){
flag = left;
}
//判断右子
if (right < nodes.length && nodes[flag].get() > nodes[right].get()){
flag = right;
}
//两者中最小的与本节点不相等，则交换
if (flag != i){
Node temp = nodes[i];
nodes[i] = nodes[flag];
nodes[flag] = temp;
i = flag;
}else {
//否则相等，堆排序完成，退出循环即可
break;
}
}
}
//请求。非常简单，直接取最小堆的堆顶元素就是连接数最少的机器
void request(){
System.out.println("---------------------");
//取堆顶元素响应请求
Node node = nodes[1];
System.out.println(node.name + " accept");
//连接数加1
node.inc();
//排序前的堆
System.out.println("before:"+Arrays.toString(nodes));
//堆顶下沉
down(1);
//排序后的堆
System.out.println("after:"+Arrays.toString(nodes));
}
public static void main(String[] args) {
//假设有7台机器
LC lc = new LC("a,b,c,d,e,f,g");
//模拟10个请求连接
for (int i = 0; i < 10; i++) {
lc.request();
}
}
class Node{
//节点标识
String name;
//计数器
AtomicInteger count = new AtomicInteger(0);
public Node(String name){
this.name = name;
}
//计数器增加
public void inc(){
count.getAndIncrement();
}
//获取连接数
public int get(){
return count.get();
}
@Override
public String toString() {
return name+"="+count;
}
}
}
结果分析
---------------------
a accept
before:[null, a=1, b=0, c=0, d=0, e=0, f=0, g=0]
after:[null, b=0, d=0, c=0, a=1, e=0, f=0, g=0]
---------------------
b accept
before:[null, b=1, d=0, c=0, a=1, e=0, f=0, g=0]
after:[null, d=0, e=0, c=0, a=1, b=1, f=0, g=0]
---------------------
d accept
before:[null, d=1, e=0, c=0, a=1, b=1, f=0, g=0]
after:[null, e=0, d=1, c=0, a=1, b=1, f=0, g=0]
---------------------
e accept
before:[null, e=1, d=1, c=0, a=1, b=1, f=0, g=0]
after:[null, c=0, d=1, f=0, a=1, b=1, e=1, g=0]
---------------------
c accept
before:[null, c=1, d=1, f=0, a=1, b=1, e=1, g=0]
after:[null, f=0, d=1, g=0, a=1, b=1, e=1, c=1]
---------------------
f accept
before:[null, f=1, d=1, g=0, a=1, b=1, e=1, c=1]
after:[null, g=0, d=1, f=1, a=1, b=1, e=1, c=1]
---------------------
g accept
before:[null, g=1, d=1, f=1, a=1, b=1, e=1, c=1]
after:[null, g=1, d=1, f=1, a=1, b=1, e=1, c=1]
---------------------
g accept
before:[null, g=2, d=1, f=1, a=1, b=1, e=1, c=1]
after:[null, d=1, a=1, f=1, g=2, b=1, e=1, c=1]
---------------------
d accept
before:[null, d=2, a=1, f=1, g=2, b=1, e=1, c=1]
after:[null, a=1, b=1, f=1, g=2, d=2, e=1, c=1]
---------------------
a accept
before:[null, a=2, b=1, f=1, g=2, d=2, e=1, c=1]
after:[null, b=1, a=2, f=1, g=2, d=2, e=1, c=1]
- 初始化后，堆节点值都为0，即每个机器连接数都为0
- 堆顶连接后，下沉，堆重新排序，最小堆规则保持成立
应用案例
nginx upstream
upstream frontend {
#源地址hash
ip_hash;
server 192.168.0.1:8081;
server 192.168.0.2:8082 weight=1 down;
server 192.168.0.3:8083 weight=2;
server 192.168.0.4:8084 weight=3 backup;
server 192.168.0.5:8085 weight=4 max_fails=3 fail_timeout=30s;
}
- ip_hash：即源地址hash算法
- down：表示当前的server暂时不参与负载
- weight：即加权算法，默认为1，weight越大，负载的权重就越大。
- backup：备份机器，只有其它所有的非backup机器down或者忙的时候，再请求backup机器。
- max_fails：最大失败次数，默认值为1，这里为3，也就是最多进行3次尝试fail_timeout：超时时间为30秒，默认值是10s。
- 注意！weight和backup不能和ip_hash关键字一起使用。
springcloud ribbon IRule
#设置负载均衡策略 eureka‐application‐service为调用的服务的名称
eureka‐application‐service.ribbon.NFLoadBalancerRuleClassName=com.netflix.loadbalancer.RandomRule
- RoundRobinRule：轮询
- RandomRule：随机AvailabilityFilteringRule：先过滤掉由于多次访问故障而处于断路器跳闸状态的服务，还有并发的连接数量超过阈值的服务，然后对剩余的服务轮询
- WeightedResponseTimeRule：根据平均响应时间计算所有服务的权重，响应时间越快服务权重越大。刚启动时如果统计信息不足，则使用RoundRobinRule策略，等统计信息足够，会切换到该策略
- RetryRule：先按照RoundRobinRule的策略，如果获取服务失败则在指定时间内重试，获取可用的服务
- BestAvailableRule：会先过滤掉由于多次访问故障而处于断路器跳闸状态的服务，然后选择一个并发量最小的服务
- ZoneAvoidanceRule：默认规则，综合判断server所在区域的性能和server的可用性
dubbo负载均衡
使用Service注解
@Service(loadbalance = "roundrobin",weight = 100)
- RandomLoadBalance: 随机，这种方式是dubbo默认的负载均衡策略
- RoundRobinLoadBalance：轮询
- LeastActiveLoadBalance：最少活跃次数，dubbo框架自定义了一个Filter，用于计算服务被调用的次数
- ConsistentHashLoadBalance：一致性hash
文章来源:https://blog.csdn.net/u014526891/article/details/134870356
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！