Soul源码阅读系列（四）负载均衡的应用
28 Mar 2021 | Soul |在divide插件中，Soul网关提供了负载均衡算法，对请求网关的IP选择一个真实的服务。在Soul中，负载均衡算法有三种：HashLoadBalance，RandomLoadBalance，RoundRobinLoadBalance。默认使用的是RandomLoadBalance算法，你可以对每个规则要使用何种策略进行设置。
使用时机
在执行divide插件时，会调用负载均衡算法，根据选择的结果，设置真实的请求服务。
//org.dromara.soul.plugin.divide.DividePlugin#doExecute
protected Mono<Void> doExecute(final ServerWebExchange exchange, final SoulPluginChain chain, final SelectorData selector, final RuleData rule) {
//省略了其他代码
final String ip = Objects.requireNonNull(exchange.getRequest().getRemoteAddress()).getAddress().getHostAddress();
//使用负载均衡
DivideUpstream divideUpstream = LoadBalanceUtils.selector(upstreamList, ruleHandle.getLoadBalance(), ip);
// 设置真实的请求服务
String domain = buildDomain(divideUpstream);
//省略了其他代码
return chain.execute(exchange);
}
LoadBalance的继承关系如下
类的设计使用的时模板方法设计模式：在抽象类中实现每个组件通用的功能，一些具体的功能留给子类去实现。在这里AbstrctLoadBalance实现了负载均衡的通用方法：获取权重，入参判断等。doSelect()留给了子类去实现，即具体的负载均衡算法逻辑。
public abstract class AbstractLoadBalance implements LoadBalance {
//子类去实现
protected abstract DivideUpstream doSelect(List<DivideUpstream> upstreamList, String ip);
@Override
public DivideUpstream select(final List<DivideUpstream> upstreamList, final String ip) {
if (CollectionUtils.isEmpty(upstreamList)) {
return null;
}
//如果只有一个服务，就直接返回
if (upstreamList.size() == 1) {
return upstreamList.get(0);
}
return doSelect(upstreamList, ip);
}
protected int getWeight(final DivideUpstream upstream) {
//省略了代码的具体实现
}
//省略其他代码
}
在select()方法中，先判断有没有服务；然后判断是否只有一个，是的话，就直接返回。因为一个不需要负载均衡，只能请求它。有多个就会通过负载均衡选择具体的类。
RandomLoadBalance的原理
RandomLoadBalance 是加权随机算法的具体实现。假设我们有一组服务器 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次。
在代码实现上，并没有真正的创建各个区间，而是通过每次生成的随机数减去服务器的权重，当出现小于0时，就选择这个服务器。
还是用上面的例子，再说明一下，我们有 servers = [A, B, C]，weights = [5, 3, 2]，生成一个随机数offset = 7。
- 第一次循环，offset - 5 = 2 > 0，即 offset > 5， 表明其不会落在服务器 A 对应的区间上。
- 第二次循环，offset - 3 = -1 < 0，即 5 < offset < 8，表明其会落在服务器 B 对应的区间上
@Override
public DivideUpstream doSelect(final List<DivideUpstream> upstreamList, final String ip) {
//所有权重
int totalWeight = calculateTotalWeight(upstreamList);
//是否相同
boolean sameWeight = isAllUpStreamSameWeight(upstreamList);
if (totalWeight > 0 && !sameWeight) {
return random(totalWeight, upstreamList);
}
// 如果权重相同或者为0，则随机选择一个。
return random(upstreamList);
}
//加权随机算法
private DivideUpstream random(final int totalWeight, final List<DivideUpstream> upstreamList) {
// 随机数
int offset = RANDOM.nextInt(totalWeight);
// 对每个服务器进行处理
for (DivideUpstream divideUpstream : upstreamList) {
//随机数 = 随机数 - 当前服务器的权重
offset -= getWeight(divideUpstream);
//小于0，就选中，表示落在这个区间内了
if (offset < 0) {
return divideUpstream;
}
}
return upstreamList.get(0);
}
//如果权重相同或者为0，则随机选择一个。
private DivideUpstream random(final List<DivideUpstream> upstreamList) {
return upstreamList.get(RANDOM.nextInt(upstreamList.size()));
}
#####
RandomLoadBalance 是一个简单，高效的负载均衡算法实现。在经过多次请求后，能够将调用请求按照权重值进行“均匀”分配。当然 RandomLoadBalance 也存在一定的缺点，当调用次数比较少时，Random 产生的随机数可能会比较集中，此时多数请求会落到同一台服务器上。这个缺点并不是很严重，多数情况下可以忽略。
HashLoadBalance的原理
通过哈希算法计算所有服务地址，保存到map。然后也对当前请求的IP计算hash值，根据这个值到map中获取服务。
这里其实应用了一致性哈希的思想，用于尽可能地降低节点变动带来的数据迁移开销，可以参看这里，。
@Override
public DivideUpstream doSelect(final List<DivideUpstream> upstreamList, final String ip) {
//线程安全，且有序的 map
final ConcurrentSkipListMap<Long, DivideUpstream> treeMap = new ConcurrentSkipListMap<>();
//计算每个服务的hash
for (DivideUpstream address : upstreamList) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
//根据服务节点的 url 和 序号 计算hash值
long addressHash = hash("SOUL-" + address.getUpstreamUrl() + "-HASH-" + i);
treeMap.put(addressHash, address);
}
}
//计算当前的hash
long hash = hash(String.valueOf(ip));
//返回所有（key >= hash）的映射集合
SortedMap<Long, DivideUpstream> lastRing = treeMap.tailMap(hash);
if (!lastRing.isEmpty()) {
//取虚拟节点对应的真实服务节点
return lastRing.get(lastRing.firstKey());
}
return treeMap.firstEntry().getValue();
}
RoundRobinLoadBalance的原理
这里使用的是平滑加权轮询算法，实现比较复杂，完整代码逻辑请看源码。
假设我们有 servers = [A, B, C]，weights = [5, 1, 1]，这个权重，我们称之为“固定权重数组”，相应的，有一个叫“非固定权重数组”，“非固定权重数组”每次都会根据一定的规则发生变动。规则如下：每次有请求时，从当前权重中选择权重最大的服务器，用于处理请求。然后，更新非固定权重数组，它等于被选中请求的服务器固定权重减去总权重，其余的保留。以后发生的请求都按照这个规则来处理。
上面描述不是很好理解，下面还是举例进行说明。这里仍然使用服务器 [A, B, C] 对应权重 [5, 1, 1] 的例子说明，现在有7个请求依次进入负载均衡逻辑，选择过程如下：
@Override
public DivideUpstream doSelect(final List<DivideUpstream> upstreamList, final String ip) {
String key = upstreamList.get(0).getUpstreamUrl();
ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.get(key);
for (DivideUpstream upstream : upstreamList) {
String rKey = upstream.getUpstreamUrl();
WeightedRoundRobin weightedRoundRobin = map.get(rKey);
int weight = getWeight(upstream);
//创建服务权重
if (weightedRoundRobin == null) {
weightedRoundRobin = new WeightedRoundRobin();
weightedRoundRobin.setWeight(weight);
map.putIfAbsent(rKey, weightedRoundRobin);
}
//权重更新
if (weight != weightedRoundRobin.getWeight()) {
//weight changed
weightedRoundRobin.setWeight(weight);
}
//增加权重
long cur = weightedRoundRobin.increaseCurrent();
weightedRoundRobin.setLastUpdate(now);
//找出最大的
if (cur > maxCurrent) {
maxCurrent = cur;
selectedInvoker = upstream;
selectedWRR = weightedRoundRobin;
}
totalWeight += weight;
}
//省略了其他代码
if (selectedInvoker != null) {
selectedWRR.sel(totalWeight);
return selectedInvoker;
}
// should not happen here
return upstreamList.get(0);
}
小结，本文主要讲解了Soul网关中所采用的的负载均衡算法及其实现原理。
参考文献