負載均衡演算法 - 基本實現

​ 最近在比賽一個項目 , 是給Dubbo寫一個負載均衡介面 , 其實dubbo已經實現了下麵四種, 所以他做的不是這個單面負載均衡, 需要做雙向負載均衡 , 負載均衡的權重取決於服務端,所以有些時候我們不知道如何計算權重, 權重受到很多因素影響 ,所以就需要動態考慮了.

​ Dubbo 提供了4種負載均衡實現，分別是基於權重隨機演算法的 RandomLoadBalance、基於最少活躍調用數演算法的 LeastActiveLoadBalance、基於 hash 一致性的 ConsistentHashLoadBalance，以及基於加權輪詢演算法的 RoundRobinLoadBalance。

1. 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次。

private <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {

    int len = invokers.size();
    int[] arr = new int[len];
    int count = 0;
    int totalWight = 0;
    for (Invoker<T> invoker : invokers) {
        int wight = invoker.getUrl().getParameter(org.apache.dubbo.common.Constants.WEIGHT_KEY, 1);
        arr[count++] = wight;
        totalWight += wight;
    }

    // 隨機偏移量
    int offset = ThreadLocalRandom.current().nextInt(totalWight);

    for (int i = 0; i < arr.length; i++) {

        // 比如 [2 , 3 , 5]  , offset=7 , 此時 offset-2=5 , offset-3=2 , offset-5=-3 ,此時當他為負數時,說明就在這個區間內, 我們是左閉右開[0,2) ,[2,5) ,[5,10)
        offset -= arr[i];

        // 此時已經小於0了, 說明在這個區間內
        if (offset < 0) {
            // 返回就行了
            return invokers.get(i);
        }
    }

    return ... 
}

2. LeastActiveLoadBalance

LeastActiveLoadBalance 翻譯過來是最小活躍數負載均衡。活躍調用數越小，表明該服務提供者效率越高，單位時間內可處理更多的請求。此時應優先將請求分配給該服務提供者。在具體實現中，每個服務提供者對應一個活躍數 active。初始情況下，所有服務提供者活躍數均為0。每收到一個請求，活躍數加1，完成請求後則將活躍數減1。在服務運行一段時間後，性能好的服務提供者處理請求的速度更快，因此活躍數下降的也越快，此時這樣的服務提供者能夠優先獲取到新的服務請求、這就是最小活躍數負載均衡演算法的基本思想。除了最小活躍數，LeastActiveLoadBalance 在實現上還引入了權重值。所以準確的來說，LeastActiveLoadBalance 是基於加權最小活躍數演算法實現的。舉個例子說明一下，在一個服務提供者集群中，有兩個性能優異的服務提供者。某一時刻它們的活躍數相同，此時 Dubbo 會根據它們的權重去分配請求，權重越大，獲取到新請求的概率就越大。如果兩個服務提供者權重相同，此時隨機選擇一個即可。

​ 這個需要我們去維護一個最小連接數的計算, 配合加權 ,當連接數相同的時候,選擇加權分最高的 ...

3. ConsistentHashLoadBalance

一致性 hash 演算法由麻省理工學院的 Karger 及其合作者於1997年提出的，演算法提出之初是用於大規模緩存系統的負載均衡。它的工作過程是這樣的，首先根據 ip 或者其他的信息為緩存節點生成一個 hash，並將這個 hash 投射到 [0, 232 - 1] 的圓環上。當有查詢或寫入請求時，則為緩存項的 key 生成一個 hash 值。然後查找第一個大於或等於該 hash 值的緩存節點，併到這個節點中查詢或寫入緩存項。如果當前節點掛了，則在下一次查詢或寫入緩存時，為緩存項查找另一個大於其 hash 值的緩存節點即可。

​ 這個主要是靠hash演算法 , 通過hash % 伺服器數量 = 伺服器索引

​ Java中可以使用這個 : int identityHashCode = System.identityHashCode(invokers);來獲取

4. RoundRobinLoadBalance

加權輪詢負載均衡的實現 RoundRobinLoadBalance , 我選擇的就是這種

這裡從最簡單的輪詢開始講起，所謂輪詢是指將請求輪流分配給每台伺服器。舉個例子，我們有三台伺服器 A、B、C。我們將第一個請求分配給伺服器 A，第二個請求分配給伺服器 B，第三個請求分配給伺服器 C，第四個請求再次分配給伺服器 A。這個過程就叫做輪詢。輪詢是一種無狀態負載均衡演算法，實現簡單，適用於每台伺服器性能相近的場景下。但現實情況下，我們並不能保證每台伺服器性能均相近。如果我們將等量的請求分配給性能較差的伺服器，這顯然是不合理的。

因此，這個時候我們需要對輪詢過程進行加權，以調控每台伺服器的負載。經過加權後，每台伺服器能夠得到的請求數比例，接近或等於他們的權重比。比如伺服器 A、B、C 權重比為 5:2:1。那麼在8次請求中，伺服器 A 將收到其中的5次請求，伺服器 B 會收到其中的2次請求，伺服器 C 則收到其中的1次請求。

下麵有個表格 , 預設權重是 [5,1,1]

此時 7 次中A節點被選中的次數是 5 , B 是1 ,C是1 ,所以符合我們的需求

計算方法如下 , 首先有三個變數 , 記錄了 currentWeight , effectiveWeight , totalWeight

 private class Node {
        private int currentWeight; // 當前權重
        private int effectiveWeight; // 有效權重,初始化的時候等於當前權重
        private int totalWeight; // 總權重
 }     

我們先看初始化 , 初始化時 ,計算權重

比如我們知道權重了 A : 5 , B : 1 , C : 1

初始化節點

A : new Node(5, 5, 7)
B : new Node(1, 1, 7)
C : new Node(1, 1, 7)
    
此時currentWeight的和是 : 7    

當第一次的時候 , A節點權重最大 ,此時 5-7=-2, A節點變成了 Node(-2, 5, 7)

A : new Node(-2, 5, 7)
B : new Node(1, 1, 7)
C : new Node(1, 1, 7)

此時currentWeight的和是 : 0

然後重新回歸, 回歸需要currentWeight= currentWeight+effectiveWeight

A : new Node(3, 5, 7)
B : new Node(2, 1, 7)
C : new Node(2, 1, 7)

此時currentWeight的和是 : 7 // 所以又回來了 .. .. 

怎樣做呢 ?

此時我們用一個 PriorityQueue<Pair<String, Node>> 維護所有節點的信息 , 同時使用 Pair<String, Node>維護單個節點

1. 初始化隊列
PriorityBlockingQueue<Pair<String, Node>> weightQueue = new PriorityBlockingQueue<>(3, (o1, o2) -> o2.getValue().getCurrentWeight() - o1.getValue().getCurrentWeight());


2. 遍歷放入權重
weightQueue.add(new Pair<>(key, new Node(currentWeight, effectiveWeight, totalWeight))); 

3. 當放入以後, 此時就可以拿到一個當前權重最大的節點 , 如果不想使用優先隊列, 可以自己實現一個大頂堆 ,很簡單的. 
    
// 獲取當前節點權重最大的 ,     
Pair<String, Node> hPair = weightQueue.take(); 
// 此時hPair節點的值應當是 5 - 7 = -2 
int afterCurrentWeight = value.getCurrentWeight() - value.getTotalWeight();
// 設置值
hNode.setCurrentWeight(afterCurrentWeight);

// 遍歷
for (Pair<String, Node> stringNodePair : weightQueue) {
    //獲取節點 
    Node node = stringNodePair.getValue();
    // 剩餘每個節點值 + 有效值 
    int after = node.getCurrentWeight() + node.getEffectiveWeight();
    
    // 設置節點值 
    node.setCurrentWeight(after);
}
// 由於我們拿出來的節點還沒有 重新計算, 還要計算
hNode.setCurrentWeight(value.getCurrentWeight() + value.getEffectiveWeight());
// 重新放入節點. ... ,重新排序
weightQueue.add(hPair);

其實自己維護的話可以進行 heapfy的 , 我們只能依賴JDK提供的數據結構進行的這種取巧方式