Java實作多種負載平衡演算法
- 怪我咯原創
- 2017-04-05 16:10:401267瀏覽
首先介紹給大家甚麼是負載平衡（來自百科）
# 負載平衡建立在現有網路結構之上，它提供了一種廉價有效透明的方法擴展網路設備和伺服器的頻寬、增加吞吐量、加強網路資料處理能力、提高網路的靈活性和可用性。
負載平衡，英文名稱為Load Balance，其意思是分攤到多個作業單元上進行執行，例如Web 伺服器、 FTP伺服器、 企業關鍵應用伺服器和其它關鍵任務伺服器等，從而共同完成工作任務。
本文講述的是"將外部發送來的請求均勻分配到對稱結構中的某一台伺服器上"的各種演算法，並以Java程式碼演示每種演算法的具體實現，OK，下面進入正題，在進入正題前，先寫一個類別來模擬Ip列表：
import java.util.HashMap;
/**
* @author [email protected]
* @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 [email protected]
* @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 keySet = serverMap.keySet();
ArrayList keyList = new ArrayList();
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 [email protected]
* @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 keySet = serverMap.keySet();
ArrayList keyList = new ArrayList();
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()區間的一個隨機值，從而從伺服器清單中隨機取得到一台伺服器位址進行回傳。基於機率統計的理論，吞吐量越大，隨機演算法的效果越接近輪詢演算法的效果。
來源位址雜湊（Hash）法
來源位址雜湊的想法是根據取得客戶端的IP位址，透過雜湊函數計算得到的數值，用該數值對伺服器列表的大小進行取模運算，得到的結果就是客服端要存取伺服器的序號。採用來源位址雜湊法進行負載平衡，同一IP位址的客戶端，當後端伺服器清單不變時，它每次都會對應到同一台後端伺服器進行存取。
來源位址雜湊演算法的程式碼實作大致如下：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/**
* @author [email protected]
* @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 keySet = serverMap.keySet();
ArrayList keyList = new ArrayList();
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 [email protected]
* @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 keySet = serverMap.keySet();
Iterator iterator = keySet.iterator();
List serverList = new ArrayList();
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 [email protected]
* @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 keySet = serverMap.keySet();
Iterator iterator = keySet.iterator();
List serverList = new ArrayList();
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）法
最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前
积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将负责合理地分流到每一台服务器。
前面几种方法费尽心思来实现服务消费者请求次数分配的均衡，当然这么做是没错的，可以为后端的多台服务器平均分配工作量，最大程度地提高服务器的利用率，但是实际情况是否真的如此？实际情况中，请求次数的均衡真的能代表负载的均衡吗？这是一个值得思考的问题。
上面的问题，再换一个角度来说就是：以后端服务器的视角来观察系统的负载，而非请求发起方来观察。最小连接数法便属于此类。
最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它正是根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前请求，尽可能地提高后端服务器的利用效率，将负载合理地分流到每一台机器。由于最小连接数设计服务器连接数的汇总和感知，设计与实现较为繁琐，此处就不说它的实现了。
以上是Java實作多種負載平衡演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！