Linux服务器集群系统(四)[4]

　　为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;
　　
　　
　　
　　
　　2.5. 基于局部性的最少链接调度
　　
　　基于局部性的最少链接调度（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;
　　
　　
　　
　　
　　此外，对关联变量ServerNode[dest_ip]要进行周期性的垃圾回收（Garbage Collection），将过期的目标IP地址到服务器关联项进行回收。过期的关联项是指哪些当前时间（实现时采用系统时钟节拍数jiffies）减去最近使用时间超过设定过期时间的关联项，系统缺省的设定过期时间为24小时。
　　
　　2.6. 带复制的基于局部性最少链接调度