Load balancing utilizing adaptive thresholding

• US 8,159,961 B1
• Filed: 03/30/2007
• Issued: 04/17/2012
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sivasubramanian, Swaminathan, Rai, Vivek, Dumitriu, Dan Mihai
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): Mitchell, Daniel
• Application Number:
  US11/694,667
• Time in Patent Office: 1,845 Days
• Field of Search: None
• US Class Current: 370/252
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

A method and a system for processing data requests in a client-server computing environment, such as the Web, are disclosed. A client device initially transmits a data request to a randomly selected first server device. The first server device may reject the data request if its request queue threshold is exceeded. The client device retransmits the data request, including the request queue threshold, to a randomly selected second server device. The second server device may reject the data request if the request queue threshold of the first server device is smaller than a request queue threshold of the second server device. The client device transmits the data request back to the first server device, including the request queue threshold of the second server device. The first server device processes the data request and adjusts its request queue threshold based on the request queue thresholds of the first and the second server devices.

Claims

1. A computer-implemented method of operating a server computing device to process data requests, the method comprising:

receiving a first data request from a client computing device at a first server computing device, wherein the first data request includes a second queue threshold obtained from a second server computing device;

comparing, by the first server computing device, a first queue threshold associated with the first server computing device and the second queue threshold obtained from the second server computing device;

determining, by the first server computing device, whether to process the data request at the first server computing device based on the comparison of the first queue threshold and the second queue threshold; and

responsive to a determination not to process the data request at the first server computing device, providing, by the first server computing device, a rejection message to the client computing device, wherein the rejection message includes the first queue threshold, and wherein the client computing device is configured to provide a second data request including the first queue threshold to the second server computing device.

2. The method of claim 1, wherein receiving a first data request comprises receiving the data request from a network.

3. The method of claim 1, wherein the first queue threshold is indicative of a number of data requests that can be placed in a first request queue for processing by the first server computing device before the first server computing device rejects a data request.

4. The method of claim 3, wherein the first request queue is operable to hold a plurality of data requests.

5. The method of claim 1, wherein the second queue threshold is indicative of a number of data requests that can be placed in a second request queue for processing by the second server computing device before the second serving computing device rejects a data request.

6. The method of claim 5, wherein the second request queue is operable to hold a plurality of data requests.

7. The method of claim 1, wherein determining whether to process the data request comprises determining whether the first queue threshold is less than or equal to the second queue threshold.

8. A system for load balancing comprising:

a first server operable to receive and process data requests from client computers, wherein the first server includes a first data store coupled with the first server for storing information associated with a data request and a first request queue including a first queue threshold, the first request queue operable to store a first number of data requests, the first number of data requests being less than the first queue threshold; and

a second server, coupled with a network, operable to receive and process data requests from client computers, wherein the second server includes a second data store coupled with the second server for storing information associated with a data request and a second request queue including a second queue threshold, the second request queue operable to store a second number of data requests, the second number of data requests being less than the second queue threshold;

wherein the first server receives a first data request including the second queue threshold from a client computer, wherein the second queue threshold was included in a first rejection message provided to the client computer by the second server, wherein the first server provides a second rejection message to the client computer responsive to a comparison of the first queue threshold and the second queue threshold included in the data request, and wherein the client computer is configured to send a second data request to the second server including the first queue threshold responsive to receipt of the second rejection message.

9. The system of claim 8, wherein the first server includes a queue processing application operable to manage the first request queue.

10. The system of claim 8, wherein the second server includes a queue processing application operable to manage the second request queue.

11. The system of claim 10, wherein the queue processing application is a stand-alone application.

12. The system of claim 8, wherein the first server increases the first queue threshold to be equal to the second queue threshold if the comparison of the first queue threshold and the second queue threshold indicates that the first queue threshold is less than the second queue threshold.

13. The system of claim 8, wherein the first server increases the first queue threshold by a predetermined amount if the comparison of the first queue threshold and the second queue threshold indicates that the first queue threshold is equal to the second queue threshold.

14. The system of claim 8, wherein the first server processes the first data request if the comparison of the first queue threshold and the second queue threshold indicates that the second queue threshold is greater than the first queue threshold.

15. A system for load balancing comprising:

a first server operable to receive and process data requests from a client computing device, wherein the first server includes a first data store coupled with the first server for storing information associated with a data request and a first request queue including a first queue threshold, the first request queue operable to store a first number of data requests, the first number of data requests being less than the first queue threshold; and

a second server, coupled with a network, operable to receive and process data requests from the client computing device, wherein the second server includes a second data store coupled with the second server for storing information associated with a data request and a second request queue including a second queue threshold, the second request queue operable to store a second number of data requests, the second number of data requests being less than the second queue threshold;

wherein the first server receives a first data request including the second queue threshold from a client computer, wherein the first server provides a first rejection message including the first queue threshold to the client computer responsive to a comparison of the first queue threshold and the second queue threshold included in the data request, and wherein the client computer is configured to send a second data request to the second server including the first queue threshold.

16. The system of claim 15, wherein the client computing device is programmed to select the first server and the second server based on a weighted probability.

17. The system of claim 16, wherein the weighted probability is determined based on a load on the first and second server.

18. The system of claim 17, wherein the load on the first server is determined based on a length of the first request queue.

19. The system of claim 17, wherein the load on the first or second server is determined based on a latency of data request processing.

20. The system of claim 15, wherein the client computing device is programmed to select the first server and the second server based on a random number.

21. The system of claim 15, wherein the client computing device is programmed to select the first server and the second server based on a preassigned server identifier.

22. A system for load balancing comprising:

a data store; and

a first server, coupled with the data store and a network, operable to obtain and process a data request from a client computer, the first server including;

a first request queue having a first queue threshold; and

a queue processing application operable to;

receive a first data request including a second queue threshold from the client computer, wherein the second queue threshold corresponds to a second server, and wherein the second queue threshold is associated with a rejection message received by the client computer from the second server;

process the second queue threshold to compare the first queue threshold and the second queue threshold; and

provide a rejection message including the first queue threshold based on the comparison of the first queue threshold and the second queue threshold, wherein the client computing device provides a second data request to the second server including the first queue threshold responsive to receipt of the rejection message.

23. The system of claim 22, wherein the data store comprises a local database.

24. The system of claim 22, wherein the data store comprises a remote database.

25. The system of claim 22, wherein the first server increases the first queue threshold to be equal to the second queue threshold if the first queue threshold is less than the second queue threshold.

26. The system of claim 22, wherein the first server increases the first queue threshold by a predetermined amount if the first queue threshold is equal to the second queue threshold.

27. The system of claim 22, wherein the first server processes the data request if the second queue threshold is greater than the first queue threshold.

28. A computer-implemented method for processing data requests, the method comprising:

transmitting a first data request to a first server computing device having a first queue threshold;

receiving a first rejection message, including the first queue threshold, from the first server computing device if the first queue threshold is exceeded;

in response to receiving the first rejection message, forming a second data request by adding the first queue threshold to the first data request, and transmitting the second data request to a second server computing device having a second queue threshold;

receiving a second rejection message, including the second queue threshold, from the second server computing device if the second queue threshold is exceeded and the second queue threshold is greater than the first queue threshold; and

in response to receiving the second rejection message, forming a third data request by adding the second queue threshold to the first data request, and transmitting the third data request to the first server computing device.

29. The method of claim 28, wherein transmitting a first data request comprises transmitting the first data request using Web protocols.

30. The method of claim 28, wherein the first server computing device is selected randomly.

31. The method of claim 28, wherein the second server computing device is selected randomly.

32. The method of claim 28, wherein the first server computing device is selected based on a weighted probability.

33. The method of claim 32, wherein the weighted probability is determined based on a load on the first server computing device.

34. The method of claim 33, wherein the load on the first server computing device is determined based on a length of a first request queue associated with the first server computing device.

35. The method of claim 33, wherein the load on the first server computing device is determined based on a latency of data request processing by the first server computing device.

36. The method of claim 28, wherein the first server computing device and the second server computing device are selected based on a random number.

37. The method of claim 28, wherein the first server computing device and the second server computing device are selected based on a preassigned server identifier.

38. A non-transitory computer-readable medium having computer-executable components stored thereon, wherein in response to execution, the components cause a computer to process data requests, the components comprising:

a data request component for providing a first data request to a first server;

an alternate data request component for providing a second data request to a second server, wherein the second data request specifies a queue threshold of the first server that has previously rejected the first data request,

wherein the data request component is configured to provide a third data request to the first server responsive to receipt of a rejection message from the second server, wherein the rejection message from the second server is based at least in part on a comparison of the queue threshold of the first server and a queue threshold of the second server, and wherein the third data request includes the queue threshold of the second server.