Resource resolution in computing environments using directed graphs

• US 8,595,262 B1
• Filed: 03/29/2012
• Issued: 11/26/2013
• Est. Priority Date: 03/29/2012
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Hayden, Andrew
• Primary Examiner(s): Fleurantin, Jean B
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US13/434,104
• Time in Patent Office: 607 Days
• Field of Search: 707/768, 707/798, 707/E17.011, 707/999.005, 709/224, 709/225, 370/252, 370/254, 719/314
• US Class Current: 707/798
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Methods and apparatus for resource resolution in computing environments using directed graphs are disclosed. A system includes a resource resolver and data sources that comprise records on resource classes of a provider network. The resolver receives a request to identify a set of resources of the provider network based on specified criteria. The resolver utilizes a directed graph representation of the data sources to identify query sequences to be directed to the data sources in response to the request. Each node of the graph represents a data source, and each edge represents a logical relationship between the data sources represented by the nodes connected by the edge. Each edge has a weight based on a performance metric obtained from a data source whose node is connected by the edge. The resolver issues queries of a preferred query sequence, identified using edge weights, to respective data sources.

Claims

1. A system, comprising a plurality of computing devices configured to implement:

a plurality of resources of a provider network;

a plurality of data sources, wherein each data source of the plurality of data sources comprises records on a respective resource class of a plurality of resource classes, wherein each resource of the plurality of resources belongs to one or more resource classes of the plurality of resource classes; and

a resource resolver;

wherein the resource resolver is operable to;

receive a request to identify a set of resources of the plurality of resources based on one or more criteria specified in the request;

utilize a directed graph representation of at least a subset of the plurality of data sources to identify one or more query sequences to respond to the request, wherein the directed graph comprises a plurality of nodes and a plurality of edges, and wherein;

each node of the directed graph represents a data source of the plurality of data sources, and each edge of the directed graph represents a logical relationship between the data sources whose nodes are connected by the edge;

each edge of a set of edges of the directed graph has an associated weight based at least in part on a performance metric obtained from one of the two data sources whose nodes are connected by the edge; and

each query sequence of the one or more query sequences comprises a plurality of queries, wherein each query of the plurality of queries is to be directed to a respective data source of the plurality of data sources; and

issue one or more queries of a preferred query sequence identified from the one or more query sequences, wherein the one or more queries are issued to respective data sources of the plurality of data sources.

2. The system as recited in claim 1, wherein a particular query sequence of the one or more query sequences comprises a first query followed by a second query, wherein at least a portion of a output data set of the first query forms at least a portion of an input data set for the second query.

3. The system as recited in claim 1, wherein the one or more query sequences comprise a plurality of query sequences, wherein the resource resolver is operable to:

assign a projected performance ranking to each query sequence of the plurality of query sequences based at least in part on one or more weights associated with edges of nodes representing the data sources to be queried in the query sequence, wherein the preferred query sequence has the highest ranking of the plurality of query sequences, and

in response to determining that a query of the preferred query sequence has failed, issue one or more queries of an alternate query sequence of the plurality of query sequences, wherein the alternate query sequence has a lower ranking than the preferred query sequence.

4. The system as recited in claim 1, wherein the performance metric comprises a query response time metric, and wherein the resource resolver is further operable to:

modify the weight of an edge of the directed graph based on a measurement of a response time of a query executed in response to the request.

5. The system as recited in claim 1, wherein the resource resolver is further operable to:

implement an interface allowing a specification of the one or more criteria of the request in a syntax based at least in part on the Structured Query Language (SQL).

6. The system as recited in claim 1, wherein a particular data source of the plurality of data sources implements a nearest-neighbors application programming interface (API), wherein, in accordance with the nearest-neighbors API, the particular data source is configured to:

respond to queries on a subset of resource classes of the plurality of resource classes comprising (a) the resource class whose records are maintained in the particular data source and (b) the resource classes of those data sources whose nodes are nearest neighbors of the node representing the particular data source in the directed graph; and

ignore or reject queries on resource classes that do not belong to the subset of resource classes; and

wherein at least one query of the preferred query sequence is formatted in accordance with the nearest-neighbors API.

7. A method, comprising:

maintaining resource records at a plurality of data sources, wherein each data source of the plurality of data sources comprises records on a respective resource class of a plurality of resource classes, wherein each resource of a plurality of resources of a provider network belongs to one or more resource classes of the plurality of resource classes;

receiving a request to identify a set of resources of the plurality of resources based on one or more criteria specified in the request;

utilizing a directed graph representation of at least a subset of the plurality of data sources to identify one or more query sequences to respond to the request, wherein;

each node of the directed graph represents a data source of the plurality of data sources, and each edge of the directed graph represents a logical relationship between the data sources whose nodes are connected by the edge;

each edge of at least a subset of the edges of the directed graph has an associated weight based at least in part on a performance metric obtained from one of the two data sources whose nodes are connected by the edge; and

each query sequence of the one or more query sequences comprises a plurality of queries, wherein each query of the plurality of queries is to be directed to a respective data source of the plurality of data sources.

8. The method as recited in claim 7, further comprising:

issuing one or more queries of a preferred query sequence of the one or more query sequences to at least one data source of the plurality of data sources.

9. The method as recited in claim 8, wherein the one or more query sequences comprise a plurality of query sequences, further comprising:

assigning a projected performance ranking to each query sequence of the plurality of query sequences based at least in part on one or more weights associated with edges of nodes representing the data sources to be queried in the query sequence; and

identifying the query sequence with the highest ranking among the plurality of query sequences as the preferred query sequence.

10. The method as recited in claim 9, further comprising:

in response to determining that a query of the preferred query sequence has failed, issuing one or more queries of an alternate query sequence of the plurality of query sequences, wherein the alternate query sequence has a lower ranking than the preferred query sequence.

11. The method as recited in claim 7, further comprising:

in response to determining that a particular query of the preferred query sequence has failed, assigning a failure-indicating weight to an edge of the directed graph, wherein the edge is connected to a node representing a data source to which the particular query was directed.

12. The method as recited in claim 7, further comprising:

storing the directed graph representation in a persistent store; and

retrieving the directed graph representation from the persistent store to respond to an additional request.

13. The method as recited in claim 7, wherein a direction of an edge of the directed graph indicates a containment relationship between the resource classes corresponding to the data sources represented by the nodes connected via the edge.

14. The method as recited in claim 7, further comprising:

modifying the weight of an edge of the directed graph based at least in part on a measurement of a response time of a query executed in response to the request.

15. The method as recited in claim 7, further comprising:

executing a set of queries of a graph update test suite scheduled in accordance with a graph refresh policy; and

updating the weights of one or more edges of the directed graph based at least in part on one or more results of the graph update test suite.

16. The method as recited in claim 7, further comprising:

implementing an interface allowing a specification of the one or more criteria of the request in a syntax based at least in part on the Structured Query Language (SQL).

17. The method as recited in claim 7, wherein a particular data source of the plurality of data sources implements a nearest-neighbors application programming interface (API), wherein, in accordance with the nearest-neighbors API, the particular data source is configured to:

respond to queries directed to a subset of resource classes comprising (a) the resource class whose records are maintained at the particular data source and (b) the resource classes of those data sources whose nodes are nearest neighbors of the node representing the particular data source in the directed graph; and

reject queries directed to resource classes that do not belong to the subset of resource classes;

and wherein at least one query of the preferred query sequence is formatted in accordance with the nearest-neighbors API.

18. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

receive a request to identify a set of resources of a plurality of resources of a provider network based on one or more criteria specified in the request; and

utilize a directed graph representation of at least a subset of a plurality of data sources to identify one or more query sequences to respond to the request, wherein each data source of the plurality of data sources comprises records on a respective resource class of a plurality of resource classes, wherein each resource of the plurality of resources of the provider network belongs to one or more resource classes of the plurality of resource classes, and wherein;

each node of the directed graph represents a data source of the plurality of data sources, and each edge of the directed graph represents a logical relationship between the data sources whose nodes are connected by the edge;

each edge of at least a subset of the edges of the directed graph has an associated weight based at least in part on a performance metric obtained from one of the two data sources whose nodes are connected by the edge; and

each query sequence of the one or more query sequences comprises a plurality of queries, wherein each query of the plurality of queries is to be directed to a respective data source of the plurality of data sources.

19. The storage medium as recited in claim 18, wherein the instructions when executed on the one or more processors:

issue one or more queries of a preferred query sequence of the one or more query sequences to at least one data source of the plurality of data sources.

20. The storage medium as recited in claim 19, wherein the one or more query sequences comprise a plurality of query sequences, wherein the instructions when executed on the one or more processors:

assign a projected performance ranking to each query sequence of the plurality of query sequences based at least in part on one or more weights associated with edges of nodes representing the data sources to be queried in the query sequence; and

identify the query sequence with the highest ranking among the plurality of query sequences as the preferred query sequence.

21. The storage medium as recited in claim 20, wherein the instructions when executed on the one or more processors:

in response to determining that a query of the preferred query sequence has failed, issue one or more queries of an alternate query sequence of the plurality of query sequences, wherein the alternate query sequence has a lower ranking than the preferred query sequence.

22. The storage medium as recited in claim 18, wherein the instructions when executed on the one or more processors:

modify the weight of an edge of the directed graph based at least in part on a measurement of an error rate of a set of queries issued to a particular data source of the plurality of data sources, wherein the edge is connected to a node representing the particular data source.

23. The storage medium as recited in claim 18, wherein the instructions when executed on the one or more processors:

implement an interface allowing a specification of the one or more criteria of the request in a syntax based at least in part on the Structured Query Language (SQL).

24. The storage medium as recited in claim 18, wherein at least one query of a particular query sequence of the one or more query sequences is formatted in accordance with a nearest-neighbors API implemented by a particular data source of the plurality of data sources, wherein, in accordance with the nearest-neighbors API, the particular data source is configured to:

respond to queries directed to a subset of resource classes comprising (a) the resource class whose records are maintained at the particular data source and (b) the resource classes of those data sources whose nodes are nearest neighbors of the node representing the particular data source in the directed graph; and

reject queries directed to resource classes that do not belong to the subset of resource classes.

25. The storage medium as recited in claim 24, wherein in accordance with the nearest-neighbors API, the particular data source is configured to:

in response to a request to indicate resource classes for which the particular data source is configured to respond to queries, provide an enumeration of the resource classes of the subset of resource classes.

26. The storage medium as recited in claim 18, wherein the plurality of resource classes comprises at least one of:

a compute instance class, a storage instance class, an availability zone class, a provider network region class, an auto-scaling group class, a load balancer class, a distributed computing cluster class, a virtual private cloud class, or a security group class.

27. The storage medium as recited in claim 18, wherein a resource record for a compute instance class of the plurality of resource classes comprises at least one of:

(a) an identifier of a machine image installed on a compute instance, (b) a host identifier for a compute instance, (c) an Internet Protocol (IP) address being used as a public IP address of a compute instance, (d) an IP address being used as a private IP address of a compute instance, (e) a hypervisor identifier of a compute instance, (f) an operating system identifier of a compute instance, or (g) a performance rating of a compute instance.

28. The storage medium as recited in claim 18, wherein the instructions when executed on the one or more processors:

determine a lowest-cost path between two nodes of the directed graph to identify a particular query sequence of the one or more query sequences, wherein the lowest-cost path is determined based at least in part on respective weights of one or more edges connected the two nodes.