一文帶你了解生産級負載均衡算法

风言闲语

負載均衡介紹

負載均衡，英文名稱爲Load Balance，指由多台服務器以對稱的方式組成一個服務器集合，每台服務器都具有等價的地位，都可以單獨對外提供服務而無須其他服務器的輔助。

通過某種負載分擔技術，將外部發送來的請求均勻分配到對稱結構中的某一台服務器上，而接收到請求的服務器獨立地回應客戶的請求。

負載均衡能夠平均分配客戶請求到服務器陣列，借此提供快速獲取重要數據，解決大量並發訪問服務問題，這種集群技術可以用最少的投資獲得接近于大型主機的性能。

負載均衡方式

負載均衡分爲軟件負載均衡和硬件負載均衡

建議沒有相關軟件使用經驗的同學不要太糾結他們的不同之處，可繼續往下看。

軟件負載均衡

常見的負載均衡軟件有Nginx、LVS、HAProxy。

關于這幾個軟件的特點比較不是本文重點，感興趣同學可以參見博客：

  • （總結）Nginx/LVS/HAProxy負載均衡軟件的優缺點詳解：http://www.ha97.com/5646.html
  • 三大主流軟件負載均衡器對比(LVS 、 Nginx 、Haproxy)：http://www.21yunwei.com/archives/5824

硬件負載均衡

常見的負載均衡硬件有Array、F5。

負載均衡算法

常見的負載均衡算法有：隨機算法、加權輪詢、一致性hash、最小活躍數算法。

千萬別以爲這幾個算法看上去都特別簡單，但其實真正在生産上用到時會遠比你想的複雜

算法前提條件

定義一個服務器列表，每個負載均衡的算法會從中挑出一個服務器作爲算法的結果。

public class ServerIps { private static final List<String> LIST = Arrays.asList( “192.168.0.1”, “192.168.0.2”, “192.168.0.3”, “192.168.0.4”, “192.168.0.5”, “192.168.0.6”, “192.168.0.7”, “192.168.0.8”, “192.168.0.9”, “192.168.0.10” ); }

隨機算法-RandomLoadBalance

先來個最簡單的實現。

public class Random { public static String getServer() { // 生成一個隨機數作爲list的下標值 java.util.Random random = new java.util.Random(); int randomPos = random.nextInt(ServerIps.LIST.size()); return ServerIps.LIST.get(randomPos); } public static void main(String[] args) { // 連續調用10次 for (int i=0; i<10; i++) { System.out.println(getServer()); } } }

運行結果： 192.168.0.3 192.168.0.4 192.168.0.7 192.168.0.1 192.168.0.2 192.168.0.7 192.168.0.3 192.168.0.9 192.168.0.1 192.168.0.1

當調用次數比較少時，Random 産生的隨機數可能會比較集中，此時多數請求會落到同一台服務器上，只有在經過多次請求後，才能使調用請求進行“均勻”分配。調用量少這一點並沒有什麽關系，負載均衡機制不正是爲了應對請求量多的情況嗎，所以隨機算法也是用得比較多的一種算法。

但是，上面的隨機算法適用于每天機器的性能差不多的時候，實際上，生産中可能某些機器的性能更高一點，它可以處理更多的請求，所以，我們可以對每台服務器設置一個權重。

在ServerIps類中增加服務器權重對應關系MAP，權重之和爲50：

public static final Map<String, Integer> WEIGHT_LIST = new HashMap<String, Integer>(); static { // 權重之和爲50 WEIGHT_LIST.put(“192.168.0.1”, 1); WEIGHT_LIST.put(“192.168.0.2”, 8); WEIGHT_LIST.put(“192.168.0.3”, 3); WEIGHT_LIST.put(“192.168.0.4”, 6); WEIGHT_LIST.put(“192.168.0.5”, 5); WEIGHT_LIST.put(“192.168.0.6”, 5); WEIGHT_LIST.put(“192.168.0.7”, 4); WEIGHT_LIST.put(“192.168.0.8”, 7); WEIGHT_LIST.put(“192.168.0.9”, 2); WEIGHT_LIST.put(“192.168.0.10”, 9); }

那麽現在的隨機算法應該要改成權重隨機算法，當調用量比較多的時候，服務器使用的分布應該近似對應權重的分布。

權重隨機算法

簡單的實現思路是，把每個服務器按它所對應的服務器進行複制，具體看代碼更加容易理解

public class WeightRandom { public static String getServer() { // 生成一個隨機數作爲list的下標值 List<String> ips = new ArrayList<String>(); for (String ip : ServerIps.WEIGHT_LIST.keySet()) { Integer weight = ServerIps.WEIGHT_LIST.get(ip); // 按權重進行複制 for (int i=0; i<weight; i++) { ips.add(ip); } } java.util.Random random = new java.util.Random(); int randomPos = random.nextInt(ips.size()); return ips.get(randomPos); } public static void main(String[] args) { // 連續調用10次 for (int i=0; i<10; i++) { System.out.println(getServer()); } } }

運行結果： 192.168.0.8 192.168.0.2 192.168.0.7 192.168.0.10 192.168.0.8 192.168.0.8 192.168.0.4 192.168.0.7 192.168.0.6 192.168.0.8

這種實現方法在遇到權重之和特別大的時候就會比較消耗內存，因爲需要對ip地址進行複制，權重之和越大那麽上文中的ips就需要越多的內存，下面介紹另外一種實現思路。

假設我們有一組服務器 servers = [A, B, C]，他們對應的權重爲 weights = [5, 3, 2]，權重總和爲10。現在把這些權重值平鋪在一維坐標值上，[0, 5) 區間屬于服務器 A，[5, 8) 區間屬于服務器 B，[8, 10) 區間屬于服務器 C。接下來通過隨機數生成器生成一個範圍在 [0, 10) 之間的隨機數，然後計算這個隨機數會落到哪個區間上。比如數字3會落到服務器 A 對應的區間上，此時返回服務器 A 即可。權重越大的機器，在坐標軸上對應的區間範圍就越大，因此隨機數生成器生成的數字就會有更大的概率落到此區間內。只要隨機數生成器産生的隨機數分布性很好，在經過多次選擇後，每個服務器被選中的次數比例接近其權重比例。比如，經過一萬次選擇後，服務器 A 被選中的次數大約爲5000次，服務器 B 被選中的次數約爲3000次，服務器 C 被選中的次數約爲2000次。

假設現在隨機數offset=7：

  1. offset<5 is false，所以不在[0, 5)區間，將offset = offset – 5（offset=2）
  2. offset<3 is true，所以處于[5, 8)區間，所以應該選用B服務器
    實現如下：

public class WeightRandomV2 { public static String getServer() { int totalWeight = 0; boolean sameWeight = true; // 如果所有權重都相等，那麽隨機一個ip就好了 Object[] weights = ServerIps.WEIGHT_LIST.values().toArray(); for (int i = 0; i < weights.length; i++) { Integer weight = (Integer) weights[i]; totalWeight += weight; if (sameWeight && i > 0 && !weight.equals(weights[i – 1])) { sameWeight = false; } } java.util.Random random = new java.util.Random(); int randomPos = random.nextInt(totalWeight); if (!sameWeight) { for (String ip : ServerIps.WEIGHT_LIST.keySet()) { Integer value = ServerIps.WEIGHT_LIST.get(ip); if (randomPos < value) { return ip; } randomPos = randomPos – value; } } return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[new java.util.Random().nextInt(ServerIps.WEIGHT_LIST.size())]; } public static void main(String[] args) { // 連續調用10次 for (int i = 0; i < 10; i++) { System.out.println(getServer()); } } }

這就是另外一種權重隨機算法。

輪詢算法-RoundRobinLoadBalance

簡單的輪詢算法很簡單

public class RoundRobin { // 當前循環的位置 private static Integer pos = 0; public static String getServer() { String ip = null; // pos同步 synchronized (pos) { if (pos >= ServerIps.LIST.size()) { pos = 0; } ip = ServerIps.LIST.get(pos); pos++; } return ip; } public static void main(String[] args) { // 連續調用10次 for (int i = 0; i < 11; i++) { System.out.println(getServer()); } } }

運行結果： 192.168.0.1 192.168.0.2 192.168.0.3 192.168.0.4 192.168.0.5 192.168.0.6 192.168.0.7 192.168.0.8 192.168.0.9 192.168.0.10 192.168.0.1

這種算法很簡單，也很公平，每台服務輪流來進行服務，但是有的機器性能好，所以能者多勞，和隨機算法一下，加上權重這個維度之後，其中一種實現方法就是複制法，這裏就不演示了，這種複制算法的缺點和隨機算法的是一樣的，比較消耗內存，那麽自然就有其他實現方法。我下面來介紹一種算法：

這種算法需要加入一個概念：調用編號，比如第1次調用爲1， 第2次調用爲2， 第100次調用爲100，調用編號是遞增的，所以我們可以根據這個調用編號推算出服務器。

假設我們有三台服務器 servers = [A, B, C]，對應的權重爲 weights = [ 2, 5, 1], 總權重爲8，我們可以理解爲有8台“服務器”，這是8台“不具有並發功能”，其中有2台爲A，5台爲B，1台爲C，一次調用過來的時候，需要按順序訪問，比如有10次調用，那麽服務器調用順序爲AABBBBBCAA，調用編號會越來越大，而服務器是固定的，所以需要把調用編號“縮小”，這裏對調用編號進行取余，除數爲總權重和，比如：

  1. 1號調用，1%8=1；
  2. 2號調用，2%8=2；
  3. 3號調用，3%8=3；
  4. 8號調用，8%8=0；
  5. 9號調用，9%8=1；
  6. 100號調用，100%8=4；
    我們發現調用編號可以被縮小爲0-7之間的8個數字，問題是怎麽根據這個8個數字找到對應的服務器呢？和我們隨機算法類似，這裏也可以把權重想象爲一個坐標軸“0—–2—–7—–8”
  7. 1號調用，1%8=1，offset = 1, offset <= 2 is true，取A；
  8. 2號調用，2%8=2；offset = 2，offset <= 2 is true, 取A;
  9. 3號調用，3%8=3；offset = 3, offset <= 2 is false, offset = offset – 2, offset = 1, offset <= 5，取B
  10. 8號調用，8%8=0；offset = 0, 特殊情況，offset = 8，offset <= 2 is false, offset = offset – 2, offset = 6, offset <= 5 is false, offset = offset – 5, offset = 1, offset <= 1 is true, 取C;
  11. 9號調用，9%8=1；// …
  12. 100號調用，100%8=4； //…
    實現：
    模擬調用編號獲取工具：

public class Sequence { public static Integer num = 0; public static Integer getAndIncrement() { return ++num; } }

public class WeightRoundRobin { private static Integer pos = 0; public static String getServer() { int totalWeight = 0; boolean sameWeight = true; // 如果所有權重都相等，那麽隨機一個ip就好了 Object[] weights = ServerIps.WEIGHT_LIST.values().toArray(); for (int i = 0; i < weights.length; i++) { Integer weight = (Integer) weights[i]; totalWeight += weight; if (sameWeight && i > 0 && !weight.equals(weights[i – 1])) { sameWeight = false; } } Integer sequenceNum = Sequence.getAndIncrement(); Integer offset = sequenceNum % totalWeight; offset = offset == 0 ? totalWeight : offset; if (!sameWeight) { for (String ip : ServerIps.WEIGHT_LIST.keySet()) { Integer weight = ServerIps.WEIGHT_LIST.get(ip); if (offset <= weight) { return ip; } offset = offset – weight; } } String ip = null; synchronized (pos) { if (pos >= ServerIps.LIST.size()) { pos = 0; } ip = ServerIps.LIST.get(pos); pos++; } return ip; } public static void main(String[] args) { // 連續調用11次 for (int i = 0; i < 11; i++) { System.out.println(getServer()); } } }

運行結果： 192.168.0.1 192.168.0.2 192.168.0.2 192.168.0.2 192.168.0.2 192.168.0.2 192.168.0.2 192.168.0.2 192.168.0.2 192.168.0.3 192.168.0.3

但是這種算法有一個缺點：一台服務器的權重特別大的時候，他需要連續的的處理請求，但是實際上我們想達到的效果是，對于100次請求，只要有100*8/50=16次就夠了，這16次不一定要連續的訪問，比如假設我們有三台服務器 servers = [A, B, C]，對應的權重爲 weights = [5, 1, 1] , 總權重爲7，那麽上述這個算法的結果是：AAAAABC，那麽如果能夠是這麽一個結果呢：AABACAA，把B和C平均插入到5個A中間，這樣是比較均衡的了。

我們這裏可以改成平滑加權輪詢。

平滑加權輪詢

思路：每個服務器對應兩個權重，分別爲 weight 和 currentWeight。其中 weight 是固定的，currentWeight 會動態調整，初始值爲0。當有新的請求進來時，遍曆服務器列表，讓它的 currentWeight 加上自身權重。遍曆完成後，找到最大的 currentWeight，並將其減去權重總和，然後返回相應的服務器即可。

一文帶你了解生産級負載均衡算法

  • 哈希值如果需要ip1和ip2之間的，則應該選擇ip2作爲結果；
  • 哈希值如果需要ip2和ip3之間的，則應該選擇ip3作爲結果；
  • 哈希值如果需要ip3和ip4之間的，則應該選擇ip4作爲結果；
  • 哈希值如果需要ip4和ip1之間的，則應該選擇ip1作爲結果；

上面這情況是比較均勻情況，如果出現ip4服務器不存在，那就是這樣了：

一文帶你了解生産級負載均衡算法

其中ip2-1, ip3-1就是虛擬結點，並不能處理節點，而是等同于對應的ip2和ip3服務器。 實際上，這只是處理這種不均衡性的一種思路，實際上就算哈希環本身是均衡的，你也可以增加更多的虛擬節點來使這個環更加平滑，比如：

相關文章:

美食

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。