Locality-Based Least-Connection with Replication Scheduling

The locality-based least-connection with replication (LBLCR) scheduling algorithm is also for destination IP load balancing. It only differs from the locality-based least-connection (LBLC) scheduling as follows: the load balancer maintains mappings from a target to a set of server nodes that can serve the target. Requests for a target are assigned to the least-connection node in the target's server set. If all the node in the server set are over loaded, it picks up a least-connection node in the cluster and adds it in the sever set for the target. If the server set has not been modified for the specified time, the most loaded node is removed from the server set, in order to avoid high degree of replication.

The pseudo code of locality-based least-connection with replication scheduling algorithm is as follows:

Supposing there is a server set S = {S0, S1, ..., Sn-1},
W(Si) is the weight of server Si;
C(Si) is the current connection number of server Si;
ServerSet[dest_ip] is a map from destination IP address to server set;
WLC(S) is the server of weighted least connection in the server set S;
WGC(S) is the server of weighted greatest connections in the server set S;
Now is the current system time;
ServerSet[dest_ip].lastmod is the last modified time of server set for destination IP;
T is the specified time for adjust server set.

if (ServerSet[dest_ip] is NULL) then {
    n = WLC(S);
    if (n is NULL) then return NULL;
    add n into ServerSet[dest_ip];
} else {
    n = WLC(ServerSet[dest_ip]);
    if ((n is NULL) OR
        (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;
        add n into ServerSet[dest_ip];
    } else
    if (|ServerSet[dest_ip]| > 1 AND
        Now - ServerSet[dest_ip].lastmod > T) then {
        m = WGC(ServerSet[dest_ip]);
        remove m from ServerSet[dest_ip];
    }
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
    ServerSet[dest_ip].lastmod = Now;
return n;

Furthermore, we do garbage collection on the map ServerSet[dest_ip] periodically, in order to collect stale entries. Stale entries is those that have not been used for the specified time, such as 24 hours by default.

The locality-based least-connection with replication (LBLCR) scheduling algorithm is usually used in cache cluster. For requests for a "hot" site, one single cache server may be busy to handle them in time, and the LBLC scheduling algorithm may allocate another cache server by WLC for those requests, this cache server may be overloaded soon, then new cache server will be allocated repeatly for those requests. Therefore, object copies for this "hot" site may be stored in all the cache servers, which will decrease the utilization of cache servers. The LBLCR scheduling algorithm can map a "hot" site to a set of cache servers. When request load for this "hot" site is increasing, more cache servers will be added in the server set; when request load for this "hot" site is decreasing, some cache servers will be removed from the server site. Therefore, object copies for this "hot" site can be controlled in a set of cache server, instead of all the cache servers, and performance of the whole system can be improved.