轉至小眼睛聊技術

概述

「負載均衡」是指，通過一定的算法使請求可以均勻的寵幸服務提供方，做到雨露均沾。市面上，軟件硬件產品一大把，解決的最最核心的問題都是選誰。

分類

按實現方式，可以分為硬件負載均衡（如 F5 、A10）、軟件負載均衡（如 LVS、Nginx、HAProxy）、DNS 負載均衡。硬件負載均衡和DNS 負載均衡我們不過多關注，重點看一下軟件負載均衡。

軟件負載均衡又分四層和七層負載均衡，四層負載均衡就是在網絡層利用 IP 地址端口進行請求的轉發，基本上就是起個轉發分配作用。而七層負載均衡就是可以根據訪問用戶的 HTTP 請求頭、URL 信息將請求轉發到特定的主機。LVS 為四層負載均衡。Nginx、HAProxy 可四可七。

除了專用硬件和 Nginx 這種專業軟件提供負載均衡外，在代碼中直接實現也是種常見的方式。比如 Spring Cloud 體系中的 Ribbon 組件提供了輪詢、隨機、根據響應時間加權幾種負載策略，比如使用 Memcached 集群時通常會在 client 中采用 hash 取模或者一致性哈希來使數據均勻分布。

常見算法

最常見的負載均衡算法有隨機、加權隨機、輪詢、最小連接數、一致性哈希這幾種，我們分別看看用 JAVA 代碼如何實現。為了方便對比，我們定義了 Balanceable 接口，假定所有參與負載均衡處理的 server 都實現了 Balanceable 接口。

1. 隨機（Random）

根據后端服務器列表的大小值來隨機選擇其中一臺進行訪問，代碼如下：

 public Balanceable choice(Balanceable[] servers) {
     int index = (int) (Math.random() * servers.length);
     return servers[index];
 }

優點：實現簡單，通過系統隨機函數隨機選擇其中一臺進行訪問

缺點：不適用后端機器承載能力不一致的情況

2. 權重隨機（Weighted Random）

各個節點帶有不同的權重，雖然隨機選擇但是期望不同權重的節點被選擇的幾率不一樣，權重高的被選中的幾率大，權重低的被選中的幾率小。代碼如下：

 public Balanceable choice(Balanceable[] servers) {
     int seed = 0;
     for (Balanceable server : servers) {
         seed += server.getWeight();
     }
     int random = r.nextInt(seed);
     Collections.sort(Arrays.asList(servers));
     int tmp = 0;
     for (Balanceable server : servers) {
         tmp += server.getWeight();
         if (tmp >= random) {
             return server;
         }
     }
     return null;
 }

假設有三個節點 A、B、C 它們的權重分別是 3、2、4 ，那么就可以這樣表示

取直線上的任意一個點，這個點屬于直線上哪個節點的區域內就是選擇了哪個節點：

所有權重相加得到 S（其實就是直線的長度）
從 [0, S) 的區間內取一個隨機數 R（直線中隨機選擇一個點）
遍歷節點列表，把訪問過的節點的權重相加得到 V，比較 V 與 R 的值，如果 V > R 當前節點即為選中的節點。（查找 R 在直線中的位置屬于哪個節點所在的區域）

優點：實現簡單，采用權重改變了被選中的概率

缺點：不適用后端機器承載能力不一致的情況

3. 輪詢（Round Robin）

輪詢指的是從已有的后端節點列表中按順序依次選擇一個節點出來提供服務。代碼如下：

 
 Integer pos = 0;
 
 public Balanceable choice(Balanceable[] servers) {
     Balanceable result = null;
     synchronized(pos) {
         if (pos >= servers.length){
             pos = 0;
         }
         result = servers[pos];
         pos++;
     }
     return result;
 }

把所有待選擇的機器看做是一個個的點，所有點串起來一個圓。想象一下，輪詢就是對圓上的每一個點，順時針遍歷，在每個節點上停留一下。我們通過請求的次數 pos ，來實現順時針選擇。需要修改 pos 的線程，只有獲取到鎖才能對該值做修改，當該值大于等于服務器列表長度時，重新從 0 開始遍歷，達到循環一周的目的。

優點：相對來說請求可以做到絕對平衡

缺點：為了絕對平衡，需要保證 pos 修改時的互斥性，引入了同步鎖會帶來性能下降

4. 最小連接數（Least Connections）

從已有的后端列表中，選擇正在處理的連接數 / 請求數最少的節點出來提供服務。既然要判斷連接數 / 請求數，那么每個節點都需要保存一個正在處理的連接數 / 請求數的信息，然后選取節點的時候判斷一下，選擇連接數最少的那個節點。代碼如下：

 public Balanceable choice(Balanceable[] servers) {
     int length = servers.size();                                                                                      
     int leastActive = -1;
     int leastCount = 0;
     int[] leastIndexs = new int[length];
     int totalWeight = 0;
     int firstWeight = 0;
     boolean sameWeight = true;
     for (int i = 0; i < length; i++) {                                                                                                                            
         Balanceable invoker = servers[i];
         int active = status.getStatus(servers).getActive();
         int weight = server.getWeight();
         
         if (leastActive == -1 || active < leastActive) {
             leastActive = active;
             leastCount = 1;
             leastIndexs[0] = i;
             totalWeight = weight;
             firstWeight = weight;
             sameWeight = true;
         } else if (active == leastActive) {
             leastIndexs[leastCount++] = i;
             totalWeight += weight;
             if (sameWeight && i > 0
                     && weight != firstWeight) {
                 sameWeight = false;
             }
         }
     }
     
     if (leastCount == 1) {    
         return servers[leastIndexs[0]];
     }
     if (!sameWeight && totalWeight > 0) {    
         int offsetWeight = random.nextInt(totalWeight);
         for (int i = 0; i < leastCount; i++) {
             int leastIndex = leastIndexs[i];
             offsetWeight -= getWeight(servers[leastIndex]);
             if (offsetWeight <= 0)
                 return servers[leastIndex];
         }
     }
     
     return servers[leastIndexs[random.nextInt(leastCount)]];
 }

首先找到服務提供者當前最小的活躍連接數，如果一個服務提供者的服務連接數比其他的都要小，則選擇這個活躍連接數最小的服務提供者發起調用，如果存在多個服務提供者的活躍連接數，并且是最小的，則在這些服務提供者之間選擇加權隨機算法選擇一個服務提供者。

優點：根據服務器當前的請求處理情況，動態分配

缺點：算法實現相對復雜，需要監控服務器請求連接數

5. 一致性哈希（Consistent Hash）

根據后端節點的某個固定屬性計算 hash 值，然后把所有節點計算出來的 hash 值組成一個 hash 環。請求過來的時候根據請求的特征計算該特征的 hash 值（使用跟計算后端節點 hash 值相同的 hash 函數進行計算），然后順時針查找 hash 環上的 hash 值，第一個比請求特征的 hash 值大的 hash 值所對應的節點即為被選中的節點。

某一部分節點發生故障時，或者新的節點動態的增加進來時都只需重定位環空間中的一小部分數據，具有較好的容錯性和可擴展性。

構造哈希環

 public static TreeMap<Long, String> populateConsistentBuckets(
    String... servers) {
 // store buckets in tree map
     TreeMap<Long, String> consistentBuckets = new TreeMap<Long, String>();
 
     MessageDigest md5 = MD5.get();
     int totalWeight = servers.length;
 
     for (int i = 0; i < servers.length; i++) {
         int thisWeight = 1;
 
         double factor = Math
             .floor(((double) (40 * servers.length * thisWeight))
                    / (double) totalWeight);
 
         for (long j = 0; j < factor; j++) {
             byte[] d = md5.digest((servers[i] + "-" + j).getBytes());
             for (int h = 0; h < 4; h++) {
                 Long k = ((long) (d[3 + h * 4] & 0xFF) << 24)
                     | ((long) (d[2 + h * 4] & 0xFF) << 16)
                     | ((long) (d[1 + h * 4] & 0xFF) << 8)
                     | ((long) (d[0 + h * 4] & 0xFF));
 
                 consistentBuckets.put(k, servers[i]);
             }
         }
     }
     return consistentBuckets;
 }

上面的 hash 還有一個問題，就是節點的 hash 值不一定是均勻的分布在 hash 環上的，這樣就會導致部分節點上承受太多的請求。解決辦法是引入虛擬節點：每個節點重復 n 次，把這些虛擬節點的 hash 值（跟實際節點的 hash 值不一樣，也就是說需要在節點屬性中加點東西保證每個虛擬節點跟實際節點的 hash 值不一樣，互相之間也要不一樣）也加入到 hash 環中以此來保證分布更均勻。

從環中找到合適的節點：

 public static final Long getBucket(TreeMap<Long, String> buckets, Long hv) {
     SortedMap<Long, String> t = buckets.tailMap(hv);
     return (t.isEmpty()) ? buckets.firstKey() : t.firstKey();
 }

這里有一個需要注意的點那就是臨界值的處理問題：可能會有部分請求處在 hash 環上最后一個點的后面，即 hash 環上找不到一個比請求特征的 hash 值更大的一個 hash。對于這種無法在 hash 環上找到對應的下一個節點的情況，一般是把 hash 環上的第一個 hash 值作為被選中的點，即進行第二圈的順時針查找。

優點：具有較好的容錯性和可擴展性，節點加入或者去除，只有少量數據需要遷移

缺點：沒有解決熱點問題，會出現部分節點需要處理大量請求