常見的負(fù)載均衡算法
- 輪詢法(Round Robin)
- 加權(quán)輪詢(Weight Round Robin)
- 隨機算法(Random)
- 源地址HASH算法(當(dāng)同一IP地址客戶端后端服務(wù)器列表不變時嗜愈，每次都會路由到相同的服務(wù)器hashCode % serverListSize)
- 加權(quán)隨機法(Weight Random)
- 最小連接數(shù)法(Least Connections)
隨機（Random）算法
通過系統(tǒng)隨機函數(shù)劝赔，根據(jù)后端服務(wù)器列表的大小值來隨機選取其中一臺進(jìn)行訪問代承。由概率統(tǒng)計理論可以得知焙蹭，隨著調(diào)用量的增大蚌堵，其實際效果越來越接近于平均分配流量到每一臺后端服務(wù)器音比，也就是輪詢的效果
public class RandomTest {
static List<String> list = Arrays.asList("192.168.0.101","192.168.0.102", "192.168.0.103", "192.168.0.104");
public static void main(String[] args) throws InterruptedException {
while (true){
System.err.println(get());
TimeUnit.SECONDS.sleep(1);
}
}
private static synchronized String get(){
// 拷貝服務(wù)列表避免出現(xiàn)由于服務(wù)器上線和下線導(dǎo)致的并發(fā)問題
List<String> result = new ArrayList<>();
result.addAll(list);
Random random = new Random();
int randomPos = random.nextInt(result.size());
return result.get(randomPos);
}
}
基于概率統(tǒng)計的理論畴蹭，吞吐量越大狼荞，隨機算法的效果越接近于輪詢算法的效果轻腺。因此基本可以替代輪詢算法
加權(quán)隨機（Weight Random）法
與加權(quán)輪詢法類似佑女，加權(quán)隨機法也根據(jù)后端服務(wù)器不同的配置和負(fù)載情況赎婚，配置不同的權(quán)重说庭。不同的是康辑，它是按照權(quán)重來隨機選取服務(wù)器的摄欲，而非順序
/**
* 實現(xiàn)方法一
*/
public static String testWeightRandom() {
// 重新創(chuàng)建一個 map，避免出現(xiàn)由于服務(wù)器上線和下線導(dǎo)致的并發(fā)問題
Map<String, Integer> serverMap = new HashMap<>();
serverMap.putAll(serverWeightMap);
// 取得 IP 地址 list
Set<String> keySet = serverMap.keySet();
Iterator<String> it = keySet.iterator();
List<String> serverList = new ArrayList<>();
while (it.hasNext()) {
String server = it.next();
Integer weight = serverMap.get(server);
for (int i = 0; i < weight; i++) {
serverList.add(server);
}
}
Random random = new Random();
int randomPos = random.nextInt(serverList.size());
String server = serverList.get(randomPos);
return server;
}
/**
* 實現(xiàn)方法二
*/
public static String testWeightRandom() {
// 重新創(chuàng)建一個 map疮薇，避免出現(xiàn)由于服務(wù)器上線和下線導(dǎo)致的并發(fā)問題
Map<String, Integer> serverMap = new HashMap<>();
serverMap.putAll(serverWeightMap);
// 計算權(quán)重和
long weightSum = 0;
for (String key : serverMap.keySet()) {
weightSum += serverMap.get(key);
}
// 產(chǎn)生隨機數(shù)
long random = Math.round(Math.random() * weightSum);
long weight = 0;
for (String server : serverMap.keySet()) {
weight += serverMap.get(server);
if (weight >= random) {
return server;
}
}
return serverMap.keySet().iterator().next();
}
輪詢算法(Round-Robin)
輪詢算法是最簡單的一種負(fù)載均衡算法胸墙。它的原理是把來自用戶的請求輪流分配給內(nèi)部的服務(wù)器：從服務(wù)器1開始，直到服務(wù)器N按咒，然后重新開始循環(huán)迟隅。
算法的優(yōu)點是其簡潔性，它無需記錄當(dāng)前所有連接的狀態(tài)，所以它是一種無狀態(tài)調(diào)度智袭；
輪詢算法假設(shè)所有服務(wù)器的處理性能都相同奔缠，不關(guān)心每臺服務(wù)器的當(dāng)前連接數(shù)和響應(yīng)速度。當(dāng)請求服務(wù)間隔時間變化比較大時吼野，輪詢算法容易導(dǎo)致服務(wù)器間的負(fù)載不平衡校哎。所以此種均衡算法適合于服務(wù)器組中的所有服務(wù)器都有相同的軟硬件配置并且平均服務(wù)請求相對均衡的情況
偽代碼：
public class LoadBalanceTest {
static int roundPos = 0;
static List<String> list = new ArrayList<>();
public static void main(String[] args) throws InterruptedException {
while (true){
System.err.println(loadBalanceOfRound());
TimeUnit.SECONDS.sleep(1);
}
}
private static synchronized String loadBalanceOfRound(){
if (roundPos >= list.size() ){
roundPos = 0;
}
return list.get(roundPos++);
}
static {
list.add("192.168.0.101");
list.add("192.168.0.102");
list.add("192.168.0.103");
list.add("192.168.0.104");
}
}
加權(quán)輪詢算法(WeightedRound-Robin)
輪詢算法并沒有考慮每臺服務(wù)器的處理能力，實際中可能并不是這種情況瞳步。由于每臺服務(wù)器的配置闷哆、安裝的業(yè)務(wù)應(yīng)用等不同，其處理能力會不一樣单起。所以加權(quán)輪詢算法的原理就是：根據(jù)服務(wù)器的不同處理能力抱怔，給每個服務(wù)器分配不同的權(quán)值，使其能夠接受相應(yīng)權(quán)值數(shù)的服務(wù)請求嘀倒；
加權(quán)輪詢算法要生成一個服務(wù)器序列屈留，該序列中包含n個服務(wù)器。n是所有服務(wù)器的權(quán)重之和括儒。在該序列中绕沈，每個服務(wù)器的出現(xiàn)的次數(shù)锐想，等于其權(quán)重值帮寻。并且，生成的序列中赠摇，服務(wù)器的分布應(yīng)該盡可能的均勻固逗。比如序列{a, a, a, a, a, b, c}中，前五個請求都會分配給服務(wù)器a藕帜，這就是一種不均勻的分配方法烫罩，更好的序列應(yīng)該是：{a, a, b, a, c, a, a}。
加權(quán)輪詢算法又可分為：
- 普通加權(quán)輪詢算法
- 平滑的加權(quán)輪詢
源地址哈希Hash算法
源地址哈希的思想是獲取客戶端訪問的 IP 地址值洽故，通過哈希函數(shù)計算得到一個數(shù)值贝攒，用該數(shù)值對服務(wù)器列表的大小進(jìn)行取模運算，得到的結(jié)果邊是要訪問的服務(wù)器的序號时甚。采用哈希法進(jìn)行負(fù)載均衡隘弊，同一 IP 地址的客戶端，當(dāng)后端服務(wù)器列表不變時荒适，它每次都會映射到同一臺后端服務(wù)器進(jìn)行訪問
public class RandomTest {
static List<String> list = Arrays.asList("192.168.0.101", "192.168.0.102", "192.168.0.103", "192.168.0.104");
public static void main(String[] args) throws InterruptedException {
while (true) {
System.err.println(get("10.168.0.101"));
TimeUnit.SECONDS.sleep(1);
}
}
private static synchronized String get(String ip) {
// 拷貝服務(wù)列表避免出現(xiàn)由于服務(wù)器上線和下線導(dǎo)致的并發(fā)問題
List<String> result = new ArrayList<>();
result.addAll(list);
int hashCode = System.identityHashCode(ip);
int size = result.size();
int index = hashCode % size;
return result.get(index);
}
}
通過參數(shù)傳入的客戶端 remoteip 參數(shù)梨熙，取得它的哈希值，對服務(wù)器列表的大小取模刀诬，結(jié)果便是選用的服務(wù)器在服務(wù)器列表中的索引值咽扇。該算法保證了相同的客戶端 IP 地址將會被“哈希”到同一臺后端服務(wù)器，直到后端服務(wù)器列表變更质欲。根據(jù)此特性可以在服務(wù)消費者與服務(wù)提供者之間建立有狀態(tài)的 session 會話
hash算法中,存在以下的幾個問題
1.當(dāng)一臺服務(wù)器宕機了或者新添加一臺機器之后,這個時候hashCode % servers.size()需要重新計算hash值, 如果在緩存的環(huán)境中,所有的請求都會涌向數(shù)據(jù)庫服務(wù)器,給數(shù)據(jù)庫服務(wù)器帶來巨大的壓力,可能導(dǎo)致整個系統(tǒng)不可用,形成雪崩效應(yīng)树埠；
2 .當(dāng)新增了一臺性能強的機器后,利用上述的hash算法無法讓,新增的性能強的服務(wù)器多承擔(dān)壓力；
基于上面的幾個問題,提出了hash算法的改進(jìn)：一致性hash算法
最小連接數(shù)（Least Connections）法
最小連接數(shù)算法比較靈活和智能把敞，由于后端服務(wù)器的配置不盡相同弥奸，對于請求的處理有快有慢，它正是根據(jù)后端服務(wù)器當(dāng)前的連接情況奋早，動態(tài)地選取其中當(dāng)前積壓連接數(shù)最小的一臺服務(wù)器來處理當(dāng)前請求盛霎，盡可能地提高后端服務(wù)器的利用效率，將負(fù)載合理地分流到每一臺機器耽装。由于最小連接數(shù)涉及服務(wù)器連接數(shù)的匯總和感知愤炸，設(shè)計與實現(xiàn)比較繁瑣。
