Load balancing utilizing adaptive thresholding

• US 9,456,056 B2
• Filed: 11/04/2013
• Issued: 09/27/2016
• 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: Rai, Vivek, Dumitriu, Dan Mihai, Sivasubramanian, Swaminathan
• Primary Examiner(s): Young, Steve
• Application Number:
  US14/071,245
• Publication Number:
  US 20140222895A1
• Time in Patent Office: 1,058 Days
• Field of Search: None
• US Class Current: 1/1
• 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

Methods and systems 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 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, the first server computing device associated with a first queue threshold, the first data request identifying a second queue threshold associated with a second server computing device;

comparing, by the first server computing device, the first queue threshold and the second queue threshold;

based on a determination that the second queue threshold is greater than or equal to the first queue threshold, increasing, by the first server computing device, the first queue threshold in order to process the first data request; and

accepting the first data request for processing, by the first server computing device, based on the comparison of the first queue threshold and the second queue threshold.

2. 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.

3. The method of claim 2, wherein the first request queue is configured to maintain a plurality of data requests for processing by the first server computing device.

4. 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 a second server computing device before the second server computing device rejects a data request.

5. The method of claim 4, wherein the second request queue is configured to maintain a plurality of data requests for processing by the first server computing device.

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

7. The method of claim 6, wherein adjusting the first queue threshold is responsive to a determination that the first queue threshold is less than or equal to the second queue threshold and further comprises increasing the first queue threshold to equal or exceed the second queue threshold.

8. The method of claim 1, wherein accepting the first data request for processing is responsive to a determination that the first queue threshold is less than or equal to the second queue threshold.

9. The method of claim 8, wherein accepting the first data request for processing further comprises placing the first data request in a first request queue.

10. The method of claim 1 further comprising rejecting the first data request, by the first server computing device, based on a determination that the first queue threshold is not less than or equal to the second queue threshold.

11. A system for managing requests comprising:

a data store; and

a first server, in communication with the data store and a network, configured 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 configured to;

receive a first data request including a second queue threshold from the client computer, wherein the second queue threshold is associated with a second server;

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

based on a determination that the second queue threshold is greater than or equal to the first queue threshold, increase the first queue threshold in order to accept the first data request for processing.

12. The system of claim 11, 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.

13. The system of claim 11, 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.

14. The system of claim 11, wherein the queue processing application is further configured to provide a rejection message including the first queue threshold based on a determination that the second queue threshold is less than the first queue threshold.

15. The system of claim 11, wherein the first server includes a queue processing application configured to manage the first request queue.

16. The system of claim 11, wherein the data store comprises at least one of a local database or a remote database.

17. 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 configured to,

provide a first data request to a first server having a first queue threshold, the first queue threshold indicative of a number of data requests that can be placed in a first request queue for processing by the first server before the first server rejects a data request;

receive a first rejection message including the first queue threshold from the first server indicating the first queue threshold is exceeded; and

provide a second data request to a second server having a second queue threshold, the second queue threshold indicative of a number of data requests that can be placed in a second request queue for processing by the second server before the second server rejects a data request, wherein the second data request includes the first queue threshold of the first server that has previously rejected the first data request,

wherein the second server is configured to increase the second queue threshold in order to accept the second data request for processing based on a determination that the second queue threshold is greater than or equal to the first queue threshold.

18. The computer-readable medium of claim 17, wherein the second server is configured to increase the second queue threshold by a predetermined amount.

19. The computer-readable medium of claim 17, wherein the second server is configured to increase the second queue threshold to be equal to the first queue threshold.