Method and system for work load balancing

• US 8,661,136 B2
• Filed: 10/17/2011
• Issued: 02/25/2014
• Est. Priority Date: 10/17/2011
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Tumbde, Adwait, Albert, Sahaya Andrews, Silberstein, Adam, Perinkulam, Suryanarayan, Mortazavi, Masood, Chen, Jianjun, Sears, Russell
• Primary Examiner(s): WON, MICHAEL YOUNG
• Application Number:
  US13/274,385
• Publication Number:
  US 20130097321A1
• Time in Patent Office: 862 Days
• Field of Search: 709/223, 709/234, 709/235, 709/241, 709/242, 709/203, 709/226
• US Class Current: 709/226
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources

Abstract

Method, system, and programs for balancing work load in a distributed system. A plurality of multi-dimensional load metrics are received from a plurality of resource units in the distributed system. Based on the received plurality of multi-dimensional load metrics and a global statistical load model, a load deviance for each resource unit is computed. The plurality of resource units in the distributed system are then ranked based on the load deviance of each resource unit. At least one load balancing action is further determined based on the ranked resource units and at least one load balancing policy.

Claims

1. A method, implemented on at least one machine each having at least one processor, storage, and a communication platform connected to a network for balancing work load in a distributed system, comprising:

receiving, by a sensing module, a plurality of multi-dimensional load metrics from a plurality of resource units in the distributed system;

computing, by a computation module, a load deviance for each resource unit based on a global statistical load model and the received plurality of multi-dimensional load metrics;

ranking, by a ranking module, the plurality of resource units in the distributed system based on the load deviance of each resource unit; and

determining, by an action module, at least one load balancing action based on the ranked resource units and at least one load balancing policy.

2. The method of claim 1 further comprising:

storing temporally, by the action module, the determined at least one load balancing action; and

performing, by a load assignment manager, one of the stored at least one load balancing action.

3. The method of claim 1 further comprising optimizing, by an optimization module, the global statistical load model by updating configuration parameters of the global statistical load model based on the received plurality of multi-dimensional load metrics and the at least one load balancing policy.

4. The method of claim 1, wherein the step of computing a load deviance for each resource unit comprises:

calculating a load mean and a load variance of the distributed system based on the received plurality of multi-dimensional load metrics;

determining a normal operation band based on the calculated load mean and load variance; and

for each resource unit, computing the load deviance based on the normal operation band and a last extreme load metric of the resource unit.

5. The method of claim 1, wherein the step of computing a load deviance for each resource unit comprises:

calculating a load median of the distributed system based on the received plurality of multi-dimensional load metrics;

determining a plurality of percentile bands based on the calculated load median; and

for each resource unit, computing the load deviance based on at least some of the plurality of percentile bands and a last extreme load metric of the resource unit.

6. The method of claim 1, wherein the step of computing a load deviance for each resource unit comprises:

calculating a load median of the distributed system based on the received plurality of multi-dimensional load metrics;

determining a plurality of percentile bands based on the calculated load median; and

for each resource unit, computing the load deviance based on at least some of the plurality of percentile bands using digit summation, wherein the load deviance is a load percentile array including a plurality of elements, each corresponding to one of the some percentile bands.

7. The method of claim 1, wherein the step of ranking the plurality of resource units further comprises:

removing any resource unit that was previously applied to a load balancing action within a predetermined time period; and

assigning some of the plurality of resource units into an overload pool and an underload pool based on the load deviances of the resource units.

8. The method of claim 7, wherein the step of determining at least one load balancing action comprises:

selecting one or more resource units from each of the overload pool and underload pool; and

determining the at least one load balancing action applying to the selected one or more resource units based on the at least one load balancing policy including a balancing objective function and a balancing rule.

9. The method of claim 1, further comprising determining, by the computation module, one or more principal load axes based on a distribution of the plurality of multi-dimensional load metrics, wherein

the step of ranking the plurality of resource units further comprises ranking the plurality of resource units in the distributed system based on the one or more principal load axes and the load deviance of each resource unit.

10. The method of claim 9, wherein the one or more principal load axes are determined along a direction in which most information can be obtained from ranking from the distribution of the plurality of multi-dimensional load metrics.

11. The method of claim 1, wherein

the plurality of multi-dimensional load metrics are periodically received at a first rate, and

the at least one load balancing action is periodically determined at a second rate.

12. A system for balancing work load in a distributed system, comprising:

a sensing module configured to receive a plurality of multi-dimensional load metrics from a plurality of resource units in the distributed system;

a computation module operatively coupled to the sensing module, configured to compute a load deviance for each resource unit based on a global statistical load model and the received plurality of multi-dimensional load metrics;

a ranking module operatively coupled to the computation module, configured to rank the plurality of resource units in the distributed system based on the load deviance of each resource unit; and

an action module operatively coupled to the ranking module, configured to determine at least one load balancing action based on the ranked resource units and at least one load balancing policy.

13. The system of claim 12, wherein

the action module is further configured to store temporally the determined at least one load balancing action, and

the system further comprises a load assignment manager operatively coupled to the action module, configured to perform one of the stored at least one load balancing action.

14. The system of claim 12 further comprising an optimization module operatively coupled to the action module, the ranking module, the computation module, and the sensing module, configured to optimize the global statistical load model by updating configuration parameters of the global statistical load model based on the received plurality of multi-dimensional load metrics and the at least one load balancing policy.

15. The system of claim 12, wherein the computation module, in computing the load deviance for each resource unit, is further configured to:

calculate a load mean and a load variance of the distributed system based on the received plurality of multi-dimensional load metrics;

determine a normal operation band based on the calculated load mean and load variance; and

for each resource unit, determine the load deviance based on the normal operation band and a last extreme load metric of the resource unit.

16. The system of claim 12, wherein the computation module, in computing the load deviance for each resource unit, is further configured to:

calculate a load median of the distributed system based on the received plurality of multi-dimensional load metrics;

determine a plurality of percentile bands based on the calculated load median; and

for each resource unit, compute the load deviance based on at least some of the plurality of percentile bands and a last extreme load metric of the resource unit.

17. The system of claim 12, wherein the computation module, in computing the load deviance for each resource unit, is further configured to:

calculate a load median of the distributed system based on the received plurality of multi-dimensional load metrics;

determine a plurality of percentile bands based on the calculated load median; and

for each resource unit, compute the load deviance based on at least some of the plurality of percentile bands using digit summation, wherein the load deviance is a load percentile array including a plurality of elements, each corresponding to one of the some percentile bands.

18. The system of claim 12, wherein the ranking module, in ranking the plurality of resource units, is further configured to:

remove any resource unit that was previously applied to a load balancing action within a predetermined time period; and

assign some of the plurality of resource units into an overload pool and an underload pool based on the load deviances of the resource units.

19. The system of claim 18, wherein the action module, in determining the at least one load balancing action, is further configured to:

select one or more resource units from each of the overload pool and underload pool; and

determine the at least one load balancing action applying to the selected one or more resource units based on the at least one load balancing policy including a balancing objective function and a balancing rule.

20. The system of claim 12, wherein

the computation module is further configured to determine one or more principal load axes based on a distribution of the plurality of multi-dimensional load metrics, and

the ranking module, in ranking the plurality of resource units, is further configured to rank the plurality of resource units in the distributed system based on the one or more principal load axes and the load deviance of each resource unit.

21. A machine-readable tangible and non-transitory medium having information for balancing work load in a distributed system recorded thereon, wherein the information, when read by the machine, causes the machine to perform the following:

receiving a plurality of multi-dimensional load metrics from a plurality of resource units in the distributed system;

computing a load deviance for each resource unit based on a global statistical load model and the received plurality of multi-dimensional load metrics;

ranking the plurality of resource units in the distributed system based on the load deviance of each resource unit; and

determining at least one load balancing action based on the ranked resource units and at least one load balancing policy.

22. The medium of claim 21, wherein computing a load deviance for each resource unit comprises:

calculating a load mean and a load variance of the distributed system based on the received plurality of multi-dimensional load metrics;

determining a normal operation band based on the calculated load mean and load variance; and

for each resource unit, computing the load deviance based on the normal operation band and a last extreme load metric of the resource unit.

23. The medium of claim 21, wherein computing a load deviance for each resource unit comprises:

calculating a load median of the distributed system based on the received plurality of multi-dimensional load metrics;

determining a plurality of percentile bands based on the calculated load median; and

for each resource unit, computing the load deviance based on at least some of the plurality of percentile bands and a last extreme load metric of the resource unit.

24. The medium of claim 21, wherein computing a load deviance for each resource unit comprises:

calculating a load median of the distributed system based on the received plurality of multi-dimensional load metrics;

determining a plurality of percentile bands based on the calculated load median; and

for each resource unit, computing the load deviance based on at least some of the plurality of percentile bands using digit summation, wherein the load deviance is a load percentile array including a plurality of elements, each corresponding to one of the some percentile bands.