Method and apparatus for stress management in a searchable data service

• US 8,775,411 B1
• Filed: 02/28/2013
• Issued: 07/08/2014
• Est. Priority Date: 12/29/2005
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Ransil, Patrick W., Martynov, Aleksey, Larson, James S., Collette, James R., Chu, Robert Wai-Chi, Saha, Partha
• Primary Examiner(s): REYES, MARIELA D
• Application Number:
  US13/780,659
• Time in Patent Office: 495 Days
• Field of Search: 707/716, 707/719, 707/720
• US Class Current: 707/716
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Method and apparatus for stress management in a searchable data service. The searchable data service may provide a searchable index to a backend data store, and an interface to build and query the searchable index, that enables client applications to search for and retrieve locators for stored entities in the backend data store. Embodiments of the searchable data service may implement a distributed stress management mechanism that may provide functionality including, but not limited to, the automated monitoring of critical resources, analysis of resource usage, and decisions on and performance of actions to keep resource usage within comfort zones. In one embodiment, in response to usage of a particular resource being detected as out of the comfort zone on a node, an action may be performed to transfer at least part of the resource usage for the local resource to another node that provides a similar resource.

Claims

1. A searchable data service system, comprising:

a plurality of nodes configured to process query requests from a client application to locate searchable data service objects in a searchable index that satisfy the query requests, wherein each searchable data service object specifies two or more attributes of a particular entity in a data store, and wherein the attributes include a unique entity identifier for locating the particular entity in the data store;

a node group comprising two or more of the plurality of nodes, wherein each node in the node group is configured to;

monitor one or more usage metrics for each of one or more local resources of the node; and

if a monitored usage metric for one of the local resources of the node crosses a boundary of a specified comfort zone for the usage metric, communicate with at least one other node in the node group to transfer at least part of the resource usage for the local resource on the node to another one of the nodes in the node group that includes a similar resource;

wherein said transferring at least part of the resource usage for the local resource on the node to another one of the nodes in the node group moves the monitored usage metric for the local resource into the specified comfort zone for the usage metric on the node.

2. The system as recited in claim 1, wherein each attribute is expressed as a {name, value} pair.

3. The system as recited in claim 1, wherein, to communicate with at least one other node in the node group to transfer at least part of the resource usage for the local resource on the node to another one of the nodes in the node group that includes a similar resource, the nodes in the node group are configured to communicate in accordance with a gossip protocol.

4. The system as recited in claim 1, wherein, to communicate with at least one other node in the node group to transfer at least part of the resource usage for the local resource on the node to another one of the nodes in the node group that includes a similar resource, the nodes in the node group are configured to communicate in accordance with an anti-entropy protocol.

5. The system as recited in claim 1, wherein, to communicate with at least one other node in the node group to transfer at least part of the resource usage for the local resource on the node to another one of the nodes in the node group that includes a similar resource, the nodes in the node group are configured to communicate in accordance with a gossip protocol and an anti-entropy protocol.

6. The system as recited in claim 1, wherein the plurality of nodes is configured to organize into one or more node groups each including a subset of the plurality of nodes, wherein each node in a node group is configured to communicate with other nodes in the node group in accordance with a gossip protocol to propagate searchable data service information relevant to the node group.

7. The system as recited in claim 1, wherein monitored usage metrics for local resources on a node include one or more storage space usage metrics for a local storage resource.

8. The system as recited in claim 1, wherein monitored usage metrics for local resources on a node include one or more processor usage metrics for a local processor resource.

9. The system as recited in claim 1, wherein monitored usage metrics for local resources on a node include one or more read load metrics for a local storage resource.

10. The system as recited in claim 1, wherein monitored usage metrics for local resources on a node include one or more write load metrics for a local storage resource.

11. The system as recited in claim 1, wherein each of the plurality of nodes is configured to communicate monitored local resource usage metrics to one or more others of the plurality of nodes.

12. The system as recited in claim 1, wherein the node group is configured to propagate monitored local resource usage metrics for each node in the node group to other nodes in the node group in accordance with a gossip protocol.

13. The system as recited in claim 1, wherein each node in the node group is further configured to receive monitored local resource usage metrics from other nodes in the node group in accordance with a gossip protocol.

14. The system as recited in claim 1, wherein the node group is a storage node group comprising a plurality of storage nodes each configured to:

persistently store at least one partition of the searchable index on a local storage resource;

monitor one or more storage space usage metrics for the local storage resource; and

if a monitored storage space usage metric for the local storage resource crosses a boundary of a specified comfort zone for the storage space usage metric on the storage node, communicate with one or more others of the storage nodes in the storage node group to transfer at least part of the at least one partition of the searchable index to another storage node in the storage node group.

15. The system as recited in claim 1, wherein the node group is a storage node group comprising a plurality of storage nodes each configured to:

persistently store a partition of the searchable index on a local storage resource;

monitor a storage space usage metric for the local storage resource; and

if the monitored storage space usage metric for the local storage resource crosses a boundary of a specified comfort zone for the storage space usage metric on the storage node;

repartition the partition to generate two or more new partitions, wherein each of the two or more new partitions includes a different subset of the searchable data service objects stored in the searchable index;

communicate with one or more others of the storage nodes in the storage node group to locate another storage node in the storage node group that volunteers to receive one of the two or more new partitions; and

communicate with the other storage node to move one of the two or more new partitions to the other storage node.

16. The system as recited in claim 15, wherein each storage node is further configured to communicate with one or more others of the storage nodes in the storage node group to locate another storage node in the storage node group that volunteers to receive one of the two or more new partitions and to communicate with the other storage node to move one of the two or more new partitions to the other storage node in accordance with a gossip protocol and an anti-entropy protocol.

17. The system as recited in claim 1, wherein the plurality of nodes comprises:

a plurality of storage nodes each configured to persistently store at least one partition of the searchable index;

one or more query nodes each configured to;

maintain a local query cache of responses to previous query requests;

access the local query cache on the query node to determine if a query request can be satisfied from the local query cache; and

if the query request cannot be satisfied from the local query cache, forward the query request to an appropriate one or more of the storage nodes;

one or more coordinator nodes each configured to;

receive service requests from the client application, wherein the service requests comprise storage requests and query requests;

forward each storage request to an appropriate one or more of the storage nodes; and

forward each query request to an appropriate one or more of the query nodes.

18. The system as recited in claim 17, wherein each of the one or more storage nodes is configured to:

receive a storage request from a coordinator node; and

modify a partition of the searchable index persistently stored by the storage node as specified in the storage request.

19. The system as recited in claim 17, wherein each of the one or more storage nodes is configured to:

receive a query request from a query node;

search a partition of the searchable index persistently stored by the storage node to locate a set of one or more searchable data service objects in the searchable index that satisfy the query request; and

return at least the entity identifiers from the set of one or more searchable data service objects that satisfy the query request to the client application.

20. The system as recited in claim 17, wherein the plurality of nodes is configured to organize into node groups each including a subset of the plurality of nodes, wherein each node in a node group is configured to communicate with other nodes in the node group in accordance with a gossip protocol and an anti-entropy protocol to propagate searchable data service information within the node group;

wherein the storage nodes are configured to organize into one or more storage node groups;

wherein the query nodes are configured to organize into one or more query node groups; and

wherein the coordinator nodes are configured to organize into one or more coordinator node groups.