Load balancing system and method in a multiprocessor system

• US 7,203,747 B2
• Filed: 05/25/2001
• Issued: 04/10/2007
• Est. Priority Date: 05/25/2001
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Broder, Andrei, Bhat, Prashanth B., Kasperski, Richard A.
• Primary Examiner(s): BULLOCK JR, LEWIS ALEXANDER
• Application Number:
  US09/865,988
• Publication Number:
  US 20030037093A1
• Time in Patent Office: 2,146 Days
• Field of Search: 709200-253, 707 1- 10, 707100-1041, 707200-206, 718/1, 718100-108
• US Class Current: 709/224
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system and method are disclosed for selecting a resource, among a plurality of resources, for servicing a request. To select a resource to service the request, a first resource is randomly selected. If a first load value associated with the first resource does not exceed a threshold value, the request is assigned to the first resource for servicing. Otherwise a second resource is randomly selected. If a second load value associated with the second resource does not exceed a threshold value, the request is assigned to the second resource for servicing. If the second load value exceeds the threshold value, the request is assigned whichever of the first and second resources has a lower load value.

Claims

1. A method for choosing a resource for processing a search query on the world wide web, among a plurality of resources, comprising:

randomly selecting a first resource among the plurality of resources in accordance with a predefined first random selection function, the first resource having an associated first load value;

performing a first comparison between the first load value and a predetermined threshold value to determine whether the first load value exceeds the predetermined threshold value;

executing said search query by said first resource when said first comparison returns false; and

randomly selecting a second different resource with a second load value among the plurality of resources in accordance with a predefined second random selection function when said first comparison returns true, wherein said first random selection function is different from said second random selection function.

2. The method of claim 1, further comprising:

performing a second comparison between said second load value and said predetermined threshold value to determine whether the second load value exceeds the predetermined threshold value;

assigning the search query to said second different resource for servicing the search query when said second comparison result returns false.

3. The method of claim 2, further comprising:

comparing the first load value to the second load value and assigning the search query to one of the first resource and second resource having a lower associated load value for servicing the search query when said second comparison result return true.

4. The method of claim 2, wherein the randomly selecting a second resource is performed by applying a one-way hashing function to the search query to generate a first intermediate value, applying a modulo function to the intermediate value to generate a second intermediate value;

and applying a mapping function for mapping the second intermediate value so as to select the second resource from among the plurality of resources.

5. The method of claim 4, wherein the modulo function applied has a modulus whose value corresponds to a total load handling capacity of the plurality of resources excluding the first resource.

6. The method of claim 5, wherein each of the resources of the plurality of resources has an associated respective load handling capacity;

and the mapping function is a probability density function in which each resource in the plurality of resources, excluding the first resource, has a mapping range whose size corresponds to the respective load handling capacity associated with the resource.

7. The method of claim 5, wherein each of the resources of the plurality of resources has an associated respective load handling capacity;

and the mapping function is a weighted mapping function that is weighted in accordance with the respective load handling capacities associated with the plurality of resources excluding the first resource.

8. The method of claim 1, further comprising:

determining whether the first resource is unavailable for selection;

upon determining that the first resource is unavailable for selection, determining which of the plurality of resources are available for selection and redefining the plurality of resources to include only those of the plurality of resources that are available for selection, and then randomly selecting a resource from among the redefined plurality of resources.

9. The method of claim 1, wherein the randomly selecting is performed by applying a one-way hashing function to the search query to generate a first intermediate value, applying a modulo function to the intermediate value to generate a second intermediate value;

and applying a mapping function for mapping the second intermediate value so as to select the first resource from among the plurality of resources.

10. The method of claim 9, wherein the modulo function applied has a modulus whose value corresponds to a total load capacity of the plurality of resources.

11. The method of claim 9, wherein each of the resources of the plurality of resources has an associated respective load capacity;

and the mapping function is a probability density function in which each resource in the plurality of resources has a mapping range whose size corresponds to the respective load capacity associated with the resource.

12. The method of claim 9, wherein each of the resources of the plurality of resources has an associated respective load capacity;

and the mapping function is a weighted mapping function that is weighted in accordance with the respective load capacities associated with the plurality of resources.

13. A system for selecting a resource for processing a search query on the world wide web, among a plurality of resources, comprising:

one or more interfaces for receiving a search query and for forwarding the search query to a selected resource;

one or more processing units for executing stored procedures;

memory for storing the procedures executed by the one or more processing units, the procedures including;

instructions for randomly selecting a first resource among the plurality of resources in accordance with a predefined first random selection function, the first resource having an associated first load value;

first comparing instructions for comparing the first load value to a predetermined threshold value to determine whether the first load value exceeds the predetermined threshold value;

instructions for assigning the search query to the first resource for servicing the search query by said first resource when execution of the first comparing instructions determines that the first load value does not exceed the predetermined threshold value; and

instructions for randomly selecting a second different resource with a second load value among the plurality of resources in accordance with a predefined second random selection function when said first load value exceeds the predetermined threshold value, wherein said first random selection function is different from said second random selection function.

14. The system of claim 13, further comprising:

second comparing instructions for comparing the second load value to the predetermined threshold value to determine whether the second load value exceeds the predetermined threshold value; and

instructions for assigning the search query to the second different resource for servicing the search query when execution of the second comparing instructions determines that the second load value does not exceed the predetermined threshold value.

15. The system of claim 14, including additional instructions whose execution by the one or more processing units is invoked when the second comparing instructions determine that the second load value exceeds the predetermined threshold value, the additional instructions including:

instructions for comparing the first load value to the second load value and assigning the search query to one of the first resource and second resource having a lower associated load value for servicing the search query.

16. The system of claim 14, wherein the instructions for randomly selecting a second resource include instructions for applying a one-way hashing function to the search query to generate a first intermediate value, applying a modulo function to the intermediate value to generate a second intermediate value, and applying a mapping function for mapping the second intermediate value so as to select the second resource from among the plurality of resources.

17. The system of claim 16, wherein the modulo function applied has a modulus whose value corresponds to a total load handling capacity of the plurality of resources excluding the first resource.

18. The system of claim 17, wherein each of the resources of the plurality of resources has an associated respective load handling capacity;

and the mapping function is a probability density function in which each resource in the plurality of resources, excluding the first resource, has a mapping range whose size corresponds to the respective load handling capacity associated with the resource.

19. The system of claim 17, wherein each of the resources of the plurality of resources has an associated respective load handling capacity;

and the mapping function is a weighted mapping function that is weighted in accordance with the respective load handling capacities associated with the plurality of resources excluding the first resource.

20. The system of claim 13, including additional instructions for:

determining whether the first resource is unavailable for selection;

upon determining that the first resource is unavailable for selection, determining which of the plurality of resources are available for selection and redefining the plurality of resources to include only those of the plurality of resources that are available for selection, and then randomly selecting a resource from among the redefined plurality of resources.

21. The system of claim 13, wherein the instructions for randomly selecting a first resource include instructions for applying a one-way hashing function to the search query to generate a first intermediate value, applying a modulo function to the intermediate value to generate a second intermediate value, and applying a mapping function for mapping the second intermediate value so as to select the first resource from among the plurality of resources.

22. The system of claim 21, wherein the modulo function applied has a modulus whose value corresponds to a total load capacity of the plurality of resources.

23. The system of claim 21, wherein each of the resources of the plurality of resources has an associated respective load capacity;

and the mapping function is a probability density function in which each resource in the plurality of resources has a mapping range whose size corresponds to the respective load capacity associated with the resource.

24. The system of claim 21, wherein each of the resources of the plurality of resources has an associated respective load capacity;

and the mapping function is a weighted mapping function that is weighted in accordance with the respective load capacities associated with the plurality of resources.

25. A system for selecting a resource for processing a search query on the world wide web, among a plurality of resources, comprising:

one or more interfaces for receiving the search query and for forwarding the search query to a selected resource;

control logic configured to randomly select a first resource among the plurality of resources in accordance with a predefined first random selection function, the first resource having an associated first load value;

performing a first comparison of the first load value to a predetermined threshold value to determine whether the first load value exceeds the predetermined threshold value;

assign the search query to the first resource for servicing the search query by the first resource when the first load value does not exceed the predetermined threshold value; and

control logic further configured to randomly selecting a second different resource with a second load value among the plurality of resources in accordance with a predefined second random selection function when the first load value exceeds the predetermined threshold value, wherein said first random selection function is different from said second random selection function.

26. The system of claim 25, further comprising:

performing a second comparison between said second load value and said predetermined threshold value to determine whether said second load value exceeds the predetermined threshold value; and

assigning the search query to the second resource for servicing the search query when it is determined that the second load value does not exceed the predetermined threshold value.

27. The system of claim 26, wherein the control logic is further configured to assign the search query to whichever of the first and second resources has a lower associated load value when the second load value exceeds the predetermined threshold value.

28. A computer program product for use in conjunction with a computer system having one or more interfaces for receiving a search query and for forwarding the search query to a selected resource for processing the search query on the world wide web, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for randomly selecting a first resource among the plurality of resources in accordance with a predefined first random selection function, the first resource having an associated first load value;

first comparing instructions for comparing the first load value to a predetermined threshold value to determine whether the first load value exceeds the predetermined threshold value; and

instructions for assigning the search query to the first resource for servicing the search query by the first resource when execution of the first comparing instructions determines that the first load value does not exceed the predetermined threshold value; and

instructions for randomly selecting a second different resource with a second load value among the plurality of resources in accordance with a predefined second random selection function when the first load value exceeds the predetermined threshold value, wherein said first random selection function is different from said second random selection function.

29. The computer program product of claim 28, further comprising:

second comparing instructions for comparing the second load value to the predetermined threshold value to determine whether the second load value exceeds the predetermined threshold value; and

instructions for assigning the search query to the second resource for servicing the search query when execution of the second comparing instructions determines that the second load value does not exceed the predetermined threshold value.

30. The computer program product of claim 29, including additional instructions whose execution by the one or more processing units is invoked when the second comparing instructions determine that the second load value exceeds the predetermined threshold value, the additional instructions including:

instructions for comparing the first load value to the second load value and assigning the search query to one of the first resource and second resource having a lower associated load value for servicing the search query.

31. The computer program product of claim 29, wherein the instructions for randomly selecting a second resource include instructions for applying a one-way hashing function to the search query to generate a first intermediate value, applying a modulo function to the intermediate value to generate a second intermediate value, and applying a mapping function for mapping the second intermediate value so as to select the second resource from among the plurality of resources.

32. The computer program product of claim 31, wherein the modulo function applied has a modulus whose value corresponds to a total load handling capacity of the plurality of resources excluding the first resource.

33. The computer program product of claim 32, wherein each of the resources of the plurality of resources has an associated respective load handling capacity;

and the mapping function is a probability density function in which each resource in the plurality of resources, excluding the first resource, has a mapping range whose size corresponds to the respective load handling capacity associated with the resource.

34. The computer program product of claim 32, wherein each of the resources of the plurality of resources has an associated respective load handling capacity;

and the mapping function is a weighted mapping function that is weighted in accordance with the respective load handling capacities associated with the plurality of resources excluding the first resource.

35. The computer program product of claim 28, including additional instructions for:

determining whether the first resource is unavailable for selection;

upon determining that the first resource is unavailable for selection, determining which of the plurality of resources are available for selection and redefining the plurality of resources to include only those of the plurality of resources that are available for selection, and then randomly selecting a resource from among the redefined plurality of resources.

36. The computer program product of claim 28, wherein the instructions for randomly selecting a first resource include instructions for applying a one-way hashing function to the search query to generate a first intermediate, value, applying a modulo function to the intermediate value to generate a second intermediate value, and applying a mapping function for mapping the second intermediate value so as to select the first resource from among the plurality of resources.

37. The computer program product of claim 36, wherein the modulo function applied has a modulus whose value corresponds to a total load capacity of the plurality of resources.

38. The computer program product of claim 36, wherein each of the resources of the plurality of resources has an associated respective load capacity;

and the mapping function is a probability density function in which each resource in the plurality of resources has a mapping range whose size corresponds to the respective load capacity associated with the resource.

39. The computer program product of claim 36, wherein each of the resources of the plurality of resources has an associated respective load capacity;

and the mapping function is a weighted mapping function that is weighted in accordance with the respective load capacities associated with the plurality of resources.