Algorithms

Load balancing is done at two places in path of HTTP request service, first at the DNS level and secondly at the front node of cluster. DNS tries to balance load on clusters by providing IP address of appropriate cluster's front node. When request reaches the front node, it balances load amongst the servers in that cluster. In exceptional cases when cluster is overloaded (due to uneven request rate from clients and caching of DNS entries), HTTP requests can be redirected to other lightly loaded cluster(s).

Within each cluster, every server periodically sends its load information to front node, which sends aggregated load information about cluster to DNS. This load information transfer can take place aperiodically too if load condition changes suddenly at any component, say any server becomes overloaded.

A number of system state information parameters are collected by each server, for example, system load averages, system and user cpu utilization, free RAM, Buffer RAM, number of disk accesses, free swap, number of processes, number of requests served in last 64 seconds and number of bytes transferred in last 64 seconds. Using average number of connections sent (dispatched and currently active) to particular server in past predefined time interval and its load condition in that time interval (a user defined function depending on bottlenecks present) capacity of each server, i.e. average number of connections it can serve without significant increase in response time is dynamically estimated and updated with every load update from server by front node. Similarly every front node aggregates load information of every server and informs available free capacity of whole cluster to DNS periodically.

We describe algorithm below at each component (DNS, front node and servers in each cluster).