Dubbo 原始碼分析 - 叢集容錯之 LoadBalance

@Override
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
if (invokers == null || invokers.isEmpty())
return null;
// 如果 invokers 列表中僅有一個 Invoker，直接返回即可，無需進行負載均衡
if (invokers.size() == 1)
return invokers.get(0);

// 呼叫 doSelect 方法進行負載均衡，該方法為抽象方法，由子類實現
return doSelect(invokers, url, invocation);
}

protected abstract <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation);

protected int getWeight(Invoker<?> invoker, Invocation invocation) {
// 從 url 中獲取 weight 配置值
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分鐘
int warmup = invoker.getUrl().getParameter(Constants.WARMUP_KEY, Constants.DEFAULT_WARMUP);
// 如果服務執行時間小於預熱時間，則重新計算服務權重，即降權
if (uptime > 0 && uptime < warmup) {
// 重新計算服務權重
weight = calculateWarmupWeight(uptime, warmup, weight);
}
}
}
return weight;
}

static int calculateWarmupWeight(int uptime, int warmup, int weight) {
// 計算權重，下面程式碼邏輯上形似於 (uptime / warmup) * weight。
// 隨著服務執行時間 uptime 增大，權重計算值 ww 會慢慢接近配置值 weight
int ww = (int) ((float) uptime / ((float) warmup / (float) weight));
return ww < 1 ? 1 : (ww > weight ? weight : ww);
}

public class RandomLoadBalance extends AbstractLoadBalance {

public static final String NAME = "random";

private final Random random = new Random();

@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
int length = invokers.size();
int totalWeight = 0;
boolean sameWeight = true;
// 下面這個迴圈有兩個作用，第一是計算總權重 totalWeight，
// 第二是檢測每個服務提供者的權重是否相同，若不相同，則將 sameWeight 置為 false
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
// 累加權重
totalWeight += weight;
// 檢測當前服務提供者的權重與上一個服務提供者的權重是否相同，
// 不相同的話，則將 sameWeight 置為 false。
if (sameWeight && i > 0
&& weight != getWeight(invokers.get(i - 1), invocation)) {
sameWeight = false;
}
}

// 下面的 if 分支主要用於獲取隨機數，並計算隨機數落在哪個區間上
if (totalWeight > 0 && !sameWeight) {
// 隨機獲取一個 [0, totalWeight) 之間的數字
int offset = random.nextInt(totalWeight);
// 迴圈讓 offset 數減去服務提供者權重值，當 offset 小於0時，返回相應的 Invoker。
// 還是用上面的例子進行說明，servers = [A, B, C]，weights = [5, 3, 2]，offset = 7。
// 第一次迴圈，offset - 5 = 2 > 0，說明 offset 肯定不會落在伺服器 A 對應的區間上。
// 第二次迴圈，offset - 3 = -1 < 0，表明 offset 落在伺服器 B 對應的區間上
for (int i = 0; i < length; i++) {
// 讓隨機值 offset 減去權重值
offset -= getWeight(invokers.get(i), invocation);
if (offset < 0) {
// 返回相應的 Invoker
return invokers.get(i);
}
}
}

// 如果所有服務提供者權重值相同，此時直接隨機返回一個即可
return invokers.get(random.nextInt(length));
}
}

public class LeastActiveLoadBalance extends AbstractLoadBalance {

public static final String NAME = "leastactive";

private final Random random = new Random();

@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
int length = invokers.size();
// 最小的活躍數
int leastActive = -1;
// 具有相同“最小活躍數”的服務者提供者（以下用 Invoker 代稱）數量
int leastCount = 0; 
// leastIndexs 用於記錄具有相同“最小活躍數”的 Invoker 在 invokers 列表中的下標資訊
int[] leastIndexs = new int[length];
int totalWeight = 0;
// 第一個最小活躍數的 Invoker 權重值，用於與其他具有相同最小活躍數的 Invoker 的權重進行對比，
// 以檢測是否所有具有相同最小活躍數的 Invoker 的權重均相等
int firstWeight = 0;
boolean sameWeight = true;

// 遍歷 invokers 列表
for (int i = 0; i < length; i++) {
Invoker<T> invoker = invokers.get(i);
// 獲取 Invoker 對應的活躍數
int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
// 獲取權重 - :star:️
int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);
// 發現更小的活躍數，重新開始
if (leastActive == -1 || active < leastActive) {
// 使用當前活躍數 active 更新最小活躍數 leastActive
leastActive = active;
// 更新 leastCount 為 1
leastCount = 1;
// 記錄當前下標值到 leastIndexs 中
leastIndexs[0] = i;
totalWeight = weight;
firstWeight = weight;
sameWeight = true;

// 當前 Invoker 的活躍數 active 與最小活躍數 leastActive 相同 
} else if (active == leastActive) {
// 在 leastIndexs 中記錄下當前 Invoker 在 invokers 集合中的下標
leastIndexs[leastCount++] = i;
// 累加權重
totalWeight += weight;
// 檢測當前 Invoker 的權重與 firstWeight 是否相等，
// 不相等則將 sameWeight 置為 false
if (sameWeight && i > 0
&& weight != firstWeight) {
sameWeight = false;
}
}
}

// 當只有一個 Invoker 具有最小活躍數，此時直接返回該 Invoker 即可
if (leastCount == 1) {
return invokers.get(leastIndexs[0]);
}

// 有多個 Invoker 具有相同的最小活躍數，但他們的權重不同
if (!sameWeight && totalWeight > 0) {
// 隨機獲取一個 [0, totalWeight) 之間的數字
int offsetWeight = random.nextInt(totalWeight);
// 迴圈讓隨機數減去具有最小活躍數的 Invoker 的權重值，
// 當 offset 小於等於0時，返回相應的 Invoker
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
// 獲取權重值，並讓隨機數減去權重值 - :star:️
offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
if (offsetWeight <= 0)
return invokers.get(leastIndex);
}
}
// 如果權重相同或權重為0時，隨機返回一個 Invoker
return invokers.get(leastIndexs[random.nextInt(leastCount)]);
}
}

int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);

offsetWeight -= getWeight(invokers.get(leastIndex), invocation);

// afterWarmup 等價於上面的 weight 變數，這樣命名是為了強調該變數經過 warmup 降權處理了
int afterWarmup = getWeight(invoker, invocation);

int offsetWeight = random.nextInt(totalWeight);
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
if (offsetWeight <= 0)// :x:
return invokers.get(leastIndex);
}

int offsetWeight = random.nextInt(totalWeight) + 1;

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) {
String methodName = RpcUtils.getMethodName(invocation);
String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;

// 獲取 invokers 原始的 hashcode
int identityHashCode = System.identityHashCode(invokers);
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
// 如果 invokers 是一個新的 List 物件，意味著服務提供者數量發生了變化，可能新增也可能減少了。
// 此時 selector.identityHashCode != identityHashCode 條件成立
if (selector == null || selector.identityHashCode != identityHashCode) {
// 建立新的 ConsistentHashSelector
selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
selector = (ConsistentHashSelector<T>) selectors.get(key);
}

// 呼叫 ConsistentHashSelector 的 select 方法選擇 Invoker
return selector.select(invocation);
}

private static final class ConsistentHashSelector<T> {...}
}

private static final class ConsistentHashSelector<T> {

// 使用 TreeMap 儲存 Invoker 虛擬節點
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) {
this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
this.identityHashCode = identityHashCode;
URL url = invokers.get(0).getUrl();
// 獲取虛擬節點數，預設為160
this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
// 獲取參與 hash 計算的引數下標值，預設對第一個引數進行 hash 運算
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]);
}
for (Invoker<T> invoker : invokers) {
String address = invoker.getUrl().getAddress();
for (int i = 0; i < replicaNumber / 4; i++) {
// 對 address + i 進行 md5 運算，得到一個長度為16的位元組陣列
byte[] digest = md5(address + i);
// 對 digest 部分位元組進行4次 hash 運算，得到四個不同的 long 型正整數
for (int h = 0; h < 4; h++) {
// h = 0 時，取 digest 中下標為 0 ~ 3 的4個位元組進行位運算
// h = 1 時，取 digest 中下標為 4 ~ 7 的4個位元組進行位運算
// h = 2, h = 3 時過程同上
long m = hash(digest, h);
// 將 hash 到 invoker 的對映關係儲存到 virtualInvokers 中，
// virtualInvokers 中的元素要有序，因此選用 TreeMap 作為儲存結構
virtualInvokers.put(m, invoker);
}
}
}
}
}

public Invoker<T> select(Invocation invocation) {
// 將引數轉為 key
String key = toKey(invocation.getArguments());
// 對引數 key 進行 md5 運算
byte[] digest = md5(key);
// 取 digest 陣列的前四個位元組進行 hash 運算，再將 hash 值傳給 selectForKey 方法，
// 尋找合適的 Invoker
return selectForKey(hash(digest, 0));
}

private Invoker<T> selectForKey(long hash) {
// 到 TreeMap 中查詢第一個節點值大於或等於當前 hash 的 Invoker
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
// 如果 hash 大於 Invoker 在圓環上最大的位置，此時 entry = null，
// 需要將 TreeMap 的頭結點賦值給 entry
if (entry == null) {
entry = virtualInvokers.firstEntry();
}

// 返回 Invoker
return entry.getValue();
}

public class RoundRobinLoadBalance extends AbstractLoadBalance {

public static final String NAME = "roundrobin";

private final ConcurrentMap<String, AtomicPositiveInteger> sequences = 
new ConcurrentHashMap<String, AtomicPositiveInteger>();

@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
// key = 全限定類名 + "." + 方法名，比如 com.xxx.DemoService.sayHello
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
int length = invokers.size();
// 最大權重
int maxWeight = 0;
// 最小權重
int minWeight = Integer.MAX_VALUE;
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);
minWeight = Math.min(minWeight, weight);
if (weight > 0) {
// 將 weight 封裝到 IntegerWrapper 中
invokerToWeightMap.put(invokers.get(i), new IntegerWrapper(weight));
// 累加權重
weightSum += weight;
}
}

// 查詢 key 對應的對應 AtomicPositiveInteger 例項，為空則建立。
// 這裡可以把 AtomicPositiveInteger 看成一個黑盒，大家只要知道
// AtomicPositiveInteger 用於記錄服務的呼叫編號即可。至於細節，
// 大家如果感興趣，可以自行分析
AtomicPositiveInteger sequence = sequences.get(key);
if (sequence == null) {
sequences.putIfAbsent(key, new AtomicPositiveInteger());
sequence = sequences.get(key);
}

// 獲取當前的呼叫編號
int currentSequence = sequence.getAndIncrement();
// 如果 最小權重 < 最大權重，表明服務提供者之間的權重是不相等的
if (maxWeight > 0 && minWeight < maxWeight) {
// 使用呼叫編號對權重總和進行取餘操作
int mod = currentSequence % weightSum;
// 進行 maxWeight 次遍歷
for (int i = 0; i < maxWeight; i++) {
// 遍歷 invokerToWeightMap
for (Map.Entry<Invoker<T>, IntegerWrapper> each : invokerToWeightMap.entrySet()) {
// 獲取 Invoker
final Invoker<T> k = each.getKey();
// 獲取權重包裝類 IntegerWrapper
final IntegerWrapper v = each.getValue();

// 如果 mod = 0，且權重大於0，此時返回相應的 Invoker
if (mod == 0 && v.getValue() > 0) {
return k;
}

// mod != 0，且權重大於0，此時對權重和 mod 分別進行自減操作
if (v.getValue() > 0) {
v.decrement();
mod--;
}
}
}
}

// 服務提供者之間的權重相等，此時通過輪詢選擇 Invoker
return invokers.get(currentSequence % length);
}

// IntegerWrapper 是一個 int 包裝類，主要包含了一個自減方法。
// 與 Integer 不同，Integer 是不可變類，而 IntegerWrapper 是可變類
private static final class IntegerWrapper {
private int value;

public void decrement() {
this.value--;
}

// 省略部分程式碼
}
}

public class RoundRobinLoadBalance extends AbstractLoadBalance {

public static final String NAME = "roundrobin";

private final ConcurrentMap<String, AtomicPositiveInteger> sequences = new ConcurrentHashMap<String, AtomicPositiveInteger>();

private final ConcurrentMap<String, AtomicPositiveInteger> indexSeqs = new ConcurrentHashMap<String, AtomicPositiveInteger>();

@Override
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();
int maxWeight = 0;
int minWeight = Integer.MAX_VALUE;
final List<Invoker<T>> invokerToWeightList = new ArrayList<>();

// 查詢最大和最小權重
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
maxWeight = Math.max(maxWeight, weight);
minWeight = Math.min(minWeight, weight);
if (weight > 0) {
invokerToWeightList.add(invokers.get(i));
}
}

// 獲取當前服務對應的呼叫序列物件 AtomicPositiveInteger
AtomicPositiveInteger sequence = sequences.get(key);
if (sequence == null) {
// 建立 AtomicPositiveInteger，預設值為0
sequences.putIfAbsent(key, new AtomicPositiveInteger());
sequence = sequences.get(key);
}

// 獲取下標序列物件 AtomicPositiveInteger
AtomicPositiveInteger indexSeq = indexSeqs.get(key);
if (indexSeq == null) {
// 建立 AtomicPositiveInteger，預設值為 -1
indexSeqs.putIfAbsent(key, new AtomicPositiveInteger(-1));
indexSeq = indexSeqs.get(key);
}

if (maxWeight > 0 && minWeight < maxWeight) {
length = invokerToWeightList.size();
while (true) {
int index = indexSeq.incrementAndGet() % length;
int currentWeight = sequence.get() % maxWeight;

// 每迴圈一輪（index = 0），重新計算 currentWeight
if (index == 0) {
currentWeight = sequence.incrementAndGet() % maxWeight;
}

// 檢測 Invoker 的權重是否大於 currentWeight，大於則返回
if (getWeight(invokerToWeightList.get(index), invocation) > currentWeight) {
return invokerToWeightList.get(index);
}
}
}

// 所有 Invoker 權重相等，此時進行普通的輪詢即可
return invokers.get(sequence.incrementAndGet() % length);
}
}

public class RoundRobinLoadBalance extends AbstractLoadBalance {
public static final String NAME = "roundrobin";

private static int RECYCLE_PERIOD = 60000;

protected static class WeightedRoundRobin {
// 服務提供者權重
private int weight;
// 當前權重
private AtomicLong current = new AtomicLong(0);
// 最後一次更新時間
private long lastUpdate;

public void setWeight(int weight) {
this.weight = weight;
// 初始情況下，current = 0
current.set(0);
}
public long increaseCurrent() {
// current = current + weight；
return current.addAndGet(weight);
}
public void sel(int total) {
// current = current - total;
current.addAndGet(-1 * total);
}
}

// 巢狀 Map 結構，儲存的資料結構示例如下：
// {
//"UserService.query": {
//"url1": WeightedRoundRobin@123, 
//"url2": WeightedRoundRobin@456, 
//},
//"UserService.update": {
//"url1": WeightedRoundRobin@123, 
//"url2": WeightedRoundRobin@456,
//}
// }
// 最外層為服務類名 + 方法名，第二層為 url 到 WeightedRoundRobin 的對映關係。
// 這裡我們可以將 url 看成是服務提供者的 id
private ConcurrentMap<String, ConcurrentMap<String, WeightedRoundRobin>> methodWeightMap = new ConcurrentHashMap<String, ConcurrentMap<String, WeightedRoundRobin>>();

// 原子更新鎖
private AtomicBoolean updateLock = new AtomicBoolean();

@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
// 獲取 url 到 WeightedRoundRobin 對映表，如果為空，則建立一個新的
ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.get(key);
if (map == null) {
methodWeightMap.putIfAbsent(key, new ConcurrentHashMap<String, WeightedRoundRobin>());
map = methodWeightMap.get(key);
}
int totalWeight = 0;
long maxCurrent = Long.MIN_VALUE;

// 獲取當前時間
long now = System.currentTimeMillis();
Invoker<T> selectedInvoker = null;
WeightedRoundRobin selectedWRR = null;

// 下面這個迴圈主要做了這樣幾件事情：
//1. 遍歷 Invoker 列表，檢測當前 Invoker 是否有
//對應的 WeightedRoundRobin，沒有則建立
//2. 檢測 Invoker 權重是否發生了變化，若變化了，
//則更新 WeightedRoundRobin 的 weight 欄位
//3. 讓 current 欄位加上自身權重，等價於 current += weight
//4. 設定 lastUpdate 欄位，即 lastUpdate = now
//5. 尋找具有最大 current 的 Invoker 以及 WeightedRoundRobin，
//暫存起來，留作後用
//6. 計算權重總和
for (Invoker<T> invoker : invokers) {
String identifyString = invoker.getUrl().toIdentityString();
WeightedRoundRobin weightedRoundRobin = map.get(identifyString);
int weight = getWeight(invoker, invocation);
if (weight < 0) {
weight = 0;
}

// 檢測當前 Invoker 是否有對應的 WeightedRoundRobin，沒有則建立
if (weightedRoundRobin == null) {
weightedRoundRobin = new WeightedRoundRobin();
// 設定 Invoker 權重
weightedRoundRobin.setWeight(weight);
// 儲存 url 唯一標識 identifyString 到 weightedRoundRobin 的對映關係
map.putIfAbsent(identifyString, weightedRoundRobin);
weightedRoundRobin = map.get(identifyString);
}
// Invoker 權重不等於 WeightedRoundRobin 中儲存的權重，說明權重變化了，此時進行更新
if (weight != weightedRoundRobin.getWeight()) {
weightedRoundRobin.setWeight(weight);
}

// 讓 current 加上自身權重，等價於 current += weight
long cur = weightedRoundRobin.increaseCurrent();
// 設定 lastUpdate，表示近期更新過
weightedRoundRobin.setLastUpdate(now);
// 找出最大的 current 
if (cur > maxCurrent) {
maxCurrent = cur;
// 將具有最大 current 權重的 Invoker 賦值給 selectedInvoker
selectedInvoker = invoker;
// 將 Invoker 對應的 weightedRoundRobin 賦值給 selectedWRR，留作後用
selectedWRR = weightedRoundRobin;
}

// 計算權重總和
totalWeight += weight;
}

// 對 <identifyString, WeightedRoundRobin> 進行檢查，過濾掉長時間未被更新的節點。
// 該節點可能掛了，invokers 中不包含該節點，所以該節點的 lastUpdate 長時間無法被更新。
// 若未更新時長超過閾值後，就會被移除掉，預設閾值為60秒。
if (!updateLock.get() && invokers.size() != map.size()) {
if (updateLock.compareAndSet(false, true)) {
try {
ConcurrentMap<String, WeightedRoundRobin> newMap = new ConcurrentHashMap<String, WeightedRoundRobin>();
// 拷貝
newMap.putAll(map);

// 遍歷修改，也就是移除過期記錄
Iterator<Entry<String, WeightedRoundRobin>> it = newMap.entrySet().iterator();
while (it.hasNext()) {
Entry<String, WeightedRoundRobin> item = it.next();
if (now - item.getValue().getLastUpdate() > RECYCLE_PERIOD) {
it.remove();
}
}

// 更新引用
methodWeightMap.put(key, newMap);
} finally {
updateLock.set(false);
}
}
}

if (selectedInvoker != null) {
// 讓 current 減去權重總和，等價於 current -= totalWeight
selectedWRR.sel(totalWeight);
// 返回具有最大 current 的 Invoker
return selectedInvoker;
}

// should not happen here
return invokers.get(0);
}
}