最小连接调度(Least-Connection Scheduling)算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法,它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已建立连接的数目,当一个请求被调度到某台服务器,其连接数加1;当连接中止或超时,其连接数减一。
在系统实现时,我们也引入当服务器的权值为零时,表示该服务器不可用而不被调度,它的算法流程如下:
最小连接调度算法流程:
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值, C(Si)表示服务器Si的当前连接数。 for (m = 0; m < n; m++) { if (W(Sm) > 0) { for (i = m+1; i < n; i++) { if (W(Si) <= 0) continue; if (C(Si) < C(Sm)) m = i; } return Sm; } } return NULL;当各个服务器有相同的处理性能时,最小连接调度算法能把负载变化大的请求分布平滑到各个服务器上,所有处理时间比较长的请求不可能被发送到同一台服务器上。但是,当各个服务器的处理能力不同时,该算法并不理想,因为TCP连接处理请求后会进入TIME_WAIT状态,TCP的TIME_WAIT一般为2分钟,此时连接还占用服务器的资源,所以会出现这样情形,性能高的服务器已处理所收到的连接,连接处于TIME_WAIT状态,而性能低的服务器已经忙于处理所收到的连接,还不断地收到新的连接请求。
加权最小连接调度(WLC)加权最小连接调度(Weighted Least-Connection Scheduling)算法是最小连接调度的超集,各个服务器用相应的权值表示其处理性能。服务器的缺省权值为1,系统管理员可以动态地设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。加权最小连接调度的算法流程如下:
加权最小连接调度的算法流程:
假设有一组服务器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)不为零 因为除法所需的CPU周期比乘法多,且在Linux内核中不允许浮点除法,服务器的 权值都大于零,所以判断条件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; 基于局部性的最少链接调度(LBLC)基于局部性的最少链接调度(Locality-Based Least Connections Scheduling,以下简称为LBLC)算法是针对请求报文的目标IP地址的负载均衡调度,目前主要用于Cache集群系统,因为在Cache集群中客户请求报文的目标IP地址是变化的。这里假设任何后端服务器都可以处理任一请求,算法的设计目标是在服务器的负载基本平衡情况下,将相同目标IP地址的请求调度到同一台服务器,来提高各台服务器的访问局部性和主存Cache命中率,从而整个集群系统的处理能力。
LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器是可用的且没有超载,将请求发送到该服务器;若服务器不存在,或者该服务器超载且有服务器处于其一半的工作负载,则用“最少链接”的原则选出一个可用的服务器,将请求发送到该服务器。该算法的详细流程如下:
LBLC调度算法流程:
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值, C(Si)表示服务器Si的当前连接数。ServerNode[dest_ip]是一个关联变量,表示 目标IP地址所对应的服务器结点,一般来说它是通过Hash表实现的。WLC(S)表示 在集合S中的加权最小连接服务器,即前面的加权最小连接调度。Now为当前系统 时间。 if (ServerNode[dest_ip] is NULL) then { n = WLC(S); if (n is NULL) then return NULL; ServerNode[dest_ip].server = n; } else { n = ServerNode[dest_ip].server; if ((n is dead) OR (C(n) > W(n) AND there is a node m with C(m) < W(m)/2))) then { n = WLC(S); if (n is NULL) then return NULL; ServerNode[dest_ip].server = n; } } ServerNode[dest_ip].lastuse = Now; return n;