题目
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).
大意是，设计一个负载均衡算法，假设输入是32位整数，负载均衡器必须在5台服务器之间负载分布。写一个简单的算法，实现5台服务器之间的负载均衡，且不显式地使用堆栈内存。（答案应该是若干行代码）
解读
首先要根据题意来完成，首先要了解以下几点分别意味着什么：
负载均衡
负载均衡即字面含义，使集群中的服务器均匀地处理负载，那么，其算法本质应该是将一个32位的数，散列成5份（散列的结果为其最终请求的服务器），散列的结果是服务器的load应该是均衡的不显式使用堆栈内存
声明一个对象，就是使用到了堆内存；声明一个基本数据类型，或者引用，就是使用到了栈内存。这边所说的不显式地使用堆栈内存，应该指的是不显式声明变量的意思。
回到算法，均匀散列，看似简单，实则有很多可以深入讨论的地方。
如果想在笔试中能够脱颖而出，那么必须要考虑尽可能多的情况，并且给出答案，而不是草草写几行代码交上去了之。
讨论
先来看看负载均衡有哪些常用的算法：
- 简单轮询：需要记录上次轮询的位置，使用到了堆或栈内存，因此不讨论
- 加权轮询
- 动态轮询：根据服务器当前的性能来分配连接，和服务器相关，不讨论
- 最少连接：根据服务器当前的连接来分配连接，和服务器相关，不讨论
- 最快连接：根据服务器的相应速度来分配连接，和服务器相关，不讨论
因此涉及设计算法的，只有加权轮询一种。
先假设每台服务器的性能都一样，那么仅需将请求的IP均匀地分布在 [0, 2^32-1] 之间就可以了，简单的 mod 取余（或者取随机数的方法，下同）就能够满足：
// 假设返回值为第n台服务器，n∈[1, 5]
public int getServer(int ip) {
return ip % 5 + 1; // 或者 return Random.next(0, 5);
}
那么假设5台服务器的性能分别为p1, p2, p3, p4, p5，性能之和 sum(p1, p2, p3, p4, p5) = s，那么分配到每台服务器的概率应该为p1/s, p2/s, p3/s, p4/s, p5/s。
设计算法，可以将ip散列在[1,s]之间。如果散列结果r∈[1, p1]，则请求第一台服务器；如果散列结果r∈[p1, p1+p2]，则请求第二台服务器；如果散列结果r∈[p1+p2, p1+p2+p3]，则请求第三台服务器...
代码即：
public int getServer(int ip) {
if( (ip % s) <= p1 ) {
return 1;
} else if( (ip % s) > p1 && (ip % s) <= (p1 + p2) ) {
return 2;
} else if(...) {
...
}
}
如果可以显式使用堆栈内存，那么可以简化为：
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;
}
}
}
