Decentralized request routing

• US 9,628,556 B2
• Filed: 09/19/2014
• Issued: 04/18/2017
• 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., Kommareddy, Christopher, Chatterjee, Preetha, Zhong, Nan, Sundt, Mitchell, Rai, Vivek
• Primary Examiner(s): Moise, Emmanuel L
• Assistant Examiner(s): Chang, Julian
• Application Number:
  US14/491,322
• Publication Number:
  US 20150006630A1
• Time in Patent Office: 942 Days
• 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 method for routing a service request from a client server to a host server, the method comprising:

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

providing, by the client server, data identifying a membership set having a number of the plurality of host servers in the membership set;

receiving, by the client server from one or more of the plurality of host servers, performance feedback information comprising data representing a current load of at least one of the plurality of host servers in the membership set upon responding to a previous service request;

identifying, by the client server, a first host server in the membership set that is not performing according to a performance level based in part on the received performance feedback information;

adding, by the client server, a second host server to the membership set, wherein the second host server is a potential replacement for the first host server within the membership set;

removing, by the client server, the first host server from the membership set at least based in part on the received performance feedback information indicating that the second host server is shown to perform above a standard level, wherein the second host server remains a member of the membership set thereby replacing the first host server; and

transmitting, by the client server, a new service request to one of the plurality of host servers in the membership set.

2. The 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 method of claim 1, further comprising receiving, by the client server, a response from the one of the plurality of host servers in the membership set, the response comprising data representing an updated current load of the one of the plurality of host servers in the membership set.

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

receiving data identifying a plurality of host servers of a service available to process one or more types of service requests;

providing data identifying a membership set having a number of the plurality of host servers in the membership set;

receiving performance feedback information comprising data representing an operational status of at least one of the plurality of host servers in the membership set upon responding to a previous service request;

identifying a first host server in the membership set that is not performing according to a standard level based in part on the received performance feedback information;

adding a second host server to the membership set, wherein the second host server is a potential replacement for the first host server within the membership set;

removing the first host server from the membership set at least based in part on the received performance feedback information indicating that the second host server is shown to perform above the standard level, wherein the second host server remains a member of the membership set thereby replacing the first host server; and

transmitting a new service request to one of the plurality of host servers in the membership set.

5. The computer-implemented method of claim 4, further comprising removing a host server from the membership set that is no longer available.

6. The computer-implemented method of claim 4, wherein the standard level comprises a maximum average wait time for processing requests.

7. The computer-implemented method of claim 5, further comprising adding a new host server to the membership set to replace the removed host server that is no longer available.

8. The computer-implemented method of claim 4, wherein the operational status comprises a total number of outstanding requests for the one of the plurality of host servers.

9. The computer-implemented method of claim 4, wherein the operational status comprises a number of outstanding requests for the one of the plurality of host servers.

10. The computer-implemented method of claim 4, wherein the operational status comprises a processor utilization rate of the one of the plurality of host servers.

11. The computer-implemented method of claim 4, wherein the operational status comprises a memory utilization rate of the one of the host servers.

12. The computer-implemented method of claim 4, further comprising invoking a discovery service to discover one or more additional host servers not currently contained in the membership set and that are available to process requests of a client server.

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

14. 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 service requests;

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

receive, from the registry server, the data identifying the plurality of host servers that are available to process one or more types of service requests;

receive, from one or more of the plurality of host servers, performance feedback information comprising data representing an operational status of at least one of the plurality of host servers, wherein the performance feedback information is provided as part of a response to a previous service request;

identify a first host server in a membership set of the plurality of host servers that is not performing according to performance level based in part on the received performance feedback information;

add a second host server to the membership set, wherein the second host server is a potential replacement for the first host server within the membership set;

remove the first host server from the membership set at least based in part on the received performance feedback information indicating that the second host server is shown to perform above a standard level, wherein the second host server remains a member of the membership set thereby replacing the first host server; and

transmit a new service request to one of the plurality of host servers in the membership set.

15. The system of claim 14, wherein the one of the plurality of host servers in the membership set is configured to send new performance feedback information to the client server in responding to the new service request from the client server, wherein the new performance feedback information comprises data representing a load of the one of the plurality of host servers in the membership set.

16. The system of claim 14, wherein the operational status comprises a total number of outstanding requests for the at least one of the plurality of host servers.

17. The system of claim 14, wherein the operational status comprises a number of outstanding requests of the client server for the at least one of the plurality of host servers.

18. The system of claim 14, wherein the operational status comprises a processor utilization rate of the at least one of the plurality of host servers.

19. The system of claim 14, wherein the operational status comprises a memory utilization rate of the at least one of the plurality of host servers.

20. The system of claim 14, wherein the client server is further operable to receive a response from the one of the plurality of host servers, the response comprising data representing an updated current load of the one of the plurality of host servers, wherein the client server utilizes the updated current load to process a subsequent service request.