Dynamically balancing load for servers

Dynamically balancing load for servers. Servers that are able to respond to requests directed at the system are monitored for. After discovery of a server, a performance metric is obtained for the discovered server. The performance metric for the discovered server is stored in a table. When a request is received, the request is routed to a selected server in the system of servers based on the performance metric, wherein the system of servers comprises the discovered servers.

TECHNICAL FIELD

Embodiments of the present invention relate to the field of computer networks. Specifically, embodiments of the present invention relate to dynamically balancing load for servers.

BACKGROUND ART

Each year, traffic over computer networks such as the Internet gets heavier. Typically, rather than having a single server handle all requests for similar information, multiple servers are used. For example, a web site may have many servers that are capable of servicing incoming requests. At essentially one point in time, there may be hundreds of users making requests to the web site. A front-end server distributes those requests among the servers as best as it can. However, conventionally, the distribution of requests is not always efficient.

The front-end server, which may be referred to as a load balancer, can use one of several common techniques to balance the load among the back-end servers. The simplest technique is round robin. A round robin system simply rotates the requests to the back-end servers with each back-end server getting one request per rotation. Another common load balancing technique is to assign the request to the back-end servers randomly. Over the long haul, each back-end server should receive an equal number of requests. Still another technique is to assign a number to each of “N” servers and forward the request to a server by determining a number between 1 and N for each request. The request is then forwarded to the back-end server whose number matches the request number. Unfortunately, each of these techniques suffers in that imbalances in load can occur for a variety of reasons.

A second problem with conventional load balancing is that one of the back-end servers can go down. The front-end server sometimes does not recognize this, which results in a request being forwarded to a server that is unable to handle the request. This typically results in an error message and a frustrated requestor. For example, the request may witness the all too common error message that information is not available. If the user tries to get the information again the problem may go away simply because by chance the request is forwarded to a functioning server this time. However, the user has wasted time and raised his/her frustration level. It is also possible that the error is only logged locally, and the user's browser sits waiting for a response that never arrives.

Thus, one problem with conventional load balancing is that the load becomes imbalanced between the servers. Another problem with some conventional load balancing techniques is that they fail to recognize when a server has gone down.

DISCLOSURE OF THE INVENTION

The present invention pertains to a method and system of dynamically balancing load for servers. In one embodiment of the present invention, certain acts are performed to dynamically discover servers and balance load to the servers. Included in those acts are monitoring for servers that are able to respond to requests directed at the system. After discovery of a server, a performance metric is obtained for the discovered server. The performance metric for the discovered server is stored in a table. When a request is received, the request is routed to a selected server in the system of servers based on the performance metric, wherein the system of servers comprises the discovered servers.

DETAILED DESCRIPTION OF THE INVENTION

In the following detailed description of embodiments of the present invention, a method and system of dynamically balancing load for servers, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, embodiments of the present invention may be practiced without these specific details or by using alternative elements or methods. In other instances well known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention.

Embodiments of the present invention provide a method and system of balancing load that dynamically discover when servers first become available and determine a performance metric for the servers at that time. Thus, methods and systems in accordance with the present invention are not limited to only routing requests to servers that a load-balancing agents was informed about by, for example, a system administrator. The performance metric for each discovered server may be stored in a table. A stress factor may also be calculated for each server, based on server load and the performance metric. Requests to the servers may be balanced based on the stress factor. Embodiments of the present invention provide a method and system of balancing load that avoids imbalances experienced by conventional load balancing techniques.

FIG. 1depicts a system150that dynamically discovers servers and dynamically balances a load between the servers, in accordance with an embodiment of the present invention. The system150comprises two front-end web servers160aand160bthat each has a load-balancing agent170a,170b. The system150also comprises a number of back-end servers180a,180b,180cthat are able to service requests to the system150. For example, the requests may be for information stored on a back-end web server180a,180b,180coradatabase that is accessible by a back-end web server180a,180b,180c. The present invention is well suited to using any number of front-end web servers160a,160band any number of back-end servers180a,180b,180c. The system150comprises a portal155to allow access to the web site, for example. In this example, the system150is a web site, although the present invention is not limited to balancing load at a web site. For example, the load may be balanced between computing devices in a LAN (local area network), WAN (wide area network), etc.

In this embodiment, at least one of the load-balancing agents170adynamically discovers new servers180n. It is not required that server discovery is performed by the load balancing agent170a,170b; another component may perform the server discover and inform the load balancing agents170a,170b. The dynamic server discovery logic185is used to discover new servers180nthat are capable of servicing requests to the system150. InFIG. 1, one of the load-balancing agents170ais depicted in the process of discovering a new server180n. Upon discovery, load-balancing agent170amay inform load-balancing agent170bof the new server180n. Alternatively, each load balancing agent170a,170bmay perform server discovery independently. Advantageously, an administrator is not required to provide the load-balancing agent170a,170bwith a configuration file identifying the new server.

In one embodiment, dynamic server discovery is performed using UDDI (Universal Description, Discovery, and Integration). In another embodiment, CORBA (Common Object Request Broker Architecture) is used to dynamically discover new servers. However, the present invention is not limited to using UDDI or CORBA for discovering new servers180n. The new servers180nthat are discovered are not servers that were once a part of the system150, but that went offline for some reason. Rather, they are servers that were not previously a part of the system150. Thus, the new servers are servers of which the load-balancing agent170a,170bwas previously unaware. However, the load-balancing agent170a,170bis capable of determining that a server that went offline has again become capable of handing requests.

An example of new servers coming online, for illustrative purposes, is a company bringing more servers online during a period in which the number of requests is expected to increase, such as holidays. Embodiments of the present invention dynamically discover the new servers without requiring an administrator to send a configuration file to the agent. This is in contrast to typical conventional systems that require a system administrator to make the agent aware of the new servers by sending a new configuration file. Moreover, in contrast to some conventional systems, the new servers do not need to be rebooted in embodiments of the present invention.

Each load-balancing agent170a,170bmaintains a table200a,200bthat is used in determining to which server180a,180b,180cto route an incoming request. The table200a,200bmay comprise a performance metric and a stress factor for each server180a,180b,180c. The performance metric may be response time to a request that is determined at the time a new server180nis discovered. Thus, the table200a,200bis modified each time a new server180nis discovered. However, the present invention is not limited to modifying the table200a,200bonly when a new server180nis discovered. In one embodiment, the table200a,200bis modified periodically, based on an analysis performed by the load-balancing agent170a,170b. Moreover, the table200a,200bmay include information for servers that the load-balancing agent was informed of by, for example, a system administrator. Thus, the table200a,200bis not limited to information about servers that the load-balancing agent discovered itself.

The table200a,200bmay also contain load information for each server180a,180b,180c. The load-balancing agent170a,170bis able to query the servers180a,180b,180cfor load information, in one embodiment of the present invention. The load-balancing agents170a,170bare depicted with load query logic188a,188bto perform this function. The load information may be used to determine a stress factor for each server180a,180b,180c, as discussed below.

FIG. 2is an exemplary performance metric table200, in accordance with an embodiment of the present invention. There is a server identifier column210, an initial response time column220, a load column230, and a stress factor column240. The stress factor may be calculated according to Equations 1-3 below. However, the present invention is not limited to calculating the stress factor via Equations 1-3. The initial response time describes the response when the server is first discovered. Hence, it is a measure of unloaded response time. The performance metrics in the table200ofFIG. 2are exemplary and many other metrics may be used within the scope of the present invention.

FIG. 3illustrates steps in a process300of dynamic server discovery and performance evaluation, in accordance with an embodiment of the present invention. Steps of process300may be stored as instructions in a computer readable medium. The instructions may be executed by a general-purpose computer, such as computer system100ofFIG. 5, in order to implement the process300. Process300is an ongoing process that is active while the load-balancing agent is routing requests to the servers, although the routing is not depicted in process300. In step310, a load balancing agent monitors for new servers that were previously not part of the system. The monitoring may be performed at any suitable time and with any suitable periodicity. When a new server is discovered, steps320,330, and340are performed in which information about the new server is collected and stored. Then, the load-balancing agent again monitors for new servers.

More specifically, process300goes to step320if step315indicates a new server is discovered. In step320, the load-balancing agent determines a performance metric for the server as that server is discovered. The performance metric is a response time to a request, in one embodiment. For example, while the new system is not yet processing requests, the load-balancing agent may send a “Hello” to the newly discovered server. In one embodiment, the load-balancing agent sends a database query to the new server.

At step330the present embodiment makes a determination of a stress factor that may be used in a request routing decision. The determination may be made in a number of ways; the exact formula is not critical. To determine the stress factor, first the load-balancing agent may first determine the average load for the servers in the system. The load-balancing agent performs a query of load information from each server and calculates average load according to Equation 1.
Ave_Load=(Serv1_Load+Serv2_Load+ . . . ServN_Load)/NEquation 1

It is not required that the load query be performed with each request. For example, the load query may be performed periodically by the load-balancing agent at any convenient interval. The load for each server is stored in the performance metric table.

The load-balancing agent of the present embodiment then may determine the average response for servers in the system according to the formula in Equation 2. In Equation 2, Init_Resp_ServN refers to the initial response of a given server that was determined by the load-balancing agent when that server was first discovered.
Ave_Resp=(Init_Resp_Serv1+Init_Resp_Serv2+ . . . Init_Resp_ServN)/NEquation 2

From Equations 1 and 2, the load balancing agent may determine the stress factor for a given server in accordance with Equation 3, where ServN_Load and Init_Resp_ServN are obtainable from the performance metric table, Ave_Load is calculated as per Equation 1, and Ave_Resp is calculated per Equation 2.
Stress—N=((ServN_Load/Ave_Load)+(Init_Resp_ServN/Ave_Resp))*0.5  Equation 3

The load-balancing agent may calculate a stress factor for each server in the system and route the request to the server with the lowest stress factor. It is possible that two or more servers have a stress factor that is either the same or so close to one another that for the present discussion the stress factor may be considered essentially the same. In either of these cases, the load balancing agent may decide between the servers by dynamically running the response query to re-order the servers. Thus, the initial response (e.g., Init_Resp_ServN) is replaced by a current response.

At step340the present embodiment stores the performance metric and the stress factor in a table. The table may be used in the process400ofFIG. 4to make a request routing decision. The process300then returns to step310of monitoring for new servers.

FIG. 4illustrates steps in a process400of dynamic load balancing, in accordance with an embodiment of the present invention. Steps of process400may be stored as instructions in a computer readable medium. The instructions may be executed by a general-purpose computer, such as computer system100ofFIG. 5, in order to implement the process400. Process300ofFIG. 3and process400ofFIG. 4may execute concurrently.

At step410, the present embodiment accesses a request that is serviceable by at least one of the servers. For example, a request may be received by a front-end web server.

Next, at step420the present embodiment routes the request to a server as determined by accessing the stress factor for the discovered servers. For example, the load-balancing agent accesses a table to find the server currently having the lowest stress factor. The servers from which the load-balancing agent selects from are not limited to those servers that the agent actively discovered itself.

In step430, the present embodiment routes the request to the server that was determined to have the lowest stress factor. The process400repeats itself as new requests are received in step410. As process300ofFIG. 3may be executing concurrently with process400, the number of servers that are available changes as servers are dynamically discovered. Moreover, the load-balancing agent does not passively wait to be informed about new servers, but actively seeks out new servers. Furthermore, the values in the table may also change dynamically as the load balancing agent performs new load queries and discovers more servers.

FIG. 5illustrates circuitry of an exemplary computer system100, which may form a platform for embodiments of the present invention. Computer system100includes an address/data bus99for communicating information, a central processor101coupled with the bus for processing information and instructions, a volatile memory102(e.g., random access memory RAM) coupled with the bus99for storing information and instructions for the central processor101and a non-volatile memory103(e.g., read only memory ROM) coupled with the bus99for storing static information and instructions for the processor101. Computer system100also includes an optional data storage device104(e.g., a magnetic or optical disk and disk drive) coupled with the bus99for storing information and instructions.

With reference still toFIG. 5, computer system also includes an alphanumeric input device106including alphanumeric and function keys coupled to bus99for communicating information and command selections to central processor unit101. Computer system also includes a cursor control device107coupled to bus99for communicating user input information and command selections to central processor unit101. Computer system of the present embodiment also includes a display device105coupled to bus99for displaying information. A signal input/output communication device108coupled to bus99provides communication with external devices.

While the present invention has been described in particular embodiments, it should be appreciated that the present invention should not be construed as limited by such embodiments, but rather construed according to the below claims.