|
負(fù)載均衡介紹 負(fù)載均衡，英文名稱為L(zhǎng)oad Balance，指由多臺(tái)服務(wù)器以對(duì)稱的方式組成一個(gè)服務(wù)器集合，每臺(tái)服務(wù)器都具有等價(jià)的地位，都可以單獨(dú)對(duì)外提供服務(wù)而無須其他服務(wù)器的輔助。通過某種負(fù)載分擔(dān)技術(shù)，將外部發(fā)送來的請(qǐng)求均勻分配到對(duì)稱結(jié)構(gòu)中的某一臺(tái)服務(wù)器上，而接收到請(qǐng)求的服務(wù)器獨(dú)立地回應(yīng)客戶的請(qǐng)求。負(fù)載均衡能夠平均分配客戶請(qǐng)求到服務(wù)器陣列，借此提供快速獲取重要數(shù)據(jù)，解決大量并發(fā)訪問服務(wù)問題，這種集群技術(shù)可以用最少的投資獲得接近于大型主機(jī)的性能。 一、負(fù)載均衡方式 負(fù)載均衡分為軟件負(fù)載均衡和硬件負(fù)載均衡建議沒有相關(guān)軟件使用經(jīng)驗(yàn)的同學(xué)不要太糾結(jié)他們的不同之處，可繼續(xù)往下看。 （1）軟件負(fù)載均衡 常見的負(fù)載均衡軟件有Nginx、LVS、HAProxy。 關(guān)于這幾個(gè)軟件的特點(diǎn)比較不是本文重點(diǎn)，感興趣同學(xué)可以參見博客： （2）硬件負(fù)載均衡 常見的負(fù)載均衡硬件有Array、F5。 二、負(fù)載均衡算法 常見的負(fù)載均衡算法有：隨機(jī)算法、加權(quán)輪詢、一致性hash、最小活躍數(shù)算法。 千萬別以為這幾個(gè)算法看上去都特別簡(jiǎn)單，但其實(shí)真正在生產(chǎn)上用到時(shí)會(huì)遠(yuǎn)比你想的復(fù)雜。 算法前提條件 定義一個(gè)服務(wù)器列表，每個(gè)負(fù)載均衡的算法會(huì)從中挑出一個(gè)服務(wù)器作為算法的結(jié)果。 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"
);
}
1、隨機(jī)算法-RandomLoadBalance 先來個(gè)最簡(jiǎn)單的實(shí)現(xiàn)。 public class Random {
public static String getServer() {
// 生成一個(gè)隨機(jī)數(shù)作為list的下標(biāo)值
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) {
// 連續(xù)調(diào)用10次
for (int i=0; i<10; i ) {
System.out.println(getServer());
}
}
}
運(yùn)行結(jié)果： 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 當(dāng)調(diào)用次數(shù)比較少時(shí)，Random 產(chǎn)生的隨機(jī)數(shù)可能會(huì)比較集中，此時(shí)多數(shù)請(qǐng)求會(huì)落到同一臺(tái)服務(wù)器上，只有在經(jīng)過多次請(qǐng)求后，才能使調(diào)用請(qǐng)求進(jìn)行“均勻”分配。調(diào)用量少這一點(diǎn)并沒有什么關(guān)系，負(fù)載均衡機(jī)制不正是為了應(yīng)對(duì)請(qǐng)求量多的情況嗎，所以隨機(jī)算法也是用得比較多的一種算法。 但是，上面的隨機(jī)算法適用于每天機(jī)器的性能差不多的時(shí)候，實(shí)際上，生產(chǎn)中可能某些機(jī)器的性能更高一點(diǎn)，它可以處理更多的請(qǐng)求，所以，我們可以對(duì)每臺(tái)服務(wù)器設(shè)置一個(gè)權(quán)重。 在ServerIps類中增加服務(wù)器權(quán)重對(duì)應(yīng)關(guān)系MAP，權(quán)重之和為50： public static final Map<String, Integer> WEIGHT_LIST = new HashMap<String, Integer>();
static {
// 權(quán)重之和為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);
}
那么現(xiàn)在的隨機(jī)算法應(yīng)該要改成權(quán)重隨機(jī)算法，當(dāng)調(diào)用量比較多的時(shí)候，服務(wù)器使用的分布應(yīng)該近似對(duì)應(yīng)權(quán)重的分布。 2、權(quán)重隨機(jī)算法 簡(jiǎn)單的實(shí)現(xiàn)思路是，把每個(gè)服務(wù)器按它所對(duì)應(yīng)的服務(wù)器進(jìn)行復(fù)制，具體看代碼更加容易理解 public class WeightRandom {
public static String getServer() {
// 生成一個(gè)隨機(jī)數(shù)作為list的下標(biāo)值
List<String> ips = new ArrayList<String>();
for (String ip : ServerIps.WEIGHT_LIST.keySet()) {
Integer weight = ServerIps.WEIGHT_LIST.get(ip);
// 按權(quán)重進(jìn)行復(fù)制
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) {
// 連續(xù)調(diào)用10次
for (int i=0; i<10; i ) {
System.out.println(getServer());
}
}
}
運(yùn)行結(jié)果： 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 這種實(shí)現(xiàn)方法在遇到權(quán)重之和特別大的時(shí)候就會(huì)比較消耗內(nèi)存，因?yàn)樾枰獙?duì)ip地址進(jìn)行復(fù)制，權(quán)重之和越大那么上文中的ips就需要越多的內(nèi)存，下面介紹另外一種實(shí)現(xiàn)思路。 假設(shè)我們有一組服務(wù)器 servers = [A, B, C]，他們對(duì)應(yīng)的權(quán)重為 weights = [5, 3, 2]，權(quán)重總和為10?，F(xiàn)在把這些權(quán)重值平鋪在一維坐標(biāo)值上，[0, 5) 區(qū)間屬于服務(wù)器 A，[5, 8) 區(qū)間屬于服務(wù)器 B，[8, 10) 區(qū)間屬于服務(wù)器 C。接下來通過隨機(jī)數(shù)生成器生成一個(gè)范圍在 [0, 10) 之間的隨機(jī)數(shù)，然后計(jì)算這個(gè)隨機(jī)數(shù)會(huì)落到哪個(gè)區(qū)間上。比如數(shù)字3會(huì)落到服務(wù)器 A 對(duì)應(yīng)的區(qū)間上，此時(shí)返回服務(wù)器 A 即可。權(quán)重越大的機(jī)器，在坐標(biāo)軸上對(duì)應(yīng)的區(qū)間范圍就越大，因此隨機(jī)數(shù)生成器生成的數(shù)字就會(huì)有更大的概率落到此區(qū)間內(nèi)。只要隨機(jī)數(shù)生成器產(chǎn)生的隨機(jī)數(shù)分布性很好，在經(jīng)過多次選擇后，每個(gè)服務(wù)器被選中的次數(shù)比例接近其權(quán)重比例。比如，經(jīng)過一萬次選擇后，服務(wù)器 A 被選中的次數(shù)大約為5000次，服務(wù)器 B 被選中的次數(shù)約為3000次，服務(wù)器 C 被選中的次數(shù)約為2000次。 假設(shè)現(xiàn)在隨機(jī)數(shù)offset=7： 1、offset<5 is false，所以不在[0, 5)區(qū)間，將offset = offset - 5（offset=2） 2、offset<3 is true，所以處于[5, 8)區(qū)間，所以應(yīng)該選用B服務(wù)器 實(shí)現(xiàn)如下： public class WeightRandomV2 {
public static String getServer() {
int totalWeight = 0;
boolean sameWeight = true; // 如果所有權(quán)重都相等，那么隨機(jī)一個(gè)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) {
// 連續(xù)調(diào)用10次
for (int i = 0; i < 10; i ) {
System.out.println(getServer());
}
}
}
這就是另外一種權(quán)重隨機(jī)算法。 3、輪詢算法-RoundRobinLoadBalance 簡(jiǎn)單的輪詢算法很簡(jiǎn)單 public class RoundRobin {
// 當(dāng)前循環(huán)的位置
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) {
// 連續(xù)調(diào)用10次
for (int i = 0; i < 11; i ) {
System.out.println(getServer());
}
}
}
運(yùn)行結(jié)果： 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 這種算法很簡(jiǎn)單，也很公平，每臺(tái)服務(wù)輪流來進(jìn)行服務(wù)，但是有的機(jī)器性能好，所以能者多勞，和隨機(jī)算法一下，加上權(quán)重這個(gè)維度之后，其中一種實(shí)現(xiàn)方法就是復(fù)制法，這里就不演示了，這種復(fù)制算法的缺點(diǎn)和隨機(jī)算法的是一樣的，比較消耗內(nèi)存，那么自然就有其他實(shí)現(xiàn)方法。我下面來介紹一種算法： 這種算法需要加入一個(gè)概念：調(diào)用編號(hào)，比如第1次調(diào)用為1， 第2次調(diào)用為2， 第100次調(diào)用為100，調(diào)用編號(hào)是遞增的，所以我們可以根據(jù)這個(gè)調(diào)用編號(hào)推算出服務(wù)器。 假設(shè)我們有三臺(tái)服務(wù)器 servers = [A, B, C]，對(duì)應(yīng)的權(quán)重為 weights = [ 2, 5, 1], 總權(quán)重為8，我們可以理解為有8臺(tái)“服務(wù)器”，這是8臺(tái)“不具有并發(fā)功能”，其中有2臺(tái)為A，5臺(tái)為B，1臺(tái)為C，一次調(diào)用過來的時(shí)候，需要按順序訪問，比如有10次調(diào)用，那么服務(wù)器調(diào)用順序?yàn)锳ABBBBBCAA，調(diào)用編號(hào)會(huì)越來越大，而服務(wù)器是固定的，所以需要把調(diào)用編號(hào)“縮小”，這里對(duì)調(diào)用編號(hào)進(jìn)行取余，除數(shù)為總權(quán)重和，比如：
1、1號(hào)調(diào)用，1%8=1； 2、2號(hào)調(diào)用，2%8=2； 3、3號(hào)調(diào)用，3%8=3； 4、8號(hào)調(diào)用，8%8=0； 5、9號(hào)調(diào)用，9%8=1； 6、100號(hào)調(diào)用，100%8=4； 我們發(fā)現(xiàn)調(diào)用編號(hào)可以被縮小為0-7之間的8個(gè)數(shù)字，問題是怎么根據(jù)這個(gè)8個(gè)數(shù)字找到對(duì)應(yīng)的服務(wù)器呢？和我們隨機(jī)算法類似，這里也可以把權(quán)重想象為一個(gè)坐標(biāo)軸“0-----2-----7-----8” 1、1號(hào)調(diào)用，1%8=1，offset = 1, offset <= 2 is true，取A； 2、2號(hào)調(diào)用，2%8=2；offset = 2，offset <= 2 is true, 取A; 3、3號(hào)調(diào)用，3%8=3；offset = 3, offset <= 2 is false, offset = offset - 2, offset = 1, offset <= 5，取B 4、8號(hào)調(diào)用，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; 5、9號(hào)調(diào)用，9%8=1；// … 100號(hào)調(diào)用，100%8=4；//… 實(shí)現(xiàn)： 模擬調(diào)用編號(hào)獲取工具： 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; // 如果所有權(quán)重都相等，那么隨機(jī)一個(gè)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) {
// 連續(xù)調(diào)用11次
for (int i = 0; i < 11; i ) {
System.out.println(getServer());
}
}
}
運(yùn)行結(jié)果： 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 但是這種算法有一個(gè)缺點(diǎn)：一臺(tái)服務(wù)器的權(quán)重特別大的時(shí)候，他需要連續(xù)的的處理請(qǐng)求，但是實(shí)際上我們想達(dá)到的效果是，對(duì)于100次請(qǐng)求，只要有100*8/50=16次就夠了，這16次不一定要連續(xù)的訪問，比如假設(shè)我們有三臺(tái)服務(wù)器 servers = [A, B, C]，對(duì)應(yīng)的權(quán)重為 weights = [5, 1, 1] , 總權(quán)重為7，那么上述這個(gè)算法的結(jié)果是：AAAAABC，那么如果能夠是這么一個(gè)結(jié)果呢：AABACAA，把B和C平均插入到5個(gè)A中間，這樣是比較均衡的了。 我們這里可以改成平滑加權(quán)輪詢，這里先講一下思路： 每個(gè)服務(wù)器對(duì)應(yīng)兩個(gè)權(quán)重，分別為 weight 和 currentWeight。其中 weight 是固定的，currentWeight 會(huì)動(dòng)態(tài)調(diào)整，初始值為0。當(dāng)有新的請(qǐng)求進(jìn)來時(shí)，遍歷服務(wù)器列表，讓它的 currentWeight 加上自身權(quán)重。遍歷完成后，找到最大的 currentWeight，并將其減去權(quán)重總和，然后返回相應(yīng)的服務(wù)器即可。 請(qǐng)求編號(hào) currentWeight 數(shù)組(current_weight = weight) 選擇結(jié)果 （max(currentWeight)） 減去權(quán)重總和后的currentWeight 數(shù)組（max(currentWeight) -= sum(weight)） 
如上，經(jīng)過平滑性處理后，得到的服務(wù)器序列為 [A, A, B, A, C, A, A]，相比之前的序列 [A, A, A, A, A, B, C]，分布性要好一些。初始情況下 currentWeight = [0, 0, 0]，第7個(gè)請(qǐng)求處理完后，currentWeight 再次變?yōu)?[0, 0, 0]。
實(shí)現(xiàn)： // 增加一個(gè)Weight類，用來保存ip, weight（固定不變的原始權(quán)重）, currentweight（當(dāng)前會(huì)變化的權(quán)重）
public class Weight {
private String ip;
private Integer weight;
private Integer currentWeight;
public Weight(String ip, Integer weight, Integer currentWeight) {
this.ip = ip;
this.weight = weight;
this.currentWeight = currentWeight;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public Integer getWeight() {
return weight;
}
public void setWeight(Integer weight) {
this.weight = weight;
}
public Integer getCurrentWeight() {
return currentWeight;
}
public void setCurrentWeight(Integer currentWeight) {
this.currentWeight = currentWeight;
}
}
public class WeightRoundRobinV2 {
private static Map<String, Weight> weightMap = new HashMap<String, Weight>();
public static String getServer() {
// java8
int totalWeight = ServerIps.WEIGHT_LIST.values().stream().reduce(0, (w1, w2) -> w1 w2);
// 初始化weightMap，初始時(shí)將currentWeight賦值為weight
if (weightMap.isEmpty()) {
ServerIps.WEIGHT_LIST.forEach((key, value) -> {
weightMap.put(key, new Weight(key, value, value));
});
}
// 找出currentWeight最大值
Weight maxCurrentWeight = null;
for (Weight weight : weightMap.values()) {
if (maxCurrentWeight == null || weight.getCurrentWeight() > maxCurrentWeight.getCurrentWeight()) {
maxCurrentWeight = weight;
}
}
// 將maxCurrentWeight減去總權(quán)重和
maxCurrentWeight.setCurrentWeight(maxCurrentWeight.getCurrentWeight() - totalWeight);
// 所有的ip的currentWeight統(tǒng)一加上原始權(quán)重
for (Weight weight : weightMap.values()) {
weight.setCurrentWeight(weight.getCurrentWeight() weight.getWeight());
}
// 返回maxCurrentWeight所對(duì)應(yīng)的ip
return maxCurrentWeight.getIp();
}
public static void main(String[] args) {
// 連續(xù)調(diào)用10次
for (int i = 0; i < 10; i ) {
System.out.println(getServer());
}
}
}
講ServerIps里的數(shù)據(jù)簡(jiǎn)化為： WEIGHT_LIST.put(“A”, 5); WEIGHT_LIST.put(“B”, 1); WEIGHT_LIST.put(“C”, 1); 運(yùn)行結(jié)果： A A B A C A A A A B 這就是輪詢算法，一個(gè)循環(huán)很簡(jiǎn)單，但是真正在實(shí)際運(yùn)用的過程中需要思考更多。 4、一致性哈希算法-ConsistentHashLoadBalance 服務(wù)器集群接收到一次請(qǐng)求調(diào)用時(shí)，可以根據(jù)根據(jù)請(qǐng)求的信息，比如客戶端的ip地址，或請(qǐng)求路徑與請(qǐng)求參數(shù)等信息進(jìn)行哈希，可以得出一個(gè)哈希值，特點(diǎn)是對(duì)于相同的ip地址，或請(qǐng)求路徑和請(qǐng)求參數(shù)哈希出來的值是一樣的，只要能再增加一個(gè)算法，能夠把這個(gè)哈希值映射成一個(gè)服務(wù)端ip地址，就可以使相同的請(qǐng)求（相同的ip地址，或請(qǐng)求路徑和請(qǐng)求參數(shù)）落到同一服務(wù)器上。 因?yàn)榭蛻舳税l(fā)起的請(qǐng)求情況是無窮無盡的（客戶端地址不同，請(qǐng)求參數(shù)不同等等），所以對(duì)于的哈希值也是無窮大的，所以我們不可能把所有的哈希值都進(jìn)行映射到服務(wù)端ip上，所以這里需要用到哈希環(huán)。如下圖
 哈希值如果需要ip1和ip2之間的，則應(yīng)該選擇ip2作為結(jié)果； 哈希值如果需要ip2和ip3之間的，則應(yīng)該選擇ip3作為結(jié)果； 哈希值如果需要ip3和ip4之間的，則應(yīng)該選擇ip4作為結(jié)果； 哈希值如果需要ip4和ip1之間的，則應(yīng)該選擇ip1作為結(jié)果；
上面這情況是比較均勻情況，如果出現(xiàn)ip4服務(wù)器不存在，那就是這樣了：
會(huì)發(fā)現(xiàn)，ip3和ip1直接的范圍是比較大的，會(huì)有更多的請(qǐng)求落在ip1上，這是不“公平的”，解決這個(gè)問題需要加入虛擬節(jié)點(diǎn)，比如：
其中ip2-1, ip3-1就是虛擬結(jié)點(diǎn)，并不能處理節(jié)點(diǎn)，而是等同于對(duì)應(yīng)的ip2和ip3服務(wù)器。 實(shí)際上，這只是處理這種不均衡性的一種思路，實(shí)際上就算哈希環(huán)本身是均衡的，你也可以增加更多的虛擬節(jié)點(diǎn)來使這個(gè)環(huán)更加平滑，比如：
這個(gè)彩環(huán)也是“公平的”，并且只有ip1,2,3,4是實(shí)際的服務(wù)器ip，其他的都是虛擬ip。 那么我們?cè)趺磥韺?shí)現(xiàn)呢？ 對(duì)于我們的服務(wù)端ip地址，我們肯定知道總共有多少個(gè)，需要多少個(gè)虛擬節(jié)點(diǎn)也有我們自己控制，虛擬節(jié)點(diǎn)越多則流量越均衡，另外哈希算法也是很關(guān)鍵的，哈希算法越散列流量也將越均衡。 實(shí)現(xiàn)： public class ConsistentHash {
private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
private static final int VIRTUAL_NODES = 160;
static {
// 對(duì)每個(gè)真實(shí)節(jié)點(diǎn)添加虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)會(huì)根據(jù)哈希算法進(jìn)行散列
for (String ip : ServerIps.LIST) {
for (int i = 0; i < VIRTUAL_NODES; i ) {
int hash = getHash(ip "VN" i);
virtualNodes.put(hash, ip);
}
}
}
private static String getServer(String client) {
int hash = getHash(client);
// 得到大于該Hash值的排好序的Map
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
// 大于該hash值的第一個(gè)元素的位置
Integer nodeIndex = subMap.firstKey();
// 如果不存在大于該hash值的元素，則返回根節(jié)點(diǎn)
if (nodeIndex == null) {
nodeIndex = virtualNodes.firstKey();
}
// 返回對(duì)應(yīng)的虛擬節(jié)點(diǎn)名稱
return subMap.get(nodeIndex);
}
private static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i )
hash = (hash ^ str.charAt(i)) * p;
hash = hash << 13;
hash ^= hash >> 7;
hash = hash << 3;
hash ^= hash >> 17;
hash = hash << 5;
// 如果算出來的值為負(fù)數(shù)則取其絕對(duì)值
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
public static void main(String[] args) {
// 連續(xù)調(diào)用10次,隨機(jī)10個(gè)client
for (int i = 0; i < 10; i ) {
System.out.println(getServer("client" i));
}
}
}
5、最小活躍數(shù)算法-LeastActiveLoadBalance 前面幾種方法主要目標(biāo)是使服務(wù)端分配到的調(diào)用次數(shù)盡量均衡，但是實(shí)際情況是這樣嗎？調(diào)用次數(shù)相同，服務(wù)器的負(fù)載就均衡嗎？當(dāng)然不是，這里還要考慮每次調(diào)用的時(shí)間，而最小活躍數(shù)算法則是解決這種問題的。 活躍調(diào)用數(shù)越小，表明該服務(wù)提供者效率越高，單位時(shí)間內(nèi)可處理更多的請(qǐng)求。此時(shí)應(yīng)優(yōu)先將請(qǐng)求分配給該服務(wù)提供者。在具體實(shí)現(xiàn)中，每個(gè)服務(wù)提供者對(duì)應(yīng)一個(gè)活躍數(shù)。初始情況下，所有服務(wù)提供者活躍數(shù)均為0。每收到一個(gè)請(qǐng)求，活躍數(shù)加1，完成請(qǐng)求后則將活躍數(shù)減1。在服務(wù)運(yùn)行一段時(shí)間后，性能好的服務(wù)提供者處理請(qǐng)求的速度更快，因此活躍數(shù)下降的也越快，此時(shí)這樣的服務(wù)提供者能夠優(yōu)先獲取到新的服務(wù)請(qǐng)求、這就是最小活躍數(shù)負(fù)載均衡算法的基本思想。除了最小活躍數(shù)，最小活躍數(shù)算法在實(shí)現(xiàn)上還引入了權(quán)重值。所以準(zhǔn)確的來說，最小活躍數(shù)算法是基于加權(quán)最小活躍數(shù)算法實(shí)現(xiàn)的。舉個(gè)例子說明一下，在一個(gè)服務(wù)提供者集群中，有兩個(gè)性能優(yōu)異的服務(wù)提供者。某一時(shí)刻它們的活躍數(shù)相同，則會(huì)根據(jù)它們的權(quán)重去分配請(qǐng)求，權(quán)重越大，獲取到新請(qǐng)求的概率就越大。如果兩個(gè)服務(wù)提供者權(quán)重相同，此時(shí)隨機(jī)選擇一個(gè)即可。 實(shí)現(xiàn)： 因?yàn)榛钴S數(shù)是需要服務(wù)器請(qǐng)求處理相關(guān)邏輯配合的，一次調(diào)用開始時(shí)活躍數(shù) 1，結(jié)束是活躍數(shù)-1，所以這里就不對(duì)這部分邏輯進(jìn)行模擬了，直接使用一個(gè)map來進(jìn)行模擬。 // 服務(wù)器當(dāng)前的活躍數(shù)
public static final Map<String, Integer> ACTIVITY_LIST = new LinkedHashMap<String, Integer>();
static {
ACTIVITY_LIST.put("192.168.0.1", 2);
ACTIVITY_LIST.put("192.168.0.2", 0);
ACTIVITY_LIST.put("192.168.0.3", 1);
ACTIVITY_LIST.put("192.168.0.4", 3);
ACTIVITY_LIST.put("192.168.0.5", 0);
ACTIVITY_LIST.put("192.168.0.6", 1);
ACTIVITY_LIST.put("192.168.0.7", 4);
ACTIVITY_LIST.put("192.168.0.8", 2);
ACTIVITY_LIST.put("192.168.0.9", 7);
ACTIVITY_LIST.put("192.168.0.10", 3);
}
public class LeastActive {
private static String getServer() {
// 找出當(dāng)前活躍數(shù)最小的服務(wù)器
Optional<Integer> minValue = ServerIps.ACTIVITY_LIST.values().stream().min(Comparator.naturalOrder());
if (minValue.isPresent()) {
List<String> minActivityIps = new ArrayList<>();
ServerIps.ACTIVITY_LIST.forEach((ip, activity) -> {
if (activity.equals(minValue.get())) {
minActivityIps.add(ip);
}
});
// 最小活躍數(shù)的ip有多個(gè)，則根據(jù)權(quán)重來選，權(quán)重大的優(yōu)先
if (minActivityIps.size() > 1) {
// 過濾出對(duì)應(yīng)的ip和權(quán)重
Map<String, Integer> weightList = new LinkedHashMap<String, Integer>();
ServerIps.WEIGHT_LIST.forEach((ip, weight) -> {
if (minActivityIps.contains(ip)) {
weightList.put(ip, ServerIps.WEIGHT_LIST.get(ip));
}
});
int totalWeight = 0;
boolean sameWeight = true; // 如果所有權(quán)重都相等，那么隨機(jī)一個(gè)ip就好了
Object[] weights = weightList.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 : weightList.keySet()) {
Integer value = weightList.get(ip);
if (randomPos < value) {
return ip;
}
randomPos = randomPos - value;
}
}
return (String) weightList.keySet().toArray()[new java.util.Random().nextInt(weightList.size())];
} else {
return minActivityIps.get(0);
}
} else {
return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[new java.util.Random().nextInt(ServerIps.WEIGHT_LIST.size())];
}
}
public static void main(String[] args) {
// 連續(xù)調(diào)用10次,隨機(jī)10個(gè)client
for (int i = 0; i < 10; i ) {
System.out.println(getServer());
}
}
}
這里因?yàn)椴粫?huì)對(duì)活躍數(shù)進(jìn)行操作，所以結(jié)果是固定的（擔(dān)任在隨機(jī)權(quán)重的時(shí)候會(huì)隨機(jī)，具體看源碼實(shí)現(xiàn)，以及運(yùn)行結(jié)果即可理解）。 負(fù)載均衡總結(jié)
|
