淺談負(fù)載均衡算法與實現(xiàn)

記得，我剛工作的時候役衡，同事說了一個故事：在他剛工作的時候茵休，他同事有一天興沖沖的跑到公司說，你們知道嗎手蝎，公司請了個大牛榕莺。大牛？對棵介，那人會寫AJAX钉鸯！哇，真是大牛啊邮辽，跟著他唠雕，可以學(xué)不少東西啊。我聽了笑了逆巍，但有點難以理解及塘，因為現(xiàn)在幾乎只要是一個開發(fā)，都會寫AJAX锐极，怎么寫個AJAX就算大牛呢？后來我明白了芳肌，三年前高深莫測的技術(shù)到現(xiàn)在變得普普通通灵再，不足為奇，就像我們今天要講的負(fù)載均衡亿笤，在幾何時翎迁，負(fù)載均衡只有大牛才能玩轉(zhuǎn)起來，但是到今天净薛，一個小開發(fā)都可以聊上幾句⊥衾疲現(xiàn)在，就讓我們簡單的看看負(fù)載均衡把肃拜。

從負(fù)載均衡設(shè)備的角度來看痴腌，分為硬件負(fù)載均衡和軟件負(fù)載均衡：

硬件負(fù)載均衡：比如最常見的F5，還有Array等燃领，這些負(fù)載均衡是商業(yè)的負(fù)載均衡器士聪，性能比較好，畢竟他們的就是為了負(fù)載均衡而生的猛蔽，背后也有非常成熟的團隊剥悟，可以提供各種解決方案灵寺，但是價格比較昂貴，所以沒有充足的理由区岗，充足的軟妹幣是不會考慮的略板。
軟件負(fù)載均衡：包括我們耳熟能詳?shù)腘ginx，LVS慈缔，Tengine（阿里對Nginx進(jìn)行的改造）等叮称。優(yōu)點就是成本比較低，但是也需要有比較專業(yè)的團隊去維護(hù)胀糜，要自己去踩坑颅拦，去DIY。

從負(fù)載均衡的技術(shù)來看教藻，分為服務(wù)端負(fù)載均衡和客戶端負(fù)載均衡：

服務(wù)端負(fù)載均衡：當(dāng)我們訪問一個服務(wù)距帅，請求會先到另外一臺服務(wù)器，然后這臺服務(wù)器會把請求分發(fā)到提供這個服務(wù)的服務(wù)器括堤，當(dāng)然如果只有一臺服務(wù)器碌秸，那好說，直接把請求給那一臺服務(wù)器就可以了悄窃，但是如果有多臺服務(wù)器呢讥电？這時候，就會根據(jù)一定的算法選擇一臺服務(wù)器轧抗。
客戶端負(fù)載均衡：客戶端服務(wù)均衡的概念貌似是有了服務(wù)治理才產(chǎn)生的恩敌，簡單的來說，就是在一臺服務(wù)器上維護(hù)著所有服務(wù)的ip横媚，名稱等信息纠炮，當(dāng)我們在代碼中訪問一個服務(wù)，是通過一個組件訪問的灯蝴，這個組件會從那臺服務(wù)器上取到所有提供這個服務(wù)的服務(wù)器的信息恢口，然后通過一定的算法，選擇一臺服務(wù)器進(jìn)行請求穷躁。

從負(fù)載均衡的算法來看耕肩，又分為隨機，輪詢问潭，哈希猿诸，最小壓力，當(dāng)然可能還會加上權(quán)重的概念睦授，負(fù)載均衡的算法就是本文的重點了两芳。

隨機

隨機就是沒有規(guī)律的，隨便從負(fù)載中獲得一臺去枷，又分為完全隨機和加權(quán)隨機：

完全隨機

public class Servers {
    public List<String> list = new ArrayList<>() {
        {
            add("192.168.1.1");
            add("192.168.1.2");
            add("192.168.1.3");
        }
    };
}

public class FullRandom {
    static Servers servers = new Servers();
    static Random random = new Random();

    public  static String  go() {
        var number = random.nextInt(servers.list.size());
        return servers.list.get(number);
    }

    public static void main(String[] args) {
        for (var i = 0; i < 15; i++) {
            System.out.println(go());
        }
    }
}

運行結(jié)果：

image.png

雖說現(xiàn)在感覺并不是那么隨機怖辆，有的服務(wù)器經(jīng)常被獲得到是复，有的服務(wù)器獲得的次數(shù)比較少，但是當(dāng)有充足的請求次數(shù)竖螃，就會越來越平均淑廊，這正是隨機數(shù)的一個特性。

完全隨機是最簡單的負(fù)載均衡算法了特咆，缺點比較明顯季惩，因為服務(wù)器有好有壞，處理能力是不同的腻格，我們希望性能好的服務(wù)器多處理些請求画拾，性能差的服務(wù)器少處理一些請求，所以就有了加權(quán)隨機菜职。

加權(quán)隨機

加權(quán)隨機青抛，雖然還是采用的隨機算法，但是為每臺服務(wù)器設(shè)置了權(quán)重酬核，權(quán)重大的服務(wù)器獲得的概率大一些蜜另，權(quán)重小的服務(wù)器獲得的概率小一些。

關(guān)于加權(quán)隨機的算法嫡意，有兩種實現(xiàn)方式：

一種是網(wǎng)上流傳的举瑰，代碼比較簡單：構(gòu)建一個服務(wù)器的List，如果A服務(wù)器的權(quán)重是2蔬螟，那么往List里面Add兩次A服務(wù)器此迅，如果B服務(wù)器的權(quán)重是7，那么往List里面Add7次B服務(wù)器旧巾，以此類推邮屁，然后我再生成一個隨機數(shù)，隨機數(shù)的上限就是權(quán)重的總和菠齿，也就是List的Size。這樣權(quán)重越大的坐昙，被選中的概率當(dāng)然越高绳匀，代碼如下：

public class Servers {
    public HashMap<String, Integer> map = new HashMap<>() {
        {
            put("192.168.1.1", 2);
            put("192.168.1.2", 7);
            put("192.168.1.3", 1);
        }
    };
}

public class WeightRandom {

    static Servers servers = new Servers();
    static Random random = new Random();

    public static String go() {
        var ipList = new ArrayList<String>();
        for (var item : servers.map.entrySet()) {
            for (var i = 0; i < item.getValue(); i++) {
                ipList.add(item.getKey());
            }
        }
        int allWeight = servers.map.values().stream().mapToInt(a -> a).sum();
        var number = random.nextInt(allWeight);
        return ipList.get(number);
    }

    public static void main(String[] args) {
        for (var i = 0; i < 15; i++) {
            System.out.println(go());
        }
    }
}

運行結(jié)果：

image.png

可以很清楚的看到，權(quán)重小的服務(wù)器被選中的概率相對是比較低的炸客。

當(dāng)然我在這里僅僅是為了演示疾棵，一般來說，可以把構(gòu)建服務(wù)器List的代碼移動到靜態(tài)代碼塊中痹仙，不用每次都構(gòu)建是尔。

這種實現(xiàn)方式相對比較簡單，很容易就能想到开仰，但是也有缺點拟枚，如果我?guī)着_服務(wù)器權(quán)重設(shè)置的都很大薪铜，比如上千，上萬恩溅，那么服務(wù)器List也有上萬條數(shù)據(jù)隔箍，這不是白白占用內(nèi)存嗎？

所以聰明的程序員想到了第二種方式：

為了方便解釋脚乡，還是就拿上面的例子來說吧：

如果A服務(wù)器的權(quán)重是2蜒滩，B服務(wù)器的權(quán)重是7，C服務(wù)器的權(quán)重是1：

如果我生成的隨機數(shù)是1奶稠，那么落到A服務(wù)器俯艰，因為1<=2（A服務(wù)器的權(quán)重）
如果我生成的隨機數(shù)是5，那么落到B服務(wù)器锌订，因為5>2（A服務(wù)器的權(quán)重）竹握，5-2（A服務(wù)器的權(quán)重）=3，3<7（B服務(wù)器的權(quán)重）
如果我生成的隨機數(shù)是10瀑志，那么落到C服務(wù)器涩搓，因為10>2（A服務(wù)器的權(quán)重），10-2（A服務(wù)器的權(quán)重）=8劈猪，8>7（B服務(wù)器的權(quán)重）昧甘，8-7（B服務(wù)器的權(quán)重）=1，
1<=1（C服務(wù)器的權(quán)重）

不知道博客對于大于小于符號战得，會不會有特殊處理充边，所以我再截個圖：

image.png

也許，光看文字描述還是不夠清楚常侦，可以結(jié)合下面丑到爆炸的圖片來理解下：

image.png

如果生成的隨機數(shù)是5浇冰，那么落到第二塊區(qū)域
如果生成的隨機數(shù)是10，那么落到第三塊區(qū)域

代碼如下：

public class WeightRandom {
    static Servers servers = new Servers();
    static Random random = new Random();

    public static String go() {
        int allWeight = servers.map.values().stream().mapToInt(a -> a).sum();
        var number = random.nextInt(allWeight);
        for (var item : servers.map.entrySet()) {
            if (item.getValue() >= number) {
                return item.getKey();
            }
            number -= item.getValue();
        }
        return "";
    }

    public static void main(String[] args) {
        for (var i = 0; i < 15; i++) {
            System.out.println(go());
        }
    }
}

運行結(jié)果：

image.png

這種實現(xiàn)方式雖然相對第一種實現(xiàn)方式比較“繞”聋亡，但卻是一種比較好的實現(xiàn)方式肘习，
對內(nèi)存沒有浪費，權(quán)重大小和服務(wù)器List的Size也沒有關(guān)系坡倔。

輪詢

輪詢又分為三種漂佩，1.完全輪詢 2.加權(quán)輪詢 3.平滑加權(quán)輪詢

完全輪詢

public class FullRound {

    static Servers servers = new Servers();
    static int index;

    public static String go() {
        if (index == servers.list.size()) {
            index = 0;
        }
        return servers.list.get(index++);
    }


    public static void main(String[] args) {
        for (var i = 0; i < 15; i++) {
            System.out.println(go());
        }
    }
}

運行結(jié)果：

image.png

完全輪詢，也是比較簡單的罪塔，但是問題和完全隨機是一樣的投蝉，所以出現(xiàn)了加權(quán)輪詢。

加權(quán)輪詢

加權(quán)輪詢還是有兩種常用的實現(xiàn)方式征堪，和加權(quán)隨機是一樣的瘩缆，在這里，我就演示我認(rèn)為比較好的一種：

public class WeightRound {

    static Servers servers = new Servers();

    static int index;

    public static String go() {
        int allWeight = servers.map.values().stream().mapToInt(a -> a).sum();
        int number = (index++) % allWeight;
        for (var item : servers.map.entrySet()) {
            if (item.getValue() > number) {
                return item.getKey();
            }
            number -= item.getValue();
        }
        return "";
    }

    public static void main(String[] args) {
        for (var i = 0; i < 15; i++) {
            System.out.println(go());
        }
    }
}

運行結(jié)果：

image.png

加權(quán)輪詢佃蚜，看起來并沒什么問題庸娱，但是還是有一點瑕疵着绊，其中一臺服務(wù)器的壓力可能會突然上升，而另外的服務(wù)器卻很“悠閑涌韩，喝著咖啡畔柔，看著新聞”。我們希望雖然是按照輪詢臣樱，但是中間最好可以有交叉靶擦，所以出現(xiàn)了第三種輪詢算法：平滑加權(quán)輪詢。

平滑加權(quán)輪詢

平滑加權(quán)是一個算法雇毫，很神奇的算法玄捕，我們有必要先對這個算法進(jìn)行講解。
比如A服務(wù)器的權(quán)重是5棚放，B服務(wù)器的權(quán)重是1枚粘，C服務(wù)器的權(quán)重是1。
這個權(quán)重飘蚯，我們稱之為“固定權(quán)重”馍迄，既然這個叫“固定權(quán)重”，那么肯定還有叫“非固定權(quán)重的”局骤，沒錯攀圈，“非固定權(quán)重”每次都會根據(jù)一定的規(guī)則變動。

第一次訪問峦甩，ABC的“非固定權(quán)重”分別是 5 1 1（初始）赘来，因為5是其中最大的，5對應(yīng)的就是A服務(wù)器凯傲，所以這次選到的服務(wù)器就是A犬辰，然后我們用當(dāng)前被選中的服務(wù)器的權(quán)重-各個服務(wù)器的權(quán)重之和，也就是A服務(wù)器的權(quán)重-各個服務(wù)器的權(quán)重之和冰单。也就是5-7=-2幌缝，沒被選中的服務(wù)器的“非固定權(quán)重”不做變化，現(xiàn)在三臺服務(wù)器的“非固定權(quán)重”分別是-2 1 1诫欠。
第二次訪問狮腿，把第一次訪問最后得到的“非固定權(quán)重”+“固定權(quán)重”，現(xiàn)在三臺服務(wù)器的“非固定權(quán)重”是3呕诉，2，2吃度，因為3是其中最大的甩挫，3對應(yīng)的就是A服務(wù)器，所以這次選到的服務(wù)器就是A椿每，然后我們用當(dāng)前被選中的服務(wù)器的權(quán)重-各個服務(wù)器的權(quán)重之和伊者，也就是A服務(wù)器的權(quán)重-各個服務(wù)器的權(quán)重之和英遭。也就是3-7=-4，沒被選中的服務(wù)器的“非固定權(quán)重”不做變化亦渗，現(xiàn)在三臺服務(wù)器的“非固定權(quán)重”分別是-4 2 2挖诸。
第三次訪問，把第二次訪問最后得到的“非固定權(quán)重”+“固定權(quán)重”法精，現(xiàn)在三臺服務(wù)器的“非固定權(quán)重”是1多律，3，3搂蜓，這個時候3雖然是最大的狼荞，但是卻出現(xiàn)了兩個，我們選第一個帮碰，第一個3對應(yīng)的就是B服務(wù)器相味，所以這次選到的服務(wù)器就是B，然后我們用當(dāng)前被選中的服務(wù)器的權(quán)重-各個服務(wù)器的權(quán)重之和殉挽，也就是B服務(wù)器的權(quán)重-各個服務(wù)器的權(quán)重之和丰涉。也就是3-7=-4，沒被選中的服務(wù)器的“非固定權(quán)重”不做變化斯碌，現(xiàn)在三臺服務(wù)器的“非固定權(quán)重”分別是1 -4 3一死。
...
以此類推，最終得到這樣的表格：

請求	獲得服務(wù)器前的非固定權(quán)重	選中的服務(wù)器	獲得服務(wù)器后的非固定權(quán)重
1	{5, 1, 1}	A	{-2, 1, 1}
2	{3, 2, 2}	A	{-4, 2, 2}
3	{1, 3, 3}	B	{1, -4, 3}
4	{6, -3, 4}	A	{-1, -3, 4}
5	{4, -2, 5}	C	{4, -2, -2}
6	{9, -1, -1}	A	{2, -1, -1}
7	{7, 0, 0}	A	{0, 0, 0}
8	{5, 1, 1}	A	{-2, 1, 1}

當(dāng)?shù)?次的時候输拇，“非固定權(quán)重“又回到了初始的5 1 1摘符，是不是很神奇，也許算法還是比較繞的策吠，但是代碼卻簡單多了：

public class Server {

    public Server(int weight, int currentWeight, String ip) {
        this.weight = weight;
        this.currentWeight = currentWeight;
        this.ip = ip;
    }

    private int weight;

    private int currentWeight;

    private String ip;

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getCurrentWeight() {
        return currentWeight;
    }

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

    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }
}

public class Servers {
    public HashMap<String, Server> serverMap = new HashMap<>() {
        {
            put("192.168.1.1", new Server(5,5,"192.168.1.1"));
            put("192.168.1.2", new Server(1,1,"192.168.1.2"));
            put("192.168.1.3", new Server(1,1,"192.168.1.3"));
        }
    };
}

public class SmoothWeightRound {

    private static Servers servers = new Servers();

    public static String go() {
        Server maxWeightServer = null;

        int allWeight = servers.serverMap.values().stream().mapToInt(Server::getWeight).sum();

        for (Map.Entry<String, Server> item : servers.serverMap.entrySet()) {
            var currentServer = item.getValue();
            if (maxWeightServer == null || currentServer.getCurrentWeight() > maxWeightServer.getCurrentWeight()) {
                maxWeightServer = currentServer;
            }
        }
        assert maxWeightServer != null;
        maxWeightServer.setCurrentWeight(maxWeightServer.getCurrentWeight() - allWeight);

        for (Map.Entry<String, Server> item : servers.serverMap.entrySet()) {
            var currentServer = item.getValue();
            currentServer.setCurrentWeight(currentServer.getCurrentWeight() + currentServer.getWeight());
        }
        return maxWeightServer.getIp();
    }

    public static void main(String[] args) {
        for (var i = 0; i < 15; i++) {
            System.out.println(go());
        }
    }
}

運行結(jié)果：

image.png

這就是平滑加權(quán)輪詢逛裤，巧妙的利用了巧妙算法，既有輪詢的效果猴抹，又避免了某臺服務(wù)器壓力突然升高带族，不可謂不妙。

哈希

負(fù)載均衡算法中的哈希算法蟀给，就是根據(jù)某個值生成一個哈希值蝙砌，然后對應(yīng)到某臺服務(wù)器上去，當(dāng)然可以根據(jù)用戶跋理，也可以根據(jù)請求參數(shù)择克，或者根據(jù)其他，想怎么來就怎么來前普。如果根據(jù)用戶肚邢，就比較巧妙的解決了負(fù)載均衡下Session共享的問題，用戶小明走的永遠(yuǎn)是A服務(wù)器，用戶小笨永遠(yuǎn)走的是B服務(wù)器骡湖。

那么如何用代碼實現(xiàn)呢贱纠，這里又需要引出一個新的概念：哈希環(huán)。

什么响蕴？我只聽過奧運五環(huán)谆焊，還有“啊五環(huán) 你比四環(huán)多一環(huán)，啊五環(huán) 你比六環(huán)少一環(huán)”浦夷，這個哈希環(huán)又是什么鬼辖试？容我慢慢道來。

哈希環(huán)军拟，就是一個環(huán)剃执！這...好像...有點難解釋呀，我們還是畫圖來說明把懈息。

image.png

一個圓是由無數(shù)個點組成的肾档，這是最簡單的數(shù)學(xué)知識，相信大家都可以理解吧辫继，哈希環(huán)也一樣怒见，哈希環(huán)也是有無數(shù)個“哈希點”構(gòu)成的，當(dāng)然并沒有“哈希點”這樣的說法姑宽，只是為了便于大家理解遣耍。

我們先計算出服務(wù)器的哈希值，比如根據(jù)IP炮车，然后把這個哈希值放到環(huán)里舵变，如上圖所示。

來了一個請求瘦穆，我們再根據(jù)某個值進(jìn)行哈希纪隙，如果計算出來的哈希值落到了A和B的中間，那么按照順時針?biāo)惴富颍@個請求給B服務(wù)器绵咱。

理想很豐滿，現(xiàn)實很骨感熙兔，可能三臺服務(wù)器掌管的“區(qū)域”大小相差很大很大悲伶，或者干脆其中一臺服務(wù)器壞了，會出現(xiàn)如下的情況：

image.png

可以看出住涉，A掌管的“區(qū)域”實在是太大麸锉，B可以說是“很悠閑，喝著咖啡，看著電影”，像這種情況，就叫“哈希傾斜”淘讥。

那么怎么避免這種情況呢主穗？虛擬節(jié)點。

什么是虛擬節(jié)點呢毙芜，說白了忽媒，就是虛擬的節(jié)點...好像..沒解釋啊...還是上一張丑到爆炸的圖吧：

image.png

其中，正方形的是真實的節(jié)點腋粥，或者說真實的服務(wù)器晦雨，五邊形的是虛擬節(jié)點，或者說是虛擬的服務(wù)器隘冲，當(dāng)一個請求過來闹瞧，落到了A1和B1之間，那么按照順時針的規(guī)則展辞，應(yīng)該由B1服務(wù)器進(jìn)行處理奥邮，但是B1服務(wù)器是虛擬的，它是從B服務(wù)器映射出來的罗珍，所以再交給B服務(wù)器進(jìn)行處理洽腺。

要實現(xiàn)此種負(fù)載均衡算法，需要用到一個平時不怎么常用的Map：TreeMap覆旱，對TreeMap不了解的朋友可以先去了解下TreeMap蘸朋，下面放出代碼：

    private static String go(String client) {
        int nodeCount = 20;
        TreeMap<Integer, String> treeMap = new TreeMap();
        for (String s : new Servers().list) {
            for (int i = 0; i < nodeCount; i++)
                treeMap.put((s + "--服務(wù)器---" + i).hashCode(), s);
        }
        int clientHash = client.hashCode();
        SortedMap<Integer, String> subMap = treeMap.tailMap(clientHash);
        Integer firstHash;
        if (subMap.size() > 0) {
            firstHash = subMap.firstKey();
        } else {
            firstHash = treeMap.firstKey();
        }
        String s = treeMap.get(firstHash);
        return s;
    }

    public static void main(String[] args) {
        System.out.println(go("今天天氣不錯啊"));
        System.out.println(go("192.168.5.258"));
        System.out.println(go("0"));
        System.out.println(go("-110000"));
        System.out.println(go("風(fēng)雨交加"));
    }

運行結(jié)果：

image.png

哈希負(fù)載均衡算法到這里就結(jié)束了。

最小壓力

最小壓力負(fù)載均衡算法就是選擇一臺當(dāng)前最“悠閑”的服務(wù)器扣唱，如果A服務(wù)器有100個請求藕坯，B服務(wù)器有5個請求，而C服務(wù)器只有3個請求噪沙，那么毫無疑問會選擇C服務(wù)器炼彪，這種負(fù)載均衡算法是比較科學(xué)的。但是遺憾的在當(dāng)前的場景下無法模擬出來“原汁原味”的最小壓力負(fù)載均衡算法的曲聂。

當(dāng)然在實際的負(fù)載均衡下霹购，可能會將多個負(fù)載均衡算法合在一起實現(xiàn)，比如先根據(jù)最小壓力算法朋腋，當(dāng)有幾臺服務(wù)器的壓力一樣小的時候齐疙，再根據(jù)權(quán)重取出一臺服務(wù)器，如果權(quán)重也一樣旭咽，再隨機取一臺贞奋，等等。

今天的內(nèi)容到這里就結(jié)束了穷绵，謝謝大家轿塔。