Decentralized request routing

• US 8,843,630 B1
• Filed: 08/20/2009
• Issued: 09/23/2014
• Est. Priority Date: 08/27/2008
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Thomas, Christopher C., Chatterjee, Preetha, Zhong, Nan, Rai, Vivek, Kommareddy, Christopher, Sundt, Mitchell
• Primary Examiner(s): Winder, Patrice
• Assistant Examiner(s): Chang, Julian
• Application Number:
  US12/544,517
• Time in Patent Office: 1,860 Days
• Field of Search: 709217-219, 709223-226, 709201-203, 709/235, 370229-240
• US Class Current: 709/226
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1025 Dynamic adaptation of the criteria on which the server selection is based

Abstract

Systems and methods provide logic for decentralized request routing. In one implementation, a computer-implemented method routes a request. The method includes receiving, by a client server, the request. The client server evaluates feedback information received by the client server from at least one of a plurality of host servers. The client server selects one of the plurality of host servers to process the request, based on the evaluation, and transmits the request to the selected one of the plurality of host servers.

Claims

1. A computer-implemented method for routing a request from a client server to a host server, comprising:

receiving, by the client server, data identifying a plurality of host servers of a service available to process one or more types of service requests;

receiving, by the client server, feedback information comprising data reflecting a load of at least one of the plurality of host servers;

assigning weights to the plurality of host servers, wherein at least a weight of the at least one of the plurality of host servers is determined from a product of a prior weight of the at least one of the plurality of host servers and an average load of the plurality of host servers, the product being divided by a prior load of the at least one of the plurality of host servers;

generating, by the client server, a request to the service;

selecting, by the client server, one of the plurality of host servers of the service to process the request, based on the weights assigned to the plurality of host servers; and

transmitting, by the client server, the request to the selected one of the plurality of host servers.

2. The computer-implemented method of claim 1, wherein the data identifying the plurality of host servers comprises a plurality of addresses of the plurality of host servers.

3. The computer-implemented method of claim 1, wherein the request is a request for a service.

4. The computer-implemented method of claim 1, wherein selecting one of the plurality of host servers comprises using the weight of the at least one of the plurality of host servers in a weighted random selection.

5. The computer-implemented method of claim 1, wherein the load comprises a total number of outstanding requests for the at least one of the plurality of host servers.

6. The computer-implemented method of claim 1, wherein the load comprises a number of outstanding requests of the client server for the at least one of the plurality of host servers.

7. The computer-implemented method of claim 1, wherein the load comprises a processor utilization rate of the at least one of the plurality of host servers.

8. The computer-implemented method of claim 1, wherein the load comprises a memory utilization rate of the at least one of the plurality of host servers.

9. The computer-implemented method of claim 1, further comprising transmitting, by the selected one of the plurality of host servers, a response to the client server, the response comprising data reflecting the load of the selected one of the plurality of host servers.

10. The computer-implemented method of claim 1, further comprising receiving, by the client server, a response from the selected one of the host servers, the response comprising data reflecting the load of the selected one of plurality of the host servers.

11. The computer-implemented method of claim 1, further comprising:

determining whether the selected host server has a sufficient capacity to handle the request, wherein the determination is made based on whether a queue depth of memory of the selected host server has reached a predetermined threshold;

responsive to determining that the selected host server has sufficient capacity to handle the request, processing the request;

responsive to determining that the selected host server does not have sufficient capacity to handle the request, determining, by the selected host server, whether the request was rejected by a prior host server;

responsive to determining that the request was not rejected by the prior host server, transmitting a response declining to process the request;

responsive to determining that the request was rejected by the prior host server, determining a threshold associated with the queue depth of the prior host server; and

responsive to the predetermined threshold associated with the queue depth of the host server being lower than the threshold associated with the queue depth of the prior host server, increasing the predetermined threshold and processing the request.

12. A computer-implemented method for routing a request, comprising:

receiving, by a host server, the request from a client server;

determining whether the host server has a sufficient capacity to handle the request, wherein the determination is made based on whether a queue depth of memory of the host server has reached a predetermined threshold;

responsive to determining that the host server has sufficient capacity to handle the request, processing the request;

responsive to determining that the host server does not have sufficient capacity to handle the request, determining, by the host server, whether the request was rejected by a prior host server;

responsive to determining that the request was not rejected by a prior host server, transmitting a response declining to process the request;

responsive to determining that the request was rejected by a prior host server, determining a threshold associated with the queue depth of the prior host server;

responsive to the predetermined threshold associated with the queue depth of the host server exceeding the threshold associated with the queue depth of the prior host server, processing the request; and

responsive to the predetermined threshold associated with the queue depth of the host server being lower than the threshold associated with the queue depth of the prior host server, increasing the predetermined threshold and processing the request.

13. The computer-implemented method of claim 12, further comprising receiving, by the client server, data identifying a plurality of host servers as a plurality of members of a membership set, the membership set being available to process requests of the client server and including the host server.

14. The computer-implemented method of claim 13, further comprising removing, by the client server, at least one of the plurality of host servers as a member of a membership set, the membership set being available to process requests of the client server.

15. The computer-implemented method of claim 14, wherein the at least one of the plurality of host servers was removed due to a failure.

16. The computer-implemented method of claim 12, further comprising assigning a weight to the host server.

17. The computer-implemented method of claim 16, further comprising selecting the host server from a plurality of host servers to process the request using the weight of the host server in a weighted random selection.

18. The computer-implemented method of claim 12, further comprising sending feedback information to the client server in responding to the client server, wherein the feedback information comprises data reflecting a load of the host server.

19. The computer-implemented method of claim 18, wherein the load comprises a total number of outstanding requests for the host server.

20. The computer-implemented method of claim 18, wherein the load comprises a number of outstanding requests of the client server for the host server.

21. The computer-implemented method of claim 18, wherein the load comprises a processor utilization rate of the host server.

22. The computer-implemented method of claim 18, wherein the load comprises a memory utilization rate of the host server.

23. The computer-implemented method of claim 12, further comprising invoking, by the client server, a discovery service to discover one or more additional host servers that are available to process requests of the client server.

24. The computer-implemented method of claim 23, wherein the discovery service accesses a data record of a registry server to discover the one or more additional host servers.

25. A system for request routing, comprising:

a registry server, the registry server comprising a data store, the data store including data identifying a plurality of host servers that are available to process one or more types of requests;

a client server comprising a processor and a memory, the client server operable to;

receive a request;

select one of a plurality of host servers to process the request;

based on an evaluation; and

transmit the request to the selected one of the plurality of host servers; and

the selected one of the plurality of host servers comprising a processor and a memory, the selected host server operable to;

receive the request;

determine whether the selected host server has a sufficient capacity to handle the request, wherein the determination is made based on whether a queue depth of memory of the selected host server has reached a predetermined threshold;

responsive to determining that the selected host server has sufficient capacity to handle the request, process the request;

responsive to determining that the selected host server does not have sufficient capacity to handle the request, determine whether the request was rejected by a prior host server;

responsive to determining that the request was rejected by the prior host server, determine a threshold associated with the queue depth of the prior host server;

responsive to the predetermined threshold associated with the queue depth of the selected host server exceeding the threshold associated with the queue depth of the prior host server, process the request; and

responsive to the predetermined threshold associated with the queue depth of the selected host server being lower than the threshold associated with the queue depth of the prior host server, increase the predetermined threshold and process the request.

26. The system of claim 25, wherein the client server assigns a weight to at least one of the plurality of host servers.

27. The system of claim 26, wherein selecting one of the plurality of host servers comprises using the weight in a weighted random selection.

28. The system of claim 25, wherein the selected host server is configured to send feedback information to the client server in responding to the client server, wherein the feedback information comprises data reflecting a load of the selected host server.

29. The system of claim 28, wherein the load comprises a total number of outstanding requests for the selected host server.

30. The system of claim 28, wherein the load comprises a number of outstanding requests of the client server for the selected host server.

31. The system of claim 28, wherein the load comprises a processor utilization rate of the selected host server.

32. The system of claim 28, wherein the load comprises a memory utilization rate of the selected host server.