2011年腾讯实习笔试总结(负载均衡)

前天参加了腾讯实习招聘笔试环节，准备不足，很多不会。不会开开眼界了，总结一下。

选择题很多不会，其中主要考查操作系统和数据结构，虽然这些都学过，但考起来还真的很多不懂。其中二叉树考的不少。

  附加题涉及负载均衡。负载均衡有两方面的含义：首先，大量的并发访问或数据流量分担到多台节点设备上分别处理，减少用户等待响应的时间；其次，单个重负载的运算分担到多台节点设备上做并行处理，每个节点设备处理结束后，将结果汇总，返回给用户，系统处理能力得到大幅度提高。

分类

1：软件负载均衡技术

该技术适用于一些中小型网站系统，可以满足一般的均衡负载需求。软件负载均衡技术是在一个或多个交互的网络系统中的多台服务器上安装一个或多个相应的负载均衡软件来实现的一种均衡负载技术。软件可以很方便的安装在服务器上，并且实现一定的均衡负载功能。软件负载均衡技术配置简单、操作也方便，最重要的是成本很低。

2：硬件负载均衡技术

由于硬件负载均衡技术需要额外的增加负载均衡器，成本比较高，所以适用于流量高的大型网站系统。硬件负载均衡技术是在多台服务器间安装相应的负载均衡设备，也就是负载均衡器来完成均衡负载技术，与软件负载均衡技术相比，能达到更好的负载均衡效果。

3：本地负载均衡技术

本地负载均衡技术是对本地服务器群进行负载均衡处理。该技术通过对服务器进行性能优化，使流量能够平均分配在服务器群中的各个服务器上，本地负载均衡技术不需要购买昂贵的服务器或优化现有的网络结构。

4：全局负载均衡技术

全局负载均衡技术适用于拥有多个低于的服务器集群的大型网站系统。全局负载均衡技术是对分布在全国各个地区的多个服务器进行负载均衡处理，该技术可以通过对访问用户的IP地理位置判定，自动转向地域最近点。很多大型网站都使用的这种技术。

5：链路集合负载均衡技术

链路集合负载均衡技术是将网络系统中的多条物理链路，当作单一的聚合逻辑链路来使用，使网站系统中的数据流量由聚合逻辑链路中所有的物理链路共同承担。这种技术可以在不改变现有的线路结构，不增加现有带宽的基础上大大提高网络数据吞吐量，节约成本。

算法

 

平衡算法设计的好坏直接决定了集群在上的表现，设计不好的算法，会导致集群的负载失衡。一般的平衡算法主要任务是决定如何选择下一个集群节点，然后将新的服务请求转发给它。有些简单平衡方法可以独立使用，有些必须和其它简单或高级方法组合使用。而一个好的负载均衡算法也并不是万能的，它一般只在某些特殊的应用环境下才能发挥最大效用。因此在考察负载均衡算法的同时，也要注意算法本身的适用面，并在采取集群部署的时候根据集群自身的特点进行综合考虑，把不同的算法和技术结合起来使用。

1 轮转法：(重点掌握，适用于集群中所有节点的处理能力和性能均相同的情况）

    轮转算法是所有调度算法中最简单也最容易实现的一种方法。在一个任务队列里，队列的每个成员（节点）都具有相同的地位，轮转法简单的在这组成员中顺序轮转选择。在负载平衡环境中，均衡器将新的请求轮流发给节点队列中的下一节点，如此连续、周而复始，每个集群的节点都在相等的地位下被轮流选择。这个算法在DNS域名轮询中被广泛使用。

    轮转法的活动是可预知的，每个节点被选择的机会是1/N，因此很容易计算出节点的负载分布。轮转法典型的适用于集群中所有节点的处理能力和性能均相同的情况，在实际应用中，一般将它与其他简单方法联合使用时比较有效。

2 散列法

    散列法也叫哈希法（HASH），通过单射不可逆的HASH函数，按照某种规则将网络请求发往集群节点。哈希法在其他几类平衡算法不是很有效时会显示出特别的威力。例如，在前面提到的UDP会话的情况下，由于轮转法和其他几类基于连接信息的算法，无法识别出会话的起止标记，会引起应用混乱。

    而采取基于数据包源地址的哈希映射可以在一定程度上解决这个问题：将具有相同源地址的数据包发给同一节点，这使得基于高层会话的事务可以以适当的方式运行。相对称的是，基于目的地址的哈希调度算法可以用在Web Cache集群中，指向同一个目标站点的访问请求都被负载平衡器发送到同一个Cache服务节点上，以避免页面缺失而带来的更新Cache问题。

3 最少连接法

    在最少连接法中，平衡器纪录目前所有活跃连接，把下一个新的请求发给当前含有最少连接数的节点。这种算法针对TCP连接进行，但由于不同应用对系统资源的消耗可能差异很大，而连接数无法反映出真实的应用负载，因此在使用重型Web作为集群节点服务时（例如Apache服务器），该算法在平衡负载的效果上要打个折扣。为了减少这个不利的影响，可以对每个节点设置最大的连接数上限（通过阈值设定体现）。

4 最低缺失法

    在最低缺失法中，平衡器长期纪录到各节点的请求情况，把下个请求发给历史上处理请求最少的节点。与最少连接法不同的是，最低缺失记录过去的连接数而不是当前的连接数。

5 最快响应法

    平衡器记录自身到每一个集群节点的网络响应时间，并将下一个到达的连接请求分配给响应时间最短的节点，这种方法要求使用ICMP包或基于UDP包的专用技术来主动探测各节点。

    在大多数基于LAN的集群中，最快响应算法工作的并不是很好，因为LAN中的ICMP包基本上都在10ms内完成回应，体现不出节点之间的差异；如果在 WAN上进行平衡的话，响应时间对于用户就近选择服务器而言还是具有现实意义的；而且集群的拓扑越分散这种方法越能体现出效果来。这种方法是高级平衡基于拓扑结构重定向用到的主要方法。

6 加权法

    加权方法只能与其他方法合用，是它们的一个很好的补充。加权算法根据节点的优先级或当前的负载状况（即权值）来构成负载平衡的多优先级队列，队列中的每个等待处理的连接都具有相同处理等级，这样在同一个队列里可以按照前面的轮转法或者最少连接法进行均衡，而队列之间按照优先级的先后顺序进行均衡处理。在这里权值是基于各节点能力的一个估计值。

下面介绍一下主要的两种算法实现：

 

负载均衡算法——轮询调度算法(Round-Robin Scheduling)

轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器,从1开始,直到N(内部服务器个数),然后重新开始循环，这也是负载均衡算法的核心内容。

算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度｡

轮询调度算法流程

假设有一组服务器N台,S = {S1, S2, …, Sn},一个指示变量i表示上一次选择的服务器ID｡变量i被初始化为N-1｡其算法如下:

j = i;
  do
{
  j = (j + 1) mod n;
  i = j;
  return Si;
} while (j != i);
return NULL;

这种算法的逻辑实现如图1所示:

 

图1 轮询调度实现逻辑图示

轮询调度算法假设所有服务器的处理性能都相同,不关心每台服务器的当前连接数和响应速度｡当请求服务间隔时间变化比较大时,轮询调度算法容易导致服务器间的负载不平衡｡

所以此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况｡

 

权重轮询调度算法(Weighted Round-Robin Scheduling)

上面所讲的轮询调度算法并没有考虑每台服务器的处理能力,在实际情况中,可能并不是这种情况｡由于每台服务器的配置､安装的业务应用等不同,其处理能力会不一样｡所以,我们根据服务器的不同处理能力,给每个服务器分配不同的权值,使其能够接受相应权值数的服务请求｡

负载均衡算法——权重轮询调度算法流程

这一负载均衡算法是轮训调度算法的升级版本。假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大公约数｡变量i初始化为-1,cw初始化为零｡其算法如下:

while (true) {
  i = (i + 1) mod n;
  if (i == 0) {
     cw = cw - gcd(S);
     if (cw <= 0) {
             cw = max(S);
             if (cw == 0)
             return NULL;
}
}
  if (W(Si) >= cw)
    return Si;
}

这种算法的逻辑实现如图2所示,图中我们假定四台服务器的处理能力为3:1:1:1｡

 

在vc6.0上编程实现：

#include
#include
#include
#include

int min_gcd(int weight[], int asize);
int max_Weight(int weights[]);

void main()
{
 char * slist[4]; /* Used to store the server names entered */
 int weight[10]; /* array for storing the weight associated with each server */
 int wno = 4; /* number of servers (or weights) */
 int n = 0; /* a counter */
 int i= -1, cw= 0, v, hcf = 0, maxw = 0; /* hcf and maxw are used to store the hcf and the max value of the weights specified */
 
 int ss = 0;
 int mm = 1;

 slist[0] = "0";
 slist[1] = "1";
 slist[2] = "2";
 slist[3] = "3";

 weight[0] = 3;
 weight[1] = 1;
 weight[2] = 1;
 weight[3] = 1;

 printf("\r\nEnter the weights: %d %d %d %d\n" ,weight[0], weight[1], weight[2], weight[3]);
 //system("pause");

 ss = weight[0] +weight[1] +weight[2] + weight[3];

 hcf  = min_gcd(weight, wno);
 maxw = max_Weight(weight);

 for (v=0; v {

  while (1)
  {
   i = (i+1) % 4;
    printf("\nvalue of index :%d value:i = %d",n++,i);  /* for checking the value of i */
   if (i == 0)
   {   
    printf ("\r\nenter...........\r\n");
    cw = cw - hcf;

    if (cw <= 0)
    {
     cw = maxw;
      if (cw == 0) return;
    }
   }

    printf("\nvalue of weight[i] = %d, cw =%d\r\n",weight[i],cw); 
   if (weight[i] >= cw)
   {
    printf("\r\n----------------------------index %d; --i = %d,value : %s",mm++,i,slist[i]);
    break;
   }
  }
  printf("\n");
 }

 return;

}

// 查找最大的权重
int max_Weight(int weights[])
{
 int maxVal = 0;
 int i = 0;

 for (i=0; i<4; i++)
 {
  if (weights[i] > maxVal)
  {
   maxVal = weights[i];
  }
 }

 return maxVal;
}

int min_gcd(int w[], int asize)/*不能直接把实参赋值到形参中，因为函数中形参数组元素的改变会导致实参数组元素值得变化，所以要先定义一个中间数组，把实参复制到该数组中。*/
{
 int i, a, t;
 
 int *win=(int*)malloc(sizeof(int)*asize);//动态分配大小，还要记得加头文件malloc.h和返回前释放内存free(win)
 
 for (i=0;i {
  win[i] = w[i];
 }

 a = win[0];

 for(i=0;i<(asize-1);i++) {

  t = 0;
  while(win[i+1] != 0)
  {
   t = win[i+1];
   win[i+1] = a % win[i+1];
   a = t;
  }
 }
 printf("\n\nHCF = %d\n\n",a);
 //system("pause");
free(win);
    return a;
}  

运行结果为：
Enter the weights: 3 1 1 1

HCF = 1

value of index :0 value:i = 0
enter...........

value of weight[i] = 3, cw =3

----------------------------index 1; --i = 0,value : 0

value of index :1 value:i = 1
value of weight[i] = 1, cw =3

value of index :2 value:i = 2
value of weight[i] = 1, cw =3

value of index :3 value:i = 3
value of weight[i] = 1, cw =3

value of index :4 value:i = 0
enter...........

value of weight[i] = 3, cw =2

----------------------------index 2; --i = 0,value : 0

value of index :5 value:i = 1
value of weight[i] = 1, cw =2

value of index :6 value:i = 2
value of weight[i] = 1, cw =2

value of index :7 value:i = 3
value of weight[i] = 1, cw =2

value of index :8 value:i = 0
enter...........

value of weight[i] = 3, cw =1

----------------------------index 3; --i = 0,value : 0

value of index :9 value:i = 1
value of weight[i] = 1, cw =1

----------------------------index 4; --i = 1,value : 1

value of index :10 value:i = 2
value of weight[i] = 1, cw =1

----------------------------index 5; --i = 2,value : 2

value of index :11 value:i = 3
value of weight[i] = 1, cw =1

----------------------------index 6; --i = 3,value : 3
Press any key to continue

可以看到不是图二的分配，而是123在s0,4-s1,5-s2,6-s3.

由于权重轮询调度算法考虑到了不同服务器的处理能力,所以这种均衡算法能确保高性能的服务器得到更多的使用率,避免低性能的服务器负载过重｡所以,在实际应用中比较常见｡

总结

两大负载均衡算法，轮询调度算法以及权重轮询调度算法的特点是实现起来比较简洁,并且实用｡目前几乎所有的负载均衡设备均提供这种功能｡