Independent evictions from datastore accelerator fleet nodes

Patent metadata

Field	Value
Publication number	US-10482062-B1
Application number	US-201615085967-A
Country	US
Kind code	B1
Filing date	Mar 30, 2016
Priority date	Mar 30, 2016
Publication date	Nov 19, 2019
Grant date	Nov 19, 2019

Abstract

A fleet of query accelerator nodes is established for a data store. Each accelerator node caches data items of the data store locally. In response to determining that an eviction criterion has been met, one accelerator node removes a particular data item from its local cache without notifying any other accelerator node. After the particular data item has been removed, a second accelerator node receives a read query for the particular data item and provides a response using a locally-cached replica of the data item.

First claim

What is claimed is:

1. A system, comprising:
a plurality of query accelerator nodes associated with a first data store of a provider network, including a first query accelerator node implemented at a first computing device, a second query accelerator node implemented at a second computing device, and a third query accelerator node implemented at a third computing device;
wherein the first query accelerator node is configured to:
in response to determining that a first data item requested by a client of the first data store is not present in a first local cache,
store, in the first local cache, contents of the first data item obtained from one or more storage nodes of the first data store; and
initiate a propagation of respective replicas of the first data item to at least the second and third query accelerator nodes;

wherein the second query accelerator node is configured to:
store a first replica of first data item, received from the first query accelerator node, in a second local cache;
in response to determining that the first replica meets a first eviction criterion, remove the first replica from the second local cache without coordinating the removal of the first replica with the first query accelerator node; and
in response to receiving a particular read query for the first data item after removing the first replica, obtain another replica of the first data item from a first source selected according to a first read miss processing rule; and

wherein the third query accelerator node is configured to:
store a second replica of the first data item, received from the first query accelerator node, in a third local cache;
in response to determining that the second replica meets a second eviction criterion, remove the second replica from the third local cache; and
in response to receiving a different read query for the first data item after removing the second replica, obtain an additional replica of the first data item from a different source.

2. The system as recited in claim 1 , wherein the first eviction criterion comprises one or more of: (a) a least-recently-used criterion, (b) a shortest time-to-live criterion, (c) a data item size-based criterion, (d) a criterion based on a property of a client-side component on whose behalf the first replica is stored in the second local cache, or (e) a locality-based criterion.

3. The system as recited in claim 1 , further comprising a control-plane component of a query acceleration service, wherein the one or more storage nodes comprise a first multi-tenant storage node, wherein the first multi-tenant storage node comprises (a) a first set of data items stored on behalf of a first client account and (b) a second set of data items stored on behalf of a second client account, wherein the control-plane component is configured to:
receive, from a client-side component associated with the first client account, a request to instantiate the plurality of query accelerator nodes;
instantiate the plurality of query accelerator nodes in single-tenant mode on behalf of the first client account; and
store metadata indicating that access to the plurality of query accelerator nodes is to be restricted to client-side components associated with the first client account.

4. The system as recited in claim 1 , further comprising a client-side component of the data store, wherein the client-side component is configured to:
determine, based at least in part on one or more of: (a) metadata associated with the plurality of query accelerator nodes or (b) one or more query predicates of the first read query, that a probability of obtaining a response to another read query from the second local cache is greater than a probability of obtaining a response to the other read query from another local cache; and
direct the other read query to the second query accelerator node.

5. The system as recited in claim 1 , wherein the second local cache differs from the third local cache in one or more of: (a) a performance capability, (b) a size, or (c) a type of storage device.

6. A method, comprising:
storing, by a first query accelerator node of a fleet of query accelerator nodes configured for a data store, wherein individual ones of the query accelerator nodes are executed at respective computing devices, a first replica of a first data item in a first local cache;
storing, by a second query accelerator node of the fleet, a second replica of the first data item in a second local cache;
in response to determining, at the first query accelerator node, that the first replica meets a first eviction criterion, removing the first replica from the first local cache without initiating a notification of the removal to the second query accelerator node; and
in response to receiving, at the second query accelerator node after the first replica has been removed from the first local cache, a first read request for the first data item from a first client-side component of the data store, transmitting at least a portion of the second replica to the first client-side component from the second local cache.

7. The method as recited in claim 6 , wherein the first eviction criterion comprises one or more of: (a) a least-recently-used criterion, (b) a shortest time-to-live criterion, (c) a data item size-based criterion, (d) a criterion based on a property of a client-side component on whose behalf the first replica is stored in the first local cache, or (e) a locality-based criterion.

8. The method as recited in claim 6 , wherein the first local cache differs in size from the second local cache.

9. The method as recited in claim 6 , wherein the first local cache comprises at least one persistent storage device, and wherein the second local cache does not comprise a persistent storage device.

10. The method as recited on claim 6 , further comprising:
in response to receiving, by the first query accelerator node after the first replica has been removed from the first local cache, a second read request for the first data item, obtaining another replica of the first data item from a first source identified according to a first read miss processing rule; and
in response to receiving, by the second query accelerator node after the second replica has been removed from the second local cache, a third read request for the first data item, obtaining a different replica of the first data item from a second source identified according to a second read miss processing rule.

11. The method as recited in claim 10 , wherein the data store comprises a plurality of storage nodes, wherein the fleet of query accelerator nodes comprises a master node and a plurality of non-master nodes, wherein the master node is configured to respond to write requests and read requests, wherein the non-master nodes are configured to respond to read requests, wherein the first query processing node is a non-master node, and wherein the first source comprises one of: (a) the master node, (b) a particular storage node of the plurality of storage nodes, or (c) a non-master node of the plurality of non-master nodes.

12. The method as recited in claim 6 , wherein the fleet of query accelerator nodes comprises a master node and a plurality of non-master nodes, wherein the master node is configured to respond to write requests and read requests, wherein the non-master nodes are configured to respond to read requests, the method further comprising:
propagating, by the master node, respective replicas of a second data item from a local cache of the master node to the first and second query accelerator nodes; and
determining, by the master node, that respective replicas of a third data item are not to be prop

Assignees

• Amazon Tech Inc

Inventors

• Muniswamy Reddy Kiran Kumar
• Sasidharan Anand
• Zaki Omer Ahmed
• O'Neill Brian

Classifications

• G06F12/0868

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0656

  Data buffering arrangements · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F16/24552

  Database cache management · CPC title