1、算法分类
抛开技术细节、各个公司针对实际情况的特定实现，根据算法的期望可以大致分为以下几类：
| 类型 | 描述 |
|---|---|
| 任务平分类 | 将接受到的请求平均分发到RS，"平均"不是特指绝对数值的平均，可以是权重平均 |
| Hash类 | 根据请求的某些关键信息进行hash运算，将相同hash值的请求负载到同一RS。常见有源ip hash，uid hash |
| 响应优先类 | 根据RS的响应时间调整请求分配 |
| 系统负载优先类 | 根据RS的CPU负载、IO使用率、网卡吞吐量等系统性能指标调整请求分配 |
2、常见负载均衡算法与优缺点
2.1、轮询
接收到的请求按照顺序轮流分配请求到服务器。轮询是一种最简单的负载均衡策略，不关心服务器实际性能与负载。
优点:
简单，只依赖服务器与负载均衡系统的连接感知服务器状态
缺点:
1.当服务器系统负载很高，或当服务器出现严重故障(bug)从而无法正常处理请求但未跟负载均衡系统断开连接时，轮询策略依旧会将请求分配到异常的服务器
2.不能根据服务器配置高低来分配请求
简单即是轮询的优点也是缺点。
实现代码：
private AtomicInteger nextServerCounter = new AtomicInteger(0);
/**
* 轮询得到下一服务器下标，不能使用AtomicInteger.incrementAndGet % module，存在溢出风险
* @param modulo 可用服务器数
* @return
*/
public int getNext(int modulo) {
for (; ; ) {
int current = nextServerCounter.get();
int next = (current + 1) % modulo;
if (nextServerCounter.compareAndSet(current, next)) {
return next;
}
}
}
2.2、 随机
接收到的请求根据随机数分配请求到服务器。优缺点跟轮询类似
实现代码：
protected int chooseRandomInt(int serverCount) {
return ThreadLocalRandom.current().nextInt(serverCount);
}
2.3、加权轮询
针对轮询策略无法根据服务器处理能力高低分配请求的缺点，可以使用配置权重的方式来实现。但加权轮询也无法处理服务器应用异常而未与负载均衡系统断开的场景。
实现代码：
public static class ServerWeight {
private String target;
private Integer weight;
}
/**服务器列表(带权重)*/
private static List<ServerWeight> serverWeights;
/**上次选择的服务器*/
private int currentIndex;
/**当前调度的权值*/
private int currentWeight;
/**最大权重*/
private int maxWeight;
/**权重的最大公约数*/
private int gcdWeight;
/**服务器数*/
private int serverCount;
private void init(){
// 初始化服务器权重信息，最大公约数等信息
...
}
public int choose() {
while (true) {
currentIndex = (currentIndex + 1) % serverCount;
if (currentIndex == 0) {
currentWeight = currentWeight - gcdWeight;
if (currentWeight <= 0) {
currentWeight = maxWeight;
if (currentWeight == 0) {
return -1;
}
}
}
if (serverWeights.get(currentIndex).getWeight() >= currentWeight) {
return currentIndex;
}
}
}
2.4、 一致性hash算法
根据请求的某些特定信息进行hash运算，将相同hash值分配到同一服务器。
根据uid/session id hash，相同的用户会话会负载到相同的服务器
根据client ip hash，相同的源设备负载到相同的服务器，应用场景如事务性操作
实现代码：
public int choose(Object key, int serverCount) {
int hashcode = key.hashCode();
int selectedIndex = Hashing.consistentHash(hashcode, serverCount); // 使用Guava的一致性哈希算法
return selectedIndex;
}
2.5、响应优先算法
响应优先算法是从客户端角度来选择服务器的算法，优先分配响应速度最快的服务器，通过这种方式让客户端能最快响应。
实现响应优先算法需要感知服务器状态，收集维护响应时间这个维度信息。
复杂点：
1.负载均衡系统需要收集、维护、分析每个服务器每次请求的响应时间。
2.为了减少收集、分析所有请求响应时间的性能消耗，可以使用采样方式来收集，但采访方式会减少准确率，同时也会带来实现复杂度。
3.需要选择统计周期，如5分钟内、30分钟内....这也会带来一定的复杂度，且需要根据实际业务选择统计周期，没有统一最优周期。
2.6、 系统负载优先算法
同响应优先算法一样，本质上系统负载优先算法也是通过感知服务器状态，将请求分配到负载最低的服务器。不同的是系统负载优先是站在服务器角度来选择分配权重，
且关心的是服务器CPU负载、I/O使用率、网卡吞吐量、网络连接数等维度的状态。
不同的负载均衡系统会根据应用场景选择最关注的服务器状态。如CPU密集型系统关注CPU负载，I/O密集型系统关注I/O使用率，LVS关注连接数。
同响应优先算法一样，由于需要感知服务器状态，进行周期统计。需要对服务器和负载均衡系统都进行一定的开发才能实现，带来了较高的复杂度，容易出现隐蔽的bug
或者由于设计不好而成为性能瓶颈。
响应优先算法和系统负载优先算法理论上可以完美解决轮询算法的缺点，因为需要感知服务器的运行状态，但同时代价是复杂度的大幅上升。
2.7、动态加权轮询算法
负载均衡系统还可以引入熔断降级等机制来对服务质量出现问题的服务器进行异常处理。
下面简易代码是动态加权轮询算法的实现，通过分析周期内某台服务器请求的错误次数、成功次数来动态加减服务器权重。
/**服务器列表(带权重)*/
private static List<ServerWeight> serverWeights;
/** 基本加权轮询实现见2.3 */
/** 动态加权逻辑如下 */
/** key：服务器target(ip:port)，value：CountLimit*/
private static Map<String, CountLimit> failCountLimitMap;
private static Map<String, CountLimit> successCountLimitMap;
public void whenRequestFail(RequestFailEvent event) {
String target = event.getTarget();
if (failCountLimitMap.containsKey(target)) {
Pair<Boolean, Boolean> pair = failCountLimitMap.get(target).grant();
if (!pair.getLeft() && pair.getRight()) {
ServerWeight expect = null;
for (ServerWeight serverWeight : serverWeights) {
if (serverWeight.getTarget().equalsIgnoreCase(target)) {
expect = serverWeight;
break;
}
}
if (expect != null) {
Integer toUpdate = expect.getWeight() - degrade;
// TODO 需要考虑新的权重是否<=0，进行特殊处理
expect.setWeight(toUpdate);
}
}
}
public void whenRequestSuccess(RequestSuccessEvent event) {
// 逻辑类似whenRequestFail，省略
...
Integer toUpdate = expect.getWeight() + upgrade;
// TODO 需要考虑新的权重是否达到初始权重，进行特殊处理
expect.setWeight(toUpdate)
}
/**
* 次数统计，在达到阈值时，一个周期只提醒一次
*/
public static class CountLimit {
private long startPoint;
private int count = 0;
/**
* 阈值
*/
private int limit;
/**
* 时间间隔
*/
private long period;
/**
* 达到阈值通知标志
*/
private boolean overNotify;
private final Object lock = new Object();
/**
* @param limit 限制次数
* @param period 时间间隔
* @param timeUnit 间隔类型
*/
public CountLimit(int limit, int period, TimeUnit timeUnit) {
this.startPoint = System.currentTimeMillis();
this.period = timeUnit.toMillis(period);
this.limit = limit;
overNotify = false;
}
public boolean grant() {
long curTime = System.currentTimeMillis();
synchronized (lock) {
count++;
if (count > limit) {
if (curTime - startPoint > period) {
startPoint = curTime;
count = 0;
overNotify = false;
return ImmutablePair.of(true, false);
} else {
if (!overNotify) {
overNotify = true;
return ImmutablePair.of(false, true);
}
return ImmutablePair.of(false, false);
}
} else {
return ImmutablePair.of(true, false);
}
}
}
}
