System and method for routing service requests

• US 8,396,957 B2
• Filed: 10/07/2011
• Issued: 03/12/2013
• Est. Priority Date: 03/14/2006
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dumitriu, Dan Mihai, Sivasubramanian, Swaminathan
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US13/269,479
• Publication Number:
  US 20120030339A1
• Time in Patent Office: 522 Days
• Field of Search: 709223-229, 709/250, 709/232
• US Class Current: 709/223
• CPC Class Codes: H04L 1/0018 based on latency requirement
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Service requests may be routed to services in a service framework provided by a plurality of hosts. A candidate host zone including a plurality of service hosts may be selected to service the request. The candidate host zone may be selected based at least in part on an aggregation of service latencies associated with the service hosts associated with the candidate host zone. A service host belonging to the selected candidate host zone may be selected to service the request.

Claims

1. A computer-implemented method of routing service requests, comprising:

receiving, by a first candidate host, a service request;

discovering a plurality of candidate host zones for servicing the service request, wherein each candidate host zone of the plurality of candidate host zones comprises a plurality of service hosts for servicing the service request;

determining a service latency associated with each of the plurality of candidate host zones, wherein the service latency associated with each of the plurality of candidate host zones is based on an aggregation of service latencies associated with the plurality of service hosts comprising the respective candidate host zone;

selecting a candidate host zone for servicing the service request based on the service latency associated with each of the plurality of candidate host zones; and

selecting a service host from the respective plurality of service hosts associated with the selected candidate host zone to service the service request.

2. The computer-implemented method of claim 1, wherein discovering the plurality of candidate host zones comprises accessing information about a hierarchy of host zones, the plurality of candidate host zones being logically defined as having locations within the hierarchy of host zones.

3. The computer-implemented method of claim 2, wherein the hierarchy of host zones comprises:

a first level comprising a plurality of leaf nodes, each of the leaf nodes corresponding to a candidate host zone; and

a second level comprising a first plurality of candidate host zones, which each comprise a subset of the plurality of leaf nodes.

4. The computer-implemented method of claim 3, wherein the hierarchy of host zones further comprises:

a third level including a second plurality of candidate host zones which each comprise a subset of the first plurality of candidate host zones; and

a fourth level including a root node which comprises the leaf nodes, the first plurality of candidate host zones, and the second plurality of candidate host zones.

5. The computer-implemented method of claim 1, wherein selecting the candidate host zone for servicing the service request based on the service latency associated with each of the plurality of candidate host zones comprises:

assigning a selection probability to each of the plurality of candidate host zones, wherein the selection probability for each candidate host zone is based at least in part on the service latency for the candidate host zone; and

selecting the candidate host zone for servicing the service request based at least in part on the selection probability assigned to each of the plurality of candidate host zones.

6. The computer-implemented method of claim 5, wherein the selection probability for each of the plurality of candidate host zones is inversely proportional to the candidate host zone'"'"'s service latency.

7. The computer-implemented method of claim 1 further comprising routing a service response from the selected service host to a computing device from which the first candidate host received the service request.

8. A system for request routing, the system comprising:

a first candidate host configured to;

receive a service request;

discover a plurality of candidate host zones for servicing the service request, wherein each candidate host zone comprises a plurality of service hosts for servicing the service request; and

determine a service latency associated with each of the plurality of candidate host zones, wherein the service latency associated with each of the plurality of candidate host zones is based on an aggregation of service latencies associated with the plurality of service hosts belonging to the respective candidate host zone; and

a request router in communication with the first candidate host and with the plurality of candidate host zones, the request router configured to;

select, based at least in part on the service latency associated with each of the plurality of candidate host zones, a candidate host zone for servicing the service request; and

select a service host from the plurality of service hosts associated with the selected candidate host zone to service the service request.

9. The system of claim 8, wherein the first candidate host is configured to discover the plurality of candidate host zones by accessing information about a hierarchy of host zones, the plurality of candidate host zones being logically defined as having locations within the hierarchy of host zones.

10. The system of claim 9, wherein the hierarchy of host zones comprises:

a first level comprising a plurality of leaf nodes, each of the leaf nodes corresponding to a candidate host zone; and

a second level comprising a first plurality of candidate host zones, which each comprise a subset of the plurality of leaf nodes.

11. The system of claim 10, wherein the hierarchy of host zones further comprises:

a third level including a second plurality of candidate host zones which each comprise a subset of the first plurality of candidate host zones; and

a fourth level including a root node which comprises the leaf nodes, the first plurality of candidate host zones, and the second plurality of candidate host zones.

12. The system of claim 8, wherein the request router is configured to select the candidate host zone by:

assigning a selection probability to each of the plurality of candidate host zones, wherein the probability for each candidate host zone is based at least in part on the service latency for the candidate host zone; and

selecting the candidate host zone for servicing the service request based at least in part on the selection probability assigned to each of the plurality of candidate host zones.

13. The system of claim 12, wherein the selection probability for each of the plurality of candidate host zones is inversely proportional to the candidate host zone'"'"'s service latency.

14. The system of claim 8, wherein the request router is further configured to route a service response from the selected service host to a computing device from which the service request was received by the first candidate host.

15. A non-transitory computer-readable medium having stored thereon a system configured to execute in one or more processors, the system comprising a request routing module configured to:

receive a service request;

discover a plurality of candidate host zones for servicing the service request, wherein each candidate host zone of the plurality of candidate host zones comprises a plurality of service hosts configured to service the service request;

determine a service latency for each of the plurality of candidate host zones, wherein the service latency for each of the plurality of candidate host zones is based on an aggregation of service latencies associated with the plurality of service hosts comprising the respective candidate host zone;

select a candidate host zone for servicing the service request based on the service latency associated with each of the plurality of candidate host zones; and

select a service host from the respective plurality of service hosts associated with the selected candidate host zone to service the service request.

16. The non-transitory computer-readable medium of claim 15, wherein the request routing module is configured to discover the plurality of candidate host zones by accessing information about a hierarchy of host zones, the plurality of candidate host zones being logically defined as having locations within the hierarchy of host zones.

17. The non-transitory computer-readable medium of claim 15, wherein the selection of the candidate host zone for servicing the service request is further based at least in part on a physical topology of the plurality of candidate host zones.

18. The non-transitory computer-readable medium of claim 15, wherein the selection of the candidate host zone for servicing the service request is further based at least in part on heterogeneity information associated with each of the plurality of candidate host zones.

19. The non-transitory computer-readable medium of claim 15, wherein the request routing component is further configured to select the candidate host zone by:

assigning a selection probability to each of the plurality of candidate host zones, wherein the selection probability for each candidate host zone is based at least in part on the service latency for the candidate host zone; and

selecting the candidate host zone for servicing the service request based at least in part on the selection probability assigned to each of the plurality of candidate host zones.

20. The non-transitory computer-readable medium of claim 15, wherein the request routing component is further configured to route a service response from the selected service host to a computing device from which the service request was received.