System and method for routing service requests

• US 7,519,734 B1
• Filed: 03/14/2006
• Issued: 04/14/2009
• 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: Sivasubramanian, Swaminathan, Dumitriu, Dan Mihai
• Primary Examiner(s): Maung; Zarni
• Application Number:
  US11/375,652
• Time in Patent Office: 1,127 Days
• Field of Search: 709238-240, 709/250, 709/229, 709/227, 718/105
• US Class Current: 709/238
• 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

A computer-implemented method routes service requests to services in a service framework provided by a plurality of hosts. The method comprises receiving a service request for a service in the service framework and discovering a plurality of candidate hosts that host the service. The plurality of candidate hosts are a subset of the plurality of hosts. The method further comprises selecting a candidate host from the plurality of candidate hosts based on measured latencies for the plurality of candidate hosts and routing the service request to the selected candidate host.

Claims

1. A computer-implemented method of routing service requests to services in a service framework provided by a plurality of hosts, comprising:

receiving a service request for a service in the service framework;

discovering a plurality of candidate hosts that host the service, the plurality of candidate hosts being a subset of the plurality of hosts;

acquiring information about measured latencies for each of the plurality of candidate hosts;

assigning weightings for the plurality of candidate hosts based on the measured latencies for each of the plurality of candidate hosts;

pseudo-randomly selecting a candidate host from the plurality of candidate hosts based on the measured latencies for the plurality of candidate hosts in accordance with the weightings for the plurality of candidate hosts; and

routing the service request to the selected candidate host.

2. A method as defined in claim 1, wherein discovering a plurality of candidate hosts comprises accessing information about a hierarchy, the plurality of candidate hosts being logically defined as having locations within the hierarchy.

3. A method as defined in claim 1, wherein the assigned weightings are based on a network latency for each of the plurality of candidate hosts, and wherein the network latency is reflected in the measured latencies for each of the plurality of candidate hosts.

4. A method as defined in claim 1, wherein the assigned weightings are based on a service latency for each of the plurality of candidate hosts, the service latency including reflecting time required to process a service request and queuing latency, and wherein the service latency is reflected in the measured latencies for each of the plurality of candidate hosts.

5. A method as defined in claim 1 wherein, based on the assigned weightings, the pseudo-random selection takes into account a physical topology of the plurality of candidate hosts.

6. A method as defined in claim 1 wherein, based on the assigned weightings, the pseudo-random selection takes into account heterogeneity in the plurality of candidate hosts.

7. A method as defined in claim 1 wherein, based on the assigned weightings, the pseudo-random selection takes into account heterogeneity in the network capacities of different networks that connect the plurality of candidate hosts.

8. A method as defined in claim 1, wherein the service framework is hierarchically organized into a hierarchy comprising (i) a first level including a plurality of leaf nodes, each of the leaf nodes corresponding to one of the plurality of hosts, and (ii) a second level including a first plurality of zones which each comprise a subset of the plurality of leaf nodes.

9. A method as defined in claim 8, wherein the hierarchy further comprises (iii) a third level including a second plurality of zones which each comprise a subset of the first plurality of zones, and (iv) a fourth level including a root node which comprises the leaf nodes, the first plurality of zones, and the second plurality of zones.

10. A method as defined in claim 8, wherein discovering a plurality of candidate hosts comprises maintaining a direct-dispatch list, and wherein selecting one of the plurality of candidate hosts comprises selecting a host identified in the direct dispatch list.

11. A method as defined in claim 1, wherein routing the service request further comprises determining whether to respond to the service request locally or whether to forward the service request to another host.

12. A computer-implemented method of routing service requests to services in a service framework comprising a plurality of service hosts, the method comprising:

storing a model of the service framework organized in a hierarchy comprising;

a first level including a plurality of leaf nodes, each of the leaf nodes corresponding to one of the plurality of service hosts, and

a second level including a first plurality of zones, wherein each of the first plurality of zones comprise a subset of the plurality of leaf nodes, and wherein each of the first plurality of zones includes a proxy host of the plurality of leaf nodes; and

receiving service requests and, for each service request;

discovering a plurality of candidate hosts from the leaf nodes and proxy hosts that host the service;

pseudo-randomly selecting one of the plurality of candidate hosts based on measured latencies for the plurality of candidate hosts; and

routing the service request to the selected candidate host.

13. A method as defined in claim 12, wherein the hierarchy further comprises a third level including a second plurality of zones which each comprise a subset of the first plurality of zones, and a fourth level including a root node which comprises the leaf nodes, the first plurality of zones, and the second plurality of zones.

14. A method as defined in claim 12, further comprising acquiring information about the measured latencies for each of the plurality of hosts, the information being acquired in responses to service requests.

15. A method as defined in claim 12, wherein the measured latencies reflect network latencies for the plurality of hosts.

16. A method as defined in claim 12, wherein the measured latencies reflect service latencies for the plurality of hosts.

17. A method as defined in claim 12, wherein pseudo-randomly selecting one of the plurality of candidate hosts further comprises

acquiring information about the measured latencies for each of the plurality of candidate hosts;

assigning weightings for the plurality of candidate hosts based on the measured latencies for each of the plurality of candidate hosts;

pseudo-randomly selecting the selected candidate host in accordance with the weightings for the plurality of candidate hosts.

18. A system comprising:

a plurality of host computers in a service framework for responding to service requests, wherein the plurality of hosts computers in the service framework are organized in a hierarchy comprising;

a first level including a plurality of leaf nodes, each of the leaf nodes corresponding to one of the plurality of hosts; and

a second level including a first plurality of zones which each comprise a subset of the plurality of leaf nodes;

a plurality of services executing on the plurality of host computers;

routing logic executing on the plurality of host computers, wherein the routing logic is configured to;

determine whether a service request can be processed locally on the host computer upon which the routing logic is executing;

process the service request locally on the host computer upon which the routing logic is executing if the service request can be processed locally; and

dispatch service requests based on measured latencies between different levels in the hierarchy tree structure.

19. A system as defined in claim 18, wherein the hierarchy further comprises a third level including a second plurality of zones which each comprise a subset of the first plurality of zones, and a fourth level including a root node which comprises the leaf nodes, the first plurality of zones, and the second plurality of zones.

20. A system as defined in claim 18, wherein the plurality of hosts are heterogeneous and have different processing capacities, and wherein the routing logic is configured account for the heterogeneity of the plurality of hosts when making routing decisions.

21. A system as defined in claim 18, wherein the routing logic is configured to acquire information about the measured latencies for each of the plurality of hosts, assign weightings for the plurality of hosts based on the measured latencies for each of the plurality of hosts, and pseudo-randomly select a destination host for dispatching a service request in accordance with the weightings for the plurality of hosts.

22. A system as defined in claim 21, wherein the assigned weightings are based on a network latency for each of the plurality of hosts, and wherein the network latency is reflected in the measured latencies for each of the plurality of hosts.

23. A system as defined in claim 21, wherein the assigned weightings are based on a service latency for each of the plurality of hosts, the service latency including reflecting time required to process a service request and queuing latency, and wherein the service latency is reflected in the measured latencies for each of the plurality of hosts.

24. A system as defined in claim 18, wherein the plurality of hosts are heterogeneous and have different processing capacities, and wherein the routing logic is configured account for the heterogeneity of the plurality of hosts when making routing decisions.

25. A tangible computer-accessible medium bearing computer-executable instructions which, when executed on a host computer in a computing system implementing a service framework comprising a plurality of host computers organized in a hierarchy for responding to service requests, direct the computing system to:

receive a service request for a service;

discover a set of candidate host computers that host the service, the set of candidate host computers being a subset of the plurality of host computers;

pseudo-randomly select a candidate host computer from the set of candidate host computers, the selection of the candidate host computer comprising a selection of a dispatch level within the hierarchy; and

route the service request to the selected candidate host computer.

26. A computer accessible medium as defined in claim 25, wherein the plurality of candidate host computers is discovered by accessing information about the hierarchy, the candidate host computers being logically defined as having locations within the hierarchy.

27. A computer accessible medium as defined in claim 25 wherein, to pseudo-random select the selected candidate host computer, the contents direct the computing system to:

acquire information about the measured latencies for each of the plurality of candidate host computers;

assign weightings for the plurality of candidate host computers based on the measured latencies for each of the plurality of candidate host computers; and

pseudo-randomly select the candidate host computer in accordance with the weightings for the plurality of candidate host computers.

28. A computer accessible medium as defined in claim 27, wherein the assigned weightings are based on a network latency for each of the plurality of candidate host computers, and wherein the network latency is reflected in the measured latencies for each of the plurality of candidate host computers.

29. A computer accessible medium as defined in claim 27, wherein the assigned weightings are based on a service latency for each of the plurality of candidate host computers, the service latency including reflecting time required to process a service request and queuing latency, and wherein the service latency is reflected in the measured latencies for each of the plurality of candidate host computers.

30. A computer accessible medium as defined in claim 27 wherein, based on the assigned weightings, the pseudo-random selection takes into account a physical topology of the plurality of candidate host computers.

31. A computer accessible medium as defined in claim 27 wherein, based on the assigned weightings, the pseudo-random selection takes into account heterogeneity in the plurality of candidate host computers.

32. A computer accessible medium as defined in claim 27 wherein, based on the assigned weightings, the pseudo-random selection takes into account heterogeneity in the network capacities of different networks that connect the plurality of candidate host computers.

33. A computer accessible medium as defined in claim 25, wherein the service framework is organized in a hierarchy which comprises a first level including a plurality of leaf nodes, each of the leaf nodes corresponding to one of the plurality of host computers, and a second level including a first plurality of zones which each comprise a subset of the plurality of leaf nodes.

34. A computer accessible medium as defined in claim 33, wherein the hierarchy further comprises a third level including a second plurality of zones which each comprise a subset of the first plurality of zones, and a fourth level including a root node which comprises the leaf nodes, the first plurality of zones, and the second plurality of zones.

35. A computer accessible medium as defined in claim 33 wherein, to discover a plurality of candidate host computers, the contents direct the computing system to maintain a direct-dispatch list, and wherein selecting one of the plurality of candidate host computers comprises selecting a host computer identified in the direct dispatch list.

36. A computer accessible medium as defined in claim 25 wherein, to route the service request, the contents direct the computing system to determine whether to respond to the service request locally or whether to forward the service request to another host computer.

37. A computer accessible medium as defined in claim 25 wherein, to route the service request, the contents direct the computing system to determine whether to respond to the service request locally or whether to forward the service request to another host computer.