多种负载均算法及其 Java 代码实现 --转
原文地址：https://www.oschina.net/news/81750/variety-pf-load-balancing-algorithm-and-its-java-code
?
首先給大家介紹下什么是負載均衡（來自百科）
負載均衡建立在現有網絡結構之上，它提供了一種廉價有效透明的方法擴展?網絡設備和?服務器的帶寬、增加?吞吐量、加強網絡數據處理能力、提高網絡的靈活性和可用性。
負載均衡，英文名稱為Load Balance，其意思就是分攤到多個操作單元上進行執行，例如Web?服務器、?FTP服務器、?企業關鍵應用服務器和其它關鍵任務服務器等，從而共同完成工作任務。
本文講述的是"將外部發送來的請求均勻分配到對稱結構中的某一臺服務器上"的各種算法，并以Java代碼演示每種算法的具體實現，OK，下面進入正題，在進入正題前，先寫一個類來模擬Ip列表：
import?java.util.HashMap;/***?@author?ashang.peng@aliyun.com*?@date?二月?07,?2017*/public?class?IpMap???{ ????//?待路由的Ip列表，Key代表Ip，Value代表該Ip的權重 ????public?static?HashMap<String,?Integer>?serverWeightMap?= ????????????new?HashMap<String,?Integer>(); ????static ????{ ????????serverWeightMap.put("192.168.1.100",?1); ????????serverWeightMap.put("192.168.1.101",?1); ????????//?權重為4 ????????serverWeightMap.put("192.168.1.102",?4); ????????serverWeightMap.put("192.168.1.103",?1); ????????serverWeightMap.put("192.168.1.104",?1); ????????//?權重為3 ????????serverWeightMap.put("192.168.1.105",?3); ????????serverWeightMap.put("192.168.1.106",?1); ????????//?權重為2 ????????serverWeightMap.put("192.168.1.107",?2); ????????serverWeightMap.put("192.168.1.108",?1); ????????serverWeightMap.put("192.168.1.109",?1); ????????serverWeightMap.put("192.168.1.110",?1); ????} }?
輪詢（Round Robin）法
輪詢調度算法的原理是每一次把來自用戶的請求輪流分配給內部中的服務器，從1開始，直到N(內部服務器個數)，然后重新開始循環。算法的優點是其簡潔性，它無需記錄當前所有連接的狀態，所以它是一種無狀態調度。
其代碼實現大致如下：
import?java.util.ArrayList; import?java.util.HashMap; import?java.util.Map; import?java.util.Set;/** ?*?@author?ashang.peng@aliyun.com ?*?@date?二月?07,?2017 ?*/ class?RoundRobin???{ ????private?static?Integer?pos?=?0; ????public?static?String?getServer() ????{ ????????//?重建一個Map，避免服務器的上下線導致的并發問題 ????????Map<String,?Integer>?serverMap?= ????????????????new?HashMap<String,?Integer>(); ????????serverMap.putAll(IpMap.serverWeightMap); ????????//?取得Ip地址List ????????Set<String>?keySet?=?serverMap.keySet(); ????????ArrayList<String>?keyList?=?new?ArrayList<String>(); ????????keyList.addAll(keySet); ????????String?server?=?null; ????????synchronized?(pos) ????????{ ????????????if?(pos?>?keySet.size()) ????????????????pos?=?0; ????????????server?=?keyList.get(pos); ????????????pos?++; ????????} ????????return?server; ????} }?
由 于serverWeightMap中的地址列表是動態的，隨時可能有機器上線、下線或者宕機，因此為了避免可能出現的并發問題，方法內部要新建局部變量 serverMap，現將serverMap中的內容復制到線程本地，以避免被多個線程修改。這樣可能會引入新的問題，復制以后 serverWeightMap的修改無法反映給serverMap，也就是說這一輪選擇服務器的過程中，新增服務器或者下線服務器，負載均衡算法將無法 獲知。新增無所謂，如果有服務器下線或者宕機，那么可能會訪問到不存在的地址。因此，服務調用端需要有相應的容錯處理，比如重新發起一次server選擇 并調用。
對于當前輪詢的位置變量pos，為了保證服務器選擇的順序性，需要在操作時對其加鎖，使得同一時刻只能有一個線程可以修改pos的值，否則當pos變量被并發修改，則無法保證服務器選擇的順序性，甚至有可能導致keyList數組越界。
輪詢法的優點在于：試圖做到請求轉移的絕對均衡。
輪詢法的缺點在于：為了做到請求轉移的絕對均衡，必須付出相當大的代價，因為為了保證pos變量修改的互斥性，需要引入重量級的悲觀鎖synchronized，這將會導致該段輪詢代碼的并發吞吐量發生明顯的下降
隨機（Random）法
通過系統的隨機算法，根據后端服務器的列表大小值來隨機選取其中的一臺服務器進行訪問。由概率統計理論可以得知，隨著客戶端調用服務端的次數增多。
其實際效果越來越接近于平均分配調用量到后端的每一臺服務器，也就是輪詢的結果。
隨機法的代碼實現大致如下：
import?java.util.ArrayList; import?java.util.HashMap; import?java.util.Map; import?java.util.Set;/** ?*?@author?ashang.peng@aliyun.com ?*?@date?二月?07,?2017 ?*/ ?class?Random???{ ????public?static?String?getServer() ????{ ????????//?重建一個Map，避免服務器的上下線導致的并發問題??? ????????Map<String,?Integer>?serverMap?= ????????????????new?HashMap<String,?Integer>(); ????????serverMap.putAll(IpMap.serverWeightMap); ????????//?取得Ip地址List??? ????????Set<String>?keySet?=?serverMap.keySet(); ????????ArrayList<String>?keyList?=?new?ArrayList<String>(); ????????keyList.addAll(keySet); ????????java.util.Random?random?=?new?java.util.Random(); ????????int?randomPos?=?random.nextInt(keyList.size()); ????????return?keyList.get(randomPos); ????} }?
整 體代碼思路和輪詢法一致，先重建serverMap，再獲取到server列表。在選取server的時候，通過Random的nextInt方法取 0~keyList.size()區間的一個隨機值，從而從服務器列表中隨機獲取到一臺服務器地址進行返回?；诟怕式y計的理論，吞吐量越大，隨機算法的 效果越接近于輪詢算法的效果。
源地址哈希（Hash）法
源地址哈希 的思想是根據獲取客戶端的IP地址，通過哈希函數計算得到的一個數值，用該數值對服務器列表的大小進行取模運算，得到的結果便是客服端要訪問服務器的序 號。采用源地址哈希法進行負載均衡，同一IP地址的客戶端，當后端服務器列表不變時，它每次都會映射到同一臺后端服務器進行訪問。、
源地址哈希算法的代碼實現大致如下：
import?java.util.ArrayList; import?java.util.HashMap; import?java.util.Map; import?java.util.Set;/** ?*?@author?ashang.peng@aliyun.com ?*?@date?二月?07,?2017 ?*/ ?class?Hash??????{ ????public?static?String?getServer() ????{ ????????//?重建一個Map，避免服務器的上下線導致的并發問題 ????????Map<String,?Integer>?serverMap?= ????????????????new?HashMap<String,?Integer>(); ????????serverMap.putAll(IpMap.serverWeightMap); ????????//?取得Ip地址List ????????Set<String>?keySet?=?serverMap.keySet(); ????????ArrayList<String>?keyList?=?new?ArrayList<String>(); ????????keyList.addAll(keySet); ????????//?在Web應用中可通過HttpServlet的getRemoteIp方法獲取 ????????String?remoteIp?=?"127.0.0.1"; ????????int?hashCode?=?remoteIp.hashCode(); ????????int?serverListSize?=?keyList.size(); ????????int?serverPos?=?hashCode?%?serverListSize; ????????return?keyList.get(serverPos); ????} }?
前兩部分和輪詢法、隨機法一樣就不說了，差別在于路由選擇部分。通過客戶端的ip也就是remoteIp，取得它的Hash值，對服務器列表的大小取模，結果便是選用的服務器在服務器列表中的索引值。
源地址哈希法的優點在于：保證了相同客戶端IP地址將會被哈希到同一臺后端服務器，直到后端服務器列表變更。根據此特性可以在服務消費者與服務提供者之間建立有狀態的session會話。
源 地址哈希算法的缺點在于：除非集群中服務器的非常穩定，基本不會上下線，否則一旦有服務器上線、下線，那么通過源地址哈希算法路由到的服務器是服務器上 線、下線前路由到的服務器的概率非常低，如果是session則取不到session，如果是緩存則可能引發"雪崩"。如果這么解釋不適合明白，可以看我 之前的一篇文章MemCache超詳細解讀，一致性Hash算法部分。
加權輪詢（Weight Round Robin）法
不 同的后端服務器可能機器的配置和當前系統的負載并不相同，因此它們的抗壓能力也不相同。給配置高、負載低的機器配置更高的權重，讓其處理更多的請；而配置 低、負載高的機器，給其分配較低的權重，降低其系統負載，加權輪詢能很好地處理這一問題，并將請求順序且按照權重分配到后端。加權輪詢法的代碼實現大致如 下：
import?java.util.*;/***?@author?ashang.peng@aliyun.com*?@date?二月?07,?2017*/ class?WeightRoundRobin???{ ????private?static?Integer?pos; ????public?static?String?getServer() ????{ ????????//?重建一個Map，避免服務器的上下線導致的并發問題 ????????Map<String,?Integer>?serverMap?= ????????????????new?HashMap<String,?Integer>(); ????????serverMap.putAll(IpMap.serverWeightMap); ????????//?取得Ip地址List ????????Set<String>?keySet?=?serverMap.keySet(); ????????Iterator<String>?iterator?=?keySet.iterator(); ????????List<String>?serverList?=?new?ArrayList<String>(); ????????while?(iterator.hasNext()) ????????{ ????????????String?server?=?iterator.next(); ????????????int?weight?=?serverMap.get(server); ????????????for?(int?i?=?0;?i?<?weight;?i++) ????????????????serverList.add(server); ????????} ????????String?server?=?null; ????????synchronized?(pos) ????????{ ????????????if?(pos?>?keySet.size()) ????????????????pos?=?0; ????????????server?=?serverList.get(pos); ????????????pos?++; ????????} ????????return?server; ????} }?
與輪詢法類似，只是在獲取服務器地址之前增加了一段權重計算的代碼，根據權重的大小，將地址重復地增加到服務器地址列表中，權重越大，該服務器每輪所獲得的請求數量越多。
加權隨機（Weight Random）法
與加權輪詢法一樣，加權隨機法也根據后端機器的配置，系統的負載分配不同的權重。不同的是，它是按照權重隨機請求后端服務器，而非順序。
import?java.util.*;/***?@author?ashang.peng@aliyun.com*?@date?二月?07,?2017*/class?WeightRandom???{ ????public?static?String?getServer() ????{ ????????//?重建一個Map，避免服務器的上下線導致的并發問題 ????????Map<String,?Integer>?serverMap?= ????????????????new?HashMap<String,?Integer>(); ????????serverMap.putAll(IpMap.serverWeightMap); ????????//?取得Ip地址List ????????Set<String>?keySet?=?serverMap.keySet(); ????????Iterator<String>?iterator?=?keySet.iterator(); ????????List<String>?serverList?=?new?ArrayList<String>(); ????????while?(iterator.hasNext()) ????????{ ????????????String?server?=?iterator.next(); ????????????int?weight?=?serverMap.get(server); ????????????for?(int?i?=?0;?i?<?weight;?i++) ????????????????serverList.add(server); ????????} ????????java.util.Random?random?=?new?java.util.Random(); ????????int?randomPos?=?random.nextInt(serverList.size()); ????????return?serverList.get(randomPos); ????} }?
這段代碼相當于是隨機法和加權輪詢法的結合，比較好理解，就不解釋了。
最小連接數（Least Connections）法
最小連接數算法比較靈活和智能，由于后端服務器的配置不盡相同，對于請求的處理有快有慢，它是根據后端服務器當前的連接情況，動態地選取其中當前
積壓連接數最少的一臺服務器來處理當前的請求，盡可能地提高后端服務的利用效率，將負責合理地分流到每一臺服務器。
前面幾種方法費盡心思來實現服務消費者請求次數分配的均衡，當然這么做是沒錯的，可以為后端的多臺服務器平均分配工作量，最大程度地提高服務器的利用率，但是實際情況是否真的如此？實際情況中，請求次數的均衡真的能代表負載的均衡嗎？這是一個值得思考的問題。
上面的問題，再換一個角度來說就是：以后端服務器的視角來觀察系統的負載，而非請求發起方來觀察。最小連接數法便屬于此類。
最 小連接數算法比較靈活和智能，由于后端服務器的配置不盡相同，對于請求的處理有快有慢，它正是根據后端服務器當前的連接情況，動態地選取其中當前積壓連接 數最少的一臺服務器來處理當前請求，盡可能地提高后端服務器的利用效率，將負載合理地分流到每一臺機器。由于最小連接數設計服務器連接數的匯總和感知，設 計與實現較為繁瑣，此處就不說它的實現了。
附了一個說明“NGINX的實現原因，大家可以看看"：
blog.csdn.net
轉載于:https://www.cnblogs.com/davidwang456/articles/6382327.html
總結
以上是生活随笔為你收集整理的多种负载均算法及其 Java 代码实现 --转的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Spring Cloud Netflix
- 下一篇： Can't access RabbitM