前言
LoadBalance（負(fù)載均衡）的職責(zé)是將網(wǎng)絡(luò)請(qǐng)求或者其他形式的負(fù)載“均攤”到不同的服務(wù)節(jié)點(diǎn)上砌烁，從而避免服務(wù)集群中部分節(jié)點(diǎn)壓力過(guò)大盹沈、資源緊張贝椿，而另一部分節(jié)點(diǎn)比較空閑的情況。
通過(guò)合理的負(fù)載均衡算法，可以讓每個(gè)服務(wù)節(jié)點(diǎn)獲取到適合自己處理能力的負(fù)載辙诞，實(shí)現(xiàn)處理能力和流量的合理分配。常用的負(fù)載均衡可分為軟件負(fù)載均衡（比如轻抱，日常工作中使用的 Nginx）和硬件負(fù)載均衡（主要有 F5飞涂、Array、NetScaler 等祈搜，不過(guò)開發(fā)工程師在實(shí)踐中很少直接接觸到）较店。
常見的 RPC 框架中都有負(fù)載均衡的概念和相應(yīng)的實(shí)現(xiàn)，Dubbo 也不例外容燕。Dubbo 需要對(duì) Consumer 的調(diào)用請(qǐng)求進(jìn)行分配梁呈，避免少數(shù) Provider 節(jié)點(diǎn)負(fù)載過(guò)大，而剩余的其他 Provider 節(jié)點(diǎn)處于空閑的狀態(tài)蘸秘。因?yàn)楫?dāng) Provider 負(fù)載過(guò)大時(shí)官卡，就會(huì)導(dǎo)致一部分請(qǐng)求超時(shí)、丟失等一系列問(wèn)題發(fā)生醋虏，造成線上故障寻咒。
Dubbo 提供了 5 種負(fù)載均衡實(shí)現(xiàn)，分別是：
基于 Hash 一致性的 ConsistentHashLoadBalance
基于權(quán)重隨機(jī)算法的 RandomLoadBalance
基于最少活躍調(diào)用數(shù)算法的 LeastActiveLoadBalance
基于加權(quán)輪詢算法的 RoundRobinLoadBalance
基于最短響應(yīng)時(shí)間的 ShortestResponseLoadBalance
LoadBalance 接口
上述 Dubbo 提供的負(fù)載均衡實(shí)現(xiàn)颈嚼，都是 LoadBalance 接口的實(shí)現(xiàn)類毛秘，如下圖所示：
LoadBalance 是一個(gè)擴(kuò)展接口，默認(rèn)使用的擴(kuò)展實(shí)現(xiàn)是 RandomLoadBalance，其定義如下所示叫挟，其中的 @Adaptive 注解參數(shù)為 loadbalance艰匙，即動(dòng)態(tài)生成的適配器會(huì)按照 URL 中的 loadbalance 參數(shù)值選擇擴(kuò)展實(shí)現(xiàn)類。
@SPI(RandomLoadBalance.NAME)
public interface LoadBalance {
@Adaptive("loadbalance")
<T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException;
}
LoadBalance 接口中 select() 方法的核心功能是根據(jù)傳入的 URL 和 Invocation抹恳，以及自身的負(fù)載均衡算法旬薯，從 Invoker 集合中選擇一個(gè) Invoker 返回。
AbstractLoadBalance 抽象類并沒(méi)有真正實(shí)現(xiàn) select() 方法适秩，只是對(duì) Invoker 集合為空或是只包含一個(gè) Invoker 對(duì)象的特殊情況進(jìn)行了處理绊序，具體實(shí)現(xiàn)如下：
public abstract class AbstractLoadBalance implements LoadBalance {
@Override
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
if (CollectionUtils.isEmpty(invokers)) {
// Invoker集合為空，直接返回null
return null;
}
if (invokers.size() == 1) {
// Invoker集合只包含一個(gè)Invoker秽荞，則直接返回該Invoker對(duì)象
return invokers.get(0);
}
// Invoker集合包含多個(gè)Invoker對(duì)象時(shí)骤公，交給doSelect()方法處理，這是個(gè)抽象方法扬跋，留給子類具體實(shí)現(xiàn)
return doSelect(invokers, url, invocation);
}
}
另外阶捆，AbstractLoadBalance 還提供了一個(gè) getWeight() 方法，該方法用于計(jì)算 Provider 權(quán)重钦听，具體實(shí)現(xiàn)如下：
public abstract class AbstractLoadBalance implements LoadBalance {
int getWeight(Invoker<?> invoker, Invocation invocation) {
int weight;
URL url = invoker.getUrl();
// Multiple registry scenario, load balance among multiple registries.
if (REGISTRY_SERVICE_REFERENCE_PATH.equals(url.getServiceInterface())) {
// 如果是RegistryService接口的話洒试，直接獲取權(quán)重即可
weight = url.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY, DEFAULT_WEIGHT);
} else {
weight = url.getMethodParameter(invocation.getMethodName(), WEIGHT_KEY, DEFAULT_WEIGHT);
if (weight > 0) {
// 獲取服務(wù)提供者的啟動(dòng)時(shí)間戳
long timestamp = invoker.getUrl().getParameter(TIMESTAMP_KEY, 0L);
if (timestamp > 0L) {
// 計(jì)算Provider運(yùn)行時(shí)長(zhǎng)
long uptime = System.currentTimeMillis() - timestamp;
if (uptime < 0) {
return 1;
}
// 計(jì)算Provider預(yù)熱時(shí)長(zhǎng)
int warmup = invoker.getUrl().getParameter(WARMUP_KEY, DEFAULT_WARMUP);
// 如果Provider運(yùn)行時(shí)間小于預(yù)熱時(shí)間，則該P(yáng)rovider節(jié)點(diǎn)可能還在預(yù)熱階段朴上，
// 需要重新計(jì)算服務(wù)權(quán)重(降低其權(quán)重)
if (uptime > 0 && uptime < warmup) {
weight = calculateWarmupWeight((int)uptime, warmup, weight);
}
}
}
}
return Math.max(weight, 0);
}
}
calculateWarmupWeight() 方法的目的是對(duì)還在預(yù)熱狀態(tài)的 Provider 節(jié)點(diǎn)進(jìn)行降權(quán)垒棋，避免 Provider 一啟動(dòng)就有大量請(qǐng)求涌進(jìn)來(lái)。服務(wù)預(yù)熱是一個(gè)優(yōu)化手段痪宰，這是由 JVM 本身的一些特性決定的叼架，例如，JIT 等方面的優(yōu)化衣撬，我們一般會(huì)在服務(wù)啟動(dòng)之后乖订，讓其在小流量狀態(tài)下運(yùn)行一段時(shí)間，然后再逐步放大流量具练。
public abstract class AbstractLoadBalance implements LoadBalance {
static int calculateWarmupWeight(int uptime, int warmup, int weight) {
// 計(jì)算權(quán)重乍构，隨著服務(wù)運(yùn)行時(shí)間uptime增大，權(quán)重ww的值會(huì)慢慢接近配置值weight
int ww = (int) ( uptime / ((float) warmup / weight));
return ww < 1 ? 1 : (Math.min(ww, weight));
}
}
了解了 LoadBalance 接口的定義以及 AbstractLoadBalance 提供的公共能力之后扛点，下面我們開始逐個(gè)介紹 LoadBalance 接口的具體實(shí)現(xiàn)哥遮。
ConsistentHashLoadBalance
ConsistentHashLoadBalance 底層使用一致性 Hash 算法實(shí)現(xiàn)負(fù)載均衡。為了更好地理解這部分內(nèi)容占键，先來(lái)簡(jiǎn)單介紹一下一致性 Hash 算法相關(guān)的知識(shí)點(diǎn)垄琐。
1膛腐、一致性 Hash 簡(jiǎn)析
一致性 Hash 負(fù)載均衡可以讓參數(shù)相同的請(qǐng)求每次都路由到相同的服務(wù)節(jié)點(diǎn)上，這種負(fù)載均衡策略可以在某些 Provider 節(jié)點(diǎn)下線的時(shí)候，讓這些節(jié)點(diǎn)上的流量平攤到其他 Provider 上玲销，不會(huì)引起流量的劇烈波動(dòng)。
下面我們通過(guò)一個(gè)示例，簡(jiǎn)單介紹一致性 Hash 算法的原理。
假設(shè)現(xiàn)在有 1钥庇、2、3 三個(gè) Provider 節(jié)點(diǎn)對(duì)外提供服務(wù)咖摹，有 100 個(gè)請(qǐng)求同時(shí)到達(dá)评姨，如果想讓請(qǐng)求盡可能均勻地分布到這三個(gè) Provider 節(jié)點(diǎn)上，我們可能想到的最簡(jiǎn)單的方法就是 Hash 取模萤晴，即 hash(請(qǐng)求參數(shù)) % 3吐句。如果參與 Hash 計(jì)算的是請(qǐng)求的全部參數(shù)，那么參數(shù)相同的請(qǐng)求將會(huì)落到同一個(gè) Provider 節(jié)點(diǎn)上店读。不過(guò)此時(shí)如果突然有一個(gè) Provider 節(jié)點(diǎn)出現(xiàn)宕機(jī)的情況嗦枢，那我們就需要對(duì) 2 取模，即請(qǐng)求會(huì)重新分配到相應(yīng)的 Provider 之上屯断。在極端情況下文虏，甚至?xí)霈F(xiàn)所有請(qǐng)求的處理節(jié)點(diǎn)都發(fā)生了變化，這就會(huì)造成比較大的波動(dòng)殖演。
為了避免因一個(gè) Provider 節(jié)點(diǎn)宕機(jī)氧秘，而導(dǎo)致大量請(qǐng)求的處理節(jié)點(diǎn)發(fā)生變化的情況，我們可以考慮使用一致性 Hash 算法趴久。一致性 Hash 算法的原理也是取模算法丸相，與 Hash 取模的不同之處在于：Hash 取模是對(duì) Provider 節(jié)點(diǎn)數(shù)量取模，而一致性 Hash 算法是對(duì) 2^32 取模朋鞍。
一致性 Hash 算法需要同時(shí)對(duì) Provider 地址以及請(qǐng)求參數(shù)進(jìn)行取模：
hash(Provider地址) % 2^32
hash(請(qǐng)求參數(shù)) % 2^32
我們按順時(shí)針的方向已添，依次將請(qǐng)求分發(fā)到對(duì)應(yīng)的 Provider。這樣滥酥，當(dāng)某臺(tái) Provider 節(jié)點(diǎn)宕機(jī)或增加新的 Provider 節(jié)點(diǎn)時(shí)，只會(huì)影響這個(gè) Provider 節(jié)點(diǎn)對(duì)應(yīng)的請(qǐng)求畦幢。
在理想情況下坎吻，一致性 Hash 算法會(huì)將這三個(gè) Provider 節(jié)點(diǎn)均勻地分布到 Hash 環(huán)上，請(qǐng)求也可以均勻地分發(fā)給這三個(gè) Provider 節(jié)點(diǎn)宇葱。但在實(shí)際情況中瘦真，這三個(gè) Provider 節(jié)點(diǎn)地址取模之后的值，可能差距不大黍瞧，這樣會(huì)導(dǎo)致大量的請(qǐng)求落到一個(gè) Provider 節(jié)點(diǎn)上诸尽，如下圖所示：
這就出現(xiàn)了數(shù)據(jù)傾斜的問(wèn)題。所謂數(shù)據(jù)傾斜是指由于節(jié)點(diǎn)不夠分散印颤，導(dǎo)致大量請(qǐng)求落到了同一個(gè)節(jié)點(diǎn)上您机，而其他節(jié)點(diǎn)只會(huì)接收到少量請(qǐng)求的情況。
為了解決一致性 Hash 算法中出現(xiàn)的數(shù)據(jù)傾斜問(wèn)題，又演化出了 Hash 槽的概念际看。
Hash 槽解決數(shù)據(jù)傾斜的思路是：既然問(wèn)題是由 Provider 節(jié)點(diǎn)在 Hash 環(huán)上分布不均勻造成的咸产，那么可以虛擬出 n 組 P1、P2仲闽、P3 的 Provider 節(jié)點(diǎn) 脑溢，讓多組 Provider 節(jié)點(diǎn)相對(duì)均勻地分布在 Hash 環(huán)上。如下圖所示赖欣，相同陰影的節(jié)點(diǎn)均為同一個(gè) Provider 節(jié)點(diǎn)屑彻，比如 P1-1、P1-2……P1-99 表示的都是 P1 這個(gè) Provider 節(jié)點(diǎn)顶吮。引入 Provider 虛擬節(jié)點(diǎn)之后酱酬，讓 Provider 在圓環(huán)上分散開來(lái)，以避免數(shù)據(jù)傾斜問(wèn)題云矫。
2膳沽、ConsistentHashSelector 實(shí)現(xiàn)分析
了解了一致性 Hash 算法的基本原理之后，我們?cè)賮?lái)看一下 ConsistentHashLoadBalance 一致性 Hash 負(fù)載均衡的具體實(shí)現(xiàn)让禀。首先來(lái)看 doSelect() 方法的實(shí)現(xiàn)挑社，其中會(huì)根據(jù) ServiceKey 和 methodName 選擇一個(gè) ConsistentHashSelector 對(duì)象，核心算法都委托給 ConsistentHashSelector 對(duì)象完成巡揍。
public class ConsistentHashLoadBalance extends AbstractLoadBalance {
private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<String, ConsistentHashSelector<?>>();
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
// 獲取調(diào)用的方法名稱
String methodName = RpcUtils.getMethodName(invocation);
// 將ServiceKey和方法拼接起來(lái)痛阻，構(gòu)成一個(gè)key
String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
// 注意：這是為了在invokers列表發(fā)生變化時(shí)都會(huì)重新生成ConsistentHashSelector對(duì)象
int invokersHashCode = invokers.hashCode();
// 根據(jù)key獲取對(duì)應(yīng)的ConsistentHashSelector對(duì)象，
// selectors是一個(gè)ConcurrentMap<String, ConsistentHashSelector>集合
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
// 未查找到ConsistentHashSelector對(duì)象腮敌，則進(jìn)行創(chuàng)建
if (selector == null || selector.identityHashCode != invokersHashCode) {
selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, invokersHashCode));
selector = (ConsistentHashSelector<T>) selectors.get(key);
}
// 通過(guò)ConsistentHashSelector對(duì)象選擇一個(gè)Invoker對(duì)象
return selector.select(invocation);
}
}
下面我們來(lái)看 ConsistentHashSelector阱当，其核心字段如下所示：
virtualInvokers（TreeMap<Long, Invoker<T>> 類型）：用于記錄虛擬 Invoker 對(duì)象的 Hash 環(huán)。這里使用 TreeMap 實(shí)現(xiàn) Hash 環(huán)糜工，并將虛擬的 Invoker 對(duì)象分布在 Hash 環(huán)上弊添。
replicaNumber（int 類型）**：虛擬 Invoker 個(gè)數(shù)。
identityHashCode（int 類型）**：Invoker 集合的 HashCode 值捌木。
argumentIndex（int[] 類型）**：需要參與 Hash 計(jì)算的參數(shù)索引油坝。例如，argumentIndex = [0, 1, 2] 時(shí)刨裆，表示調(diào)用的目標(biāo)方法的前三個(gè)參數(shù)要參與 Hash 計(jì)算澈圈。
接下來(lái)看 ConsistentHashSelector 的構(gòu)造方法，其中的主要任務(wù)是：
構(gòu)建 Hash 槽帆啃；
確認(rèn)參與一致性 Hash 計(jì)算的參數(shù)瞬女，默認(rèn)是第一個(gè)參數(shù)。
這些操作的目的就是為了讓 Invoker 盡可能均勻地分布在 Hash 環(huán)上努潘，具體實(shí)現(xiàn)如下：
public class ConsistentHashLoadBalance extends AbstractLoadBalance {
private static final class ConsistentHashSelector<T> {
private final TreeMap<Long, Invoker<T>> virtualInvokers;
private final int replicaNumber;
private final int identityHashCode;
private final int[] argumentIndex;
ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
// 初始化virtualInvokers字段诽偷，也就是虛擬Hash槽
this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
// 記錄Invoker集合的hashCode坤学，用該hashCode值來(lái)判斷Provider列表是否發(fā)生了變化
this.identityHashCode = identityHashCode;
URL url = invokers.get(0).getUrl();
// 從hash.nodes參數(shù)中獲取虛擬節(jié)點(diǎn)的個(gè)數(shù)
this.replicaNumber = url.getMethodParameter(methodName, HASH_NODES, 160);
// 獲取參與Hash計(jì)算的參數(shù)下標(biāo)值，默認(rèn)對(duì)第一個(gè)參數(shù)進(jìn)行Hash運(yùn)算
String[] index = 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]);
}
// 構(gòu)建虛擬Hash槽渤刃，默認(rèn)replicaNumber=160拥峦，相當(dāng)于在Hash槽上放160個(gè)槽位
// 外層輪詢40次，內(nèi)層輪詢4次卖子，共40*4=160次略号，也就是同一節(jié)點(diǎn)虛擬出160個(gè)槽位
for (Invoker<T> invoker : invokers) {
String address = invoker.getUrl().getAddress();
for (int i = 0; i < replicaNumber / 4; i++) {
// 對(duì)address + i進(jìn)行md5運(yùn)算，得到一個(gè)長(zhǎng)度為16的字節(jié)數(shù)組
byte[] digest = Bytes.getMD5(address + i);
// 對(duì)digest部分字節(jié)進(jìn)行4次Hash運(yùn)算洋闽，得到4個(gè)不同的long型正整數(shù)
for (int h = 0; h < 4; h++) {
// h = 0 時(shí)玄柠，取 digest 中下標(biāo)為 0~3 的 4 個(gè)字節(jié)進(jìn)行位運(yùn)算
// h = 1 時(shí)，取 digest 中下標(biāo)為 4~7 的 4 個(gè)字節(jié)進(jìn)行位運(yùn)算
// h = 2 和 h = 3時(shí)诫舅，過(guò)程同上
long m = hash(digest, h);
virtualInvokers.put(m, invoker);
}
}
}
}
}
}
最后羽利，請(qǐng)求會(huì)通過(guò) ConsistentHashSelector.select() 方法選擇合適的 Invoker 對(duì)象，其中會(huì)先對(duì)請(qǐng)求參數(shù)進(jìn)行 md5 以及 Hash 運(yùn)算刊懈，得到一個(gè) Hash 值这弧，然后再通過(guò)這個(gè) Hash 值到 TreeMap 中查找目標(biāo) Invoker。具體實(shí)現(xiàn)如下：
public class ConsistentHashLoadBalance extends AbstractLoadBalance {
private static final class ConsistentHashSelector<T> {
private final TreeMap<Long, Invoker<T>> virtualInvokers;
public Invoker<T> select(Invocation invocation) {
// 將參與一致性Hash的參數(shù)拼接到一起
String key = toKey(invocation.getArguments());
// 計(jì)算key的Hash值
byte[] digest = Bytes.getMD5(key);
// 匹配Invoker對(duì)象
return selectForKey(hash(digest, 0));
}
private Invoker<T> selectForKey(long hash) {
// 從virtualInvokers集合（TreeMap是按照Key排序的）中查找第一個(gè)節(jié)點(diǎn)值大于或等于傳入Hash值的Invoker對(duì)象
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash);
if (entry == null) {
// 如果Hash值大于Hash環(huán)中的所有Invoker虚汛，則回到Hash環(huán)的開頭匾浪，返回第一個(gè)Invoker對(duì)象
entry = virtualInvokers.firstEntry();
}
return entry.getValue();
}
}
}
RandomLoadBalance
RandomLoadBalance 使用的負(fù)載均衡算法是加權(quán)隨機(jī)算法。RandomLoadBalance 是一個(gè)簡(jiǎn)單卷哩、高效的負(fù)載均衡實(shí)現(xiàn)蛋辈，它也是 Dubbo 默認(rèn)使用的 LoadBalance 實(shí)現(xiàn)。
這里我們通過(guò)一個(gè)示例來(lái)說(shuō)明加權(quán)隨機(jī)算法的核心思想将谊。假設(shè)我們有三個(gè) Provider 節(jié)點(diǎn) A冷溶、B、C尊浓，它們對(duì)應(yīng)的權(quán)重分別為 5逞频、2、3眠砾，權(quán)重總和為 10÷簿ⅲ現(xiàn)在把這些權(quán)重值放到一維坐標(biāo)軸上，[0, 5) 區(qū)間屬于節(jié)點(diǎn) A褒颈，[5, 7) 區(qū)間屬于節(jié)點(diǎn) B，[7, 10) 區(qū)間屬于節(jié)點(diǎn) C励堡，如下圖所示：
下面我們通過(guò)隨機(jī)數(shù)生成器在 [0, 10) 這個(gè)范圍內(nèi)生成一個(gè)隨機(jī)數(shù)谷丸，然后計(jì)算這個(gè)隨機(jī)數(shù)會(huì)落到哪個(gè)區(qū)間中。例如应结，隨機(jī)生成 4刨疼，就會(huì)落到 Provider A 對(duì)應(yīng)的區(qū)間中泉唁，此時(shí) RandomLoadBalance 就會(huì)返回 Provider A 這個(gè)節(jié)點(diǎn)。
接下來(lái)我們?cè)賮?lái)看 RandomLoadBalance 中 doSelect() 方法的實(shí)現(xiàn)揩慕，其核心邏輯分為三個(gè)關(guān)鍵點(diǎn)：
計(jì)算每個(gè) Invoker 對(duì)應(yīng)的權(quán)重值以及總權(quán)重值亭畜；
當(dāng)各個(gè) Invoker 權(quán)重值不相等時(shí)，計(jì)算隨機(jī)數(shù)應(yīng)該落在哪個(gè) Invoker 區(qū)間中迎卤，返回對(duì)應(yīng)的 Invoker 對(duì)象拴鸵；
當(dāng)各個(gè) Invoker 權(quán)重值相同時(shí)，隨機(jī)返回一個(gè) Invoker 即可蜗搔。
RandomLoadBalance 經(jīng)過(guò)多次請(qǐng)求后劲藐，能夠?qū)⒄{(diào)用請(qǐng)求按照權(quán)重值均勻地分配到各個(gè) Provider 節(jié)點(diǎn)上。下面是 RandomLoadBalance 的核心實(shí)現(xiàn)：
public class RandomLoadBalance extends AbstractLoadBalance {
public static final String NAME = "random";
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
// Number of invokers
int length = invokers.size();
// Every invoker has the same weight?
boolean sameWeight = true;
// 計(jì)算每個(gè)Invoker對(duì)象對(duì)應(yīng)的權(quán)重樟凄，并填充到weights[]數(shù)組中
int[] weights = new int[length];
// totalWeight用于記錄總權(quán)重值
int totalWeight = 0;
for (int i = 0; i < length; i++) {
// 計(jì)算每個(gè)Invoker的權(quán)重聘芜，以及總權(quán)重totalWeight
int weight = getWeight(invokers.get(i), invocation);
// Sum
totalWeight += weight;
// save for later use
weights[i] = totalWeight;
// 檢測(cè)每個(gè)Provider的權(quán)重是否相同
if (sameWeight && totalWeight != weight * (i + 1)) {
sameWeight = false;
}
}
// 各個(gè)Invoker權(quán)重值不相等時(shí)，計(jì)算隨機(jī)數(shù)落在哪個(gè)區(qū)間上
if (totalWeight > 0 && !sameWeight) {
// 隨機(jī)獲取一個(gè)[0, totalWeight) 區(qū)間內(nèi)的數(shù)字
int offset = ThreadLocalRandom.current().nextInt(totalWeight);
// 循環(huán)讓offset數(shù)減去Invoker的權(quán)重值缝龄，當(dāng)offset小于0時(shí)汰现，返回相應(yīng)的Invoker
for (int i = 0; i < length; i++) {
if (offset < weights[i]) {
return invokers.get(i);
}
}
}
// 各個(gè)Invoker權(quán)重值相同時(shí)，隨機(jī)返回一個(gè)Invoker即可
return invokers.get(ThreadLocalRandom.current().nextInt(length));
}
}
LeastActiveLoadBalance
LeastActiveLoadBalance 使用的是最小活躍數(shù)負(fù)載均衡算法叔壤。它認(rèn)為當(dāng)前活躍請(qǐng)求數(shù)越小的 Provider 節(jié)點(diǎn)瞎饲，剩余的處理能力越多，處理請(qǐng)求的效率也就越高百新，那么該 Provider 在單位時(shí)間內(nèi)就可以處理更多的請(qǐng)求企软，所以我們應(yīng)該優(yōu)先將請(qǐng)求分配給該 Provider 節(jié)點(diǎn)。
LeastActiveLoadBalance 需要配合 ActiveLimitFilter 使用饭望，ActiveLimitFilter 會(huì)記錄每個(gè)接口方法的活躍請(qǐng)求數(shù)仗哨，在 LeastActiveLoadBalance 進(jìn)行負(fù)載均衡時(shí)，只會(huì)從活躍請(qǐng)求數(shù)最少的 Invoker 集合里挑選 Invoker铅辞。
在 LeastActiveLoadBalance 的實(shí)現(xiàn)中厌漂，首先會(huì)選出所有活躍請(qǐng)求數(shù)最小的 Invoker 對(duì)象，之后的邏輯與 RandomLoadBalance 完全一樣斟珊，即按照這些 Invoker 對(duì)象的權(quán)重挑選最終的 Invoker 對(duì)象苇倡。下面是 LeastActiveLoadBalance.doSelect() 方法的具體實(shí)現(xiàn)：
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) {
// 初始化Invoker數(shù)量
int length = invokers.size();
// 記錄最小的活躍請(qǐng)求數(shù)
int leastActive = -1;
// 記錄活躍請(qǐng)求數(shù)最小的Invoker集合的個(gè)數(shù)
int leastCount = 0;
// 記錄活躍請(qǐng)求數(shù)最小的Invoker在invokers數(shù)組中的下標(biāo)位置
int[] leastIndexes = new int[length];
// 記錄活躍請(qǐng)求數(shù)最小的Invoker集合中，每個(gè)Invoker的權(quán)重值
int[] weights = new int[length];
// 記錄活躍請(qǐng)求數(shù)最小的Invoker集合中囤踩，所有Invoker的權(quán)重值之和
int totalWeight = 0;
// 記錄活躍請(qǐng)求數(shù)最小的Invoker集合中旨椒，第一個(gè)Invoker的權(quán)重值
int firstWeight = 0;
// 活躍請(qǐng)求數(shù)最小的集合中，所有Invoker的權(quán)重值是否相同
boolean sameWeight = true;
// 遍歷所有Invoker堵漱，獲取活躍請(qǐng)求數(shù)最小的Invoker集合
for (int i = 0; i < length; i++) {
Invoker<T> invoker = invokers.get(i);
// 獲取該Invoker的活躍請(qǐng)求數(shù)
int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
// 獲取該Invoker的權(quán)重
int afterWarmup = getWeight(invoker, invocation);
// save for later use
weights[i] = afterWarmup;
// 比較活躍請(qǐng)求數(shù)
if (leastActive == -1 || active < leastActive) {
// 當(dāng)前的Invoker是第一個(gè)活躍請(qǐng)求數(shù)最小的Invoker综慎，則記錄如下信息
// 重新記錄最小的活躍請(qǐng)求數(shù)
leastActive = active;
// 重新記錄活躍請(qǐng)求數(shù)最小的Invoker集合個(gè)數(shù)
leastCount = 1;
// 重新記錄Invoker
leastIndexes[0] = i;
// 重新記錄總權(quán)重值
totalWeight = afterWarmup;
// 該Invoker作為第一個(gè)Invoker，記錄其權(quán)重值
firstWeight = afterWarmup;
// 重新記錄是否權(quán)重值相等
sameWeight = true;
// If current invoker's active value equals with leaseActive, then accumulating.
} else if (active == leastActive) {
// 當(dāng)前Invoker屬于活躍請(qǐng)求數(shù)最小的Invoker集合
// 記錄該Invoker的下標(biāo)
leastIndexes[leastCount++] = i;
// 更新總權(quán)重
totalWeight += afterWarmup;
// If every invoker has the same weight?
if (sameWeight && afterWarmup != firstWeight) {
// 更新權(quán)重值是否相等
sameWeight = false;
}
}
}
// 如果只有一個(gè)活躍請(qǐng)求數(shù)最小的Invoker對(duì)象勤庐，直接返回即可
if (leastCount == 1) {
// If we got exactly one invoker having the least active value, return this invoker directly.
return invokers.get(leastIndexes[0]);
}
// 下面按照RandomLoadBalance的邏輯示惊，從活躍請(qǐng)求數(shù)最小的Invoker集合中好港，隨機(jī)選擇一個(gè)Invoker對(duì)象返回
if (!sameWeight && totalWeight > 0) {
// If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on
// totalWeight.
int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
// Return a invoker based on the random value.
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexes[i];
offsetWeight -= weights[leastIndex];
if (offsetWeight < 0) {
return invokers.get(leastIndex);
}
}
}
// If all invokers have the same weight value or totalWeight=0, return evenly.
return invokers.get(leastIndexes[ThreadLocalRandom.current().nextInt(leastCount)]);
}
}
ActiveLimitFilter 以及底層的 RpcStatus 記錄活躍請(qǐng)求數(shù)的具體原理。
RoundRobinLoadBalance
RoundRobinLoadBalance 實(shí)現(xiàn)的是加權(quán)輪詢負(fù)載均衡算法米罚。
輪詢指的是將請(qǐng)求輪流分配給每個(gè) Provider钧汹。例如，有 A录择、B拔莱、C 三個(gè) Provider 節(jié)點(diǎn)，按照普通輪詢的方式糊肠，我們會(huì)將第一個(gè)請(qǐng)求分配給 Provider A辨宠，將第二個(gè)請(qǐng)求分配給 Provider B，第三個(gè)請(qǐng)求分配給 Provider C货裹，第四個(gè)請(qǐng)求再次分配給 Provider A……如此循環(huán)往復(fù)嗤形。
輪詢是一種無(wú)狀態(tài)負(fù)載均衡算法，實(shí)現(xiàn)簡(jiǎn)單弧圆，適用于集群中所有 Provider 節(jié)點(diǎn)性能相近的場(chǎng)景赋兵。 但現(xiàn)實(shí)情況中就很難保證這一點(diǎn)了，因?yàn)楹苋菀壮霈F(xiàn)集群中性能最好和最差的 Provider 節(jié)點(diǎn)處理同樣流量的情況搔预，這就可能導(dǎo)致性能差的 Provider 節(jié)點(diǎn)各方面資源非常緊張霹期，甚至無(wú)法及時(shí)響應(yīng)了，但是性能好的 Provider 節(jié)點(diǎn)的各方面資源使用還較為空閑拯田。這時(shí)我們可以通過(guò)加權(quán)輪詢的方式历造，降低分配到性能較差的 Provider 節(jié)點(diǎn)的流量。
加權(quán)之后船庇，分配給每個(gè) Provider 節(jié)點(diǎn)的流量比會(huì)接近或等于它們的權(quán)重比吭产。例如，Provider 節(jié)點(diǎn) A鸭轮、B臣淤、C 權(quán)重比為 5:1:1，那么在 7 次請(qǐng)求中窃爷，節(jié)點(diǎn) A 將收到 5 次請(qǐng)求邑蒋，節(jié)點(diǎn) B 會(huì)收到 1 次請(qǐng)求，節(jié)點(diǎn) C 則會(huì)收到 1 次請(qǐng)求按厘。
在 Dubbo 2.6.4 版本及之前医吊，RoundRobinLoadBalance 的實(shí)現(xiàn)存在一些問(wèn)題，例如逮京，選擇 Invoker 的性能問(wèn)題遮咖、負(fù)載均衡時(shí)不夠平滑等。在 Dubbo 2.6.5 版本之后造虏，這些問(wèn)題都得到了修復(fù)御吞，所以這里我們就來(lái)介紹最新的 RoundRobinLoadBalance 實(shí)現(xiàn)。
每個(gè) Provider 節(jié)點(diǎn)有兩個(gè)權(quán)重：一個(gè)權(quán)重是配置的 weight漓藕，該值在負(fù)載均衡的過(guò)程中不會(huì)變化陶珠；另一個(gè)權(quán)重是 currentWeight，該值會(huì)在負(fù)載均衡的過(guò)程中動(dòng)態(tài)調(diào)整享钞，初始值為 0揍诽。
當(dāng)有新的請(qǐng)求進(jìn)來(lái)時(shí)，RoundRobinLoadBalance 會(huì)遍歷 Invoker 列表栗竖，并用對(duì)應(yīng)的 currentWeight 加上其配置的權(quán)重暑脆。遍歷完成后，再找到最大的 currentWeight狐肢，將其減去權(quán)重總和添吗，然后返回相應(yīng)的 Invoker 對(duì)象。
下面我們通過(guò)一個(gè)示例說(shuō)明 RoundRobinLoadBalance 的執(zhí)行流程份名，這里我們依舊假設(shè) A碟联、B、C 三個(gè)節(jié)點(diǎn)的權(quán)重比例為 5:1:1僵腺。
1鲤孵、處理第一個(gè)請(qǐng)求，currentWeight 數(shù)組中的權(quán)重與配置的 weight 相加辰如，即從 [0, 0, 0] 變?yōu)?[5, 1, 1]普监。接下來(lái)，從中選擇權(quán)重最大的 Invoker 作為結(jié)果琉兜，即節(jié)點(diǎn) A凯正。最后，將節(jié)點(diǎn) A 的 currentWeight 值減去 totalWeight 值呕童，最終得到 currentWeight 數(shù)組為 [-2, 1, 1]漆际。
2、處理第二個(gè)請(qǐng)求夺饲，currentWeight 數(shù)組中的權(quán)重與配置的 weight 相加奸汇，即從 [-2, 1, 1] 變?yōu)?[3, 2, 2]。接下來(lái)往声，從中選擇權(quán)重最大的 Invoker 作為結(jié)果擂找，即節(jié)點(diǎn) A。最后浩销，將節(jié)點(diǎn) A 的 currentWeight 值減去 totalWeight 值贯涎，最終得到 currentWeight 數(shù)組為 [-4, 2, 2]。
3慢洋、處理第三個(gè)請(qǐng)求塘雳，currentWeight 數(shù)組中的權(quán)重與配置的 weight 相加陆盘，即從 [-4, 2, 2] 變?yōu)?[1, 3, 3]。接下來(lái)败明，從中選擇權(quán)重最大的 Invoker 作為結(jié)果隘马，即節(jié)點(diǎn) B。最后妻顶，將節(jié)點(diǎn) B 的 currentWeight 值減去 totalWeight 值酸员，最終得到 currentWeight 數(shù)組為 [1, -4, 3]。
4讳嘱、處理第四個(gè)請(qǐng)求幔嗦，currentWeight 數(shù)組中的權(quán)重與配置的 weight 相加，即從 [1, -4, 3] 變?yōu)?[6, -3, 4]沥潭。接下來(lái)邀泉，從中選擇權(quán)重最大的 Invoker 作為結(jié)果，即節(jié)點(diǎn) A叛氨。最后呼渣，將節(jié)點(diǎn) A 的 currentWeight 值減去 totalWeight 值，最終得到 currentWeight 數(shù)組為 [-1, -3, 4]寞埠。
5屁置、處理第五個(gè)請(qǐng)求，currentWeight 數(shù)組中的權(quán)重與配置的 weight 相加仁连，即從 [-1, -3, 4] 變?yōu)?[4, -2, 5]蓝角。接下來(lái)，從中選擇權(quán)重最大的 Invoker 作為結(jié)果饭冬，即節(jié)點(diǎn) C使鹅。最后，將節(jié)點(diǎn) C 的 currentWeight 值減去 totalWeight 值昌抠，最終得到 currentWeight 數(shù)組為 [4, -2, -2]患朱。
6、處理第六個(gè)請(qǐng)求炊苫，currentWeight 數(shù)組中的權(quán)重與配置的 weight 相加裁厅，即從 [4, -2, -2] 變?yōu)?[9, -1, -1]。接下來(lái)侨艾，從中選擇權(quán)重最大的 Invoker 作為結(jié)果执虹，即節(jié)點(diǎn) A。最后唠梨，將節(jié)點(diǎn) A 的 currentWeight 值減去 totalWeight 值袋励，最終得到 currentWeight 數(shù)組為 [2, -1, -1]。
7、處理第七個(gè)請(qǐng)求茬故，currentWeight 數(shù)組中的權(quán)重與配置的 weight 相加盖灸，即從 [2, -1, -1] 變?yōu)?[7, 0, 0]。接下來(lái)均牢，從中選擇權(quán)重最大的 Invoker 作為結(jié)果糠雨，即節(jié)點(diǎn) A。最后徘跪，將節(jié)點(diǎn) A 的 currentWeight 值減去 totalWeight 值，最終得到 currentWeight 數(shù)組為 [0, 0, 0]琅攘。
到此為止垮庐，一個(gè)輪詢的周期就結(jié)束了。
而在 Dubbo 2.6.4 版本中坞琴，上面示例的一次輪詢結(jié)果是 [A, A, A, A, A, B, C]哨查，也就是說(shuō)前 5 個(gè)請(qǐng)求會(huì)全部都落到 A 這個(gè)節(jié)點(diǎn)上。這將會(huì)使節(jié)點(diǎn) A 在短時(shí)間內(nèi)接收大量的請(qǐng)求剧辐，壓力陡增寒亥，而節(jié)點(diǎn) B 和節(jié)點(diǎn) C 此時(shí)沒(méi)有收到任何請(qǐng)求，處于完全空閑的狀態(tài)荧关，這種“瞬間分配不平衡”的情況也就是前面提到的“不平滑問(wèn)題”溉奕。
在 RoundRobinLoadBalance 中，為每個(gè) Invoker 對(duì)象創(chuàng)建了一個(gè)對(duì)應(yīng)的 WeightedRoundRobin 對(duì)象忍啤，用來(lái)記錄配置的權(quán)重（weight 字段）以及隨每次負(fù)載均衡算法執(zhí)行變化的 current 權(quán)重（current 字段）加勤。
了解了 WeightedRoundRobin 這個(gè)內(nèi)部類后，我們?cè)賮?lái)看 RoundRobinLoadBalance.doSelect() 方法的具體實(shí)現(xiàn)：
public class RoundRobinLoadBalance extends AbstractLoadBalance {
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
// 獲取整個(gè)Invoker列表對(duì)應(yīng)的WeightedRoundRobin映射表同波，如果為空鳄梅，則創(chuàng)建一個(gè)新的WeightedRoundRobin映射表
ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.computeIfAbsent(key, k -> new ConcurrentHashMap<>());
int totalWeight = 0;
long maxCurrent = Long.MIN_VALUE;
// 獲取當(dāng)前時(shí)間
long now = System.currentTimeMillis();
Invoker<T> selectedInvoker = null;
WeightedRoundRobin selectedWRR = null;
for (Invoker<T> invoker : invokers) {
String identifyString = invoker.getUrl().toIdentityString();
int weight = getWeight(invoker, invocation);
// 檢測(cè)當(dāng)前Invoker是否有相應(yīng)的WeightedRoundRobin對(duì)象，沒(méi)有則進(jìn)行創(chuàng)建
WeightedRoundRobin weightedRoundRobin = map.computeIfAbsent(identifyString, k -> {
WeightedRoundRobin wrr = new WeightedRoundRobin();
wrr.setWeight(weight);
return wrr;
});
// 檢測(cè)Invoker權(quán)重是否發(fā)生了變化未檩，若發(fā)生變化戴尸，則更新WeightedRoundRobin的weight字段
if (weight != weightedRoundRobin.getWeight()) {
//weight changed
weightedRoundRobin.setWeight(weight);
}
// 讓currentWeight加上配置的Weight
long cur = weightedRoundRobin.increaseCurrent();
// 設(shè)置lastUpdate字段
weightedRoundRobin.setLastUpdate(now);
// 尋找具有最大currentWeight的Invoker，以及Invoker對(duì)應(yīng)的WeightedRoundRobin
if (cur > maxCurrent) {
maxCurrent = cur;
selectedInvoker = invoker;
selectedWRR = weightedRoundRobin;
}
// 計(jì)算權(quán)重總和
totalWeight += weight;
}
if (invokers.size() != map.size()) {
map.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
}
if (selectedInvoker != null) {
// 用currentWeight減去totalWeight
selectedWRR.sel(totalWeight);
// 返回選中的Invoker對(duì)象
return selectedInvoker;
}
// should not happen here
return invokers.get(0);
}
}
ShortestResponseLoadBalance
ShortestResponseLoadBalance 是Dubbo 2.7 版本之后新增加的一個(gè) LoadBalance 實(shí)現(xiàn)類冤狡。它實(shí)現(xiàn)了最短響應(yīng)時(shí)間的負(fù)載均衡算法孙蒙，也就是從多個(gè) Provider 節(jié)點(diǎn)中選出調(diào)用成功的且響應(yīng)時(shí)間最短的 Provider 節(jié)點(diǎn)，不過(guò)滿足該條件的 Provider 節(jié)點(diǎn)可能有多個(gè)筒溃，所以還要再使用隨機(jī)算法進(jìn)行一次選擇马篮，得到最終要調(diào)用的 Provider 節(jié)點(diǎn)。
了解了 ShortestResponseLoadBalance 的核心原理之后怜奖，我們一起來(lái)看 ShortestResponseLoadBalance.doSelect() 方法的核心實(shí)現(xiàn)浑测，如下所示：
public class ShortestResponseLoadBalance extends AbstractLoadBalance {
public static final String NAME = "shortestresponse";
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
// 記錄Invoker集合的數(shù)量
int length = invokers.size();
// 用于記錄所有Invoker集合中最短響應(yīng)時(shí)間
long shortestResponse = Long.MAX_VALUE;
// 具有相同最短響應(yīng)時(shí)間的Invoker個(gè)數(shù)
int shortestCount = 0;
// 存放所有最短響應(yīng)時(shí)間的Invoker的下標(biāo)
int[] shortestIndexes = new int[length];
// 存儲(chǔ)每個(gè)Invoker的權(quán)重
int[] weights = new int[length];
// 存儲(chǔ)權(quán)重總和
int totalWeight = 0;
// 記錄第一個(gè)Invoker對(duì)象的權(quán)重
int firstWeight = 0;
// 最短響應(yīng)時(shí)間Invoker集合中的Invoker權(quán)重是否相同
boolean sameWeight = true;
// Filter out all the shortest response invokers
for (int i = 0; i < length; i++) {
Invoker<T> invoker = invokers.get(i);
RpcStatus rpcStatus = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName());
// 獲取調(diào)用成功的平均時(shí)間，具體計(jì)算方式是：調(diào)用成功的請(qǐng)求數(shù)總數(shù)對(duì)應(yīng)的總耗時(shí) / 調(diào)用成功的請(qǐng)求數(shù)總數(shù) = 成功調(diào)用的平均時(shí)間
// RpcStatus 的內(nèi)容在前面課時(shí)已經(jīng)介紹過(guò)了，這里不再重復(fù)
long succeededAverageElapsed = rpcStatus.getSucceededAverageElapsed();
// 獲取的是該P(yáng)rovider當(dāng)前的活躍請(qǐng)求數(shù)迁央，也就是當(dāng)前正在處理的請(qǐng)求數(shù)
int active = rpcStatus.getActive();
// 計(jì)算一個(gè)處理新請(qǐng)求的預(yù)估值掷匠，也就是如果當(dāng)前請(qǐng)求發(fā)給這個(gè)Provider，大概耗時(shí)多久處理完成
long estimateResponse = succeededAverageElapsed * active;
// 計(jì)算該Invoker的權(quán)重（主要是處理預(yù)熱）
int afterWarmup = getWeight(invoker, invocation);
weights[i] = afterWarmup;
// Same as LeastActiveLoadBalance
if (estimateResponse < shortestResponse) {
// 第一次找到Invoker集合中最短響應(yīng)耗時(shí)的Invoker對(duì)象岖圈，記錄其相關(guān)信息
shortestResponse = estimateResponse;
shortestCount = 1;
shortestIndexes[0] = i;
totalWeight = afterWarmup;
firstWeight = afterWarmup;
sameWeight = true;
} else if (estimateResponse == shortestResponse) {
// 出現(xiàn)多個(gè)耗時(shí)最短的Invoker對(duì)象
shortestIndexes[shortestCount++] = i;
totalWeight += afterWarmup;
if (sameWeight && i > 0
&& afterWarmup != firstWeight) {
sameWeight = false;
}
}
}
if (shortestCount == 1) {
return invokers.get(shortestIndexes[0]);
}
// 如果耗時(shí)最短的所有Invoker對(duì)象的權(quán)重不相同讹语，則通過(guò)加權(quán)隨機(jī)負(fù)載均衡的方式選擇一個(gè)Invoker返回
if (!sameWeight && totalWeight > 0) {
int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
for (int i = 0; i < shortestCount; i++) {
int shortestIndex = shortestIndexes[i];
offsetWeight -= weights[shortestIndex];
if (offsetWeight < 0) {
return invokers.get(shortestIndex);
}
}
}
// 如果耗時(shí)最短的所有Invoker對(duì)象的權(quán)重相同，則隨機(jī)返回一個(gè)
return invokers.get(shortestIndexes[ThreadLocalRandom.current().nextInt(shortestCount)]);
}
}
總結(jié)
本文重點(diǎn)介紹了 Dubbo Cluster 層中負(fù)載均衡相關(guān)的內(nèi)容：
1蜂科、首先我們介紹了 LoadBalance 接口的定義以及 AbstractLoadBalance 抽象類提供的公共能力顽决。
2、然后我們還詳細(xì)講解了 ConsistentHashLoadBalance 的核心實(shí)現(xiàn)导匣，其中還簡(jiǎn)單說(shuō)明了一致性 Hash 算法的基礎(chǔ)知識(shí)點(diǎn)才菠。
3、接著又分析了 RandomLoadBalance 的基本原理和核心實(shí)現(xiàn)贡定。
4赋访、接著又介紹了 LeastActiveLoadBalance 實(shí)現(xiàn)，它使用最小活躍數(shù)負(fù)載均衡算法缓待，選擇當(dāng)前請(qǐng)求最少的 Provider 節(jié)點(diǎn)處理最新的請(qǐng)求蚓耽。
5、接下來(lái)介紹了 RoundRobinLoadBalance 實(shí)現(xiàn)旋炒，它使用加權(quán)輪詢負(fù)載均衡算法步悠，彌補(bǔ)了單純的輪詢負(fù)載均衡算法導(dǎo)致的問(wèn)題，同時(shí)隨著 Dubbo 版本的升級(jí)国葬，也將其自身不夠平滑的問(wèn)題優(yōu)化掉了贤徒。
6、最后介紹了 ShortestResponseLoadBalance 實(shí)現(xiàn)汇四，它會(huì)從響應(yīng)時(shí)間最短的 Provider 節(jié)點(diǎn)中選擇一個(gè) Provider 節(jié)點(diǎn)來(lái)處理新請(qǐng)求接奈。
