Distributed application load distribution aid tool

[0002] The present invention relates to a toolkit for balancing the load of an application distributed among several machines belonging to a distributed data processing system in a local area network.

[0003] The current trend in the development of data processing systems is to form a data processing system through the association of a plurality of machines connected to one another through a network for example a local area network. Any user can run applications of widely varied types on this set of machines. These applications call services which supply the information required to handle the problem or problems they are working on, which are offered by all or some of these machines.

[0004] When an application in the process of running requires the use of a particular service, in current practice, it proceeds in the following manner:

[0005] either it chooses, in a purely random manner, the machine which will provide it with this service and assigns the work to this machine,

[0006] or it makes a circular choice among all the machines, which means that it assigns by turns, always in the same chronological order, the work of providing the services it requires in succession: thus, if the system has three machines, it assigns the work of providing the services it requires first to machine No. 1, those it requires second to machine No. 2, those it requires third to machine No. 3, and so on in the following order: No. 1, No. 2, No. 3, No. 1, etc.

[0007] No matter which of the two cases described above applies, none of the work of any of the machines is optimized in terms of time, and the capabilities of these machines in terms of speed and performance are used only at a level far below their maximum.

[0008] There are some known solutions which make it possible to eliminate these drawbacks: one of these is described in French patent application No. 94 08764, filed Jul. 13, 1994 by the Assignee of the subject application, under the title “Open Data Processing System with Multiple Servers”. In a system of this type, formed by the association of a central system called a client with several servers, each server calculates its own load based on the criteria specific to each application running on the client, as well as its foreseeable development over time, and transmits these two factors to the client. The latter, when a particular application requires the services of a server, chooses the one with the lightest load during the period of time in which the services must be rendered and assigns it the work of supplying the services requested.

[0009] The present invention constitutes an improvement and a generalization of the preceding solution.

[0010] According to the invention, the tool at the service of a distributed application running on the machines of a distributed data processing system in a local area network, which is intended for balancing the load on each of these machines, is characterized in that it comprises a plurality of data processing modules called DAEMONs which run on these machines, one of which is called the master, the others being agents,

[0011] the master and the agents each having means for calculating the load of the machines on which they are running, at first predetermined sampling instants, and means for storing the load data of the master and the agents,

[0012] the master containing:

[0013] means for collecting the load data of each agent, at second predetermined sampling instants,

[0014] means for sending the load data of each agent to all of the other agents,

[0015] each agent containing:

[0016] means for receiving the load data of the other agents,

[0017] the local agent closest to the application indicating to the latter, at the request of the latter, the machine with the lightest load, the application then making the decision to request this machine to execute the services it needs.

[0018] Other characteristics and advantages of the present invention will become apparent from the following description given as a non-limiting example in reference to the appended drawings. In these drawings:

[0019] FIG. 1 shows a distributed data processing system which includes the load balancing toolkit according to the invention.

[0020] FIG. 2 shows the controller for distributing the master-agent roles among the various elements which constitute the load balancing toolkit according to the invention.

[0021] A) Structure:

[0022] The various essential characteristic elements of the load balancing toolkit ORC for (load balancing toolkit, in English) (load balancing toolkit, in English) in a distributed data processing system according to the invention—for simplicity's sake, from this point forward, it will be called the “toolkit”—appear in FIG. 1.

[0023] As shown in FIG. 1, the distributed data processing system, which can be any type whatsoever, here called SID, comprises four data processing machines of any size and shape whatsoever, namely MCO, MC1, MC2, MC3. Each of these machines—small-, medium, or large-scale computers—comprise the usual elements, namely one or more central processor unit, called CPU , memories associated with the latter, input/output units (I/O units,) and means for connecting to the network RE. These means are symbolically represented by two-way arrows which represent the data links between the four machines MCO through MC3 in FIG. 1.

[0024] The toolkit ORC itself comprises the master MS0 and the three agents A1, A2, A3. Any agent can also be a master, depending on conditions which will be explained below. Both the master and the agents are constituted by data processing tools known to one skilled in the art as DAEMONs. A DAEMON is a data processing tool or entity running on a machine, which is capable of responding to a question.

[0025] Inside each of the machines MCO through MC3, the DAEMONs MS0, A1, A2, A3 are respectively associated with shared memories MPO, MP1, MP2, MP3. Each of them contains the load of the corresponding machine, but also the loads of the other machines in SID.

[0026] FIG. 1 assumes that the distributed application is running on the machine MC2 and that it requires services supplied by the other machines MCO, MC1, MC3. This application is designated APU. The places where the master and the agents are located are independent from the place where APU is running.

[0027] B) Operation:

[0028] The following are the main lines of operation of the tool ORC, it being understood that during the establishment of communication between all the machines in the system SID, it is assumed to be established that MS0 is the master and that A1, A2, A3 are the agents. Refer again to FIG. 1, and specifically to the arrows and the circled numbers which accompany them, which respectively indicate the direction of the information flowing between the master and the agents, and the sequence of operations.

[0029] OPERATION 1: Each agent as well as the master collects, for the machine on which it is running, at given time intervals which constituted the first determined sampling instants ti, the load data of this machine, for each of the elements which constitute it (the CPU load, the loads of the associated memories, the loads of the I/Os, the network load, etc.). From the load of each element, expressed as a percentage of its maximum allowable load, the total load of the machine in question is calculated. This is accomplished by load calculation means, respectively MCC0 for MS0, MCC1 for A1, MCC2 for A2, MCC3 for A3. These means are simply constituted by calculation programs which implement the load calculation method described below, in paragraph 2: “Method for load calculation by each of the agents.”These means are naturally an integral part of the master and of each agent, MS0, A1 through A3 and for this reason they are not represented per se in FIG. 1, for simplicity's sake. Once the total load of the machine in question is calculated a set of statistical data on the load of this machine, namely DSC, is obtained. In FIG. 1, this operation is shown for the agent A2 only, obviously for the purpose of preserving the clarity of this figure.

[0030] OPERATION 2: At regular intervals, the agents send MS0 the statistical load data from the corresponding machine, through the network (for A2, through the link L2 between MC2 and MC0).

[0031] OPERATION 3: The master MS0 centralizes, at practically the same regular intervals defined for Operation 2, which constitute the second determined sampling instants Ti, all the statistical load data of all the agents, as well as its own, at the level of its associated shared memory, in this case MP0. This centralization is in fact an operation for collecting the load data. It is therefore executed by load data collection means, respectively MRC0 for MS0, MRC1 for A1, MRC2 for A2, MRC3 for A3, which are in fact collection programs integrated into the master and into each of the agents A1 through A3 and are therefore not represented in FIG. 1 for simplicity's sake.

[0032] OPERATION 4: The master MS0 sends, using sending means MTCO, all this data to each agent A1, A2, A3 through the network RE, namely through the links L1 between MC0 and MC1, L2 between MC0 and MC2, L3 between MC0 and MC3, MTC0 is an integral part of MS0 and is therefore not represented in FIG. 1 for simplicity's sake.

[0033] OPERATION 5: Each agent receives this load data and copies it into its associated shared memory. MP1 for A1, MP2 for A2, MP3 for A3. This is accomplished by the means MRCC1 through MRCC3 for A1 through A3 respectively, which means are integral parts of the latter and are not represented in FIG. 1 for simplicity's sake.

[0034] OPERATION 6: The application APU scans the shared memory of the machine on which it is running to search it for the load estimated for each of the machines, and at the moment it needs the determined services to be rendered, it deduces the machine with the lightest load at this moment and requests the latter to render it these services.

[0035] 2) METHOD FOR LOAD CALCULATION BY EACH OF THE AGENTS:

[0036] Examples of loads on the CPU, memory, Input/Output, and network RE elements are described below.

[0037] The description of the method for load calculation by each of the means MCCO through MCC3 is given in reference to Tables 1 through 4, which appear below and in which the loads are given as percentages.

[0038] The calculation of the load for each agent and master is identical to that described in the above-mentioned patent. It is briefly summarized here.

[0039] The total load Wt of an agent (and also of the master) is obtained using the following formula:

[0040] Wt=k1*W1+k2*W2+k3*W3+k4*W4, in which:

[0041] W1 is the percentage of the utilization of the central processor of the agent in terms of time,

[0042] W2 is the percentage of the utilization of the memory of the agent, that is, the ratio between the storage capacity actually used and its total capacity,

[0043] W3 is the percentage of the utilization of the network by the agent, that is, the ratio between the number of pieces of information sent and received by the agent and the maximum allowable rate in the network,

[0044] W4 is the percentage of the utilization of the input/output units by the agent.

[0045] k1, k2, k3, k4 are specific weighting factors of the processor, the memory, the network, and the input/output units. Their sum is equal to 1. Their values depend on the nature of the application in the process of running, in this case APU on the machine MC2.

[0046] The loads W1, W2, W3, W4 are measured and Wt is calculated as shown in each of the tables in Appendix 1, at determined sampling instants t1, t2, t3, t4, t5, t6, t7, etc. of the period T (which are, in fact, the instants ti mentioned above in the description of Operation 1).

[0047] Table 1 gives an example of load data collected by any agent, for example A1, relative to the corresponding machine MC1, for all the instants t1 through t7. This data is, of course, stored in the shared memory MP1 of the machine MC1 on which A1 is running, before it is sent to MS0.

[0048] This table shows, for example, that W1 is equal to 35 at the instant t1, W2 to 67 at the instant t4, W3 to 38 at t6, W4 to 32 at t7, and so on.

[0049] A calculation program API associated with APU, which runs on MC2, then applies—for the load data of each agent and the master which, after the execution of Operation 3, is contained in the shared memory MP0 of MC0 associated with MS0—the weighting factors k1 through k4 specific to the corresponding machines for the application APU.

[0050] Thus Table 2 is obtained, which shows, for each of the machines MCO through MC4, the global load value Wt at the instants t1 through t7. Thus it may be seen that, for MC0, Wt is equal to 56 at the instant t1, 32 at t2, 67 at t3, etc. For MC1, Wt is equal to 23 at t1, 34 at t2, etc., and so on for the other machines.

[0051] The following step for calculating the load for all the machines consists of estimating, by extrapolation, using the known mathematical method of least error squares, the value of the estimated load Wt at the instant t8=(t7+T).

[0052] Thus, Table 3 is obtained. This table makes it possible to read, for example, that the estimated values of the loads of MCO through MC3 at this instant t8 are 73, 82, 36, and 76, respectively.

[0053] Next, a power coefficient Cp specific to each machine is applied to the total load of each machine in order to obtain its actual available capacity rate C1, using the formula:

[0054] C1=(100−Wt(estimated))*Cp

[0055] In effect, it is important to take into account the characteristics of each machine, given that this is a heterogeneous data processing environment wherein the power, the size and the type of the machines which compose it are different. Thus, if a machine has a light load but at the same time does not have enough processing power to provide the services requested of it by the application APU at a given moment, it is obvious that another machine must provide these services. Hence the necessity for a correction factor in order to define the load, and hence the existence of the power coefficient CP which corresponds to this purpose.

[0056] The coefficient Cp of a given machine is calculated by generating a synthesis of the power of the central processor CPU, the capacity of the memories, the processing power of the input/output units, etc. It is recalculated each time the hardware configuration of the machine is changed or its operating system is modified. Likewise, each time the general configuration of the distributed data processing system SID is changed, all the coefficients CP of all the machines in the system are redefined. A Cp equal to 1 corresponds to a medium-scale machine, which is defined by the user.

[0057] In Table 4, it is possible to read examples of actual available capacity rates C1 for each machine MCO through MC3. Thus, for MCO, with an estimated capacity rate of 73 and a power coefficient Cp of 2.5, the actual available capacity rate is 67.5. The same figures are respectively 82, 2, 36 for MC1, and so on for MC2 and MC3.

[0058] 3) METHOD FOR SELECTING THE MASTER MS0:

[0059] The basic philosophy is that any DAEMON running on any machine can be a master. It is therefore important to develop a mechanism which makes it possible to define which one of them will be the master and the conditions for its selection, as well as the modalities for its replacement should it fail.

[0060] The selection mechanism must ensure that at least 1 DAEMON is running and that two of them cannot be masters simultaneously (especially if they start up at the same time).

[0061] It is composed of the following 5 main phases:

[0062] Phase 1: When a DAEMON starts up, it generates a unique identifier ID in conformity with the protocol used in the network RE, for example in conformity with the TCP-IP protocol used in the exemplary embodiment of the invention described herein. This identifier is composed of the Ethernet address (Ethernet is the part of the TCP-IP protocol related to local area networks and is used in the exemplary embodiment described herein. Ethernet being understood to be standardized and therefore known to one skilled in the art), the moment at which the identifier is transmitted, and a random value. At the same time, it puts itself into an intermediate state and sends these two pieces of information (its current state, ID) through the network RE to all the machines in the network.

[0063] Phase 2: it waits to receive the identical information from the other DEMONS, for determined a time interval Tr (on the order of 5 to 10 seconds). It is a candidate for the role of master.

[0064] Phase 3: As soon as it receives this information, it analyzes it.

[0065] If it comes from a DAEMON which is in fact a master, that is, considered to be MS0, it considers itself to be an agent.

[0066] If it comes from a DAEMON in an intermediate state, it compares its own identifier with the one it receives.

[0067] If its own identifier is lower than the one it receives, it retains the right to be the master MS0.

[0068] If its own identifier is higher than or equal to the one it receives, it cedes the position. It then retransmits the two pieces of information (its own ID, its state) and again waits for responses during the time interval Tr, also called the timer.

[0069] Phase 4: Once this time interval has elapsed, the DAEMON in question tries again. In order to avoid a loss of messages, which is always possible in the network RE, it uses the following procedure:

[0070] The transmission and the listening for responses are repeated 5 times.

[0071] If the DAEMON in question receives a response from another DAEMON which reveals itself to be an agent, it can be sure that a master MS0 exists and it waits for the response from the latter to reach it.

[0072] Phase 5: When 5 repetitions have taken place, and the DAEMON in question has not received any response from the other DAEMONs, it then decides that it is the master MS0.

[0073] When one of the three agents A1 through A3 realizes that the master MS0 is no longer communicating with it, it starts the procedure below in all its phases, which results in the choice of a new master chosen from among the three.

[0074] Moreover, the master periodically notifies all the machines in the system SID of its existence. If the master detects the existence of another master, the procedure is restarted by the one whose ID is lower.

[0075] FIG. 2, which shows the controller AUT which distributes the master-agent roles among the various DAEMONs running on the machines of SID, will make it easier to understand the sequence of the different phases 1 through 5 described above.

[0076] This controller AUT comprises 5 states:

[0077] State IO: The DAEMON in question sends the two pieces of information (its own ID, its state), which corresponds to Phase 1.

[0078] State I1: This DAEMON listens for responses from the other DAEMONs, which corresponds to Phases 2 and 3.

[0079] State I2: This DAEMON waits for the time interval Tr to elapse, and for a possible response from the master MS0.

[0080] State A: The DAEMON in question becomes an agent A1, A2 or A3.

[0081] State M: The DAEMON in question becomes the master MS0.

[0082] The events which correspond to this controller, which are denominated e1 through e8, are the following:

[0083] e1: The DAEMON in question has disseminated its ID and its state and has set a time interval Tr.

[0084] e2: An ID is received, and the local identifier ID (that of the DAEMON in question) is lower than the identifier it receives.

[0085] e3: An ID is received, and the local ID is greater than or equal to the ID received.

[0086] e4: The time interval Tr has expired.

[0087] e5: The time interval Tr has expired and the number of attempts is less than 5, or an agent has just responded.

[0088] e6: The master has just responded.

[0089] e7: The time interval Tr has expired, the number of attempts is equal to 5, and no agent has responded.

[0090] e8: The connection with the master is lost.

[0091] e9: Detection by a master of the existence of another master with a higher ID.

[0092] While this invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the preferred embodiments of the invention as set forth herein, are intended to be illustrative, not limiting. Various changes may be made without departing from the true spirit and full scope of the invention as set forth herein and defined in the claims.