今天在看《大型網(wǎng)站技術(shù)架構(gòu)》時讳癌，里面介紹負載均衡算法時提到加權(quán)輪詢(Weighted Round Robin) , 對其具體實現(xiàn)不太熟悉巷疼，網(wǎng)上的介紹有點亂搀擂，不太好理解，所以這里自己實現(xiàn)一下這個算法吗跋，以自己能通俗理解的方式記錄一下

一. 加權(quán)輪詢在nginx中的部分配置

http {  
    upstream cluster {  
        server 192.168.1.2 weight=5;  
        server 192.168.1.3 weight=3;  
        server 192.168.1.4 weight=1;  
    }  
    ...
location / {
       proxy_set_header X-Real-IP $remote_addr;               //返回真實IP
       proxy_pass http://cluster;                           //代理指向cluster 
   }

二. 加權(quán)輪詢算法介紹

1. 由于不同服務(wù)器的配置侧戴、部署的應(yīng)用不同，其處理能力會不一樣。所以救鲤，加權(quán)輪詢算法的原理就是：根據(jù)服務(wù)器的不同處理能力久窟，給每個服務(wù)器分配不同的權(quán)值，使其能夠接受相應(yīng)權(quán)值數(shù)的服務(wù)請求本缠。
2. 在Nginx加權(quán)輪詢算法中斥扛，每個節(jié)點有三個權(quán)重變量

• weight : 配置的權(quán)重，即在配置文件或初始化時約定好的每個節(jié)點的權(quán)重
• currentWeight : 節(jié)點當前權(quán)重丹锹，會一直變化
• effectiveWeight ：有效權(quán)重稀颁，初始值為weight, 通訊過程中發(fā)現(xiàn)節(jié)點異常，則-1 楣黍，之后再次選取本節(jié)點匾灶，調(diào)用成功一次則+1，直達恢復(fù)到weight 租漂。 用于健康檢查阶女，處理異常節(jié)點，降低其權(quán)重哩治。

3. 算法邏輯
   (1) 輪詢所有節(jié)點秃踩，計算當前狀態(tài)下所有節(jié)點的effectiveWeight之和totalWeight；
   (2) currentWeight = currentWeight + effectiveWeight; 選出所有節(jié)點中currentWeight中最大的一個節(jié)點作為選中節(jié)點业筏；
   (3) 選中節(jié)點的currentWeight = currentWeight - totalWeight憔杨；
   注：（為了簡單清晰，后面的實現(xiàn)不考慮健康檢查effectiveWeight這個功能實現(xiàn)蒜胖，假設(shè)所有節(jié)點都是100%可用消别，所以上面的邏輯要把使用effectiveWeight的地方換成weight
4. 例子
   假設(shè)有三個節(jié)點{serverA , serverB , serverC} , 權(quán)重為分別為{4,3,2} ,現(xiàn)在請求7次的分配情況如下：

totaoWeight = 4 + 3 + 2 = 9 ,
第一次請求 serverA= 4 + 4(原始比重) = 8 ,serverB= 3+3(原始比重) = 6,serverC= 2+2(原始比重) = 4 ， 最大的是serverA , 所以 serverA= 8 - 9 (權(quán)重總和) = -1 台谢，所以最后值為 serverA= -1,serverB= 6,serverC= 4
第二次請求 serverA= -1 + 4(原始比重) = 3 ,serverB= 6+3(原始比重) = 9,serverC= 4+2(原始比重) = 6 寻狂， 最大的是serverB , 所以 serverB= 9 - 9 (權(quán)重總和) = 0 ，所以最后值為 serverA= 3,serverB= 0,serverC= 6
依此類推...

三. 代碼實現(xiàn)（java）

• DemoApplication main方法

package com.example.demo;

public class DemoApplication {
    public static void main(String[] args) {
        /**
         * 假設(shè)有三個服務(wù)器權(quán)重配置如下：
         * server A  weight = 4 ;
         * server B  weight = 3 ;
         * server C  weight = 2 ;
         */
        Node serverA = new Node("serverA", 4);
        Node serverB = new Node("serverB", 3);
        Node serverC = new Node("serverC", 2);
        
        SmoothWeightedRoundRobin smoothWeightedRoundRobin = new SmoothWeightedRoundRobin(serverA,serverB ,serverC);
        for (int i = 0; i < 7; i++) {
            Node i1 = smoothWeightedRoundRobin.select();
            System.out.println(i1.getServerName());
        }
    }
}

• SmoothWeightedRoundRobin 加權(quán)輪詢算法

package com.example.demo;

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

public class SmoothWeightedRoundRobin {
    private volatile List<Node> nodeList = new ArrayList<>() ; // 保存權(quán)重
    private ReentrantLock lock = new ReentrantLock() ;

    public SmoothWeightedRoundRobin(Node ...nodes) {
        for (Node node : nodes) {
            nodeList.add(node) ;
        }
    }

    public Node select(){
        try {
            lock.lock();
            return this.selectInner() ;
        }finally {
            lock.unlock();
        }
    }

    private Node selectInner(){
        int totalWeight = 0 ;
        Node maxNode = null ;
        int maxWeight = 0 ;

        for (int i = 0; i < nodeList.size(); i++) {
            Node n = nodeList.get(i);
            totalWeight += n.getWeight() ;

            // 每個節(jié)點的當前權(quán)重要加上原始的權(quán)重
            n.setCurrentWeight(n.getCurrentWeight() + n.getWeight());

            // 保存當前權(quán)重最大的節(jié)點
            if (maxNode == null || maxWeight < n.getCurrentWeight() ) {
                maxNode = n ;
                maxWeight = n.getCurrentWeight() ;
            }
        }
        // 被選中的節(jié)點權(quán)重減掉總權(quán)重
        maxNode.setCurrentWeight(maxNode.getCurrentWeight() - totalWeight);

//        nodeList.forEach(node -> System.out.print(node.getCurrentWeight()));
        return maxNode ;
    }
}

• Node 服務(wù)節(jié)點

package com.example.demo;

public class Node {
    private final int weight ;  // 初始權(quán)重 （保持不變）
    private final String serverName ; // 服務(wù)名

    private int currentWeight ; // 當前權(quán)重

    public Node( String serverName, int weight) {
        this.weight = weight;
        this.serverName = serverName ;
        this.currentWeight = weight ;
    }

    public int getCurrentWeight() {
        return currentWeight;
    }

    public int getWeight() {
        return weight;
    }

    public void setCurrentWeight(int currentWeight) {
        this.currentWeight = currentWeight;
    }

    public String getServerName() {
        return serverName;
    }
}

這個算法相對保證了的平滑性和均勻性