淺談負載均衡算法與實作

淺談負載均衡算法與實作

記得，我剛工作的時候，同僚說了一個故事：在他剛工作的時候，他同僚有一天興沖沖的跑到公司說，你們知道嗎，公司請了個大牛。大牛？對，那人會寫AJAX！哇，真是大牛啊，跟着他，可以學不少東西啊。我聽了笑了，但有點難以了解，因為現在幾乎隻要是一個開發，都會寫AJAX，怎麼寫個AJAX就算大牛呢？後來我明白了，三年前高深莫測的技術到現在變得普普通通，不足為奇，就像我們今天要講的負載均衡，在幾何時，負載均衡隻有大牛才能玩轉起來，但是到今天，一個小開發都可以聊上幾句。現在，就讓我們簡單的看看負載均衡把。

從負載均衡裝置的角度來看，分為硬體負載均衡和軟體負載均衡：

• 硬體負載均衡：比如最常見的F5，還有Array等，這些負載均衡是商業的負載均衡器，性能比較好，畢竟他們的就是為了負載均衡而生的，背後也有非常成熟的團隊，可以提供各種解決方案，但是價格比較昂貴，是以沒有充足的理由，充足的軟妹币是不會考慮的。
• 軟體負載均衡：包括我們耳熟能詳的Nginx，LVS，Tengine（阿裡對Nginx進行的改造）等。優點就是成本比較低，但是也需要有比較專業的團隊去維護，要自己去踩坑，去DIY。

從負載均衡的技術來看，分為服務端負載均衡和用戶端負載均衡：

• 服務端負載均衡：當我們通路一個服務，請求會先到另外一台伺服器，然後這台伺服器會把請求分發到提供這個服務的伺服器，當然如果隻有一台伺服器，那好說，直接把請求給那一台伺服器就可以了，但是如果有多台伺服器呢？這時候，就會根據一定的算法選擇一台伺服器。
• 用戶端負載均衡：用戶端服務均衡的概念貌似是有了服務治理才産生的，簡單的來說，就是在一台伺服器上維護着所有服務的ip，名稱等資訊，當我們在代碼中通路一個服務，是通過一個元件通路的，這個元件會從那台伺服器上取到所有提供這個服務的伺服器的資訊，然後通過一定的算法，選擇一台伺服器進行請求。

從負載均衡的算法來看，又分為 随機，輪詢，哈希，最小壓力，當然可能還會加上權重的概念，負載均衡的算法就是本文的重點了。

随機

随機就是沒有規律的，随便從負載中獲得一台，又分為完全随機和權重随機：

完全随機

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());
        }
    }
}           

運作結果：

雖說現在感覺并不是那麼随機，有的伺服器經常被獲得到，有的伺服器獲得的次數比較少，但是當有充足的請求次數，就會越來越平均，這正是随機數的一個特性。

完全随機是最簡單的負載均衡算法了，缺點比較明顯，因為伺服器有好有壞，處理能力是不同的，我們希望性能好的伺服器多處理些請求，性能差的伺服器少處理一些請求，是以就有了權重随機。

權重随機

權重随機，雖然還是采用的随機算法，但是為每台伺服器設定了權重，權重大的伺服器獲得的機率大一些，權重小的伺服器獲得的機率小一些。

關于權重随機的算法，有兩種實作方式：

一種是網上流傳的，代碼比較簡單：建構一個伺服器的List，如果A伺服器的權重是2，那麼往List裡面Add兩次A伺服器，如果B伺服器的權重是7，那麼我往List裡面Add7次B伺服器，以此類推，然後我再生成一個随機數，随機數的上限就是權重的總和，也就是List的Size。這樣權重越大的，被選中的機率當然越高，代碼如下：

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());
        }
    }
}           

可以很清楚的看到，權重小的伺服器被選中的機率相對是比較低的。

當然我在這裡僅僅是為了示範，一般來說，可以把建構伺服器List的代碼移動到靜态代碼塊中，不用每次都建構。

這種實作方式相對比較簡單，很容易就能想到，但是也有缺點，如果我幾台伺服器權重設定的都很大，比如上千，上萬，那麼伺服器List也有上萬條資料，這不是白白占用記憶體嗎？

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

為了友善解釋，還是就拿上面的例子來說吧：

如果A伺服器的權重是2，B伺服器的權重是7，C伺服器的權重是1：

• 如果我生成的随機數是1，那麼落到A伺服器，因為1<=2（A伺服器的權重）
• 如果我生成的随機數是5，那麼落到B伺服器，因為5>2（A伺服器的權重），5-2（A伺服器的權重）=3，3<7（B伺服器的權重）

• 如果我生成的随機數是10，那麼落到C伺服器，因為10>2（A伺服器的權重），10-2（A伺服器的權重）=8，8>7（B伺服器的權重），8-7（B伺服器的權重）=1，

  1<=1（C伺服器的權重）

不知道部落格對于大于小于符号，會不會有特殊處理，是以我再截個圖：

也許，光看文字描述還是不夠清楚，可以結合下面醜到爆炸的圖檔來了解下：

• 如果生成的随機數是5，那麼落到第二塊區域
• 如果生成的随機數是10，那麼落到第三塊區域

代碼如下：

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());
        }
    }
}           

這種實作方式雖然相對第一種實作方式比較“繞”，但卻是一種比較好的實作方式，

對記憶體沒有浪費，權重大小和伺服器List的Size也沒有關系。

輪詢

輪詢又分為三種，1.完全輪詢 2.權重輪詢 3.平滑權重輪詢

完全輪詢

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());
        }
    }
}           

完全輪詢，也是比較簡單的，但是問題和完全随機是一樣的，是以出現了權重輪詢。

權重輪詢

權重輪詢還是有兩種常用的實作方式，和權重随機是一樣的，在這裡，我就示範我認為比較好的一種：

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());
        }
    }
}
           

權重輪詢，看起來并沒什麼問題，但是還是有一點瑕疵，其中一台伺服器的壓力可能會突然上升，而另外的伺服器卻很“悠閑，喝着咖啡，看着新聞”。我們希望雖然是按照輪詢，但是中間最好可以有交叉，是以出現了第三種輪詢算法：平滑權重輪詢。

平滑權重輪詢

平滑權重是一個算法，很神奇的算法，我們有必要先對這個算法進行講解。

比如A伺服器的權重是5，B伺服器的權重是1，C伺服器的權重是1。

這個權重，我們稱之為“固定權重”，既然這個叫“固定權重”，那麼肯定還有叫“非固定權重的”，沒錯，“非固定權重”每次都會根據一定的規則變動。

1. 第一次通路，ABC的“非固定權重”分别是 5 1 1（初始），因為5是其中最大的，5對應的就是A伺服器，是以這次選到的伺服器就是A，然後我們用目前被選中的伺服器的權重-各個伺服器的權重之和，也就是A伺服器的權重-各個伺服器的權重之和。也就是5-7=-2，沒被選中的伺服器的“非固定權重”不做變化，現在三台伺服器的“非固定權重”分别是-2 1 1。
2. 第二次通路，把第一次通路最後得到的“非固定權重”+“固定權重”，現在三台伺服器的“非固定權重”是3，2，2，因為3是其中最大的，3對應的就是A伺服器，是以這次選到的伺服器就是A，然後我們用目前被選中的伺服器的權重-各個伺服器的權重之和，也就是A伺服器的權重-各個伺服器的權重之和。也就是3-7=-4，沒被選中的伺服器的“非固定權重”不做變化，現在三台伺服器的“非固定權重”分别是-4 1 1。

3. 第三次通路，把第二次通路最後得到的“非固定權重”+“固定權重”，現在三台伺服器的“非固定權重”是1，3，3，這個時候3雖然是最大的，但是卻出現了兩個，我們選第一個，第一個3對應的就是B伺服器，是以這次選到的伺服器就是B，然後我們用目前被選中的伺服器的權重-各個伺服器的權重之和，也就是B伺服器的權重-各個伺服器的權重之和。也就是3-7=-4，沒被選中的伺服器的“非固定權重”不做變化，現在三台伺服器的“非固定權重”分别是1 -4 3。

   ...

   以此類推，最終得到這樣的表格：

請求	獲得伺服器前的非固定權重	選中的伺服器	獲得伺服器後的非固定權重
1	{5, 1, 1}	A	{-2, 1, 1}
2	{3, 2, 2}		{-4, 2, 2}
3	{1, 3, 3}	B	{1, -4, 3}
4	{6, -3, 4}		{-1, -3, 4}
5	{4, -2, 5}	C	{4, -2, -2}
6	{9, -1, -1}		{2, -1, -1}
7	{7, 0, 0}		{0, 0, 0}
8

當第8次的時候，“非固定權重“又回到了初始的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());
        }
    }
}           

這就是平滑權重輪詢，巧妙的利用了巧妙算法，既有輪詢的效果，又避免了某台伺服器壓力突然升高，不可謂不妙。

哈希

負載均衡算法中的雜湊演算法，就是根據某個值生成一個哈希值，然後對應到某台伺服器上去，當然可以根據使用者，也可以根據請求參數，或者根據其他，想怎麼來就怎麼來。如果根據使用者，就比較巧妙的解決了負載均衡下Session共享的問題，使用者小明走的永遠是A伺服器，使用者小笨永遠走的是B伺服器。

那麼如何用代碼實作呢，這裡又需要引出一個新的概念：哈希環。

什麼？我隻聽過奧運五環，還有“啊 五環 你比四環多一環，啊 五環 你比六環少一環”，這個哈希環又是什麼鬼？容我慢慢道來。

哈希環，就是一個環！這...好像...有點難解釋呀，我們還是畫圖來說明把。

一個圓是由無數個點組成的，這是最簡單的數學知識，相信大家都可以了解吧，哈希環也一樣，哈希環也是有無數個“哈希點”構成的，當然并沒有“哈希點”這樣的說法，隻是為了便于大家了解。

我們先計算出伺服器的哈希值，比如根據IP，然後把這個哈希值放到環裡，如上圖所示。

來了一個請求，我們再根據某個值進行哈希，如果計算出來的哈希值落到了A和B的中間，那麼按照順時針算法，這個請求給B伺服器。

理想很豐滿，現實很孤單，可能三台伺服器掌管的“區域”大小相差很大很大，或者幹脆其中一台伺服器壞了，會出現如下的情況：

可以看出，B掌管的“區域”實在是太大，A可以說是“很悠閑，喝着咖啡，看着電影”，像這種情況，就叫“哈希傾斜”。

那麼怎麼避免這種情況呢？虛拟節點。

什麼是虛拟節點呢，說白了，就是虛拟的節點...好像..沒解釋啊...還是上一張醜到爆炸的圖吧：

其中，正方形的是真實的節點，或者說真實的伺服器，五邊形的是虛拟節點，或者說是虛拟的伺服器，當一個請求過來，落到了A1和B1之間，那麼按照順時針的規則，應該由B1伺服器進行處理，但是B1伺服器是虛拟的，它是從B伺服器映射出來的，是以再交給B伺服器進行處理。

要實作此種負載均衡算法，需要用到一個平時不怎麼常用的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 + "--伺服器---" + 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("風雨交加"));
    }           

哈希負載均衡算法到這裡就結束了。

最小壓力

是以的最小壓力負載均衡算法就是 選擇一台目前最“悠閑”的伺服器，如果A伺服器有100個請求，B伺服器有5個請求，而C伺服器隻有3個請求，那麼毫無疑問會選擇C伺服器，這種負載均衡算法是比較科學的。但是遺憾的在目前的場景下無法模拟出來“原汁原味”的最小壓力負載均衡算法的。

當然在實際的負載均衡下，可能會将多個負載均衡算法合在一起實作，比如先根據最小壓力算法，當有幾台伺服器的壓力一樣小的時候，再根據權重取出一台伺服器，如果權重也一樣，再随機取一台，等等。

今天的内容到這裡就結束了，謝謝大家。

原文位址

https://www.cnblogs.com/CodeBear/p/10508880.html