详谈负载均衡算法
前言
19年我几乎把阿里很多部门都面过，那一年也是行情最好的一年，icbu、uc、淘系、乌鸫、ae、上海支付宝（刚好有朋友在那），那会真的惨烈，被摁在地上摩擦，不过我也因此全方面的对自己有了一次认识，知道了基础知识（八股文）不熟，在技术深度上欠缺。最后是拿了淘系的offer，不容易啊～
每次面试都是对过往的review，也是自我提升的垫脚石
最近在搞流量负载相关的东西，顺便就温故下负载均衡算法，然后也玩了一下ChatGPT，发现很强大，给的代码demo都很详细，感觉百度都可有可无了，hhh
负载均衡算法有哪些
我感觉可以让gpt帮我写篇文章了，笑死。
- 轮训
- 随机
- 最小活跃数
- 权重
- 自适应 6.so on...
前两个我们就不用说了，从第三点来聊聊
最小活跃数
什么是活跃数？它储存在哪里？为什么要这么做？
这里的活跃数指的是dubbo连接数，就是客户端对服务端的连接数有多少，它会优先指向连接数小的。它储存在客户端，也就是说每次请求会给连接+1，释放的时候又会-1。为什么这么做呢？为了分摊压力，让空闲的服务端多接点流量。
逻辑：从客户端的记录里面搂出哪个服务端连接数最小，如果有并列则看权重，如果权重一样则随机。
public class LeastActiveLoadBalance extends AbstractLoadBalance {
public static final String NAME = "leastactive";
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
int length = invokers.size(); // 总个数
int leastActive = -1; // 最小的活跃数
int leastCount = 0; // 相同最小活跃数的个数
int[] weights = new int[length]; // 权重
int totalWeight = 0; // 总权重
for (int i = 0; i < length; i++) {
Invoker<T> invoker = invokers.get(i);
int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive(); // 活跃数
int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), WEIGHT_KEY, DEFAULT_WEIGHT); // 权重
if (leastActive == -1 || active < leastActive) { // 发现更小的活跃数，重新开始
leastActive = active; // 记录最小活跃数
leastCount = 1; // 重新统计相同最小活跃数的个数
weights[0] = weight; // 将当前权重记录下来，留作备选
totalWeight = weight; // 初始化总权重
} else if (active == leastActive) { // 累计相同最小的活跃数
weights[leastCount++] = weight; // 将当前权重记录下来，留作备选
totalWeight += weight; // 累加权重
}
}
if (leastCount == 1) { // 如果只有一个最小则直接返回
return invokers.get(0);
}
// 如果权重不相等且权重大于0则按权重分配，否则随机分配
return selectByRandomWeight(invokers, weights, totalWeight);
}
}
复制代码
加权负载
这个就是我们人为给这些dubbo服务端加上权重，这样做的好处就是我们本来就是知道那台服务器配置比较牛，它可以承受更多的请求，这样我们让流量更多的打到它上面，更好利用资源。
基于rt自适应负载均衡
这个一开始我在博客看到的，就是讲dubbo3对这块会有关于cpu还有类似rt相关自适应的负载均衡
我看阿里的天池比赛中，看到这样一个根据rt来做负载均衡的，大家可以观摩一哈
- [complone/dubbo-loadbalance](Github.com/complone/du…)
package com.aliware.tianchi;
import org.Apache.dubbo.common.URL;
import org.apache.dubbo.rpc.Invocation;
import org.apache.dubbo.rpc.Invoker;
import org.apache.dubbo.rpc.RpcException;
import org.apache.dubbo.rpc.cluster.LoadBalance;
import com.aliware.tianchi.comm.CustomerInfo;
import JAVA.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @author complone
*/
public class UserLoadBalance implements LoadBalance {
@Override
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException {
//1、所有服务器争取每个打一次请求
Invoker invoker = doSelectInFreeInvokers(invokers);
//2、根据服务端信息分配权重
invoker = invoker != null ? invoker : doSelectWithWeigth(invokers);
return invoker;
}
/**
* 落实优先每个机器都有流量请求
*/
private <T> Invoker<T> doSelectInFreeInvokers(List<Invoker<T>> invokers) {
if (CustomerInfoManager.LOAD_INFO.size() < invokers.size()) {
for (Invoker invoker : invokers) {
CustomerInfo customerInfo = CustomerInfoManager.getServerLoadInfo(invoker);
if (customerInfo != null) break;
return invoker;
}
}
return null;
}
/**
* 根据服务端配置和平均耗时计算权重
*/
private <T> Invoker<T> doSelectWithWeigth(List<Invoker<T>> invokers) {
// 重新分配权重的<服务,权重>映射
int[] serviceWeight = new int[invokers.size()];
// 总权重
int totalWeight = 0;
// 1、计算总权重
for (int index = 0, size = invokers.size(); index < size; ++index) {
Invoker<T> invoker = invokers.get(index);
CustomerInfo customerInfo = CustomerInfoManager.getServerLoadInfo(invoker);
AtomicInteger availThreadAtomic = CustomerInfoManager.getAvailThread(invoker);
if (customerInfo != null) {
if (availThreadAtomic.get() > 0) {
int weight = customerInfo.getServerWeight();
//根据耗时重新计算权重(基本权重*(1秒/单个请求耗时))
int clientTimeAvgSpendCurr = customerInfo.getAvgSpendTime();
if (clientTimeAvgSpendCurr == 0) {
// 耗时为0，性能优，请求直接打到该机器
// 也有可能是性能差，采用随机
return invokers.get(ThreadLocalRandom.current().nextInt(invokers.size()));
}
// 计算权重
weight = weight * (500 / clientTimeAvgSpendCurr);
serviceWeight[index] = weight;
totalWeight = totalWeight + weight;
}
}
}
// 2、按照新的权重选择服务，权重加权随机算法
int oneWeight = ThreadLocalRandom.current().nextInt(totalWeight);
for (int i = 0, size = invokers.size(); i < size; ++i) {
oneWeight -= serviceWeight[i];
if (oneWeight < 0) {
return invokers.get(i);
}
}
//兜底采用随机算法
return invokers.get(ThreadLocalRandom.current().nextInt(invokers.size()));
}
}
复制代码
首先是
customerInfo.getAvgSpendTime()，就是客户端会保持每个服务端请求次数、总的请求时间，这样平均响应时间就出来了，这里为什么要用500去除，而不是其他数字呢？我没有仔细看内部细节，当分母越大，这个数越小，也就是rt越长，服务节点性能越差，对应的权重会越小，这个思想我们还是能理解的。
int oneWeight = ThreadLocalRandom.current().nextInt(totalWeight);
for (int i = 0, size = invokers.size(); i < size; ++i) {
oneWeight -= serviceWeight[i];
if (oneWeight < 0) {
return invokers.get(i);
}
}
复制代码
这块有点意思了，大家看得懂吗？让我想起之前抽奖算法，比如说a商品有40%，b商品有60%几率，怎么去抽奖呢？
同比比例扩大，比如说a有4个商品，b有6个商品，你去随机抽一个，是不是有那味了，哈哈。同样这里也是，就是我们把所有服务器节点的权重拿到了，总计一个总的权重，然后我们生成一个随机数，那么看它最后是命中那个节点，当权重大的它会更有几率命中，是这么个意思～
那基于cpu呢？
基于cpu自适应负载均衡
最重要就这些数据指标怎么拿到，chatgpt已经跟我讲了，可以通过grafana类似运维监控工具来提供，如何跟dubbo结合起来？如果这些数据没有拿到怎么兜底？
这个思路可以参考服务注册中心，其实就是pingpong，异步定期去拉取数据然后存到本地缓存里面，具体拉取的频率怎样，根据实际情况决定要多久去拉取，其次是访问量，比如说有很多节点请求次数频繁，那么就启用缓存，先把数据存缓存，dubbo直接读取缓存数据即可。最后兜底方案比如说读不到服务cpu值，那么直接换负载算法兜底。
总结
流量负载算法是一种常用的负载均衡策略，它可以将网络流量分配到多个服务器上，从而提高系统的性能和可靠性。常见的流量负载算法包括轮询、加权轮询、最小连接数等。在选择合适的负载均衡算法时，需要考虑服务器的性能、网络拓扑结构以及用户访问模式等因素。同时，为了保证系统的可靠性，需要采取故障转移和容错机制。
原文链接：
https://juejin.cn/post/7212616585768009787
