一道实习生笔试题

题目

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;
    }
  }
}