前言
前不久公司有個(gè)需求是任務(wù)需要按照權(quán)重分配來(lái)選擇综膀，當(dāng)時(shí)就想到負(fù)載均衡算法里的加權(quán)隨機(jī)法呻征，因此對(duì)常見(jiàn)的負(fù)載均衡算法做個(gè)總結(jié)谆级。
一洞拨、輪詢(xún)（Round Robin）法
輪詢(xún)就是將請(qǐng)求按順序輪流地分配到后端服務(wù)器上扯罐，它均衡地對(duì)待后端每一臺(tái)服務(wù)器，而不關(guān)心服務(wù)器實(shí)際的連接數(shù)和當(dāng)前的系統(tǒng)負(fù)載烦衣。
// serverWeightMap 表示服務(wù)器地址和權(quán)重的映射
Map<String, Integer> serverWeightMap = new HashMap<>();
serverWeightMap.put("192.168.1.100", 1);
serverWeightMap.put("192.168.1.101", 1);
// 權(quán)重為 4
serverWeightMap.put("192.168.1.102", 4);
serverWeightMap.put("192.168.1.103", 1);
serverWeightMap.put("192.168.1.104", 1);
// 權(quán)重為 3
serverWeightMap.put("192.168.1.105", 3);
serverWeightMap.put("192.168.1.106", 1);
// 權(quán)重為 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);
public static String testRoundRobin() {
// 重新創(chuàng)建一個(gè) map歹河，避免出現(xiàn)由于服務(wù)器上線(xiàn)和下線(xiàn)導(dǎo)致的并發(fā)問(wèn)題
Map<String, Integer> serverMap = new HashMap<>();
serverMap.putAll(serverWeightMap);
// 取得 IP 地址 list
Set<String> keySet = serverMap.keySet();
List<String> keyList = new ArrayList<>();
keyList.addAll(keySet);
String server = null;
Integer pos = 0;
synchronized (pos) {
if (pos >= keySet.size()) {
pos = 0;
}
server = keyList.get(pos);
pos++;
}
return server;
}
由于 serverWeightMap 中的地址列表是動(dòng)態(tài)的，隨時(shí)可能有機(jī)器上線(xiàn)琉挖、下線(xiàn)或者宕機(jī)启泣，因此為了避免可能出現(xiàn)的并發(fā)問(wèn)題，如數(shù)組越界示辈，通過(guò)新建方法內(nèi)的局部變量 serverMap寥茫，先將域變量復(fù)制到線(xiàn)程本地，避免對(duì)多個(gè)線(xiàn)程修改矾麻。這樣會(huì)引入新的問(wèn)題纱耻，復(fù)制以后 serverWeightMap 的修改將無(wú)法反應(yīng)給 serverMap，也就是說(shuō)险耀，在這一輪選擇服務(wù)器的過(guò)程中弄喘，新增服務(wù)器或者下線(xiàn)服務(wù)器，負(fù)載均衡算法中將無(wú)法獲知甩牺。新增比較好處理蘑志，而當(dāng)服務(wù)器下線(xiàn)或者宕機(jī)時(shí)，服務(wù)消費(fèi)者將有可能訪(fǎng)問(wèn)到不存在的地址。因此急但，在服務(wù)消費(fèi)者的實(shí)現(xiàn)端需要考慮該問(wèn)題澎媒，并且進(jìn)行相應(yīng)的容錯(cuò)處理，比如重新發(fā)起一次調(diào)用波桩。
對(duì)于當(dāng)前輪詢(xún)的位置變量 pos戒努，為了保證服務(wù)器選擇的順序性，需要在操作時(shí)對(duì)其加上 synchronized 鎖镐躲，使得在同一時(shí)刻只有一個(gè)線(xiàn)程能夠修改 pos 的值储玫，否則當(dāng) pos 變量被并發(fā)修改時(shí)，則無(wú)法保證服務(wù)器選擇的順序性萤皂，甚至有可能導(dǎo)致 keyList 數(shù)組越界撒穷。
使用輪詢(xún)策略的目的在于，希望做到請(qǐng)求轉(zhuǎn)移的絕對(duì)平衡裆熙，但付出的性能代價(jià)也是相當(dāng)大的桥滨。為了 pos 保證變量的互斥性，需要引入重量級(jí)的悲觀鎖 synchronized弛车，將會(huì)導(dǎo)致該段輪詢(xún)代碼的并發(fā)吞吐量發(fā)生明顯的下降。
二蒲每、隨機(jī)（Random）法
通過(guò)系統(tǒng)隨機(jī)函數(shù)纷跛，根據(jù)后端服務(wù)器列表的大小值來(lái)隨機(jī)選取其中一臺(tái)進(jìn)行訪(fǎng)問(wèn)。由概率統(tǒng)計(jì)理論可以得知邀杏，隨著調(diào)用量的增大贫奠，其實(shí)際效果越來(lái)越接近于平均分配流量到每一臺(tái)后端服務(wù)器，也就是輪詢(xún)的效果望蜡。
public static String testRandom() {
// 重新創(chuàng)建一個(gè) map唤崭，避免出現(xiàn)由于服務(wù)器上線(xiàn)和下線(xiàn)導(dǎo)致的并發(fā)問(wèn)題
Map<String, Integer> serverMap = new HashMap<>();
serverMap.putAll(serverWeightMap);
// 取得 IP 地址 list
Set<String> keySet = serverMap.keySet();
List<String> keyList = new ArrayList<>();
keyList.addAll(keySet);
Random random = new Random();
int randomPos = random.nextInt(keyList.size());
String server = keyList.get(randomPos);
return server;
}
跟前面類(lèi)似，為了避免可能的并發(fā)問(wèn)題脖律，需要將 serverWeightMap 復(fù)制到 serverMap 中谢肾。通過(guò) Random 的 nextInt 方法，取到在 0~keyList.size() 區(qū)間的一個(gè)隨機(jī)值小泉，從而從服務(wù)器列表中隨機(jī)獲取到一臺(tái)服務(wù)器地址芦疏，進(jìn)行返回∥㈡ⅲ基于概率統(tǒng)計(jì)的理論酸茴，吞吐量越大，隨機(jī)算法的效果越接近于輪詢(xún)算法的效果兢交。因此薪捍，基本可以替代輪詢(xún)算法。
三、源地址哈希（Hash）法
源地址哈希的思想是獲取客戶(hù)端訪(fǎng)問(wèn)的 IP 地址值酪穿，通過(guò)哈希函數(shù)計(jì)算得到一個(gè)數(shù)值凳干，用該數(shù)值對(duì)服務(wù)器列表的大小進(jìn)行取模運(yùn)算，得到的結(jié)果邊是要訪(fǎng)問(wèn)的服務(wù)器的序號(hào)昆稿。采用哈希法進(jìn)行負(fù)載均衡纺座，同一 IP 地址的客戶(hù)端，當(dāng)后端服務(wù)器列表不變時(shí)溉潭，它每次都會(huì)映射到同一臺(tái)后端服務(wù)器進(jìn)行訪(fǎng)問(wèn)净响。
public static String testConsumerHash(String remoteip) {
// 重新創(chuàng)建一個(gè) map，避免出現(xiàn)由于服務(wù)器上線(xiàn)和下線(xiàn)導(dǎo)致的并發(fā)問(wèn)題
Map<String, Integer> serverMap = new HashMap<>();
serverMap.putAll(serverWeightMap);
// 取得 IP 地址 list
Set<String> keySet = serverMap.keySet();
List<String> keyList = new ArrayList<>();
keyList.addAll(keySet);
int hashCode = remoteip.hashCode();
int serverListSize = keyList.size();
int serverPos = hashCode % serverListSize;
return keyList.get(serverPos);
}
通過(guò)參數(shù)傳入的客戶(hù)端 remoteip 參數(shù)喳瓣，取得它的哈希值馋贤，對(duì)服務(wù)器列表的大小取模，結(jié)果便是選用的服務(wù)器在服務(wù)器列表中的索引值畏陕。該算法保證了相同的客戶(hù)端 IP 地址將會(huì)被“哈吓渑遥”到同一臺(tái)后端服務(wù)器，直到后端服務(wù)器列表變更惠毁。根據(jù)此特性可以在服務(wù)消費(fèi)者與服務(wù)提供者之間建立有狀態(tài)的 session 會(huì)話(huà)犹芹。
四、加權(quán)輪詢(xún)（Weight Round Robin）法
不同的后端服務(wù)器可能機(jī)器的配置和當(dāng)前系統(tǒng)的負(fù)載并不相同鞠绰，因此它們的抗壓能力也不盡相同腰埂。給配置高、負(fù)載低的機(jī)器配置更高的權(quán)重蜈膨，讓其處理更多的請(qǐng)求屿笼，而低配置、負(fù)載高的機(jī)器翁巍，則給其分配較低的權(quán)重驴一，降低其系統(tǒng)負(fù)載，加權(quán)輪詢(xún)能很好地處理這一問(wèn)題灶壶，并將請(qǐng)求順序且按照權(quán)重分配到后端肝断。
public static String testWeightRoundRobin() {
// 重新創(chuàng)建一個(gè) map，避免出現(xiàn)由于服務(wù)器上線(xiàn)和下線(xiàn)導(dǎo)致的并發(fā)問(wèn)題
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);
}
}
String server = null;
Integer pos = 0;
synchronized (pos) {
if (pos >= serverList.size()) {
pos = 0;
}
server += serverList.get(pos);
pos++;
}
return server;
}
與輪詢(xún)算法類(lèi)似驰凛，只是在獲取服務(wù)器地址之前增加了一段權(quán)重計(jì)算的代碼孝情，根據(jù)權(quán)重的大小，將地址重復(fù)地增加到服務(wù)器地址列表中洒嗤，權(quán)重越大箫荡，該服務(wù)器每輪所獲得的請(qǐng)求數(shù)量越多。
五渔隶、加權(quán)隨機(jī)（Weight Random）法
與加權(quán)輪詢(xún)法類(lèi)似羔挡，加權(quán)隨機(jī)法也根據(jù)后端服務(wù)器不同的配置和負(fù)載情況洁奈，配置不同的權(quán)重。不同的是绞灼，它是按照權(quán)重來(lái)隨機(jī)選取服務(wù)器的利术，而非順序。
/**
* 實(shí)現(xiàn)方法一
*/
public static String testWeightRandom() {
// 重新創(chuàng)建一個(gè) map低矮，避免出現(xiàn)由于服務(wù)器上線(xiàn)和下線(xiàn)導(dǎo)致的并發(fā)問(wèn)題
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;
}
/**
* 實(shí)現(xiàn)方法二
*/
public static String testWeightRandom() {
// 重新創(chuàng)建一個(gè) map印叁，避免出現(xiàn)由于服務(wù)器上線(xiàn)和下線(xiàn)導(dǎo)致的并發(fā)問(wèn)題
Map<String, Integer> serverMap = new HashMap<>();
serverMap.putAll(serverWeightMap);
// 計(jì)算權(quán)重和
long weightSum = 0;
for (String key : serverMap.keySet()) {
weightSum += serverMap.get(key);
}
// 產(chǎn)生隨機(jī)數(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();
}
我們費(fèi)盡心思來(lái)實(shí)現(xiàn)服務(wù)消費(fèi)者請(qǐng)求次數(shù)分配的均衡，我們知道這樣做是沒(méi)錯(cuò)的军掂，可以為后端的多臺(tái)服務(wù)器平均分配工作量轮蜕，最大程度地提高服務(wù)器的利用率，但是蝗锥，實(shí)際情況真的如此嗎跃洛？在實(shí)際情況中，請(qǐng)求次數(shù)的均衡真的能代表負(fù)載的均衡嗎终议？我們必須認(rèn)真地思考這個(gè)問(wèn)題汇竭。從算法實(shí)施的角度來(lái)看，以后端服務(wù)器的視角來(lái)觀察系統(tǒng)的負(fù)載穴张，而非請(qǐng)求發(fā)起方來(lái)觀察细燎。因此，我們得有其它的算法來(lái)實(shí)現(xiàn)可供選擇皂甘，最小連接數(shù)法便屬于此類(lèi)算法找颓。
六、最小連接數(shù)（Least Connections）法
最小連接數(shù)算法比較靈活和智能叮贩，由于后端服務(wù)器的配置不盡相同，對(duì)于請(qǐng)求的處理有快有慢佛析，它正是根據(jù)后端服務(wù)器當(dāng)前的連接情況益老，動(dòng)態(tài)地選取其中當(dāng)前積壓連接數(shù)最小的一臺(tái)服務(wù)器來(lái)處理當(dāng)前請(qǐng)求，盡可能地提高后端服務(wù)器的利用效率寸莫，將負(fù)載合理地分流到每一臺(tái)機(jī)器捺萌。由于最小連接數(shù)涉及服務(wù)器連接數(shù)的匯總和感知，設(shè)計(jì)與實(shí)現(xiàn)比較繁瑣膘茎。
