Method and system for work load balancing

• US 9,104,497 B2
• Filed: 11/07/2012
• Issued: 08/11/2015
• Est. Priority Date: 11/07/2012
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Mortazavi, Masood
• Primary Examiner(s): Nguyen, Dustin
• Assistant Examiner(s): Mesa, Joel
• Application Number:
  US13/671,046
• Publication Number:
  US 20140129715A1
• Time in Patent Office: 1,007 Days
• Field of Search: 709/226, 709/223
• US Class Current: 1/1
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

Method, system, and programs for balancing work load in a distributed system. A plurality of resource units in the distributed system are ranked based a plurality of multi-dimensional load metrics determined from each of the plurality of resource units. The plurality of resource units are divided into a plurality of resource unit groups based on the ranking of the plurality of resource units. At least one pair of resource unit groups is formed. Each of the at least one pair of resource unit groups is assigned with a probability of load balancing action. For each pair of resource unit groups, a load balancing action is determined based on the assigned probability of load balancing action.

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 the steps of:

ranking a plurality of resource units in the distributed system based a plurality of multi-dimensional load metrics determined from each of the plurality of resource units;

dividing the plurality of resource units into a plurality of resource unit groups based on the ranking of the plurality of resource units;

forming at least one pair of resource unit groups, wherein each of the at least one pair of resource unit groups is assigned with a probability of load balancing action; and

for each pair of resource unit groups, determining a load balancing action based on the assigned probability of load balancing action, wherein

for each pair of resource unit groups, a first resource unit group is selected from top half of resource unit groups in the ranking, and a second resource unit group is selected from bottom half of resource unit groups in the ranking.

2. The method of claim 1, further comprising the step of performing the determined plurality of load balancing actions in parallel for each pair of resource unit groups.

3. The method of claim 1, wherein the load balancing action includes at least one of:

exchanging work between two resource units or resource unit groups,

assigning work to a resource unit,

re-assigning work from one resource unit to another resource unit,

splitting work among a plurality of resource units, and

keeping the current work assignment.

4. The method of claim 1, wherein probabilities of load balancing actions are different from each other among different pairs of resource unit groups.

5. The method of claim 1, wherein a relative position of the first resource unit group with respect to a middle of the ranking is the same as that of the second resource unit group with respect to the middle of the ranking.

6. The method of claim 5, wherein the probability of load balancing action assigned to each pair of resource unit groups is determined based on the relative positions.

7. The method of claim 6, wherein the probability of load balancing action decreases as the relative positions get closer to the middle of the ranking.

8. The method of claim 1, wherein the plurality of multi-dimensional load metrics include at least one of latency, query length, storage usage, processing unit usage, memory usage, input/output unit usage, and any combination thereof.

9. A system for balancing work load in a distributed system, comprising a load controller implemented on at least one processor, the load controller comprising:

a ranking module configured to;

rank a plurality of resource units in the distributed system based a plurality of multi-dimensional load metrics determined from each of the plurality of resource units, and

divide the plurality of resource units into a plurality of resource unit groups based on the ranking of the plurality of resource units; and

an action module configured to;

form a plurality of pairs of resource unit groups, wherein each pair of resource unit groups is assigned with a probability of load balancing action, and

for each pair of resource unit groups, determine a load balancing action based on the assigned probability of load balancing action, wherein

for each pair of resource unit groups, a first resource unit group is selected from top half of resource unit groups in the ranking, and a second resource unit group is selected from bottom half of resource unit groups in the ranking.

10. The system of claim 9, further comprising a load assignment manager operatively coupled to the load controller and configured to perform the determined plurality of load balancing actions in parallel for each pair of resource unit groups.

11. The system of claim 9, wherein the load balancing action includes at least one of:

exchanging work between two resource units or resource unit groups,

assigning work to a resource unit,

re-assigning work from one resource unit to another resource unit,

splitting work among a plurality of resource units, and

keeping the current work assignment.

12. The system of claim 9, wherein probabilities of load balancing actions are different from each other among different pairs of resource unit groups.

13. The system of claim 9, wherein a relative position of the first resource unit group with respect to a middle of the ranking is the same as that of the second resource unit group with respect to the middle of the ranking.

14. The system of claim 13, wherein the probability of load balancing action assigned to each pair of resource unit groups is determined based on the relative positions.

15. The system of claim 14, wherein the probability of load balancing action decreases as the relative positions get closer to the middle of the ranking.

16. The system of claim 9, wherein the plurality of multi-dimensional load metrics include at least one of latency, query length, storage usage, processing unit usage, memory usage, input/output unit usage, and any combination thereof.

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

ranking a plurality of resource units in the distributed system based a plurality of multi-dimensional load metrics determined from each of the plurality of resource units;

dividing the plurality of resource units into a plurality of resource unit groups based on the ranking of the plurality of resource units;

forming at least one pair of resource unit groups, wherein each of the at least one pair of resource unit groups is assigned with a probability of load balancing action; and

for each pair of resource unit groups, determining a load balancing action based on the assigned probability of load balancing action, wherein

for each pair of resource unit groups, a first resource unit group is selected from top half of resource unit groups in the ranking, and a second resource unit group is selected from bottom half of resource unit groups in the ranking.

18. The medium of claim 17, further comprising the step of performing the determined load balancing action in parallel for each pair of resource unit groups.