一篇有趣的負載均衡算法實作

一篇有趣的負載均衡算法實作

負載平衡（Load balancing）是一種在多個計算機（網絡、CPU、磁盤）之間均勻配置設定資源，以提高資源利用的技術。使用負載均衡可以最大化服務吞吐量，可能最小化響應時間，同時由于使用負載均衡時，會使用多個伺服器節點代單點服務，也提高了服務的可用性。

負載均衡的實作可以軟體可以硬體，硬體如大名鼎鼎的 F5 負載均衡裝置，軟體如 NGINX 中的負載均衡實作，又如 Springcloud Ribbon 元件中的負載均衡實作。

如果看到這裡你還不知道負載均衡是幹嘛的，那麼隻能放一張圖了，畢竟沒圖說個啥。

負載均衡要做到在多次請求下，每台伺服器被請求的次數大緻相同。但是實際生産中，可能每台機器的性能不同，我們會希望性能好的機器承擔的請求更多一些，這也是正常需求。

如果這樣說下來你看不懂，那我就再舉個例子好了，一排可愛的小熊（伺服器）站好。

這時有人（使用者）要過來打臉（請求通路）。

那麼怎麼樣我們才能讓這每一個可愛的小熊被打的次數大緻相同呢？

又或者熊 4 比較胖，抗擊打能力是别人的兩倍，我們怎麼提高熊 4 被打的次數也是别人的兩倍呢？

又或者每次出手的力度不同，有重有輕，恰巧熊 4 總是承受這種大力度啪啪打臉，熊 4 即将不省熊事，還要繼續打它嗎？

這些都是值的思考的問題。

說了那麼多，口幹舌燥，我雙手已經饑渴難耐了，迫不及待的想要撸起代碼了。

1. 随機通路

   上面說了，為了負載均衡，我們必須保證多次出手後，熊 1 到熊 4 被打次數均衡。比如使用随機通路法，根據數學上的機率論，随機出手次數越多，每隻熊被打的次數就會越相近。代碼實作也比較簡單，使用一個随機數，随機通路一個就可以了。

/* 伺服器清單 /

private static List serverList = new ArrayList<>();

static {

serverList.add("192.168.1.2");
serverList.add("192.168.1.3");
serverList.add("192.168.1.4");
serverList.add("192.168.1.5");           

}

/**

• 随機路由算法

  */

public static String random() {

// 複制周遊用的集合，防止操作中集合有變更
List<String> tempList = new ArrayList<>(serverList.size());
tempList.addAll(serverList);
// 随機數随機通路
int randomInt = new Random().nextInt(tempList.size());
return tempList.get(randomInt);           

因為使用了非線程安全的集合，是以在通路操作時操作的是集合的拷貝，下面幾種輪訓方式中也是這種思想。

寫一個模拟請求方法，請求10w次，記錄請求結果。

public static void main(String[] args) {

HashMap<String, Integer> serverMap = new HashMap<>();
for (int i = 0; i < 20000; i++) {
    String server = random();
    Integer count = serverMap.get(server);
    if (count == null) {
        count = 1;
    } else {
        count++;
    }
    // 記錄
    serverMap.put(server, count);
}
// 路由總體結果
for (Map.Entry<String, Integer> entry : serverMap.entrySet()) {
    System.out.println("IP:" + entry.getKey() + "，次數：" + entry.getValue());
}           

運作得到請求結果。

IP:192.168.1.3，次數：24979

IP:192.168.1.2，次數：24896

IP:192.168.1.5，次數：25043

IP:192.168.1.4，次數：25082

每台伺服器被通路的次數都趨近于 2.5w，有點負載均衡的意思。但是随機畢竟是随機，是不能保證通路次數絕對均勻的。

1. 輪訓通路

   輪訓通路就簡單多了，拿上面的熊1到熊4來說，我們一個接一個的啪啪 - 打臉，熊1打完打熊2，熊2打完打熊3，熊4打完打熊1，最終也是實作了被打均衡。但是保證均勻總是要付出代價的，随機通路中需要随機，輪訓通路中需要什麼來保證輪訓呢？

serverList.add("192.168.1.2");
serverList.add("192.168.1.3");
serverList.add("192.168.1.4");
serverList.add("192.168.1.5");           

private static Integer index = 0;

public static String randomOneByOne() {

// 複制周遊用的集合，防止操作中集合有變更
List<String> tempList = new ArrayList<>(serverList.size());
tempList.addAll(serverList);
String server = "";
synchronized (index) {
    index++;
    if (index == tempList.size()) {
        index = 0;
    }
    server = tempList.get(index);;
}
return server;           

由代碼裡可以看出來，為了保證輪訓，必須記錄上次通路的位置，為了讓在并發情況下不出現問題，還必須在使用位置記錄時進行加鎖，很明顯這種互斥鎖增加了性能開銷。

依舊使用上面的測試代碼測試10w次請求負載情況。

IP:192.168.1.3，次數：25000

IP:192.168.1.2，次數：25000

IP:192.168.1.5，次數：25000

IP:192.168.1.4，次數：25000

1. 輪訓權重

   上面示範了輪訓方式，還記的一開始提出的熊4比較胖抗擊打能力強，可以承受别人2倍的挨打次數嘛？上面兩種方式都沒有展現出來熊 4 的這個特點，熊 4 竊喜，不痛不癢。但是熊 1 到 熊 3 已經在崩潰的邊緣，不行，我們必須要讓胖着多打，能者多勞，提高整體性能。

private static HashMap serverMap = new HashMap<>();

serverMap.put("192.168.1.2", 2);
serverMap.put("192.168.1.3", 2);
serverMap.put("192.168.1.4", 2);
serverMap.put("192.168.1.5", 4);           

• 權重路由算法

public static String oneByOneWithWeight() {

List<String> tempList = new ArrayList();
HashMap<String, Integer> tempMap = new HashMap<>();
tempMap.putAll(serverMap);
for (String key : serverMap.keySet()) {
    for (int i = 0; i < serverMap.get(key); i++) {
        tempList.add(key);
    }
}
synchronized (index) {
    index++;
    if (index == tempList.size()) {
        index = 0;
    }
    return tempList.get(index);
}           

這次記錄下了每台伺服器的整體性能，給出一個數值，數值越大，性能越好。可以承受的請求也就越多，可以看到伺服器 192.168.1.5 的性能為 4，是其他伺服器的兩倍，依舊 10 w 請求測試。

IP:192.168.1.3，次數：20000

IP:192.168.1.2，次數：20000

IP:192.168.1.5，次數：40000

IP:192.168.1.4，次數：20000

192.168.1.5 承擔了 2 倍的請求。

1. 随機權重

   随機權重的方式和輪訓權重的方式大緻相同，隻是把使用互斥鎖輪訓的方式換成了随機通路，按照機率論來說，通路量增多時，服務通路也會達到負載均衡。

serverMap.put("192.168.1.2", 2);
serverMap.put("192.168.1.3", 2);
serverMap.put("192.168.1.4", 2);
serverMap.put("192.168.1.5", 4);           

public static String randomWithWeight() {

List<String> tempList = new ArrayList();
HashMap<String, Integer> tempMap = new HashMap<>();
tempMap.putAll(serverMap);
for (String key : serverMap.keySet()) {
    for (int i = 0; i < serverMap.get(key); i++) {
        tempList.add(key);
    }
}
int randomInt = new Random().nextInt(tempList.size());
return tempList.get(randomInt);           

依舊 10 w 請求測試，192.168.1.5 的權重是其他伺服器的近似兩倍，

IP:192.168.1.3，次數：19934

IP:192.168.1.2，次數：20033

IP:192.168.1.5，次數：39900

IP:192.168.1.4，次數：20133

1. IP-Hash

   上面的幾種方式要麼使用随機數，要麼使用輪訓，最終都達到了請求的負載均衡。但是也有一個很明顯的缺點，就是同一個使用者的多次請求很有可能不是同一個服務進行處理的，這時問題來了，如果你的服務依賴于 session ，那麼因為服務不同， session 也會丢失，不是我們想要的，是以出現了一種根據請求端的 ip 進行哈希計算來決定請求到哪一台伺服器的方式。這種方式可以保證同一個使用者的請求落在同一個服務上。

serverList.add("192.168.1.2");
serverList.add("192.168.1.3");
serverList.add("192.168.1.4");
serverList.add("192.168.1.5");           

• ip hash 路由算法

public static String ipHash(String ip) {

// 複制周遊用的集合，防止操作中集合有變更
List<String> tempList = new ArrayList<>(serverList.size());
tempList.addAll(serverList);
// 哈希計算請求的伺服器
int index = ip.hashCode() % serverList.size();
return tempList.get(Math.abs(index));           

1. 總結

   上面的四種方式看似不錯，那麼這樣操作下來真的展現了一開始說的負載均衡嗎？答案是不一定的。就像上面的最後一個提問。

伺服器也是這個道理，每次請求進行的操作對資源的消耗可能是不同的。比如說某些操作它對 CPU 的使用就是比較高，也很正常。是以負載均衡有時不能簡單的通過請求的負載來作為負載均衡的唯一依據。還可以結合服務的目前連接配接數量、最近響應時間等次元進行總體均衡，總而言之，就是為了達到資源使用的負載均衡。

最後的話

文章已經收錄在 Github.com/niumoo/JavaNotes ，歡迎Star和指教。更有一線大廠面試點，Java程式員需要掌握的核心知識等文章，也整理了很多我的文字，歡迎 Star 和完善，希望我們一起變得優秀。

原文位址

https://www.cnblogs.com/niumoo/p/13021938.html