负载均衡算法及原理

原文地址：http://wangwx.blog.51cto.com/361401/72842
最少连接数调度算法(Least Connection Scheduling)

　　在实际情况中，客户端的每一次请求服务在服务器停留的时间可能会有较大的差异，随着工作时间的延伸，如果采用简单的轮询或随机均衡算法，每一台服务器上的连接数目可能会产生极大的不同，这样实际上并没有达到真正的负载均衡。

　　最少连接数均衡算法对内部中需负载的每一台服务器都有一个数据记录，记录当前该服务器正在处理的连接数量，当有新的服务连接请求时，将把当前请求分配给连接数最少的服务器，使均衡更加符合实际情况，负载更加均衡。

　　与轮询调度算法想反，最小连接调度是一种动态调度算法，它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已建立连接的数目，当一个请求被调度到某台服务器，其连接数加1;当连接中止或超时，其连接数减一。

　　此种均衡算法适合长时处理的请求服务，如FTP等应用。

　　最少连接数调度算法流程

　　假设有一组服务器S = {S0, S1, ..., Sn-1}，C(Si)表示服务器Si的当前连接数。其算法如下：

      for (m = 0; m < n; m++) {
　　for (i = m+1; i < n; i++) {
　　if (C(Si) < C(Sm))
　　m = i;
　　}
　　return Sm;
　　}
　　return NULL;

　　当各个服务器有相同的处理性能时，最小连接调度算法能把负载变化大的请求分布平滑到各个服务器上，所有处理时间比较长的请求不可能被发送到同一台服务器上。但是，当各个服务器的处理能力不同时，该算法并不理想，因为连接处理请求后会进入TE_WT状态，TCP的TIME_W一般为2分钟，此时连接还占用服务器的资源，所以会出现这样情形，性能高的服务器已处理所收到的连接，连接处于TIME_WAIT状态，而性能低的服务器已经忙于处理所收到的连接，还不断地收到新的连接请求。

　　所以，针对这种算法是需要改进的，也是有改进的余地的，这就是权重最少连接数调度算法。权重最少连接数调度算法(Weighted Least Connection Scheduling)

　　权重最少连接数调度算法是在做少连接数调度算法的基础上，根据服务器的不同处理能力，给每个服务器分配不同的权值，使其能够接受相应权值数的服务请求，是在最少连接数调度算法的基础上的改进。

　　权重最少连接数调度算法流程

　　假设有一组服务器S = {S0, S1, ..., Sn-1}，W(Si)表示服务器Si的权值，C(Si)表示服务器Si的当前连接数。所有服务器当前连接数的总和为

　　CSUM = ΣC(Si) (i=0, 1, .. , n-1)。

　　当前的新连接请求会被发送服务器Sm，当且仅当服务器Sm满足以下条件：

　　(C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)} (i=0, 1, . , n-1)

　　其中W(Si)不为零

　　因为CSUM在这一轮查找中是个常数，所以判断条件可以简化为

　　C(Sm) / W(Sm) = min { C(Si) / W(Si)} (i=0, 1, . , n-1)

　　其中W(Si)不为零

　　因为除法所需的周期比乘法多，且在某些(如) 的内核中不允许浮点除法，服务器的权值都大于零，所以判断条件C(Sm) / W(Sm) > C(Si) / W(Si) 可以进一步优化为C(Sm)*W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时，服务器不被调度。所以，算法只要执行以下流程。

      for (m = 0; m < n; m++) {
　　if (W(Sm) > 0) {
　　for (i = m+1; i < n; i++) {
　　if (C(Sm)*W(Si) > C(Si)*W(Sm))
　　m = i;
　　}
　　return Sm;
　　}
　　}
　　return NULL;

　　这种算法的逻辑实现如图1和图2所示：

　　图1显示在T时刻，一个新请求到来时，负载均衡设备的响应情况：

　　

　　                                图1 (权重)最少连接数调度算法逻辑示意图

　　当经过t时间后，新的请求到来是，负载均衡设备的调度情况变化结果如下：

　　

　　                       图2 (权重)经过t时间后最少连接数调度算法逻辑示意图

　　总结

　　权重最少连接数调度算法特点是实现起来比较简洁，在大多数情况下非常有效，在很多产品，如ArrayNetWorks等公司的产品中均有实现。