Landscape reorganization algorithm for dynamic load balancing

• US 8,127,299 B2
• Filed: 03/29/2006
• Issued: 02/28/2012
• Est. Priority Date: 03/28/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Morich, Kai, Rebholz, Oliver, Leonkev, Vladislav
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): KUMABE, BLAKE K
• Application Number:
  US11/393,927
• Publication Number:
  US 20070234366A1
• Time in Patent Office: 2,162 Days
• Field of Search: 718/105, 718/104
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method and system for reorganizing a distributed computing landscape for dynamic load balancing is presented. A method includes the steps of collecting information about resource usage by a plurality of hosts in a distributed computing system, and generating a target distribution of the resource usage for the distributed computing system. The method further includes the step of generating an estimate of an improvement of the resource usage according to a reorganization plan.

Claims

1. A computer-implemented method comprising:

collecting, using one or more processors, information about an actual load distribution of resource usage by a distributed computing system comprising a plurality of hosts, the actual load distribution comprising static information of a total size in memory of each of a plurality of objects accessed by an information processing application implemented on the distributed computing system and CPU usage by each of the plurality of hosts per a predetermined interval;

calculating, using the one or more processors, a target load distribution of the resource usage by the distributed computing system, the target load distribution comprising a balancing of the CPU usage by each of the plurality of hosts;

using the one or more processors, sorting the plurality of objects by size from largest to smallest, retaining the objects above a certain size based on the sorting on their current hosts, and distributing the objects below the certain size across the plurality of hosts to an approximately equal number of objects per host to create a reorganization plan to transform the actual load distribution into the target load distribution, the creating of the reorganization plan further comprising recognizing a split object having more than one part and distributing the more than one part on different hosts of the plurality of hosts;

generating, using the one or more processors, an estimate of an improvement of the resource usage to be realized by executing the reorganization plan; and

if the estimate of an improvement corresponds with the target load distribution, executing, using the one or more processors, the reorganization plan on the distributed computing system.

2. A method in accordance with claim 1, wherein the information includes static information that comprises the total size of each of the plurality of objects and dynamic information that comprises the CPU usage by each of the plurality of hosts per the predetermined interval.

3. A method in accordance with claim 1, wherein the information about the resource usage is an estimate based on comparative values measured at particular times or intervals.

4. A method in accordance with claim 1, wherein the target load distribution further comprises:

minimizing memory usage of the distributed computing system.

5. A method in accordance with claim 1, wherein the balancing of the CPU usage by each of the plurality of hosts further comprises minimizing CPU usage at selected hosts of the plurality of hosts.

6. A method in accordance with claim 1, wherein the collecting information about CPU usage by each of the plurality of hosts per a predetermined interval comprises:

measuring, using the one or more processors, a number of read-write lock requests issued from the information processing application for a subset of the plurality of objects provided by each host of the plurality of hosts and a duration associated with each read-write lock request; and

estimating, using the one or more processors, the CPU usage for each host based on the number and duration.

7. A method in accordance with claim 1, wherein the creating of the reorganization plan further comprises treating objects of the plurality of objects that differ in size by less a relative amount as equal in size.

8. A computer-implemented method for reorganizing a distributed computing landscape comprising a plurality of hosts, the method comprising:

creating, using one or more processors, a target data structure that is similar to a current data structure but representing the plurality of hosts as empty of objects prior to reorganizing the distributed computing landscape;

forming, using the one or more processors, two groups of objects based on large objects and small objects of the current data structure; and

reorganizing, using the one or more processors, the current data structure according to selection of new hosts for at least some of the large objects and small objects based on memory and central processing unit (CPU) values, the reorganizing comprising sorting the plurality of objects by size from largest to smallest, retaining the objects above a certain size based on the sorting on their current hosts in the target data structure, and distributing the objects below the certain size across the plurality of hosts to an approximately equal number of objects per host in the target data structure, the reorganizing further comprising recognizing a split object having more than one part and distributing the more than one part on different hosts of the plurality of hosts.

9. A method in accordance with claim 8, wherein reorganizing the target data structure further comprises:

selecting, using the one or more processors, a host having large objects and having the lowest memory and CPU values; and

moving, using the one or more processors, at least some of the large objects to other hosts.

10. A method in accordance with claim 8, wherein reorganizing the target data structures further comprises:

selecting, using the one or more processors, a host having small objects and having the lowest number of objects; and

moving, using the one or more processors, at least some of the small objects to other hosts.

11. A method in accordance with claim 8, further comprising executing the reorganizing, using the one or more processors.

12. A computer program product comprising a computer-readable storage medium including instructions that, when executed, perform operations comprising:

collecting, using one or more processors, information about an actual load distribution of resource usage by a distributed computing system comprising a plurality of hosts, the actual load distribution comprising static information concerning a total size in memory of each of a plurality of objects accessed by an information processing application implemented on the distributed computing system and CPU usage by each of the plurality of hosts per a predetermined interval, the collecting of information about CPU usage by each of the plurality of hosts per a predetermined interval comprising;

measuring, using the one or more processors, a number of read-write lock requests issued from the information processing application for a subset of the plurality of objects provided by each host of the plurality of hosts and a duration associated with each read-write lock request, and

estimating, using the one or more processors, the CPU usage for each host based on the number and duration;

calculating, using the one or more processors, a target load distribution of the resource usage by the distributed computing system, the target load distribution comprising a balancing of the CPU usage by each of the plurality of hosts;

using the one or more processors, sorting the plurality of objects by size from largest to smallest, retaining the objects above a certain size based on the sorting on their current hosts, and distributing the objects below the certain size across the plurality of hosts to an approximately equal number of objects per host to create a reorganization plan to transform the actual load distribution into the target load distribution;

generating, using the one or more processors, an estimate of an improvement of the resource usage to be realized by executing the reorganization plan; and

if the estimate of an improvement corresponds with the target load distribution, executing, using the one or more processors, the reorganization plan on the distributed computing system.

13. A computer program product in accordance with claim 12, wherein the information includes static information that comprises the total size of each of the plurality of objects and dynamic information that comprises the CPU usage by each of the plurality of hosts per the predetermined interval.

14. A computer program product in accordance with claim 12, further comprising instructions that, when executed, perform operations comprising:

minimizing, using the one or more processors, memory usage of the distributed computing system.