Programmatic response-time based workload distribution techniques

• US 7,207,043 B2
• Filed: 12/31/2002
• Issued: 04/17/2007
• Est. Priority Date: 12/31/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Daughtrey, Erik A., Cuomo, Gennaro A., Hogstrom, Matt R., Blythe, Christopher James
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): To; Jennifer N.
• Application Number:
  US10/334,262
• Publication Number:
  US 20040139433A1
• Time in Patent Office: 1,568 Days
• Field of Search: 718100-108, 709200-226, 707/3, 707/8, 705400-412
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G06Q 50/06 Energy or water supply

Abstract

Workload is programmatically distributed across a set of execution resources. In a multithreaded server environment, response time to end users is improved while increasing the efficiency of software execution and resource usage. Execution time and wait/queued time are tracked, for various types of requests being serviced by a server. Multiple logical pools of threads are used to service these requests, and inbound requests are directed to a selected one of these pools such that requests of similar execution-time requirements are serviced by the threads in that pool. The number and size of thread pools may be adjusted programmatically, and the distribution calculation (i.e., determining which inbound requests should be assigned to which pools) is a programmatic determination. In preferred embodiments, only one of these variables is adjusted at a time, and the results are monitored to determine whether the effect was positive or negative. The disclosed techniques also apply to tracking and classifying requests by method name (and, optionally, parameters).

Claims

1. A computer-implemented method of programmatically distributing workload across thread pools of a multithreaded server, comprising:

determining a number of available thread pools at the server;

obtaining execution times from historical statistics of a workload on the server;

programmatically distributing the obtained execution times over the number of available thread pools, further comprising;

sorting the obtained execution times;

determining a count of the execution times;

dividing the count of execution times by the number of available thread pools to find a value, “

N”

; and

assigning an upper bound on execution time for each of the available thread pools, according to the sorted execution times when accessed using integer multiples of the value “

N”

as an index; and

using the assigned upper bounds for assigning inbound requests to the available thread pools at run time.

2. The method according to claim 1, wherein using the assigned upper bounds further comprises:

receiving at the server, at run time, the inbound requests;

determining, for each of the received requests, an expected execution time for that request; and

assigning each of the inbound requests to a first one of the available thread pools for which the assigned upper bound is greater than or equal to the expected execution time of the inbound request, or to a last one of the available thread pools if none of the assigned upper bounds is greater than or equal to the expected execution time.

3. The method according to claim 2, further comprising:

tracking execution time of each of the inbound requests as they execute at the server; and

revising the historical statistics of the workload on the server to reflect the tracked execution times.

4. The method according to claim 3, further comprising periodically recomputing the assigned upper bounds to reflect the revised historical statistics by repeating operation of the determining of the number of available threads, the obtaining, and the programmatically distributing.

5. The method according to claim 1, wherein the obtained execution times are moving average execution times.

6. The method according to claim 1, wherein the obtained execution times are maintained per request type.

7. The method according to claim 1, wherein the obtained execution times are maintained per request type and parameter value.

8. The method according to claim 1, wherein the obtained execution times are maintained per method name.

9. The method according to claim 1, wherein the obtained execution times are maintained per method name and parameter values.

10. The method according to claim 1, wherein the obtained execution times are maintained per method name and parameter names and values.

11. The method according to claim 1, wherein the obtained execution times are maintained per Uniform Resource Identifier (“

URI”

) name and parameter values.

12. The method according to claim 1, wherein the obtained execution times are maintained per processing destination.

13. The method according to claim 1, wherein using the assigned upper bounds further comprises, for each of the inbound requests,

receiving the inbound request at the server;

determining a classification key of the received request;

locating an average execution time for the received request, using the determined classification key; and

assigning the received request to a particular one of the available thread pools for executing the received request by iteratively comparing the located average execution time to each of the assigned upper bounds until the compared-to assigned upper bound is greater than or equal to the located average execution time and assigning the received request to the available thread pool having that compared-to assigned upper bound, or assigning the received request to a last one of the available thread pools if none of the compared-to assigned upper bounds is greater than or equal to the located average execution time.

14. The method according to claim 1, wherein the thread pools are logically organized groupings of a physical thread pool.

15. A system for programmatically distributing inbound requests across thread pools in a multithreaded server, comprising:

means for determining a number of available thread pools at the server;

means for obtaining execution times from historical statistics of a workload on the server;

means for programmatically distributing the obtained execution times over the number of available thread pools, further comprising;

means for sorting the obtained execution times;

means for determining a count of the execution times;

means for dividing the count of execution times by the number of available thread pools to find a value, “

N”

; and

means for assigning an upper bound on execution time for each of the available thread pools, according to the sorted execution times when accessed using integer multiples of the value “

N”

as an index;

means for receiving at the server, at run time, inbound requests; and

means for assigning the received requests to the available thread pools according to the assigned upper bounds.

16. The system according to claim 15, further comprising:

means for tracking execution time of each of the inbound requests as they execute at the server; and

means for revising the historical statistics of the workload on the server to reflect the tracked execution times.

17. The system according to claim 16, further comprising means for periodically recomputing the assigned upper bounds to reflect the revised historical statistics by repeating operation of the means for determining the number of available threads the means for obtaining, and the means for programmatically distributing.

18. The system according to claim 15, wherein the obtained execution times are moving average execution times.

19. The system according to claim 15, wherein the obtained execution times are maintained per request type.

20. The system according to claim 15, wherein the obtained execution times are maintained per method name.

21. The system according to claim 15, wherein the obtained execution times are maintained per Uniform Resource Identifier (“

URI”

) name.

22. The system according to claim 15, wherein the obtained execution times are maintained per processing destination.

23. The system according to claim 15, wherein the means for assigning further comprises, for each of the received inbound requests:

means for determining a classification key of the received request;

means for locating an average execution time for the received request, using the determined classification key; and

means for assigning the received request to a particular one of the available thread pools for executing the received request by iteratively comparing the located average execution time to each of the assigned upper bounds until the compared-to assigned upper bound is greater than or equal to the located average execution time and assigning the received request to the available thread pool having that compared-to assigned upper bound, or assigning the received request to a last one of the available thread pools if none of the compared-to assigned upper bounds is greater than or equal to the located average execution time.

24. A computer program product for programmatically distributing workload across thread pools of a multithreaded server, the computer program product embodied on one or more computer readable media readable by a computing system in a computing environment and comprising:

computer-readable program code for determining a number of available thread pools at the server;

computer-readable program code for obtaining execution times from historical statistics of a workload on the server;

computer-readable program code for programmatically distributing the obtained execution times over the number of available thread pools, further comprising;

computer-readable program code for sorting the obtained execution times;

computer-readable program code for determining a count of the execution times;

computer-readable program code for dividing the count of execution times by the number of available thread pools to find a value, “

N”

; and

computer-readable program code for assigning an upper bound on execution time for each of the available thread pools, according to the sorted execution times when accessed using integer multiples of the value “

N”

as an index; and

computer-readable program code for using the assigned upper bounds for assigning inbound requests to the available thread pools at run time.

25. The computer program product according to claim 24, wherein the computer-readable program code for using further comprises:

computer-readable program code for receiving at the server, at run time, the inbound requests;

computer-readable program code for determining, for each of the received requests, an expected execution time for that request; and

computer-readable program code for assigning each of the inbound requests to a first one of the available thread pools for which the assigned upper bound is greater than or equal to the expected execution time of the inbound request, or to a last one of the available thread pools if none of the assigned upper bounds is greater than or equal to the expected execution time.

26. The computer program product according to claim 25, further comprising:

computer-readable program code for tracking execution time of each of the inbound requests as they execute at the server; and

computer-readable program code for revising the historical statistics of the workload on the server to reflect the tracked execution times.

27. The computer program product according to claim 26, further comprising the step of periodically recomputing the assigned upper bounds to reflect the revised historical statistics by repeating operation of the computer-readable program code for determining the number of available threads, the computer-readable program code for obtaining, and the computer-readable program code for programmatically distributing.

28. The computer program product according to claim 24, wherein the obtained execution times are maintained per request type, parameter names, and parameter values.

29. The computer program product according to claim 24, wherein the obtained execution times are maintained per method name and parameter values.

30. The computer program product according to claim 24, wherein the obtained execution times are maintained per Uniform Resource Identifier (“

URI”

) name and parameter values.

31. The computer program product according to claim 24, wherein the obtained execution times are maintained per processing destination.

32. The computer program product according to claim 24, wherein the computer-readable program code for using further comprises, for each of the inbound requests:

computer-readable program code for receiving the inbound request at the server;

computer-readable program code for determining a classification key of the received request;

computer-readable program code for locating an average execution time for the received request, using the determined classification key; and

computer-readable program code for assigning the received request to particular one of the available thread pools for executing the received request by iteratively comparing the located average execution time to each of the assigned upper bounds until the compared-to assigned upper bound is greater than or equal to the located average execution time and assigning the received request to the available thread pool having that compared-to assigned upper bound, or assigning the received request to a last one of the available thread pools if none of the compared-to assigned upper bounds is greater than or equal to the located average execution time.

33. A method of programmatically distributing workload across thread pools of a multithreaded server, comprising steps of:

programmatically monitoring operational characteristics of a workload at a server;

programmatically distributing the workload across thread pools of the server, further comprising the steps of;

determining a number of available thread pools at the server;

obtaining execution times from historical statistics of the workload;

programmatically distributing the obtained execution times over the number of available thread pools, further comprising;

sorting the obtained execution times;

determining a count of the execution times;

dividing the count of execution times by the number of available thread pools to find a value, “

N”

; and

assigning an upper bound on execution time for each of the available thread pools, according to the sorted execution times when accessed using integer multiples of the value “

N”

as an index;

receiving at the server, at run time, inbound requests; and

assigning each of the inbound requests to a first one of the available thread pools for which the assigned upper bound is greater than or equal to an expected execution time for the request, or to a last one of the available thread pools if none of the assigned upper bounds is greater than or equal to the expected execution time; and

charging a fee for carrying out the programmatically monitoring and programmatically distributing steps.