Adaptive Demand-Driven Load Balancing

• US 20110321058A1
• Filed: 06/24/2010
• Published: 12/29/2011
• Est. Priority Date: 06/24/2010
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schmidt, Olaf
• Granted Patent: US 8,719,833 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

The present disclosure involves systems, software, and computer implemented methods for providing adaptive demand-driven load balancing for processing jobs in business applications. One process includes operations for identifying a workload for distribution among a plurality of work processes. A subset of the workload is assigned to a plurality of work processes for processing of the subset of the workload based on an application-dependent algorithm. An indication of availability is received from one of the plurality of work processes, and a new subset of the workload is assigned to the work process.

Claims

1. A computer implemented method performed by one or more processors for balancing a workload, the method comprising the following operations:

identify a workload for distribution among a plurality of work processes;

assign a subset of the workload to a plurality of work processes for processing of the subset of the workload, the subset of the workload assigned based on an application-dependent algorithm and further divided into work packages, each work package assigned to a different work process;

receive an indication of availability from a particular one of the plurality of work processes that has completed processing of a particular work package assigned to the particular work process; and

assign a new subset of the workload to the particular one of the plurality of work processes in response to receiving the indication of availability.

2. The method of claim 1, wherein each work process is a computer processor or a server.

3. The method of claim 1, wherein each work package is divided into a particular size based on the application-dependent algorithm.

4. The method of claim 1, wherein each work package is further assigned to a work process based on a dynamically determined priority of particular work packages.

5. The method of claim 1, wherein the application-dependent algorithm is selected based on at least one of a type of the workload, a number of work processes in the plurality of work processes, a business context of the workload, or a type of the work processes in the plurality of work processes.

6. The method of claim 1, wherein the new subset of the workload is assigned based on a different application-dependent algorithm.

7. The method of claim 1, wherein the application-dependent algorithm is based on parameters including at least one of an estimate of a maximum deviation of processing times for two different work items from the workload, a number of work processes in the plurality of work processes, or a number of work items in the workload.

8. The method of claim 7, wherein the estimate of a maximum deviation of processing times for two different work items from the workload is determined based on historical data of processing times associated with work items similar to the work items in the workload.

9. The method of claim 8, wherein the subset of the workload is further assigned based on an amount of the historical data of processing times associated with work items similar to the work items in the workload.

10. The method of claim 1, wherein the subset of the workload is assigned without analyzing a content of the subset of the workload.

11. The method of claim 1, wherein the work packages are equal in size.

12. A computer program product encoded on a tangible storage medium, the product comprising computer readable instructions for causing one or more processors to perform operations comprising:

identifying a workload for distribution among a plurality of work processes;

segmenting the workload into a plurality of work packages, each work package segmented into a particular size based on an application-dependent algorithm;

assigning a portion of the plurality of work packages to at least some of the plurality of work processes;

receiving an indication of availability from a particular one of the plurality of work processes that has completed processing of a particular work package assigned to the work process; and

assigning at least one remaining work package in the plurality of work packages to the particular one of the plurality of work processes in response to receiving the indication of availability.

13. The computer program product of claim 12, wherein the at least one remaining work package is assigned based on a different application-dependent algorithm.

14. The computer program product of claim 12, wherein the application-dependent algorithm is based on parameters including at least one of an estimate of a maximum deviation of processing times for two different work items from the workload, a number of work processes in the plurality of work processes, or a number of work items in the workload.

15. The computer program product of claim 14, wherein the estimate of a maximum deviation of processing times for two different work items from the workload is determined based on historical data of processing times associated with work items similar to the work items in the workload.

16. The computer program product of claim 15, wherein the portion of the plurality of work packages is assigned based at least in part on an amount of the historical data of processing times associated with work items similar to the work items in the workload.

17. A system, comprising:

memory operable to store information associated with an application-dependent algorithm for load balancing; and

one or more processors operable to;

identify a workload for distribution among a plurality of work processes;

segment the workload into a plurality of work packages, each work package segmented into a particular size based on the application-dependent algorithm;

assign a portion of the plurality of work packages to at least some of the plurality of work processes;

receive an indication of availability from a particular one of the plurality of work processes that has completed processing of a particular work package assigned to the particular work process; and

assign at least one remaining work package in the plurality of work packages to the particular one of the plurality of work processes in response to receiving the indication of availability.

18. The system of claim 17, wherein the application-dependent algorithm is based on parameters including at least one of an estimate of a maximum deviation of processing times for two different work items from the workload, a number of work processes in the plurality of work processes, or a number of work items in the workload.

19. The system of claim 18, wherein the estimate of a maximum deviation of processing times for two different work items from the workload is determined based on historical data of processing times associated with work items similar to the work items in the workload.

20. The system of claim 17, wherein the work packages are assigned without analyzing a content of the workload.