自古帝王多短命，假如皇帝也懂負載均衡算法…

• 2020 年 2 月 24 日
• 筆記

「

大家都知道古代皇帝各個都是後宮佳麗三千，而皇帝身上都天然的帶着雨露均沾的精神，不想單獨的寵愛一人！

轉自：51CTO技術棧

弱水三千，又怎捨得只取一瓢飲？據傳皇帝們晚上睡覺個個都怕冷，因此每晚都需要有人侍寢，那麼這麼多後宮，該翻誰牌子、怎麼分配侍寢名額呢？

還別說，皇帝行房事竟還挺講究的！早在《春秋》就有記載「晦陰惑疾，明謠心疾，以辟六氣」。

九嬪以下，每九人中進御一人，八十一女御佔九個晚上，世婦二十七人佔三個晚上，九嬪佔一個晚上，三夫人佔一個晚上，以上共十四夜，皇后獨佔一個晚上，共十五夜。上半個月按上述安排進御，下半個月從十六日開始，由皇后起，再御九嬪、世婦、女御，與月亮由盛而衰相對應……

不同朝代的皇帝也有不同寵幸妃子的方法，著名的有羊車望幸、擲篩侍寢、蝶幸、翻牌懸燈等等。

不過在我看來，如果皇帝懂負載均衡算法的話，大可不必這麼折騰，一套算法便可搞定終身侍寢大事！因此我們今天來介紹幾種常用的負載均衡算法及代碼實現！

先看下文章的大綱：

• 輪詢算法
• 加權輪詢算法
• 隨機算法
• 加權隨機算法
• 源地址 hash 算法
• 一致性 hash 算法

輪詢算法

據史料記載，乾隆一生妃嬪就有 42 人，還不算大明湖畔的夏雨荷等在下江南時候留下的情。

假設在某個時期內，皇阿瑪最寵幸的有令妃、嫻妃、高貴妃、純妃四位。那普通的輪詢算法怎麼去選擇呢？

我們先定義一個妃子集合如下：

/**   * *所有妃子集合   */  public static final List<String> PRINCESS_LIST = Arrays.asList("令妃", "嫻妃", "高貴妃", "純妃");

然後從列表中輪詢侍寢的妃子，用一個變量 index 去記錄輪詢的位置。

// 記錄循環的位置  private static Integer index = 0;  public static void main(String[] args) {      for (int i = 0; i < 10; i++) {          System.out.println(getPrincess());      }  }  private static String getPrincess() {      // 超過數組大小需要歸零（每次獲取前判斷，防止配置變化導致索引越界）      if (index >= PrincessConfig.PRINCESS_LIST.size()) {          index = 0;      }      String princess = PrincessConfig.PRINCESS_LIST.get(index);      index++;      return princess;  }

輸出結果就不貼出來了。該算法的特點就是簡單、簡單、簡單！但是也存在很大缺點！

如果皇帝更寵愛令妃，想讓她侍寢的概率更高呢？那就需要用到下面的加權輪詢算法！

加權輪詢算法

加權輪詢就是可以主觀的給每個妃子設置一個喜好值（權重值），以控制被選中的概率，因此我們需要定義如下的配置：

/**   * *所有妃子集合   */  public static final Map<String, Integer> PRINCESS_MAP = new LinkedHashMap<String, Integer>() {      {          put("令妃", 5);          put("嫻妃", 1);          put("高貴妃", 3);          put("純妃", 2);      }  };

這裡的配置就不再是簡單的一個集合，每個妃子都對應了一個權重值，那輪詢的時候怎麼根據這個值去提高被選中的概率呢？

下面我們來講三種比較常見的實現。

加權輪詢實現一

我們的思路是把這個 map 的 key（妃子）根據權重值轉存到一個 list 中，然後再去輪詢這個 list，如果權重值為 5，那就在 list 中添加 5 條相同的記錄！

然後我們去遍歷這個 list，這樣權重值越高，在 list 中出現的概率就越高，被輪詢中的概率也就越高！

// 記錄循環的位置  private static Integer index = 0;    public static void main(String[] args) {     for (int i = 0; i < 11; i++) {         System.out.println(getPrincess1());    }  }    private static String getPrincess1() {       // 遍歷map放入到list中     List<String> princessList = new ArrayList<String>();     for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {         int weight = PrincessConfig.PRINCESS_MAP.get(princess);         // 根據權重值重複放入到一個list中         for (int i = 0; i < weight; i++) {             princessList.add(princess);        }    }       if (index >= princessList.size()) {         index = 0;    }     String princess = princessList.get(index);       index++;       return princess;  }

輸出結果如下：

該加權輪詢算法比較簡單，比較容易實現。但是也有個問題，我們配置的權重值是 5、1、3、2，那我們是不是也可以配置成 50、10、30、20 呢？

那按照上面的方式，我們是不是就需要把同樣的元素往 list 裏面放幾百個呢？這顯然是比較不合理且耗內存的！

加權輪詢實現二

基於上面的算法存在的問題，我們考慮用類似佔比的方式來處理。

比如我們配置的權重值為 50、10、30、20，那在橫坐標上表示就是 0_____50_60__80__110。

我們還是用一個 index 去記錄輪詢的位置，如果 index 在 0~50 之間就代表第一個妃子被選中，如果在 50~60 之間就代表第二個妃子被選中……

我們看具體代碼實現：

// 記錄循環的位置  private static Integer indexInteger = 0;    public static void main(String[] args) {     for (int i = 0; i < 11; i++) {         System.out.println(getPrincess2());    }  }    private static String getPrincess2() {     //記錄總權重值     int totalWeight = 0;     for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {         int weight = PrincessConfig.PRINCESS_MAP.get(princess);         totalWeight += weight;    }       // 歸零     if (indexInteger >= totalWeight) {         indexInteger = 0;    }       int index = indexInteger;     String result = null;     for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {         int weight = PrincessConfig.PRINCESS_MAP.get(princess);           // 落在當前區間 直接返回         if (index < weight) {               result = princess;             break;        }           // 沒有落在當前區間 繼續循環         index = index - weight;      }       indexInteger++;     return result;  }

輸出結果與上面的方法一毛一樣：

該加權輪詢算法略複雜於第一種，但是這兩種實現都存在的共同問題是，按照我們目前的配置去輪詢會連續 5 次令妃、再 1 次嫻妃、再 3 次高貴妃……

連續 5 次！就算皇阿瑪再喜歡令妃，怕是令妃也有點吃不消！用計算機術語說也就是負載不是很均衡！

加權輪詢實現三（平滑加權輪詢）

平滑加權輪詢算法就是為了解決上面負載不均衡的情況的，該算法實現起來相對比較複雜！

每個妃子不僅有一個權重值（weight），還有一個會變化的動態權重值（dynamicWeight）來輔助計算。

動態權重值計算邏輯如下：

• 動態權重值 dynamicWeight 初始為 0。
• 每次獲取輪詢獲取目標妃子時先設置 dynamicWeight=dynamicWeight+weight。
• 然後找到所有妃子中動態權重值 dynamicWeight 最大的一個，則為本次輪詢到的目標。
• 將本次輪詢到的目標的 dynamicWeight 設置為 dynamicWeight-totalWeight(總權重值)。

這樣看可能會有點不是很明白，我們來做個推算，假設我們還是有如下配置（配置中只有妃子名稱及對應的權重值）：

/**   * *所有妃子集合   */  public static final Map<String, Integer> PRINCESS_MAP = new LinkedHashMap<String, Integer>() {      {          put("令妃", 5);          put("嫻妃", 1);          put("高貴妃", 3);          put("純妃", 2);      }  };

在上面的配置中總權重值 totalWeight=5+1+3+2 等於 11。

①按照上面算法的第一點，在第一次輪詢目標之前她們的 dynamicWeight 都是0。

因此四位妃子的 weight 和 dynamicWeight 值如下：

②按照上面算法的第二點，在第一次輪詢選中目標的時候 dynamicWeight=dynamicWeight+weight。

變化後四位妃子的 weight 和 dynamicWeight 值如下：

③按照上面算法的第三點，然後找最大的 dynamicWeight，也就是 5，因此第一次輪詢選中的就是令妃。

④按照上面算法的第四點，令妃的 dynamicWeight 需要減去 totalWeight。

變化後四位妃子的 weight 和 dynamicWeight 值如下：

然後第二次輪詢的時候又需要按照算法的第一點設置 dynamicWeight。

設置後四位妃子的 weight 和 dynamicWeight 值如下：

就這樣一直按照算法處理下去，輪詢完 11 次後，所有妃子的 dynamicWeight 又會全部變為 0……

如果大家依然還是有點模糊，我們只能上代碼為敬了！我們需要先定義一個實體，來存放每個妃子及對應的 weight 及 dynamicWeight 屬性：

/**   * *權重實體   *   * @author sullivan   *   */  public class PrincessWeight {      private String princess;      private Integer weight;      private Integer dynamicWeight;      public PrincessWeight(String princess, Integer weight, Integer dynamicWeight) {          super();          this.princess = princess;          this.weight = weight;          this.dynamicWeight = dynamicWeight;      }  }

然後定義兩個全局的對象存放對象：

// 每個妃子及對應的權重實體  private static Map<String, PrincessWeight> weightMap = new HashMap<String, PrincessWeight>();  // 總權重值  private static int totalWeight = 0;

再進行算法的實現：

private static String getPrincess() {      // 初始化妃子及對應的權重實體      if (weightMap.isEmpty()) {          //將配置初始化到map中去          for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {              // 算法的第一點：初始dynamicWeight為0              weightMap.put(princess, new PrincessWeight(princess, PrincessConfig.PRINCESS_MAP.get(princess), 0));              totalWeight += PrincessConfig.PRINCESS_MAP.get(princess);          }      }        // 算法的第二點：設置currentWeight=設置weight+currentWeight      for (PrincessWeight weight : weightMap.values()) {          weight.setDynamicWeight(weight.getWeight() + weight.getDynamicWeight());      }        // 算法的第三點：尋找最大的currentWeight      PrincessWeight maxPrincessWeight = null;      for (PrincessWeight weight : weightMap.values()) {          if (maxPrincessWeight == null || weight.getDynamicWeight() > maxPrincessWeight.getDynamicWeight()) {              maxPrincessWeight = weight;          }      }        // 算法的第四點：最大的dynamicWeight = dynamicWeight-totalWeight      maxPrincessWeight.setDynamicWeight(maxPrincessWeight.getDynamicWeight() - totalWeight);        return maxPrincessWeight.getPrincess();  }

最終輸出如下：

這樣經過 11 次輪詢，令妃同樣出現了 5 次，但是明顯不會再像之前算法那樣連續出現了，會均衡得多！！！如果還有不清楚的，可以去文末的 Github 地址上下載代碼自己調試及理解！

隨機算法

平滑加權輪詢算法能很好的進行負載了！但是皇阿瑪又說了，按照輪詢算法，我自己都能夠推出來每晚侍寢的妃子，不刺激不刺激。

皇帝嘛，總喜歡來些新鮮的刺激的我們也可以理解！還好我們有隨機算法可以解決，每晚都是隨機選一個，讓皇帝無法提前推測，給皇帝足夠的刺激感！

我們依然先定義一個妃子集合如下：

/**   * *所有妃子集合   */  public static final List<String> PRINCESS_LIST = Arrays.asList("令妃", "嫻妃", "高貴妃", "純妃");

然後利用隨機函數去選擇一個目標：

public static void main(String[] args) {      for (int i = 0; i < 10; i++) {          System.out.println(getPrincess());      }  }  /**   * *隨機獲取侍寢妃子   * @return   */  private static String getPrincess() {      SecureRandom rd = new SecureRandom();      int index = rd.nextInt(PrincessConfig.PRINCESS_LIST.size());      return PrincessConfig.PRINCESS_LIST.get(index);  }

因為輸出是隨機的，所以這裡就不貼出來了。如果明白了輪詢算法，隨機算法理解起來也就簡單了，只是在輪詢中用一個全局的 index 去保存每次循環的位置，而在隨機中是每次去隨機出來一個值。

加權隨機算法

加權隨機實現一

加權隨機實現一與上面的加權輪詢實現一的思路幾乎一毛一樣，這裡就直接上代碼了：

public static void main(String[] args) {          for (int i = 0; i < 10; i++) {              System.out.println(getPrincess());          }      }  private static String getPrincess() {      List<String> princessList = new ArrayList<String>();      for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {          int weight = PrincessConfig.PRINCESS_MAP.get(princess);          for (int i = 0; i < weight; i++) {              princessList.add(princess);          }      }      Random rd = new Random();      int index = rd.nextInt(princessList.size());      return princessList.get(index);  }

加權隨機實現二

加權隨機實現二與上面的加權輪詢實現二的思路幾乎一模一樣，這裡也就直接上代碼了：

public static void main(String[] args) {      for (int i = 0; i < 10; i++) {          System.out.println(getPrincess2());      }  }    private static String getPrincess2() {        List<String> princessList = new ArrayList<String>();      int totalWeight = 0;      for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {          int weight = PrincessConfig.PRINCESS_MAP.get(princess);          totalWeight += weight;          for (int i = 0; i < weight; i++) {              princessList.add(princess);          }      }        Random rd = new Random();      int index = rd.nextInt(totalWeight);        String result = null;      for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {          int weight = PrincessConfig.PRINCESS_MAP.get(princess);            // 落在當前區間 直接返回          if (index < weight) {                result = princess;              break;          }            // 沒有落在當前區間 繼續循環          index = index - weight;        }      return result;  }

源地址 hash 算法

我們的工作中開發系統很常見的一個需求就是需要登錄後才能訪問，這就會涉及到 session！

如果我們沒有做 session 共享，那登錄後的 session 信息只會存在我們調用登錄接口的那台服務器上！

按照前面的輪詢算法或者隨機算法，我們同一客戶端的多次請求就會落在不同的服務器上，這樣就會導致部分接口沒權限訪問！

因此我們需要同一個客戶端多次的請求落在同一台服務器上，這裡常見的一種做法是對源地址進行 hash！

到這裡我們也得讓我們的皇阿瑪歇會兒了，回到我們正常的業務場景中。假如我們有服務器配置如下：

/**       * *所有服務器集合       */      public static final List<String> SERVER_IP_LIST = Arrays.asList(          "192.168.1.10",          "192.168.2.20",          "192.168.3.30",          "192.168.4.40");

客戶端訪問的 ip 我也模擬了一個集合：

    /**       * *客戶端ip       */      public static final List<String> CLIENT_IP_LIST = Arrays.asList(          "113.88.97.173",          "106.11.154.33",          "207.46.13.149",          "42.156.137.120",          "203.208.60.0",          "119.39.47.182",          "171.34.179.4",          "111.175.58.52",          "124.235.138.199",          "175.184.166.184");

源地址 hash 算法的思路就是對客戶端的 ip 進行 hash，然後用 hash 值與服務器的數量進行取模，得到需要訪問的服務器的 ip。只要客戶端 ip 不變，那 hash 後的值就是固定的！

實現如下：

public static void main(String[] args) {          for (String clientIp : CLIENT_IP_LIST) {              int index = Math.abs(getHash(clientIp)) % PrincessConfig.SERVER_IP_LIST.size();              String serverIp = PrincessConfig.SERVER_IP_LIST.get(index);              System.out.println(clientIp + "請求的服務器ip為" + serverIp);          }      }

最終輸出如下：

這樣不管執行多少次，相同的客戶端 ip 請求得到的服務器地址都是一樣的！

這種實現很簡單，但也很脆弱！因為我們服務器的數量是可能變化的，今天下線一台機器明天增加一台機器是很常見的！

服務器數量一旦變化，那源地址 hash 之後取模的值可能就變化了，獲取到的服務器的 ip 自然就也會發生變化！

比如我們服務器去掉一台 192.168.4.10 的機器再看下輸出結果：

對比輸出結果我們就能看到，影響幾乎是全局的！那我們能不能有一種方案就算是服務器數量變化，也能減少受影響的客戶端呢？這就需要用到下面的一致性 hash 算法！

一致性 hash 算法

加權輪詢算法實現二中我們講到過把權重值轉化為橫坐標展示，我們這裡是不是也可以用同樣的思路呢？

客戶端 ip 進行 hash 後不就是一個 int32 的數字嘛，那我們就可以把一個 int32 的數字分為幾個段，讓每個服務器負責一個段的請求！

下面為了直觀我們把服務器 192.168.2.10、192.168.2.20、192.168.2.30、192.168.2.40 分別用 IP1、IP2、IP3、IP4 表示，如上圖：

• 如果客戶端 ip 進行 hash 後的值在 0~536870911 之間，那就交給 IP2 服務器處理。
• 如果客戶端 ip 進行 hash 後的值在 536870911~1073741822 之間，那就交給 IP3 服務器處理。
• 如果客戶端 ip 進行 hash 後的值在 1073741822~1610612733 之間，那就交給 IP4 服務器處理。
• 如果客戶端 ip 進行 hash 後的值大於 1610612733 之間，那就交給 IP1 服務器處理。

但是專業一點的表示都會把這個橫坐標掰彎，形成一個環，就叫所謂的 hash 環，如下圖：

這樣看就更直觀了！如果有天 IP4 這台服務器宕機，那原來需要到 IP4 的請求就會全部轉移到 IP1 服務器進行處理。

這樣對部分客戶端的請求依然會有影響，但至少影響也只是局部的，如下圖：

這樣就可以了嗎？我們思考兩個問題：

• 每個服務器在 hash 環上的位置是我們人為的均勻的分配的，這樣經常需要擴容縮容的時候會不會比較難以維護呢？
• IP4 宕機，原本會到 IP4 的請求全部轉移到 IP1，那會不會導致 IP1 的流量不均衡？能不能有一個更均衡一點的方案讓原本到 IP4 的流量均衡的轉移到 IP1、IP2、IP3 呢？

解決問題 1 的方案就是不再人為分配結點所在的位置，而是根據服務器的 ip 計算出 hash 值，再看 hash 值落在環上的哪個位置！

這樣存在的一個問題是每個集群的服務器 ip 都會不同，因此計算後落在環上的位置可能就是不可控的。

如上面四台服務器計算後所在的位置可能會如下圖所示：

很明顯，這種情況是極為不均勻的，會造成數據的傾斜！上面問題 2 的問題其實也是宕機導致的數據傾斜！

環的左上部分那麼空，我們是不是可以把現在的 4 台服務器再根據其他的規則在左上方生成一些結點呢？這樣是不是請求就會稍微均勻一點呢？

這就是所謂的虛擬結點！虛擬結點就是同一個服務器 ip 會根據某個規則生成多個 hashcode，這樣在環上就存在多個結點了。

如下圖所示：

這裡只是模擬了每台服務器有兩個虛擬結點，實際在開發中會更多！這樣就算 IP4 機器掛掉，請求也不會全部壓到某一台服務器上去！

講了這麼多，但實現起來也不難，下面就該上代碼了（服務器配置及請求的客戶端 ip 與源地址 hash 算法部分的一致，這裡就不貼對應的代碼了，直接上算法邏輯）：

//虛擬結點數量100  private static final Integer VIRTUAL_NODES = 100;    public static void main(String[] args) {        // 遍歷服務器ip，生成對應的虛擬結點      TreeMap<Integer, String> nodeMap = new TreeMap<Integer, String>();      for (String serverIp : PrincessConfig.SERVER_IP_LIST) {          for (int i = 0; i < VIRTUAL_NODES; i++) {              nodeMap.put(getHash(serverIp + "VN" + i), serverIp);          }      }        for (String clientIp : CLIENT_IP_LIST) {          //這裡利用的TreeMap的特性，不清楚的可以去自己去了解一下tailMap方法的作用          SortedMap<Integer, String> subMap = nodeMap.tailMap(getHash(clientIp));          Integer firstKey = null;          try {              firstKey = subMap.firstKey();          } catch (Exception e) {          }            if (firstKey == null) {              firstKey = nodeMap.firstKey();          }          System.out.println("請求的服務器ip為" + nodeMap.get(firstKey));      }  }

到此，幾種常用的負載均衡算法及代碼實現都已介紹完畢！還有不清楚可以去同性交友網下載示例代碼自己調試：

https://github.com/sujing910206/load-balance

作者：蘇靜

簡介：有過多年大型互聯網項目的開發經驗，對高並發、分佈式、以及微服務技術有深入的研究及相關實踐經驗。經歷過自學，熱衷於技術研究與分享！格言：始終保持虛心學習的態度！

編輯：陶家龍、孫淑娟