Method and apparatus for assigning tasks in a distributed server system

• US 6,223,205 B1
• Filed: 02/13/1998
• Issued: 04/24/2001
• Est. Priority Date: 10/20/1997
• Status: Expired due to Term

• Current Assignee: Boston University, Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Harchol-Balter, Mor, Crovella, Mark E.
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US09/023,893
• Time in Patent Office: 1,166 Days
• Field of Search: 709/312, 709/203, 709/102, 709/105, 709/100, 709/101, 709/103, 709/104
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/5013 Request control
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A distributed server system is disclosed which includes a load balancer and a plurality of host processors. The load balancer receives requests for service and distributes task assignments among the plurality of processors based upon the amount of work associated with the respective requests for service. More specifically, each host processor services requests for service within a predefined task size interval and the load balancer assigns to each host processor only those requests for service which involve task sizes within the particular task size interval associated with the respective processor. In the foregoing manner, the variability of the task sizes assigned to any given host processor is minimized and performance of the distributed server system is improved. In one embodiment of the invention, the thresholds defining the task size intervals served by respective host processors are selected using the task size distribution so as to attempt to allocate substantially the same amount of work to each of the host processors. In another embodiment of the invention, the thresholds defining the task size intervals served by the respective host processors are selected so as to intentionally vary the amount of work performed by the respective processors. This embodiment of the invention is intended to service requests for service in the nature of heavy tailed distributions. Task size interval assignments are skewed such that requests for service corresponding to smaller tasks are serviced by a host processor which is more lightly loaded than other processors. In this manner, mean slowdown metrics are improved.

Claims

1. Load balancing apparatus for assigning for processing received requests for service, said load balancing apparatus comprising:

a plurality of host processors for processing requests for service, wherein each of said host processors is operative to process requests for service within a predetermined task size interval;

a request dispatch processor operative to receive a request for service and to ascertain, based upon such request, the task size of the respective request;

said request dispatch processor operative to dispatch the request for service to one of said plurality of host processors for which the task size interval encompasses the task size for the respective request.

2. The load balancing apparatus of claim 1 wherein the predetermined task size intervals for the plurality of host processors are specified based upon an expected task size distribution.

3. The load balancing apparatus of claim 2 wherein the task size intervals for the respective host processors correspond to a unique portion of said expected task size distribution.

4. The load balancing apparatus of claim 2 wherein the task size intervals for the respective host processors are specified such that the sum of the task sizes corresponding to the requests expected to be served by each of the processors is approximately equal.

5. The load balancing apparatus of claim 2 wherein at least some of said plurality of host processors include at least one first come first serve queue and said at least some of said plurality of host processors are operative to queue requests for service in said at least one first come first serve queue upon receipt, and in advance of the processing of the respective requests.

6. The load balancing apparatus of claim 2 wherein at least some of said plurality of host processors are operative to queue requests for service in a time multiplexing manner upon receipt, in advance of the processing of the respective requests.

7. The load balancing apparatus of claim 2 wherein said request dispatch processor is further operative to dynamically reassign said task size intervals served by the respective host processors based upon historical task size data.

8. The load balancing apparatus of claim 2 wherein the requests for service comprise database queries, said host processors are operative to perform database queries in response to said requests for service, and said request dispatch processor is operative to determine the task size associated with said query.

9. The load balancing apparatus of claim 8 wherein said request dispatch processor is operative to determine the task size associated with said query based upon inspection of said query.

10. The load balancing apparatus of claim 2 wherein said request dispatch processor is operative to determine the task size associated with one of said requests for service based upon historical data pertaining to a similar request for service.

11. The load balancing apparatus of claim 2 wherein said request for service comprises a request to execute a program and said request dispatch processor is operative to determine the task size associated with the execution of the respective program.

12. The load balancing apparatus of claim 2 wherein said request dispatch processor comprises one of said plurality of host processors.

14. The load balancing apparatus of claim 1 wherein said distribution of task sizes approximates a heavily tailed distribution.

35. The load balancing apparatus of claim 1 wherein each of said host processors is operative in one of a plurality of service order modes and the service order mode for each of said host processors is specified based upon a predetermined criterion.

36. The load balancing apparatus of claim 35 wherein said predetermined criterion comprises the variance in the task size distribution of the tasks arriving at the respective host processor.

37. The load balancing apparatus of claim 1 wherein said requests for service comprise hypertext transport protocol requests.

39. The load balancing apparatus of claim 1 wherein said request dispatch processor is operative to dispatch a pre-determined percentage of the requests for service to one of said plurality of host processors for which the task size interval encompasses the task size for the respective request.

13. Load balancing apparatus for assigning tasks in response to requests for service appearing at said apparatus in the nature of a distribution of task sizes from small jobs to large jobs in which the small jobs comprise a majority of the requests for service and the large jobs comprise a minority of the requests for service, said apparatus comprising:

a plurality of host processors for processing requests for service, wherein each of said host processors is operative to process requests for service corresponding to task sizes within a predetermined task size interval, wherein said task size intervals are specified for the respective host processors such that at least one of the host processors servicing its respective task size interval is more lightly loaded than host processors servicing requests corresponding to larger task sizes;

a request dispatch processor operative to receive a request for service and to ascertain, based upon such request, the task size of the respective request;

said request dispatch processor being further operative to dispatch the request for service to the respective one of said plurality of host processors assigned to service tasks of the task size for the respective request.

15. The load balancing apparatus of claim 13 wherein said request dispatch processor comprises one of said plurality of host processors.

16. A method for assigning a request for service to one of a plurality of host processors in response to the receipt of said request for service, comprising the steps of:

assigning each host processor of said plurality of host processors to handle requests for service associated with task sizes within a specified task size interval;

receiving a request for service;

determining the task size associated with the respective request for service in response to receipt of the request for service;

dispatching the request for service to the respective one of said plurality of host processors for which the task size associated with the request for service is within the task size interval serviced by the respective host processors.

17. The method of claim 16 wherein said assigning step comprises the step of assigning each one of said plurality of host processors to handle requests for service associated with task sizes within said specified task size interval based upon an expected task size distribution.

18. The method of claim 17 wherein said assigning step further comprises the step of assigning each one of said plurality of host processors to handle requests for service associated with task sizes within a unique task size interval.

19. The method of claim 17 wherein said assigning step further comprises the step of assigning task size intervals to the respective host processors such that the sum of the task sizes expected to be served by each of the processors is approximately equal.

20. The method of claim 17 wherein at least some of said plurality of host processors include a first come first serve queue and said dispatching step further comprises the step of dispatching the request for service to the first come first serve queue in the respective host processor.

21. The method of claim 16 further comprising the step of processing the request for service at the respective host processor in a time multiplexing manner in the event no more than a predetermined number of requests for service have been dispatched to the respective host processor and remain unserviced.

22. The method of claim 16 further including the step of dynamically reassigning said task size intervals served by the respective host processors based upon historical task size data.

23. The method of claim 16 wherein said receiving step comprises the step of receiving a hypertext transport protocol request.

24. The method of claim 16 wherein said receiving step comprises the step of receiving a request to perform a database query, said determining step comprises the step of determining the task size associated with the database query and said dispatching step comprises the step of dispatching the database query to the respective one of said plurality of host processors based upon the task size for the respective query.

25. The method of claim 24 wherein said step of determining the task size of said query comprises the step of inspecting the database query to ascertain the task size associated with the respective query.

26. The method of claim 16 wherein said determining step comprises the step of determining the task size associated with the respective request for service based upon historical task size data.

27. The method of claim 26 wherein said step of determining the task size associated with the database query further comprises the step of assigning a task size to the respective request in the event historical task size data is unavailable, said dispatching step further comprises the step of dispatching the request for service to one of said plurality of host processors based upon the assigned task size for the respective request and said method further includes the step of generating and storing historical data pertaining to the respective request following the servicing of the request at the respective host processor.

28. The method of claim 16 wherein said dispatching step comprises the step of dispatching said request for service to at least one processor comprising the respective host processor in a distributed computing system.

29. The method of claim 16 wherein said receiving step comprises the step of receiving a request to execute a program and said determining step comprises the step of determining the task size associated with the execution of said program.

30. The method of claim 16 wherein said determining step comprises the step of performing at least one table lookup to determine the task size associated with the respective request for service.

31. The method of claim 16 wherein the request for service includes task size information indicative of the task size for the respective request and said determining step comprises the step of determining the task size for the request based upon said task size information contained within the request for service.

32. A method for assigning requests for service received at distributed server system to one of a plurality of host processors for service, wherein the nature of the received requests for service correspond to task sizes in the nature of a distribution of job task sizes from small jobs to large jobs in which the small jobs comprise a majority of the requests for service and the large jobs comprise a minority of the requests for service, said method comprising:

assigning each host processor of said plurality of host processors to handle requests for service associated with task sizes within predetermined task size intervals such that at least one of the host processors is more lightly loaded than the host processors servicing requests for service involving larger task sizes;

receiving said request for service;

determining the task size associated with the respective request for service;

dispatching the request for service to the respective one of said plurality of host processors for which the task size associated with the request for service is within the respective host processors assigned task size interval.

33. The method of claim 32 wherein said assigning step further comprises the step of assigning said the one of said plurality of host processors which is more lightly loaded to service the smallest jobs within said distribution of job task sizes.

34. The method of claim 32 wherein said assigning step further comprises the step of assigning the task size intervals to respective host processors such that at least some of the task size intervals comprise unique task size intervals.

38. A method for assigning a request for service to one of a plurality of host processors in response to the receipt of said request for service, comprising the steps of:

receiving a request for service communicated via the Internet;

determining the task size associated with the respective request for service in response to receipt of the request for service; and

dispatching the request for service to the respective one of said plurality of host processors in response to the determined task size associated with the request for service.