下面我们来分析一下Dubbo的负载均衡机制。我们知道，服务的调用会有很多的并发请求，这就需要在服务间进行负载均衡，来减轻服务的访问压力。我们先来看一下AbstractClusterInvoker的select方法
protected Invoker<T> select(LoadBalance loadbalance, Invocation invocation, List<Invoker<T>> invokers, List<Invoker<T>> selected) throws RpcException {
if (invokers == null || invokers.isEmpty()) {
return null;
}
// 获得 sticky 配置项，方法级
String methodName = invocation == null ? "" : invocation.getMethodName();
boolean sticky = invokers.get(0).getUrl().getMethodParameter(methodName, Constants.CLUSTER_STICKY_KEY, Constants.DEFAULT_CLUSTER_STICKY);
{
// ignore overloaded method
// 若 stickyInvoker 不存在于 invokers 中，说明不在候选中，需要置空，重新选择
if (stickyInvoker != null && !invokers.contains(stickyInvoker)) {
stickyInvoker = null;
}
// ignore cucurrent problem
// 若开启粘滞连接的特性，且 stickyInvoker 不存在于 selected 中，则返回 stickyInvoker 这个 Invoker 对象
if (sticky && stickyInvoker != null && (selected == null || !selected.contains(stickyInvoker))) {
// 若开启排除非可用的 Invoker 的特性，则校验 stickyInvoker 是否可用。若可用，则进行返回
if (availablecheck && stickyInvoker.isAvailable()) {
return stickyInvoker;
}
}
}
// 执行选择
Invoker<T> invoker = doselect(loadbalance, invocation, invokers, selected);
// 若开启粘滞连接的特性，记录最终选择的 Invoker 到 stickyInvoker
if (sticky) {
stickyInvoker = invoker;
}
return invoker;
}
再到doselect方法
private Invoker<T> doselect(LoadBalance loadbalance, Invocation invocation, List<Invoker<T>> invokers, List<Invoker<T>> selected) throws RpcException {
if (invokers == null || invokers.isEmpty()) {
return null;
}
// 【第一种】如果只有一个 Invoker ，直接选择
if (invokers.size() == 1) {
return invokers.get(0);
}
// 【第二种】如果只有两个 Invoker ，退化成轮循
// If we only have two invokers, use round-robin instead.
if (invokers.size() == 2 && selected != null && !selected.isEmpty()) {
return selected.get(0) == invokers.get(0) ? invokers.get(1) : invokers.get(0);
}
// 【第三种】使用 Loadbalance ，选择一个 Invoker 对象。
Invoker<T> invoker = loadbalance.select(invokers, getUrl(), invocation);
// If the `invoker` is in the `selected` or invoker is unavailable && availablecheck is true, reselect.
// 如果 selected中包含（优先判断） 或者 不可用&&availablecheck=true 则重试.
if ((selected != null && selected.contains(invoker))
|| (!invoker.isAvailable() && getUrl() != null && availablecheck)) {
try {
//【第四种】重选一个 Invoker 对象
Invoker<T> rinvoker = reselect(loadbalance, invocation, invokers, selected, availablecheck);
if (rinvoker != null) {
invoker = rinvoker;
} else {
// Check the index of current selected invoker, if it's not the last one, choose the one at index+1.
// 【第五种】看下第一次选的位置，如果不是最后，选+1位置.
int index = invokers.indexOf(invoker);
try {
// Avoid collision
// 最后在避免碰撞
invoker = index < invokers.size() - 1 ? invokers.get(index + 1) : invoker;
} catch (Exception e) {
logger.warn(e.getMessage() + " may because invokers list dynamic change, ignore.", e);
}
}
} catch (Throwable t) {
logger.error("clustor relselect fail reason is :" + t.getMessage() + " if can not slove ,you can set cluster.availablecheck=false in url", t);
}
}
return invoker;
}
其实就是从Invoker集合中通过负载均衡算法选择一个进行调用
下面我们来看一个接口LoadBalance
/**
* select one invoker in list.
*
* 从 Invoker 集合中，选择一个
*
* @param invokers invokers.
* @param url refer url
* @param invocation invocation.
* @return selected invoker.
*/
@Adaptive("loadbalance")
<T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException;
再看一个类AbstractLoadBalance，这个类提供了计算权重的方法
protected int getWeight(Invoker<?> invoker, Invocation invocation) {
// 获得 weight 配置，即服务权重。默认为 100
int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);
if (weight > 0) {
long timestamp = invoker.getUrl().getParameter(Constants.REMOTE_TIMESTAMP_KEY, 0L);
if (timestamp > 0L) {
// 获得启动总时长
int uptime = (int) (System.currentTimeMillis() - timestamp);
// 获得预热需要总时长。默认为 10 * 60 * 1000 = 10 分钟
int warmup = invoker.getUrl().getParameter(Constants.WARMUP_KEY, Constants.DEFAULT_WARMUP);
// 处于预热中，计算当前的权重
if (uptime > 0 && uptime < warmup) {
weight = calculateWarmupWeight(uptime, warmup, weight);
}
}
}
return weight;
}
下面介绍几种Dubbo提供的负载均衡算法
RandomLoadBalance，随机，按权重设置随机概率。 在一个截面上碰撞的概率高，但调用量越大分布越均匀，而且按概率使用权重后也比较均匀，有利于动态调整提供者权重。
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
int length = invokers.size(); // Number of invokers
int totalWeight = 0; // The sum of weights
boolean sameWeight = true; // Every invoker has the same weight?
// 计算总权限
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation); // 获得权重
totalWeight += weight; // Sum
if (sameWeight && i > 0 && weight != getWeight(invokers.get(i - 1), invocation)) {
sameWeight = false;
}
}
// 权重不相等，随机后，判断在哪个 Invoker 的权重区间中
if (totalWeight > 0 && !sameWeight) {
// 随机
// If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on totalWeight.
int offset = random.nextInt(totalWeight);
// Return a invoker based on the random value.
// 区间判断
for (Invoker<T> invoker : invokers) {
offset -= getWeight(invoker, invocation);
if (offset < 0) {
return invoker;
}
}
}
// 权重相等，平均随机
// If all invokers have the same weight value or totalWeight=0, return evenly.
return invokers.get(random.nextInt(length));
}
ConsistentHashLoadBalance，一致性 Hash，相同参数的请求总是发到同一提供者。 当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
// 基于 invokers 集合，根据对象内存地址来计算定义哈希值
int identityHashCode = System.identityHashCode(invokers);
// 获得 ConsistentHashSelector 对象。若为空，或者定义哈希值变更（说明 invokers 集合发生变化），进行创建新的 ConsistentHashSelector 对象
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
if (selector == null || selector.identityHashCode != identityHashCode) {
selectors.put(key, new ConsistentHashSelector<T>(invokers, invocation.getMethodName(), identityHashCode));
selector = (ConsistentHashSelector<T>) selectors.get(key);
}
return selector.select(invocation);
}
private static final class ConsistentHashSelector<T> {
/**
* 虚拟节点与 Invoker 的映射关系
*/
private final TreeMap<Long, Invoker<T>> virtualInvokers;
/**
* 每个Invoker 对应的虚拟节点数
*/
private final int replicaNumber;
/**
* 定义哈希值
*/
private final int identityHashCode;
/**
* 取值参数位置数组
*/
private final int[] argumentIndex;
ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
// 设置 identityHashCode
this.identityHashCode = identityHashCode;
URL url = invokers.get(0).getUrl();
// 初始化 replicaNumber
this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
// 初始化 argumentIndex
String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
argumentIndex = new int[index.length];
for (int i = 0; i < index.length; i++) {
argumentIndex[i] = Integer.parseInt(index[i]);
}
// 初始化 virtualInvokers
for (Invoker<T> invoker : invokers) {
String address = invoker.getUrl().getAddress();
// 每四个虚拟结点为一组，为什么这样？下面会说到
for (int i = 0; i < replicaNumber / 4; i++) {
// 这组虚拟结点得到惟一名称
byte[] digest = md5(address + i);
// Md5是一个16字节长度的数组，将16字节的数组每四个字节一组，分别对应一个虚拟结点，这就是为什么上面把虚拟结点四个划分一组的原因
for (int h = 0; h < 4; h++) {
// 对于每四个字节，组成一个long值数值，做为这个虚拟节点的在环中的惟一key
long m = hash(digest, h);
virtualInvokers.put(m, invoker);
}
}
}
}
public Invoker<T> select(Invocation invocation) {
// 基于方法参数，获得 KEY
String key = toKey(invocation.getArguments());
// 计算 MD5 值
byte[] digest = md5(key);
// 计算 KEY 值
return selectForKey(hash(digest, 0));
}
private String toKey(Object[] args) {
StringBuilder buf = new StringBuilder();
for (int i : argumentIndex) {
if (i >= 0 && i < args.length) {
buf.append(args[i]);
}
}
return buf.toString();
}
private Invoker<T> selectForKey(long hash) {
// 得到大于当前 key 的那个子 Map ，然后从中取出第一个 key ，就是大于且离它最近的那个 key
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
// 不存在，则取 virtualInvokers 第一个
if (entry == null) {
entry = virtualInvokers.firstEntry();
}
// 存在，则返回
return entry.getValue();
}
private long hash(byte[] digest, int number) {
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
// 计算 MD5
private byte[] md5(String value) {
MessageDigest md5;
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.reset();
byte[] bytes;
try {
bytes = value.getBytes("UTF-8");
} catch (UnsupportedEncodingException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.update(bytes);
return md5.digest();
}
}
LeastActiveLoadBalance，最少活跃调用数，相同活跃数的随机，活跃数指调用前后计数差。使慢的提供者收到更少请求，因为越慢的提供者的调用前后计数差会越大。
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
int length = invokers.size(); // 总个数
int leastActive = -1; // 最小的活跃数
int leastCount = 0; // 相同最小活跃数的个数
int[] leastIndexes = new int[length]; // 相同最小活跃数的下标
int totalWeight = 0; // 总权重
int firstWeight = 0; // 第一个权重，用于于计算是否相同
boolean sameWeight = true; // 是否所有权重相同
// 计算获得相同最小活跃数的数组和个数
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(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT); // 权重
if (leastActive == -1 || active < leastActive) { // 发现更小的活跃数，重新开始
leastActive = active; // 记录最小活跃数
leastCount = 1; // 重新统计相同最小活跃数的个数
leastIndexes[0] = i; // 重新记录最小活跃数下标
totalWeight = weight; // 重新累计总权重
firstWeight = weight; // 记录第一个权重
sameWeight = true; // 还原权重相同标识
} else if (active == leastActive) { // 累计相同最小的活跃数
leastIndexes[leastCount++] = i; // 累计相同最小活跃数下标
totalWeight += weight; // 累计总权重
// 判断所有权重是否一样
if (sameWeight && weight != firstWeight) {
sameWeight = false;
}
}
}
// assert(leastCount > 0)
if (leastCount == 1) {
// 如果只有一个最小则直接返回
return invokers.get(leastIndexes[0]);
}
if (!sameWeight && totalWeight > 0) {
// 如果权重不相同且权重大于0则按总权重数随机
int offsetWeight = random.nextInt(totalWeight);
// 并确定随机值落在哪个片断上
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexes[i];
offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
if (offsetWeight <= 0) {
return invokers.get(leastIndex);
}
}
}
// 如果权重相同或权重为0则均等随机
return invokers.get(leastIndexes[random.nextInt(leastCount)]);
}
RoundRobinLoadBalance，轮循，按公约后的权重设置轮循比率。存在慢的提供者累积请求的问题，比如：第二台机器很慢，但没挂，当请求调到第二台时就卡在那，久而久之，所有请求都卡在调到第二台上。
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
int length = invokers.size(); // Number of invokers
int maxWeight = 0; // The maximum weight
int minWeight = Integer.MAX_VALUE; // The minimum weight
final LinkedHashMap<Invoker<T>, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<Invoker<T>, IntegerWrapper>();
int weightSum = 0;
// 计算最小、最大权重，总的权重和。
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
maxWeight = Math.max(maxWeight, weight); // Choose the maximum weight
minWeight = Math.min(minWeight, weight); // Choose the minimum weight
if (weight > 0) {
invokerToWeightMap.put(invokers.get(i), new IntegerWrapper(weight));
weightSum += weight;
}
}
// 获得 AtomicPositiveInteger 对象
AtomicPositiveInteger sequence = sequences.get(key);
if (sequence == null) {
sequences.putIfAbsent(key, new AtomicPositiveInteger());
sequence = sequences.get(key);
}
// 获得当前顺序号，并递增 + 1
int currentSequence = sequence.getAndIncrement();
// 权重不相等，顺序根据权重分配
if (maxWeight > 0 && minWeight < maxWeight) {
int mod = currentSequence % weightSum; // 剩余权重
for (int i = 0; i < maxWeight; i++) { // 循环最大权重
for (Map.Entry<Invoker<T>, IntegerWrapper> each : invokerToWeightMap.entrySet()) { // 循环 Invoker 集合
final Invoker<T> k = each.getKey();
final IntegerWrapper v = each.getValue();
// 剩余权重归 0 ，当前 Invoker 还有剩余权重，返回该 Invoker 对象
if (mod == 0 && v.getValue() > 0) {
return k;
}
// 若 Invoker 还有权重值，扣除它( value )和剩余权重( mod )。
if (v.getValue() > 0) {
v.decrement();
mod--;
}
}
}
}
// 权重相等，平均顺序获得
// Round robin
return invokers.get(currentSequence % length);
}
主要就是一致性hash算法要复杂一些，其它的实现还不算很难。Dubbo通过这些负载均衡算法实现了服务间调用的负载均衡。
Dubbo的负载均衡算法就介绍到这里了。
网友评论