基于局部性的最少链接算法及其实现原理

在负载均衡产品的调度器(Load Balancer)的实现技术中，IP负载均衡技术是效率最高的。这里我们将要介绍的LBLC和LBLCR就是实现IP负载均衡技术的两种方式。

　　基于局部性的最少链接调度算法

　　这里讲的LBLC，即基于局部性的最少链接调度(Locality-Based Least Connections Scheduling)算法就是针对请求报文的目标IP地址的负载均衡调度。

　　这种算法的前提假设是：任意一台服务器都可以处理任一请求。算法的设计目标是在服务器的负载基本平衡情况下，将相同目标IP地址的请求调度到同一台服务器，来提高各台服务器的访问局部性和主存Cache命中率，从而整个集群系统的处理能力。

　　LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器，若该服务器是可用的且没有超载，将请求发送到该服务器;若服务器不存在，或者该服务器超载且有其它服务器处于其一半的工作负载，则用”最少链接”的原则选出一个可用的服务器，将请求发送到该服务器。

　　由于在Cache集群中客户请求报文的目标IP地址是变化的，所以此种均衡算法主要应用在Cache集群系统中。

　　最少连接数调度算法流程

　　假设有一组服务器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; 


　　带复制的基于局部性最少链接调度(LBLCR)

　　LBLCR，即Locality-Based Least Connections Scheduling with Replication，也就是带复制的基于局部性最少链接调度。LBLCR算法也是针对目标IP地址的负载均衡，也是主要用于Cache集群系统。

　　它与LBLC算法基本相同，唯一的不同之处是它要维护从一个目标IP地址到一个服务器组的映射，而LBLC算法维护从一个目标IP地址到一台服务器的映射。

　　LBLC算法的主要缺点是：对于一个“热门”站点的服务请求，一台Cache服务器可能会忙不过来处理这些请求。这时，LBLC调度算法会从所有的Cache服务器中按“最小连接”原则选出一台Cache服务器，映射该“热门”站点到这台Cache服务器，很快这台Cache服务器也会超载，就会重复上述过程选出新的Cache服务器。这样，可能会导致该“热门”站点的映像会出现在所有的Cache服务器上，降低了Cache服务器的使用效率。