題目
Develop an implementation of a load balancer for incoming IP traffic. Assume the input is 32-bit integer. The load balancer must distribute load among 5 servers. Write a simple algorithm that implements load balancing between 5 servers WITHOUT explicitly using stack or heap memory. (The answer should only be a few lines of code).
大意是唆姐，設(shè)計(jì)一個(gè)負(fù)載均衡算法庐氮，假設(shè)輸入是32位整數(shù)触幼，負(fù)載均衡器必須在5臺(tái)服務(wù)器之間負(fù)載分布嚷往。寫一個(gè)簡(jiǎn)單的算法，實(shí)現(xiàn)5臺(tái)服務(wù)器之間的負(fù)載均衡宣增，且不顯式地使用堆棧內(nèi)存薄嫡。（答案應(yīng)該是若干行代碼）
解讀
首先要根據(jù)題意來(lái)完成胳泉，首先要了解以下幾點(diǎn)分別意味著什么：
負(fù)載均衡
負(fù)載均衡即字面含義，使集群中的服務(wù)器均勻地處理負(fù)載们何，那么萄焦，其算法本質(zhì)應(yīng)該是將一個(gè)32位的數(shù)，散列成5份（散列的結(jié)果為其最終請(qǐng)求的服務(wù)器）冤竹，散列的結(jié)果是服務(wù)器的load應(yīng)該是均衡的不顯式使用堆棧內(nèi)存
聲明一個(gè)對(duì)象拂封，就是使用到了堆內(nèi)存；聲明一個(gè)基本數(shù)據(jù)類型鹦蠕，或者引用冒签，就是使用到了棧內(nèi)存。這邊所說(shuō)的不顯式地使用堆棧內(nèi)存片部，應(yīng)該指的是不顯式聲明變量的意思镣衡。
回到算法，均勻散列档悠，看似簡(jiǎn)單廊鸥，實(shí)則有很多可以深入討論的地方。
如果想在筆試中能夠脫穎而出辖所，那么必須要考慮盡可能多的情況惰说，并且給出答案，而不是草草寫幾行代碼交上去了之缘回。
討論
先來(lái)看看負(fù)載均衡有哪些常用的算法：
- 簡(jiǎn)單輪詢：需要記錄上次輪詢的位置吆视，使用到了堆或棧內(nèi)存，因此不討論
- 加權(quán)輪詢
- 動(dòng)態(tài)輪詢：根據(jù)服務(wù)器當(dāng)前的性能來(lái)分配連接酥宴，和服務(wù)器相關(guān)啦吧，不討論
- 最少連接：根據(jù)服務(wù)器當(dāng)前的連接來(lái)分配連接，和服務(wù)器相關(guān)拙寡，不討論
- 最快連接：根據(jù)服務(wù)器的相應(yīng)速度來(lái)分配連接授滓，和服務(wù)器相關(guān)，不討論
因此涉及設(shè)計(jì)算法的，只有加權(quán)輪詢一種般堆。
先假設(shè)每臺(tái)服務(wù)器的性能都一樣在孝，那么僅需將請(qǐng)求的IP均勻地分布在 [0, 2^32-1] 之間就可以了，簡(jiǎn)單的 mod 取余（或者取隨機(jī)數(shù)的方法淮摔，下同）就能夠滿足：
// 假設(shè)返回值為第n臺(tái)服務(wù)器私沮，n∈[1, 5]
public int getServer(int ip) {
return ip % 5 + 1; // 或者 return Random.next(0, 5);
}
那么假設(shè)5臺(tái)服務(wù)器的性能分別為p1, p2, p3, p4, p5，性能之和 sum(p1, p2, p3, p4, p5) = s和橙，那么分配到每臺(tái)服務(wù)器的概率應(yīng)該為p1/s, p2/s, p3/s, p4/s, p5/s仔燕。
設(shè)計(jì)算法，可以將ip散列在[1,s]之間胃碾。如果散列結(jié)果r∈[1, p1]涨享，則請(qǐng)求第一臺(tái)服務(wù)器；如果散列結(jié)果r∈[p1, p1+p2]仆百，則請(qǐng)求第二臺(tái)服務(wù)器厕隧；如果散列結(jié)果r∈[p1+p2, p1+p2+p3]，則請(qǐng)求第三臺(tái)服務(wù)器...
代碼即：
public int getServer(int ip) {
if( (ip % s) <= p1 ) {
return 1;
} else if( (ip % s) > p1 && (ip % s) <= (p1 + p2) ) {
return 2;
} else if(...) {
...
}
}
如果可以顯式使用堆棧內(nèi)存俄周，那么可以簡(jiǎn)化為：
public int getServer(int ip) {
int serverNum = 1;
int hashNum = ip % s;
while(true) {
hashNum -= p[serverNum++];
if(hashNum <= 0) {
return serverNum;
}
if(serverNum >= 5) {
return 5;
}
}
}
